Re: [jgrapht-users] closeSimpleDirectedGraph() doesn't return

[John S. <js...@gm...>]

In general, directed graphs are not required to be acyclic, which is
why you don't receive any warning.  Class
org.jgrapht.experimental.dag.DirectedAcyclicGraph is intended for when
you need to prevent loops from being created.

If you have a huge graph, maybe it just takes a long time?  Looks like
the worst case running time for the current implementation should be
log2(|V|)*|E|^2.  FloydWarshall would probably do better.

JVS


On Mon, Apr 22, 2013 at 1:19 AM, Yi Lin <qi...@gm...> wrote:
> Hi all,
>
> I am trying to use JGraphT in my project.
>
> I used SimpleDirectedGraph to store my graph (the graph is dynamically
> generated, and huge). All the vertices and edges are added to the graph,
> it seems fine - no warning to say there is a loop.
>
> Then I tried to get transitive closure on the graph. So I called
> TransitiveClosure.INSTANCE.closeSimpleDirectedGraph(myGraph);
> However, the execution got stuck in this method and it didn't return.
>
> I tried to call new CycleDetector<V, E>(myGraph).detectCycles() before
> computing transitive closure, and it returns true.
>
> It seems weird to me now, since SimpleDirectedGraph should prompt a
> warning if there is any loop when an edge is added. There wasn't any
> warning, but CycleDectector reported cycles.
>
> Thus I am not sure what the problem is now. Possible cycles in the
> graph, or I used those APIs in a wrong way, or any known implementation
> problem with JGraphT (with
> CycleDetector/TransitiveClosure/SimpleDirectedGraph)?
>
> I could dump the graph, and check through it. But the graph is huge, I
> would rather not to walk through it unless I have to.
> I think I would better ask the question here for some suggestions. Any
> help would be appreciated. Thank you very much.
>
> Regards,
> Yi
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users