[Lemon-user] Removing redundant paths in digraph?

[Tim Tautges]

Aha, fantastic; I'm a meshing guy, so when I saw topological sort the first time, I ignored it thinking it only worked 
with graphs representing a topology like what we see in meshes.

- tim

On 01/24/2011 10:44 PM, Alpár Jüttner wrote:
> Hi,
>
>>> 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.
>
> LEMON does have topological sort algorithm:
>
> http://lemon.cs.elte.hu/pub/doc/1.2.1/a00538.html#ga67cdef21788938be90604624f5af8569
>
> Alpar
>
>

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