Directed acyclic graph with topological sort

Question

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.

Answer 1

Performance

A very cache friendly representation of a directed graph is the forward 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.

• mid: Is this post using a link to the Web Archive in case the original goes down in the future? I'm asking because it's currently still up.