1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
#pragma once
#include <unordered_map>
namespace vcpkg { namespace Graphs
{
enum class ExplorationStatus
{
// We have not visited this vertex
NOT_EXPLORED,
// We have visited this vertex but haven't visited all vertices in its subtree
PARTIALLY_EXPLORED,
// We have visited this vertex and all vertices in its subtree
FULLY_EXPLORED
};
template <class V>
class Graph
{
static void find_topological_sort_internal(V vertex,
ExplorationStatus& status,
const std::unordered_map<V, std::vector<V>>& adjacency_list,
std::unordered_map<V, ExplorationStatus>& exploration_status,
std::vector<V>& sorted)
{
status = ExplorationStatus::PARTIALLY_EXPLORED;
for (V neighbour : adjacency_list.at(vertex))
{
ExplorationStatus& neighbour_status = exploration_status[neighbour];
if (neighbour_status == ExplorationStatus::NOT_EXPLORED)
{
find_topological_sort_internal(neighbour, neighbour_status, adjacency_list, exploration_status, sorted);
}
else if (neighbour_status == ExplorationStatus::PARTIALLY_EXPLORED)
{
throw std::runtime_error("cycle in graph");
}
}
status = ExplorationStatus::FULLY_EXPLORED;
sorted.push_back(vertex);
}
public:
void add_vertex(V v)
{
this->vertices[v];
}
// TODO: Change with iterators
void add_vertices(const std::vector<V>& vs)
{
for (const V& v : vs)
{
this->vertices[v];
}
}
void add_edge(V u, V v)
{
this->vertices[v];
this->vertices[u].push_back(v);
}
std::vector<V> find_topological_sort() const
{
std::unordered_map<V, int> indegrees = count_indegrees();
std::vector<V> sorted;
sorted.reserve(indegrees.size());
std::unordered_map<V, ExplorationStatus> exploration_status;
exploration_status.reserve(indegrees.size());
for (auto& pair : indegrees)
{
if (pair.second == 0) // Starting from vertices with indegree == 0. Not required.
{
V vertex = pair.first;
ExplorationStatus& status = exploration_status[vertex];
if (status == ExplorationStatus::NOT_EXPLORED)
{
find_topological_sort_internal(vertex, status, this->vertices, exploration_status, sorted);
}
}
}
return sorted;
}
std::unordered_map<V, int> count_indegrees() const
{
std::unordered_map<V, int> indegrees;
for (auto& pair : this->vertices)
{
indegrees[pair.first];
for (V neighbour : pair.second)
{
++indegrees[neighbour];
}
}
return indegrees;
}
const std::unordered_map<V, std::vector<V>>& adjacency_list() const
{
return this->vertices;
}
private:
std::unordered_map<V, std::vector<V>> vertices;
};
}}
|
