forked from spaghetti-source/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhamilton_cycle_ore.cc
More file actions
139 lines (129 loc) · 3.42 KB
/
hamilton_cycle_ore.cc
File metadata and controls
139 lines (129 loc) · 3.42 KB
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//
// Hamilton Cycle for graphs with Ore condition
//
// Description:
// When an undirected graph satisfies the Ore condition,
// d(u) + d(v) >= n, (u,v) not in E.
// it has a Hamiltonian cycle.
//
// Algorithm:
// Palmer's construction.
// Arrange vertices on n-cycle (regardless of the edges).
// For two vertices, i and i+1, with (i,i+1) not in E,
// we find vertex j such that (i,j) and (j+1,i+1) in E.
// We rearrange cycles by
// i -> j -> j-1 -> ... -> i -> j+1,
// which increases the length of a span.
//
// Complexity:
// O(n^2)
//
// References:
// E. M. Palmer (1997): The hidden algorithm of Ore's theorem on Hamiltonian cycles.
// Computers & Mathematics with Applications, vol.34, no.11, pp.113--119.
//
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <unordered_set>
#include <numeric>
#include <functional>
#include <random>
using namespace std;
#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
struct graph {
int n;
vector<unordered_set<int>> adj;
graph(int n) : n(n), adj(n) { }
void add_edge(int src, int dst) {
adj[src].insert(dst);
adj[dst].insert(src);
}
vector<int> hamilton_cycle() {
auto X = [&](int i) { return i < n ? i : i - n; }; // faster than mod
vector<int> cycle(n);
iota(all(cycle), 0);
while (1) {
bool updated = false;
for (int i = 0; i < n; ++i) {
if (adj[cycle[i]].count(cycle[X(i+1)])) continue;
for (int j = i+2; j < i+n; ++j) {
if (adj[cycle[i]].count(cycle[X(j)]) &&
adj[cycle[X(i+1)]].count(cycle[X(j+1)])) {
for (int k = i+1, l = j; k < l; ++k, --l)
swap(cycle[X(k)], cycle[X(l)]);
updated = true;
break;
}
}
}
if (!updated) break;
}
return cycle;
}
};
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << "[";
for (int i = 0; i < v.size(); os << v[i++])
if (i > 0) os << " ";
os << "]";
return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
os << "[";
for (int i = 0; i < v.size(); os << v[i++])
if (i > 0) os << endl << " ";
os << "]";
return os;
}
// === tick a time ===
#include <ctime>
double tick() {
static clock_t oldtick;
clock_t newtick = clock();
double diff = 1.0*(newtick - oldtick) / CLOCKS_PER_SEC;
oldtick = newtick;
return diff;
}
int main() {
for (int seed = 0; seed < 100; ++seed) {
cout << "seed = " << seed << endl;
int n = 500;
graph g(n);
vector<int> ord(n);
iota(all(ord), 0);
//shuffle(all(ord), default_random_engine(time(0)));
auto engine = default_random_engine(seed);
shuffle(all(ord), engine);
for (int i: ord) for (int j: ord) {
if (i == j) continue;
if (engine() % (n/2)) g.add_edge(i, j);
}
while (1) {
bool finish = true;
for (int i: ord) for (int j: ord) {
if (i == j) continue;
if (g.adj[i].count(j)) continue;
if (g.adj[i].size() + g.adj[j].size() < n) {
g.add_edge(i, j);
finish = false;
}
}
if (finish) break;
}
tick();
auto cycle = g.hamilton_cycle();
cout << tick() << endl;
// cout << cycle << endl;
for (int i = 0; i < n; ++i) {
if (!g.adj[cycle[i]].count(cycle[(i+1)%n])) {
cout << "seed = " << seed << ": something wrong\n";
}
}
}
}