mirror of
https://github.com/boostorg/graph.git
synced 2026-01-19 16:22:14 +00:00
117 lines
4.3 KiB
HTML
117 lines
4.3 KiB
HTML
<!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>
|