Graph distances, how can I speed it up?

[Jiri Baum]

Miki Tebeka:
> 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).

The matrix version of this might be more efficient, the one that solves the
whole thing as a set of simultaneous equations... I think it'd involve one
matrix inversion to begin with, and then a dot product each time you need a
distance, but I'd have to check.

Make sure you use a sparse matrix library if your matrix is sparse (and it
will be) - it can take quite some shortcuts.


Jiri
-- 
Jiri Baum <jiri at baum.com.au>           http://www.csse.monash.edu.au/~jirib
  MAT LinuxPLC project --- http://mat.sf.net --- Machine Automation Tools