<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <!-- Copyright (c) 2005 Trustees of Indiana University 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) --> <head> <title>Boost Graph Library: Sequential Vertex Coloring</title> </head> <body> <IMG SRC="../../../boost.png" ALT="C++ Boost" width="277" height="86"> <h1><img src="figs/python.gif" alt="(Python)"/><tt>sequential_vertex_coloring</tt></h1> <p> <pre> template<class VertexListGraph, class OrderPA, class ColorMap> typename property_traits<ColorMap>::value_type sequential_vertex_coloring(const VertexListGraph& g, OrderPA order, ColorMap color); template<class VertexListGraph, class ColorMap> typename property_traits<ColorMap>::value_type sequential_vertex_coloring(const VertexListGraph& g, ColorMap color); </pre> <p>Computes a <a href="graph_coloring.html">vertex coloring</a> for the vertices in the graph, using a simple algorithm [<a href="bibliography.html#coleman83">59</a>]. Given vertices ordered v<sub>1</sub>, v<sub>2</sub>, ... , v<sub>n</sub>, for k = 1, 2, ..., n the algorithm assigns v<sub>k</sub> to the smallest possible color. The algorithm does not guarantee an optimum coloring. <p>Here is the coloring that would be produced on a graph given the vertex ordering A, B, C, D, E. <p><img src="figs/sequential_vertex_coloring.png">, <h3>Where Defined</h3> <a href="../../../boost/graph/sequential_vertex_coloring.hpp"><tt>boost/graph/sequential_vertex_coloring.hpp</tt></a> <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="VertexListGraph.html">Vertex List Graph</a> and <a href="AdjacencyGraph.html">Adjacency Graph</a>.<br> <b>Python</b>: The parameter is named <tt>graph</tt>. </blockquote> OUT: <tt>ColorMap color</tt> <blockquote> This property map records the colors of each vertex. It must be a model of <a href="../../property_map/doc/WritablePropertyMap.html">Writeable Property Map</a> whose key type is the same as the vertex descriptor type of the graph and whose value type is an integral type that can store all values of the graph's <tt>vertices_size_type</tt>.<br> <b>Python</b>: Must be an <tt>vertex_int_map</tt> for the graph. </blockquote> IN: <tt>OrderPA order</tt> <blockquote> A mapping from integers in the range <em>[0, num_vertices(g))</em> to the vertices of the graph.<br> <b>Default:</b> A property map ordering the vertices in the same way they are ordered by <tt>vertices(g)</tt>.<br> <b>Python</b>: Unsupported parameter. </blockquote> <h3>Complexity</h3> The time complexity is <em>O(V(d+k))</em>, where <em>V</em> is the number of vertices, <em>d</em> is the maximum degree of the vertices in the graph, and <em>k</em> is the number of colors used. <h3>Example</h3> <pre> typedef adjacency_list<listS, vecS, undirectedS> Graph; typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor; typedef graph_traits<Graph>::vertices_size_type vertices_size_type; typedef property_map<Graph, vertex_index_t>::const_type vertex_index_map; typedef std::pair<int, int> Edge; enum nodes {A, B, C, D, E, n}; Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E), Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B) }; int m = sizeof(edge_array) / sizeof(Edge); Graph g(edge_array, edge_array + m, n); <em>// Test with the normal order</em> std::vector<vertices_size_type> color_vec(num_vertices(g)); iterator_property_map<vertices_size_type*, vertex_index_map> color(&color_vec.front(), get(vertex_index, g)); <b>vertices_size_type num_colors = sequential_vertex_coloring(g, color);</b> </pre> <hr> <TABLE> <TR valign=top> <TD nowrap>Copyright © 1997-2004</TD><TD> <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>, Indiana University (<A HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)<br> <A HREF="http://www.boost.org/people/doug_gregor.html">Douglas Gregor</A>, Indiana University (dgregor -at- cs.indiana.edu)</A>) </TD></TR></TABLE> </body> </html>