Re: [igraph] Utilizing previous calculations for performance

[Gábor Csárdi]

Data structures are designed with the required (or usual) operations
on them in mind. Storing more information about the graph can be good
in some cases and storing the same piece of information can be bad in
others.

Storing all the shortest paths in a graph may requires a lot of
storage, at least O(n^2), so it would only make sense if you can
utilize it in some "slower" algorithm, e.g. one with exponential
running time. I don't think that they help much for betweenness, that
is an O(n^2 log n) algorithm.

Gabor

On Sat, Jan 24, 2009 at 11:39 PM, Chris Wj <address@hidden> wrote:
> This is just a thought on performance for graph data structures...
>
> Are there algorithms that would benefit from the calculations already made
> on a graph? For example, if you calculated a shortest path for a set of
> vertices, you may not need to calculate them again when you call a
> betweenness function. Of course, upon graph change/alteration, you would
> have to reset everything as the calculations would be invalid. Also, this
> type of model would require more memory for keeping the additional
> information around. Thoughts?
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM