VuoDirectedAcyclicGraph.hh

Go to the documentation of this file.

 
#pragma once
 
class VuoDirectedAcyclicGraph
{
public:
    class Vertex
    {
    public:
        virtual string key(void) = 0;
 
        virtual ~Vertex(void);
    };
 
    VuoDirectedAcyclicGraph(void);
    ~VuoDirectedAcyclicGraph(void);
    void addVertex(Vertex *vertex);
    void removeVertex(Vertex *vertex);
    Vertex * findVertex(const string &key);
    void addEdge(Vertex *fromVertex, Vertex *toVertex);
    vector<Vertex *> getDownstreamVertices(Vertex *vertex);
    vector<Vertex *> getUpstreamVertices(Vertex *vertex);
    set<Vertex *> getCycleVertices(void);
    string toString(bool showVertexAddresses=false);
 
private:
    static vector<Vertex *> getReachableVertices(Vertex *vertex, const map< Vertex *, vector<Vertex *> > &edges, set<Vertex *> &cycleVertices);
 
    map< Vertex *, vector<Vertex *> > edges;  // Adjacency list. Every vertex has a key in this map, even if it doesn't have any outgoing edges.
    map< Vertex *, vector<Vertex *> > downstreamVerticesCache;
    map< Vertex *, vector<Vertex *> > upstreamVerticesCache;
    bool cycleVerticesCacheReady;
    set<Vertex *> cycleVerticesCache;
 
    friend class VuoDirectedAcyclicNetwork;
};
 
class VuoDirectedAcyclicNetwork
{
public:
    vector<VuoDirectedAcyclicGraph::Vertex *> findVertex(const string &key);
    void addEdge(VuoDirectedAcyclicGraph *fromGraph, VuoDirectedAcyclicGraph *toGraph);
    vector<VuoDirectedAcyclicGraph::Vertex *> getDownstreamVertices(VuoDirectedAcyclicGraph::Vertex *vertex);
    vector<VuoDirectedAcyclicGraph::Vertex *> getUpstreamVertices(VuoDirectedAcyclicGraph::Vertex *vertex);
    string toString(bool showVertexAddresses=false);
 
private:
    static vector<VuoDirectedAcyclicGraph::Vertex *> getReachableVertices(VuoDirectedAcyclicGraph::Vertex *vertex, const map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> > &edges, bool isDownstream);
 
    map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> > edges;
};