Re: [Boost-users] algorithm question

Subject: Re: [Boost-users] algorithm question
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2011-07-09 02:20:35

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

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