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
|
//=======================================================================
// 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)
//=======================================================================
#ifndef BOOST_GRAPH_EDGE_COLORING_HPP
#define BOOST_GRAPH_EDGE_COLORING_HPP
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/properties.hpp>
#include <algorithm>
#include <limits>
#include <vector>
/* This algorithm is to find coloring of an edges
Reference:
Misra, J., & Gries, D. (1992). A constructive proof of Vizing's
theorem. In Information Processing Letters.
*/
namespace boost {
namespace detail {
template<typename Graph, typename ColorMap>
bool
is_free(const Graph &g,
ColorMap color,
typename boost::graph_traits<Graph>::vertex_descriptor u,
typename boost::property_traits<ColorMap>::value_type free_color)
{
typedef typename boost::property_traits<ColorMap>::value_type color_t;
if (free_color == (std::numeric_limits<color_t>::max)())
return false;
BGL_FORALL_OUTEDGES_T(u, e, g, Graph) {
if (get(color, e) == free_color) {
return false;
}
}
return true;
}
template<typename Graph, typename ColorMap>
std::vector<typename boost::graph_traits<Graph>::vertex_descriptor>
maximal_fan(const Graph &g,
ColorMap color,
typename boost::graph_traits<Graph>::vertex_descriptor x,
typename boost::graph_traits<Graph>::vertex_descriptor y)
{
typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
std::vector<vertex_t> fan;
fan.push_back(y);
bool extended;
do {
extended = false;
BGL_FORALL_OUTEDGES_T(x, e, g, Graph) {
vertex_t v = target(e, g);
if (is_free(g, color, fan.back(), get(color, e)) &&
std::find(fan.begin(), fan.end(), v) == fan.end()) {
fan.push_back(v);
extended = true;
}
}
} while(extended);
return fan;
}
template<typename Graph, typename ColorMap>
typename boost::property_traits<ColorMap>::value_type
find_free_color(const Graph &g,
ColorMap color,
typename boost::graph_traits<Graph>::vertex_descriptor u)
{
typename boost::property_traits<ColorMap>::value_type c = 0;
while (!is_free(g, color, u, c)) c++;
return c;
}
template<typename Graph, typename ColorMap>
void
invert_cd_path(const Graph &g,
ColorMap color,
typename boost::graph_traits<Graph>::vertex_descriptor x,
typename boost::graph_traits<Graph>::edge_descriptor eold,
typename boost::property_traits<ColorMap>::value_type c,
typename boost::property_traits<ColorMap>::value_type d)
{
put(color, eold, d);
BGL_FORALL_OUTEDGES_T(x, e, g, Graph) {
if (get(color, e) == d && e != eold) {
invert_cd_path(g, color, target(e, g), e, d, c);
return;
}
}
}
template<typename Graph, typename ColorMap>
void
invert_cd_path(const Graph &g,
ColorMap color,
typename boost::graph_traits<Graph>::vertex_descriptor x,
typename boost::property_traits<ColorMap>::value_type c,
typename boost::property_traits<ColorMap>::value_type d)
{
BGL_FORALL_OUTEDGES_T(x, e, g, Graph) {
if (get(color, e) == d) {
invert_cd_path(g, color, target(e, g), e, d, c);
return;
}
}
}
template<typename Graph, typename ColorMap, typename ForwardIterator>
void
rotate_fan(const Graph &g,
ColorMap color,
typename boost::graph_traits<Graph>::vertex_descriptor x,
ForwardIterator begin,
ForwardIterator end)
{
typedef typename boost::graph_traits<Graph>::edge_descriptor edge_t;
if (begin == end) {
return;
}
edge_t previous = edge(x, *begin, g).first;
for (begin++; begin != end; begin++) {
edge_t current = edge(x, *begin, g).first;
put(color, previous, get(color, current));
previous = current;
}
}
template<typename Graph, typename ColorMap>
class find_free_in_fan
{
public:
find_free_in_fan(const Graph &graph,
const ColorMap color,
typename boost::property_traits<ColorMap>::value_type d)
: graph(graph),
color(color),
d(d) {}
bool operator()(const typename boost::graph_traits<Graph>::vertex_descriptor u) const {
return is_free(graph, color, u, d);
}
private:
const Graph &graph;
const ColorMap color;
const typename boost::property_traits<ColorMap>::value_type d;
};
}
template<typename Graph, typename ColorMap>
typename boost::property_traits<ColorMap>::value_type
color_edge(const Graph &g,
ColorMap color,
typename boost::graph_traits<Graph>::edge_descriptor e)
{
typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef typename boost::property_traits<ColorMap>::value_type color_t;
typedef typename std::vector<vertex_t>::iterator fan_iterator;
using namespace detail;
vertex_t x = source(e, g), y = target(e, g);
std::vector<vertex_t> fan = maximal_fan(g, color, x, y);
color_t c = find_free_color(g, color, x);
color_t d = find_free_color(g, color, fan.back());
invert_cd_path(g, color, x, c, d);
fan_iterator w = std::find_if(fan.begin(),
fan.end(),
find_free_in_fan<Graph, ColorMap>(g, color, d));
rotate_fan(g, color, x, fan.begin(), w + 1);
put(color, edge(x, *w, g).first, d);
return (std::max)(c, d);
}
template<typename Graph, typename ColorMap>
typename boost::property_traits<ColorMap>::value_type
edge_coloring(const Graph &g,
ColorMap color)
{
typedef typename boost::property_traits<ColorMap>::value_type color_t;
BGL_FORALL_EDGES_T(e, g, Graph) {
put(color, e, (std::numeric_limits<color_t>::max)());
}
color_t colors = 0;
BGL_FORALL_EDGES_T(e, g, Graph) {
colors = (std::max)(colors, color_edge(g, color, e) + 1);
}
return colors;
}
}
#endif
|
