Re: [jgrapht-users] Directed Path Question

[Kyle L. <ky...@ar...>]

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