Topological Sort on a DAG

toposort-ex.cc

#include <set>
#include <stack>
#include <vector>
#include <memory>
#include <iostream>
#include <exception>
#include <cassert>


using namespace std;


// represent a graph using predecessor set to represent edges
class Graph
{
private:    // member data

    int V;                          // number of vertices
    unique_ptr<set<int>[]> prec;    // predecessor set: prec[n] contains edges TO n from ...
    unique_ptr<set<int>[]> adj;     // adjacent set: adj[n] contains edges FROM n to ...

public:     // public interface

    Graph(int nV);  // create a graph to contain V vertices

    void add_edge(int from, int to);
    void remove_edge(int from, int to);

    // perform a topological sort on the graph, returning a vector of
    // the vertices' indices, in its topological order
    vector<int> topological_sort() const;

private:    // helper functions

    // define copy semantics only for internal use
    Graph(const Graph &other);
    Graph& operator=(const Graph &other);

    void _copy_from(const Graph &other);

    // given a predecessor set (and number of vertices), remove all edges
    // originating from vertex n, and return a set (array) of vertices
    // adjacent to n (one of whose incoming edges we just removed)
    static vector<int> _remove_edges_from(int n, set<int> *prec, int V);

};


Graph::Graph(int nV)
    : V(nV)
{
    prec.reset( new set<int>[nV] );
    adj.reset( new set<int>[nV] );
}

Graph::Graph(const Graph &other)
{
    _copy_from(other);
}

Graph& Graph::operator=(const Graph &other)
{
    _copy_from(other);
    return *this;
}

void Graph::_copy_from(const Graph &other)
{
    V = other.V;
    prec.reset( new set<int>[V] );
    adj.reset( new set<int>[V] );
    for (int i = 0; i < V; ++i)
    {
        for (auto cit = other.prec[i].cbegin(); cit != other.prec[i].cend(); ++cit)
        {
            prec[i].insert(*cit);
        }
        for (auto cit = other.adj[i].cbegin(); cit != other.adj[i].cend(); ++cit)
        {
            adj[i].insert(*cit);
        }
    }
}

void Graph::add_edge(int from, int to)
{
    if (from < 0 || from >= V ||
        to < 0 || to >= V)
    {
        throw out_of_range("Illegal vertex index");
    }
    
    prec[to].insert(from);
    adj[from].insert(to);
}

void Graph::remove_edge(int from, int to)
{
    if (from < 0 || from >= V ||
        to < 0 || to >= V)
    {
        throw out_of_range("Illegal vertex index");
    }
    
    auto removed = prec[to].erase(from);
    if (removed)
    {
        removed = adj[from].erase(to);
        assert (removed);
    }
    else
    {
        assert (adj[from].find(to) == adj[from].end());
    }
}

vector<int> Graph::topological_sort() const
{
    // this algorithm needs to be able to modify (remove) edges, so
    // let's copy this Graph to a temporary copy to operate on
    Graph copy(*this);

    // this array will contain the vertices' indices, in topological order
    vector<int> result;

    // our scratch spaces:
    stack<int> next;    // contains vertices with no incoming edges; candidate for next visit
    set<int> rest;      // the rest of the vertices in the graph
    // information about vertices that are visited
    vector<bool> visited(V, false);

    // first, populate our temporary containers
    for (int i = 0; i < V; ++i)
    {
        if (copy.prec[i].empty())
        {
            next.push(i);
        }
        else
        {
            rest.insert(i);
        }
    }

    while (!next.empty())
    {
        // pop the next vertex that has no incoming edges,
        // and store it in our result (i.e. "visit" it)
        int vertex = next.top(); next.pop();
        if (!visited[vertex])
        {
            result.push_back(vertex);
            // mark it visited
            visited[vertex] = true;
        }
        else
        {
            continue;
        }

        // remove all edges coming from this vertex we just visited
        vector<int> adjacents;  // have to find out adjacent vertices first, as we cannot remove edges while iterating through them
        for (auto it = copy.adj[vertex].begin();
             it != copy.adj[vertex].end();
             ++it)
        {
            adjacents.push_back(*it);
        }
        for (auto it = adjacents.begin();
             it != adjacents.end();
             ++it)
        {
            copy.remove_edge(vertex, *it);
            // after removing this edge, check if this adjacent node now becomes
            // a candidate next node (no incoming edges)
            if (copy.prec[*it].empty())
            {
                rest.erase(*it);
                next.push(*it);
            }
        }
    }

    // at the end, check that the "rest" vertices set is empty
    if (!rest.empty())
    {
        // found an unvisited vertex! must be a cycle...
        throw exception();
    }

    return result;
}


int main()
{
    /**
     *
     *      5     4
     *     / \   / \
     *    /   \ /   \
     *   v     v     v
     *   2     0     1
     *    \          ^
     *     \         |
     *      \       /
     *       \     /
     *        \   /
     *         \ /
     *          v
     *          3
     *
     */

    // Create a graph given in the above diagram
    Graph g(6);
    g.add_edge(5, 2);
    g.add_edge(5, 0);
    g.add_edge(4, 0);
    g.add_edge(4, 1);
    g.add_edge(2, 3);
    g.add_edge(3, 1);

    const Graph &cg = g;
 
    vector<int> order = cg.topological_sort();
    cout << "Topological Sort of the given graph:" << endl;
    for (vector<int>::iterator it = order.begin();
         it != order.end();
         ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
 
    return 0;
}


/**
 * Output:
 *
 * $ g++ -std=c++11 -Wall -g -o toposort-ex toposort-ex.cc && valgrind ./toposort-ex
 * ==115132== Memcheck, a memory error detector
 * ==115132== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
 * ==115132== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
 * ==115132== Command: ./toposort-ex
 * ==115132== 
 * Topological Sort of the given graph:
 * 5 2 3 4 1 0 
 * ==115132== 
 * ==115132== HEAP SUMMARY:
 * ==115132==     in use at exit: 0 bytes in 0 blocks
 * ==115132==   total heap usage: 47 allocs, 47 frees, 3,556 bytes allocated
 * ==115132== 
 * ==115132== All heap blocks were freed -- no leaks are possible
 * ==115132== 
 * ==115132== For counts of detected and suppressed errors, rerun with: -v
 * ==115132== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
 *
 */

toposort.cc

#include <list>
#include <stack>
#include <vector>
#include <memory>
#include <iostream>
#include <exception>
#include <cassert>


using namespace std;


// represent a graph using adjacency list to represent edges
class Graph
{
private:    // member data

    int V;  // number of vertices
    unique_ptr<list<int>[]> adj;    // adjacency list: adj[n] contains edges FROM n to ...

public:     // public interface

    Graph(int nV);  // create a graph to contain V vertices

    void add_edge(int from, int to);

    // perform a topological sort on the graph, returning a vector of
    // the vertices' indices, in its topological order
    vector<int> topological_sort() const;

private:    // helper functions

    void _topological_sort_util(int n, vector<bool> &visited, stack<int> &partial) const;

};


Graph::Graph(int nV)
    : V(nV)
{
    adj.reset( new list<int>[nV] );
}

void Graph::add_edge(int from, int to)
{
    if (from < 0 || from >= V ||
        to < 0 || to >= V)
    {
        throw out_of_range("Illegal vertex index");
    }
    
    adj[from].push_back(to);
}

vector<int> Graph::topological_sort() const
{
    // our scratch spaces:
    // the resulting topological order of vertex indices
    vector<int> result(V, -1);
    // for marking whether a vertex has been visited
    vector<bool> visited(V, false);
    // to temporarily store partial ordering of visited vertices, in a stack fashion
    stack<int> partial;

    for (int i = 0; i < V; ++i)
    {
        if (!visited[i])
        {
            _topological_sort_util(i, visited, partial);
        }
    }
    // when that is done, the "partial" stack will be full with the vertices in the
    // ordering that we want, top first

    int index = 0;
    while (!partial.empty())
    {
        result[index++] = partial.top(); partial.pop();
    }

    return result;
}

// perform topological sort starting from vertex n, given the contexts:
// * visited stores runtime information of whether vertices have been visited
// * partial contains already-visited vertices in topological order (top first)
void Graph::_topological_sort_util(int n, vector<bool> &visited, stack<int> &partial) const
{
    assert (n >= 0 && n < V);
    visited[n] = true;

    // first, push this vertex' adjacent vertices in the partially ordered stack
    for (auto it = adj[n].begin(); it != adj[n].end(); ++it)
    {
        if (!visited[*it])
        {
            _topological_sort_util(*it, visited, partial);
        }
    }

    // finally, push this vertex on top of the partial stack, since--compared to its
    // adjacent vertices--this vertex goes before them in topological order
    partial.push(n);
}


int main()
{
    /**
     *
     *      5     4
     *     / \   / \
     *    /   \ /   \
     *   v     v     v
     *   2     0     1
     *    \          ^
     *     \         |
     *      \       /
     *       \     /
     *        \   /
     *         \ /
     *          v
     *          3
     *
     */

    // Create a graph given in the above diagram
    Graph g(6);
    g.add_edge(5, 2);
    g.add_edge(5, 0);
    g.add_edge(4, 0);
    g.add_edge(4, 1);
    g.add_edge(2, 3);
    g.add_edge(3, 1);

    const Graph &cg = g;
 
    vector<int> order = cg.topological_sort();
    cout << "Topological Sort of the given graph:" << endl;
    for (vector<int>::iterator it = order.begin();
         it != order.end();
         ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
 
    return 0;
}


/**
 * Output:
 *
 * :! g++ -std=c++11 -Wall -g -o toposort toposort.cc && ./toposort
 * Topological Sort of the given graph:
 * 5 4 2 3 1 0 
 *
 */