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 is_free(const Graph & g,ColorMap color,typename boost::graph_traits<Graph>::vertex_descriptor u,typename boost::property_traits<ColorMap>::value_type free_color)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> maximal_fan(const Graph & g,ColorMap color,typename boost::graph_traits<Graph>::vertex_descriptor x,typename boost::graph_traits<Graph>::vertex_descriptor y)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 find_free_color(const Graph & g,ColorMap color,typename boost::graph_traits<Graph>::vertex_descriptor u)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 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)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 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)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 rotate_fan(const Graph & g,ColorMap color,typename boost::graph_traits<Graph>::vertex_descriptor x,ForwardIterator begin,ForwardIterator end)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: find_free_in_fan(const Graph & graph,const ColorMap color,typename boost::property_traits<ColorMap>::value_type d)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) {} operator ()(const typename boost::graph_traits<Graph>::vertex_descriptor u) const146 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 color_edge(const Graph & g,ColorMap color,typename boost::graph_traits<Graph>::edge_descriptor e)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 edge_coloring(const Graph & g,ColorMap color)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 197