Re: [jgrapht-users] Maximally connected component for dependencies?

[<org...@io...>]

On Tue, 31 Dec 2013 17:05:50 +0100
"H.N. de Ridder" <hnr...@gr...> wrote:

> Hi,
> 
> no, the ConnectivityInspector ignores the direction of the edges. So if your graph has edges s->t->u and you call connectedSetOf(t), you will get {s, t, u} as the result. If you want to get precisely those nodes that are reachable from t (traversing edges in the "proper" direction only), you can do a breadth first search from t with BreadthFirstInspector.

Yes, makes sense. Someone recommended DepthFirstInspector off-list, so I attempted
that first (there are a few other properties of the depth first search that I can
make use of in the implementation).

> 
> If you want to do this for many nodes, it may be faster to first calculate the transitive closure of the graph and then check the out-neighbours of your node. The transitive closure G' of G has an edge u->v precisely when there is a path u==>v in G.

Right.

> 
> Do you have a unique top level term from which all useful terms are reachable, or is your construction more complicated?

The top level term is chosen manually at compile-time in much the same way that the
top-level term is chosen at run-time in Java.

Thanks!

M