algorithm question

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

algorithm question

Peter Foelsche
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;
}




_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: algorithm question

Peter Foelsche

"Peter Foelsche" <[hidden email]> wrote in message
news:iv8fap$5ju$[hidden email]...

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;
> }


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: algorithm question

Peter Foelsche

"Peter Foelsche" <[hidden email]> wrote in message
news:iv8fia$6gl$[hidden email]...

>
> "Peter Foelsche" <[hidden email]> wrote in message
> news:iv8fap$5ju$[hidden email]...
>
> 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...


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: algorithm question

Gordon Woodhull
In reply to this post by Peter Foelsche

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

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: algorithm question

Peter Foelsche

"Gordon Woodhull" <[hidden email]> wrote in message
news:[hidden email]...

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


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users