[Lemon-user] Removing redundant paths in digraph?

[Tim Tautges]

On 01/22/2011 04:23 PM, Kovács Péter wrote:
> 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.

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.

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

Thanks for your help.

- tim

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