boost/graph/edge_coloring.hpp

0001 //=======================================================================
0002 // Copyright 2013 Maciej Piechotka
0003 // Authors: Maciej Piechotka
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 #ifndef BOOST_GRAPH_EDGE_COLORING_HPP
0010 #define BOOST_GRAPH_EDGE_COLORING_HPP
0011
0012 #include <boost/graph/graph_traits.hpp>
0013 #include <boost/graph/iteration_macros.hpp>
0014 #include <boost/graph/properties.hpp>
0015 #include <algorithm>
0016 #include <limits>
0017 #include <vector>
0018
0019 /* This algorithm is to find coloring of an edges
0020
0021    Reference:
0022
0023    Misra, J., & Gries, D. (1992). A constructive proof of Vizing's
0024    theorem. In Information Processing Letters.
0025 */
0026
0027 namespace boost
0028 {
0029 namespace detail
0030 {
0031     template < typename Graph, typename ColorMap >
0032     bool is_free(const Graph& g, ColorMap color,
0033         typename boost::graph_traits< Graph >::vertex_descriptor u,
0034         typename boost::property_traits< ColorMap >::value_type free_color)
0035     {
0036         typedef typename boost::property_traits< ColorMap >::value_type color_t;
0037         if (free_color == (std::numeric_limits< color_t >::max)())
0038             return false;
0039         BGL_FORALL_OUTEDGES_T(u, e, g, Graph)
0040         {
0041             if (get(color, e) == free_color)
0042             {
0043                 return false;
0044             }
0045         }
0046         return true;
0047     }
0048
0049     template < typename Graph, typename ColorMap >
0050     std::vector< typename boost::graph_traits< Graph >::vertex_descriptor >
0051     maximal_fan(const Graph& g, ColorMap color,
0052         typename boost::graph_traits< Graph >::vertex_descriptor x,
0053         typename boost::graph_traits< Graph >::vertex_descriptor y)
0054     {
0055         typedef
0056             typename boost::graph_traits< Graph >::vertex_descriptor vertex_t;
0057         std::vector< vertex_t > fan;
0058         fan.push_back(y);
0059         bool extended;
0060         do
0061         {
0062             extended = false;
0063             BGL_FORALL_OUTEDGES_T(x, e, g, Graph)
0064             {
0065                 vertex_t v = target(e, g);
0066                 if (is_free(g, color, fan.back(), get(color, e))
0067                     && std::find(fan.begin(), fan.end(), v) == fan.end())
0068                 {
0069                     fan.push_back(v);
0070                     extended = true;
0071                 }
0072             }
0073         } while (extended);
0074         return fan;
0075     }
0076     template < typename Graph, typename ColorMap >
0077     typename boost::property_traits< ColorMap >::value_type find_free_color(
0078         const Graph& g, ColorMap color,
0079         typename boost::graph_traits< Graph >::vertex_descriptor u)
0080     {
0081         typename boost::property_traits< ColorMap >::value_type c = 0;
0082         while (!is_free(g, color, u, c))
0083             c++;
0084         return c;
0085     }
0086
0087     template < typename Graph, typename ColorMap >
0088     void invert_cd_path(const Graph& g, ColorMap color,
0089         typename boost::graph_traits< Graph >::vertex_descriptor x,
0090         typename boost::graph_traits< Graph >::edge_descriptor eold,
0091         typename boost::property_traits< ColorMap >::value_type c,
0092         typename boost::property_traits< ColorMap >::value_type d)
0093     {
0094         put(color, eold, d);
0095         BGL_FORALL_OUTEDGES_T(x, e, g, Graph)
0096         {
0097             if (get(color, e) == d && e != eold)
0098             {
0099                 invert_cd_path(g, color, target(e, g), e, d, c);
0100                 return;
0101             }
0102         }
0103     }
0104
0105     template < typename Graph, typename ColorMap >
0106     void invert_cd_path(const Graph& g, ColorMap color,
0107         typename boost::graph_traits< Graph >::vertex_descriptor x,
0108         typename boost::property_traits< ColorMap >::value_type c,
0109         typename boost::property_traits< ColorMap >::value_type d)
0110     {
0111         BGL_FORALL_OUTEDGES_T(x, e, g, Graph)
0112         {
0113             if (get(color, e) == d)
0114             {
0115                 invert_cd_path(g, color, target(e, g), e, d, c);
0116                 return;
0117             }
0118         }
0119     }
0120
0121     template < typename Graph, typename ColorMap, typename ForwardIterator >
0122     void rotate_fan(const Graph& g, ColorMap color,
0123         typename boost::graph_traits< Graph >::vertex_descriptor x,
0124         ForwardIterator begin, ForwardIterator end)
0125     {
0126         typedef typename boost::graph_traits< Graph >::edge_descriptor edge_t;
0127         if (begin == end)
0128         {
0129             return;
0130         }
0131         edge_t previous = edge(x, *begin, g).first;
0132         for (begin++; begin != end; begin++)
0133         {
0134             edge_t current = edge(x, *begin, g).first;
0135             put(color, previous, get(color, current));
0136             previous = current;
0137         }
0138     }
0139
0140     template < typename Graph, typename ColorMap > class find_free_in_fan
0141     {
0142     public:
0143         find_free_in_fan(const Graph& graph, const ColorMap color,
0144             typename boost::property_traits< ColorMap >::value_type d)
0145         : graph(graph), color(color), d(d)
0146         {
0147         }
0148         bool operator()(
0149             const typename boost::graph_traits< Graph >::vertex_descriptor u)
0150             const
0151         {
0152             return is_free(graph, color, u, d);
0153         }
0154
0155     private:
0156         const Graph& graph;
0157         const ColorMap color;
0158         const typename boost::property_traits< ColorMap >::value_type d;
0159     };
0160 }
0161
0162 template < typename Graph, typename ColorMap >
0163 typename boost::property_traits< ColorMap >::value_type color_edge(
0164     const Graph& g, ColorMap color,
0165     typename boost::graph_traits< Graph >::edge_descriptor e)
0166 {
0167     typedef typename boost::graph_traits< Graph >::vertex_descriptor vertex_t;
0168     typedef typename boost::property_traits< ColorMap >::value_type color_t;
0169     typedef typename std::vector< vertex_t >::iterator fan_iterator;
0170     using namespace detail;
0171     vertex_t x = source(e, g), y = target(e, g);
0172     std::vector< vertex_t > fan = maximal_fan(g, color, x, y);
0173     color_t c = find_free_color(g, color, x);
0174     color_t d = find_free_color(g, color, fan.back());
0175     invert_cd_path(g, color, x, c, d);
0176     fan_iterator w = std::find_if(fan.begin(), fan.end(),
0177         find_free_in_fan< Graph, ColorMap >(g, color, d));
0178     rotate_fan(g, color, x, fan.begin(), w + 1);
0179     put(color, edge(x, *w, g).first, d);
0180     return (std::max)(c, d);
0181 }
0182
0183 template < typename Graph, typename ColorMap >
0184 typename boost::property_traits< ColorMap >::value_type edge_coloring(
0185     const Graph& g, ColorMap color)
0186 {
0187     typedef typename boost::property_traits< ColorMap >::value_type color_t;
0188     BGL_FORALL_EDGES_T(e, g, Graph)
0189     {
0190         put(color, e, (std::numeric_limits< color_t >::max)());
0191     }
0192     color_t colors = 0;
0193     BGL_FORALL_EDGES_T(e, g, Graph)
0194     {
0195         colors = (std::max)(colors, color_edge(g, color, e) + 1);
0196     }
0197     return colors;
0198 }
0199 }
0200
0201 #endif