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 #ifndef BOOST_GRAPH_EDGE_COLORING_HPP
10 #define BOOST_GRAPH_EDGE_COLORING_HPP
11
12 #include <boost/graph/graph_traits.hpp>
13 #include <boost/graph/iteration_macros.hpp>
14 #include <boost/graph/properties.hpp>
15 #include <algorithm>
16 #include <limits>
17 #include <vector>
18
19 /* This algorithm is to find coloring of an edges
20
21 Reference:
22
23 Misra, J., & Gries, D. (1992). A constructive proof of Vizing's
24 theorem. In Information Processing Letters.
25 */
26
27 namespace boost
28 {
29 namespace detail
30 {
31 template < typename Graph, typename ColorMap >
is_free(const Graph & g,ColorMap color,typename boost::graph_traits<Graph>::vertex_descriptor u,typename boost::property_traits<ColorMap>::value_type free_color)32 bool is_free(const Graph& g, ColorMap color,
33 typename boost::graph_traits< Graph >::vertex_descriptor u,
34 typename boost::property_traits< ColorMap >::value_type free_color)
35 {
36 typedef typename boost::property_traits< ColorMap >::value_type color_t;
37 if (free_color == (std::numeric_limits< color_t >::max)())
38 return false;
39 BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
40 {
41 if (get(color, e) == free_color)
42 {
43 return false;
44 }
45 }
46 return true;
47 }
48
49 template < typename Graph, typename ColorMap >
50 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)51 maximal_fan(const Graph& g, ColorMap color,
52 typename boost::graph_traits< Graph >::vertex_descriptor x,
53 typename boost::graph_traits< Graph >::vertex_descriptor y)
54 {
55 typedef
56 typename boost::graph_traits< Graph >::vertex_descriptor vertex_t;
57 std::vector< vertex_t > fan;
58 fan.push_back(y);
59 bool extended;
60 do
61 {
62 extended = false;
63 BGL_FORALL_OUTEDGES_T(x, e, g, Graph)
64 {
65 vertex_t v = target(e, g);
66 if (is_free(g, color, fan.back(), get(color, e))
67 && std::find(fan.begin(), fan.end(), v) == fan.end())
68 {
69 fan.push_back(v);
70 extended = true;
71 }
72 }
73 } while (extended);
74 return fan;
75 }
76 template < typename Graph, typename ColorMap >
find_free_color(const Graph & g,ColorMap color,typename boost::graph_traits<Graph>::vertex_descriptor u)77 typename boost::property_traits< ColorMap >::value_type find_free_color(
78 const Graph& g, ColorMap color,
79 typename boost::graph_traits< Graph >::vertex_descriptor u)
80 {
81 typename boost::property_traits< ColorMap >::value_type c = 0;
82 while (!is_free(g, color, u, c))
83 c++;
84 return c;
85 }
86
87 template < typename Graph, typename ColorMap >
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)88 void invert_cd_path(const Graph& g, ColorMap color,
89 typename boost::graph_traits< Graph >::vertex_descriptor x,
90 typename boost::graph_traits< Graph >::edge_descriptor eold,
91 typename boost::property_traits< ColorMap >::value_type c,
92 typename boost::property_traits< ColorMap >::value_type d)
93 {
94 put(color, eold, d);
95 BGL_FORALL_OUTEDGES_T(x, e, g, Graph)
96 {
97 if (get(color, e) == d && e != eold)
98 {
99 invert_cd_path(g, color, target(e, g), e, d, c);
100 return;
101 }
102 }
103 }
104
105 template < typename Graph, typename ColorMap >
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)106 void invert_cd_path(const Graph& g, ColorMap color,
107 typename boost::graph_traits< Graph >::vertex_descriptor x,
108 typename boost::property_traits< ColorMap >::value_type c,
109 typename boost::property_traits< ColorMap >::value_type d)
110 {
111 BGL_FORALL_OUTEDGES_T(x, e, g, Graph)
112 {
113 if (get(color, e) == d)
114 {
115 invert_cd_path(g, color, target(e, g), e, d, c);
116 return;
117 }
118 }
119 }
120
121 template < typename Graph, typename ColorMap, typename ForwardIterator >
rotate_fan(const Graph & g,ColorMap color,typename boost::graph_traits<Graph>::vertex_descriptor x,ForwardIterator begin,ForwardIterator end)122 void rotate_fan(const Graph& g, ColorMap color,
123 typename boost::graph_traits< Graph >::vertex_descriptor x,
124 ForwardIterator begin, ForwardIterator end)
125 {
126 typedef typename boost::graph_traits< Graph >::edge_descriptor edge_t;
127 if (begin == end)
128 {
129 return;
130 }
131 edge_t previous = edge(x, *begin, g).first;
132 for (begin++; begin != end; begin++)
133 {
134 edge_t current = edge(x, *begin, g).first;
135 put(color, previous, get(color, current));
136 previous = current;
137 }
138 }
139
140 template < typename Graph, typename ColorMap > class find_free_in_fan
141 {
142 public:
find_free_in_fan(const Graph & graph,const ColorMap color,typename boost::property_traits<ColorMap>::value_type d)143 find_free_in_fan(const Graph& graph, const ColorMap color,
144 typename boost::property_traits< ColorMap >::value_type d)
145 : graph(graph), color(color), d(d)
146 {
147 }
operator ()(const typename boost::graph_traits<Graph>::vertex_descriptor u) const148 bool operator()(
149 const typename boost::graph_traits< Graph >::vertex_descriptor u)
150 const
151 {
152 return is_free(graph, color, u, d);
153 }
154
155 private:
156 const Graph& graph;
157 const ColorMap color;
158 const typename boost::property_traits< ColorMap >::value_type d;
159 };
160 }
161
162 template < typename Graph, typename ColorMap >
color_edge(const Graph & g,ColorMap color,typename boost::graph_traits<Graph>::edge_descriptor e)163 typename boost::property_traits< ColorMap >::value_type color_edge(
164 const Graph& g, ColorMap color,
165 typename boost::graph_traits< Graph >::edge_descriptor e)
166 {
167 typedef typename boost::graph_traits< Graph >::vertex_descriptor vertex_t;
168 typedef typename boost::property_traits< ColorMap >::value_type color_t;
169 typedef typename std::vector< vertex_t >::iterator fan_iterator;
170 using namespace detail;
171 vertex_t x = source(e, g), y = target(e, g);
172 std::vector< vertex_t > fan = maximal_fan(g, color, x, y);
173 color_t c = find_free_color(g, color, x);
174 color_t d = find_free_color(g, color, fan.back());
175 invert_cd_path(g, color, x, c, d);
176 fan_iterator w = std::find_if(fan.begin(), fan.end(),
177 find_free_in_fan< Graph, ColorMap >(g, color, d));
178 rotate_fan(g, color, x, fan.begin(), w + 1);
179 put(color, edge(x, *w, g).first, d);
180 return (std::max)(c, d);
181 }
182
183 template < typename Graph, typename ColorMap >
edge_coloring(const Graph & g,ColorMap color)184 typename boost::property_traits< ColorMap >::value_type edge_coloring(
185 const Graph& g, ColorMap color)
186 {
187 typedef typename boost::property_traits< ColorMap >::value_type color_t;
188 BGL_FORALL_EDGES_T(e, g, Graph)
189 {
190 put(color, e, (std::numeric_limits< color_t >::max)());
191 }
192 color_t colors = 0;
193 BGL_FORALL_EDGES_T(e, g, Graph)
194 {
195 colors = (std::max)(colors, color_edge(g, color, e) + 1);
196 }
197 return colors;
198 }
199 }
200
201 #endif
202