1 //=======================================================================
2 // Copyright 2013 Maciej Piechotka
3 // Authors: Maciej Piechotka
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9
10 #include <iostream>
11 #include <boost/config.hpp>
12 #include <boost/graph/adjacency_list.hpp>
13 #include <boost/graph/edge_coloring.hpp>
14 #include <boost/graph/properties.hpp>
15
16 /*
17 Sample output
18 Colored using 5 colors
19 a-d: 4
20 a-f: 0
21 b-c: 2
22 b-e: 3
23 b-g: 1
24 b-j: 0
25 c-d: 0
26 c-e: 1
27 d-f: 2
28 d-i: 1
29 e-g: 4
30 f-g: 3
31 f-h: 1
32 g-h: 0
33 */
34
main(int,char * [])35 int main(int, char*[])
36 {
37 using namespace boost;
38 using namespace std;
39 typedef adjacency_list< vecS, vecS, undirectedS, no_property, size_t,
40 no_property >
41 Graph;
42
43 typedef std::pair< std::size_t, std::size_t > Pair;
44 Pair edges[14] = { Pair(0, 3), // a-d
45 Pair(0, 5), // a-f
46 Pair(1, 2), // b-c
47 Pair(1, 4), // b-e
48 Pair(1, 6), // b-g
49 Pair(1, 9), // b-j
50 Pair(2, 3), // c-d
51 Pair(2, 4), // c-e
52 Pair(3, 5), // d-f
53 Pair(3, 8), // d-i
54 Pair(4, 6), // e-g
55 Pair(5, 6), // f-g
56 Pair(5, 7), // f-h
57 Pair(6, 7) }; // g-h
58
59 Graph G(10);
60
61 for (size_t i = 0; i < sizeof(edges) / sizeof(edges[0]); i++)
62 add_edge(edges[i].first, edges[i].second, G);
63
64 size_t colors = edge_coloring(G, get(edge_bundle, G));
65
66 cout << "Colored using " << colors << " colors" << endl;
67 for (size_t i = 0; i < sizeof(edges) / sizeof(edges[0]); i++)
68 {
69 cout << " " << (char)('a' + edges[i].first) << "-"
70 << (char)('a' + edges[i].second) << ": "
71 << G[edge(edges[i].first, edges[i].second, G).first] << endl;
72 }
73
74 return 0;
75 }
76