Boost logo

Boost Users :

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

I'll read up about it...


> 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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at