Incrementally update strongly connected components and topological order

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
Report Content as Inappropriate

Incrementally update strongly connected components and topological order

Hello everyone,
I have a directed graph which I modify continuously. I need to
calculate the connected components and the topology for each of these
components, being performance critical. My questions are:

1. How do I get the components (not strong) from a DAG? I have seen
that the ConnectivityInspector doesn't have any method to retrieve the
list of components. The method connectedSets returns a list of sets of
vertex, so I would need then to get the related edges for each set in
the list and construct the corresponding component. Another way might be
to create first the undirected graph and calculate the strongly
connected components, but that seems to me a bit of overhead. Is there
no other easier and faster(performance is critical) way to do that?

2. Every time I update the graph I would like to update boths,
components and topology, in an incremental manner without the need of
recalculating everything from scratch. Is it possible to do that?


Slashdot TV.  Videos for Nerds.  Stuff that Matters.
jgrapht-users mailing list
[hidden email]