Prev: Slimming down a tclkit
Next: Help removing remote files with Expect
From: Andreas Kupries on 3 Feb 2010 02:04
tomk <krehbiel.tom(a)gmail.com> writes:

>> > My first impulse here would be to perform a depth first search of the graph to
>> > compute a spanning tree and then sort the tree. Some advanced compiler books
>> > might be a good resource since flow graphs have many of these properties and
>> > compiler optimizations do a lot of graph manipulations.

>> That's a thought.  My initial idea was to use a topological sorting
>> algorithm that detects cycles; and when it has gone as far as it can,
>> remove dependencies arbitrarily until it can make more progress.  If I
>> mark where the initial topo sort stops, then I know that those nodes,
>> at least, can be computed once; I only need to iterate on the
>> subsequent ones.
>>
>> As with everything else, I suppose the answer is to give it a try and
>> measure the results.
>
> FYI - if you're doing this in tcl then you can use struct::graph
> (Create and manipulate directed graph objects) from tcllib to test out
> ideas.

Not to forget the adjunct package struct::graph::op, which implements
quite a number of algorithms now, courtesy of two Google Summer Of
Code's.

http://docs.activestate.com/activetcl/8.5/tcllib/struct/graphops.html

Kruskal and Prim are Spanning Tree algorithms.
Tarjan computes strongly connected components = cycles.

--
So long,
Andreas Kupries <akupries(a)shaw.ca>
<http://www.purl.org/NET/akupries/>
Developer @ <http://www.activestate.com/>
-------------------------------------------------------------------------------
From: Will Duquette on 3 Feb 2010 11:01
On Feb 2, 11:04 pm, Andreas Kupries <akupr...(a)shaw.ca> wrote:
> tomk <krehbiel....(a)gmail.com> writes:
> >> > My first impulse here would be to perform a depth first search of the graph to
> >> > compute a spanning tree and then sort the tree. Some advanced compiler books
> >> > might be a good resource since flow graphs have many of these properties and
> >> > compiler optimizations do a lot of graph manipulations.
> >> That's a thought.  My initial idea was to use a topological sorting
> >> algorithm that detects cycles; and when it has gone as far as it can,
> >> remove dependencies arbitrarily until it can make more progress.  If I
> >> mark where the initial topo sort stops, then I know that those nodes,
> >> at least, can be computed once; I only need to iterate on the
> >> subsequent ones.
>
> >> As with everything else, I suppose the answer is to give it a try and
> >> measure the results.
>
> > FYI - if you're doing this in tcl then you can use struct::graph
> > (Create and manipulate directed graph objects) from tcllib to test out
> > ideas.
>
> Not to forget the adjunct package struct::graph::op, which implements
> quite a number of algorithms now, courtesy of two Google Summer Of
> Code's.
>
> http://docs.activestate.com/activetcl/8.5/tcllib/struct/graphops.html
>
> Kruskal and Prim are Spanning Tree algorithms.
> Tarjan computes strongly connected components = cycles.

Aha! Exactly the sort of thing I was looking for. Thanks!

WIll
First  |  Prev  | 
Pages: 1 2 3 4
Prev: Slimming down a tclkit
Next: Help removing remote files with Expect