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