[tor-bugs] #16750 [Onionoo]: Add improved family measure to Onionoo

[Tor Bug Tracker & Wiki]

#16750: Add improved family measure to Onionoo
----------------------------+----------------------------------
 Reporter:  virgilgriffith  |          Owner:
     Type:  enhancement     |         Status:  new
 Priority:  normal          |      Milestone:
Component:  Onionoo         |        Version:  Tor: unspecified
 Keywords:  roster          |  Actual Points:
Parent ID:                  |         Points:
----------------------------+----------------------------------
 This is a follow-up from the graphs I've posted before.  Particularly,

 * https://dl.dropboxusercontent.com/u/3308162/family_graph_uncolored.pdf
 *
 https://dl.dropboxusercontent.com/u/3308162/family_graph_colored_by_effective_family.pdf

 We want the above algorithm implemented in Onionoo.  Here's how it works:

 For each entry in the MyFamily list...
 1. truncate all fingerprints to 40 characters
 2. remove all fingerprints <40 characters.
 3. Relays A and B are in the same effective_family if and only if, via
 *symmetric links only*, A can reach each relay B.  You can use the
 standard iterative depth-first-search on: https://en.wikipedia.org/wiki
 /Depth-first_search
 4. Finally, in Onionoo, each relay has a (sorted) list of the fingerprints
 of its effective_family.

 Misc:
 * If the relay's own fingerprint appears as part of its effective_family,
 remove the fingerprint.
 * As far as I know no one is using the current effective_family measure.
 If not, I recommend replacing the previous effective_family with the
 above.
 * If someone wants to keep the existing effective_family, I suggest doing
 the above but calling it the "extended_family".  Either is fine by me.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/16750>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online