1 | #include <boost/config.hpp>
|
---|
2 | #include <iostream>
|
---|
3 | #include <boost/graph/adjacency_list.hpp>
|
---|
4 | #include <boost/graph/prim_minimum_spanning_tree.hpp>
|
---|
5 |
|
---|
6 | int
|
---|
7 | main()
|
---|
8 | {
|
---|
9 | using namespace boost;
|
---|
10 | typedef adjacency_list < vecS, vecS, undirectedS,
|
---|
11 | property<vertex_distance_t, int>, property < edge_weight_t, int > > Graph;
|
---|
12 | typedef std::pair < int, int >E;
|
---|
13 | const int num_nodes = 6;
|
---|
14 |
|
---|
15 | #if SPECIFY_ONCE
|
---|
16 | E edges_l[] = { E(0, 1), E(0, 2), E(0, 3), E(0, 4), E(0, 5),
|
---|
17 | E(1, 2), E(1, 3), E(1, 4), E(1, 5),
|
---|
18 | E(2, 3), E(2, 4), E(2, 5),
|
---|
19 | E(3, 4), E(3, 5),
|
---|
20 | E(4, 5),
|
---|
21 | };
|
---|
22 | int weights[] = { 6, 7, 26, 9, 2,
|
---|
23 | 1, 26, 10, 5,
|
---|
24 | 27, 11, 6,
|
---|
25 | 17, 24,
|
---|
26 | 7,
|
---|
27 | };
|
---|
28 | #else
|
---|
29 | E edges_l[] = { E(0, 1), E(0, 2), E(0, 3), E(0, 4), E(0, 5),
|
---|
30 | E(1, 0), E(1, 2), E(1, 3), E(1, 4), E(1, 5),
|
---|
31 | E(2, 0), E(2, 1), E(2, 3), E(2, 4), E(2, 5),
|
---|
32 | E(3, 0), E(3, 1), E(3, 2), E(3, 4), E(3, 5),
|
---|
33 | E(4, 0), E(4, 1), E(4, 2), E(4, 3), E(4, 5),
|
---|
34 | E(5, 0), E(5, 1), E(5, 2), E(5, 3), E(5, 4)
|
---|
35 | };
|
---|
36 | int weights[] = { 6, 7, 26, 9, 2,
|
---|
37 | 6, 1, 26, 10, 5,
|
---|
38 | 7, 1, 27, 11, 6,
|
---|
39 | 26, 26, 27, 17, 24,
|
---|
40 | 9, 10, 11, 17, 7,
|
---|
41 | 2, 5, 6, 24, 7
|
---|
42 | };
|
---|
43 | #endif
|
---|
44 |
|
---|
45 | Graph g(edges_l, edges_l + sizeof(edges_l) / sizeof(E), weights, num_nodes);
|
---|
46 | property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);
|
---|
47 |
|
---|
48 | std::vector < graph_traits < Graph >::vertex_descriptor >
|
---|
49 | p(num_vertices(g));
|
---|
50 |
|
---|
51 | #if DEBUG
|
---|
52 | typedef graph_traits<Graph>::edge_iterator edge_iterator;
|
---|
53 | edge_iterator ei, e_end;
|
---|
54 |
|
---|
55 | std::cout << " edge info: " << std::endl;
|
---|
56 | for ( tie(ei, e_end) = edges(g); ei != e_end; ++ei )
|
---|
57 | {
|
---|
58 | std::cout << " from " << source(*ei, g);
|
---|
59 | std::cout << " to " << target(*ei, g);
|
---|
60 | std::cout << " weight " << weightmap[*ei];
|
---|
61 | std::cout << std::endl;
|
---|
62 | }
|
---|
63 | std::cout << std::endl;
|
---|
64 | #endif
|
---|
65 |
|
---|
66 | prim_minimum_spanning_tree(g, &p[0]);
|
---|
67 |
|
---|
68 | for (std::size_t i = 0; i != p.size(); ++i)
|
---|
69 | if (p[i] != i)
|
---|
70 | std::cout << "parent[" << i << "] = " << p[i] << std::endl;
|
---|
71 | else
|
---|
72 | std::cout << "parent[" << i << "] = no parent" << std::endl;
|
---|
73 |
|
---|
74 | return EXIT_SUCCESS;
|
---|
75 | }
|
---|
76 |
|
---|