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
|
//=======================================================================
// Copyright 2013 Maciej Piechotka
// Authors: Maciej Piechotka
//
// 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 <iostream>
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edge_coloring.hpp>
#include <boost/graph/properties.hpp>
/*
Sample output
Colored using 5 colors
a-d: 4
a-f: 0
b-c: 2
b-e: 3
b-g: 1
b-j: 0
c-d: 0
c-e: 1
d-f: 2
d-i: 1
e-g: 4
f-g: 3
f-h: 1
g-h: 0
*/
int main(int, char*[])
{
using namespace boost;
using namespace std;
typedef adjacency_list< vecS, vecS, undirectedS, no_property, size_t,
no_property >
Graph;
typedef std::pair< std::size_t, std::size_t > Pair;
Pair edges[14] = { Pair(0, 3), // a-d
Pair(0, 5), // a-f
Pair(1, 2), // b-c
Pair(1, 4), // b-e
Pair(1, 6), // b-g
Pair(1, 9), // b-j
Pair(2, 3), // c-d
Pair(2, 4), // c-e
Pair(3, 5), // d-f
Pair(3, 8), // d-i
Pair(4, 6), // e-g
Pair(5, 6), // f-g
Pair(5, 7), // f-h
Pair(6, 7) }; // g-h
Graph G(10);
for (size_t i = 0; i < sizeof(edges) / sizeof(edges[0]); i++)
add_edge(edges[i].first, edges[i].second, G);
size_t colors = edge_coloring(G, get(edge_bundle, G));
cout << "Colored using " << colors << " colors" << endl;
for (size_t i = 0; i < sizeof(edges) / sizeof(edges[0]); i++)
{
cout << " " << (char)('a' + edges[i].first) << "-"
<< (char)('a' + edges[i].second) << ": "
<< G[edge(edges[i].first, edges[i].second, G).first] << endl;
}
return 0;
}
|
