[Lemon-user] Removing redundant paths in digraph?

[Tim Tautges]

On 01/23/2011 03:34 AM, Kovács Péter wrote:
> 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
>

Yes, I think that would do it, with no need for arc removal.  I don't see any mention of that algorithm in Lemon, am I 
missing it, or is there just not one?  Doesn't seem terribly difficult to implement, so that's not a show-stopper.

- tim

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

-- 
================================================================
"You will keep in perfect peace him whose mind is
   steadfast, because he trusts in you."               Isaiah 26:3

              Tim Tautges            Argonne National Laboratory
          (tautges at mcs.anl.gov)      (telecommuting from UW-Madison)
          phone: (608) 263-8485      1500 Engineering Dr.
            fax: (608) 263-4499      Madison, WI 53706