Graph distances, how can I speed it up?

[Terry Reedy]

"Miki Tebeka" <tebeka at cs.bgu.ac.il> wrote in message
news:33803989.0206030235.4134d33e at posting.google.com...
> Hello All,
>
> I'm trying to calculate distances in a graph. (The ultimate goal is
> to calculate the distances between verbs in WordNet)
>
> The graph is built edge after edge and each time I recalculate the
> distances matrix. However this takes ages to complete. (will finish
in ~50H).

There is a reasonably efficient algorithm for computing the distance
between vertices in a graph.  I am sure that this is *much* more
efficient than doing so incrementally.  I am pretty sure that I would
be available in the graphical algorithms section of the C-coded Boost
package, which has a Python wrapper.  (Don't know details.)

>     Distances are held in hash table of pairs (x,y) -> distance.

A 2-d array would take about the same space and probably be quicker.
A 2-d Numerical Python array, which you would want for a large graph,
would be better both ways.

>     For each vertex a hash of all vertexes conncted to it is saved
>     to improve distance update.

As near as I can tell, you only access the lists of neighbors as
lists, so store them that way.

>         return self.forward.get(x, {}).keys()
>         return self.backwards.get(x, {}).keys()

But biggest boost will come from using C-coded function.

Terry J. Reedy