[Lemon-user] Removing redundant paths in digraph?

[Kovács Péter]

Hi Tim,

Yes, I was wrong. I'm sorry. E.g. if the dependencies are A->B, B->C, 
D->C, then D->C should not be removed.

 >> 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.
 >
 > Not quite. If there are nodes in the shorter path that are not part
 > of the longer paths, those arcs most be kept (to properly reflect the
 > dependency on those other nodes). As near as I can tell, this only
 > happens when there are longer paths between a node and a direct
 > (distance=1) ancestor. The tricky part here is I want to keep the
 > longer paths, not the shorter one.

I mean, an arc should be kept if and only if there are nodes u and v, 
for which a longest u->v path contains this arc. It seems to be correct, 
but the proposed method is not sufficient for making this distinction 
for all arcs.

> The reason I think I need to remove this short path is because, if I
> don't, a BFS traversal will visit that node through the short path
> before the nodes along the longer path have been visited, which won't be
> right (need to visit a node only after all its ancestors have been
> visited).

What about using a topological ordering instead of a BFS traversal? As 
far as I see, it would solve your problem. Do you need this arc removal 
procedure at all? Don't you need just a topological sort?
http://en.wikipedia.org/wiki/Topological_sorting

> Thanks for your help.
>
> - tim

Peter

>
>>
>> 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
>>>
>>
>