Re: [Boost-users] algorithm question

Subject: Re: [Boost-users] algorithm question
From: Peter Foelsche (foelsche_at_[hidden])
Date: 2011-07-09 14:28:32

"Gordon Woodhull" <gordon_at_[hidden]> wrote in message 
news:62FB31DF-8393-4DB1-B8F7-63FE4E2B522D_at_woodhull.com...
>
> On Jul 8, 2011, at 10:44 PM, Peter Foelsche wrote:
>
>> Dear All,
>>
>> I'm trying to get some objects sorted.
>> Every object has a set of pointers to other objects,
>> which need to come before this object (or are considered smaller than 
>> this object).
>
> No cycles, right?  This sounds and looks like your standard topological 
> sort, O(N).

thanks a lot -- I learned something:
http://en.wikipedia.org/wiki/Topological_sorting

I'll read up about it...

Peter

> You could put your objects in a graph and use the algo in Boost.Graph.
>
> Or you could do the depth first search yourself with a function that first 
> recursively adds all predecessors to the sorted list, then adds the 
> current item.  Then keep calling this with any items not yet added to the 
> sorted list.  (Topological sort is depth first search with a postorder 
> traversal.)
>
> HTH,
> Gordon