[jgrapht-users] Directed Path Question

[Alexandros M. <al...@gm...>]

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.