algorithm question
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). It is kind of a make-tool algorithm. I can imagine the straight-forward way to attack this -- searching. Is there some more elegant way I'm missing? The number of objects not small. I tried to write some recursive functor to be passed to std::sort -- caching the result of previous comparisions -- but I was not successful. My brain is hurting... Thanks Peter struct object { std::set<object*> m_sPredecessors; }; // to be sorted: std::list<object*> sList; std::list<object*> sort(std::list<object*> _sList) { std::set<object*> sSet; std::list<object*> sSorted; while (_sList.size()) for (std::list<object*>::iterator p = _sList.begin(), pNext = p, pEnd = _sList.end(); p != pEnd; p = pNext) { ++pNext; bool bFound = false; for (std::set<object*>::const_iterator p1 = (*p)->m_sPredecessors.begin(), p1End = (*p)->m_sPredecessors.end(); p1 != p1End; ++p1) if (sSet.find(*p1) == sSet.end()) { bFound = true; break; } if (!bFound) { sSorted.push_back(*p); _sList.erase(p); } } return sSorted; }
"Peter Foelsche" <foelsche@sbcglobal.net> wrote in message news:iv8fap$5ju$1@dough.gmane.org... something was missing:
std::list<object*> sort(std::list<object*> _sList) { std::set<object*> sSet; std::list<object*> sSorted; while (_sList.size()) for (std::list<object*>::iterator p = _sList.begin(), pNext = p, pEnd = _sList.end(); p != pEnd; p = pNext) { ++pNext; bool bFound = false; for (std::set<object*>::const_iterator p1 = (*p)->m_sPredecessors.begin(), p1End = (*p)->m_sPredecessors.end(); p1 != p1End; ++p1) if (sSet.find(*p1) == sSet.end()) { bFound = true; break; } if (!bFound) { sSorted.push_back(*p); sSet.insert(*p); _sList.erase(p); } } return sSorted; }
"Peter Foelsche" <foelsche@sbcglobal.net> wrote in message news:iv8fia$6gl$1@dough.gmane.org...
"Peter Foelsche" <foelsche@sbcglobal.net> wrote in message news:iv8fap$5ju$1@dough.gmane.org...
something was missing:
std::list<object*> sort(std::list<object*> _sList) { std::set<object*> sSet; std::list<object*> sSorted; while (_sList.size()) for (std::list<object*>::iterator p = _sList.begin(), pNext = p, pEnd = _sList.end(); p != pEnd; p = pNext) { ++pNext; bool bFound = false; for (std::set<object*>::const_iterator p1 = (*p)->m_sPredecessors.begin(), p1End = (*p)->m_sPredecessors.end(); p1 != p1End; ++p1) if (sSet.find(*p1) == sSet.end()) { bFound = true; break; } if (!bFound) { sSorted.push_back(*p); sSet.insert(*p); _sList.erase(p); } } return sSorted; }
ok -- one could use std::includes http://www.cplusplus.com/reference/algorithm/includes/ to find out if all elements of the set attached to the object currently considered are contained in the local sSet instead of iterating...
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
"Gordon Woodhull" <gordon@woodhull.com> wrote in message news:62FB31DF-8393-4DB1-B8F7-63FE4E2B522D@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
participants (2)
-
Gordon Woodhull -
Peter Foelsche