]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | namespace detail { | |
29 | template<typename Graph, typename ColorMap> | |
30 | bool | |
31 | is_free(const Graph &g, | |
32 | 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 | if (get(color, e) == free_color) { | |
41 | return false; | |
42 | } | |
43 | } | |
44 | return true; | |
45 | } | |
46 | ||
47 | template<typename Graph, typename ColorMap> | |
48 | std::vector<typename boost::graph_traits<Graph>::vertex_descriptor> | |
49 | maximal_fan(const Graph &g, | |
50 | ColorMap color, | |
51 | typename boost::graph_traits<Graph>::vertex_descriptor x, | |
52 | typename boost::graph_traits<Graph>::vertex_descriptor y) | |
53 | { | |
54 | typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t; | |
55 | std::vector<vertex_t> fan; | |
56 | fan.push_back(y); | |
57 | bool extended; | |
58 | do { | |
59 | extended = false; | |
60 | BGL_FORALL_OUTEDGES_T(x, e, g, Graph) { | |
61 | vertex_t v = target(e, g); | |
62 | if (is_free(g, color, fan.back(), get(color, e)) && | |
63 | std::find(fan.begin(), fan.end(), v) == fan.end()) { | |
64 | fan.push_back(v); | |
65 | extended = true; | |
66 | } | |
67 | } | |
68 | } while(extended); | |
69 | return fan; | |
70 | } | |
71 | template<typename Graph, typename ColorMap> | |
72 | typename boost::property_traits<ColorMap>::value_type | |
73 | find_free_color(const Graph &g, | |
74 | ColorMap color, | |
75 | typename boost::graph_traits<Graph>::vertex_descriptor u) | |
76 | { | |
77 | typename boost::property_traits<ColorMap>::value_type c = 0; | |
78 | while (!is_free(g, color, u, c)) c++; | |
79 | return c; | |
80 | } | |
81 | ||
82 | template<typename Graph, typename ColorMap> | |
83 | void | |
84 | invert_cd_path(const Graph &g, | |
85 | ColorMap color, | |
86 | typename boost::graph_traits<Graph>::vertex_descriptor x, | |
87 | typename boost::graph_traits<Graph>::edge_descriptor eold, | |
88 | typename boost::property_traits<ColorMap>::value_type c, | |
89 | typename boost::property_traits<ColorMap>::value_type d) | |
90 | { | |
91 | put(color, eold, d); | |
92 | BGL_FORALL_OUTEDGES_T(x, e, g, Graph) { | |
93 | if (get(color, e) == d && e != eold) { | |
94 | invert_cd_path(g, color, target(e, g), e, d, c); | |
95 | return; | |
96 | } | |
97 | } | |
98 | } | |
99 | ||
100 | template<typename Graph, typename ColorMap> | |
101 | void | |
102 | invert_cd_path(const Graph &g, | |
103 | ColorMap color, | |
104 | typename boost::graph_traits<Graph>::vertex_descriptor x, | |
105 | typename boost::property_traits<ColorMap>::value_type c, | |
106 | typename boost::property_traits<ColorMap>::value_type d) | |
107 | { | |
108 | BGL_FORALL_OUTEDGES_T(x, e, g, Graph) { | |
109 | if (get(color, e) == d) { | |
110 | invert_cd_path(g, color, target(e, g), e, d, c); | |
111 | return; | |
112 | } | |
113 | } | |
114 | } | |
115 | ||
116 | template<typename Graph, typename ColorMap, typename ForwardIterator> | |
117 | void | |
118 | rotate_fan(const Graph &g, | |
119 | ColorMap color, | |
120 | typename boost::graph_traits<Graph>::vertex_descriptor x, | |
121 | ForwardIterator begin, | |
122 | ForwardIterator end) | |
123 | { | |
124 | typedef typename boost::graph_traits<Graph>::edge_descriptor edge_t; | |
125 | if (begin == end) { | |
126 | return; | |
127 | } | |
128 | edge_t previous = edge(x, *begin, g).first; | |
129 | for (begin++; begin != end; begin++) { | |
130 | edge_t current = edge(x, *begin, g).first; | |
131 | put(color, previous, get(color, current)); | |
132 | previous = current; | |
133 | } | |
134 | } | |
135 | ||
136 | template<typename Graph, typename ColorMap> | |
137 | class find_free_in_fan | |
138 | { | |
139 | public: | |
140 | find_free_in_fan(const Graph &graph, | |
141 | const ColorMap color, | |
142 | typename boost::property_traits<ColorMap>::value_type d) | |
143 | : graph(graph), | |
144 | color(color), | |
145 | d(d) {} | |
146 | bool operator()(const typename boost::graph_traits<Graph>::vertex_descriptor u) const { | |
147 | return is_free(graph, color, u, d); | |
148 | } | |
149 | private: | |
150 | const Graph &graph; | |
151 | const ColorMap color; | |
152 | const typename boost::property_traits<ColorMap>::value_type d; | |
153 | }; | |
154 | } | |
155 | ||
156 | template<typename Graph, typename ColorMap> | |
157 | typename boost::property_traits<ColorMap>::value_type | |
158 | color_edge(const Graph &g, | |
159 | ColorMap color, | |
160 | typename boost::graph_traits<Graph>::edge_descriptor e) | |
161 | { | |
162 | typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t; | |
163 | typedef typename boost::property_traits<ColorMap>::value_type color_t; | |
164 | typedef typename std::vector<vertex_t>::iterator fan_iterator; | |
165 | using namespace detail; | |
166 | vertex_t x = source(e, g), y = target(e, g); | |
167 | std::vector<vertex_t> fan = maximal_fan(g, color, x, y); | |
168 | color_t c = find_free_color(g, color, x); | |
169 | color_t d = find_free_color(g, color, fan.back()); | |
170 | invert_cd_path(g, color, x, c, d); | |
171 | fan_iterator w = std::find_if(fan.begin(), | |
172 | fan.end(), | |
173 | find_free_in_fan<Graph, ColorMap>(g, color, d)); | |
174 | rotate_fan(g, color, x, fan.begin(), w + 1); | |
175 | put(color, edge(x, *w, g).first, d); | |
176 | return (std::max)(c, d); | |
177 | } | |
178 | ||
179 | template<typename Graph, typename ColorMap> | |
180 | typename boost::property_traits<ColorMap>::value_type | |
181 | edge_coloring(const Graph &g, | |
182 | ColorMap color) | |
183 | { | |
184 | typedef typename boost::property_traits<ColorMap>::value_type color_t; | |
185 | BGL_FORALL_EDGES_T(e, g, Graph) { | |
186 | put(color, e, (std::numeric_limits<color_t>::max)()); | |
187 | } | |
188 | color_t colors = 0; | |
189 | BGL_FORALL_EDGES_T(e, g, Graph) { | |
190 | colors = (std::max)(colors, color_edge(g, color, e) + 1); | |
191 | } | |
192 | return colors; | |
193 | } | |
194 | } | |
195 | ||
196 | #endif |