Quantcast

Topological sort ... branch behavior

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

Topological sort ... branch behavior

Cecilia Arenas

Hello,

I'm using Jgrapht to do a topological sort and I would like to get a specific behavior when finding branches:

Here's my example:

I have

Path 1: A - B - C - 1D - 1E - 1F

Path 2: A - B - C - 2D - 2E - 2F

What I would like to have after using the topological sort is: 
Either:
A - B - C - 1D - 1E - 1F - 2D - 2E - 2F

Or
A - B - C - 2D - 2E - 2F - 1D - 1E - 1F 


But what I get when using the Class TopologicalOrderIterator is:

A - B - C - 1D - 2D - 1E - 2E - 1F - 2F

Anyone could give me any suggestion about how to adapt the TopologicalOrderIerator or anything that might help me ?

Cheers,

--
Cecilia Arenas

------------------------------------------------------------------------------
See everything from the browser to the database with AppDynamics
Get end-to-end visibility with application monitoring from AppDynamics
Isolate bottlenecks and diagnose root cause in seconds.
Start your free trial of AppDynamics Pro today!
http://pubads.g.doubleclick.net/gampad/clk?id=48808831&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: Topological sort ... branch behavior

Sebastian Müller
Hi Cecilia,

I'm not a jgrapht developer, but your example sounds like depth-first search. There is a org.jgrapht.traverse.DepthFirstIterator<V,E> class for that.

Looking at the code of TopoligicalOrderIterator, the list of verteces is sorted by indegree, which makes changing it to suit your example rather complicated.


Sebastian


Am 20.07.2013 17:04, schrieb Cecilia Arenas:

Hello,

I'm using Jgrapht to do a topological sort and I would like to get a specific behavior when finding branches:

Here's my example:

I have

Path 1: A - B - C - 1D - 1E - 1F

Path 2: A - B - C - 2D - 2E - 2F

What I would like to have after using the topological sort is: 
Either:
A - B - C - 1D - 1E - 1F - 2D - 2E - 2F

Or
A - B - C - 2D - 2E - 2F - 1D - 1E - 1F 


But what I get when using the Class TopologicalOrderIterator is:

A - B - C - 1D - 2D - 1E - 2E - 1F - 2F

Anyone could give me any suggestion about how to adapt the TopologicalOrderIerator or anything that might help me ?

Cheers,

--
Cecilia Arenas


------------------------------------------------------------------------------
See everything from the browser to the database with AppDynamics
Get end-to-end visibility with application monitoring from AppDynamics
Isolate bottlenecks and diagnose root cause in seconds.
Start your free trial of AppDynamics Pro today!
http://pubads.g.doubleclick.net/gampad/clk?id=48808831&iu=/4140/ostg.clktrk


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


------------------------------------------------------------------------------
See everything from the browser to the database with AppDynamics
Get end-to-end visibility with application monitoring from AppDynamics
Isolate bottlenecks and diagnose root cause in seconds.
Start your free trial of AppDynamics Pro today!
http://pubads.g.doubleclick.net/gampad/clk?id=48808831&iu=/4140/ostg.clktrk
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...