[boost-doc-zh] r285 committed - graph 库文档第21.3.2-21.3.4节
- From: codesite-noreply@xxxxxxxxxx
- To: boost-doc-zh-notify@xxxxxxxxxxxxx
- Date: Sat, 08 Aug 2009 02:43:39 +0000
Revision: 285
Author: alai04
Date: Fri Aug 7 19:42:01 2009
Log: graph 库文档第21.3.2-21.3.4节
http://code.google.com/p/boost-doc-zh/source/detail?r=285
Modified:
/trunk/glossary/glossary.txt
/trunk/libs/disjoint_sets/disjoint_sets.html
/trunk/libs/graph/doc/biconnected_components.html
/trunk/libs/graph/doc/connected_components.html
/trunk/libs/graph/doc/edmonds_karp_max_flow.html
/trunk/libs/graph/doc/incremental_components.html
/trunk/libs/graph/doc/kolmogorov_max_flow.html
/trunk/libs/graph/doc/kruskal_min_spanning_tree.html
/trunk/libs/graph/doc/maximum_matching.html
/trunk/libs/graph/doc/prim_minimum_spanning_tree.html
/trunk/libs/graph/doc/push_relabel_max_flow.html
/trunk/libs/graph/doc/strong_components.html
/trunk/libs/graph/doc/table_of_contents.html
=======================================
--- /trunk/glossary/glossary.txt Wed May 27 01:51:16 2009
+++ /trunk/glossary/glossary.txt Fri Aug 7 19:42:01 2009
@@ -135,6 +135,9 @@
block 内存块
chunk 内存区块 或 区块
+ 7) graph //alai04
+
+
f) misc 其它
rationale 理论注记
原理 // jinq
=======================================
--- /trunk/libs/disjoint_sets/disjoint_sets.html Thu Sep 4 17:45:49 2008
+++ /trunk/libs/disjoint_sets/disjoint_sets.html Fri Aug 7 19:42:01 2009
@@ -1,136 +1,93 @@
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-
-<html>
-<head>
+<html><head>
<meta http-equiv="Content-Language" content="en-us">
- <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
-
- <title>Boost Disjoint Sets</title>
-</head>
-
-<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B"
alink=
-"#FF0000">
- <img src="../../boost.png" alt="C++ Boost" width="277" height=
- "86"><br clear="none">
+ <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
+
+ <title>Boost Disjoint Sets</title></head>
+
+
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+ <img src="../../boost.png" alt="C++ Boost" height="86" width="277"><br
clear="none">
<h1><a name="sec:disjoint-sets" id="sec:disjoint-sets"></a> Disjoint
- Sets</h1>
- <pre>
-disjoint_sets<Rank, Parent, FindCompress>
-</pre>
-
- <p>This is class that provides disjoint sets operations with <i>union by
- rank</i> and <i>path compression</i>. A disjoint-sets data structure
- maintains a collection <i>S = {S<sub>1</sub>, S<sub>2</sub>, ...,
- S<sub>k</sub>}</i> of disjoint sets. Each set is identified by a
- <i>representative</i> which is some member of of the set. Sets are
- represented by rooted trees which are encoded in the <tt>Parent</tt>
- property map. Two heuristics: "union by rank" and "path compression" are
- used to speed up the operations [<a href=
- "./bibliography.html#tarjan83:_data_struct_network_algo">1</a>, <a href=
- "./bibliography.html#clr90">2</a>].</p>
-
- <h3>Where Defined</h3><a href=
- "../../boost/pending/disjoint_sets.hpp"><tt>boost/disjoint_sets.hpp</tt></a>
-
- <h3>Template Parameters</h3>
-
- <table border summary="">
- <tr>
+ Sets 不相交集合</h1>
+ <pre>disjoint_sets<Rank, Parent, FindCompress><br></pre>
+
+ <p>这个类提供带有 <i>按秩合并</i> 以及 <i>路径压缩</i> 的不相交集合操作。
不相交集合数据结构维护不相交集合的一个聚集 <i>S = {S<sub>1</sub>,
S<sub>2</sub>, ...,
+ S<sub>k</sub>}</i>。每个集合通过一个 <i>代表representative</i> 来标识，该
代表是集合中的某个成员。集合通过有根树来表示，该有限树被编码至
<tt>Parent</tt>
+ 属性映射。两个启发式策略："按秩合并" 和 "路径压缩" 用于加快操作的速度[<a
href="./bibliography.html#tarjan83:_data_struct_network_algo">1</a>, <a
href="./bibliography.html#clr90">2</a>]。</p>
+
+ <h3>Where Defined 定义于</h3><a
href="../../boost/pending/disjoint_sets.hpp"><tt>boost/disjoint_sets.hpp</tt></a>
+
+ <h3>Template Parameters 模板参数</h3>
+
+ <table summary="" border="1">
+ <tbody><tr>
<td><tt>Rank</tt></td>
- <td>must be a model of <a href=
- "../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>
- with an integer value type and a key type equal to the set's element
- type.</td>
+ <td>必须符合 <a href="../property_map/ReadWritePropertyMap.html">读写
属性映射</a>，具有整数值类型以及与集合的元素类型相同的键类型。</td>
</tr>
<tr>
<td><tt>Parent</tt></td>
- <td>must be a model of <a href=
- "../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>
- and the key and value type the same as the set's element type.</td>
+ <td>必须符合 <a href="../property_map/ReadWritePropertyMap.html">读写
属性映射</a>，键类型和值类型均与集合的元素类型相同。</td>
</tr>
<tr>
<td><tt>FindCompress</tt></td>
- <td>should be one of the find representative and path compress
function
- objects.</td>
+ <td>应为 查找代表 和 路径压缩 函数对象之一。</td>
</tr>
- </table>
-
- <h3>Example</h3>
-
- <p>A typical usage pattern for <tt>disjoint_sets</tt> can be seen in the
- <a href=
-
"../graph/doc/kruskal_min_spanning_tree.html"><tt>kruskal_minimum_spanning_tree()</tt></a>
- algorithm. In this example, we call <tt>link()</tt> instead of
- <tt>union_set()</tt> because <tt>u</tt> and <tt>v</tt> were obtained from
- <tt>find_set()</tt> and therefore are already the representatives for
their
- sets.</p>
- <pre>
- ...
- disjoint_sets<Rank, Parent, FindCompress> dsets(rank, p);
-
- for (ui = vertices(G).first; ui != vertices(G).second; ++ui)
- dsets.make_set(*ui);
- ...
- while ( !Q.empty() ) {
- e = Q.front();
- Q.pop();
- u = dsets.find_set(source(e));
- v = dsets.find_set(target(e));
- if ( u != v ) {
- *out++ = e;
- dsets.link(u, v);
- }
- }
-</pre>
-
- <h3>Members</h3>
-
- <table border summary="">
- <tr>
- <th>Member</th>
-
- <th>Description</th>
+ </tbody></table>
+
+ <h3>Example 示例</h3>
+
+ <p><tt>disjoint_sets</tt> 的一个典型使用模式可见于 <a
href="../graph/doc/kruskal_min_spanning_tree.html"><tt>kruskal_minimum_spanning_tree()</tt></a>
+ 算法。在此例子中，我们调用 <tt>link()</tt> 而不是
+ <tt>union_set()</tt>，因为 <tt>u</tt> 和 <tt>v</tt> 是从
<tt>find_set()</tt> 得到的，因此它们已是所属集合的代表。</p>
+ <pre> ...<br> disjoint_sets<Rank, Parent, FindCompress>
dsets(rank, p);<br> <br> for (ui = vertices(G).first; ui !=
vertices(G).second; ++ui)<br> dsets.make_set(*ui);<br> ...<br> while
( !Q.empty() ) {<br> e = Q.front();<br> Q.pop();<br> u =
dsets.find_set(source(e));<br> v = dsets.find_set(target(e));<br> if
( u != v ) {<br> *out++ = e;<br> dsets.link(u, v);<br> }<br>
}<br></pre>
+
+ <h3>Members 成员</h3>
+
+ <table summary="" border="1">
+ <tbody><tr>
+ <th>成员</th>
+
+ <th>说明</th>
</tr>
<tr>
<td><tt>disjoint_sets(Rank r, Parent p)</tt></td>
- <td>Constructor.</td>
+ <td>构造函数。</td>
</tr>
<tr>
<td><tt>disjoint_sets(const disjoint_sets& x)</tt></td>
- <td>Copy constructor.</td>
+ <td>复制构造函数。</td>
</tr>
<tr>
<td><tt>template <class Element><br>
void make_set(Element x)</tt></td>
- <td>Creates a singleton set containing Element <tt>x</tt>.</td>
+ <td>构造一个单件集合，包含 Element <tt>x</tt>.</td>
</tr>
<tr>
<td><tt>template <class Element><br>
void link(Element x, Element y)</tt></td>
- <td>Union the two sets <i>represented</i> by element <tt>x</tt> and
- <tt>y</tt>.</td>
+ <td>合并由元素 <tt>x</tt> 和 <tt>y</tt> 所代表的两个集合。</td>
</tr>
<tr>
<td><tt>template <class Element><br>
void union_set(Element x, Element y)</tt></td>
- <td>Union the two sets that <i>contain</i> elements <tt>x</tt> and
- <tt>y</tt>. This is equivalent to
+ <td>合并包含元素 <tt>x</tt> 和 <tt>y</tt> 的两个集合。等价于
<tt>link(find_set(x),find_set(y))</tt>.</td>
</tr>
@@ -138,8 +95,8 @@
<td><tt>template <class Element><br>
Element find_set(Element x)</tt></td>
- <td>Return the representative for the set containing element
- <tt>x</tt>.</td>
+ <td>返回包含元素
+ <tt>x</tt> 的集体的代表。</td>
</tr>
<tr>
@@ -147,7 +104,7 @@
std::size_t count_sets(ElementIterator first, ElementIterator
last)</tt></td>
- <td>Returns the number of disjoint sets.</td>
+ <td>返回不相交集合的数量。</td>
</tr>
<tr>
@@ -155,56 +112,36 @@
void compress_sets(ElementIterator first, ElementIterator
last)</tt></td>
- <td>Flatten the parents tree so that the parent of every element is
its
- representative.</td>
+ <td>将父节点树压平，使得每个元素的父节点为其代表。</td>
</tr>
- </table>
-
- <h3>Complexity</h3>
-
- <p>The time complexity is <i>O(m alpha(m,n))</i>, where <i>alpha</i> is
the
- inverse Ackermann's function, <i>m</i> is the number of disjoint-set
- operations (<tt>make_set()</tt>, <tt>find_set()</tt>, and <tt>link()</tt>
- and <i>n</i> is the number of elements. The <i>alpha</i> function grows
- very slowly, much more slowly than the <i>log</i> function.</p>
-
- <h3>See Also</h3><a href=
-
"../graph/doc/incremental_components.html"><tt>incremental_connected_components()</tt></a>
+ </tbody></table>
+
+ <h3>Complexity 复杂度</h3>
+
+ <p>时间复杂度为 <i>O(m alpha(m,n))</i>，其中 <i>alpha</i> 为逆 Ackermann
函数，<i>m</i> 为不相交集合操作(<tt>make_set()</tt>, <tt>find_set()</tt>,
和 <tt>link()</tt>)的数量，<i>n</i> 为元素数量。函数 <i>alpha</i> 增长非常缓
慢，比 <i>log</i> 函数要慢得多。</p>
+
+ <h3>See Also 参见</h3><a
href="../graph/doc/incremental_components.html"><tt>incremental_connected_components()</tt></a>
<hr>
- <pre>
-disjoint_sets_with_storage<ID,InverseID,FindCompress>
-</pre>
-
- <p>This class manages the storage for the rank and parent properties
- internally. The storage is in arrays, which are indexed by element ID,
- hence the requirement for the <tt>ID</tt> and <tt>InverseID</tt>
functors.
- The rank and parent properties are initialized during construction so the
- each element is in a set by itself (so it is not necessary to initialize
- objects of this class with the <a href=
-
"../graph/doc/incremental_components.html#sec:initialize-incremental-components">
- <tt>initialize_incremental_components()</tt></a> function). This class is
- especially useful when computing the (dynamic) connected components of an
- <tt>edge_list</tt> graph which does not provide a place to store vertex
- properties.</p>
-
- <h3>Template Parameters</h3>
-
- <table border summary="">
- <tr>
- <th>Parameter</th>
-
- <th>Description</th>
-
- <th>Default</th>
+
<pre>disjoint_sets_with_storage<ID,InverseID,FindCompress><br></pre>
+
+ <p>该类管理内部的 rank 和 parent 属性的存储。存储是用数组的，以元素ID为索
引，因此需要有 <tt>ID</tt> 和 <tt>InverseID</tt> 仿函数。rank 和 parent 属性
在构造时进行初始化，每个元素属于其自身的一个集合(因此对于 <a
href="../graph/doc/incremental_components.html#sec:initialize-incremental-components">
+ <tt>initialize_incremental_components()</tt></a> 函数不需要初始化该类的对
象)。在计算一个不提供顶点属性存储的 <tt>edge_list</tt> 图的(动态)连通分支
时，这个类尤其有用。</p>
+
+ <h3>Template Parameters 模板参数</h3>
+
+ <table summary="" border="1">
+ <tbody><tr>
+ <th>参数</th>
+
+ <th>说明</th>
+
+ <th>缺省值</th>
</tr>
<tr>
<td><tt>ID</tt></td>
- <td>must be a model of <a href=
- "../property_map/ReadablePropertyMap.html">ReadablePropertyMap</a>
that
- maps elements to integers between zero 0 and N, the total number of
- elements in the sets.</td>
+ <td>必须符合 <a href="../property_map/ReadablePropertyMap.html">可读
属性映射</a>，将元素映射至 0 到 N 的整数，N为集合中的元素总数。</td>
<td><tt>boost::identity_property_map</tt></td>
</tr>
@@ -212,9 +149,7 @@
<tr>
<td><tt>InverseID</tt></td>
- <td>must be a model of <a href=
- "../property_map/ReadablePropertyMap.html">ReadablePropertyMap</a>
that
- maps integers to elements.</td>
+ <td>必须符合 <a href="../property_map/ReadablePropertyMap.html">可读
属性映射</a>，将整数映射至元素。</td>
<td><tt>boost::identity_property_map</tt></td>
</tr>
@@ -222,88 +157,55 @@
<tr>
<td><tt>FindCompress</tt></td>
- <td>should be one of the find representative and path compress
function
- objects.</td>
+ <td>应为 查找代表 和 路径压缩 函数对象之一。</td>
<td><tt>representative_with_full_path_compression</tt></td>
</tr>
- </table>
-
- <h3>Members</h3>
-
- <p>This class has all of the members in <tt>disjoint_sets</tt> as well as
- the following members.</p>
- <pre>
-disjoint_sets_with_storage(size_type n = 0,
- ID id = ID(),
- InverseID inv = InverseID())
-</pre>Constructor.
- <pre>
-template <class ElementIterator>
-void disjoint_sets_with_storage::
- normalize_sets(ElementIterator first, ElementIterator last)
-</pre>This rearranges the representatives such that the representative of
-each set is the element with the smallest ID.<br>
- Postcondition: <tt>v >= parent[v]</tt><br>
- Precondition: the disjoint sets structure must be compressed.<br>
+ </tbody></table>
+
+ <h3>Members 成员</h3>
+
+ <p>该类带有 <tt>disjoint_sets</tt> 的所有成员，以及以下成员。</p>
+ <pre>disjoint_sets_with_storage(size_type n =
0,<br> ID id =
ID(),<br> InverseID inv = InverseID())<br></pre>构
造函数。
+ <pre>template <class ElementIterator><br>void
disjoint_sets_with_storage::<br> normalize_sets(ElementIterator first,
ElementIterator last)<br></pre>对代表进行重排，令每个集合的代表均为最小ID的
元素。<br>后验条件：<tt>v >= parent[v]</tt><br>先验条件：不相交集合结构必
须是已压缩的。<br>
<hr>
- <h2><a name="sec:representative-with-path-halving" id=
- "sec:representative-with-path-halving"></a></h2>
- <pre>
-representative_with_path_halving<Parent>
-</pre>
-
- <p>This is a functor which finds the representative vertex for the same
- component as the element <tt>x</tt>. While traversing up the
representative
- tree, the functor also applies the path halving technique to shorten the
- height of the tree.</p>
- <pre>
-Element operator()(Parent p, Element x)
-</pre>
+ <h2><a name="sec:representative-with-path-halving"
id="sec:representative-with-path-halving"></a></h2>
+ <pre>representative_with_path_halving<Parent><br></pre>
+
+ <p>这是一个仿函数，查找与元素 <tt>x</tt> 同一分支的代表顶点。在树中遍历
时，该仿函数还会使用路径减半技术来缩短树的高度。</p>
+ <pre>Element operator()(Parent p, Element x)<br></pre>
<hr>
- <h2><a name="sec:representative-with-full-path-compression" id=
- "sec:representative-with-full-path-compression"></a><br></h2>
- <pre>
-representative_with_full_path_compression<Parent>
-</pre>
-
- <p>This is a functor which finds the representative element for the set
- that element <tt>x</tt> belongs to.</p>
- <pre>
-Element operator()(Parent p, Element x)
-</pre>
+ <h2><a name="sec:representative-with-full-path-compression"
id="sec:representative-with-full-path-compression"></a><br></h2>
+ <pre>representative_with_full_path_compression<Parent><br></pre>
+
+ <p>这是一个仿函数，查找元素 <tt>x</tt> 所属集合的代表。</p>
+ <pre>Element operator()(Parent p, Element x)<br></pre>
<p><br></p>
<hr>
- <p><a href="http://validator.w3.org/check?uri=referer";><img border="0"
src=
- "http://www.w3.org/Icons/valid-html401"; alt="Valid HTML 4.01
Transitional"
- height="31" width="88"></a></p>
+ <p><a href="http://validator.w3.org/check?uri=referer";><img
src="http://www.w3.org/Icons/valid-html401"; alt="Valid HTML 4.01
Transitional" border="0" height="31" width="88"></a></p>
<p>Revised
<!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y"
startspan -->01
December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38508"
--></p>
<table summary="">
- <tr valign="top">
- <td nowrap><i>Copyright © 2000</i></td>
+ <tbody><tr valign="top">
+ <td nowrap="nowrap"><i>Copyright © 2000</i></td>
<td><i><a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy
Siek</a>, Univ.of
Notre Dame (<a
href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)<br>
<a href="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan
Lee</a>,
- Univ.of Notre Dame (<a href=
- "mailto:llee1@xxxxxxxxxx";>llee1@xxxxxxxxxx</a>)<br>
- <a href="http://www.lsc.nd.edu/~lums";>Andrew Lumsdaine</a>, Univ.of
- Notre Dame (<a href=
- "mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</a>)</i></td>
+ Univ.of Notre Dame (<a
href="mailto:llee1@xxxxxxxxxx";>llee1@xxxxxxxxxx</a>)<br>
+ <a href="http://www.lsc.nd.edu/%7Elums";>Andrew Lumsdaine</a>, Univ.of
+ Notre Dame (<a
href="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</a>)</i></td>
</tr>
- </table>
+ </tbody></table>
<p><i>Distributed under the Boost Software License, Version 1.0. (See
accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or
- copy at <a href=
-
"http://www.boost.org/LICENSE_1_0.txt";>http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
-</body>
-</html>
+ copy at <a
href="http://www.boost.org/LICENSE_1_0.txt";>http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
+</body></html>
=======================================
--- /trunk/libs/graph/doc/biconnected_components.html Mon Mar 30 07:58:04
2009
+++ /trunk/libs/graph/doc/biconnected_components.html Fri Aug 7 19:42:01
2009
@@ -1,5 +1,5 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright 2001-2004 The Trustees of Indiana University.
--
-- Use, modification and distribution is subject to the Boost Software
@@ -10,245 +10,171 @@
-- Jeremy Siek
-- Andrew Lumsdaine
-->
-<Head>
-<Title>Boost Graph Library: Biconnected Components and Articulation
Points</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>
+<title>Boost Graph Library: Biconnected Components and Articulation
Points</title></head>
+
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+
+<br clear="">
<h1>
-<TT>
-<img src="figs/python.gif" alt="(Python)"/>
-<A NAME="sec:biconnected-components">biconnected_components
-</A>
-</TT>
+<tt>
+<img src="figs/python.gif" alt="(Python)">
+<a name="sec:biconnected-components">biconnected_components
+</a>
+</tt>
and
<tt>articulation_points</tt>
</h1>
-<PRE>
-<i>// named parameter version</i>
+<pre><i>// 命名参数版本</i>
template <typename Graph, typename ComponentMap, typename
OutputIterator,
typename P, typename T, typename R>
std::pair<std::size_t, OutputIterator>
-biconnected_components(const Graph& g, ComponentMap comp, OutputIterator
out,
+biconnected_components(const Graph& g, ComponentMap comp,
OutputIterator out,
const bgl_named_params<P, T, R>& params)
template <typename Graph, typename ComponentMap,
typename P, typename T, typename R>
std::size_t
-biconnected_components(const Graph& g, ComponentMap comp,
+biconnected_components(const Graph& g, ComponentMap comp,
const bgl_named_params<P, T, R>& params)
template <typename Graph, typename OutputIterator,
typename P, typename T, typename R>
-OutputIterator articulation_points(const Graph& g, OutputIterator out,
+OutputIterator articulation_points(const Graph& g, OutputIterator out,
const bgl_named_params<P, T,
R>& params)
-<i>// non-named parameter version</i>
+<i>// 非命名参数版本</i>
template <typename Graph, typename ComponentMap, typename
OutputIterator,
typename DiscoverTimeMap, typename LowPointMap>
std::pair<std::size_t, OutputIterator>
-biconnected_components(const Graph& g, ComponentMap comp, OutputIterator
out,
+biconnected_components(const Graph& g, ComponentMap comp,
OutputIterator out,
DiscoverTimeMap discover_time, LowPointMap lowpt);
template <typename Graph, typename ComponentMap, typename
OutputIterator>
std::pair<std::size_t, OutputIterator>
-biconnected_components(const Graph& g, ComponentMap comp, OutputIterator
out);
+biconnected_components(const Graph& g, ComponentMap comp,
OutputIterator out);
template <typename Graph, typename ComponentMap>
-std::size_t biconnected_components(const Graph& g, ComponentMap comp);
+std::size_t biconnected_components(const Graph& g, ComponentMap comp);
<a name="sec:articulation_points">
template <typename Graph, typename OutputIterator>
-OutputIterator articulation_points(const Graph& g, OutputIterator out);
-</PRE>
-
-<P>
-A connected graph is <i>biconnected</i> if the removal of any single
-vertex (and all edges incident on that vertex) can not disconnect the
-graph. More generally, the biconnected components of a graph are the
-maximal subsets of vertices such that the removal of a vertex from a
-particular component will not disconnect the component. Unlike
-connected components, vertices may belong to multiple biconnected
-components: those vertices that belong to more than one biconnected
-component are called <em>articulation points</em> or, equivalently,
-<em>cut vertices</em>. Articulation points are vertices whose removal
-would increase the number of connected components in the graph. Thus,
-a graph without articulation points is biconnected. The following
-figure illustrates the articulation points and biconnected components
-of a small graph:
-
-<p><center><img src="figs/biconnected.png"></center>
-
-<p>Vertices can be present in multiple biconnected components, but each
-edge can only be contained in a single biconnected component. The
-output of the <tt>biconnected_components</tt> algorithm records the
-biconnected component number of each edge in the property map
-<tt>comp</tt>. Articulation points will be emitted to the (optional)
-output iterator argument to <tt>biconnected_components</tt>, or can be
-computed without the use of a biconnected component number map via
-<tt>articulation_points</tt>. These functions return the number of
-biconnected components, the articulation point output iterator, or a
-pair of these quantities, depending on what information was
-recorded.
-
-<p>The algorithm implemented is due to Tarjan [<a
href="bibliography.html#tarjan72:dfs_and_linear_algo">41</a>].
-
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/biconnected_components.hpp"><TT>boost/graph/biconnected_components.hpp</TT></a>
+OutputIterator articulation_points(const Graph& g, OutputIterator out);
+</a></pre>
+
+<p>
+<a name="sec:articulation_points">一个连通图如果移除其任一个顶点(及该顶点关
联的所有边)，该图仍然连通，则称该图为 <i>双连通biconnected</i> 的。一般来
说，一个图的双连通分支是指满足以下条件的最大顶点子集，从该子图中去掉任一顶点
都不会令子图变为不连通。与连通分支不同，一个顶点可能属于多个双连通分支：那些
属于一个以上双连通分支的顶点被称为 <em>挂接点</em> 或
+<em>分割点</em>。挂接点是这样的顶点，移除它们将会增加图中连通分支的数量。因
此，没有挂接点的图是双连通的。下图示范了一个小图中的挂接点和双连通分支：
+
+</a></p><p></p><center><a name="sec:articulation_points"><img
src="figs/biconnected.png"></a></center>
+
+<p><a name="sec:articulation_points">一个顶点可以出现在多个双连通分支中，但
每条边只能属于一个双连通分支。<tt>biconnected_components</tt> 算法的输出将每
条边所属的双连通分支号记录在属性映射
+<tt>comp</tt>中。挂接点则被输出至</a> <tt>biconnected_components</tt> (可选
的)输出迭代器参数，或者通过
+<tt>articulation_points</tt>
+来计算，不需要使用双连通分支号映射。这些函数返回双连通分支的数量、挂接点输
出迭代器，或者这些数量的值对，这取决于记录了哪些信息。
+
+</p><p><a name="sec:articulation_points">该算法的实现归功于 Tarjan [</a><a
href="bibliography.html#tarjan72:dfs_and_linear_algo">41</a>].
+
+</p><h3>Where Defined 定义于</h3>
+
+<p>
+<a
href="../../../boost/graph/biconnected_components.hpp"><tt>boost/graph/biconnected_components.hpp</tt></a>
-<h3>Parameters</h3>
+</p><h3>Parameters 参数</h3>
IN: <tt>const Graph& g</tt>
-<blockquote>
-An undirected graph. The graph type must be a model of <a
-href="VertexListGraph.html">Vertex List Graph</a> and <a
-href="IncidenceGraph.html">Incidence Graph</a>.<br>
-<b>Python</b>: The parameter is named <tt>graph</tt>.
+<blockquote>一个无向图。图的类型必须符合 <a href="VertexListGraph.html">点
列表图Vertex List Graph</a> 和 <a href="IncidenceGraph.html">关联图
Incidence Graph</a>。<br>
+<b>Python</b>: 该参数名为 <tt>graph</tt>.
</blockquote>
OUT: <tt>ComponentMap c</tt>
-<blockquote>
-The algorithm computes how many biconnected components are in the graph,
-and assigning each component an integer label. The algorithm then
-records which component each edge in the graph belongs to by
-recording the component number in the component property map. The
-<tt>ComponentMap</tt> type must be a model of <a
-href="../../property_map/WritablePropertyMap.html">Writable Property
-Map</a>. The value type shouch be an integer type, preferably the same
-as the <tt>edges_size_type</tt> of the graph. The key type must be
-the graph's edge descriptor type.<br>
-<b>Default</b>: <tt>dummy_property_map</tt>.<br>
- <b>Python</b>: Must be an <tt>edge_int_map</tt> for the graph.<br>
- <b>Python default</b>: <tt>graph.get_edge_int_map("bicomponent")</tt>
+<blockquote>该算法计算图中有多少双连通分支，并赋给每个分支一个整数标签。然
后该算法通过将分支号写入分支属性映射，来记录每条边属于哪个分支。类型
+<tt>ComponentMap</tt> 必须符合 <a
href="../../property_map/WritablePropertyMap.html">可写属性映射</a>。其值类
型应为整数类型，最好与图的 <tt>edges_size_type</tt> 相同。键类型则必须为图的
边描述符类型。<br>
+<b>缺省值：</b><tt>dummy_property_map</tt>.<br>
+ <b>Python</b>: 必须是该图的一个 <tt>edge_int_map</tt>。<br>
+ <b>Python 缺省值：</b><tt>graph.get_edge_int_map("bicomponent")</tt>
</blockquote>
OUT: <tt>OutputIterator out</tt>
-<blockquote>
-The algorithm writes articulation points via this output
-iterator and returns the resulting iterator.<br>
-<b>Default</b>: a dummy iterator that ignores values written to it.<br>
-
-<b>Python</b>: this parameter is not used in Python. Instead, both
-algorithms return a Python <tt>list</tt> containing the articulation
-points.
+<blockquote>该算法通过这个输出迭代器写出挂接点，并返回结果迭代器。<br>
+<b>缺省值：</b>一个哑迭代器，忽略写入的值。<br>
+
+<b>Python</b>: Python 中没有使用该参数。而是返回一个包含有挂接点的 Python
<tt>list</tt>。
</blockquote>
-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>
IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
-<blockquote>
- This maps each vertex to an integer in the range <tt>[0,
- num_vertices(g))</tt>. The type
- <tt>VertexIndexMap</tt> must be a model of
- <a href="../../property_map/ReadablePropertyMap.html">Readable Property
Map</a>. The value type of the map must be an
- integer type. The vertex descriptor type of the graph needs to be
- usable as the key type of the map.<br>
- <b>Default:</b> <tt>get(vertex_index, g)</tt><br>
-
- <b>Python</b>: Unsupported parameter.
+<blockquote>它将每个顶点映射至位于区间 <tt>[0,
+ num_vertices(g))</tt> 中的一个整数。仅当使用了缺省的颜色属性映射时需要该
参数。类型 <tt>VertexIndexMap</tt>
+ 必须符合 <a
href="http://alai04.kmip.net/boost_doc/libs/property_map/ReadablePropertyMap.html";>可
读属性映射</a>。该映射的值类型必须是一个整数类型。图的顶点描述符类型需要可以
被用作该映射的键类型。<br>
+
+
+ <b>缺省值：</b><tt>get(vertex_index, g)</tt>. <br>
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
UTIL/OUT: <tt>discover_time_map(DiscoverTimeMap discover_time)</tt>
-<blockquote>
- The discovery time of each vertex in the depth-first search. The
- type <tt>DiscoverTimeMap</tt> must be a model of <a
- href="../../property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a>. The value type of the map must be an integer
- type. The vertex descriptor type of the graph needs to be usable as
- the key type of the map.<br>
-<b>Default</b>: an <a
- href="../../property_map/iterator_property_map.html">
- </tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of <tt>vertices_size_type</tt> of size
- <tt>num_vertices(g)</tt> and using <tt>get(vertex_index, g)</tt> for
- the index map.<br>
-
- <b>Python</b>: Unsupported parameter.
+<blockquote>各顶点在深度优先搜索中被发现的时间。类型
<tt>DiscoverTimeMap</tt> 必须符合 <a
href="../../property_map/ReadWritePropertyMap.html"> 读/写属性映射</a>。该映
射的值类型必须为整数类型。图的顶点描述符类型必须可作为该映射的键类型。<br>
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a>，创建自一个大小为
<tt>num_vertices(g)</tt> 的 <tt>vertices_size_type</tt> <tt>的
std::vector</tt>，且以 <tt>get(vertex_index, g)</tt><tt></tt> 作为索引
映射。<br>
+
+
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
UTIL/OUT: <tt>lowpoint_map(LowPointMap lowpt)</tt>
-<blockquote>
- The low point of each vertex in the depth-first search, which is the
- smallest vertex reachable from a given vertex with at most one back
- edge. The type <tt>LowPointMap</tt> must be a model of <a
- href="../../property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a>. The value type of the map must be an integer
- type. The vertex descriptor type of the graph needs to be usable as
- the key type of the map.<br>
-<b>Default</b>: an <a
- href="../../property_map/iterator_property_map.html">
- </tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of <tt>vertices_size_type</tt> of size
- <tt>num_vertices(g)</tt> and using <tt>get(vertex_index, g)</tt> for
- the index map.<br>
-
- <b>Python</b>: Unsupported parameter.
+<blockquote>各顶点在深度优先搜索中的低点，即从给定顶点通过至多一条反向边可
到达的最小顶点。类型 <tt>LowPointMap</tt> 必须符合 <a
href="../../property_map/ReadWritePropertyMap.html">读/写属性映射</a>。该映
射的值类型必须是整数类型。图的顶点描述符必须可用作该映射的键类型。<br>
+<b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ iterator_property_map</a>，创建自一个大小为 <tt>num_vertices(g)</tt> 的
<tt>vertices_size_type</tt> <tt>的 std::vector</tt>，且以
<tt>get(vertex_index, g)</tt> 作为索引映射。<br>
+
+
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
UTIL/OUT: <tt>predecessor_map(PredecessorMap p_map)</tt>
-<blockquote>
- The predecessor map records the depth first search tree.
- The <tt>PredecessorMap</tt> type
- must be a <a
- href="../../property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a> whose key and value types are the same as the vertex
- descriptor type of the graph.<br>
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- </tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of <tt>vertex_descriptor</tt> of size
- <tt>num_vertices(g)</tt> and using <tt>get(vertex_index, g)</tt> for
- the index map.<br>
-
- <b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br>
+<blockquote>该前趋映射记录了深度优先搜索树。类型 <tt>PredecessorMap</tt> 必
须是一个 <a href="../../property_map/ReadWritePropertyMap.html">读/写属性映
射</a>，其键类型与值类型均与图的顶点描述符类型相同。<br>
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ iterator_property_map</a>，创建自一个大小为 <tt>num_vertices(g)</tt> 的
<tt>vertices_</tt><tt>descriptor</tt> <tt>的 std::vector</tt>，且以
<tt>get(vertex_index, g)</tt> 作为索引映射。<br>
+
+
+
+ <b>Python</b>: 必须是图的一个 <tt>vertex_vertex_map</tt>。<br>
</blockquote>
IN: <tt>visitor(DFSVisitor vis)</tt>
<blockquote>
- A visitor object that is invoked inside the algorithm at the
- event-points specified by the <a href="./DFSVisitor.html">DFS
- Visitor</a> concept. The visitor object is passed by value <a
- href="#1">[1]</a>. <br> <b>Default:</b>
- <tt>dfs_visitor<null_visitor></tt><br>
-
- <b>Python</b>: The parameter should be an object that derives from
- the <a href="DFSVisitor.html#python"><tt>DFSVisitor</tt></a> type of
- the graph.
+ 一个遍历器对象，在算法内部的某些事件点被调用，这些事件点由 <a
href="./DFSVisitor.html">DFS
+ 遍历器</a> 概念给出。该遍历器对象是以值方式传递的<a href="#1">[1]</a>。
<br> <b>缺省值：</b><tt>dfs_visitor<null_visitor></tt><br>
+
+ <b>Python</b>: 该参数应为派生自该图的 <a
href="DFSVisitor.html#python"><tt>DFSVisitor</tt></a> 类型的一个对象。
</blockquote>
-<H3>Complexity</H3>
-
-<P>
-The time complexity for the biconnected components and articulation
-points algorithms
+<h3>Complexity 复杂度</h3>
+
+<p>双连通分支和挂接点算法的时间复杂度为
<i>O(V + E)</i>.
-<P>
-
-<H3>Example</H3>
-
-<P> The file <a
-href="../example/biconnected_components.cpp"><tt>examples/biconnected_components.cpp</tt></a>
-contains an example of calculating the biconnected components and
-articulation points of an undirected graph.
+</p><p>
+
+</p><h3>Example 示例</h3>
+
+<p>文件 <a
href="../example/biconnected_components.cpp"><tt>examples/biconnected_components.cpp</tt></a>
+包含了计算一个无向图的双连通分支和挂接点的例子。
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2004</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana
-University (<A
-HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
+</p><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright © 2000-2004</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,
Indiana
+University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)<br>
<a href="http://www.boost.org/people/doug_gregor.html";>Doug Gregor</a>,
Indiana University
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+</td></tr></tbody></table>
+
+</body></html>
=======================================
--- /trunk/libs/graph/doc/connected_components.html Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/connected_components.html Fri Aug 7 19:42:01 2009
@@ -1,157 +1,106 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek 2000-2001
--
-- 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: Connected Components</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>
-<A NAME="sec:connected-components">
-<img src="figs/python.gif" alt="(Python)"/>
-<TT>connected_components</TT></A>
-</H1>
-
-<PRE>
-<i>// named parameter version</i>
+<title>Boost Graph Library: Connected Components</title></head>
+
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+
+<br clear="">
+
+
+<h1>
+<a name="sec:connected-components">
+<img src="figs/python.gif" alt="(Python)">
+<tt>connected_components</tt></a>
+</h1>
+
+<pre><i>// 命名参数版本</i>
template <class VertexListGraph, class ComponentMap, class P, class T,
class R>
typename property_traits<ComponentMap>::value_type
connected_components(VertexListGraph& G, ComponentMap comp,
- const bgl_named_params<P, T, R>& params = <i>all
defaults</i>);
-
-<i>// there is not a non-named parameter version of this function</i>
-</PRE>
-
-<P>
-The <TT>connected_components()</TT> functions compute the connected
-components of an undirected graph using a DFS-based approach. A
-<b><I>connected component</I></b> of an undirected graph is a set of
-vertices that are all reachable from each other. If the connected
-components need to be maintained while a graph is growing the
-disjoint-set based approach of function <a
-href="./incremental_components.html">
-<TT>incremental_components()</TT></a> is faster. For ``static'' graphs
-this DFS-based approach is faster [<A
-HREF="bibliography.html#clr90">8</A>].
-
-<P>
-The output of the algorithm is recorded in the component property map
-<TT>comp</TT>, which will contain numbers giving the component number
-assigned to each vertex. The total number of components is the return
-value of the function.
-
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/connected_components.hpp"><TT>boost/graph/connected_components.hpp</TT></a>
-
-
-<h3>Parameters</h3>
+ const bgl_named_params<P, T, R>& params = <i>all
defaults</i>);<br><br><i>// 该函数没有非命名参数版本</i>
+</pre>
+
+<p>函数 <tt>connected_components()</tt> 使用基于DFS的方法计算一个无向图的连
通分支。无向图的<b><i>连通分支</i></b>是指一组顶点，它们相互之间均可到达。如
果要在一个图的增长过程中维护各个连通分支，则基于不相交集合方法的函数 <a
href="./incremental_components.html">
+<tt>incremental_components()</tt></a> 速度较快。对于"静态"图来说，则基于
DFS的方法更快[<a href="bibliography.html#clr90">8</a>]。
+
+</p><p>该算法的输出被记录在连通分支映射
+<tt>comp</tt> 中，其中将包含赋给各个顶点的分支号。总的分支数为函数的返回
值。
+
+</p><h3>Where Defined 定义于</h3>
+
+<p>
+<a
href="../../../boost/graph/connected_components.hpp"><tt>boost/graph/connected_components.hpp</tt></a>
+
+
+</p><h3>Parameters 参数</h3>
IN: <tt>const Graph& g</tt>
-<blockquote>
-An undirected graph. The graph type must be a model of <a
-href="VertexListGraph.html">Vertex List Graph</a> and <a
-href="IncidenceGraph.html">Incidence Graph</a>.<br>
-
-<b>Python</b>: The parameter is named <tt>graph</tt>.
+<blockquote>一个无向图。图的类型必须符合 <a href="VertexListGraph.html">点
列表图Vertex List Graph</a> 和 <a href="IncidenceGraph.html">关联图
Incidence Graph</a>。<br>
+
+<b>Python</b>: 该参数名为 <tt>graph</tt>.
</blockquote>
OUT: <tt>ComponentMap c</tt>
-<blockquote>
-The algorithm computes how many connected components are in the graph,
-and assigning each component an integer label. The algorithm then
-records which component each vertex in the graph belongs to by
-recording the component number in the component property map. The
-<tt>ComponentMap</tt> type must be a model of <a
-href="../../property_map/WritablePropertyMap.html">Writable Property
-Map</a>. The value type shouch be an integer type, preferably the same
-as the <tt>vertices_size_type</tt> of the graph. The key type must be
-the graph's vertex descriptor type.<br>
-
- <b>Python</b>: Must be an <tt>vertex_int_map</tt> for the graph.<br>
- <b>Python default</b>: <tt>graph.get_vertex_int_map("component")</tt>
+<blockquote>本算法计算图中有多少连通分支，并赋给每个分支一个整数标签。然后
本算法通过将分支号写入分支属性映射，来记录图中各顶点属于哪个分支。类型
+<tt>ComponentMap</tt> 必须符合 <a
href="../../property_map/WritablePropertyMap.html">可写属性映射</a>。其值类
型应为整数类型，最好与图的 <tt>vertices_size_type</tt> 相同。而键类型必须是
图的顶点描述符类型。<br>
+
+ <b>Python</b>: 必须是该图的一个 <tt>vertex_int_map</tt>。<br>
+ <b>Python 缺省值：</b><tt>graph.get_vertex_int_map("component")</tt>
</blockquote>
-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>
UTIL: <tt>color_map(ColorMap color)</tt>
-<blockquote>
- This is used by the algorithm to keep track of its progress through
- the graph. The type <tt>ColorMap</tt> must be a model of <a
- href="../../property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a> and its key type must be the graph's vertex
- descriptor type and the value type of the color map must model
- <a href="./ColorValue.html">ColorValue</a>.<br>
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- </tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of <tt>default_color_type</tt> of size
- <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
- map.<br>
- <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for
- the graph.
+<blockquote>本算法用它来跟踪对图的处理过程。类型 <tt>ColorMap</tt> 必须符
合 <a href="../../property_map/ReadWritePropertyMap.html">读/写属性映射</a>
且其键类型必须是图的顶点描述符类型，值类型必须符合
+ <a href="./ColorValue.html">颜色值ColorValue</a>。<br>
+
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a>，创建自一个大小为
<tt>num_vertices(g)</tt> 的 <tt>default_color_type</tt> 的
<tt>std::vector</tt>，且以 <tt>i_map</tt> 作为索引映射。<br>
+
+ <b>Python</b>: 颜色映射必须是该图的一个 <tt>vertex_color_map</tt>。
</blockquote>
IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
-<blockquote>
- This maps each vertex to an integer in the range <tt>[0,
- num_vertices(g))</tt>. This parameter is only necessary when the
- default color property map is used. The type <tt>VertexIndexMap</tt>
- must be a model of <a
- href="../../property_map/ReadablePropertyMap.html">Readable Property
- Map</a>. The value type of the map must be an integer type. The
- vertex descriptor type of the graph needs to be usable as the key
- type of the map.<br>
-
- <b>Default:</b> <tt>get(vertex_index, g)</tt>.
- Note: if you use this default, make sure your graph has
- an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
- not have an internal <tt>vertex_index</tt> property.<br>
-
- <b>Python</b>: Unsupported parameter.
+<blockquote>它将每个顶点映射至位于区间 <tt>[0,
+ num_vertices(g))</tt> 中的一个整数。仅当使用了缺省的颜色属性映射时需要该
参数。类型 <tt>VertexIndexMap</tt>
+ 必须符合 <a
href="http://alai04.kmip.net/boost_doc/libs/property_map/ReadablePropertyMap.html";>可
读属性映射</a>。该映射的值类型必须是一个整数类型。图的顶点描述符类型需要可以
被用作该映射的键类型。<br>
+
+
+ <b>缺省值：</b><tt>get(vertex_index, g)</tt>.
+ 注意：如果你使用该缺省值，请确认你的图具有一个内部的
<tt>vertex_index</tt> 属性。例如，带 <tt>VertexList=listS</tt> 的
+ <tt>adjacenty_list</tt> 并不具有内部的 <tt>vertex_index</tt> 属性。<br>
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
-<H3>Complexity</H3>
-
-<P>
-The time complexity for the connected components algorithm is also
+<h3>Complexity 复杂度</h3>
+
+<p>连通分支算法的时间复杂度也是
<i>O(V + E)</i>.
-<P>
-
-<h3>See Also</h3>
-
-<a href="./strong_components.html"><tt>strong_components()</tt></a>
-and <a
href="./incremental_components.html"><tt>incremental_components()</tt></a>
-
-<H3>Example</H3>
-
-<P>
-The file <a
-href="../example/connected_components.cpp"><tt>examples/connected_components.cpp</tt></a>
-contains an example of calculating the connected components of an
-undirected graph.
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+</p><p>
+
+</p><h3>See Also 参见</h3>
+
+<a href="./strong_components.html"><tt>strong_components()</tt></a> 和 <a
href="./incremental_components.html"><tt>incremental_components()</tt></a>
+
+<h3>Example 示例</h3>
+
+<p>文件 <a
href="../example/connected_components.cpp"><tt>examples/connected_components.cpp</tt></a>
+包含了计算一个无向图的通过分支的例子。<br>
+</p><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright © 2000-2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,
Indiana University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
+
+</body></html>
=======================================
--- /trunk/libs/graph/doc/edmonds_karp_max_flow.html Mon Mar 30 07:58:04
2009
+++ /trunk/libs/graph/doc/edmonds_karp_max_flow.html Fri Aug 7 19:42:01
2009
@@ -1,234 +1,131 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
Copyright (c) Jeremy Siek 2000
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: Edmonds-Karp Maximum Flow</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><A NAME="sec:edmonds_karp_max_flow">
-<TT>edmonds_karp_max_flow</TT>
-</H1>
-
-<PRE>
-<i>// named paramter version</i>
-template <class <a href="./Graph.html">Graph</a>, class P, class T,
class R>
-typename detail::edge_capacity_value<Graph, P, T, R>::value_type
-edmonds_karp_max_flow(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink,
- const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
-
-<i>// non-named parameter version</i>
-template <class <a href="./Graph.html">Graph</a>,
- class CapacityEdgeMap, class ResidualCapacityEdgeMap,
- class ReverseEdgeMap, class ColorMap, class PredEdgeMap>
-typename property_traits<CapacityEdgeMap>::value_type
-edmonds_karp_max_flow(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink,
- CapacityEdgeMap cap, ResidualCapacityEdgeMap res, ReverseEdgeMap rev,
- ColorMap color, PredEdgeMap pred)
-</PRE>
-
-<P>
-The <tt>edmonds_karp_max_flow()</tt> function calculates the maximum flow
-of a network. See Section <a
-href="./graph_theory_review.html#sec:network-flow-algorithms">Network
-Flow Algorithms</a> for a description of maximum flow. The calculated
-maximum flow will be the return value of the function. The function
-also calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in
-<i>E</i>, which are returned in the form of the residual capacity
-<i>r(u,v) = c(u,v) - f(u,v)</i>.
+<title>Boost Graph Library: Edmonds-Karp Maximum Flow</title></head>
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+
+<br clear="">
+
+<h1><a name="sec:edmonds_karp_max_flow">
+<tt>edmonds_karp_max_flow</tt>
+</a></h1>
+
+<pre><a name="sec:edmonds_karp_max_flow"><i>// 命名参数版本</i>
+template <class </a><a href="./Graph.html">Graph</a>, class P, class T,
class R><br>typename detail::edge_capacity_value<Graph, P, T,
R>::value_type<br>edmonds_karp_max_flow(Graph& g, <br> typename
graph_traits<Graph>::vertex_descriptor src,<br> typename
graph_traits<Graph>::vertex_descriptor sink,<br> const
bgl_named_params<P, T, R>& params = <i>all
defaults</i>)<br><br><i>// 非命名参数版本</i>
+template <class <a href="./Graph.html">Graph</a>, <br> class
CapacityEdgeMap, class ResidualCapacityEdgeMap,<br> class ReverseEdgeMap,
class ColorMap, class PredEdgeMap><br>typename
property_traits<CapacityEdgeMap>::value_type<br>edmonds_karp_max_flow(Graph&
g, <br> typename graph_traits<Graph>::vertex_descriptor src,<br>
typename graph_traits<Graph>::vertex_descriptor sink,<br>
CapacityEdgeMap cap, ResidualCapacityEdgeMap res, ReverseEdgeMap rev,
<br> ColorMap color, PredEdgeMap pred)<br></pre>
<p>
-There are several special requirements on the input graph and property
-map parameters for this algorithm. First, the directed graph
-<i>G=(V,E)</i> that represents the network must be augmented to
-include the reverse edge for every edge in <i>E</i>. That is, the
-input graph should be <i>G<sub>in</sub> = (V,{E U
-E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
-must map each edge in the original graph to its reverse edge, that is
-<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>. The
-<tt>CapacityEdgeMap</tt> argument <tt>cap</tt> must map each edge in
-<i>E</i> to a positive number, and each edge in <i>E<sup>T</sup></i>
-to 0.
-
-<p>
-The algorithm is due to <a
-href="./bibliography.html#edmonds72:_improvements_netflow">Edmonds and
-Karp</a>, though we are using the variation called the ``labeling
-algorithm'' described in <a
-href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>.
-
-<p>
-This algorithm provides a very simple and easy to implement solution to
-the maximum flow problem. However, there are several reasons why this
-algorithm is not as good as the <a
-href="./push_relabel_max_flow.html"><tt>push_relabel_max_flow()</tt></a>
-or the <a
-href="./kolmogorov_max_flow.html"><tt>kolmogorov_max_flow()</tt></a>
-algorithm.
-
-<ul>
- <li>In the non-integer capacity case, the time complexity is <i>O(V
- E<sup>2</sup>)</i> which is worse than the time complexity of the
- push-relabel algorithm <i>O(V<sup>2</sup>E<sup>1/2</sup>)</i>
- for all but the sparsest of graphs.</li>
-
- <li>In the integer capacity case, if the capacity bound <i>U</i> is
- very large then the algorithm will take a long time.</li>
+函数 <tt>edmonds_karp_max_flow()</tt> 计算一个网络的最大流。关于最大流的描
述，请见 <a href="./graph_theory_review.html#sec:network-flow-algorithms">网
络流算法</a> 一节。该函数的返回值即为计算所得的最大流。该函数还针对
+<i>E</i> 中所有 <i>(u,v)</i> 计算了流值 <i>f(u,v)</i>，它以残留容量
+<i>r(u,v) = c(u,v) - f(u,v)</i> 的形式来返回。
+
+</p><p>本算法的输入图及属性映射参数有几个特别的要求。首先，表示本网络的有向
图
+<i>G=(V,E)</i> 必须被扩展，对于 <i>E</i> 中的每条边，增加相应的反向边。
即，输入图应为 <i>G<sub>in</sub> = (V,{E U
+E<sup>T</sup>})</i>。<tt>ReverseEdgeMap</tt> 参数 <tt>rev</tt>
+必须将原图中的每条边映射至它的反向边，即对于 <i>E</i> 中的所有
<i>(u,v)</i>，<i>(u,v) -> (v,u)</i>。<tt>CapacityEdgeMap</tt> 参数
<tt>cap</tt> 必须将
+<i>E</i> 中的每条边映射至一个正数，而 <i>E<sup>T</sup></i>
+中的每条边则映射至 0。
+
+</p><p>该算法归功于 <a
href="./bibliography.html#edmonds72:_improvements_netflow">Edmonds 和
+Karp</a>，虽然我们在 <a href="bibliography.html#ahuja93:_network_flows">网
络流</a> 中会用另一个名称 "标签函数"。
+
+</p><p>该算法为最大流问题的解答提供了一个非常简单和容易的实现。但是，有几个
原因令到本算法不如 <a
href="./push_relabel_max_flow.html"><tt>push_relabel_max_flow()</tt></a> 或
<a href="./kolmogorov_max_flow.html"><tt>kolmogorov_max_flow()</tt></a> 算法
好。
+
+</p><ul>
+ <li>在非整数容量的情形下，时间复杂度为 <i>O(V
+ E<sup>2</sup>)</i>，对于除最为稀疏的图以外的所有图，都劣于
+ push-relabel 算法的时间复杂度 <i>O(V<sup>2</sup>E<sup>1/2</sup>)</i>。
</li>
+
+ <li>在整数容量的情形下，如果由 <i>U</i> 所界定的容量非常大，则该算法将花
费很长时间。</li>
</ul>
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/edmonds_karp_max_flow.hpp"><TT>boost/graph/edmonds_karp_max_flow.hpp</TT></a>
-
-<P>
-
-<h3>Parameters</h3>
+<h3>Where Defined 定义于</h3>
+
+<p>
+<a
href="../../../boost/graph/edmonds_karp_max_flow.hpp"><tt>boost/graph/edmonds_karp_max_flow.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Parameters 参数</h3>
IN: <tt>Graph& g</tt>
-<blockquote>
- A directed graph. The
- graph's type must be a model of <a
- href="./VertexListGraph.html">VertexListGraph</a> and <a
href="./IncidenceGraph.html">IncidenceGraph</a> For each edge
- <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
- be in the graph.
+<blockquote>一个有向图。图的类型必须符合 <a
href="./VertexListGraph.html">点列表图VertexListGraph</a> 和 <a
href="./IncidenceGraph.html">关联图IncidenceGraph</a>。对于图中的每条边
<i>(u,v)</i>，反向边 <i>(v,u)</i> 必须也在图中。
</blockquote>
IN: <tt>vertex_descriptor src</tt>
-<blockquote>
- The source vertex for the flow network graph.
+<blockquote>流网络图的源顶点。
</blockquote>
IN: <tt>vertex_descriptor sink</tt>
-<blockquote>
- The sink vertex for the flow network graph.
+<blockquote>流网络图的汇顶点。
</blockquote>
-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>
IN: <tt>capacity_map(CapacityEdgeMap cap)</tt>
-<blockquote>
- The edge capacity property map. The type must be a model of a
- constant <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property
Map</a>. The
- key type of the map must be the graph's edge descriptor type.<br>
- <b>Default:</b> <tt>get(edge_capacity, g)</tt>
+<blockquote>边容量属性映射。该类型必须是一个常性的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。该映射的
键类型必须是该图的边描述符类型。<br>
+ <b>缺省值：</b><tt>get(edge_capacity, g)</tt>
</blockquote>
OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
-<blockquote>
- This maps edges to their residual capacity. The type must be a model
- of a mutable <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property
- Map</a>. The key type of the map must be the graph's edge descriptor
- type.<br>
- <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt>
+<blockquote>将边映射至它的残留容量。该类型必须是一个可变的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。该映射的
键类型必须是该图的边描述符类型。<br>
+ <b>缺省值：</b><tt>get(edge_residual_capacity, g)</tt>
</blockquote>
IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
-<blockquote>
- An edge property map that maps every edge <i>(u,v)</i> in the graph
- to the reverse edge <i>(v,u)</i>. The map must be a model of
- constant <a href="../../property_map/LvaluePropertyMap.html">Lvalue
- Property Map</a>. The key type of the map must be the graph's edge
- descriptor type.<br>
- <b>Default:</b> <tt>get(edge_reverse, g)</tt>
+<blockquote>一个边属性映射，将图中每条边 <i>(u,v)</i> 映射至反向边
<i>(v,u)</i>。该映射必须是一个常性的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。该映射的
键类型必须是图的边描述符类型。<br>
+ <b>缺省值：</b><tt>get(edge_reverse, g)</tt>
</blockquote>
UTIL: <tt>color_map(ColorMap color)</tt>
-<blockquote>
- Used by the algorithm to keep track of progress during the
- breadth-first search stage. At the end of the algorithm, the white
- vertices define the minimum cut set. The map must be a model of
- mutable <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property Map</a>.
- The key type of the map should be the graph's vertex descriptor type, and
- the value type must be a model of <a
- href="./ColorValue.html">ColorValue</a>.<br>
-
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
- of <tt>default_color_type</tt> of size <tt>num_vertices(g)</tt> and
- using the <tt>i_map</tt> for the index map.
+<blockquote>被算法用于在广度优先搜索阶段跟踪处理过程。在算法结束时，白色顶
点定义了最小割集。该映射必须是一个可变的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。该映射的
键类型应为图的顶点描述符类型，且值类型必须符合 <a
href="./ColorValue.html">颜色值ColorValue</a>。<br>
+
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a>，创建自一个大小为
<tt>num_vertices(g)</tt> 的 <tt>default_color_type</tt> 的
<tt>std::vector</tt><tt></tt>，且以 <tt>i_map</tt> 作为索引映射。
</blockquote>
UTIL: <tt>predecessor_map(PredEdgeMap pred)</tt>
-<blockquote>
- Use by the algorithm to store augmenting paths. The map must be a
- model of mutable <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property Map</a>.
- The key type must be the graph's vertex descriptor type and the
- value type must be the graph's edge descriptor type.<br>
-
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
- of edge descriptors of size <tt>num_vertices(g)</tt> and
- using the <tt>i_map</tt> for the index map.
+<blockquote>被算法用于保存增广路径。该映射必须是一个可变的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。该映射的
键类型必须为图的顶点描述符类型，且值类型必须为图的边描述符类型。<br>
+
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a>，创建自一个大小为
<tt>num_vertices(g)</tt> 的边描述符 <tt>std::vector</tt>，且以
<tt>i_map</tt> 作为索引映射。
</blockquote>
IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
-<blockquote>
- Maps each vertex of the graph to a unique integer in the range
- <tt>[0, num_vertices(g))</tt>. This property map is only needed
- if the default for the color or predecessor map is used.
- The vertex index map must be a model of <a
- href="../../property_map/ReadablePropertyMap.html">Readable Property
- Map</a>. The key type of the map must be the graph's vertex
- descriptor type.<br>
- <b>Default:</b> <tt>get(vertex_index, g)</tt>
- Note: if you use this default, make sure your graph has
- an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
- not have an internal <tt>vertex_index</tt> property.
+<blockquote>将图中每个顶点映射至 <tt>[0, num_vertices(g))</tt> 区间中的一个
整数。该属性映射仅当颜色映射或前趋映射使用缺省值时需要。该顶点索引映射必须符
合 <a href="../../property_map/ReadablePropertyMap.html">可读属性映射</a>。
该映射的键类型必须是图的顶点描述符类型。<br>
+ <b>缺省值：</b><tt>get(vertex_index, g)</tt>
+ 注意：如果你使用该缺省值，请确认你的图具有一个内部的
<tt>vertex_index</tt> 属性。例如，带 <tt>VertexList=listS</tt> 的
+ <tt>adjacenty_list</tt> 并不具有内部的 <tt>vertex_index</tt> 属性。
</blockquote>
-<h3>Complexity</h3>
-
-The time complexity is <i>O(V E<sup>2</sup>)</i> in the general case
-or <i>O(V E U)</i> if capacity values are integers bounded by
-some constant <i>U</i>.
-
-<h3>Example</h3>
-
-The program in <a
-href="../example/edmonds-karp-eg.cpp"><tt>example/edmonds-karp-eg.cpp</tt></a>
-reads an example maximum flow problem (a graph with edge capacities)
-from a file in the DIMACS format and computes the maximum flow.
-
-
-<h3>See Also</h3>
+<h3>Complexity 复杂度</h3>在通常的情况下，时间复杂度为 <i>O(V
E<sup>2</sup>)</i>，如果容量值为由某个常数 <i>U</i> 所界定的整数，则为
<i>O(V E U)</i>。
+
+<h3>Example 示例</h3><a
href="../example/edmonds-karp-eg.cpp"><tt>example/edmonds-karp-eg.cpp</tt></a>
+中的例子从一个DIMACS格式的文件中读入一个最大流问题(一个带有边容量的图)，并
计算最大流。
+
+
+<h3>See Also 参见</h3>
<a
href="./push_relabel_max_flow.html"><tt>push_relabel_max_flow()</tt></a><br>
<a href="./kolmogorov_max_flow.html"><tt>kolmogorov_max_flow()</tt></a>.
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/users/people/jeremy_siek.htm";>Jeremy
Siek</A>, Indiana University (<A
HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+<hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright © 2000-2001</td><td>
+<a href="http://www.boost.org/users/people/jeremy_siek.htm";>Jeremy
Siek</a>, Indiana University (<a
href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
+
<!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG
SRC
-->
<!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD
PRE lt
@@ -245,3 +142,4 @@
-->
<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu
p -->
+</body></html>
=======================================
--- /trunk/libs/graph/doc/incremental_components.html Mon Jun 1 21:27:33
2009
+++ /trunk/libs/graph/doc/incremental_components.html Fri Aug 7 19:42:01
2009
@@ -1,421 +1,282 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
--
-- 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: Incremental Connected Components</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>Incremental Connected Components</H1>
-
-<P>
-This section describes a family of functions and classes that work
-together to calculate the connected components of an undirected graph.
-The algorithm used here is based on the disjoint-sets (fast
-union-find) data structure [<A
-HREF="bibliography.html#clr90">8</A>,<A
-HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>]
-which is a good method to use for situations where the graph is
-growing (edges are being added) and the connected components
-information needs to be updated repeatedly. This method does not cover
-the situation where edges are both added and removed from the graph,
-hence it is called <b><i>incremental</i></b><a
-href="bibliography.html#eppstein97:dynamic_graph">[42]</a> (and not
-fully dynamic). The disjoint-sets class is described in Section <A
-HREF="../../disjoint_sets/disjoint_sets.html">Disjoint Sets</A>.
-
-<P>
-The following five operations are the primary functions that you will
-use to calculate and maintain the connected components. The objects
-used here are a graph <TT>g</TT>, a disjoint-sets structure <TT>ds</TT>,
-and vertices <TT>u</TT> and <TT>v</TT>.
-
-<P>
-
-<UL>
-<LI><TT>initialize_incremental_components(g, ds)</TT>
-<BR>
-Basic initialization of the disjoint-sets structure. Each
- vertex in the graph <TT>g</TT> is in its own set.
-</LI>
-<LI><TT>incremental_components(g, ds)</TT>
-<BR>
-The connected components are calculated based on the edges in the graph
- <TT>g</TT> and the information is embedded in <TT>ds</TT>.
-</LI>
-<LI><TT>ds.find_set(v)</TT>
-<BR>
-Extracts the component information for vertex <TT>v</TT> from the
- disjoint-sets.
-</LI>
-<LI><TT>ds.union_set(u, v)</TT>
-<BR>
-Update the disjoint-sets structure when edge <i>(u,v)</i> is added to the
graph.
-</LI>
-</UL>
-
-<P>
-
-<H3>Complexity</H3>
-
-<P>
-The time complexity for the whole process is <i>O(V + E
-alpha(E,V))</i> where <i>E</i> is the total number of edges in the
-graph (by the end of the process) and <i>V</i> is the number of
-vertices. <i>alpha</i> is the inverse of Ackermann's function which
-has explosive recursively exponential growth. Therefore its inverse
-function grows <I>very</I> slowly. For all practical purposes
-<i>alpha(m,n) <= 4</i> which means the time complexity is only
-slightly larger than <i>O(V + E)</i>.
-
-<P>
-
-<H3>Example</H3>
-
-<P>
-Maintain the connected components of a graph while adding edges using
-the disjoint-sets data structure. The full source code for this
-example can be found in <a
-href="../example/incremental_components.cpp"><TT>examples/incremental_components.cpp</TT></a>.
-
-<P>
-<PRE>
-typedef adjacency_list <vecS, vecS, undirectedS> Graph;
-typedef graph_traits<Graph>::vertex_descriptor Vertex;
-typedef graph_traits<Graph>::vertices_size_type size_type;
-
-const int N = 6;
-Graph G(N);
-
-std::vector<size_type> rank(num_vertices(G));
-std::vector<Vertex> parent(num_vertices(G));
-typedef size_type* Rank;
-typedef Vertex* Parent;
-disjoint_sets<Rank, Parent> ds(&rank[0], &parent[0]);
-
-initialize_incremental_components(G, ds);
-incremental_components(G, ds);
-
-graph_traits<Graph>::edge_descriptor e;
-bool flag;
-boost::tie(e,flag) = add_edge(0, 1, G);
-ds.union_set(0,1);
-
-boost::tie(e,flag) = add_edge(1, 4, G);
-ds.union_set(1,4);
-
-boost::tie(e,flag) = add_edge(4, 0, G);
-ds.union_set(4,0);
-
-boost::tie(e,flag) = add_edge(2, 5, G);
-ds.union_set(2,5);
-
-cout << "An undirected graph:" << endl;
-print_graph(G, get(vertex_index, G));
-cout << endl;
-
-graph_traits<Graph>::vertex_iterator i,end;
-for (boost::tie(i, end) = vertices(G); i != end; ++i)
- cout << "representative[" << *i << "] =
" <<
- ds.find_set(*i) << endl;;
-cout << endl;
-
-typedef component_index<unsigned int> Components;
-Components components(&parent[0], &parent[0] + parent.size());
-
-for (Components::size_type c = 0; c < components.size(); ++c) {
- cout << "component " << c << "
contains: ";
- Components::value_type::iterator
- j = components[c].begin(),
- jend = components[c].end();
- for ( ; j != jend; ++j)
- cout << *j << " ";
- cout << endl;
-}
-</PRE>
-
-<P>
-<hr>
+<title>Boost Graph Library: Incremental Connected Components</title></head>
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+
+<br clear="">
+
+<h1>Incremental Connected Components 增量连通分支</h1>
+
+<p>
+本节介绍一组函数和类，它们共同协作完成对一个无向图的连通分支的计算。这里所
用的算法是基于不相交集合(快速合并-查找)数据结构的[<a
href="bibliography.html#clr90">8</a>,<a
href="bibliography.html#tarjan83:_data_struct_network_algo">27</a>]，在图不
断增长(加入新边)以及需要不断更新连通分支信息的情况下，这是一种好方法。不过这
种方法不能用于既有加边也有减边的情况，因此它被称为 <b><i>增量的</i></b><a
href="bibliography.html#eppstein97:dynamic_graph">[42]</a> (不是完全动态的
)。不相交集合类在 <a href="../../disjoint_sets/disjoint_sets.html">不相交集
合</a> 一节中介绍。
+
+</p><p>以下五种操作是用于计算和维护连通分支的基本函数。这里所用的对象有图
<tt>g</tt>, 不相交集合结构 <tt>ds</tt>, 以及顶点 <tt>u</tt> 和 <tt>v</tt>。
+
+</p><ul>
+<li><tt>initialize_incremental_components(g, ds)</tt>
+<br>对不相交集合结构的基本初始化。图 <tt>g</tt> 中的每个顶点对应自身的一个
集合。
+</li>
+<li><tt>incremental_components(g, ds)</tt>
+<br>基于图
+ <tt>g</tt> 中的边以及 <tt>ds</tt> 中的信息计算连通分支。
+</li>
+<li><tt>ds.find_set(v)</tt>
+<br>从不相交集合中获取顶点 <tt>v</tt> 的分支信息。
+</li>
+<li><tt>ds.union_set(u, v)</tt>
+<br>在边 <i>(u,v)</i> 被加入至图中时，更新不相交集合结构。
+</li>
+</ul>
+
+<p>
+
+</p><h3>Complexity 复杂度</h3>
+
+<p>整个过程的时间复杂度为 <i>O(V + E
+alpha(E,V))</i>，其中 <i>E</i> 为图中的总边数(整个过程结束后)，<i>V</i> 为
顶点数。<i>alpha</i> 是逆 Ackermann 函数，Ackermann 函数具有爆炸性的递归指数
增长。因此逆 Ackermann 函数增长非常缓慢。对于所有有实际意义的输
入，<i>alpha(m,n) <= 4</i>，这意味着时间复杂度仅仅轻微大于 <i>O(V +
E)</i>。
+
+</p><p>
+
+</p><h3>Example 示例</h3>
+
+<p>使用不相交集合数据结构，在往一个图中增加边时，维护其连通分支。该例子的完
整源代码可以在 <a
href="../example/incremental_components.cpp"><tt>examples/incremental_components.cpp</tt></a>
中找到。
+
+</p><pre>typedef adjacency_list <vecS, vecS, undirectedS>
Graph;<br>typedef graph_traits<Graph>::vertex_descriptor
Vertex;<br>typedef graph_traits<Graph>::vertices_size_type
size_type;<br><br>const int N = 6;<br>Graph
G(N);<br><br>std::vector<size_type>
rank(num_vertices(G));<br>std::vector<Vertex>
parent(num_vertices(G));<br>typedef size_type* Rank;<br>typedef Vertex*
Parent;<br>disjoint_sets<Rank, Parent> ds(&rank[0],
&parent[0]);<br><br>initialize_incremental_components(G,
ds);<br>incremental_components(G,
ds);<br><br>graph_traits<Graph>::edge_descriptor e;<br>bool
flag;<br>boost::tie(e,flag) = add_edge(0, 1,
G);<br>ds.union_set(0,1);<br><br>boost::tie(e,flag) = add_edge(1, 4,
G);<br>ds.union_set(1,4);<br><br>boost::tie(e,flag) = add_edge(4, 0,
G);<br>ds.union_set(4,0);<br><br>boost::tie(e,flag) = add_edge(2, 5,
G);<br>ds.union_set(2,5);<br><br>cout << "An undirected graph:"
<< endl;<br>print_graph(G, get(vertex_index, G));<br>cout <<
endl;<br><br>graph_traits<Graph>::vertex_iterator i,end;<br>for
(boost::tie(i, end) = vertices(G); i != end; ++i)<br> cout
<< "representative[" << *i << "] = " << <br>
ds.find_set(*i) << endl;;<br>cout << endl;<br><br>typedef
component_index<unsigned int> Components;<br>Components
components(&parent[0], &parent[0] + parent.size());<br><br>for
(Components::size_type c = 0; c < components.size(); ++c) {<br> cout
<< "component " << c << " contains: ";<br>
Components::value_type::iterator<br> j = components[c].begin(),<br>
jend = components[c].end();<br> for ( ; j != jend; ++j)<br> cout
<< *j << " ";<br> cout << endl;<br>}<br></pre>
+
+<p>
+</p><hr>
+<p>
+
+</p><h2><a name="sec:initialize-incremental-components"></a>
+<tt>initialize_incremental_components</tt>
+</h2>
+
+<p>
+</p><div align="left">
+<table border="1" cellpadding="3">
+<tbody><tr><th align="left"><b>图：</b></th>
+<td align="left">无向</td>
+</tr>
+<tr><th align="left"><b>属性：</b></th>
+<td align="left">秩，(在不相交集合中的)父节点</td>
+</tr>
+<tr><th align="left"><b>复杂度：</b></th>
+<td></td>
+</tr>
+</tbody></table>
+</div>
+
+<p>
+</p><pre>template <class VertexListGraph, class DisjointSets>
<br>void initialize_incremental_components(VertexListGraph& G,
DisjointSets& ds)<br></pre>
+
+<p>为增量连通分支算法准备不相交集合数据结构，将图中每个顶点作为其自身分支
(或集合)的成员。
+
+</p><p>
+
+</p><h3>Where Defined 定义于</h3>
+
+<p>
+<a
href="../../../boost/graph/incremental_components.hpp"><tt>boost/graph/incremental_components.hpp</tt></a>
+
+</p><p>
+</p><hr>
+<p>
+
+</p><h2><a name="sec:incremental-components"></a>
+<tt>incremental_components</tt>
+</h2>
+
+<p>
+</p><div align="left">
+<table border="1" cellpadding="3">
+<tbody><tr><th align="left"><b>图：</b></th>
+<td align="left">无向</td>
+</tr>
+<tr><th align="left"><b>属性：</b></th>
+<td align="left">秩，(在不相交集合中的)父节点</td>
+</tr>
+<tr><th align="left"><b>复杂度：</b></th>
+<td align="left"><i>O(E)</i></td>
+</tr>
+</tbody></table>
+</div>
+
<p>
-
-<H2><A NAME="sec:initialize-incremental-components"></A>
-<TT>initialize_incremental_components</TT>
-</H2>
-
-<P>
-<DIV ALIGN="left">
-<TABLE CELLPADDING=3 border>
-<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH>
-<TD ALIGN="LEFT">undirected</TD>
-</TR>
-<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
-<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD>
-</TR>
-<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
-<TD></TD>
-</TR>
-</TABLE>
-</DIV>
-
-<P>
-<PRE>
-template <class VertexListGraph, class DisjointSets>
-void initialize_incremental_components(VertexListGraph& G,
DisjointSets& ds)
-</PRE>
-
-<P>
-This prepares the disjoint-sets data structure for the incremental
-connected components algorithm by making each vertex in the graph a
-member of its own component (or set).
-
-<P>
-
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
+</p><pre>template <class EdgeListGraph, class DisjointSets><br>void
incremental_components(EdgeListGraph& g, DisjointSets& ds)<br></pre>
+
+<p>该函数计算该图的连通分支，将结果嵌入到不相交集合的数据结构中。
+
+</p><p>
+
+</p><h3>Where Defined 定义于</h3>
+
+<p>
+<a
href="../../../boost/graph/incremental_components.hpp"><tt>boost/graph/incremental_components.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Requirements on Types 对类型的要求</h3>
+
+<ul>
+<li>图的类型必须符合 <a href="./EdgeListGraph.html">边列表图
EdgeListGraph</a>。
+</li>
+</ul>
<p>
-<hr>
-<P>
-
-<H2><A NAME="sec:incremental-components"></A>
-<TT>incremental_components</TT>
-</H2>
-
-<P>
-<DIV ALIGN="left">
-<TABLE CELLPADDING=3 border>
-<TR><TH ALIGN="LEFT"><B>Graphs:</B></TH>
-<TD ALIGN="LEFT">undirected</TD>
-</TR>
-<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
-<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD>
-</TR>
-<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
-<TD ALIGN="LEFT"><i>O(E)</i></TD>
-</TR>
-</TABLE>
-</DIV>
+</p><hr>
+<p>
+
+</p><h2><a name="sec:same-component">
+<tt>same_component</tt></a>
+</h2>
+
+<p>
+</p><div align="left">
+<table border="1" cellpadding="3">
+<tbody><tr><th align="left"><b>属性：</b></th>
+<td align="left">秩，(在不相交集合中的)父节点</td>
+</tr>
+<tr><th align="left"><b>复杂度：</b></th>
+<td align="left"><i>O(alpha(E,V))</i></td>
+</tr>
+</tbody></table>
+</div>
<p>
-<PRE>
-template <class EdgeListGraph, class DisjointSets>
-void incremental_components(EdgeListGraph& g, DisjointSets& ds)
-</PRE>
-
-<P>
-This function calculates the connected components of the graph,
-embedding the results in the disjoint-sets data structure.
-
-<P>
-
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
-
-<P>
-
-<H3>Requirements on Types</H3>
-
-<P>
-
-<UL>
-<LI>The graph type must be a model of <a
href="./EdgeListGraph.html">EdgeListGraph</a>.
-</LI>
-</UL>
-
-<P>
-<hr>
+</p><pre>template <class Vertex, class DisjointSet><br>bool
same_component(Vertex u, Vertex v, DisjointSet& ds)<br></pre>
+
+<p>该函数判断 <tt>u</tt> 与 <tt>v</tt> 是否属于同一个分支。
+
+</p><p>
+
+</p><h3>Where Defined 定义于</h3>
+
+<p>
+<a
href="../../../boost/graph/incremental_components.hpp"><tt>boost/graph/incremental_components.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Requirements on Types 对类型的要求</h3>
+
+<ul>
+<li><tt>Vertex</tt> 必须兼容于 <tt>DisjointSets</tt> 数据结构的 rank 和
parent
+ 属性映射。
+</li>
+</ul>
+
+<p>
+</p><hr>
<p>
-<H2><A NAME="sec:same-component">
-<TT>same_component</TT></A>
-</H2>
-
-<P>
-<DIV ALIGN="left">
-<TABLE CELLPADDING=3 border>
-<TR><TH ALIGN="LEFT"><B>Properties:</B></TH>
-<TD ALIGN="LEFT">rank, parent (in disjoint-sets)</TD>
-</TR>
-<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
-<TD ALIGN="LEFT"><i>O(alpha(E,V))</i></TD>
-</TR>
-</TABLE>
-</DIV>
-
-<P>
-<PRE>
-template <class Vertex, class DisjointSet>
-bool same_component(Vertex u, Vertex v, DisjointSet& ds)
-</PRE>
-
-<P>
-This function determines whether <TT>u</TT> and <TT>v</TT> are in the same
-component.
-
-<P>
-
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
-
-<P>
-
-<H3>Requirements on Types</H3>
-
-<P>
-
-<UL>
-<LI><TT>Vertex</TT> must be compatible with the rank and parent
- property maps of the <TT>DisjointSets</TT> data structure.
-</LI>
-</UL>
-
-<P>
-<hr>
+</p><h2><a name="sec:component-index"></a>
+<tt>component_index</tt>
+</h2>
+
<p>
-
-<H2><A NAME="sec:component-index"></A>
-<TT>component_index</TT>
-</H2>
+</p><pre>component_index<Index><br></pre>
+
+<p>该类为图的分支提供一个类似于STL容器的视图。每个分支是一个类似于容器的对
象，<tt>component_index</tt> 对象提供通过 <tt>operator[]</tt> 对分支对
象的访问。<tt>component_index</tt>
+对象是用从 <tt>incremental_components()</tt> 函数计算得到的不相交集合中的父
节点属性进行初始化的。</p><h3>Where Defined 定义于</h3>
<p>
-<PRE>
-component_index<Index>
-</PRE>
-
-<P>
-The is a class that provides an STL container-like view for the
-components of the graph. Each component is a container-like object,
-and the <TT>component_index</TT> object provides access to the
-component objects via <TT>operator[]</TT>. A <TT>component_index</TT>
-object is initialized with the parents property in the disjoint-sets
-calculated from the <TT>incremental_components()</TT> function.
-
-<P>
-
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/incremental_components.hpp"><TT>boost/graph/incremental_components.hpp</TT></a>
-
-<P>
-
-<H3>Members</H3>
-
-<P>
-
-<table border>
-
-<tr>
-<th>Member</th> <th>Description</th>
+<a
href="../../../boost/graph/incremental_components.hpp"><tt>boost/graph/incremental_components.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Members 成员</h3>
+
+<p>
+
+<table border="1">
+
+<tbody><tr>
+<th>成员</th> <th>说明</th>
</tr>
<tr>
<td><tt>size_type</tt></td>
-<td>The type used for representing the number of components.</td>
+<td>用于表示分支数量的类型。</td>
</tr>
<tr>
<td><tt>value_type</tt></td>
-<td>
-The type for a component object. The component type has the following
members.
+<td>分支对象的类型。分支类型具有以下成员。
</td>
</tr>
<tr>
<td><tt>value_type::value_type</tt></td>
-<td>
-The value type of a component object is a vertex ID.
+<td>分支对象的值类型为顶点ID。
</td>
</tr>
<tr>
<td><tt>value_type::iterator</tt></td>
-<td>
-This iterator can be used to traverse all of the vertices
-in the component. This iterator dereferences to give a vertex ID.
+<td>该迭代器可用于遍历该分支中的所有顶点。解引用该迭代器得到一个顶点ID。
</td>
</tr>
<tr>
<td><tt>value_type::const_iterator</tt></td>
-<td>
-The const iterator.
+<td>常量迭代器。
</td>
</tr>
<tr>
<td><tt>value_type::iterator value_type::begin() const</tt></td>
-<td>
-Return an iterator pointing to the first vertex in the component.
+<td>返回一个迭代器，指向该分支中的第一个顶点。
</td>
</tr>
<tr>
<td><tt>value_type::iterator value_type::end() const</tt></td>
-<td>
-Return an iterator pointing past the end of the last vertex in the
-component.
+<td>返回一个迭代器，指向该分支中最后一个顶点之后。
</td>
-<tr>
-
-<tr>
+</tr><tr>
+
+</tr><tr>
<td>
<tt>
template <class ComponentsContainer>
component_index(const ComponentsContainer& c)
</tt>
</td>
-<td>
-Construct the <TT>component_index</TT> using the information
-from the components container <TT>c</TT> which was the result
-of executing <TT>connected_components_on_edgelist</TT>.
+<td>用分支容器 <tt>c</tt> 中的信息构造
<tt>component_index</tt>，<tt>c</tt> 是执行
<tt>connected_components_on_edgelist</tt> 所得到的结果。
</td>
</tr>
<tr>
<td><tt>value_type operator[](size_type i)</tt></td>
<td>
-Returns the <TT>i</TT>th component in the graph.
+返回图中第 <tt>i</tt> 个分支。
</td>
</tr>
<tr>
<td><tt>size_type component_index::size()</tt></td>
-<td>
-Returns the number of components in the graph.
+<td>返回图中的分支数量。
</td>
-</table>
+</tr></tbody></table>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
-Indiana University (<A
-HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
-<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>,
Indiana University (<A
HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
-Indiana University (<A
-HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+</p><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright © 2000-2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,
+Indiana University (<a
href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)<br>
+<a href="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</a>,
Indiana University (<a
href="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</a>)<br>
+<a href="http://www.osl.iu.edu/%7Elums";>Andrew Lumsdaine</a>,
+Indiana University (<a href="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
+
+</body></html>
=======================================
--- /trunk/libs/graph/doc/kolmogorov_max_flow.html Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/kolmogorov_max_flow.html Fri Aug 7 19:42:01 2009
@@ -1,384 +1,198 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
-<HTML>
-<HEAD>
- <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html;
charset=iso-8859-15">
- <TITLE>Boost Graph Library: Kolmogorov Maximum Flow</TITLE>
- <META NAME="GENERATOR" CONTENT="OpenOffice.org 2.0 (Linux)">
- <META NAME="CREATED" CONTENT="20060820;17315200">
- <META NAME="CHANGEDBY" CONTENT="Stephan Diederich">
- <META NAME="CHANGED" CONTENT="20060820;23125100">
-<!--
-// Copyright (c) 2006, Stephan Diederich
-//
-// This documentation may be used under either of the following two
licences:
-//
-// Permission is hereby granted, free of charge, to any person
-// obtaining a copy of this software and associated documentation
-// files (the "Software"), to deal in the Software without
-// restriction, including without limitation the rights to use,
-// copy, modify, merge, publish, distribute, sublicense, and/or
-// sell copies of the Software, and to permit persons to whom the
-// Software is furnished to do so, subject to the following
-// conditions:
-//
-// The above copyright notice and this permission notice shall be
-// included in all copies or substantial portions of the Software.
-//
-// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
-// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
-// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
-// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
-// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
-// OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
-//
-// Or:
-//
-// 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)
- -->
- <STYLE>
- <!--
- TD P { color: #000000 }
- H1 { color: #000000 }
- P { color: #000000 }
- PRE { color: #000000 }
- H3 { color: #000000 }
- BLOCKQUOTE { color: #000000 }
- A:link { color: #0000ee }
- A:visited { color: #551a8b }
- -->
- </STYLE>
-</HEAD>
-<BODY LANG="de-DE" TEXT="#000000" LINK="#0000ee" VLINK="#551a8b"
BGCOLOR="#ffffff" DIR="LTR">
-<P><IMG SRC="../../../boost.png" NAME="Grafik1" ALT="C++ Boost"
ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0>
-</P>
-<H1><A NAME="sec:kolmogorov_max_flow"></A><TT>kolmogorov_max_flow</TT>
-</H1>
-<PRE><I>// named parameter version</I>
-template <class Graph, class P, class T, class R>
-typename property_traits<typename property_map<Graph,
edge_capacity_t>::const_type>::value_type
-kolmogorov_max_flow(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink,
- const bgl_named_params<P, T, R>& params = <I>all defaults</I>)
-
-<I>// non-named parameter version</I>
-template <class Graph, class CapacityEdgeMap, class
ResidualCapacityEdgeMap, class ReverseEdgeMap,
- class PredecessorMap, class ColorMap, class DistanceMap, class
IndexMap>
-typename property_traits<CapacityEdgeMap>::value_type
-kolmogorov_max_flow(Graph& g,
- CapacityEdgeMap cap,
- ResidualCapacityEdgeMap res_cap,
- ReverseEdgeMap rev_map,
- PredecessorMap pre_map,
- ColorMap color,
- DistanceMap dist,
- IndexMap idx,
- typename graph_traits <Graph>::vertex_descriptor src,
- typename graph_traits <Graph >::vertex_descriptor
sink)</PRE><P>
-<FONT SIZE=3>Additional overloaded versions for non-named parameters
-are provided (without DistanceMap/ColorMap/DistanceMap; for those
-iterator_property_maps with the provided index map are used)</FONT></P>
-<P>The <TT>kolmogorov_max_flow()</TT> function calculates the maximum
-flow of a network. See Section <A
HREF="graph_theory_review.html#sec:network-flow-algorithms">Network
-Flow Algorithms</A> for a description of maximum flow. The calculated
-maximum flow will be the return value of the function. The function
-also calculates the flow values <I>f(u,v)</I> for all <I>(u,v)</I> in
-<I>E</I>, which are returned in the form of the residual capacity
-<I>r(u,v) = c(u,v) - f(u,v)</I>.
-</P>
-<P><B>Requirements:</B><BR>The directed graph <I>G=(V,E)</I> that
-represents the network must include a reverse edge for every edge in
-<I>E</I>. That is, the input graph should be <I>G<SUB>in</SUB> =
-(V,{E U E<SUP>T</SUP>})</I>. The <TT>ReverseEdgeMap</TT> argument
<TT>rev</TT>
-must map each edge in the original graph to its reverse edge, that is
-<I>(u,v) -> (v,u)</I> for all <I>(u,v)</I> in <I>E</I>.
-</P>
-<P>Remarks: While the push-relabel method states that each edge in
<I>E<SUP>T</SUP></I>
-has to have capacity of 0, the reverse edges for this algorithm ARE
-allowed to carry capacities. If there are already reverse edges in
-the input Graph <I><FONT FACE="Courier New, monospace">G</FONT></I>,
-those can be used. This can halve the amount of edges and will
-noticeably increase the performance.<BR><BR><B>Algorithm
-description:</B><BR>Kolmogorov's algorithm is a variety of the
-augmenting-path algorithm. Standard augmenting path algorithms find
-shortest paths from source to sink vertex and augment them by
-substracting the bottleneck capacity found on that path from the
-residual capacities of each edge and adding it to the total flow.
-Additionally the minimum capacity is added to the residual capacity
-of the reverse edges. If no more paths in the residual-edge tree are
-found, the algorithm terminates. Instead of finding a new shortest
-path from source to sink in the graph in each iteration, Kolmogorov's
-version keeps the already found paths as follows:</P>
-<P>The algorithm builds up two search trees, a source-tree and a
-sink-tree. Each vertex has a label (stored in <I>ColorMap</I>) to
-which tree it belongs and a status-flag if this vertex is active or
-passive. In the beginning of the algorithm only the source and the
-sink are colored (source==black, sink==white) and have active status.
-All other vertices are colored gray. The algorithm consists of three
-phases:</P>
-<P><I>grow-phase</I>: In this phase active vertices are allowed to
-acquire neighbor vertices that are connected through an edge that has
-a capacity-value greater than zero. Acquiring means that those vertices
-become active and belong now to the search tree of the current
-active vertex. If there are no more valid connections to neighbor
-vertices, the current vertex becomes passive and the grow phase
-continues with the next active vertex. The grow phase terminates if
-there are no more active vertices left or a vertex discovers a vertex
-from the other search tree through an unsaturated edge. In this case
-a path from source to sink is found.</P>
-<P><I>augment-phase</I>: This phase augments the path that was found
-in the grow phase. First it finds the bottleneck capacity of the
-found path, and then it updates the residual-capacity of the edges
-from this path by substracting the bottleneck capacity from the
-residual capacity. Furthermore the residual capacity of the reverse
-edges are updated by adding the bottleneck capacity. This phase can
-destroy the built up search trees, as it creates at least one
-saturated edge. That means, that the search trees collapse to
-forests, because a condition for the search trees is, that each
-vertex in them has a valid (=non-saturated) connection to a terminal.</P>
-<P><I>adoption-phase</I>: Here the search trees are reconstructed. A
-simple solution would be to mark all vertices coming after the first
-orphan in the found path free vertices (gray). A more sophisticated
-solution is to give those orphans new parents: The neighbor vertices
-are checked if they have a valid connection to the same terminal like
-this vertex had (a path with unsaturated edges). If there is one,
-this vertex becomes the new parent of the current orphan and this
-forest is re-included into the search tree. If no new valid parent is
-found, this vertex becomes a free vertex (marked gray), and it's
-children become orphans. The adoption phase terminates if there are
-no more orphans.</P>
-<P><IMG SRC="figs/kolmogorov_max_flow.gif" NAME="Grafik2" ALIGN=LEFT
WIDTH=827 HEIGHT=311 BORDER=0><BR CLEAR=LEFT><B>Details:</B></P>
-<UL>
- <LI><P>Marking heuristics: A timestamp is stored for each vertex
- which shows in which iteration of the algorithm the distance to the
- corresponding terminal was calculated.
- </P>
- <UL>
- <LI><P>This distance is used and gets calculated in the
- adoption-phase. In order to find a valid new parent for an
orphan,
- the possible parent is checked for a connection to the terminal
to
- which tree it belongs. If there is such a connection, the path
is
- tagged with the current time-stamp, and the distance value. If
- another orphan has to find a parent and it comes across a vertex
- with a current timestamp, this information is used.</P>
- <LI><P>The distance is also used in the grow-phase. If a vertex
- comes across another vertex of the same tree while searching for
- new vertices, the other's distance is compared to its distance.
If
- it is smaller, that other vertex becomes the new parent of the
- current. This can decrease the length of the search paths, and
so
- amount of adoptions.</P>
- </UL>
- <LI><P>Ordering of orphans: As described above, the augment-phase
- and the adoption phase can create orphans. The orphans the
- augment-phase generates, are ordered according to their distance to
- the terminals (smallest first). This combined with the
- distance/timestamp heuristics results in the possibility for not
- having to recheck terminal-connections too often. New orphans which
- are generated in adoption phase are processed before orphans from
- the main queue for the same reason.</P>
-</UL>
-<P><BR><B>Implementation notes:</B></P>
-<P>The algorithm is mainly implemented as described in the PhD thesis
-of Kolmogorov. Few changes were made for increasing performance:</P>
-<UL>
- <LI><P>initialization: the algorithm first augments all paths from
- source->sink and all paths from source->VERTEX->sink. This
- improves especially graph-cuts used in image vision where nearly
- each vertex has a source and sink connect. During this step, all
- vertices that have an unsaturated connection from source are added
- to the active vertex list and so the source is not.
- </P>
- <LI><P>active vertices: Kolmogorov uses two lists for active nodes
- and states that new active vertices are added to the rear of the
- second. Fetching an active vertex is done from the beginning of the
- first list. If the first list is empty, it is exchanged by the
- second. This implementation uses just one list.</P>
- <LI><P>grow-phase: In the grow phase the first vertex in the
- active-list is taken and all outgoing edges are checked if they are
- unsaturated. This decreases performance for graphs with high-edge
- density. This implementation stores the last accessed edge and
- continues with it, if the first vertex in the active-list is the
- same one as during the last grow-phase.</P>
-</UL>
-<P>This algorithm [<A HREF="bibliography.html#kolmogorov03">68</a>, <a
href="bibliography.html#boykov-kolmogorov04">69</a>] was developed by
Boykov and Kolmogorov.
-</P>
-<H3>Where Defined</H3>
-<P><TT><A
HREF="../../../boost/graph/kolmogorov_max_flow.hpp">boost/graph/kolmogorov_max_flow.hpp</A></TT>
-</P>
-<H3>Parameters</H3>
-<P>IN: <TT>Graph& g</TT>
-</P>
-<BLOCKQUOTE>A directed graph. The graph's type must be a model of
-<A HREF="VertexListGraph.html">Vertex List Graph</A>, <A
HREF="EdgeListGraph.html">Edge
-List Graph</A> and <A HREF="IncidenceGraph.html">Incidence Graph</A>.
-For each edge <I>(u,v)</I> in the graph, the reverse edge <I>(v,u)</I>
-must also be in the graph.
-</BLOCKQUOTE>
-<P>IN: <TT>vertex_descriptor src</TT>
-</P>
-<BLOCKQUOTE>The source vertex for the flow network graph.
-</BLOCKQUOTE>
-<P>IN: <TT>vertex_descriptor sink</TT>
-</P>
-<BLOCKQUOTE>The sink vertex for the flow network graph.
-</BLOCKQUOTE>
-<H3>Named Parameters</H3>
-<P>IN: <TT>capacity_map(EdgeCapacityMap cap)</TT>
-</P>
-<BLOCKQUOTE>The edge capacity property map. The type must be a model
-of a constant <A HREF="../../property_map/LvaluePropertyMap.html">Lvalue
-Property Map</A>. The key type of the map must be the graph's edge
-descriptor type.<BR><B>Default:</B> <TT>get(edge_capacity, g)</TT>
-</BLOCKQUOTE>
-<P>OUT: <TT>residual_capacity_map(ResidualCapacityEdgeMap res)</TT>
-</P>
-<BLOCKQUOTE>The edge residual capacity property map. The type must be
-a model of a mutable <A
HREF="../../property_map/LvaluePropertyMap.html">Lvalue
-Property Map</A>. The key type of the map must be the graph's edge
-descriptor type.<BR><B>Default:</B> <TT>get(edge_residual_capacity,
-g)</TT>
-</BLOCKQUOTE>
-<P>IN: <TT>reverse_edge_map(ReverseEdgeMap rev)</TT>
-</P>
-<BLOCKQUOTE>An edge property map that maps every edge <I>(u,v)</I> in
-the graph to the reverse edge <I>(v,u)</I>. The map must be a model
-of constant <A HREF="../../property_map/LvaluePropertyMap.html">Lvalue
-Property Map</A>. The key type of the map must be the graph's edge
-descriptor type.<BR><B>Default:</B> <TT>get(edge_reverse, g)</TT>
-</BLOCKQUOTE>
-<P>UTIL: <TT>vertex_predecessor(PredecessorMap pre_map)</TT>
-</P>
-<BLOCKQUOTE>A vertex property map that stores the edge to the vertex'
-predecessor. The map must be a model of mutable <A
HREF="../../property_map/LvaluePropertyMap.html">Lvalue
-Property Map</A>. The key type of the map must be the graph's vertex
-descriptor type.<BR><B>Default:</B> <TT>get(vertex_predecessor, g)</TT>
-</BLOCKQUOTE>
-<P>OUT/UTIL: <TT>vertex_color(ColorMap color)</TT>
-</P>
-<BLOCKQUOTE>A vertex property map that stores a color for edge
-vertex. If the color of a vertex after running the algorithm is black
-the vertex belongs to the source tree else it belongs to the
-sink-tree (used for minimum cuts). The map must be a model of mutable
-<A HREF="../../property_map/LvaluePropertyMap.html">Lvalue Property
-Map</A>. The key type of the map must be the graph's vertex
-descriptor type.<BR><B>Default:</B> <TT>get(vertex_color, g)</TT>
-</BLOCKQUOTE>
-<P>UTIL: <TT>vertex_distance(DistanceMap dist)</TT>
-</P>
-<BLOCKQUOTE>A vertex property map that stores the distance to the
-corresponding terminal. It's a utility-map for speeding up the
-algorithm. The map must be a model of mutable <A
HREF="../../property_map/LvaluePropertyMap.html">Lvalue
-Property Map</A>. The key type of the map must be the graph's vertex
-descriptor type.<BR><B>Default:</B> <TT>get(vertex_distance, g)</TT>
-</BLOCKQUOTE>
-<P>IN: <TT>vertex_index_map(VertexIndexMap index_map)</TT>
-</P>
-<BLOCKQUOTE>Maps each vertex of the graph to a unique integer in the
-range <TT>[0, num_vertices(g))</TT>. The map must be a model of
-constant <A
HREF="../../property_map/LvaluePropertyMap.html">LvaluePropertyMap</A>.
-The key type of the map must be the graph's vertex descriptor
-type.<BR><B>Default:</B> <TT>get(vertex_index, g)</TT>
-</BLOCKQUOTE>
-<H3>Example</H3>
-<P>This reads an example maximum flow problem (a graph with edge
-capacities) from a file in the DIMACS format (<TT><A
HREF="../example/max_flow.dat">example/max_flow.dat</A></TT>).
-The source for this example can be found in
-<TT><A
HREF="../example/kolmogorov-eg.cpp">example/kolmogorov-eg.cpp</A></TT>.
-</P>
-<PRE>#include <boost/config.hpp>
-#include <iostream>
-#include <string>
-#include <boost/graph/kolmogorov_map_flow.hpp>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/read_dimacs.hpp>
-
-int
-main()
-{
- using namespace boost;
-
- typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
- typedef adjacency_list<vecS, vecS, directedS,
- property<vertex_name_t, std::string>,
- property<edge_capacity_t, long,
- property<edge_residual_capacity_t, long,
- property<edge_reverse_t, Traits::edge_descriptor> > >
- > Graph;
-
- Graph g;
- long flow;
-
- property_map<Graph, edge_capacity_t>::type
- capacity = get(edge_capacity, g);
- property_map<Graph, edge_reverse_t>::type
- rev = get(edge_reverse, g);
- property_map<Graph, edge_residual_capacity_t>::type
- residual_capacity = get(edge_residual_capacity, g);
-
- Traits::vertex_descriptor s, t;
- read_dimacs_max_flow(g, capacity, rev, s, t);
-
- flow = kolmogorov_max_flow(g, s, t);
-
- std::cout << "c The total flow:" << std::endl;
- std::cout << "s " << flow << std::endl
<< std::endl;
-
- std::cout << "c flow values:" << std::endl;
- graph_traits<Graph>::vertex_iterator u_iter, u_end;
- graph_traits<Graph>::out_edge_iterator ei, e_end;
- for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
- for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
- if (capacity[*ei] > 0)
- std::cout << "f " << *u_iter << "
" << target(*ei, g) << " "
- << (capacity[*ei] - residual_capacity[*ei])
<< std::endl;
- return 0;
-}</PRE><P>
-The output is:
-</P>
-<PRE>c The total flow:
-s 13
-
-c flow values:
-f 0 6 3
-f 0 1 0
-f 0 2 10
-f 1 5 1
-f 1 0 0
-f 1 3 0
-f 2 4 4
-f 2 3 6
-f 2 0 0
-f 3 7 5
-f 3 2 0
-f 3 1 1
-f 4 5 4
-f 4 6 0
-f 5 4 0
-f 5 7 5
-f 6 7 3
-f 6 4 0
-f 7 6 0
-f 7 5 0</PRE><H3>
-See Also</H3>
-<P STYLE="margin-bottom: 0cm"><TT><A
HREF="edmonds_karp_max_flow.html">edmonds_karp_max_flow()</A></TT>,<BR><TT><A
HREF="push_relabel_max_flow.html">push_relabel_max_flow()</A></TT>.
-</P>
-<HR>
-<TABLE CELLPADDING=2 CELLSPACING=2>
- <TR VALIGN=TOP>
- <TD>
- <P>Copyright © 2006</P>
- </TD>
- <TD>
- <P>Stephan Diederich, University
- Mannheim(<A
HREF="mailto:diederich@xxxxxxxxxxxxxxxxx";>diederich@xxxxxxxxxxxxxxxxx</A>)</P>
- </TD>
- </TR>
-</TABLE>
-<P><BR><BR>
-</P>
-</BODY>
-</HTML>
+<html><head>
+<meta http-equiv="CONTENT-TYPE" content="text/html;
charset=UTF-8"><title>Boost Graph Library: Kolmogorov Maximum Flow</title>
+
+<meta name="GENERATOR" content="OpenOffice.org 2.0 (Linux)">
+<meta name="CREATED" content="20060820;17315200">
+<meta name="CHANGEDBY" content="Stephan Diederich">
+<meta name="CHANGED" content="20060820;23125100">
+<!-- // Copyright (c) 2006, Stephan Diederich // // This documentation may
be used under either of the following two licences: // // Permission is
hereby granted, free of charge, to any person // obtaining a copy of this
software and associated documentation // files (the "Software"), to deal in
the Software without // restriction, including without limitation the
rights to use, // copy, modify, merge, publish, distribute, sublicense,
and/or // sell copies of the Software, and to permit persons to whom the //
Software is furnished to do so, subject to the following // conditions: //
// The above copyright notice and this permission notice shall be //
included in all copies or substantial portions of the Software. // // THE
SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, // EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES // OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND // NONINFRINGEMENT. IN NO EVENT SHALL
THE AUTHORS OR COPYRIGHT // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, // WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR //
OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE. // // Or: // // 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) -->
+<style>
+<!--
+TD P { color: #000000 }
+H1 { color: #000000 }
+P { color: #000000 }
+PRE { color: #000000 }
+H3 { color: #000000 }
+BLOCKQUOTE { color: #000000 }
+A:link { color: #0000ee }
+A:visited { color: #551a8b }
+-->
+</style>
+</head>
+<body style="direction: ltr; color: rgb(0, 0, 0); background-color:
rgb(255, 255, 255);" lang="de-DE" link="#0000ee" vlink="#551a8b">
+<p><img src="../../../boost.png" name="Grafik1" alt="C++ Boost"
align="bottom" border="0" height="86" width="277">
+</p>
+<h1><a name="sec:kolmogorov_max_flow"></a><tt>kolmogorov_max_flow</tt>
+</h1>
+<pre><i>// 命名参数版本</i><br>template <class Graph, class P, class T,
class R><br>typename property_traits<typename property_map<Graph,
edge_capacity_t>::const_type>::value_type<br>kolmogorov_max_flow(Graph&
g, typename graph_traits<Graph>::vertex_descriptor src,<br>typename
graph_traits<Graph>::vertex_descriptor sink,<br>const
bgl_named_params<P, T, R>& params = <i>all
defaults</i>)<br><br><i>// 非命名参数版本</i><br>template <class Graph,
class CapacityEdgeMap, class ResidualCapacityEdgeMap, class
ReverseEdgeMap,<br>class PredecessorMap, class ColorMap, class DistanceMap,
class IndexMap><br>typename
property_traits<CapacityEdgeMap>::value_type<br>kolmogorov_max_flow(Graph&
g,<br>CapacityEdgeMap cap,<br>ResidualCapacityEdgeMap
res_cap,<br>ReverseEdgeMap rev_map,<br>PredecessorMap pre_map,<br>ColorMap
color,<br>DistanceMap dist,<br>IndexMap idx,<br>typename graph_traits
<Graph>::vertex_descriptor src,<br>typename graph_traits <Graph
>::vertex_descriptor sink)</pre>
+<p><font size="3">还提供了其它重载的非命名参数版本(不带
+DistanceMap/ColorMap/DistanceMap 的；使用带有给定索引映射的
+iterator_property_maps)</font></p>
+<p>函数 <tt>kolmogorov_max_flow()</tt>
+计算一个网络的最大流。关于最大流的描述，请见 <a
href="graph_theory_review.html#sec:network-flow-algorithms">网
+络流算法</a> 一节。该函数的返回值即为计算所得的最大流。该函数还针对
+<i>E</i> 中所有 <i>(u,v)</i> 计算了流值 <i>f(u,v)</i>，
+它以残留容量
+<i>r(u,v) = c(u,v) - f(u,v)</i> 的形式来返回。 </p>
+<p><b>要求：</b><br>
+表示网络的有向图 <i>G=(V,E)</i> 必须对于
+<i>E</i> 中的每条边都有一条反向边。即，输入图应为 <i>G<sub>in</sub>
+= (V,{E U
+E<sup>T</sup>})</i>。<tt>ReverseEdgeMap</tt>
+参数 <tt>rev</tt>
+必须将原图中的每条边映射至它的反向边，即对于 <i>E</i> 中的所有
<i>(u,v)</i>，<i>(u,v)
+-> (v,u)</i>。 </p>
+<p>注释：虽然 push-relabel 方法要求 <i>E<sup>T</sup></i>
+中的每条边必须具有容量 0，但本算法中的反向边允许带有容量值。如果在输入图
<i><font face="Courier New, monospace">G</font></i>
+中已有反向边，则它们可以被使用。这可以减少一半的边数，并显著提高性能。<br>
+<br>
+<b>算法描述：</b><br>
+Kolmogorov
+算法是增广路径算法的一种变体。标准的增广路径算法查找从源点到汇点的最短路
径，并通过从每条边的残留容量中减去该路径的瓶颈容量和将该容量增加到总流量
+中，来完成增广。同时，该最小容量被增加至反向边的残留容量中。如果在残留边树
中没有找到路径，则算法结束。Kolmogorov
+版本则不是在每次迭代中从源点到汇点查找新的最短路径，而是按如下方式保持已找
到的路径：</p>
+<p>该算法建立两棵搜索树，一棵源点树和一棵汇点树。每个顶点有一个标签(保存于
<i>ColorMap</i>)
+来识别它属于哪棵树，还有一个状态标志，表示该顶点是主动的还是被动的。在算法
开始时，只有源点和汇点被着色(源点==黑色，汇点==白色)和具有主动状
+态。所有其它顶点为灰色。该算法包含三个阶段：</p>
+<p><i>增长-阶段</i>：在这个阶段中，主动顶点可以获取那些通过具有大于零的容量
值的边所连接的邻接顶点
+为。获取的意思是，那些顶点成为主动
+的，且属于当前主动顶点的搜索树。如果没有更多的有效邻接顶点连接了，则当前顶
点变为被动的，且对下一个主动顶点继续增长阶段。如果没有主动顶点了，或某
+个顶点通过一条不饱和边发现了一个其它搜索树的顶点，则增长阶段终止。这种情况
下，发现了一条从源点到汇点的路径。</p>
+<p><i>增广-阶段</i>：这个阶段增广在增长阶段找到的路径。首先，它找出被发现路
径的瓶颈容量，然后更新
+该路径上各边的残留容量，从原残留容量
+中减去瓶颈容量。此外，反向边的残留容量被加上瓶颈容量。这个阶段可以销毁建立
起来的搜索树，因为它至少创建了一条饱和边。这意味着，搜索树坍塌成了森
+林，因为搜索树的一个条件是，它们中的每条边具有一条到终点的有效(=非饱和)连
接。</p>
+<p><i>采纳-阶段</i>：该阶段重建搜索树。一个简单的方法是，将被发现的路径上第
一个孤点之后的所有顶点
+标记为自由顶点(灰色)。
+而更复杂的方法是，给这些孤点安排新的父点：邻接顶点是已检查的，如果它们有一
个到同一个终点的有效连接，就象这个顶点有(一条带不饱和边的路径)。如果
+有，则该顶点成为当前孤点的新父点，且这个森林被重新包含入搜索树中。如果没有
找到新的父点，则这个顶点成为一个自由顶点(标为灰色)，且它的子孙成为孤
+点。当没有孤点时，采纳阶段结束。</p>
+<p><img src="figs/kolmogorov_max_flow.gif" name="Grafik2" align="left"
border="0" height="311" width="827"><br clear="left">
+<b>细节：</b></p>
+<ul>
+<li>
+<p>标记启发式策略：为每个顶点保存一个时间戳，表明处于算法的哪一次迭代中，计
算离对应终点的距离。 </p>
+<ul>
+<li>
+<p>这
+个距离在采纳-阶段被使用和进行计算。为了为孤点查找一个有效的新父点，要对可能
的父点进行检查，看是否有一个至所属树的终点的连接。如果有这
+样的连接，则该路径被用当前时间戳和距离值来标签。如果另一个孤点需要查找
点，且与一个带当前时间戳的顶点相遇，则该信息被使用。</p>
+</li>
+<li>
+<p>这个距离也在增长-阶段被使用。如果在查找新顶点时，一个顶点与另一个同树的
顶点相遇，则用另一个顶点的距离与它的距
+离相比较。如果该顶点距离较小，则另一个顶点成为当前顶点的新父点。这可以减少
搜索路径的长度，从而减少采纳操作的数量。</p>
+</li>
+</ul>
+</li>
+<li>
+<p>孤
+点的顺序：如上所述，增广-阶段和采纳-阶段会造成孤点。增广-阶段生成的孤点，根
据它们与终点的距离排序(最小的在前)。它与距离/时间戳策
+略相结合，可以不需要过于频繁地重新检查至终点的连接。出于同一原因，在采纳阶
段生成的新孤点在主队列的孤点之前被处理。</p>
+</li>
+</ul>
+<p><br>
+<b>实现说明：</b></p>
+<p>该算法的主要实现在 Kolmogorov 的博士论文中描述。我们进行了一些改动，以提
高性能：</p>
+<ul>
+<li>
+<p>初始化：该算法首先增广从源点->汇点的所有路径和从源点
->VERTEX->汇
+点的所有路径。这尤其改进了在图像视觉中所用的图切割，几乎每个顶点都有一个源
点和汇点的连接。在这一步中，具有从源点出发的不饱和连接的所有顶点被增加至主动
顶点列表中，而源点不会。 </p>
+</li>
+<li>
+<p>主动顶点：Kolmogorov
+用了两个主动节点列表，表明新的主动顶点被增加至另一个列表的尾部。取出一个主
动顶点是从第一个列表的头部进行的。如果第一个列表为空，则被第二个列表所
+交换。本实现只使用一个列表。</p>
+</li>
+<li>
+<p>增长-阶段：在增长阶段，主动列表的第一个顶点被取出，且所有出边被检查，如
果它们是不饱和的。对于边密度较高的图来说，这会
+降低性能。本实现保存了最后访问的边并从它继续，如果主动列表中的第一个顶点与
上一次增长-阶段中的是同一个的话。</p>
+</li>
+</ul>
+<p>该算法[<a href="bibliography.html#kolmogorov03">68</a>,
+<a href="bibliography.html#boykov-kolmogorov04">69</a>]
+由 Boykov 和 Kolmogorov 开发。
+</p>
+<h3>Where Defined 定义于</h3>
+<p><tt><a
href="../../../boost/graph/kolmogorov_max_flow.hpp">boost/graph/kolmogorov_max_flow.hpp</a></tt>
+</p>
+<h3>Parameters 参数</h3>
+<p>IN: <tt>Graph& g</tt> </p>
+<blockquote>一个有向图。图的类型必须符合
+<a href="VertexListGraph.html">点列表图Vertex List Graph</a>,
+<a href="EdgeListGraph.html">边列表图Edge
+List Graph</a> 和 <a href="IncidenceGraph.html">关联图
+Incidence Graph</a>。对于图中的每条边 <i>(u,v)</i>，反向边 <i>(v,u)</i>
+必须也在图中。 </blockquote>
+<p>IN: <tt>vertex_descriptor src</tt> </p>
+<blockquote>流网络图的源顶点。 </blockquote>
+<p>IN: <tt>vertex_descriptor sink</tt> </p>
+<blockquote>流网络图的汇顶点。 </blockquote>
+<h3>Named Parameters 命名参数</h3>
+<p>IN: <tt>capacity_map(EdgeCapacityMap cap)</tt> </p>
+<blockquote>边容量属性映射。该类型必须是一个常性的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。
+该映射的键类型必须是该图的边描述符类型。<br>
+<b>缺省值：</b><tt>get(edge_capacity, g)</tt> </blockquote>
+<p>OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap
+res)</tt> </p>
+<blockquote>将边映射至它的残留容量。该类型必须是一个可变的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。
+该映射的键类型必须是该图的边描述符类型。<br>
+<b>缺省值：</b><tt>get(edge_residual_capacity, g)</tt>
+</blockquote>
+<p>IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
+</p>
+<blockquote>一个边属性映射，将图中每条边 <i>(u,v)</i> 映射至反向边
<i>(v,u)</i>。
+该映射必须是一个常性的 <a
href="../../property_map/LvaluePropertyMap.html">左
+值属性映射</a>。该映射的键类型必须是图的边描述符类型。<br>
+<b>缺省值：</b><tt>get(edge_reverse, g)</tt> </blockquote>
+<p>UTIL: <tt>vertex_predecessor(PredecessorMap pre_map)</tt>
+</p>
+<blockquote>一个顶点属性映射，将边信息保存为顶点的前趋。该映射必须是一个可
变的 <a href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。
+该映射的键类型必须是图的顶点描述符类型。<br>
+<b>缺省值：</b><tt>get(vertex_predecessor, g)</tt>
+</blockquote>
+<p>OUT/UTIL: <tt>vertex_color(ColorMap color)</tt> </p>
+<blockquote>一个顶点属性映射，为边顶点保存颜色。如果一个顶点的颜色在本算法
运行后为黑色，则该顶点属于源点树，否则属于汇点
+树(用于表示最小割)。该映射必须是一个可变的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。
+该映射的键类型必须是图的顶点描述符类型。<br>
+<b>缺省值：</b><tt>get(vertex_color, g)</tt> </blockquote>
+<p>UTIL: <tt>vertex_distance(DistanceMap dist)</tt> </p>
+<blockquote>一个顶点属性映射，保存至对应终点的距离。它是一个用于加速本算法
的辅助映射。该映射必须是一个可变的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。
+该映射的键类型必须是图的顶点描述符类型。<br>
+<b>缺省值：</b><tt>get(vertex_distance, g)</tt> </blockquote>
+<p>IN: <tt>vertex_index_map(VertexIndexMap index_map)</tt>
+</p>
+<blockquote>将图中每个顶点映射至 <tt>[0, num_vertices(g))</tt>
+区间中的一个整数。该映射必须是一个常性的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。
+该映射的键类型必须是图的顶点描述符类型。<br>
+<b>缺省值：</b><tt>get(vertex_index, g)</tt> </blockquote>
+<h3>Example 示例</h3>
+<p>以下例子从一个DIMACS格式的文件(<tt><a
href="../example/max_flow.dat">example/max_flow.dat</a></tt>)
+中读入一个最大流问题(一个带有边容量的图)。该例子的源码可在
+<tt><a
href="../example/kolmogorov-eg.cpp">example/kolmogorov-eg.cpp</a></tt>
+中找到。
+</p>
+<pre>#include <boost/config.hpp><br>#include
<iostream><br>#include <string><br>#include
<boost/graph/kolmogorov_map_flow.hpp><br>#include
<boost/graph/adjacency_list.hpp><br>#include
<boost/graph/read_dimacs.hpp><br><br>int<br>main()<br>{<br> using
namespace boost;<br><br> typedef adjacency_list_traits<vecS, vecS,
directedS> Traits;<br> typedef adjacency_list<vecS, vecS, directedS,
<br> property<vertex_name_t, std::string>,<br>
property<edge_capacity_t, long,<br>
property<edge_residual_capacity_t, long,<br> property<edge_reverse_t,
Traits::edge_descriptor> > ><br> > Graph;<br><br> Graph g;<br>
long flow;<br><br> property_map<Graph, edge_capacity_t>::type <br>
capacity = get(edge_capacity, g);<br> property_map<Graph,
edge_reverse_t>::type <br> rev = get(edge_reverse, g);<br>
property_map<Graph, edge_residual_capacity_t>::type <br>
residual_capacity = get(edge_residual_capacity, g);<br><br>
Traits::vertex_descriptor s, t;<br> read_dimacs_max_flow(g, capacity, rev,
s, t);<br><br> flow = kolmogorov_max_flow(g, s, t);<br><br> std::cout
<< "c The total flow:" << std::endl;<br> std::cout
<< "s " << flow << std::endl << std::endl;<br><br>
std::cout << "c flow values:" << std::endl;<br>
graph_traits<Graph>::vertex_iterator u_iter, u_end;<br>
graph_traits<Graph>::out_edge_iterator ei, e_end;<br> for
(tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)<br> for
(tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)<br> if
(capacity[*ei] > 0)<br> std::cout << "f " << *u_iter
<< " " << target(*ei, g) << " " <br> <<
(capacity[*ei] - residual_capacity[*ei]) << std::endl;<br> return
0;<br>}</pre>
+<p>输出如下： </p>
+<pre>c The total flow:<br>s 13<br><br>c flow values:<br>f 0 6 3<br>f 0 1
0<br>f 0 2 10<br>f 1 5 1<br>f 1 0 0<br>f 1 3 0<br>f 2 4 4<br>f 2 3 6<br>f 2
0 0<br>f 3 7 5<br>f 3 2 0<br>f 3 1 1<br>f 4 5 4<br>f 4 6 0<br>f 5 4 0<br>f
5 7 5<br>f 6 7 3<br>f 6 4 0<br>f 7 6 0<br>f 7 5 0</pre>
+<h3>See Also 参见</h3>
+<p style="margin-bottom: 0cm;"><tt><a
href="edmonds_karp_max_flow.html">edmonds_karp_max_flow()</a></tt>,<br>
+<tt><a href="push_relabel_max_flow.html">push_relabel_max_flow()</a></tt>.
+</p>
+<hr>
+<table cellpadding="2" cellspacing="2">
+<tbody>
+<tr valign="top">
+<td>
+<p>Copyright © 2006</p>
+</td>
+<td>
+<p>Stephan Diederich, University Mannheim(<a
href="mailto:diederich@xxxxxxxxxxxxxxxxx";>diederich@xxxxxxxxxxxxxxxxx</a>)</p>
+</td>
+</tr>
+</tbody>
+</table>
+<p><br>
+<br>
+</p>
+</body></html>
=======================================
--- /trunk/libs/graph/doc/kruskal_min_spanning_tree.html Mon Mar 30
07:58:04 2009
+++ /trunk/libs/graph/doc/kruskal_min_spanning_tree.html Fri Aug 7
19:42:01 2009
@@ -1,199 +1,124 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek 2000
--
-- 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: Kruskal Minimum Spanning Tree</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><A NAME="sec:kruskal">
-<img src="figs/python.gif" alt="(Python)"/>
-<TT>kruskal_minimum_spanning_tree</TT>
-</H1>
-
-<PRE>
-template <class Graph, class OutputIterator, class P, class T, class
R>
-OutputIterator
-kruskal_minimum_spanning_tree(Graph& g, OutputIterator tree_edges,
- const bgl_named_params<P, T, R>& params = <i>all
defaults</i>);
-</PRE>
-
-<P>
-The <tt>kruskal_minimum_spanning_tree()</tt> function find a minimum
-spanning tree (MST) in an undirected graph with weighted edges. A MST is a
-set of edges that connects all the vertices in the graph where the
-total weight of the edges in the tree is minimized. For more details,
-see section <a
-href="graph_theory_review.html#sec:minimum-spanning-tree">Minimum
-Spanning Tree Problem</a>. The edges in the MST are output to the
-<tt>tree_edges</tt> output iterator. This function uses Kruskal's
-algorithm to compute the MST [<A
-HREF="bibliography.html#kruskal56">18</A>,<A
-HREF="bibliography.html#clr90">8</A>,<A
-HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>,<A
-HREF="bibliography.html#graham85">15</A>].
+<title>Boost Graph Library: Kruskal Minimum Spanning Tree</title></head>
+
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+
+<br clear="">
+
+
+<h1><a name="sec:kruskal">
+<img src="figs/python.gif" alt="(Python)">
+<tt>kruskal_minimum_spanning_tree</tt>
+</a></h1>
+
+<pre><a name="sec:kruskal">template <class Graph, class OutputIterator,
class P, class T, class
R><br>OutputIterator<br>kruskal_minimum_spanning_tree(Graph& g,
OutputIterator tree_edges, <br> const bgl_named_params<P, T,
R>& params = <i>all defaults</i>);<br></a></pre>
+
+<p>
+<a name="sec:kruskal">函数 <tt>kruskal_minimum_spanning_tree()</tt> 用于寻
找一个有权边无向图的最小生成树(MST)。MST是一个边集，其中的边连接了图中所有顶
点，且树中各边的权重之和为最小化。更多细节，请见 </a><a
href="graph_theory_review.html#sec:minimum-spanning-tree">最小生成树问题
</a>。MST中的边被输出至
+<tt>tree_edges</tt> 输出迭代器。该函数使用 Kruskal
+算法来计算 MST [<a href="bibliography.html#kruskal56">18</a>,<a
href="bibliography.html#clr90">8</a>,<a
href="bibliography.html#tarjan83:_data_struct_network_algo">27</a>,<a
href="bibliography.html#graham85">15</a>]。
</p>
<p>
-Kruskal's algorithm starts with each vertex in a tree by itself, and
-with no edges in the minimum spanning tree <i>T</i>. The algorithm
-then examines each edge in the graph in order of increasing edge
-weight. If an edge connects two vertices in different trees the
-algorithm merges the two trees into a single tree and adds the edge to
-<i>T</i>. We use the ``union by rank'' and ``path compression''
-heuristics to provide fast implementations of the disjoint set
-operations (<tt>MAKE-SET</tt>, <tt>FIND-SET</tt>, and
-<tt>UNION-SET</tt>). The algorithm is as follows:
+Kruskal 算法开始时只有树中各个顶点，不带最小生成树 <i>T</i> 中的任何边。然
后该算法按边的权重的非递增顺序检查图中各边。如果某条边连接的两个顶点位于两棵
不同的树，则该算法将这两棵树合并为一棵树，并将该边加入至
+<i>T</i>。我们用"按秩合并"以及"路径压缩"两种启发式策略来提供不相交集合操作
(<tt>MAKE-SET</tt>, <tt>FIND-SET</tt>, 和
+<tt>UNION-SET</tt>)的快速实现。算法如下：
</p>
-<pre>
-KRUSKAL-MST(<i>G</i>, <i>w</i>)
- <i>T := Ø</i>
- <b>for</b> each vertex <i>u in V</i>
- MAKE-SET(<i>DS</i>, <i>u</i>)
- <b>end for</b>
- <b>for</b> each edge <i>(u,v) in E</i> in order of nondecreasing weight
- <b>if</b> FIND-SET(<i>DS</i>, <i>u</i>) != FIND-SET(<i>DS</i>,
<i>v</i>)
- UNION-SET(<i>DS</i>, <i>u</i>, <i>v</i>)
- <i>T := T U {(u,v)}</i>
- <b>end for</b>
+<pre>KRUSKAL-MST(<i>G</i>, <i>w</i>) <br> <i>T := Ø</i> <br> <b>for</b>
each vertex <i>u in V</i> <br> MAKE-SET(<i>DS</i>, <i>u</i>) <br>
<b>end for</b>
+ <b>for</b> each edge <i>(u,v) in E</i> in order of nondecreasing weight
<br> <b>if</b> FIND-SET(<i>DS</i>, <i>u</i>) != FIND-SET(<i>DS</i>,
<i>v</i>) <br> UNION-SET(<i>DS</i>, <i>u</i>, <i>v</i>) <br>
<i>T := T U {(u,v)}</i> <br> <b>end for</b>
<b>return</b> <i>T</i>
</pre>
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/kruskal_min_spanning_tree.hpp"><TT>boost/graph/kruskal_min_spanning_tree.hpp</TT></a>
-
-<P>
-
-<h3>Parameters</h3>
+<h3>Where Defined 定义于</h3>
+
+<p>
+<a
href="../../../boost/graph/kruskal_min_spanning_tree.hpp"><tt>boost/graph/kruskal_min_spanning_tree.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Parameters 参数</h3>
IN: <tt>const Graph& g</tt>
-<blockquote>
- An undirected graph. The graph type must be a model of
- <a href="./VertexListGraph.html">Vertex List Graph</a>
- and <a href="./EdgeListGraph.html">Edge List Graph</a>.<br>
-
- <b>Python</b>: The parameter is named <tt>graph</tt>.
+<blockquote>一个无向图。图类型必须符合 <a href="./VertexListGraph.html">点
列表图Vertex List Graph</a> 和 <a href="./EdgeListGraph.html">边列表图Edge
List Graph</a>。<br>
+
+ <b>Python</b>: 该参数名为 <tt>graph</tt>.
</blockquote>
IN: <tt>OutputIterator spanning_tree_edges</tt>
-<blockquote>
- The edges of the minimum spanning tree are output to this <a
- href="http://www.sgi.com/tech/stl/OutputIterator.html";>Output
- Iterator</a>.<br>
-
- <b>Python</b>: This parameter is not used in Python. Instead, a
- Python <tt>list</tt> containing all of the spanning tree edges is
- returned.
+<blockquote>最小生成树的边被输出至该 <a
href="http://www.sgi.com/tech/stl/OutputIterator.html";>输出迭代器</a>。<br>
+
+ <b>Python</b>: 在Python中未使用该参数。而是用一个包含生成树所有边的
+ Python <tt>list</tt> 返回。
</blockquote>
-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>
IN: <tt>weight_map(WeightMap w_map)</tt>
-<blockquote>
-The weight or ``length'' of
- each edge in the graph. The <tt>WeightMap</tt> type must be a model
- of <a href="../../property_map/ReadablePropertyMap.html">Readable
- Property Map</a> and its value type must be <a
- href="http://www.sgi.com/tech/stl/LessThanComparable.html";>Less Than
- Comparable</a>. The key type of this map needs to be the graph's
- edge descriptor type.<br>
- <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
- <b>Python</b>: Must be an <tt>edge_double_map</tt> for the graph.<br>
- <b>Python default</b>: <tt>graph.get_edge_double_map("weight")</tt>
+<blockquote>图中每条边的权重或"长度"。类型 <tt>WeightMap</tt> 必须符合
+ <a
href="http://alai04.kmip.net/boost_doc/libs/property_map/ReadablePropertyMap.html";>可
读属性映射</a> 且其值类型必须符合 <a
href="http://www.sgi.com/tech/stl/LessThanComparable.html";>可小于比较</a>。
这个映射的键类型必须可以是图的边描述符类型。<br>
+ <b>缺省值：</b><tt>get(edge_weight, g)</tt><br>
+
+ <b>Python</b>: 必须为该图的一个 <tt>edge_double_map</tt>。<br>
+ <b>Python 缺省
值：</b><tt>graph.get_edge_double_map("weight")</tt><tt></tt>
</blockquote>
UTIL: <tt>rank_map(RankMap r_map)</tt>
-<blockquote>
- This is used by the disjoint sets data structure.
- The type <tt>RankMap</tt> must be a model of <a
- href="../../property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a>. The vertex descriptor type of the graph needs to
- be usable as the key type of the rank map. The value type of the
- rank map must be an integer type.<br>
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of the integers of size
- <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
- map.<br>
-
- <b>Python</b>: Unsupported parameter.
+<blockquote>由不相交集合数据结构使用。类型 <tt>RankMap</tt> 必须符合 <a
href="../../property_map/ReadWritePropertyMap.html">读/写属性映射</a>。图的
顶点描述符类型必须可用作这个秩映射的键类型。秩映射的值类型必须为整数类型。
<br>
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a>，创建自一个值大小为
+ <tt>num_vertices(g)</tt> 的整数
+ <tt>std::vector</tt><span style="font-family: monospace;">，</span>且以
<tt>i_map</tt> 作为索引映射。<br>
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
UTIL: <tt>predecessor_map(PredecessorMap p_map)</tt>
-<blockquote>
- This is used by the disjoint sets data structure, and is <b>not</b>
- used for storing predecessors in the spanning tree. The predecessors
- of the spanning tree can be obtained from the spanning tree edges
- output. The type <tt>PredecessorMap</tt> must be a model of <a
- href="../../property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a>. The key type value types of the predecessor map
- must be the vertex descriptor type of the graph. <br>
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of vertex descriptors of size
- <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
- map.<br>
-
- <b>Python</b>: Unsupported parameter.
+<blockquote>用于不相交集合数据结构，而不是用于保存生成树中的前趋。生成树的
前趋可以从生成树边的输出获得。类型 <tt>PredecessorMap</tt> 必须符合 <a
href="http://alai04.kmip.net/boost_doc/libs/property_map/ReadWritePropertyMap.html";>读
/写属性映射</a>。这个前趋映射的键类型必须是图的顶点描述符类型。<br>
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a><tt>，</tt>创建自一个值大小为
+ <tt>num_vertices(g)</tt> 的顶点描述符
+ <tt>std::vector</tt><span style="font-family: monospace;">，</span>且以
<tt>i_map</tt> 作为索引映射。<br>
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
-<blockquote>
- This maps each vertex to an integer in the range <tt>[0,
- num_vertices(g))</tt>. This is only necessary if the default is used
- for the rank or predecessor maps. The type <tt>VertexIndexMap</tt>
- must be a model of <a
- href="../../property_map/ReadablePropertyMap.html">Readable Property
- Map</a>. The value type of the map must be an integer type. The
- vertex descriptor type of the graph needs to be usable as the key
- type of the map.<br>
- <b>Default:</b> <tt>get(vertex_index, g)</tt>
- Note: if you use this default, make sure your graph has
- an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
- not have an internal <tt>vertex_index</tt> property.
- <br>
-
- <b>Python</b>: Unsupported parameter.
+<blockquote>它将每个顶点映射至位于区间 <tt>[0,
+ num_vertices(g))</tt> 中的一个整数。仅当秩映射或前趋映射使用缺省值时需
要。类型 <tt>VertexIndexMap</tt>
+ 必须符合 <a
href="http://alai04.kmip.net/boost_doc/libs/property_map/ReadablePropertyMap.html";>可
读属性映射</a>。该映射的值类型必须是一个整数类型。图的顶点描述符类型需要可以
被用作该映射的键类型。<br>
+
+
+ <b>缺省值：</b><tt>get(vertex_index, g)</tt>.
+ 注意：如果你使用该缺省值，请确认你的图具有一个内部的
<tt>vertex_index</tt> 属性。例如，带 <tt>VertexList=listS</tt> 的
+ <tt>adjacenty_list</tt> 并不具有内部的 <tt>vertex_index</tt> 属性。<br>
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
-<H3>Complexity</H3>
-
-<P>
-The time complexity is <i>O(E log E)</i>
-
-<H3>Example</H3>
-
-<P>
-The file <a
-href="../example/kruskal-example.cpp"><TT>examples/kruskal-example.cpp</TT></a>
-contains an example of using Kruskal's algorithm.
-
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+<h3>Complexity 复杂度</h3>
+
+<p>时间复杂度为 <i>O(E log E)</i>
+
+</p><h3>Example 示例</h3>
+
+<p>文件 <a
href="../example/kruskal-example.cpp"><tt>examples/kruskal-example.cpp</tt></a>
+包含了一个使用 Kruskal 算法的例子。<br>
+</p><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright © 2000-2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,
Indiana University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
+
+</body></html>
=======================================
--- /trunk/libs/graph/doc/maximum_matching.html Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/maximum_matching.html Fri Aug 7 19:42:01 2009
@@ -1,4 +1,5 @@
-<html><head><!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright 2005 Aaron Windsor
--
-- Use, modification and distribution is subject to the Boost Software
@@ -11,258 +12,137 @@
<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
<br clear="">
<h1>
-<a name="sec:maximum_cardinality_matching">Maximum Cardinality Matching</a>
+<a name="sec:maximum_cardinality_matching">Maximum Cardinality Matching 最
大基数匹配</a>
</h1>
-<pre>
-template <typename Graph, typename MateMap>
-void edmonds_maximum_cardinality_matching(const Graph& g, MateMap
mate);
-
-template <typename Graph, typename MateMap, typename VertexIndexMap>
-void edmonds_maximum_cardinality_matching(const Graph& g, MateMap
mate, VertexIndexMap vm);
-
-template <typename Graph, typename MateMap>
-bool checked_edmonds_maximum_cardinality_matching(const Graph& g,
MateMap mate);
-
-template <typename Graph, typename MateMap, typename VertexIndexMap>
-bool checked_edmonds_maximum_cardinality_matching(const Graph& g,
MateMap mate, VertexIndexMap vm);
-</pre>
+<pre>template <typename Graph, typename MateMap><br>void
edmonds_maximum_cardinality_matching(const Graph& g, MateMap
mate);<br><br>template <typename Graph, typename MateMap, typename
VertexIndexMap><br>void edmonds_maximum_cardinality_matching(const
Graph& g, MateMap mate, VertexIndexMap vm);<br><br>template
<typename Graph, typename MateMap><br>bool
checked_edmonds_maximum_cardinality_matching(const Graph& g, MateMap
mate);<br><br>template <typename Graph, typename MateMap, typename
VertexIndexMap><br>bool
checked_edmonds_maximum_cardinality_matching(const Graph& g, MateMap
mate, VertexIndexMap vm);<br></pre>
<p>
-<a name="sec:articulation_points">A <i>matching</i> is a subset of the
edges
-of a graph such that no two edges share a common vertex.
-Two different matchings in the same graph are illustrated below (edges in
the
-matching are colored blue.) The matching on the left is a <i>maximal
matching</i>,
-meaning that its size can't be increased by adding edges. The matching on
the
-right is a <i>maximum cardinality matching</i>, meaning that is has
maximum size
-over all matchings in the graph.
-
-</a></p><p></p><center>
+<a name="sec:articulation_points">一个 <i>匹配matching</i> 是指，图的一个边
子集，其中没有两条边共享同一个顶点。下图示范了同一个图中的两个不同的匹配(匹
配中的边以蓝色表示)。左边的匹配是一个 <i>最大匹配maximal matching</i>，即不
能通过增加边来增加它的大小。右边的匹配则是一个 <i>最大基数匹配maximum
cardinality matching</i>，即在该图所有可能的匹配中，它的大小是最大的。
</a></p><center>
<table border="0">
-<tr>
+<tbody><tr>
<td><a name="sec:articulation_points"><img
src="figs/maximal-match.png"></a></td>
<td width="150"></td>
<td><a name="sec:articulation_points"><img
src="figs/maximum-match.png"></a></td>
</tr>
-</table>
+</tbody></table>
</center>
<p>
-Both <tt>edmonds_maximum_cardinality_matching</tt> and
-<tt>checked_edmonds_maximum_cardinality_matching</tt> find the
-maximum cardinality matching in any undirected graph. The matching is
returned in a
-<tt>MateMap</tt>, which is a
-<a
href="../../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>
-that maps vertices to vertices. In the mapping returned, each vertex is
either mapped
-to the vertex it's matched to, or to
<tt>graph_traits<Graph>::null_vertex()</tt> if it
-doesn't participate in the matching. If no <tt>VertexIndexMap</tt> is
provided, both functions
-assume that the <tt>VertexIndexMap</tt> is provided as an internal graph
property accessible
-by calling <tt>get(vertex_index,g)</tt>. The only difference between
-<tt>edmonds_maximum_cardinality_matching</tt> and
-<tt>checked_edmonds_maximum_cardinality_matching</tt> is that as a final
step,
-the latter algorithm runs a simple verification on the matching computed
and
-returns <tt>true</tt> if and only if the matching is indeed
-a maximum cardinality matching.
-
-<p>
-Given a matching M, any vertex that isn't covered by an edge in M is
called <i>free</i>. Any
-simple path containing exactly <i>2n + 1</i> edges that starts and ends at
free vertices and contains
-<i>n</i> edges from M is called an <i>alternating path</i>. Given an
alternating path <i>p</i>, all matching and
-non-matching edges on <i>p</i> can be swapped, resulting in a new matching
that's larger than the
-original matching by exactly one edge. This method of incrementally
increasing the size of matching, along
-with the following fact, forms the basis of Edmonds' matching algorithm:
-
-<blockquote>
-<i>An alternating path through the matching M exists if and only if M is
not a maximum cardinality matching.</i>
-</blockquote>
-
-The difficult part is, of course, finding an augmenting path whenever one
exists.
-The algorithm we use for finding a maximum cardinality matching consists
of three basic steps:
+<tt>edmonds_maximum_cardinality_matching</tt> 和
+<tt>checked_edmonds_maximum_cardinality_matching</tt> 都可在任意无向图中查
找最大基数匹配。匹配在一个
+<tt>MateMap</tt> 中返回，它是一个
+<a href="../../property_map/ReadWritePropertyMap.html">读写属性映射</a>，从
顶点映射至顶点。在所返回的映射中，每个顶点要么映射至它所匹配的顶点，要么映射
至 <tt>graph_traits<Graph>::null_vertex()</tt>，如果它不在该匹配中。如
果没有给定 <tt>VertexIndexMap</tt>，则两个函数均假定
<tt>VertexIndexMap</tt> 是一个可通过调用 <tt>get(vertex_index,g)</tt> 来进行
访问的一个图内部属性。<tt>edmonds_maximum_cardinality_matching</tt> 与
+<tt>checked_edmonds_maximum_cardinality_matching</tt> 的唯一差别在于最后的
步骤，后一个算法对计算得到的匹配运行一次简单的校验，当且仅当该匹配的确是一个
最大基数匹配时，返回 <tt>true</tt>。
+
+</p><p>给定一个匹配M，未被M中的边所覆盖的顶点被称为<i>自由的</i>。任意一条
恰好有 <i>2n + 1</i> 条边、以自由顶点开始及结束、包含M中
+<i>n</i> 条边的简单路径，被称为 <i>交替路径alternating path</i>。给定一条交
替路径 <i>p</i>，<i>p</i> 中的匹配边和非匹配边可以交换，从而得到一个恰好比原
匹配多一条边的新匹配。这个增量法可以递增匹配的大小，加上以下事实，形成了
Edmonds 匹配算法的基础：
+
+</p><blockquote>
+<i>匹配M存在一条交替路径，当且仅当M不是最大基数匹配。</i>
+</blockquote>当然，难点在于，当存在一条增广路径时，如何找到它。我们用于查找
最大基数匹配的算法包含以下三个基本步骤：
<ol>
-<li>Create an initial matching.
-<li>Repeatedly find an augmenting path and use it to increase the size of
the matching until no augmenting path exists.
-<li>Verify that the matching found is a maximum cardinality matching.
-</ol>
-
-If you use <tt>checked_edmonds_maximum_cardinality_matching</tt> or
-<tt>edmonds_maximum_cardinality_matching</tt>, all three of these
-steps are chosen for you, but it's easy to plug in different algorithms
for these three steps
-using a generic matching function discussed below - in fact, both
<tt>checked_edmonds_maximum_cardinality_matching</tt>
-and <tt>edmonds_maximum_cardinality_matching</tt> are just inlined
specializations of this function.
-
-<p>
-When quoting time bounds for algorithms, we assume that
<tt>VertexIndexMap</tt> is a property map
-that allows for constant-time mapping between vertices and indices (which
is easily achieved if,
-for instance, the vertices are stored in contiguous memory.) We use
<i>n</i> and <i>m</i> to represent the size
-of the vertex and edge sets, respectively, of the input graph.
-
-<h4>Algorithms for Creating an Initial Matching</h4>
+<li>创建一个初始匹配。
+</li><li>重复查找一条增广路径，并用它来递增匹配的大小，直至增广路径不存在。
+</li><li>校验所找到的匹配是最大基数匹配。
+</li></ol>如果你使用 <tt>checked_edmonds_maximum_cardinality_matching</tt>
或
+<tt>edmonds_maximum_cardinality_matching</tt>，则以上三步均为你选中，不过也
很容易将它们插入其它算法中，因为这三个步骤使用了下面将要讨论的通用匹配函数
- 事实上，<tt>checked_edmonds_maximum_cardinality_matching</tt> 和
<tt>edmonds_maximum_cardinality_matching</tt> 只是这个函数的内联特化版本。
+
+<p>在引用这个算法时，我们假定 <tt>VertexIndexMap</tt> 是一个属性映射，它可
以在常量时间内，在顶点和索引间进行映射(这很容易实现，例如，顶点被保存在连续
的内存中)。我们用 <i>n</i> 和 <i>m</i> 来分别表示输入图的顶点集和边集大小。
+
+</p><h4>创建一个初始匹配的算法</h4>
<ul>
-<li><b><tt>empty_matching</tt></b>: Takes time <i>O(n)</i> to initialize
the empty matching.
-<li><b><tt>greedy_matching</tt></b>: The matching obtained by iterating
through the edges and adding an edge
-if it doesn't conflict with the edges already in the matching. This
matching is maximal, and is therefore
-guaranteed to contain at least half of the edges that a maximum matching
has. Takes time <i>O(m log n)</i>.
-<li><b><tt>extra_greedy_matching</tt></b>: Sorts the edges in increasing
order of the degree of the vertices
-contained in each edge, then constructs a greedy matching from those
edges. Also a maximal matching, and can
-sometimes be much closer to the maximum cardinality matching than a simple
<tt>greedy_matching</tt>.
-Takes time <i>O(m log n)</i>, but the constants involved make this a
slower algorithm than
-<tt>greedy_matching</tt>.
-</ul>
-
-<h4>Algorithms for Finding an Augmenting Path</h4>
+<li><b><tt>empty_matching</tt></b>: 用 <i>O(n)</i> 的时间初始化一个空的匹
配。
+</li><li><b><tt>greedy_matching</tt></b>: 通过对边进行迭代，如果某条边与匹
配中的已有边不冲突，则加入该边，从而得到一个匹配。该匹配是最大的，因此保证至
少包含了最大匹配所具有的一半边。花费的时间为 <i>O(m log n)</i>。
+</li><li><b><tt>extra_greedy_matching</tt></b>: 按每条边所含顶点的度数的递
增序对边进行排序，然后从这些边构造一个贪心匹配。这也是一个最大匹配，并且有时
会比简单的 <tt>greedy_matching</tt> 更加接近于最大基数匹配。花费的时间为
<i>O(m log n)</i>，但其常量系数令此算法慢于
+<tt>greedy_matching</tt>。
+</li></ul>
+
+<h4>查找一个增广路径的算法</h4>
<ul>
-<li><b><tt>edmonds_augmenting_path_finder</tt></b>: Finds an augmenting
path in time <i>O(m alpha(m,n))</i>,
-where <i>alpha(m,n)</i> is an inverse of the Ackerman function.
<i>alpha(m,n)</i> is one of the slowest
-growing functions that occurs naturally in computer science; essentially,
<i>alpha(m,n)</i> ≤ 4 for any
-graph that we'd ever hope to run this algorithm on. Since we arrive at a
maximum cardinality matching after
-augmenting <i>O(n)</i> matchings, the entire algorithm takes time <i>O(mn
alpha(m,n))</i>. Edmonds' original
-algorithm appeared in [<a href="bibliography.html#edmonds65">64</a>], but
our implementation of
-Edmonds' algorithm closely follows Tarjan's
-description of the algorithm from [<a
href="bibliography.html#tarjan83:_data_struct_network_algo">27</a>].
-<li><b><tt>no_augmenting_path_finder</tt></b>: Can be used if no
augmentation of the initial matching is desired.
-</ul>
-
-<h4>Verification Algorithms</h4>
+<li><b><tt>edmonds_augmenting_path_finder</tt></b>: 在 <i>O(m
alpha(m,n))</i> 时间内查找一个增广路径，其中 <i>alpha(m,n)</i> 是一个逆
Ackerman 函数。<i>alpha(m,n)</i> 是计算机科学中自然发生的增长最慢的函数之
一；基本上，对于我们准备对其运行该算法的任意图来说，<i>alpha(m,n)</i> ≤ 4。
由于我们会在 <i>O(n)</i> 次匹配增广后得到最大基数匹配，所以整个算法的时间为
<i>O(mn alpha(m,n))</i>。Edmonds 的原算法在[<a
href="bibliography.html#edmonds65">64</a>]中，但我们的
+Edmonds' 算法实现更接近于[<a
href="bibliography.html#tarjan83:_data_struct_network_algo">27</a>]中的
Tarjan 对该算法的描述。
+</li><li><b><tt>no_augmenting_path_finder</tt></b>: 如果初始匹配不需要增广
时，可以用它。
+</li></ul>
+
+<h4>校验算法</h4>
<ul>
-<li><b><tt>maximum_cardinality_matching_verifier</tt></b>: Returns true if
and only if the matching found is a
-maximum cardinality matching. Takes time <i>O(m alpha(m,n))</i>, which is
on the order of a single iteration
-of Edmonds' algorithm.
-<li><b><tt>no_matching_verifier</tt></b>: Always returns true
-</ul>
-
-Why is a verification algorithm needed? Edmonds' algorithm is fairly
complex, and it's nearly
-impossible for a human without a few days of spare time to figure out if
the matching produced by
-<tt>edmonds_matching</tt> on a graph with, say, 100 vertices and 500 edges
is indeed a maximum cardinality
-matching. A verification algorithm can do this mechanically, and it's much
easier to verify by inspection
-that the verification algorithm has been implemented correctly than it is
to verify by inspection that
-Edmonds' algorithm has been implemented correctly.
-The Boost Graph library makes it incredibly simple to perform the
subroutines needed by the verifier
-(such as finding all the connected components of odd cardinality in a
graph, or creating the induced graph
-on all vertices with a certain label) in just a few lines of code.
-
-<p>
-Understanding how the verifier works requires a few graph-theoretic facts.
-Let <i>m(G)</i> be the size of a maximum cardinality matching in the graph
<i>G</i>.
-Denote by <i>o(G)</i> the number of connected components in <i>G</i> of
odd cardinality, and for a set of
-vertices <i>X</i>, denote by <i>G - X</i> the induced graph on the vertex
set <i>V(G) - X</i>. Then the
-Tutte-Berge Formula says that
-<blockquote>
+<li><b><tt>maximum_cardinality_matching_verifier</tt></b>: 当且仅当找到的匹
配为最大基数匹配时，返回 true。花费的时间为 <i>O(m alpha(m,n))</i>，与
Edmonds' 算法的单次迭代相同。
+</li><li><b><tt>no_matching_verifier</tt></b>: 总是返回 true
+</li></ul>为何需要一个校验算法？Edmonds' 算法相当复杂，没有几天的时间，几乎
没有可能指出
+<tt>edmonds_matching</tt> 在一个，比如说有100个点和500条边的图上，所产生的
匹配是否确是最大基数匹配。校验算法可以自动来做这个工作，而且验证这个校验算法
是否正确实现，比验证
+Edmonds' 算法是否正确实现，要容易得多。Boost Graph 库使得执行校验器所需的子
程序(如查找一个图中所有奇基数的连通分支，或是创建带有特定标签的所有顶点的导
出图)相当地简单，只需要短短几行代码。
+
+<p>要了解校验器如何工作，需要一点图论知识。令 <i>m(G)</i> 为图 <i>G</i> 中
最大基数匹配的大小。<i>o(G)</i> 表示 <i>G</i> 中奇基数的连通分支数量，且对于
点集 <i>X</i>，<i>G - X</i> 表示点集 <i>V(G) - X</i> 的导出图。Tutte-Berge
公式表明
+</p><blockquote>
<i>2 * m(G) = min ( |V(G)| + |X| - o(G-X) )</i>
-</blockquote>
-Where the minimum is taken over all subsets <i>X</i> of the vertex set
<i>V(G)</i>. A side effect of the
-Edmonds Blossom-Shrinking algorithm is that it computes what is known as
the Edmonds-Gallai decomposition
-of a graph: it decomposes the graph into three disjoint sets of vertices,
one of which achieves the minimum
-in the Tutte-Berge Formula.
-
-An outline of our verification procedure is:
-
-Given a <tt>Graph g</tt> and <tt>MateMap mate</tt>,
+</blockquote>其中的最小值是从顶点集 <i>V(G)</i> 的所有子集 <i>X</i> 中得到
的。Edmonds
+Blossom-Shrinking 算法的一个副作用是，它计算了一个图的所谓 Edmonds-Gallai
+分解：它将图分解为三个不相交的顶点集，其中一个实现了 Tutte-Berge 公式中的最
小值。我们的校验程序的概况是：给定一个 <tt>Graph g</tt> 和一个 <tt>MateMap
mate</tt>,
<ol>
-<li>Check to make sure that <tt>mate</tt> is a valid matching on
<tt>g</tt>.
-<li>Run <tt>edmonds_augmenting_path_finder</tt> once on <tt>g</tt> and
<tt>mate</tt>. If it finds an augmenting
-path, the matching isn't a maximum cardinality matching. Otherwise, we
retrieve a copy of the <tt>vertex_state</tt>
-map used by the <tt>edmonds_augmenting_path_finder</tt>. The
Edmonds-Gallai decomposition tells us that the set
-of vertices labeled <tt>V_ODD</tt> by the <tt>vertex_state</tt> map can be
used as the set X to achieve the
-minimum in the Tutte-Berge Formula.
-<li>Count the number of vertices labeled <tt>V_ODD</tt>, store this in
<tt>num_odd_vertices</tt>.
-<li>Create a <a href="filtered_graph.html"><tt>filtered_graph</tt></a>
-consisting of all vertices that aren't labeled <tt>V_ODD</tt>. Count the
number of odd connected components
-in this graph and store the result in
<tt>num_odd_connected_components</tt>.
-<li>Test to see if equality holds in the Tutte-Berge formula using |X| =
<tt>num_odd_vertices</tt> and o(G-X) =
<tt>num_odd_connected_components</tt>. Return true if it holds, false
otherwise.
-</ol>
-
-Assuming these steps are implemented correctly, the verifier will never
return a false positive,
-and will only return a false negative if
<tt>edmonds_augmenting_path_finder</tt> doesn't compute the
-<tt>vertex_state</tt> map correctly, in which case the
<tt>edmonds_augmenting_path_finder</tt>
-isn't working correctly.
-
-
-<h4>Creating Your Own Matching Algorithms</h4>
-
-Creating a matching algorithm is as simple as plugging the algorithms
described above into a generic
-matching function, which has the following signature:
-<pre>
-template <typename Graph,
- typename MateMap,
- typename VertexIndexMap,
- template <typename, typename, typename> class
AugmentingPathFinder,
- template <typename, typename> class InitialMatchingFinder,
- template <typename, typename, typename> class
MatchingVerifier>
- bool matching(const Graph& g, MateMap mate, VertexIndexMap vm)
-</pre>
-The matching functions provided for you are just inlined specializations
of this function:
-<tt>edmonds_maximum_cardinality_matching</tt> uses
<tt>edmonds_augmenting_path_finder</tt>
-as the <tt>AugmentingPathFinder</tt>, <tt>extra_greedy_matching</tt> as
the <tt>InitialMatchingFinder</tt>,
-and <tt>no_matching_verifier</tt> as the <tt>MatchingVerifier</tt>.
-<tt>checked_edmonds_maximum_cardinality_matching</tt> uses the same
parameters except that
-<tt>maximum_cardinality_matching_verifier</tt> is used for the
<tt>MatchingVerifier</tt>.
-
-<p>
-These aren't necessarily the best choices for any situation - for example,
it's been claimed in the literature
-that for sparse graphs, Edmonds' algorithm converges to the maximum
cardinality matching more quickly if it
-isn't supplied with an intitial matching. Such an algorithm can be easily
assembled by calling <tt>matching</tt> with
-<ul>
+<li>检查以确认 <tt>mate</tt> 是 <tt>g</tt> 上的一个有效匹配。
+</li><li>对 <tt>g</tt> 和 <tt>mate</tt> 运行一次
<tt>edmonds_augmenting_path_finder</tt>。如果它找到一条增广路径，则该匹配不
是最大基数匹配。否则，我们取一份 <tt>edmonds_augmenting_path_finder</tt> 所
用的 <tt>vertex_state</tt>
+映射的拷贝。Edmonds-Gallai 分解告诉我们，被 <tt>vertex_state</tt> 映射标记
为 <tt>V_ODD</tt> 的顶点集可以作为集合 X 以达到 Tutte-Berge 公式中的最小值。
</li><li>计算标记为 <tt>V_ODD</tt> 的顶点数量，保存于
<tt>num_odd_vertices</tt>。
+</li><li>创建一个 <a
href="filtered_graph.html"><tt>filtered_graph</tt></a>，包含未被标记为
<tt>V_ODD</tt> 的所有顶点。计算该图中奇连通分支的数量，将结果保存于
<tt>num_odd_connected_components</tt>。
+</li><li>用 |X| = <tt>num_odd_vertices</tt> and o(G-X) =
<tt>num_odd_connected_components</tt> 来测试在 Tutte-Berge 公式中的相等性是
否保持。如果是，则返回 true，否则返回 false。
+</li></ol>假设这些步骤都正确地实现，则校验器不可能返回 false positive，只会
在 <tt>edmonds_augmenting_path_finder</tt> 未能正确计算
+<tt>vertex_state</tt> 映射时返回 false negative，在这种情况
下，<tt>edmonds_augmenting_path_finder</tt>
+工作不正常。
+
+
+<h4>创建你自己的匹配算法</h4>创建一个匹配算法和将上述算法插入到泛型匹配函数
中同样简单，匹配算法具有以下签名：
+<pre>template <typename Graph, <br> typename MateMap,<br> typename
VertexIndexMap,<br> template <typename, typename, typename> class
AugmentingPathFinder, <br> template <typename, typename> class
InitialMatchingFinder,<br> template <typename, typename, typename>
class MatchingVerifier><br> bool matching(const Graph& g, MateMap
mate, VertexIndexMap vm)<br></pre>为你提供的匹配函数只是这个函数的内联特化版
本：<tt>edmonds_maximum_cardinality_matching</tt> 使用
<tt>edmonds_augmenting_path_finder</tt> 作为
<tt>AugmentingPathFinder</tt>，用 <tt>extra_greedy_matching</tt> 作为
<tt>InitialMatchingFinder</tt>，用 <tt>no_matching_verifier</tt> 作为
<tt>MatchingVerifier</tt>。
+<tt>checked_edmonds_maximum_cardinality_matching</tt> 使用了相同的参
数，除了用
+<tt>maximum_cardinality_matching_verifier</tt> 作为
<tt>MatchingVerifier</tt>。
+
+<p>这些不一定是任意情况下的最好选择 - 例如，已有文献声称，对于稀疏图，如果
不提供一个初始匹配，Edmonds' 算法可以更快地收敛至最大基数匹配。这样的一个算
法可以很容易地通过用以下参数调用 <tt>matching</tt> 来组装得到：
+</p><ul>
<li><tt>AugmentingPathFinder = edmonds_augmenting_path_finder</tt>
-<li><tt>InitialMatchingFinder = empty_matching</tt>
-</ul>
-and choosing the <tt>MatchingVerifier</tt> depending on how careful you're
feeling.
-
-<p>
-Suppose instead that you want a relatively large matching quickly, but are
not exactly interested in a maximum matching.
-Both extra_greedy_matching and greedy_matching find maximal matchings,
which means they're guaranteed to be at
-least half the size of a maximum cardinality matching, so you could call
<tt>matching</tt> with
-<ul>
+</li><li><tt>InitialMatchingFinder = empty_matching</tt>
+</li></ul>并根据你觉得要多小心，来选择 <tt>MatchingVerifier</tt>。
+
+<p>假如你想快点得到一个较大的匹配，而不关心是不是精确的最大匹配。
extra_greedy_matching 和 greedy_matching 都能找出最大匹配，这意味着它们保证
至少有最大基数匹配一半的大小，所以你可以用以下参数调用 <tt>matching</tt>：
+</p><ul>
<li><tt>AugmentingPathFinder = no_augmenting_path_finder</tt>
-<li><tt>InitialMatchingFinder = extra_greedy_matching</tt>
-<li><tt>MatchingVerifier = maximum_cardinality_matching_verifier</tt>
-</ul>
-The resulting algorithm will find an extra greedy matching in time <i>O(m
log n)</i> without looking for
-augmenting paths. As a bonus, the return value of this function is true if
and only if the extra greedy
-matching happens to be a maximum cardinality matching.
-
-</p><h3>Where Defined</h3>
+</li><li><tt>InitialMatchingFinder = extra_greedy_matching</tt>
+</li><li><tt>MatchingVerifier = maximum_cardinality_matching_verifier</tt>
+</li></ul>这样所得到的算法会在 <i>O(m log n)</i> 时间内找到一个额外贪心匹
配，它不查找增广路径。作为额外的奖励，当且仅当这个额外贪心匹配刚好是一个最大
基数匹配时，该函数返回 true。
+
+<p></p><h3>Where Defined 定义于</h3>
<p>
<a
href="../../../boost/graph/max_cardinality_matching.hpp"><tt>boost/graph/max_cardinality_matching.hpp</tt></a>
-</p><h3>Parameters</h3>
+</p><h3>Parameters 参数</h3>
IN: <tt>const Graph& g</tt>
-<blockquote>
-An undirected graph. The graph type must be a model of
-<a href="VertexAndEdgeListGraph.html">Vertex and Edge List Graph</a> and
-<a href="IncidenceGraph.html">Incidence Graph</a>.<br>
+<blockquote>一个无向图。图的类型必须符合
+<a href="VertexAndEdgeListGraph.html">点边列表图Vertex and Edge List
Graph</a> 和
+<a href="IncidenceGraph.html">关联图Incidence Graph</a>。<br>
</blockquote>
IN: <tt>VertexIndexMap vm</tt>
-<blockquote>
-Must be a model of <a
href="../../property_map/ReadablePropertyMap.html">ReadablePropertyMap</a>,
mapping vertices to integer indices.
+<blockquote>必须符合 <a
href="../../property_map/ReadablePropertyMap.html">可读属性映射</a>，从顶点
映射至整数索引。
</blockquote>
OUT: <tt>MateMap mate</tt>
-<blockquote>
-Must be a model of <a
href="../../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>,
mapping
-vertices to vertices. For any vertex v in the graph, <tt>get(mate,v)</tt>
will be the vertex that v is matched to, or
-<tt>graph_traits<Graph>::null_vertex()</tt> if v isn't matched.
+<blockquote>必须符合 <a
href="../../property_map/ReadWritePropertyMap.html">读写属性映射</a>，从顶点
映射至顶点。对于图中任一顶点 v，<tt>get(mate,v)</tt> 为 v 所匹配的顶点，或
+<tt>graph_traits<graph>::null_vertex()</graph></tt> 如果 v 未被匹配。
</blockquote>
-<h3>Complexity</h3>
-
-<p>
-Let <i>m</i> and <i>n</i> be the number of edges and vertices in the input
graph, respectively. Assuming the
-<tt>VertexIndexMap</tt> supplied allows constant-time lookups, the time
complexity for both
-<tt>edmonds_matching</tt> and <tt>checked_edmonds_matching</tt> is <i>O(mn
alpha(m,n))</i>.
-<i>alpha(m,n)</i> is a slow growing function that is at most 4 for any
feasible input.
+<h3>Complexity 复杂度</h3>
+
+<p>令 <i>m</i> 和 <i>n</i> 分别为输入图的边数和顶点数。假定
+<tt>VertexIndexMap</tt> 提供常量时间的查找，则
+<tt>edmonds_matching</tt> 和 <tt>checked_edmonds_matching</tt> 的时间复杂度
均为 <i>O(mn alpha(m,n))</i>。<i>alpha(m,n)</i> 是一个慢速增长的函数，对于所
有可能的输入，至多为4。
</p><p>
-</p><h3>Example</h3>
-
-<p> The file <a
href="../example/matching_example.cpp"><tt>example/matching_example.cpp</tt></a>
-contains an example.
-
-<br>
+</p><h3>Example 示例</h3>
+
+<p>文件 <a
href="../example/matching_example.cpp"><tt>example/matching_example.cpp</tt></a>
+包含了一个例子。<br>
</p><hr>
<table>
<tbody><tr valign="top">
=======================================
--- /trunk/libs/graph/doc/prim_minimum_spanning_tree.html Mon Mar 30
07:58:04 2009
+++ /trunk/libs/graph/doc/prim_minimum_spanning_tree.html Fri Aug 7
19:42:01 2009
@@ -1,35 +1,31 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek 2000
--
-- 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: Prim Minimum Spanning Tree</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>
+<title>Boost Graph Library: Prim Minimum Spanning Tree</title></head>
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+
+<br clear="">
-<H1><A NAME="sec:prim"></A>
-<img src="figs/python.gif" alt="(Python)"/>
-<TT>prim_minimum_spanning_tree</TT>
-</H1>
-
-<P>
-<PRE>
-<i>// named parameter version</i>
+<h1><a name="sec:prim"></a>
+<img src="figs/python.gif" alt="(Python)">
+<tt>prim_minimum_spanning_tree</tt>
+</h1>
+
+<p>
+</p><pre><i>// 命名参数版本</i>
template <class Graph, class PredMap, class P, class T, class R>
void prim_minimum_spanning_tree(const Graph& g, PredMap p_map,
const bgl_named_params<P, T, R>& params)
-<i>// non-named parameter version</i>
+<i>// 非命名参数版本</i>
template <class Graph, class DijkstraVisitor,
class PredecessorMap, class DistanceMap,
class WeightMap, class IndexMap>
@@ -37,252 +33,136 @@
typename graph_traits<Graph>::vertex_descriptor s,
PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
IndexMap index_map, DijkstraVisitor vis)
-</PRE>
-
-<P>
-This is Prim's algorithm [<A
-HREF="bibliography.html#prim57:_short">25</A>,<A
-HREF="bibliography.html#clr90">8</A>,<A
-HREF="bibliography.html#tarjan83:_data_struct_network_algo">27</A>,<A
-HREF="bibliography.html#graham85">15</A>] for solving the minimum
-spanning tree problem for an undirected graph with weighted edges. A
-MST is a set of edges that connects all the vertices in the graph
-where the total weight of the edges in the tree is minimized. See
-Section <A
-HREF="graph_theory_review.html#sec:minimum-spanning-tree">Minimum
-Spanning Tree Problem</A> for more details. The implementation is
-simply a call to <a
-href="./dijkstra_shortest_paths.html"><TT>dijkstra_shortest_paths()</TT></a>
-with the appropriate choice of comparison and combine functors.
-The pseudo-code for Prim's algorithm is listed below.
+</pre>
+
+<p>这个是 Prim 算法[<a href="bibliography.html#prim57:_short">25</a>,<a
href="bibliography.html#clr90">8</a>,<a
href="bibliography.html#tarjan83:_data_struct_network_algo">27</a>,<a
href="bibliography.html#graham85">15</a>]，用于解决有权边无向图的最小生成树
问题。MST是一个边集，其中的边连接了图中所有顶点，且树中各边的权重之和为最小
化。更多细节，请见 <a
href="graph_theory_review.html#sec:minimum-spanning-tree">最小生成树问题
</a>。本实现只是以适当选择的比较和合并仿函数调用 <a
href="./dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths()</tt></a>。
Prim 算法的伪代码列出如下。
</p>
<table>
-<tr>
+<tbody><tr>
<td valign="top">
-<pre>
-PRIM-MST(<i>G</i>, <i>s</i>, <i>w</i>)
- <b>for</b> each vertex <i>u</i> <i>in</i> <i>V[G]</i>
- <i>color[u] :=</i> WHITE
- <i>d[u] :=</i> <i>infinity</i>
- <i>color[s] :=</i> GRAY
- <i>d[s] := 0</i>
- ENQUEUE(<i>PQ</i>, <i>s</i>)
- <i>p[s] := s</i>
- <b>while</b> (<i>PQ != Ø</i>)
- <i>u :=</i> DEQUEUE(<i>PQ</i>)
- <b>for</b> each <i>v in Adj[u]</i>
- <b>if</b> (<i>w(u,v) < d[v]</i>)
- <i>d[v] := w(u,v)</i>
- <i>p[v] := u</i>
- <b>if</b> (<i>color[v] = </i> WHITE)
- ENQUEUE(<i>PQ</i>, <i>v</i>)
- <i>color[v] :=</i> GRAY
- <b>else if</b> (<i>color[v] = </i> GRAY)
- UPDATE(<i>PQ</i>, <i>v</i>)
- <b>else</b>
- do nothing
- <b>end for</b>
- <i>color[u] :=</i> BLACK
- <b>end while</b>
- <b>return</b> (<i>p</i>, <i>d</i>)
-</pre>
+<pre>PRIM-MST(<i>G</i>, <i>s</i>, <i>w</i>)<br> <b>for</b> each vertex
<i>u</i> <i>in</i> <i>V[G]</i> <br> <i>color[u] :=</i> WHITE<br>
<i>d[u] :=</i> <i>infinity</i> <br> <i>color[s] :=</i> GRAY<br>
<i>d[s] := 0</i> <br> ENQUEUE(<i>PQ</i>, <i>s</i>) <br> <i>p[s] := s</i>
<br> <b>while</b> (<i>PQ != Ø</i>) <br> <i>u :=</i>
DEQUEUE(<i>PQ</i>)<br> <b>for</b> each <i>v in Adj[u]</i> <br>
<b>if</b> (<i>w(u,v) < d[v]</i>)<br> <i>d[v] := w(u,v)</i>
+ <i>p[v] := u</i> <br> <b>if</b> (<i>color[v] = </i> WHITE)
<br> ENQUEUE(<i>PQ</i>, <i>v</i>) <br> <i>color[v] :=</i>
GRAY <br> <b>else if</b> (<i>color[v] = </i> GRAY) <br>
UPDATE(<i>PQ</i>, <i>v</i>) <br> <b>else</b> <br> do
nothing<br> <b>end for</b>
+ <i>color[u] :=</i> BLACK<br> <b>end while</b>
+ <b>return</b> (<i>p</i>, <i>d</i>)<br></pre>
</td>
<td valign="top">
-<pre>
-
-initialize vertex <i>u</i>
+<pre>初始化顶点 <i>u</i>
+
-
-start vertex <i>s</i>
-discover vertex <i>s</i>
+开始顶点 <i>s</i>
+发现顶点 <i>s</i> <br><br><br>检查顶点 <i>u</i>
+检查边 <i>(u,v)</i> <br><br>边 <i>(u,v)</i> 被松驰<br><br><br>发现顶点
<i>v</i>
+
-examine vertex <i>u</i>
-examining edge <i>(u,v)</i>
-
-edge <i>(u,v)</i> relaxed
-
-
-discover vertex <i>v</i>
-
-
-
-
-edge <i>(u,v)</i> not relaxed
-
-finish <i>u</i>
+
+边 <i>(u,v)</i> 未被松驰<br><br>结束顶点 <i>u</i>
</pre>
-</tr>
-</table>
+</td></tr>
+</tbody></table>
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/prim_minimum_spanning_tree.hpp"><TT>boost/graph/prim_minimum_spanning_tree.hpp</TT></a>
-
-<P>
-
-<h3>Parameters</h3>
+<h3>Where Defined 定义于</h3>
+
+<p>
+<a
href="../../../boost/graph/prim_minimum_spanning_tree.hpp"><tt>boost/graph/prim_minimum_spanning_tree.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Parameters 参数</h3>
IN: <tt>const Graph& g</tt>
-<blockquote>
- An undirected graph. The type <tt>Graph</tt> must be a
- model of <a href="./VertexListGraph.html">Vertex List Graph</a>
- and <a href="./IncidenceGraph.html">Incidence Graph</a>.<br>
-
- <b>Python</b>: The parameter is named <tt>graph</tt>.
+<blockquote>一个无向图。类型 <tt>Graph</tt> 必须符合 <a
href="./VertexListGraph.html">点列表图Vertex List Graph</a> 和 <a
href="./IncidenceGraph.html">关联图Incidence Graph</a>。<br>
+
+ <b>Python</b>: 该参数名为 <tt>graph</tt>.
</blockquote>
OUT: <tt>PredecessorMap p_map</tt>
-<blockquote>
- The predecessor map records the edges in the minimum spanning
- tree. Upon completion of the algorithm, the edges
- <i>(p[u],u)</i> for all <i>u in V</i> are in the minimum spanning
- tree. If <i>p[u] = u</i> then <i>u</i> is either the root of the
- tree or is a vertex that is not reachable from the root.
- The <tt>PredecessorMap</tt> type must be a <a
- href="../../property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a>
- with key and vertex types the same as the vertex descriptor type
- of the graph.<br>
-
- <b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br>
+<blockquote>前趋映射记录了最小生成树中的边。在算法结束时，对于<i> V</i> 中
的所有 <i>u</i>，边
+ <i>(p[u],u)</i> 属于最小生成树。如果 <i>p[u] = u</i>，则 <i>u</i> 为树的
根，或为不能从根到达的顶点。类型 <tt>PredecessorMap</tt> 必须是一个 <a
href="../../property_map/ReadWritePropertyMap.html">读/写属性映射</a>，其键
类型及值类型均与图的顶点描述符类型相同。<br>
+
+ <b>Python</b>: 必须是该图的一个 <tt>vertex_vertex_map</tt>。<br>
</blockquote>
-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>
IN: <tt>root_vertex(vertex_descriptor r)</tt>
-<blockquote>
- The vertex that will be the root of the minimum spanning tree.
- The choice of the root vertex is arbitrary.<br>
- <b>Default:</b> <tt>*vertices(g).first</tt>
+<blockquote>作为最小生成树根的顶点。根顶点的选择是任意的。<br>
+ <b>缺省值：</b><tt>*vertices(g).first</tt>
</blockquote>
IN: <tt>weight_map(WeightMap w_map)</tt>
-<blockquote>
- The weight or ``length'' of each edge in the graph.
- The type <tt>WeightMap</tt> must be a model of
- <a href="../../property_map/ReadablePropertyMap.html">Readable Property
Map</a>. The edge descriptor type of
- the graph needs to be usable as the key type for the weight
- map. The value type for the map must be
- <i>Addable</i> with the value type of the distance map.<br>
- <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
- <b>Python</b>: Must be an <tt>edge_double_map</tt> for the graph.<br>
- <b>Python default</b>: <tt>graph.get_edge_double_map("weight")</tt>
+<blockquote>图中每条边的权重或"长度"。类型 <tt>WeightMap</tt> 必须符合
+ <a
href="http://alai04.kmip.net/boost_doc/libs/property_map/ReadablePropertyMap.html";>可
读属性映射</a>。图的边描述符必须可用作权重映射的键类型。该映射的值类型必须可
以与距离映射的值类型相加。<br>
+ <b>缺省值：</b><tt>get(edge_weight, g)</tt><br>
+
+ <b>Python</b>: 必须为该图的一个 <tt>edge_double_map</tt>。<br>
+ <b>Python 缺省值：</b><tt>graph.get_edge_double_map("weight")</tt>
</blockquote>
IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
-<blockquote>
- This maps each vertex to an integer in the range <tt>[0,
- num_vertices(g))</tt>. This is necessary for efficient updates of the
- heap data structure when an edge is relaxed. The type
- <tt>VertexIndexMap</tt> must be a model of
- <a href="../../property_map/ReadablePropertyMap.html">Readable Property
Map</a>. The value type of the map must be an
- integer type. The vertex descriptor type of the graph needs to be
- usable as the key type of the map.<br>
- <b>Default:</b> <tt>get(vertex_index, g)</tt>
- Note: if you use this default, make sure your graph has
- an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
- not have an internal <tt>vertex_index</tt> property.
- <br>
- <b>Python</b>: Unsupported parameter.
+<blockquote>它将每个顶点映射至位于区间 <tt>[0,
+ num_vertices(g))</tt> 中的一个整数。为了在对边进行松驰时可以高效地访问堆
数据结构，需要此映射。类型 <tt>VertexIndexMap</tt>
+ 必须符合 <a
href="http://alai04.kmip.net/boost_doc/libs/property_map/ReadablePropertyMap.html";>可
读属性映射</a>。该映射的值类型必须是一个整数类型。图的顶点描述符类型需要可以
被用作该映射的键类型。<br>
+
+
+ <b>缺省值：</b><tt>get(vertex_index, g)</tt>.
+ 注意：如果你使用该缺省值，请确认你的图具有一个内部的
<tt>vertex_index</tt> 属性。例如，带 <tt>VertexList=listS</tt> 的
+ <tt>adjacenty_list</tt> 并不具有内部的 <tt>vertex_index</tt> 属性。<br>
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
UTIL/OUT: <tt>distance_map(DistanceMap d_map)</tt>
-<blockquote>
- The shortest path weight from the source vertex <tt>s</tt> to each
- vertex in the graph <tt>g</tt> is recorded in this property map. The
- shortest path weight is the sum of the edge weights along the
- shortest path. The type <tt>DistanceMap</tt> must be a model of
- <a
- href="../../property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a>. The vertex descriptor type of the
- graph needs to be usable as the key type of the distance map. The
- value type of the distance map must be <a
- href="http://www.sgi.com/tech/stl/LessThanComparable.html";>Less Than
- Comparable</a>.<br>
- <b>Default:</b> <a href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
- <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
- map.<br>
-
- <b>Python</b>: Must be a <tt>vertex_double_map</tt> for the graph.<br>
+<blockquote>从源顶点 <tt>s</tt> 到图 <tt>g</tt> 中每个顶点的最短路径权重被
记录在这个属性映射中。最短路径权重为最短路径上各边权重之和。类型
<tt>DistanceMap</tt> 必须符合 <a
href="../../property_map/ReadWritePropertyMap.html">读/写属性映射</a>。图的
顶点描述符类型必须可被用作这个距离映射的键类型。距离映射的值类型必须是 <a
href="http://www.sgi.com/tech/stl/LessThanComparable.html";>可小于比较</a>
的。<br>
+ <b>缺省值：</b><a
href="../../property_map/iterator_property_map.html"><tt>iterator_property_map</tt></a>
创建自一个值类型为 <tt>WeightMap</tt>，大小为
+ <tt>num_vertices(g)</tt> 的
+ <tt>std::vector</tt><span style="font-family: monospace;">，</span>且以
<tt>i_map</tt> 作为索引映射。<br>
+
+ <b>Python</b>: 必须为该图的一个 <tt>vertex_double_map</tt>。<br>
</blockquote>
UTIL/OUT: <tt>color_map(ColorMap c_map)</tt>
-<blockquote>
- This is used during the execution of the algorithm to mark the
- vertices. The vertices start out white and become gray when they are
- inserted in the queue. They then turn black when they are removed
- from the queue. At the end of the algorithm, vertices reachable from
- the source vertex will have been colored black. All other vertices
- will still be white. The type <tt>ColorMap</tt> must be a model of
- <a href="../../property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a>. A vertex descriptor must be usable as the key type
- of the map, and the value type of the map must be a model of
- <a href="./ColorValue.html">Color Value</a>.<br>
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
- of <tt>default_color_type</tt> of size <tt>num_vertices(g)</tt> and
- using the <tt>i_map</tt> for the index map.<br>
-
- <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for
- the graph.
+<blockquote>用于在算法的执行期间对顶点进行标记。各顶点在开始时为白色，当被
插入队列时变为灰色。当被从队列中移出时变为黑色。在算法结束时，可以从源顶点到
达的所有顶点均变为黑色。其它所有顶点仍为白色。类型 <tt>ColorMap</tt> 必须符
合
+ <a href="../../property_map/ReadWritePropertyMap.html">读/写属性映射
</a>。顶点描述符必须可被用作该映射的键类型，且该映射的值类型必须符合
+ <a href="ColorValue.html">颜色值Color Value</a>。<br>
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a>，创建自一个大小为
<tt>num_vertices(g)</tt> 的 <tt>default_color_type</tt> 的
<tt>std::vector</tt>，且以 <tt>i_map</tt> 作为索引映射。<br>
+
+ <b>Python</b>: 颜色映射必须是该图的一个 <tt>vertex_color_map</tt>。
</blockquote>
OUT: <tt>visitor(DijkstraVisitor v)</tt>
-<blockquote>
- Use this to specify actions that you would like to happen
- during certain event points within the algorithm.
- The type <tt>DijkstraVisitor</tt> must be a model of the
- <a href="./DijkstraVisitor.html">Dijkstra Visitor</a> concept.
- The visitor object is passed by value <a
- href="#1">[1]</a>.<br>
- <b>Default:</b> <tt>dijkstra_visitor<null_visitor></tt><br>
-
- <b>Python</b>: The parameter should be an object that derives from
- the <a
- href="DijkstraVisitor.html#python"><tt>DijkstraVisitor</tt></a> type
- of the graph.
+<blockquote>用于指定你想在算法内某些特定事件点上执行的动作。类型
<tt>DijkstraVisitor</tt> 必须符合
+ <a href="DijkstraVisitor.html">Dijkstra 遍历器</a> 概念。该遍历器对象是以
值方式传递的<a href="prim_minimum_spanning_tree.html#1">[1]</a>。<br>
+ <b>缺省值：</b><tt>dijkstra_visitor<null_visitor></tt><br>
+
+ <b>Python</b>: 该参数应为派生自该图的 <a
href="DijkstraVisitor.html#python"><tt>DijkstraVisitor</tt></a> 类型的一个对
象。
</blockquote>
-<H3>Complexity</H3>
-
-<P>
-The time complexity is <i>O(E log V)</i>.
-
-<P>
-
-<H3>Example</H3>
-
-<P>
-The file <a
-href="../example/prim-example.cpp"><TT>examples/prim-example.cpp</TT></a>
-contains an example of using Prim's algorithm.
+<h3>Complexity 复杂度</h3>
+
+<p>时间复杂度为 <i>O(E log V)</i>.
+
+</p><p>
+
+</p><h3>Example 示例</h3>
+
+<p>文件 <a
href="../example/prim-example.cpp"><tt>examples/prim-example.cpp</tt></a>
+包含了使用 Prim 算法的一个例子。
-<h3>Notes</h3>
+</p><h3>Notes 备注</h3>
<p><a name="1">[1]</a>
- Since the visitor parameter is passed by value, if your visitor
- contains state then any changes to the state during the algorithm
- will be made to a copy of the visitor object, not the visitor object
- passed in. Therefore you may want the visitor to hold this state by
- pointer or reference.
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+ 由于 visitor 参数是以值方式传递的，所以如果你的遍历器含有状态，则在算法中
对该状态的所有修改都是针对该遍历器对象的一个拷贝，而不对传入的遍历器对象进行
的。因此你应该让该遍历器以指针或引用的方式保存该状态。<br>
+</p><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright © 2000-2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,
Indiana University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
+
+</body></html>
=======================================
--- /trunk/libs/graph/doc/push_relabel_max_flow.html Mon Mar 30 07:58:04
2009
+++ /trunk/libs/graph/doc/push_relabel_max_flow.html Fri Aug 7 19:42:01
2009
@@ -1,35 +1,30 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek 2000
--
-- 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: Push-Relabel Maximum Flow</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><A NAME="sec:push_relabel_max_flow">
-<TT>push_relabel_max_flow</TT>
-</H1>
-
-<P>
-<PRE>
-<i>// named parameter version</i>
+<title>Boost Graph Library: Push-Relabel Maximum Flow</title></head>
+
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+
+<br clear="">
+
+<h1><a name="sec:push_relabel_max_flow">
+<tt>push_relabel_max_flow</tt>
+</a></h1>
+
+<p>
+</p><pre><a name="sec:push_relabel_max_flow"><i>// 命名参数版本</i>
template <class Graph, class P, class T, class R>
typename property_traits<CapacityEdgeMap>::value_type
push_relabel_max_flow(Graph& g,
typename graph_traits<Graph>::vertex_descriptor src,
typename graph_traits<Graph>::vertex_descriptor sink,
- const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
-
-<i>// non-named parameter version</i>
+ const bgl_named_params<P, T, R>& params = <i>all
defaults</i>)<br><br><i>// 非命名参数版本</i>
template <class Graph,
class CapacityEdgeMap, class ResidualCapacityEdgeMap,
class ReverseEdgeMap, class VertexIndexMap>
@@ -39,205 +34,89 @@
typename graph_traits<Graph>::vertex_descriptor sink,
CapacityEdgeMap cap, ResidualCapacityEdgeMap res,
ReverseEdgeMap rev, VertexIndexMap index_map)
-</PRE>
-
-<P>
-The <tt>push_relabel_max_flow()</tt> function calculates the maximum flow
-of a network. See Section <a
-href="./graph_theory_review.html#sec:network-flow-algorithms">Network
-Flow Algorithms</a> for a description of maximum flow. The calculated
-maximum flow will be the return value of the function. The function
-also calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in
-<i>E</i>, which are returned in the form of the residual capacity
-<i>r(u,v) = c(u,v) - f(u,v)</i>.
+</a></pre>
<p>
-There are several special requirements on the input graph and property
-map parameters for this algorithm. First, the directed graph
-<i>G=(V,E)</i> that represents the network must be augmented to
-include the reverse edge for every edge in <i>E</i>. That is, the
-input graph should be <i>G<sub>in</sub> = (V,{E U
-E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
-must map each edge in the original graph to its reverse edge, that is
-<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>. The
-<tt>CapacityEdgeMap</tt> argument <tt>cap</tt> must map each edge in
-<i>E</i> to a positive number, and each edge in <i>E<sup>T</sup></i>
-to 0.
-
-<p>
-This algorithm was developed by <a
-href="./bibliography.html#goldberg85:_new_max_flow_algor">Goldberg</a>.
+<a name="sec:push_relabel_max_flow">函数 <tt>push_relabel_max_flow()</tt>
计算一个网络的最大流。关于最大流的描述，请见 </a><a
href="graph_theory_review.html#sec:network-flow-algorithms">网络流算法</a>
一节。该函数的返回值即为计算所得的最大流。该函数还针对
+<i>E</i> 中所有 <i>(u,v)</i> 计算了流值 <i>f(u,v)</i>，它以残留容量
+<i>r(u,v) = c(u,v) - f(u,v)</i> 的形式来返回。
+
+</p><p>本算法的输入图及属性映射参数有几个特别的要求。首先，表示本网络的有向
图
+<i>G=(V,E)</i> 必须被扩展，对于 <i>E</i> 中的每条边，增加相应的反向边。
即，输入图应为 <i>G<sub>in</sub> = (V,{E U
+E<sup>T</sup>})</i>。<tt>ReverseEdgeMap</tt> 参数 <tt>rev</tt>
+必须将原图中的每条边映射至它的反向边，即对于 <i>E</i> 中的所有
<i>(u,v)</i>，<i>(u,v) -> (v,u)</i>。<tt>CapacityEdgeMap</tt> 参数
<tt>cap</tt> 必须将
+<i>E</i> 中的每条边映射至一个正数，而 <i>E<sup>T</sup></i>
+中的每条边则映射至 0。<br></p><p>该算法由 <a
href="./bibliography.html#goldberg85:_new_max_flow_algor">Goldberg</a> 开
发。
-<H3>Complexity</H3>
-
-The time complexity is <i>O(V<sup>3</sup>)</i>.
-
-
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/push_relabel_max_flow.hpp"><TT>boost/graph/preflow_push_max_flow.hpp</TT></a>
-
-<P>
-
-<h3>Parameters</h3>
+</p><h3>Complexity 复杂度</h3>时间复杂度为 <i>O(V<sup>3</sup>)</i>.
+
+
+<h3>Where Defined 定义于</h3>
+
+<p>
+<a
href="../../../boost/graph/push_relabel_max_flow.hpp"><tt>boost/graph/preflow_push_max_flow.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Parameters 参数</h3>
IN: <tt>VertexListGraph& g</tt>
-<blockquote>
- A directed graph. The
- graph's type must be a model of <a
- href="./VertexListGraph.html">Vertex List Graph</a>. For each edge
- <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
- be in the graph.
+<blockquote>一个有向图。图的类型必须符合 <a href="VertexListGraph.html">点
列表图VertexListGraph</a>。对于图中的每条边 <i>(u,v)</i>，反向边
<i>(v,u)</i> 必须也在图中。
</blockquote>
IN: <tt>vertex_descriptor src</tt>
-<blockquote>
- The source vertex for the flow network graph.
+<blockquote>流网络图的源顶点。
</blockquote>
IN: <tt>vertex_descriptor sink</tt>
-<blockquote>
- The sink vertex for the flow network graph.
+<blockquote>流网络图的汇顶点。
</blockquote>
-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>
IN: <tt>capacity_map(EdgeCapacityMap cap)</tt>
-<blockquote>
- The edge capacity property map. The type must be a model of a
- constant <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property
Map</a>. The
- key type of the map must be the graph's edge descriptor type.<br>
- <b>Default:</b> <tt>get(edge_capacity, g)</tt>
+<blockquote>边容量属性映射。该类型必须是一个常性的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。该映射的
键类型必须是该图的边描述符类型。<br>
+ <b>缺省值：</b><tt>get(edge_capacity, g)</tt><tt><br></tt>
</blockquote>
OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
-<blockquote>
- The edge residual capacity property map. The type must be a model of
- a mutable <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property
Map</a>. The
- key type of the map must be the graph's edge descriptor type.<br>
- <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt>
+<blockquote>将边映射至它的残留容量。该类型必须是一个可变的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。该映射的
键类型必须是该图的边描述符类型。<br>
+ <b>缺省值：</b><tt>get(edge_residual_capacity, g)<br></tt><tt></tt>
</blockquote>
IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
-<blockquote>
- An edge property map that maps every edge <i>(u,v)</i> in the graph
- to the reverse edge <i>(v,u)</i>. The map must be a model of
- constant <a
- href="../../property_map/LvaluePropertyMap.html">Lvalue Property
Map</a>. The
- key type of the map must be the graph's edge descriptor type.<br>
- <b>Default:</b> <tt>get(edge_reverse, g)</tt>
+<blockquote>一个边属性映射，将图中每条边 <i>(u,v)</i> 映射至反向边
<i>(v,u)</i>。该映射必须是一个常性的 <a
href="../../property_map/LvaluePropertyMap.html">左值属性映射</a>。该映射的
键类型必须是图的边描述符类型。<br>
+ <b>缺省值：</b><tt>get(edge_reverse, g)</tt><tt></tt>
</blockquote>
IN: <tt>vertex_index_map(VertexIndexMap index_map)</tt>
-<blockquote>
- Maps each vertex of the graph to a unique integer in the range
- <tt>[0, num_vertices(g))</tt>. The map must be a model of constant <a
- href="../../property_map/LvaluePropertyMap.html">LvaluePropertyMap</a>.
The
- key type of the map must be the graph's vertex descriptor type.<br>
- <b>Default:</b> <tt>get(vertex_index, g)</tt>
- Note: if you use this default, make sure your graph has
- an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
- not have an internal <tt>vertex_index</tt> property.
- <br>
+<blockquote>将图中每个顶点映射至 <tt>[0, num_vertices(g))</tt> 区间中的一个
整数。该属性映射仅当颜色映射或前趋映射使用缺省值时需要。该顶点索引映射必须符
合 <a href="../../property_map/ReadablePropertyMap.html">可读属性映射</a>。
该映射的键类型必须是图的顶点描述符类型。<br>
+ <b>缺省值：</b><tt>get(vertex_index, g)</tt>
+ 注意：如果你使用该缺省值，请确认你的图具有一个内部的
<tt>vertex_index</tt> 属性。例如，带 <tt>VertexList=listS</tt> 的
+ <tt>adjacenty_list</tt> 并不具有内部的 <tt>vertex_index</tt> 属性。
+<br>
</blockquote>
-<h3>Example</h3>
-
-This reads in an example maximum flow problem (a graph with edge
-capacities) from a file in the DIMACS format. The source for this
-example can be found in <a
-href="../example/max_flow.cpp"><tt>example/max_flow.cpp</tt></a>.
-
-<pre>
-#include <boost/config.hpp>
-#include <iostream>
-#include <string>
-#include <boost/graph/push_relabel_map_flow.hpp>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/read_dimacs.hpp>
-
-int
-main()
-{
- using namespace boost;
-
- typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
- typedef adjacency_list<vecS, vecS, directedS,
- property<vertex_name_t, std::string>,
- property<edge_capacity_t, long,
- property<edge_residual_capacity_t, long,
- property<edge_reverse_t, Traits::edge_descriptor> > >
- > Graph;
-
- Graph g;
- long flow;
-
- property_map<Graph, edge_capacity_t>::type
- capacity = get(edge_capacity, g);
- property_map<Graph, edge_reverse_t>::type
- rev = get(edge_reverse, g);
- property_map<Graph, edge_residual_capacity_t>::type
- residual_capacity = get(edge_residual_capacity, g);
-
- Traits::vertex_descriptor s, t;
- read_dimacs_max_flow(g, capacity, rev, s, t);
-
- flow = push_relabel_max_flow(g, s, t);
-
- std::cout << "c The total flow:" << std::endl;
- std::cout << "s " << flow << std::endl <<
std::endl;
-
- std::cout << "c flow values:" << std::endl;
- graph_traits<Graph>::vertex_iterator u_iter, u_end;
- graph_traits<Graph>::out_edge_iterator ei, e_end;
- for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
- for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
- if (capacity[*ei] > 0)
- std::cout << "f " << *u_iter << " " <<
target(*ei, g) << " "
- << (capacity[*ei] - residual_capacity[*ei])
<< std::endl;
- return 0;
-}
-</pre>
-The output is:
-<pre>
-c The total flow:
-s 4
-
-c flow values:
-f 0 1 4
-f 1 2 4
-f 2 3 2
-f 2 4 2
-f 3 1 0
-f 3 6 2
-f 4 5 3
-f 5 6 0
-f 5 7 3
-f 6 4 1
-f 6 7 1
-</pre>
-
-<h3>See Also</h3>
+<h3>Example 示例</h3>该例子从一个DIMACS格式的文件中读入一个最大流问题(一个
带有边容量的图)。该例子的源码可在 <a
href="../example/max_flow.cpp"><tt>example/max_flow.cpp</tt></a> 中找到。
+
+<pre>#include <boost/config.hpp><br>#include
<iostream><br>#include <string><br>#include
<boost/graph/push_relabel_map_flow.hpp><br>#include
<boost/graph/adjacency_list.hpp><br>#include
<boost/graph/read_dimacs.hpp><br><br>int<br>main()<br>{<br> using
namespace boost;<br><br> typedef adjacency_list_traits<vecS, vecS,
directedS> Traits;<br> typedef adjacency_list<vecS, vecS, directedS,
<br> property<vertex_name_t, std::string>,<br>
property<edge_capacity_t, long,<br>
property<edge_residual_capacity_t, long,<br> property<edge_reverse_t,
Traits::edge_descriptor> > ><br> > Graph;<br><br> Graph
g;<br> long flow;<br><br> property_map<Graph,
edge_capacity_t>::type <br> capacity = get(edge_capacity, g);<br>
property_map<Graph, edge_reverse_t>::type <br> rev =
get(edge_reverse, g);<br> property_map<Graph,
edge_residual_capacity_t>::type <br> residual_capacity =
get(edge_residual_capacity, g);<br><br> Traits::vertex_descriptor s,
t;<br> read_dimacs_max_flow(g, capacity, rev, s, t);<br><br> flow =
push_relabel_max_flow(g, s, t);<br><br> std::cout << "c The total
flow:" << std::endl;<br> std::cout << "s " << flow
<< std::endl << std::endl;<br><br> std::cout << "c flow
values:" << std::endl;<br>
graph_traits<Graph>::vertex_iterator u_iter, u_end;<br>
graph_traits<Graph>::out_edge_iterator ei, e_end;<br> for
(tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)<br> for
(tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)<br> if
(capacity[*ei] > 0)<br> std::cout << "f " << *u_iter
<< " " << target(*ei, g) << " " <br>
<< (capacity[*ei] - residual_capacity[*ei]) << std::endl;<br>
return 0;<br>}<br></pre>输出如下：
+<pre>c The total flow:<br>s 4<br><br>c flow values:<br>f 0 1 4<br>f 1 2
4<br>f 2 3 2<br>f 2 4 2<br>f 3 1 0<br>f 3 6 2<br>f 4 5 3<br>f 5 6 0<br>f 5
7 3<br>f 6 4 1<br>f 6 7 1<br></pre>
+
+<h3>See Also 参见</h3>
<a
href="./edmonds_karp_max_flow.html"><tt>edmonds_karp_max_flow()</tt></a><br>
<a href="./kolmogorov_max_flow.html"><tt>kolmogorov_max_flow()</tt></a>.
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+<hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright © 2000-2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,
Indiana University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
+
<!-- LocalWords: HTML Siek BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
preflow
-->
<!-- LocalWords: gif ALT BR sec TT DIV CELLPADDING TR TD PRE lt
@@ -254,3 +133,4 @@
-->
<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu
-->
+</body></html>
=======================================
--- /trunk/libs/graph/doc/strong_components.html Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/strong_components.html Fri Aug 7 19:42:01 2009
@@ -1,201 +1,131 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek 2000
--
-- 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: Strongly Connected Components</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>
+<title>Boost Graph Library: Strongly Connected Components</title></head>
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+
+<br clear="">
-<H1>
-<A NAME="sec:connected-components"></A><A
NAME="sec:strongly-connected-components"></A>
-<img src="figs/python.gif" alt="(Python)"/>
-<TT>strong_components</TT>
-</H1>
-
-<PRE>
-<i>// named parameter version</i>
+<h1>
+<a name="sec:connected-components"></a><a
name="sec:strongly-connected-components"></a>
+<img src="figs/python.gif" alt="(Python)">
+<tt>strong_components</tt>
+</h1>
+
+<pre><i>// 命名参数版本</i>
template <class Graph, class ComponentMap, class P, class T, class R>
typename property_traits<ComponentMap>::value_type
-strong_components(Graph& g, ComponentMap comp,
- const bgl_named_params<P, T, R>& params = <i>all
defaults</i>)
-
-<i>// there is not a non-named parameter version of this function</i>
-</PRE>
-
-<P>
-The <TT>strong_components()</TT> functions compute the strongly
-connected components of a directed graph using Tarjan's algorithm
-based on DFS [<A
-HREF="bibliography.html#tarjan72:dfs_and_linear_algo">41</A>].
+strong_components(Graph& g, ComponentMap comp,
+ const bgl_named_params<P, T, R>& params = <i>all
defaults</i>)<br><br><i>// 该函数没有非命名参数版本</i>
+</pre>
+
+<p>函数 <tt>strong_components()</tt> 使用基于DFS的 Tarjan 算法[<a
href="bibliography.html#tarjan72:dfs_and_linear_algo">41</a>]计算一个有向图
的强连通分支。
</p>
-<P>
-The output of the algorithm is recorded in the component property
-map <TT>comp</TT>, which will contain numbers giving the component ID
-assigned to each vertex. The number of components is the return value
-of the function.
-</p>
-
-<H3>Where Defined</H3>
-
-<P>
-<a
href="../../../boost/graph/strong_components.hpp"><TT>boost/graph/strong_components.hpp</TT></a>
-
-<P>
-
-<H3>Definitions</H3>
-
-<P>
-A <a name="def:strongly-connected-component"><b><I>strongly connected
-component</I></b></a> of a directed graph <i>G=(V,E)</i> is a maximal
-set of vertices <i>U</i> which is in <i>V</i> such that for every pair
-of vertices <i>u</i> and <i>v</i> in <i>U</i>, we have both a path
-from <i>u</i> to <i>v</i> and path from <i>v</i> to <i>u</i>. That is
-to say that <i>u</i> and <i>v</i> are reachable from each other.
-
-<P>
-
-<h3>Parameters</h3>
+<p>该算法的输出被记录在连通分支映射
+<tt>comp</tt> 中，其中将包含赋给各个顶点的分支ID。总的分支数为函数的返回
值。</p><h3>Where Defined 定义于</h3>
+
+<p>
+<a
href="../../../boost/graph/strong_components.hpp"><tt>boost/graph/strong_components.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Definitions 定义</h3>
+
+<p>有向图 <i>G=(V,E)</i> 的 <a
name="def:strongly-connected-component"><b><i>强连通分支</i></b></a> 是
指，<i>V</i> 中的一个最大顶点集 <i>U</i>，满足 <i>U</i> 中的任意一对顶点
<i>u</i> 和 <i>v</i><i></i>，均有从 <i>u</i> 到 <i>v</i> 和从 <i>v</i> 到
<i>u</i> 的路径。即 <i>u</i> 和 <i>v</i> 相互可达。
+
+</p><p>
+
+</p><h3>Parameters 参数</h3>
IN: <tt>const Graph& g</tt>
-<blockquote>
-A directed graph. The graph type must be a model of <a
-href="VertexListGraph.html">Vertex List Graph</a> and <a
-href="IncidenceGraph.html">Incidence Graph</a>.<br>
-
-<b>Python</b>: The parameter is named <tt>graph</tt>.
+<blockquote>一个有向图。图的类型必须符合 <a href="VertexListGraph.html">点
列表图Vertex List Graph</a> 和 <a href="IncidenceGraph.html">关联图
Incidence Graph</a>。<br>
+
+<b>Python</b>: 该参数名为 <tt>graph</tt>.
</blockquote>
OUT: <tt>ComponentMap c</tt>
-<blockquote>
-The algorithm computes how many connected components are in the graph,
-and assigning each component an integer label. The algorithm then
-records which component each vertex in the graph belongs to by
-recording the component number in the component property map. The
-<tt>ComponentMap</tt> type must be a model of <a
-href="../../property_map/WritablePropertyMap.html">Writable Property
-Map</a>. The value type shouch be an integer type, preferably the same
-as the <tt>vertices_size_type</tt> of the graph. The key type must be
-the graph's vertex descriptor type.<br>
-
- <b>Python</b>: Must be an <tt>vertex_int_map</tt> for the graph.<br>
- <b>Python default</b>: <tt>graph.get_vertex_int_map("component")</tt>
+<blockquote>该算法计算在图中有多少连通分支，并赋给每个分支一个整数标签。然
后本算法通过将分支号写入分支属性映射，来记录图中各顶点属于哪个分支。类型
+<tt>ComponentMap</tt> 必须符合 <a
href="../../property_map/WritablePropertyMap.html">可写属性映射</a>。其值类
型应为整数类型，最好与图的 <tt>vertices_size_type</tt> 相同。而键类型必须是
图的顶点描述符类型。<br>
+
+ <b>Python</b>: 必须是该图的一个 <tt>vertex_int_map</tt>。<br>
+ <b>Python 缺省
值：</b><tt>graph.get_vertex_int_map("component")</tt><tt></tt>
</blockquote>
-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>
UTIL: <tt>root_map(RootMap r_map)</tt>
-<blockquote>
- This is used by the algorithm to record the candidate root vertex for
- each vertex. By the end of the algorithm, there is a single root vertex
- for each component and <tt>get(r_map, v)</tt> returns the root
- vertex for whichever component vertex <tt>v</tt> is a member.
- The <TT>RootMap</TT> must be a <a
- href="../../property_map/ReadWritePropertyMap.html">
- Read/Write Property Map</a>, where the key type and the value type are
- the vertex descriptor type of the graph.<br>
-
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of vertex descriptors of size
- <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
- map.<br>
- <b>Python</b>: Unsupported parameter.
+<blockquote>被本算法用于记录每个顶点的候选根。在算法结束时，每个分支有单个
根顶点且 <tt>get(r_map, v)</tt> 会返回顶点 <tt>v</tt> 所属分支的根顶点。
<tt>RootMap</tt> 必须是一个 <a
href="../../property_map/ReadWritePropertyMap.html">
+ 读/写属性映射</a>，其键类型和值类型均为图的顶点描述符。<br>
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a>，创建自一个大小为
<tt>num_vertices(g)</tt> 的顶点描述符 <tt>std::vector</tt>，且以
<tt>i_map</tt> 作为索引映射。<br>
+
+
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
UTIL: <tt>discover_time_map(TimeMap t_map)</tt>
-<blockquote>
- This is used by the algorithm to keep track of the DFS ordering
- of the vertices. The <TT>TimeMap</TT> must be a model
- of <a href="../../property_map/ReadWritePropertyMap.html"> Read/Write
- Property Map</a> and its value type must be an integer type. The key
- type must be the vertex descriptor type of the graph.<br>
- <b>Default:</b>an <a
- href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of integers with size
- <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
- map.<br>
- <b>Python</b>: Unsupported parameter.
+<blockquote>被本算法用于跟踪各顶点的DFS顺序。<tt>TimeMap</tt> 必须符合 <a
href="../../property_map/ReadWritePropertyMap.html"> 读/写属性映射</a> 且其
值类型必须为整数类型。键类型必须为图的顶点描述符类型。<br>
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a>，创建自一个大小为
<tt>num_vertices(g)</tt> 的整数 <tt>std::vector</tt>，且以 <tt>i_map</tt> 作
为索引映射。<br>
+
+
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
UTIL: <tt>color_map(ColorMap c_map)</tt>
-<blockquote>
- This is used by the algorithm to keep track of its progress through
- the graph. The type <tt>ColorMap</tt> must be a model of <a
- href="../../property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a> and its key type must be the graph's vertex
- descriptor type and the value type of the color map must model
- <a href="./ColorValue.html">ColorValue</a>.<br>
- <b>Default:</b> an <a
- href="../../property_map/iterator_property_map.html">
- <tt>iterator_property_map</tt></a> created from a
- <tt>std::vector</tt> of <tt>default_color_type</tt> of size
- <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
- map.<br>
- <b>Python</b>: Unsupported parameter.
+<blockquote>被本算法用于跟踪其处理过程。类型 <tt>ColorMap</tt> 必须符合 <a
href="../../property_map/ReadWritePropertyMap.html">读/写属性映射</a> 且其键
类型必须是图的顶点描述符类型，值类型必须符合
+ <a href="ColorValue.html">颜色值ColorValue</a>。<br>
+
+ <b>缺省值：</b>一个 <a
href="../../property_map/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a>，创建自一个大小为
<tt>num_vertices(g)</tt> 的 <tt>default_color_type</tt> 的
<tt>std::vector</tt>，且以 <tt>i_map</tt> 作为索引映射。<br>
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
-<blockquote>
- This maps each vertex to an integer in the range <tt>[0,
- num_vertices(g))</tt>. This parameter is only necessary when a
- default is used for one of the other named parameters. The type
- <tt>VertexIndexMap</tt> must be a model of <a
- href="../../property_map/ReadablePropertyMap.html">Readable Property
- Map</a>. The value type of the map must be an integer type. The
- vertex descriptor type of the graph needs to be usable as the key
- type of the map.<br>
-
- <b>Default:</b> <tt>get(vertex_index, g)</tt>
- Note: if you use this default, make sure your graph has
- an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
- not have an internal <tt>vertex_index</tt> property.
- <br>
-
- <b>Python</b>: Unsupported parameter.
+<blockquote>它将每个顶点映射至位于区间 <tt>[0,
+ num_vertices(g))</tt> 中的一个整数。仅当使用了缺省的颜色属性映射时需要该
参数。类型 <tt>VertexIndexMap</tt>
+ 必须符合 <a
href="http://alai04.kmip.net/boost_doc/libs/property_map/ReadablePropertyMap.html";>可
读属性映射</a>。该映射的值类型必须是一个整数类型。图的顶点描述符类型需要可以
被用作该映射的键类型。<br>
+
+
+ <b>缺省值：</b><tt>get(vertex_index, g)</tt>.
+ 注意：如果你使用该缺省值，请确认你的图具有一个内部的
<tt>vertex_index</tt> 属性。例如，带 <tt>VertexList=listS</tt> 的
+ <tt>adjacenty_list</tt> 并不具有内部的 <tt>vertex_index</tt> 属性。<br>
+
+ <b>Python</b>: 不支持该参数。
</blockquote>
-<H3>Complexity</H3>
-
-<P>
-The time complexity for the strongly connected components algorithm is
+<h3>Complexity 复杂度</h3>
+
+<p>强连通分支算法的时间复杂度为
<i>O(V + E)</i>.
-<P>
-
-<h3>See Also</h3>
-
-<a href="./connected_components.html"><tt>connected_components()</tt></a>
-and <a
href="./incremental_components.html"><tt>incremental_components()</tt></a>
-
-<H3>Example</H3>
-
-<P>
-See <a
-href="../example/strong_components.cpp"><tt>examples/strong_components.cpp</tt></a>.
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+</p><p>
+
+</p><h3>See Also 参数</h3>
+
+<a href="./connected_components.html"><tt>connected_components()</tt></a>
和 <a
href="./incremental_components.html"><tt>incremental_components()</tt></a>
+
+<h3>Example 示例</h3>
+
+<p>请见 <a
href="../example/strong_components.cpp"><tt>examples/strong_components.cpp</tt></a>。
<br>
+</p><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright © 2000-2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,
Indiana University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
+
+</body></html>
=======================================
--- /trunk/libs/graph/doc/table_of_contents.html Wed Jul 8 07:54:49 2009
+++ /trunk/libs/graph/doc/table_of_contents.html Fri Aug 7 19:42:01 2009
@@ -236,7 +236,7 @@
</li>
<li>Maximum Flow and Matching Algorithms 最大流和最大匹配算法
<ol>
-<li><a
href="./edmunds_karp_max_flow.html"><tt>edmunds_karp_max_flow</tt></a>
+<li><a href="./edmunds_karp_max_flow.html"><tt></tt></a><a
href="edmonds_karp_max_flow.html"><tt>edmonds_karp_max_flow</tt></a>
</li>
<li><a
href="./push_relabel_max_flow.html"><tt>push_relabel_max_flow</tt></a></li>
<li><a
href="kolmogorov_max_flow.html"><tt>kolmogorov_max_flow</tt></a></li>
Other related posts:
- » [boost-doc-zh] r285 committed - graph 库文档第21.3.2-21.3.4节 - codesite-noreply
