VuoDirectedAcyclicGraph.cc

Go to the documentation of this file.

 
#include "VuoDirectedAcyclicGraph.hh"
#include <sstream>
 
VuoDirectedAcyclicGraph::Vertex::~Vertex(void)
{
}
 
VuoDirectedAcyclicGraph::VuoDirectedAcyclicGraph(void)
{
    cycleVerticesCacheReady = false;
}
 
VuoDirectedAcyclicGraph::~VuoDirectedAcyclicGraph(void)
{
    for (map< Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
        delete i->first;
}
 
void VuoDirectedAcyclicGraph::addVertex(Vertex *vertex)
{
    edges[vertex];
}
 
void VuoDirectedAcyclicGraph::removeVertex(Vertex *vertex)
{
    for (map< Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
    {
        for (vector<Vertex *>::iterator j = i->second.begin(); j != i->second.end(); )
        {
            if (*j == vertex)
                j = i->second.erase(j);
            else
                ++j;
        }
    }
 
    for (map< Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); )
    {
        if (i->first == vertex)
            edges.erase(i++);
        else
            ++i;
    }
 
    delete vertex;
 
    downstreamVerticesCache.clear();
    upstreamVerticesCache.clear();
    cycleVerticesCacheReady = false;
    longestDownstreamPathsCache.clear();
}
 
VuoDirectedAcyclicGraph::Vertex * VuoDirectedAcyclicGraph::findVertex(const string &key)
{
    for (map< Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
        if (i->first->key() == key)
            return i->first;
 
    return NULL;
}
 
void VuoDirectedAcyclicGraph::addEdge(Vertex *fromVertex, Vertex *toVertex)
{
    if (find(edges[fromVertex].begin(), edges[fromVertex].end(), toVertex) == edges[fromVertex].end())
    {
        edges[fromVertex].push_back(toVertex);
        edges[toVertex];
    }
 
    downstreamVerticesCache.clear();
    upstreamVerticesCache.clear();
    cycleVerticesCacheReady = false;
    longestDownstreamPathsCache.clear();
}
 
vector<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicGraph::getDownstreamVertices(Vertex *vertex)
{
    map< Vertex *, vector<Vertex *> >::iterator iter = downstreamVerticesCache.find(vertex);
    if (iter != downstreamVerticesCache.end())
        return iter->second;
 
    set<Vertex *> unused;
    vector<Vertex *> downstreamVertices = getReachableVertices(vertex, edges, unused);
 
    downstreamVerticesCache[vertex] = downstreamVertices;
 
    return downstreamVertices;
}
 
vector<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicGraph::getUpstreamVertices(Vertex *vertex)
{
    map< Vertex *, vector<Vertex *> >::iterator iter = upstreamVerticesCache.find(vertex);
    if (iter != upstreamVerticesCache.end())
        return iter->second;
 
    map< Vertex *, vector<Vertex *> > backEdges;
    for (map< Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
    {
        for (vector<Vertex *>::iterator j = i->second.begin(); j != i->second.end(); ++j)
            if (find(backEdges[*j].begin(), backEdges[*j].end(), i->first) == backEdges[*j].end())
                backEdges[*j].push_back(i->first);
 
        backEdges[i->first];
    }
 
    set<Vertex *> unused;
    vector<Vertex *> upstreamVertices = getReachableVertices(vertex, backEdges, unused);
 
    upstreamVerticesCache[vertex] = upstreamVertices;
 
    return upstreamVertices;
}
 
set<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicGraph::getCycleVertices(void)
{
    if (cycleVerticesCacheReady)
        return cycleVerticesCache;
 
    set<Vertex *> cycleVertices;
    for (map< Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
    {
        set<Vertex *> c;
        getReachableVertices(i->first, edges, c);
        cycleVertices.insert(c.begin(), c.end());
    }
 
    cycleVerticesCacheReady = true;
    cycleVerticesCache = cycleVertices;
 
    return cycleVertices;
}
 
int VuoDirectedAcyclicGraph::getLongestDownstreamPath(Vertex *vertex)
{
    auto iter = longestDownstreamPathsCache.find(vertex);
    if (iter != longestDownstreamPathsCache.end())
        return iter->second;
 
    int longest = -1;
    for (Vertex *v : getDownstreamVertices(vertex))
    {
        int curr = getLongestDownstreamPath(v);
        longest = std::max(longest, curr);
    }
 
    return longest + 1;
}
 
vector<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicGraph::getReachableVertices(Vertex *vertex,
                                                                                        const map< Vertex *, vector<Vertex *> > &edges,
                                                                                        set<Vertex *> &cycleVertices)
{
    map<Vertex *, vector<Vertex *> > reachableVertices;
 
    if (edges.find(vertex) == edges.end())
        return vector<Vertex *>();
 
    list<Vertex *> toVisit;  // Used as a stack, except for a call to find().
    toVisit.push_back(vertex);
 
    while (! toVisit.empty())
    {
        // Visit the vertex at the top of the stack.
        Vertex *currVertex = toVisit.back();
 
        set<Vertex *> nextVertices;
        bool areCurrVerticesComplete = true;
 
        // Consider each vertex immediately downstream of this vertex.
        map< Vertex *, vector<Vertex *> >::const_iterator edgesIter = edges.find(currVertex);
        if (edgesIter != edges.end())
        {
            for (vector<Vertex *>::const_iterator j = edgesIter->second.begin(); j != edgesIter->second.end(); ++j)
            {
                Vertex *nextVertex = *j;
                nextVertices.insert(nextVertex);
 
                map<Vertex *, vector<Vertex *> >::iterator nextNextVerticesIter = reachableVertices.find(nextVertex);
                if (nextNextVerticesIter != reachableVertices.end())
                {
                    // The downstream vertex has already been visited, so add its downstream vertices to this vertex's.
                    nextVertices.insert( nextNextVerticesIter->second.begin(), nextNextVerticesIter->second.end() );
                }
                else
                {
                    if (find(toVisit.begin(), toVisit.end(), nextVertex) != toVisit.end())
                    {
                        // The downstream vertex is already on the stack, so there's a cycle.
                        cycleVertices.insert(nextVertex);
                    }
                    else
                    {
                        // The downstream vertex has not yet been visited, so add it to the stack.
                        toVisit.push_back(nextVertex);
                        areCurrVerticesComplete = false;
                    }
                }
            }
        }
 
        if (areCurrVerticesComplete)
        {
            reachableVertices[currVertex].insert(reachableVertices[currVertex].end(), nextVertices.begin(), nextVertices.end());
            toVisit.pop_back();
        }
    }
 
    return reachableVertices[vertex];
}
 
string VuoDirectedAcyclicGraph::toString(bool showVertexPointers)
{
    ostringstream ss;
 
    for (map< Vertex *, vector<Vertex *> >::iterator i = edges.begin(); i != edges.end(); ++i)
    {
        ss << i->first->key();
        if (showVertexPointers)
            ss << " (" << i->first << ")";
        ss << " ->";
 
        for (Vertex *vertex : i->second)
        {
            ss << " " << vertex->key();
            if (showVertexPointers)
                ss << " (" << vertex << ")";
        }
 
        ss << "\n";
    }
 
    return ss.str();
}
 
vector<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicNetwork::findVertex(const string &key)
{
    vector<VuoDirectedAcyclicGraph::Vertex *> foundVertices;
 
    for (map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::const_iterator i = edges.begin(); i != edges.end(); ++i)
    {
        VuoDirectedAcyclicGraph::Vertex *vertex = i->first->findVertex(key);
        if (vertex)
            foundVertices.push_back(vertex);
    }
 
    return foundVertices;
}
 
void VuoDirectedAcyclicNetwork::addEdge(VuoDirectedAcyclicGraph *fromGraph, VuoDirectedAcyclicGraph *toGraph)
{
    if (find(edges[fromGraph].begin(), edges[fromGraph].end(), toGraph) == edges[fromGraph].end())
    {
        edges[fromGraph].push_back(toGraph);
        edges[toGraph];
    }
}
 
vector<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicNetwork::getDownstreamVertices(VuoDirectedAcyclicGraph::Vertex *vertex)
{
    return getReachableVertices(vertex, edges, true);
}
 
vector<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicNetwork::getUpstreamVertices(VuoDirectedAcyclicGraph::Vertex *vertex)
{
    map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> > backEdges;
    for (map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::iterator i = edges.begin(); i != edges.end(); ++i)
    {
        for (vector<VuoDirectedAcyclicGraph *>::iterator j = i->second.begin(); j != i->second.end(); ++j)
            if (find(backEdges[*j].begin(), backEdges[*j].end(), i->first) == backEdges[*j].end())
                backEdges[*j].push_back(i->first);
 
        backEdges[i->first];
    }
 
    return getReachableVertices(vertex, backEdges, false);
}
 
vector<VuoDirectedAcyclicGraph::Vertex *> VuoDirectedAcyclicNetwork::getReachableVertices(VuoDirectedAcyclicGraph::Vertex *vertex,
                                                                                          const map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> > &edges,
                                                                                          bool isDownstream)
{
    vector<VuoDirectedAcyclicGraph::Vertex *> reachableVertices;
 
    VuoDirectedAcyclicGraph *containingGraph = NULL;
    for (map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::const_iterator i = edges.begin(); i != edges.end(); ++i)
    {
        if (i->first->edges.find(vertex) != i->first->edges.end())
        {
            containingGraph = i->first;
            break;
        }
    }
 
    if (! containingGraph)
        return reachableVertices;
 
    list< pair< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph::Vertex *> > > toVisit;
    toVisit.push_back( make_pair(containingGraph, vector<VuoDirectedAcyclicGraph::Vertex *>(1, vertex)) );
 
    while (! toVisit.empty())
    {
        VuoDirectedAcyclicGraph *currGraph = toVisit.front().first;
        vector<VuoDirectedAcyclicGraph::Vertex *> currVertices = toVisit.front().second;
        toVisit.pop_front();
 
        map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::const_iterator edgesIter = edges.find(currGraph);
        if (edgesIter != edges.end())
        {
            map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph::Vertex *> > moreToVisit;
 
            for (vector<VuoDirectedAcyclicGraph::Vertex *>::iterator i = currVertices.begin(); i != currVertices.end(); ++i)
            {
                VuoDirectedAcyclicGraph::Vertex *currVertex = *i;
                vector<VuoDirectedAcyclicGraph::Vertex *> currReachableVertices = (isDownstream ?
                                                                                       currGraph->getDownstreamVertices(currVertex) :
                                                                                       currGraph->getUpstreamVertices(currVertex));
 
                for (vector<VuoDirectedAcyclicGraph::Vertex *>::iterator j = currReachableVertices.begin(); j != currReachableVertices.end(); ++j)
                {
                    VuoDirectedAcyclicGraph::Vertex *currReachableVertex = *j;
 
                    if (find(reachableVertices.begin(), reachableVertices.end(), currReachableVertex) == reachableVertices.end())
                        reachableVertices.push_back(currReachableVertex);
                }
 
                vector<VuoDirectedAcyclicGraph::Vertex *> candidateVertices;
                candidateVertices.push_back(currVertex);
                candidateVertices.insert(candidateVertices.end(), currReachableVertices.begin(), currReachableVertices.end());
 
                for (vector<VuoDirectedAcyclicGraph::Vertex *>::iterator j = candidateVertices.begin(); j != candidateVertices.end(); ++j)
                {
                    VuoDirectedAcyclicGraph::Vertex *candidateVertex = *j;
 
                    for (vector<VuoDirectedAcyclicGraph *>::const_iterator k = edgesIter->second.begin(); k != edgesIter->second.end(); ++k)
                    {
                        VuoDirectedAcyclicGraph *otherGraph = *k;
 
                        VuoDirectedAcyclicGraph::Vertex *matchingVertexInOtherGraph = otherGraph->findVertex(candidateVertex->key());
                        if (matchingVertexInOtherGraph)
                        {
                            moreToVisit[otherGraph].push_back(matchingVertexInOtherGraph);
 
                            if (find(reachableVertices.begin(), reachableVertices.end(), matchingVertexInOtherGraph) == reachableVertices.end())
                                reachableVertices.push_back(matchingVertexInOtherGraph);
                        }
                    }
                }
            }
 
            for (map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph::Vertex *> >::iterator i = moreToVisit.begin(); i != moreToVisit.end(); ++i)
                toVisit.push_back( make_pair(i->first, i->second) );
        }
    }
 
    return reachableVertices;
}
 
string VuoDirectedAcyclicNetwork::toString(bool showVertexAddresses)
{
    ostringstream ss;
 
    for (map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::iterator i = edges.begin(); i != edges.end(); ++i)
    {
        ss << i->first << " ->";
        for (VuoDirectedAcyclicGraph *graph : i->second)
            ss << " " << graph;
        ss << "\n";
    }
 
    for (map< VuoDirectedAcyclicGraph *, vector<VuoDirectedAcyclicGraph *> >::iterator i = edges.begin(); i != edges.end(); ++i)
    {
        string graphString = i->first->toString(showVertexAddresses);
        if (! graphString.empty())
            ss << "\n" << i->first << ":\n" << graphString << "\n";
    }
 
    return ss.str();
}