373 lines
12 KiB
C++
373 lines
12 KiB
C++
|
// #define NDEBUG
|
||
|
|
|
||
|
|
#include <stdlib.h>
|
||
|
|
// #include <string>
|
||
|
|
#include <vector>
|
||
|
|
// #include <array>
|
||
|
|
// #include <queue>
|
||
|
|
#include <iostream>
|
||
|
|
// #include <map>
|
||
|
|
// #include <math.h>
|
||
|
|
// #include <numeric>
|
||
|
|
// #include <tuple>
|
||
|
|
// #include <set>
|
||
|
|
|
||
|
|
|
||
|
|
// #define NDEBUG
|
||
|
|
|
||
|
|
#include <stdlib.h>
|
||
|
|
#include <vector>
|
||
|
|
#include <iostream>
|
||
|
|
#include <queue>
|
||
|
|
#include <algorithm>
|
||
|
|
#include <limits>
|
||
|
|
|
||
|
|
template <typename T = long> class Graph;
|
||
|
|
template <typename T = long> class WeightedGraph;
|
||
|
|
template <typename T, typename EDGE> class BaseGraph;
|
||
|
|
|
||
|
|
template <typename T>
|
||
|
|
class Graph : public BaseGraph<T, int> {
|
||
|
|
virtual int construct_edge(int v, T w) {
|
||
|
|
w; // Remove warning
|
||
|
|
return v;
|
||
|
|
}
|
||
|
|
|
||
|
|
virtual int get_edge_vertex(int e) {
|
||
|
|
return e;
|
||
|
|
}
|
||
|
|
|
||
|
|
virtual T get_edge_weight(int e) {
|
||
|
|
e; // Remove warning
|
||
|
|
return 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
public:
|
||
|
|
Graph(size_t N, size_t min_index) : BaseGraph<T, int>(N, min_index) {};
|
||
|
|
};
|
||
|
|
|
||
|
|
template <typename T>
|
||
|
|
class WeightedGraph : public BaseGraph<T, std::pair<T, int>> {
|
||
|
|
virtual std::pair<T, int> construct_edge(int v, T w) {
|
||
|
|
return {w, v};
|
||
|
|
}
|
||
|
|
|
||
|
|
virtual int get_edge_vertex(std::pair<T, int> e) {
|
||
|
|
return e.second;
|
||
|
|
}
|
||
|
|
|
||
|
|
virtual T get_edge_weight(std::pair<T, int> e) {
|
||
|
|
return e.first;
|
||
|
|
}
|
||
|
|
|
||
|
|
bool min_cut_max_flow_dfs(std::vector<std::vector<std::pair<std::pair<T, int>&, std::pair<T, int>&>>> &edge_pairs, std::vector<std::pair<std::pair<T, int>&, std::pair<T, int>&>>& path, std::vector<bool>& visited, int v, int sink, T threshold) {
|
||
|
|
if (v == sink)
|
||
|
|
return EXIT_SUCCESS;
|
||
|
|
visited[v] = true;
|
||
|
|
for (auto e : edge_pairs[v]) {
|
||
|
|
int u = get_edge_vertex(e.first);
|
||
|
|
int w = get_edge_weight(e.first);
|
||
|
|
if (!visited[u] && w >= threshold) {
|
||
|
|
bool res = min_cut_max_flow_dfs(edge_pairs, path, visited, u, sink, threshold);
|
||
|
|
if (res == EXIT_SUCCESS) {
|
||
|
|
path.push_back(e);
|
||
|
|
return EXIT_SUCCESS;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return EXIT_FAILURE;
|
||
|
|
}
|
||
|
|
|
||
|
|
public:
|
||
|
|
WeightedGraph(size_t N, size_t min_index) : BaseGraph<T, std::pair<T, int>>(N, min_index) {};
|
||
|
|
|
||
|
|
Graph<T> get_shortest_path_graph(int from) {
|
||
|
|
std::vector<T> best_distance = this->dijkstra(from);
|
||
|
|
Graph<T> G(this->N, this->min_index);
|
||
|
|
for (size_t i = this->min_index; i < this->N; i++) {
|
||
|
|
for (auto e : this->adj[i]) {
|
||
|
|
T w = get_edge_weight(e);
|
||
|
|
int v = get_edge_vertex(e);
|
||
|
|
if (best_distance[i] + w == best_distance[v])
|
||
|
|
G.add_directed_edge(i, v);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return G;
|
||
|
|
}
|
||
|
|
|
||
|
|
WeightedGraph<T> get_weighted_shortest_path_graph(int from) {
|
||
|
|
std::vector<T> best_distance = this->dijkstra(from);
|
||
|
|
WeightedGraph<T> G(this->N, this->min_index);
|
||
|
|
for (size_t i = this->min_index; i < this->N; i++) {
|
||
|
|
for (auto e : this->adj[i]) {
|
||
|
|
T w = get_edge_weight(e);
|
||
|
|
int v = get_edge_vertex(e);
|
||
|
|
if (best_distance[i] + w == best_distance[v])
|
||
|
|
G.add_directed_edge(i, v, w);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return G;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Running time: O(m^2n)
|
||
|
|
T min_cut_max_flow(int source, int sink) {
|
||
|
|
// TODO: Implement non-destructive version?
|
||
|
|
// Ford-Fulkerson - "scaling algorithm" version
|
||
|
|
std::vector<std::vector<std::pair<std::pair<T, int>&, std::pair<T, int>&>>> edge_pairs(this->N, std::vector<std::pair<std::pair<T, int>&, std::pair<T, int>&>>());
|
||
|
|
T threshold = 0;
|
||
|
|
for (size_t v = this->min_index; v < this->N; v++) {
|
||
|
|
for (auto& e : this->adj[v]) {
|
||
|
|
if (get_edge_weight(e) == 0) continue;
|
||
|
|
threshold = threshold > get_edge_weight(e) ? threshold : get_edge_weight(e); // max(threshold, get_edge_weight(e));
|
||
|
|
int u = get_edge_vertex(e);
|
||
|
|
this->adj[u].push_back(construct_edge(v, 0));
|
||
|
|
edge_pairs[v].push_back({e, this->adj[u][this->adj[u].size()-1]});
|
||
|
|
edge_pairs[u].push_back({this->adj[u][this->adj[u].size()-1], e});
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
std::vector<bool> visited(this->N, false);
|
||
|
|
std::vector<std::pair<std::pair<T, int>&, std::pair<T, int>&>> path;
|
||
|
|
while (true) {
|
||
|
|
bool res = min_cut_max_flow_dfs(edge_pairs, path, visited, source, sink, threshold);
|
||
|
|
if (res == EXIT_SUCCESS) {
|
||
|
|
T path_max_flow = std::numeric_limits<T>::max();
|
||
|
|
for (auto e : path)
|
||
|
|
path_max_flow = path_max_flow < get_edge_weight(e.first) ? path_max_flow : get_edge_weight(e.first);
|
||
|
|
// min(path_max_flow, get_edge_weight(e.first));
|
||
|
|
for (auto e : path) {
|
||
|
|
e.first = construct_edge(get_edge_vertex(e.first), get_edge_weight(e.first)-threshold);
|
||
|
|
e.second = construct_edge(get_edge_vertex(e.second), get_edge_weight(e.second)+threshold);
|
||
|
|
}
|
||
|
|
} else {
|
||
|
|
if (threshold == 1)
|
||
|
|
break; // Done!
|
||
|
|
threshold /= 2;
|
||
|
|
}
|
||
|
|
std::fill(visited.begin(), visited.end(), false);
|
||
|
|
path.clear();
|
||
|
|
}
|
||
|
|
|
||
|
|
T max_flow = 0;
|
||
|
|
for (auto e : this->adj[sink]) {
|
||
|
|
max_flow += get_edge_weight(e);
|
||
|
|
}
|
||
|
|
|
||
|
|
return max_flow;
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
template <typename T, typename EDGE>
|
||
|
|
class BaseGraph {
|
||
|
|
std::vector<int> top_sort;
|
||
|
|
int contains_cycles = 0; // 0 = unknown, 1 = yes, 2 = no
|
||
|
|
bool contains_negative_edge_weight = false;
|
||
|
|
|
||
|
|
virtual int get_edge_vertex(EDGE) = 0;
|
||
|
|
virtual T get_edge_weight(EDGE) = 0;
|
||
|
|
virtual EDGE construct_edge(int vertex, T w) = 0;
|
||
|
|
|
||
|
|
bool topological_sort_dfs(std::vector<int8_t>& status, int v, std::vector<int>& top_sort) {
|
||
|
|
if (status[v] == 1)
|
||
|
|
return EXIT_FAILURE;
|
||
|
|
if (status[v] == 0) {
|
||
|
|
status[v] = 1;
|
||
|
|
for (auto e : adj[v]) {
|
||
|
|
bool res = topological_sort_dfs(status, get_edge_vertex(e), top_sort);
|
||
|
|
if (res == EXIT_FAILURE)
|
||
|
|
return EXIT_FAILURE;
|
||
|
|
}
|
||
|
|
status[v] = 2;
|
||
|
|
top_sort.push_back(v);
|
||
|
|
}
|
||
|
|
return EXIT_SUCCESS;
|
||
|
|
}
|
||
|
|
|
||
|
|
void do_topological_sort() {
|
||
|
|
std::vector<int8_t> status(N, 0);
|
||
|
|
std::vector<int> top_sort = std::vector<int>();
|
||
|
|
for (size_t i = min_index; i < N; i++) {
|
||
|
|
bool res = topological_sort_dfs(status, i, top_sort);
|
||
|
|
if (res == EXIT_FAILURE) {
|
||
|
|
contains_cycles = 1;
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
contains_cycles = 2;
|
||
|
|
std::reverse(top_sort.begin(), top_sort.end());
|
||
|
|
this->top_sort = top_sort;
|
||
|
|
}
|
||
|
|
|
||
|
|
public:
|
||
|
|
size_t N;
|
||
|
|
size_t min_index;
|
||
|
|
std::vector<std::vector<EDGE>> adj;
|
||
|
|
|
||
|
|
BaseGraph(size_t N, size_t min_index) {
|
||
|
|
N += min_index;
|
||
|
|
this->N = N;
|
||
|
|
this->min_index = min_index;
|
||
|
|
adj = std::vector<std::vector<EDGE>>(N, std::vector<EDGE>());
|
||
|
|
}
|
||
|
|
|
||
|
|
void add_directed_edge(int from, int to, T w = 1) {
|
||
|
|
adj[from].push_back(construct_edge(to, w));
|
||
|
|
contains_cycles = 0;
|
||
|
|
if (w < 0)
|
||
|
|
contains_negative_edge_weight = true;
|
||
|
|
}
|
||
|
|
|
||
|
|
void add_undirected_edge(size_t a, size_t b, T w = 1) {
|
||
|
|
adj[a].push_back(construct_edge(b, w));
|
||
|
|
adj[b].push_back(construct_edge(a, w));
|
||
|
|
contains_cycles = 0;
|
||
|
|
if (w < 0)
|
||
|
|
contains_negative_edge_weight = true;
|
||
|
|
}
|
||
|
|
|
||
|
|
std::vector<EDGE> get(int v) {
|
||
|
|
return adj[v];
|
||
|
|
}
|
||
|
|
|
||
|
|
std::vector<int> topological_sort() {
|
||
|
|
if (contains_cycles != 2)
|
||
|
|
std::cerr << "Check for cycles first!" << std::endl;
|
||
|
|
return top_sort;
|
||
|
|
}
|
||
|
|
|
||
|
|
bool has_cycles() {
|
||
|
|
if (contains_cycles == 0)
|
||
|
|
do_topological_sort();
|
||
|
|
return contains_cycles == 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
std::vector<T> count_paths(int from) {
|
||
|
|
if (contains_cycles != 2)
|
||
|
|
std::cerr << "Check for cycles first!" << std::endl;
|
||
|
|
std::vector<T> paths(N, 0);
|
||
|
|
for (auto v : top_sort) {
|
||
|
|
T p = 0;
|
||
|
|
if (v == from) p++;
|
||
|
|
for (auto e : adj[v])
|
||
|
|
p += paths[get_edge_vertex(e)];
|
||
|
|
paths[v] = p;
|
||
|
|
}
|
||
|
|
return paths;
|
||
|
|
}
|
||
|
|
|
||
|
|
std::vector<T> dijkstra(int from) {
|
||
|
|
if (contains_negative_edge_weight)
|
||
|
|
std::cerr << "Dijkstra only works if the graph doesn't contain any negative edge weights" << std::endl;
|
||
|
|
std::vector<T> distance(N, std::numeric_limits<T>::max());
|
||
|
|
distance[from] = 0;
|
||
|
|
std::vector<bool> processed(N, false);
|
||
|
|
std::priority_queue<std::pair<T, int>> q;
|
||
|
|
q.push({0, from});
|
||
|
|
while (!q.empty()) {
|
||
|
|
int v = q.top().second; q.pop();
|
||
|
|
if (processed[v]) continue;
|
||
|
|
processed[v] = true;
|
||
|
|
for (auto e : adj[v]) {
|
||
|
|
int u = get_edge_vertex(e);
|
||
|
|
T w = get_edge_weight(e);
|
||
|
|
if (distance[v] + w < distance[u]) {
|
||
|
|
distance[u] = distance[v] + w;
|
||
|
|
q.push({-distance[u], u});
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return distance;
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
using namespace std;
|
||
|
|
|
||
|
|
int main() {
|
||
|
|
// TODO: SEGFAULT
|
||
|
|
// WeightedGraph G(6, 1);
|
||
|
|
// G.add_directed_edge(1, 2, 5);
|
||
|
|
// G.add_directed_edge(1, 4, 4);
|
||
|
|
// G.add_directed_edge(4, 2, 3);
|
||
|
|
// G.add_directed_edge(2, 3, 6);
|
||
|
|
// G.add_directed_edge(4, 5, 1);
|
||
|
|
// G.add_directed_edge(3, 5, 8);
|
||
|
|
// G.add_directed_edge(3, 6, 5);
|
||
|
|
// G.add_directed_edge(5, 6, 2);
|
||
|
|
|
||
|
|
// cout << "foo" << endl;
|
||
|
|
// cout << G.min_cut_max_flow(1, 6) << endl;
|
||
|
|
|
||
|
|
// // Works! (Probably)
|
||
|
|
// WeightedGraph G(6, 1);
|
||
|
|
// G.add_directed_edge(1, 2, 5);
|
||
|
|
// G.add_directed_edge(4, 1, 4);
|
||
|
|
// G.add_directed_edge(4, 5, 4);
|
||
|
|
// G.add_directed_edge(5, 2, 4);
|
||
|
|
// G.add_directed_edge(5, 3, 4);
|
||
|
|
// G.add_directed_edge(2, 3, 4);
|
||
|
|
// G.add_directed_edge(3, 6, 4);
|
||
|
|
|
||
|
|
// cout << "foo" << endl;
|
||
|
|
// bool cycles = G.has_cycles();
|
||
|
|
// cout << "Has cycles: " << cycles << endl;
|
||
|
|
// vector<int> top = G.topological_sort();
|
||
|
|
// for (auto i : top)
|
||
|
|
// cout << i << " ";
|
||
|
|
// cout << endl;
|
||
|
|
|
||
|
|
// // Works! (Probably)
|
||
|
|
// WeightedGraph G(6, 1);
|
||
|
|
// G.add_directed_edge(1, 2, 5);
|
||
|
|
// G.add_directed_edge(1, 4, 4);
|
||
|
|
// G.add_directed_edge(5, 1, 4);
|
||
|
|
// G.add_directed_edge(4, 5, 4);
|
||
|
|
// G.add_directed_edge(5, 2, 4);
|
||
|
|
// G.add_directed_edge(5, 3, 4);
|
||
|
|
// G.add_directed_edge(2, 3, 4);
|
||
|
|
// G.add_directed_edge(3, 6, 4);
|
||
|
|
|
||
|
|
// cout << "foo" << endl;
|
||
|
|
// bool cycles = G.has_cycles();
|
||
|
|
// cout << "Has cycles: " << cycles << endl;
|
||
|
|
|
||
|
|
// // Works! (Probably)
|
||
|
|
// Graph G(6, 1);
|
||
|
|
// G.add_directed_edge(1, 2);
|
||
|
|
// G.add_directed_edge(4, 1);
|
||
|
|
// G.add_directed_edge(4, 5);
|
||
|
|
// G.add_directed_edge(5, 2);
|
||
|
|
// G.add_directed_edge(5, 3);
|
||
|
|
// G.add_directed_edge(2, 3);
|
||
|
|
// G.add_directed_edge(3, 6);
|
||
|
|
|
||
|
|
// cout << "foo" << endl;
|
||
|
|
// bool cycles = G.has_cycles();
|
||
|
|
// cout << "Has cycles: " << cycles << endl;
|
||
|
|
// vector<int> top = G.topological_sort();
|
||
|
|
// for (auto i : top)
|
||
|
|
// cout << i << " ";
|
||
|
|
// cout << endl;
|
||
|
|
|
||
|
|
// Works! (Probably)
|
||
|
|
WeightedGraph G(6, 1);
|
||
|
|
G.add_directed_edge(1, 2, 5);
|
||
|
|
G.add_directed_edge(4, 1, 4);
|
||
|
|
G.add_directed_edge(4, 5, 4);
|
||
|
|
G.add_directed_edge(5, 2, 4);
|
||
|
|
G.add_directed_edge(5, 3, 4);
|
||
|
|
G.add_directed_edge(2, 3, 4);
|
||
|
|
G.add_directed_edge(3, 6, 4);
|
||
|
|
|
||
|
|
cout << "foo" << endl;
|
||
|
|
bool cycles = G.has_cycles();
|
||
|
|
cout << "Has cycles: " << cycles << endl;
|
||
|
|
vector<long> dist = G.dijkstra(1);
|
||
|
|
for (int i = 1; i <= 6; i++)
|
||
|
|
cout << i << " " << dist[i] << endl;
|
||
|
|
|
||
|
|
return EXIT_SUCCESS;
|
||
|
|
}
|