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   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