Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r85534 - in trunk: boost/graph libs/graph/doc libs/graph/example
From: jewillco_at_[hidden]
Date: 2013-08-31 15:44:08

Author: jewillco
Date: 2013-08-31 15:44:08 EDT (Sat, 31 Aug 2013)
New Revision: 85534
URL: http://svn.boost.org/trac/boost/changeset/85534

Log:
Added edge coloring code from Maciej Piechotka; fixes #8317

Added:
   trunk/boost/graph/edge_coloring.hpp (contents, props changed)
   trunk/libs/graph/doc/edge_coloring.html (contents, props changed)
   trunk/libs/graph/example/edge_coloring.cpp (contents, props changed)
Text files modified:
   trunk/boost/graph/edge_coloring.hpp | 196 ++++++++++++++++++++++++++++++++++++++++
   trunk/libs/graph/doc/edge_coloring.html | 98 ++++++++++++++++++++
   trunk/libs/graph/doc/table_of_contents.html | 1
   trunk/libs/graph/example/Jamfile.v2 | 1
   trunk/libs/graph/example/edge_coloring.cpp | 70 ++++++++++++++
   5 files changed, 366 insertions(+), 0 deletions(-)

Added: trunk/boost/graph/edge_coloring.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/graph/edge_coloring.hpp 2013-08-31 15:44:08 EDT (Sat, 31 Aug 2013) (r85534)
@@ -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

Added: trunk/libs/graph/doc/edge_coloring.html
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/doc/edge_coloring.html 2013-08-31 15:44:08 EDT (Sat, 31 Aug 2013) (r85534)
@@ -0,0 +1,98 @@
+<HTML>
+
+
+
+<Head>
+<Title>Boost Graph Library: Edge Coloring</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1>
+
+<TT>edge_coloring</TT>
+</H1>
+
+
+<P>
+<DIV ALIGN="LEFT">
+<TABLE CELLPADDING=3 border>
+<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH>
+<TD ALIGN="LEFT">undirected, loop-free</TD>
+</TR>
+<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
+<TD ALIGN="LEFT">color</TD>
+</TR>
+<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
+<TD ALIGN="LEFT">time: <i>O(|E| |V|)</i> </TD>
+</TR>
+</TABLE>
+</DIV>
+
+
+<pre>
+ template <class Graph, class ColorMap>
+ typename boost::property_traits<ColorMap>::value_type
+ edge_coloring(const Graph &g, ColorMap color);
+</pre>
+
+<p>Computes an edge coloring for the vertices in the graph, using
+an algorithm proposed by Mista et al. []. Given edges ordered
+e<sub>1</sub>, e<sub>2</sub>, ..., e<sub>n</sub> it assignes a
+colors c<sub>1</sub>, c<sub>2</sub>, ..., c<sub>n</sub> in a way
+that no vertex connects with 2 edges of the same color. Furthermore
+at most m + 1 colors are used.
+
+
+
+<h3>Where defined</h3>
+boost/graph/edge_coloring.hpp
+
+<h3>Parameters</h3>
+
+IN: <tt>const Graph& g</tt>
+<blockquote>
+ The graph object on which the algorithm will be applied. The type
+ <tt>Graph</tt> must be a model of <a href="EdgeListGraph.html">
+ Edge List Graph</a> and <a href="IncidenceGraph.html">Incidence
+ Graph</a>.
+</blockquote>
+
+OUT: <tt>ColorMap color</tt>
+<blockquote>
+ This property map records the colors of each edges. It must be a
+ model of <A HREF="../../property_map/doc/ReadWritePropertyMap.html">
+ Read/Write Property Map</A> whose key type is the same as the edge
+ descriptor type of the graph and whose value type is an integral type
+ that can store all values smaller or equal to m.
+</blockquote>
+
+
+<h3>Example</h3>
+
+See <A
+href="../example/edge_coloring.cpp"><tt>example/king_ordering.cpp</tt></A>.
+
+<h3>See Also</h3>
+
+sequential vertex ordering.
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2013</TD><TD>
+Maciej Piechotka (<A HREF="mailto:uzytkownik2_at_[hidden]">uzytkownik2_at_[hidden]</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>

Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html Sat Aug 31 15:29:22 2013 (r85533)
+++ trunk/libs/graph/doc/table_of_contents.html 2013-08-31 15:44:08 EDT (Sat, 31 Aug 2013) (r85534)
@@ -285,6 +285,7 @@
                   <ol>
                       <li>metric_tsp_approx</li>
                       <LI>sequential_vertex_coloring</li>
+ <LI>edge_coloring</li>
                       <LI>is_bipartite (including two-coloring of bipartite graphs)</li>
                       <LI>find_odd_cycle</li>
                       <LI>maximum_adjacency_search</li>

Modified: trunk/libs/graph/example/Jamfile.v2
==============================================================================
--- trunk/libs/graph/example/Jamfile.v2 Sat Aug 31 15:29:22 2013 (r85533)
+++ trunk/libs/graph/example/Jamfile.v2 2013-08-31 15:44:08 EDT (Sat, 31 Aug 2013) (r85534)
@@ -51,4 +51,5 @@
exe vf2_sub_graph_iso_multi_example : vf2_sub_graph_iso_multi_example.cpp ;
exe sloan_ordering : sloan_ordering.cpp ;
exe hawick_circuits : hawick_circuits.cpp ;
+exe edge_coloring : edge_coloring.cpp ;

Added: trunk/libs/graph/example/edge_coloring.cpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/example/edge_coloring.cpp 2013-08-31 15:44:08 EDT (Sat, 31 Aug 2013) (r85534)
@@ -0,0 +1,70 @@
+//=======================================================================
+// 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)
+//=======================================================================
+
+#include <boost/config.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/edge_coloring.hpp>
+#include <boost/graph/properties.hpp>
+
+/*
+ Sample output
+ Colored using 5 colors
+ a-d: 4
+ a-f: 0
+ b-c: 2
+ b-e: 3
+ b-g: 1
+ b-j: 0
+ c-d: 0
+ c-e: 1
+ d-f: 2
+ d-i: 1
+ e-g: 4
+ f-g: 3
+ f-h: 1
+ g-h: 0
+*/
+
+int main(int, char *[])
+{
+ using namespace boost;
+ using namespace std;
+ typedef adjacency_list<vecS, vecS, undirectedS, no_property, size_t, no_property> Graph;
+
+ typedef std::pair<std::size_t, std::size_t> Pair;
+ Pair edges[14] = { Pair(0,3), //a-d
+ Pair(0,5), //a-f
+ Pair(1,2), //b-c
+ Pair(1,4), //b-e
+ Pair(1,6), //b-g
+ Pair(1,9), //b-j
+ Pair(2,3), //c-d
+ Pair(2,4), //c-e
+ Pair(3,5), //d-f
+ Pair(3,8), //d-i
+ Pair(4,6), //e-g
+ Pair(5,6), //f-g
+ Pair(5,7), //f-h
+ Pair(6,7) }; //g-h
+
+ Graph G(10);
+
+ for (size_t i = 0; i < sizeof(edges)/sizeof(edges[0]); i++)
+ add_edge(edges[i].first, edges[i].second, G).first;
+
+ size_t colors = edge_coloring(G, get(edge_bundle, G));
+
+ cout << "Colored using " << colors << " colors" << endl;
+ for (size_t i = 0; i < sizeof(edges)/sizeof(edges[0]); i++) {
+ cout << " " << (char)('a' + edges[i].first) << "-" << (char)('a' + edges[i].second) << ": " << G[edge(edges[i].first, edges[i].second, G).first] << endl;
+ }
+
+ return 0;
+}
+

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk