diff options
Diffstat (limited to 'boost/graph/edge_coloring.hpp')
| -rw-r--r-- | boost/graph/edge_coloring.hpp | 196 |
1 files changed, 196 insertions, 0 deletions
diff --git a/boost/graph/edge_coloring.hpp b/boost/graph/edge_coloring.hpp new file mode 100644 index 0000000000..8eb79ad43b --- /dev/null +++ b/boost/graph/edge_coloring.hpp @@ -0,0 +1,196 @@ +//======================================================================= +// 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 |