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 

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

class Graph
{
public:
    template
    using VertexMap     = std::unordered_map;
    using AdjacencyList = VertexMap>;

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

    std::vector topoSort();

    VertexMap 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& visited,
std::vector& 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)
{

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.

StackExchange Code Review Q#80491, answer score: 4