#include <string>
// vertex header
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;
protected:
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;
}
// test
#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;
}
}