123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116 |
- <!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="https://homes.cs.washington.edu/~al75">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>
|