boost/graph/edge_coloring.hpp
//======================================================================= // Copyright 2013 Maciej Piechotka // Authors: Maciej Piechotka // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= #ifndef BOOST_GRAPH_EDGE_COLORING_HPP #define BOOST_GRAPH_EDGE_COLORING_HPP #include <boost/graph/graph_traits.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/properties.hpp> #include <algorithm> #include <limits> #include <vector> /* This algorithm is to find coloring of an edges Reference: Misra, J., & Gries, D. (1992). A constructive proof of Vizing's theorem. In Information Processing Letters. */ namespace boost { namespace detail { template < typename Graph, typename ColorMap > 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) { typedef typename boost::property_traits< ColorMap >::value_type color_t; if (free_color == (std::numeric_limits< color_t >::max)()) return false; BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { if (get(color, e) == free_color) { return false; } } return true; } template < typename Graph, typename ColorMap > 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) { typedef typename boost::graph_traits< Graph >::vertex_descriptor vertex_t; std::vector< vertex_t > fan; fan.push_back(y); bool extended; do { extended = false; BGL_FORALL_OUTEDGES_T(x, e, g, Graph) { vertex_t v = target(e, g); if (is_free(g, color, fan.back(), get(color, e)) && std::find(fan.begin(), fan.end(), v) == fan.end()) { fan.push_back(v); extended = true; } } } while (extended); return fan; } template < typename Graph, typename ColorMap > typename boost::property_traits< ColorMap >::value_type find_free_color( const Graph& g, ColorMap color, typename boost::graph_traits< Graph >::vertex_descriptor u) { typename boost::property_traits< ColorMap >::value_type c = 0; while (!is_free(g, color, u, c)) c++; return c; } template < typename Graph, typename ColorMap > 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) { put(color, eold, d); BGL_FORALL_OUTEDGES_T(x, e, g, Graph) { if (get(color, e) == d && e != eold) { invert_cd_path(g, color, target(e, g), e, d, c); return; } } } template < typename Graph, typename ColorMap > 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) { BGL_FORALL_OUTEDGES_T(x, e, g, Graph) { if (get(color, e) == d) { invert_cd_path(g, color, target(e, g), e, d, c); return; } } } template < typename Graph, typename ColorMap, typename ForwardIterator > void rotate_fan(const Graph& g, ColorMap color, typename boost::graph_traits< Graph >::vertex_descriptor x, ForwardIterator begin, ForwardIterator end) { typedef typename boost::graph_traits< Graph >::edge_descriptor edge_t; if (begin == end) { return; } edge_t previous = edge(x, *begin, g).first; for (begin++; begin != end; begin++) { edge_t current = edge(x, *begin, g).first; put(color, previous, get(color, current)); previous = current; } } template < typename Graph, typename ColorMap > class find_free_in_fan { public: find_free_in_fan(const Graph& graph, const ColorMap color, typename boost::property_traits< ColorMap >::value_type d) : graph(graph), color(color), d(d) { } bool operator()( const typename boost::graph_traits< Graph >::vertex_descriptor u) const { return is_free(graph, color, u, d); } private: const Graph& graph; const ColorMap color; const typename boost::property_traits< ColorMap >::value_type d; }; } template < typename Graph, typename ColorMap > typename boost::property_traits< ColorMap >::value_type color_edge( const Graph& g, ColorMap color, typename boost::graph_traits< Graph >::edge_descriptor e) { typedef typename boost::graph_traits< Graph >::vertex_descriptor vertex_t; typedef typename boost::property_traits< ColorMap >::value_type color_t; typedef typename std::vector< vertex_t >::iterator fan_iterator; using namespace detail; vertex_t x = source(e, g), y = target(e, g); std::vector< vertex_t > fan = maximal_fan(g, color, x, y); color_t c = find_free_color(g, color, x); color_t d = find_free_color(g, color, fan.back()); invert_cd_path(g, color, x, c, d); fan_iterator w = std::find_if(fan.begin(), fan.end(), find_free_in_fan< Graph, ColorMap >(g, color, d)); rotate_fan(g, color, x, fan.begin(), w + 1); put(color, edge(x, *w, g).first, d); return (std::max)(c, d); } template < typename Graph, typename ColorMap > typename boost::property_traits< ColorMap >::value_type edge_coloring( const Graph& g, ColorMap color) { typedef typename boost::property_traits< ColorMap >::value_type color_t; BGL_FORALL_EDGES_T(e, g, Graph) { put(color, e, (std::numeric_limits< color_t >::max)()); } color_t colors = 0; BGL_FORALL_EDGES_T(e, g, Graph) { colors = (std::max)(colors, color_edge(g, color, e) + 1); } return colors; } } #endif