# Directed acyclic graph with topological sort

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>;

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

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

private:
};


## Graph definitions

void Graph::addEdge(Vertex* u, Vertex* v)
{
_vertices[v];               // initialise adjacency list for v
}

enum Colour { White, Grey, Black };

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

{
Colour& neighbour_colour = visited[neighbour];
if (neighbour_colour == White)
{
}
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);
}

{
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" };

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

{
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';

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


# 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.