Re: [jgrapht-users] Directed Path Question

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

For directedPathExists, you can use 
DijkstraShortestPath.findPathBetween, or DepthFirstIterator.

JVS

Alexandros Marinos wrote:
> Hello JGraphT team,
> 
> First of all, i'd like to congratulate you on the excelent work you have 
> put in making this library a stable and useful piece of open source 
> software. On to my problem:
> 
> I'll start with my general problem, continue with the solution strategy 
> i have followed so i can get to the specific problem i have encountered. 
> If anyone knows of a solution/algorithm that i can apply at an earlier 
> part of the process, that is welcome too.
> 
> I am starting with an unweighted directed graph and I am attempting to 
> find its Minimum Equivalent Graph. Essentially a MEG is a graph that has 
> the minimum number of edges from the original graph but maintains the 
> same connectivity properties. Things are not so difficult because my 
> Graph is acyclical.
> 
> My approach is to remove each edge and see if there is a path from 
> source to destination vertex. Essentially i am checking to see if there 
> is an alternative path. If there is no path, i add the edge back. I am 
> not sure 100% if this is efficient theoretically but i think it will do 
> for now untill a better solution comes up.
> 
> However, pathExists does not work for directed paths as is stated in the 
> documentation.
> So i am stuck without having a way of finding if there is a directed 
> path that leads from one vertex to another. If there is no such 
> algorithm implemented in the library i will have to implement one on my 
> own, which i am trying to avoid. However, if there is no solution 
> currently, i would be happy to write and contribute any relevant code 
> that is required.
> 
> So, if anyone has any ideas on how to solve either my general or my 
> specific problem i would be happy to hear them. If there is no solution 
> currently implemented, i would appreciate information on what would be 
> the most proper place in the library to implement (either 
> directedPathExists or findMinimumEquivalentGraph) and i can make an 
> attempt on my own.
> 
> Best,
> Alexandros.
> 
> 
> ------------------------------------------------------------------------
> 
> -------------------------------------------------------------------------
> This SF.net email is sponsored by DB2 Express
> Download DB2 Express C - the FREE version of DB2 express and take
> control of your XML. No limits. Just data. Click to get it now.
> http://sourceforge.net/powerbar/db2/
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users