/
107.cpp
203 lines (189 loc) · 10.8 KB
/
107.cpp
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>
#include <fstream>
int
main()
{
using namespace boost;
typedef adjacency_list < vecS, vecS, undirectedS,
no_property, property < edge_weight_t, int > > Graph;
typedef graph_traits < Graph >::edge_descriptor Edge;
typedef graph_traits < Graph >::vertex_descriptor Vertex;
typedef std::pair<int, int> E;
const int num_nodes = 7;
E edge_array[] = {E(0, 3), E(0, 4), E(0, 5), E(0, 6), E(0, 7), E(0, 9), E(0, 12), \
E(0, 14), E(0, 15), E(0, 16), E(0, 17), E(0, 18), E(0, 20), E(0, 24), \
E(0, 25), E(0, 26), E(0, 28), E(0, 29), E(0, 30), E(0, 31), E(0, 33), \
E(0, 34), E(0, 35), E(0, 36), E(0, 39), E(1, 2), E(1, 5), E(1, 6), \
E(1, 7), E(1, 9), E(1, 10), E(1, 11), E(1, 12), E(1, 13), E(1, 15), \
E(1, 16), E(1, 17), E(1, 19), E(1, 20), E(1, 21), E(1, 22), E(1, 23), \
E(1, 24), E(1, 25), E(1, 26), E(1, 27), E(1, 29), E(1, 32), E(1, 33), \
E(1, 34), E(1, 36), E(1, 37), E(1, 38), E(1, 39), E(2, 4), E(2, 6), \
E(2, 7), E(2, 8), E(2, 9), E(2, 10), E(2, 11), E(2, 12), E(2, 14), \
E(2, 15), E(2, 16), E(2, 17), E(2, 18), E(2, 19), E(2, 20), E(2, 21), \
E(2, 22), E(2, 26), E(2, 28), E(2, 29), E(2, 30), E(2, 31), E(2, 33), \
E(2, 34), E(2, 36), E(2, 37), E(2, 38), E(2, 39), E(3, 4), E(3, 7), \
E(3, 9), E(3, 10), E(3, 11), E(3, 12), E(3, 13), E(3, 14), E(3, 15), \
E(3, 16), E(3, 17), E(3, 18), E(3, 20), E(3, 21), E(3, 22), E(3, 23), \
E(3, 24), E(3, 27), E(3, 28), E(3, 29), E(3, 31), E(3, 33), E(3, 34), \
E(3, 35), E(3, 38), E(3, 39), E(4, 7), E(4, 8), E(4, 10), E(4, 11), \
E(4, 13), E(4, 15), E(4, 16), E(4, 17), E(4, 18), E(4, 19), E(4, 23), \
E(4, 24), E(4, 25), E(4, 26), E(4, 27), E(4, 28), E(4, 29), E(4, 31), \
E(4, 32), E(4, 35), E(4, 36), E(5, 7), E(5, 8), E(5, 9), E(5, 10), \
E(5, 11), E(5, 12), E(5, 15), E(5, 17), E(5, 19), E(5, 20), E(5, 23), \
E(5, 25), E(5, 28), E(5, 30), E(5, 32), E(5, 33), E(5, 34), E(5, 36), \
E(5, 37), E(5, 38), E(5, 39), E(6, 9), E(6, 10), E(6, 12), E(6, 13), \
E(6, 14), E(6, 15), E(6, 16), E(6, 17), E(6, 21), E(6, 27), E(6, 28), \
E(6, 29), E(6, 30), E(6, 31), E(6, 32), E(6, 34), E(6, 35), E(6, 36), \
E(6, 37), E(6, 38), E(6, 39), E(7, 9), E(7, 11), E(7, 12), E(7, 13), \
E(7, 14), E(7, 16), E(7, 17), E(7, 18), E(7, 19), E(7, 23), E(7, 25), \
E(7, 26), E(7, 27), E(7, 28), E(7, 30), E(7, 31), E(7, 33), E(7, 36), \
E(7, 37), E(7, 38), E(7, 39), E(8, 9), E(8, 11), E(8, 13), E(8, 14), \
E(8, 15), E(8, 16), E(8, 17), E(8, 18), E(8, 21), E(8, 22), E(8, 23), \
E(8, 24), E(8, 25), E(8, 28), E(8, 29), E(8, 30), E(8, 31), E(8, 32), \
E(8, 34), E(8, 38), E(8, 39), E(9, 10), E(9, 12), E(9, 13), E(9, 14), \
E(9, 15), E(9, 16), E(9, 17), E(9, 18), E(9, 21), E(9, 22), E(9, 23), \
E(9, 24), E(9, 25), E(9, 26), E(9, 27), E(9, 28), E(9, 29), E(9, 30), \
E(9, 32), E(9, 33), E(9, 37), E(9, 38), E(9, 39), E(10, 11), E(10, \
12), E(10, 15), E(10, 16), E(10, 17), E(10, 18), E(10, 19), E(10, \
20), E(10, 21), E(10, 22), E(10, 26), E(10, 29), E(10, 30), E(10, \
31), E(10, 32), E(10, 33), E(10, 35), E(10, 36), E(10, 39), E(11, \
14), E(11, 15), E(11, 17), E(11, 18), E(11, 21), E(11, 22), E(11, \
23), E(11, 25), E(11, 26), E(11, 29), E(11, 31), E(11, 32), E(11, \
33), E(11, 34), E(11, 35), E(11, 36), E(11, 38), E(12, 13), E(12, \
14), E(12, 18), E(12, 19), E(12, 21), E(12, 22), E(12, 23), E(12, \
25), E(12, 26), E(12, 27), E(12, 28), E(12, 29), E(12, 30), E(12, \
32), E(12, 33), E(12, 34), E(12, 37), E(12, 38), E(13, 14), E(13, \
16), E(13, 17), E(13, 20), E(13, 21), E(13, 25), E(13, 26), E(13, \
28), E(13, 29), E(13, 30), E(13, 31), E(13, 34), E(13, 35), E(13, \
38), E(13, 39), E(14, 16), E(14, 17), E(14, 18), E(14, 19), E(14, \
21), E(14, 23), E(14, 24), E(14, 25), E(14, 26), E(14, 28), E(14, \
29), E(14, 30), E(14, 32), E(14, 35), E(14, 36), E(14, 37), E(14, \
38), E(15, 16), E(15, 17), E(15, 18), E(15, 19), E(15, 20), E(15, \
22), E(15, 23), E(15, 26), E(15, 27), E(15, 30), E(15, 31), E(15, \
32), E(15, 34), E(15, 36), E(15, 37), E(15, 38), E(16, 18), E(16, \
20), E(16, 23), E(16, 25), E(16, 27), E(16, 30), E(16, 31), E(16, \
32), E(16, 33), E(16, 35), E(16, 37), E(16, 38), E(16, 39), E(17, \
19), E(17, 20), E(17, 21), E(17, 23), E(17, 24), E(17, 25), E(17, \
26), E(17, 27), E(17, 28), E(17, 30), E(17, 34), E(17, 35), E(17, \
38), E(18, 19), E(18, 22), E(18, 23), E(18, 24), E(18, 25), E(18, \
27), E(18, 28), E(18, 29), E(18, 31), E(18, 37), E(19, 21), E(19, \
22), E(19, 23), E(19, 24), E(19, 25), E(19, 26), E(19, 27), E(19, \
28), E(19, 30), E(19, 31), E(19, 32), E(19, 33), E(19, 34), E(19, \
37), E(19, 38), E(19, 39), E(20, 22), E(20, 26), E(20, 27), E(20, \
28), E(20, 29), E(20, 30), E(20, 31), E(20, 33), E(20, 34), E(20, \
37), E(20, 38), E(21, 23), E(21, 28), E(21, 29), E(21, 30), E(21, \
31), E(21, 32), E(21, 34), E(21, 36), E(21, 38), E(22, 23), E(22, \
24), E(22, 26), E(22, 28), E(22, 29), E(22, 30), E(22, 33), E(22, \
34), E(22, 36), E(22, 37), E(22, 38), E(23, 24), E(23, 25), E(23, \
27), E(23, 28), E(23, 29), E(23, 30), E(23, 33), E(23, 35), E(23, \
37), E(23, 38), E(24, 26), E(24, 27), E(24, 28), E(24, 30), E(24, \
31), E(24, 33), E(24, 34), E(24, 35), E(24, 37), E(24, 38), E(24, \
39), E(25, 27), E(25, 31), E(25, 32), E(25, 34), E(25, 35), E(25, \
36), E(25, 38), E(25, 39), E(26, 28), E(26, 29), E(26, 30), E(26, \
32), E(26, 33), E(26, 34), E(26, 36), E(26, 37), E(26, 38), E(26, \
39), E(27, 28), E(27, 29), E(27, 30), E(27, 32), E(27, 34), E(27, \
35), E(27, 36), E(27, 37), E(27, 39), E(28, 29), E(28, 30), E(28, \
31), E(28, 32), E(28, 33), E(28, 34), E(28, 35), E(28, 36), E(28, \
37), E(29, 31), E(29, 32), E(29, 35), E(29, 37), E(29, 38), E(29, \
39), E(30, 31), E(30, 32), E(30, 33), E(30, 34), E(30, 36), E(30, \
37), E(30, 39), E(31, 32), E(31, 33), E(31, 34), E(31, 37), E(31, \
38), E(32, 33), E(32, 37), E(33, 34), E(33, 35), E(33, 36), E(33, \
39), E(34, 35), E(34, 37), E(34, 39), E(35, 36), E(35, 38), E(35, \
39), E(36, 37), E(36, 39), E(37, 38), E(37, 39), E(38, 39)};
int weights[] = {427, 668, 495, 377, 678, 177, 870, 869, 624, 300, 609, 131, 251, \
856, 221, 514, 591, 762, 182, 56, 884, 412, 273, 636, 774, 262, 508, \
472, 799, 956, 578, 363, 940, 143, 162, 122, 910, 729, 802, 941, 922, \
573, 531, 539, 667, 607, 920, 315, 649, 937, 185, 102, 636, 289, 926, \
958, 158, 647, 47, 621, 264, 81, 402, 813, 649, 386, 252, 391, 264, \
637, 349, 108, 727, 225, 578, 699, 898, 294, 575, 168, 432, 833, 366, \
635, 32, 962, 468, 893, 854, 718, 427, 448, 916, 258, 760, 909, 529, \
311, 404, 588, 680, 875, 615, 409, 758, 221, 76, 257, 250, 268, 503, \
944, 677, 727, 793, 457, 981, 191, 351, 969, 925, 987, 328, 282, 589, \
873, 477, 19, 450, 765, 711, 819, 305, 302, 926, 582, 861, 683, 293, \
66, 27, 290, 786, 554, 817, 33, 54, 506, 386, 381, 120, 42, 134, 219, \
457, 639, 538, 374, 966, 449, 120, 797, 358, 232, 550, 305, 997, 662, \
744, 686, 239, 35, 106, 385, 652, 160, 890, 812, 605, 953, 79, 712, \
613, 312, 452, 978, 900, 901, 225, 533, 770, 722, 283, 172, 663, 236, \
36, 403, 286, 986, 810, 761, 574, 53, 793, 777, 330, 936, 883, 286, \
174, 828, 711, 50, 565, 36, 767, 684, 344, 489, 565, 103, 810, 463, \
733, 665, 494, 644, 863, 25, 385, 342, 470, 730, 582, 468, 155, 519, \
256, 990, 801, 154, 53, 474, 650, 402, 966, 406, 989, 772, 932, 7, \
823, 391, 933, 380, 438, 41, 266, 104, 867, 609, 270, 861, 165, 675, \
250, 686, 995, 366, 191, 433, 313, 851, 248, 220, 826, 359, 829, 234, \
198, 145, 409, 68, 359, 814, 218, 186, 929, 203, 132, 433, 598, 168, \
870, 128, 437, 383, 364, 966, 227, 807, 993, 526, 17, 596, 903, 613, \
730, 261, 142, 379, 885, 89, 848, 258, 112, 900, 818, 639, 268, 600, \
539, 379, 664, 561, 542, 999, 585, 321, 398, 950, 68, 193, 697, 390, \
588, 848, 73, 318, 500, 968, 291, 765, 196, 504, 757, 542, 395, 227, \
148, 946, 136, 399, 941, 707, 156, 757, 258, 251, 807, 461, 501, 616, \
686, 575, 627, 817, 282, 698, 398, 222, 649, 654, 389, 729, 553, 304, \
703, 455, 857, 260, 991, 182, 351, 477, 867, 889, 217, 853, 392, 267, \
407, 27, 651, 80, 927, 974, 977, 457, 117, 202, 867, 140, 403, 962, \
785, 511, 1, 707, 388, 939, 959, 83, 463, 361, 512, 931, 224, 690, \
369, 164, 829, 620, 523, 639, 936, 490, 695, 505, 109, 616, 716, 728, \
889, 349, 963, 150, 447, 292, 586, 264, 822, 736, 576, 697, 946, 443, \
205, 194, 349, 156, 339, 102, 790, 359, 439, 938, 809, 260, 293, 486, \
943, 779, 6, 880, 116, 775, 947, 212, 684, 505, 341, 384, 9, 992, \
507, 48, 349, 723, 186, 36, 240, 752, 965, 302, 676, 725, 327, 134, \
147, 474, 178, 833, 555, 853, 689, 451, 245, 596, 445, 343, 949, 270, \
112, 91, 768, 273, 248, 344, 371, 680, 540};
std::size_t num_edges = sizeof(edge_array) / sizeof(E);
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
Graph g(num_nodes);
property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);
for (std::size_t j = 0; j < num_edges; ++j) {
Edge e; bool inserted;
boost::tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
weightmap[e] = weights[j];
}
#else
Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
#endif
property_map < Graph, edge_weight_t >::type weight = get(edge_weight, g);
std::vector < Edge > spanning_tree;
kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));
int cnt = 0;
std::cout << "Print the edges in the MST:" << std::endl;
for (std::vector < Edge >::iterator ei = spanning_tree.begin();
ei != spanning_tree.end(); ++ei) {
std::cout << source(*ei, g) << " <--> " << target(*ei, g)
<< " with weight of " << weight[*ei]
<< std::endl;
cnt += weight[*ei];
}
std::ofstream fout("figs/kruskal-eg.dot");
fout << "graph A {\n"
<< " rankdir=LR\n"
<< " size=\"3,3\"\n"
<< " ratio=\"filled\"\n"
<< " edge[style=\"bold\"]\n" << " node[shape=\"circle\"]\n";
graph_traits<Graph>::edge_iterator eiter, eiter_end;
for (boost::tie(eiter, eiter_end) = edges(g); eiter != eiter_end; ++eiter) {
fout << source(*eiter, g) << " -- " << target(*eiter, g);
if (std::find(spanning_tree.begin(), spanning_tree.end(), *eiter)
!= spanning_tree.end())
fout << "[color=\"black\", label=\"" << get(edge_weight, g, *eiter)
<< "\"];\n";
else
fout << "[color=\"gray\", label=\"" << get(edge_weight, g, *eiter)
<< "\"];\n";
}
fout << "}\n";
std::cout << "Edge Sum is: " << cnt << "\n";
int totwgt = 0;
for(int k=0; k< sizeof(weights)/sizeof(weights[0]); k++)
{
totwgt += weights[k];
}
std::cout << "Initial weight: " << totwgt << " Saved weight: " << totwgt - cnt << "\n";
return EXIT_SUCCESS;
}