Add improved family measure to Onionoo
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...
- truncate all fingerprints to 40 characters
- remove all fingerprints <40 characters.
- 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
- 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.