Improve: edge_clustering_centrality utility

[math1um]

The code (in invariants.sage, and called by 3 or more invariants) is theoretically efficient but takes forever even on a graph with 100 vertices.

It can be written much more efficiently. In particular, on each loop over the edges, it calls every single vertex in the graph. BUT there's no way that this test can pass unless the considered vertex is close to the edge.

Start by finding the dictionary g.distance_all_pairs(). then for any edge e=(u,w), find the list of vertices v where the distance(v,u)<=1 AND distance(v,w)<=1. then replace the iteration over all vertices in the graph with JUST iteration over this list.

[nvcleemp]

Finding all distances is still going to be rather inefficient. There are some other things wrong with that function as well. I will have a look.

[nvcleemp]

Can you test whether this version is efficient enough. Probably you already have some graphs for which it was too slow, so you can be a better judge of the gain. If this is fast enough, than the issue may be closed.

As a general rule it is inefficient to go through g.distance_all_pairs() to find vertices at distance 1. Just use g.neighbors(v) for that.

[yirkajk]

Running now. I'll update you once I get results.

[yirkajk]

I don't have exact timings since I just ran the update method on all efficient_invariants. But, before this change, the update method timed out on almost all graphs even with a 20 minute timeout. Now, it finished on every graph within the allotted time. So, yes, I think it's fast enough 😉. Closing this issue.