Maximally connected component for dependencies?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Maximally connected component for dependencies?

org.jgrapht
'Lo.

As mentioned previously, I'm using jgrapht to handle dependencies in
a small programming language I'm developing. I was originally only using
the library to handle module imports, but I've since moved to using the
library to track dependencies between all types and terms in the
language.

For example: In the term graph, if a term t contains a reference to a
term u, the graph contains an edge from t -> u.

I'd like to use the connectivity information during code generation to
exclude all unreferenced terms from the final program. Is the
ConnectivityInspector the right way to handle this? Specifically, given
a "top level" term t, I want all of those terms to which t refers, and
the terms to which those terms refer, and so on, and so on, excluding
any otherwise unreferenced terms.

I think that basically means instantiating a new ConnectivityInspector
for the term graph and then calling connectedSetOf(t)?

Am I correct in thinking that, given that the graph is directed and
acyclic, that I won't get terms that depend on t (vertices with
outgoing edges to t)? If that's correct, then presumably I *would*
get those terms if the graph was undirected?

Apologies if these are blindingly obvious questions. I'm not all that
familiar with graph algorithms.

M




------------------------------------------------------------------------------
Rapidly troubleshoot problems before they affect your business. Most IT
organizations don't have a clear picture of how application performance
affects their revenue. With AppDynamics, you get 100% visibility into your
Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro!
http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Maximally connected component for dependencies?

H.N. de Ridder
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.

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.

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

Regards,
  Ernst

----- Reply message -----
From: [hidden email]
To: <[hidden email]>
Subject: [jgrapht-users] Maximally connected component for dependencies?
Date: Mon, Dec 30, 2013 21:32


'Lo.

As mentioned previously, I'm using jgrapht to handle dependencies in
a small programming language I'm developing. I was originally only using
the library to handle module imports, but I've since moved to using the
library to track dependencies between all types and terms in the
language.

For example: In the term graph, if a term t contains a reference to a
term u, the graph contains an edge from t -> u.

I'd like to use the connectivity information during code generation to
exclude all unreferenced terms from the final program. Is the
ConnectivityInspector the right way to handle this? Specifically, given
a "top level" term t, I want all of those terms to which t refers, and
the terms to which those terms refer, and so on, and so on, excluding
any otherwise unreferenced terms.

I think that basically means instantiating a new ConnectivityInspector
for the term graph and then calling connectedSetOf(t)?

Am I correct in thinking that, given that the graph is directed and
acyclic, that I won't get terms that depend on t (vertices with
outgoing edges to t)? If that's correct, then presumably I *would*
get those terms if the graph was undirected?

Apologies if these are blindingly obvious questions. I'm not all that
familiar with graph algorithms.

M




------------------------------------------------------------------------------
Rapidly troubleshoot problems before they affect your business. Most IT
organizations don't have a clear picture of how application performance
affects their revenue. With AppDynamics, you get 100% visibility into your
Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro!
http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
Rapidly troubleshoot problems before they affect your business. Most IT
organizations don't have a clear picture of how application performance
affects their revenue. With AppDynamics, you get 100% visibility into your
Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro!
http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Maximally connected component for dependencies?

org.jgrapht
In reply to this post by org.jgrapht
On Tue, 31 Dec 2013 17:05:50 +0100
"H.N. de Ridder" <[hidden email]> 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

------------------------------------------------------------------------------
Rapidly troubleshoot problems before they affect your business. Most IT
organizations don't have a clear picture of how application performance
affects their revenue. With AppDynamics, you get 100% visibility into your
Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro!
http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users