Quantcast

Getting an ordered set of edges for graph cycles?

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

Getting an ordered set of edges for graph cycles?

org.jgrapht
Hello.

I'm attempting to use jgrapht to handle dependencies in a small
programming language.

Essentially, I want to ensure that a "module" can only import known
modules and that imports cannot introduce cyclic dependencies. I want
to give good error messages when the user manages either of the
previous errors: A list of the import statements that caused the cycle.

Something like:

error: cyclic import detected
     import of N at m.z:23
  -> import of M at n.z:12
  -> import of N at m.z:23

I've tried the following:

1. Use a DirectedGraph where modules are the vertices and import
declarations are the edges. This allows me to catch imports of unknown
modules by catching IllegalArgumentExceptions raised by addEdge. I
then run the CycleDetector after each addition of an edge.
Unfortunately, the CycleDetector can only return a set of vertices
rather than the edges (so I can't directly tell the user exactly which
series of import declarations caused the cycle). It also comes with a
rather scary warning that it might not actually catch all cycles (and
recommends the use of the StrongConnectivityInspector, but doesn't say
exactly how to use it and the documentation is non-obvious).

2. Use a DirectedAcyclicGraph. This allows me to catch imports of
unknown modules by checking to see if an edge could actually be
inserted (the boolean return value of addDagEdge). It also raises
exceptions when cycles are introduced, but this gives me even less
information than the CycleDetector (it just tells me that they've
happened, not why).

Is there some better way to achieve what I want? My ideal scenario is
that I add edges to graphs and upon adding an edge, I get a list of all
the *edges and vertices* that led to a cycle in some well-defined order.

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
|  
Report Content as Inappropriate

Re: Getting an ordered set of edges for graph cycles?

H.N. de Ridder
On Thu, Dec 19, 2013 at 05:26:30PM +0000, [hidden email] wrote:

> Hello.
>
> I'm attempting to use jgrapht to handle dependencies in a small
> programming language.
>
> Essentially, I want to ensure that a "module" can only import known
> modules and that imports cannot introduce cyclic dependencies. I want
> to give good error messages when the user manages either of the
> previous errors: A list of the import statements that caused the cycle.
>
> Something like:
>
> error: cyclic import detected
>      import of N at m.z:23
>   -> import of M at n.z:12
>   -> import of N at m.z:23
>
> I've tried the following:
>
> 1. Use a DirectedGraph where modules are the vertices and import
> declarations are the edges. This allows me to catch imports of unknown
> modules by catching IllegalArgumentExceptions raised by addEdge. I
> then run the CycleDetector after each addition of an edge.
> Unfortunately, the CycleDetector can only return a set of vertices
> rather than the edges (so I can't directly tell the user exactly which
> series of import declarations caused the cycle). It also comes with a
> rather scary warning that it might not actually catch all cycles (and
> recommends the use of the StrongConnectivityInspector, but doesn't say
> exactly how to use it and the documentation is non-obvious).

I think the warning for findCyclesContainingVertex(v) means that the Set it
returns might not contain every cycle containing v, but it will contain at
least one cycle containing v. In any case your second approach seems to me
the simpler one:

> 2. Use a DirectedAcyclicGraph. This allows me to catch imports of
> unknown modules by checking to see if an edge could actually be
> inserted (the boolean return value of addDagEdge). It also raises
> exceptions when cycles are introduced, but this gives me even less
> information than the CycleDetector (it just tells me that they've
> happened, not why).

If adding an edge u->v to G would create a cycle that wasn't there before, then
G contains a path v==>u. You can find this path using e.g.
DijkstraShortestPath, which can tell you both the vertices and edges on the
path in the proper order (getPath()).

Hope this helps,
   Ernst

P.S. DirectedAcyclicGraph is in the experimental package. Does anybody know
how reliable it is? The unit test seems quite thorough.

--
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org

------------------------------------------------------------------------------
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
|  
Report Content as Inappropriate

Re: Getting an ordered set of edges for graph cycles?

org.jgrapht
On Thu, 19 Dec 2013 20:26:38 +0100
"H.N. de Ridder" <[hidden email]> wrote:
>
> If adding an edge u->v to G would create a cycle that wasn't there before, then
> G contains a path v==>u. You can find this path using e.g.
> DijkstraShortestPath, which can tell you both the vertices and edges on the
> path in the proper order (getPath()).
>
> Hope this helps,
>    Ernst

Ah, thank you. Works perfectly!

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
Loading...