ceph/src/boost/boost/graph/edge_coloring.hpp

   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 >
  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 >
  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 >
  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 >
  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 >
 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 >
 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:
 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         }
 148         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 >
 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 >
 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