Quantcast

closeSimpleDirectedGraph() doesn't return

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

closeSimpleDirectedGraph() doesn't return

Yi Lin
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: closeSimpleDirectedGraph() doesn't return

John Sichi
Administrator
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 <[hidden email]> 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
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: closeSimpleDirectedGraph() doesn't return

Yi Lin
Yes, you are right.. I tried to be more patient waiting for the result
and did get the transitive closure.

Also thanks to Georg Hieronimus for letting me know the difference
between loop and cycle.

Regards,
Yi

On 23/04/13 10:40 , John Sichi wrote:

> 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 <[hidden email]> 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
>> [hidden email]
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...