4
\$\begingroup\$

I have here a class which represents a directed acyclic graph (Graph) and a vertex in the graph (Vertex). The vertices are stored in an adjacency list. It has the ability to find a vertex's indegree, and to find a topological sort order. The graph does not own the vertices.

I'm particularly interested in comments regarding correctness and performance.

Vertex header

#include <string>

class Vertex
{
public:
    Vertex(std::string name, int weight = 1);
    virtual ~Vertex() = default;

    const std::string& name() const { return _name; }
    int weight() const { return _weight; }
protected:
    std::string _name;
    int         _weight;
};

Vertex definitions

Vertex::Vertex(std::string name, int weight)
    : _name(std::move(name))
    , _weight(weight)
{}

Graph header

#include <vector>
#include <unordered_map>

class Graph
{
public:
    template<typename T>
    using VertexMap     = std::unordered_map<Vertex*, T>;
    using AdjacencyList = VertexMap<std::vector<Vertex*>>;

    void addEdge(Vertex* u, Vertex* v);

    std::vector<Vertex*> topoSort();

    VertexMap<int> indegrees() const;
    int indegree(Vertex*) const;

    const AdjacencyList& adjacencyList() const;
private:
    AdjacencyList _vertices;
};

Graph definitions

void Graph::addEdge(Vertex* u, Vertex* v)
{
    _vertices[v];               // initialise adjacency list for v
    _vertices[u].push_back(v);  // add v as being adjacent to u
}

enum Colour { White, Grey, Black };

void topoSortVertex(Vertex* vertex,
                    Colour& colour,
                    const Graph::AdjacencyList& adjacencyList,
                    Graph::VertexMap<Colour>& visited,
                    std::vector<Vertex*>& sorted)
{
    colour = Grey;

    for (Vertex* neighbour : adjacencyList.at(vertex))
    {
        Colour& neighbour_colour = visited[neighbour];
        if (neighbour_colour == White)
        {
            topoSortVertex(neighbour, neighbour_colour, adjacencyList, visited, sorted);
        }
        else
        if (neighbour_colour == Grey)
        {
            throw std::runtime_error("cycle in graph");
        }
    }

    colour = Black;
    sorted.push_back(vertex);
}

std::vector<Vertex*> Graph::topoSort()
{
    VertexMap<int> indegs = indegrees();

    std::vector<Vertex*> sorted;
    sorted.reserve(indegs.size());

    VertexMap<Colour> visited;
    visited.reserve(indegs.size());

    for (auto& pair : indegs)
    {
        if (pair.second == 0) // vertex has indegree of 0
        {
            Vertex* vertex = pair.first;
            Colour& colour = visited[vertex];
            if (colour == White)
            {
                topoSortVertex(vertex, colour, _vertices, visited, sorted);
            }
        }
    }

    return sorted;
}

Graph::VertexMap<int> Graph::indegrees() const
{
    VertexMap<int> indegrees;

    for (auto& pair : _vertices)
    {
        indegrees[pair.first]; // initialise indegree for this vertex
        for (Vertex* neighbour : pair.second)
        {
            ++indegrees[neighbour];
        }
    }

    return indegrees;
}

int Graph::indegree(Vertex* v) const
{
    return indegrees().at(v);
}

const Graph::AdjacencyList& Graph::adjacencyList() const
{
    return _vertices;
}

Exemplar

#include <iostream>

int main()
{
    Graph g;
    Vertex v2  {  "2" };
    Vertex v3  {  "3" };
    Vertex v5  {  "5" };
    Vertex v7  {  "7" };
    Vertex v8  {  "8" };
    Vertex v9  {  "9" };
    Vertex v10 { "10" };
    Vertex v11 { "11" };

    g.addEdge(&v7,  &v11);
    g.addEdge(&v7,  &v8);
    g.addEdge(&v5,  &v11);
    g.addEdge(&v3,  &v8);
    g.addEdge(&v3,  &v10);
    g.addEdge(&v8,  &v9);
    g.addEdge(&v11, &v9);
    g.addEdge(&v9,  &v2);

    /*
     *    3   7    5
     *   / \ / \  /
     * 10   8   11
     *       \ /
     *        9
     *        |
     *        2
     */

    std::cout << "adjacency list:\n";
    for (auto& pair : g.adjacencyList())
    {
        std::cout << pair.first->name() << ": ";
        for (const Vertex* neighbour : pair.second)
            std::cout << neighbour->name() << ", ";
        std::cout << '\n';
    }

    std::cout << "indegrees:\n";
    for (auto& pair : g.indegrees())
        std::cout << pair.first->name() << ": " << pair.second << '\n';

    std::cout << "topoSort:\n";
    for (Vertex* v : g.topoSort())
        std::cout << v->name() << ", ";
    std::cout << '\n';

    // add cycle
    g.addEdge(&v9, &v3);
    try
    {
        g.topoSort();
    }
    catch (const std::exception& e)
    {
        std::cerr << e.what() << std::endl;
    }
}

Output

adjacency list:
2: 
9: 2, 
10: 
3: 8, 10, 
5: 11, 
8: 9, 
7: 11, 8, 
11: 9, 
indegrees:
7: 0
11: 2
5: 0
8: 2
3: 0
10: 1
9: 2
2: 1
topoSort:
2, 9, 11, 8, 7, 5, 10, 3, 
cycle in graph

Here is the code running on Ideone.

\$\endgroup\$
3
\$\begingroup\$

Performance

A very cache friendly representation of a directed graph is the foward star representation. Basically it's a single vector containing all edges sorted by their head node, with another index vector mapping a node to its first outgoing edge.

Correctness

Your definition of a "cycle" is somewhat non-standard? Usually, a cycle in a directed graph means that you can get back to a particular vertex. In your example, adding a vertex from 9 -> 8 -> 7 would make it cyclic. But I guess, it depends on what you're after.

Likewise, your sort order is reversed to the standard definition as given in Cormen:

If there is an edge (u,v) then u appears before v in the ordering.

Code style

class Vertex
{
public:
    virtual ~Vertex() = default;
}

No need to default the destructor here.

Consider making colouran attribute at CVertex instead of a separate vector. You're only shifting around pointers to it anyway so no need to have it separate.

Make indegrees a member of Graph. At the moment, every call to Graph::indegree iterates the whole vertex list.

In Graph::topoSort:

    if (colour == White)

I think that could be assert (colour == White). It doesn't have an indegree so it shouldn't have been visited before.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.