Class DirectedGraphTopologicalSort

Synopsis

#include <Source/Falcor/Utils/Algorithm/DirectedGraphTraversal.h>

class DirectedGraphTopologicalSort

Description

No description yet.

Methods

sort

Source

Lines 166-210 in Source/Falcor/Utils/Algorithm/DirectedGraphTraversal.h.

class DirectedGraphTopologicalSort
{
public:
    static std::vector<uint32_t> sort(DirectedGraph* pGraph)
    {
        DirectedGraphTopologicalSort ts(pGraph);
        for (uint32_t i = 0; i < ts.mpGraph->getCurrentNodeId(); i++)
        {
            if (ts.mVisited[i] == false && ts.mpGraph->getNode(i))
            {
                ts.sortInternal(i);
            }
        }
        std::vector<uint32_t> result;
        result.reserve(ts.mStack.size());
        while (ts.mStack.empty() == false)
        {
            result.push_back(ts.mStack.top());
            ts.mStack.pop();
        }
        return result;
    }
private:
    DirectedGraphTopologicalSort(DirectedGraph* pGraph) : mpGraph(pGraph), mVisited(pGraph->getCurrentNodeId(), false) {}
    DirectedGraph* mpGraph;
    std::stack<uint32_t> mStack;
    std::vector<bool> mVisited;
    void sortInternal(uint32_t node)
    {
        mVisited[node] = true;
        const DirectedGraph::Node* pNode = mpGraph->getNode(node);
        for (uint32_t e = 0; e < pNode->getOutgoingEdgeCount(); e++)
        {
            uint32_t nextNode = mpGraph->getEdge(pNode->getOutgoingEdge(e))->getDestNode();
            if (!mVisited[nextNode])
            {
                sortInternal(nextNode);
            }
        }
        mStack.push(node);
    }
};





Add Discussion as Guest

Log in