# Graph (adjacency list) and DFS (topological sort)

The vertices on the graph are numbers from 0 to |V| - 1 for convenience. I was thinking later to use a template wrapper for the graph.

Graph.h:

#pragma once
#include <unordered_set>
#include <vector>

class Graph
{
public:
using size_type = std::size_t;
using adj_list = std::unordered_set<size_type>;
private:
std::vector<adj_list> list;
size_type edges;
void check_range(size_type) const;
public:
using size_type = std::size_t;
Graph(size_type v);
~Graph();

void add_vertex();
void add_edge(size_type, size_type);

const adj_list& adj(size_type) const;
Graph reverse() const;

size_type E() const;
size_type V() const;
};


Graph.cpp:

#include "Graph.h"

Graph::Graph(size_type v)
: list(std::vector<adj_list>(v, std::unordered_set<size_type>())) {
}

Graph::~Graph() {
}

void Graph::add_vertex() {
list.push_back(std::unordered_set<size_type>());
}

void Graph::add_edge(size_type v, size_type w) {
check_range(v);
check_range(w);

list[v].insert(w);
++edges;
}

const typename Graph::adj_list & Graph::adj(size_type v) const {
check_range(v);
return list[v];
}

Graph Graph::reverse() const {
Graph g(list.size());
for (size_type v = 0, size = list.size(); v < size; ++v) {
for (auto w : list[v]) {
g.add_edge(w, v);
}
}
return g;
}

void Graph::check_range(size_type v) const {
if (v >= list.size()) {
throw std::out_of_range("vertex out of range");
}
}

typename Graph::size_type Graph::E() const {
return edges;
}

typename Graph::size_type Graph::V() const {
return list.size();
}


DFS.h:

#pragma once
#include "Graph.h"
#include <deque>
#include <stack>

class DFS
{
enum vertex_state { on_stack, undiscovered, done };

std::vector<vertex_state> vertices;
std::deque<Graph::size_type> topo_sort;

public:
using iterator = std::deque<Graph::size_type>::iterator;
using reverse_iterator = std::deque<Graph::size_type>::reverse_iterator;

DFS(const Graph&);

bool DFS_visit(const Graph& graph, Graph::size_type, std::stack<std::pair<Graph::size_type, bool>> &);

bool DAG();

iterator begin() { return topo_sort.begin(); }
iterator end() { return topo_sort.end(); }

reverse_iterator rbegin() { return topo_sort.rbegin(); }
reverse_iterator rend() { return topo_sort.rend(); }

};


DFS.cpp:

#include "DFS.h"

DFS::DFS(const Graph& G)
: vertices(std::vector<vertex_state>(G.V(), undiscovered)),
topo_sort(std::deque<Graph::size_type>()) {

std::stack<std::pair<Graph::size_type, bool>> stack;
for (auto v = 0; v < G.V(); ++v) {
if (vertices[v] == undiscovered
&& !DFS_visit(G, v, stack)) {
break;
}
}
//while(v < G.V() && (marked(x) || DFS_visit(G, v++)))
}

bool DFS::DFS_visit(const Graph& graph, Graph::size_type v,
std::stack<std::pair<Graph::size_type, bool>> &stack) {

stack.push(std::make_pair(v, false));
while (!stack.empty()) {
auto &current = stack.top();
auto v        = current.first;

if (current.second) {
topo_sort.push_front(v);
vertices[v] = done;
}
else switch (vertices[v]) {

case undiscovered:
current.second = true;
vertices[v]    = on_stack;
for (auto w : graph.adj(v)) {
stack.push(std::make_pair(w, false));
}
continue;

case on_stack:
topo_sort.clear();
return false;
}
stack.pop();
}
return true;
}

bool DFS::DAG() {
return !topo_sort.empty();
}