-
Notifications
You must be signed in to change notification settings - Fork 15
/
ChinesePostman.h
152 lines (128 loc) · 4.03 KB
/
ChinesePostman.h
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
140
141
142
143
144
145
146
147
148
149
150
151
152
#include "Dijkstra.h"
#include "./Minimum-Cost-Perfect-Matching/Matching.h"
#include "./Minimum-Cost-Perfect-Matching/Graph.h"
bool Connected(const Graph & G)
{
vector<bool> visited(G.GetNumVertices(), false);
list<int> L;
int n = 0;
L.push_back(0);
while(not L.empty())
{
int u = L.back();
L.pop_back();
if(visited[u]) continue;
visited[u] = true;
n++;
for(list<int>::const_iterator it = G.AdjList(u).begin(); it != G.AdjList(u).end(); it++)
{
int v = *it;
L.push_back(v);
}
}
return G.GetNumVertices() == n;
}
/*
Solves the chinese postman problem
returns a pair containing a list and a double
the list is the sequence of vertices in the solution
the double is the solution cost
*/
pair< list<int>, double > ChinesePostman(const Graph & G, const vector<double> & cost)
{
//Check if the graph if connected
if(not Connected(G))
throw "Error: Graph is not connected";
//Build adjacency lists using edges in the graph
vector< list<int> > A(G.GetNumVertices(), list<int>());
for(int u = 0; u < G.GetNumVertices(); u++)
A[u] = G.AdjList(u);
//Find vertices with odd degree
vector<int> odd;
for(int u = 0; u < G.GetNumVertices(); u++)
if(A[u].size() % 2)
odd.push_back(u);
//If there are odd degree vertices
if(not odd.empty())
{
//Create a graph with the odd degree vertices
Graph O(odd.size());
for(int u = 0; u < (int)odd.size(); u++)
for(int v = u+1; v < (int)odd.size(); v++)
O.AddEdge(u, v);
vector<double> costO(O.GetNumEdges());
//Find the shortest paths between all odd degree vertices
vector< vector<int> > shortestPath(O.GetNumVertices());
for(int u = 0; u < (int)odd.size(); u++)
{
pair< vector<int>, vector<double> > sp = Dijkstra(G, odd[u], cost);
shortestPath[u] = sp.first ;
//The cost of an edge uv in O will be the cost of the corresponding shortest path in G
for(int v = 0; v < (int)odd.size(); v++)
if(v != u)
costO[ O.GetEdgeIndex(u, v) ] = sp.second[odd[v]];
}
//Find the minimum cost perfect matching of the graph of the odd degree vertices
Matching M(O);
pair< list<int>, double > p = M.SolveMinimumCostPerfectMatching(costO);
list<int> matching = p.first;
//If an edge uv is in the matching, the edges in the shortest path from u to v should be duplicated in G
for(list<int>::iterator it = matching.begin(); it != matching.end(); it++)
{
pair<int, int> p = O.GetEdge(*it);
int u = p.first, v = odd[p.second];
//Go through the path adding the edges
int w = shortestPath[u][v];
while(w != -1)
{
A[w].push_back(v);
A[v].push_back(w);
v = w;
w = shortestPath[u][v];
}
}
}
//Find an Eulerian cycle in the graph implied by A
list<int> cycle;
//This is to keep track of how many times we can traverse an edge
vector<int> traversed(G.GetNumEdges(), 0);
for(int u = 0; u < G.GetNumVertices(); u++)
{
for(list<int>::iterator it = A[u].begin(); it != A[u].end(); it++)
{
int v = *it;
//we do this so that the edge is not counted twice
if(v < u) continue;
traversed[G.GetEdgeIndex(u, v)]++;
}
}
cycle.push_back(0);
list<int>::iterator itp = cycle.begin();
double obj = 0;
while(itp != cycle.end())
{
//Let u be the current vertex in the cycle, starting at the first
int u = *itp;
list<int>::iterator jtp = itp;
jtp++;
//if there are non-traversed edges incident to u, find a subcycle starting at u
//replace u in the cycle by the subcycle
while(not A[u].empty())
{
while(not A[u].empty() and traversed[ G.GetEdgeIndex(u, A[u].back()) ] == 0)
A[u].pop_back();
if(not A[u].empty())
{
int v = A[u].back();
A[u].pop_back();
cycle.insert(jtp, v);
traversed[G.GetEdgeIndex(u, v)]--;
obj += cost[ G.GetEdgeIndex(u, v) ];
u = v;
}
}
//go to the next vertex in the cycle and do the same
itp++;
}
return pair< list<int>, double >(cycle, obj);
}