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