Quantcast

JGraphT cycle algorithms

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

JGraphT cycle algorithms

feedlivi@gmail.com
Hi there,

Has anyone used any of the cycle algorithms provided by org.jgrapht.alg.cycle (Tarjan, Johnson, etc)???

I’m running a code to detect cycles on a graph with 216 vertices and 1861 edges. Unfortunately, I’ve not been able to get an answer  because of a Java heap space error….it's just running out memory very quickly!!

Have you guys gone through a similar situation??? …..or just my graph is too large??

As far as I know Tarjan, Johnson, Tiernan, and the others are very efficient procedures.

Thanks.


Phil
------------------------------------------------------------------------------
_______________________________________________
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: JGraphT cycle algorithms

Rushang Karia
I guess your graph has too many cycles?

I looked at the source code for the Tarjan's cycle and it tries to find all cycles of the graph.
The algorithm is still efficient.

I think its just that the input size is very large (the # of cycles in your graph is too damn high) and the memory you provide is not enough given the input size.

Even if you have the most efficient algorithm in the world, if you provide an input size that is much larger than the resources you have it will still give an out of memory error!

I would try to give it a graph with 216 vertices but fewer # of cycles. Try using DIMACS graph examples. They have sample graphs with a fixed # of cycles and a fixed chromatic number.

> From: [hidden email]

> Date: Tue, 4 Aug 2015 10:53:34 -0400
> To: [hidden email]
> Subject: [jgrapht-users] JGraphT cycle algorithms
>
> Hi there,
>
> Has anyone used any of the cycle algorithms provided by org.jgrapht.alg.cycle (Tarjan, Johnson, etc)???
>
> I’m running a code to detect cycles on a graph with 216 vertices and 1861 edges. Unfortunately, I’ve not been able to get an answer because of a Java heap space error….it's just running out memory very quickly!!
>
> Have you guys gone through a similar situation??? …..or just my graph is too large??
>
> As far as I know Tarjan, Johnson, Tiernan, and the others are very efficient procedures.
>
> Thanks.
>
>
> Phil
> ------------------------------------------------------------------------------
> _______________________________________________
> jgrapht-users mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...