Re: [jgrapht-users] Getting an ordered set of edges for graph cycles?

[H.N. de R. <hnr...@gr...>]

On Thu, Dec 19, 2013 at 05:26:30PM +0000, org...@io... 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