DirectedAcyclicGraph.h

Go to the documentation of this file.

#pragma once
#include "Object.h"
 
#include <map>
#include <list>
#include <stack>
#include <set>
#include <vector>
#include <queue>
#include <unordered_set>
 
namespace dyno {
    class DirectedAcyclicGraph
    {
    public:
        DirectedAcyclicGraph() {};
        ~DirectedAcyclicGraph();
 
        // Add an edge to DAG
        void addEdge(ObjectId v, ObjectId w);
 
        // Depth first traversal of the vertices
        std::vector<ObjectId>& topologicalSort(ObjectId v);
 
        // Depth first traversal of the vertices
        std::vector<ObjectId>& topologicalSort();
 
        size_t sizeOfVertex() const;
 
        size_t OtherVerticesSize() { return OtherVertices.size(); }
 
        std::set<ObjectId>& getOtherVertices() { return OtherVertices;}
 
        std::set<ObjectId>& vertices();
 
        std::map<ObjectId, std::unordered_set<ObjectId>>& edges();
 
        std::map<ObjectId, std::unordered_set<ObjectId>>& reverseEdges();
 
        void addOtherVertices(ObjectId v);
 
        void addtoRemoveList(ObjectId v);
 
        void removeID(ObjectId v = -1, ObjectId w = -1);
 
    private:
        // Functions used by topologicalSort
        void topologicalSortUtil(ObjectId v, std::map<ObjectId, bool>& visited, std::stack<ObjectId>& stack);
        void topologicalSortUtil(ObjectId v, std::map<ObjectId, bool>& visited);
 
    private:
        std::vector<ObjectId> mOrderVertices;
        std::set<ObjectId> mVertices;
        std::map<ObjectId, std::unordered_set<ObjectId>> mEdges;
        std::map<ObjectId, std::unordered_set<ObjectId>> mReverseEdges;
        std::set<ObjectId> OtherVertices;
        std::set<ObjectId> RemoveList;
    };
}