Thread: [jgrapht-users] Directed Path Question
Brought to you by:
barak_naveh,
perfecthash
From: Alexandros M. <al...@gm...> - 2007-06-18 07:23:34
|
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. |
From: John V. S. <js...@gm...> - 2007-06-18 07:54:26
|
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 |
From: Kyle L. <ky...@ar...> - 2007-06-18 18:22:03
|
If there are two edges from A to B, then remove one. If there is an edge from A to B, and a path of length n>1 from A to B then remove the edge. (path does not have edge because lack of cycles in graph). This probably can be done with matrix operations: 1) Make adjacency matrix A(1) 2) Perform A(n+1)=(A(n)*A(n))+A(n) until fix point achieved* 3) Perform M=A(n)*A(1) to get reach on path lengths > 1 4) Remove edges from graph found in M * Note "+" is cell-wise binary OR Warning: This is completely made up by a guy with rusty math skills. Be sure to verify algorithm. 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 > -- ---------------------------------------------------------------------- Kyle Lahnakoski ky...@ar... (416) 892-7784 Arcavia Software Ltd |