[Lemon-user] Removing redundant paths in digraph?

[Kovács Péter]

Hi Tim,

LEMON does not provide a direct algorithm for your problem, but it 
provides tools that can be combined to solve it.

As far as I understand, you would like to keep the longest paths of the 
dependency graph, and remove all arcs that are not part of a longest path.

In a directed acyclic graph (DAG), you can easily determine the distance 
layers by using a topological ordering and a simple algorithm, which is 
described here:
http://en.wikipedia.org/wiki/Longest_path_problem#Weighted_directed_acyclic_graphs
I think, you would like to keep only those arcs, that connect nodes of 
neighboring layers.

Once you have assigned a layer number l(u) to each node u of the graph, 
you can easily detect which arcs are superfluous. l(v)>=l(u)+1 holds for 
each arc (u,v). If l(v)=l(u)+1, then this arc is necessary, and if 
l(v)>l(u)+1, then this arc is superfluous, it can be safely removed.
The sample code of the wikipedia page computes l(u) for each node (it is 
denoted by length_to[u]).

LEMON provides functions for topological sort, so you only need to 
implement the cited simple algorithm. The whole solution will be simple 
and it will run in linear time.

Please correct me if I overlook something.

Best regards,
Peter


> Hi all,
>     I have a ListDigraph that represents dependencies between nodes in the graph, for this example say 3 nodes, A, B, C,
> and 2 arcs, A-B and A-C.  Now I'd like to add a dependency B-C; after doing that, B will have ancestors A and C, and
> there will be two paths between A and B.  Since this is a dependency graph, there's no point in keeping the A-B arc,
> since B always has to wait for C anyway.  Is there an algorithm or combination of them in Lemon that would remove these
> sorts of things automatically?  I'm not formally trained in graph theory, but intuitively it seems like that could be
> phrased in terms of some of the path and flow algorithms.
>
> BTW, great package, I've started using it in a mesh generation library I'm developing (will send a link when it's ready
> for release).
>
> - tim
>