[boost-doc-zh] r286 committed - graph 库文档第21.3.5-21.3.15节

  • From: codesite-noreply@xxxxxxxxxx
  • To: boost-doc-zh-notify@xxxxxxxxxxxxx
  • Date: Fri, 14 Aug 2009 05:59:39 +0000

Revision: 286
Author: alai04
Date: Thu Aug 13 22:58:12 2009
Log: graph 库文档第21.3.5-21.3.15节
http://code.google.com/p/boost-doc-zh/source/detail?r=286

Modified:
 /trunk/libs/graph/doc/bandwidth.html
 /trunk/libs/graph/doc/copy_graph.html
 /trunk/libs/graph/doc/cuthill_mckee_ordering.html
 /trunk/libs/graph/doc/isomorphism.html
 /trunk/libs/graph/doc/king_ordering.html
 /trunk/libs/graph/doc/metric_tsp_approx.html
 /trunk/libs/graph/doc/minimum_degree_ordering.html
 /trunk/libs/graph/doc/profile.htm
 /trunk/libs/graph/doc/sequential_vertex_coloring.html
 /trunk/libs/graph/doc/sloan_ordering.htm
 /trunk/libs/graph/doc/sloan_start_end_vertices.htm
 /trunk/libs/graph/doc/topological_sort.html
 /trunk/libs/graph/doc/transitive_closure.html
 /trunk/libs/graph/doc/transpose_graph.html
 /trunk/libs/graph/doc/wavefront.htm

=======================================
--- /trunk/libs/graph/doc/bandwidth.html        Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/bandwidth.html        Thu Aug 13 22:58:12 2009
@@ -1,93 +1,61 @@
-<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: Bandwidth</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:bandwidth">
-<TT>bandwidth</TT>
-</H1>
-
-<pre>
-  (1)
-  template &lt;typename Graph&gt;
-  typename graph_traits&lt;Graph&gt;::vertices_size_type
-  bandwidth(const Graph& g)
-
-  (2)
-  template &lt;typename Graph, typename VertexIndexMap&gt;
-  typename graph_traits&lt;Graph&gt;::vertices_size_type
-  bandwidth(const Graph& g, VertexIndexMap index_map)
-</pre>
-
-The <b><i>bandwidth</i></b> of an undirected graph is the maximum
-distance between two adjacent vertices, with distance measured on a
-line upon which the vertices have been placed at unit intervals. To
-put it another way, if the vertices of an undirected graph
-<i>G=(V,E)</i> are each assigned an index from zero to <i>|V| - 1</i>
-given by <i>index[v]</i>, then the bandwidth of <i>G</i> is<br>
+<title>Boost Graph Library: Bandwidth</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:bandwidth">
+<tt>bandwidth</tt>
+</a></h1>
+
+<pre><a name="sec:bandwidth"> (1)<br> template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> bandwidth(const Graph&amp; g)<br><br> (2)<br> template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> bandwidth(const Graph&amp; g, VertexIndexMap index_map)<br></a></pre>
+
+<a name="sec:bandwidth">一个无向图的 <b><i>带宽bandwidth</i></b> 是指,两个 邻接顶点间的最大距离,这里的距离是通过将所有顶点放在一个单元间隔的直线上来进 行测量的。换句话说,如果一个无向图
+<i>G=(V,E)</i> 的每个顶点被赋予从 0 至 <i>|V| - 1</i>
+的一个整数,由 <i>index[v]</i> 给出,则 <i>G</i> 的带宽为<br>
 <br>
 <i>B(G) = max { |index[u] - index[v]|&nbsp;&nbsp;| (u,v) in E }</i><br>


-<h3>Defined in</h3>
+</a><h3><a name="sec:bandwidth">Defined in 定义于</a></h3>

<a href="../../../boost/graph/bandwidth.hpp"><tt>boost/graph/bandwidth.hpp</tt></a>


 <hr>

-<H1><A NAME="sec:ith-bandwidth">
-<TT>ith_bandwidth</TT>
-</H1>
-
-<pre>
-  (1)
-  template &lt;typename Graph&gt;
-  typename graph_traits&lt;Graph&gt;::vertices_size_type
-  ith_bandwidth(typename graph_traits&lt;Graph&gt;::vertex_descriptor i,
-               const Graph&amp; g)
-
-  (2)
-  template &lt;typename Graph, typename VertexIndexMap&gt;
-  typename graph_traits&lt;Graph&gt;::vertices_size_type
-  ith_bandwidth(typename graph_traits&lt;Graph&gt;::vertex_descriptor i,
-               const Graph&amp; g,
-               VertexIndexMap index)
-</pre>
-
-The <b><i>i-th bandwidth</i></b> a graph is the maximum distance
-between the <i>i-th</i> vertex and any of its neighbors.<br>
+<h1><a name="sec:ith-bandwidth">
+<tt>ith_bandwidth</tt>
+</a></h1>
+
+<pre><a name="sec:ith-bandwidth"> (1)<br> template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> ith_bandwidth(typename graph_traits&lt;Graph&gt;::vertex_descriptor i,<br> const Graph&amp; g)<br><br> (2)<br> template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> ith_bandwidth(typename graph_traits&lt;Graph&gt;::vertex_descriptor i,<br> const Graph&amp; g,<br> VertexIndexMap index)<br></a></pre>
+
+<a name="sec:ith-bandwidth">一个图的 <b><i>第i带宽</i></b> 是指,第<i>i个 </i>顶点与它任一邻接点间的最大距离。<br>
 <br>
<i>B<sub>i</sub>(G) = max { |index[i] - index[j]|&nbsp;&nbsp;| (i,j) in E }</i><br>
-<br>
-So the bandwidth <i>B(G)</i> can be expressed as the maximum
-of the i-th bandwidths <i>B<sub>i</sub>(G)</i>.<br>
+<br>所以,带宽 <i>B(G)</i> 可以表示为 第i带宽 <i>B<sub>i</sub>(G)</i> 的最 大值。<br>
 <br>
 <i>B(G) = max { B<sub>i</sub>(G) &nbsp;&nbsp;| i=0...|V|-1 }</i><br>

-<h3>Defined in</h3>
+</a><h3><a name="sec:ith-bandwidth">Defined in 定义于</a></h3>

<a href="../../../boost/graph/bandwidth.hpp"><tt>boost/graph/bandwidth.hpp</tt></a>

 <br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 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 (c) 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/copy_graph.html       Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/copy_graph.html       Thu Aug 13 22:58:12 2009
@@ -1,116 +1,81 @@
-<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: Copy Graph</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
-        ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
-     ALT="C++ Boost" width="277" height="86">
-
-<BR Clear>
-
-<H1><TT>copy_graph</TT></H1>
-
-<PRE>
-template &lt;class <a href="./VertexListGraph.html">VertexListGraph</a>, class <a href="./MutableGraph.html">MutableGraph</a>&gt;
-void copy_graph(const VertexListGraph&amp; G, MutableGraph&amp; G_copy,
- const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
-</PRE>
-
-This function copies all of the vertices and edges from graph
-<tt>G</tt> into <tt>G_copy</tt>. Also, it copies the vertex and edge
-properties, either by using the <tt>vertex_all</tt> and
-<tt>edge_all</tt> property maps, or by user-supplied copy functions.
-
-<H3>Where Defined</H3>
-
-<P>
-<a href="../../../boost/graph/copy.hpp"><TT>boost/graph/copy.hpp</TT></a>
-
-<P>
-
-<H3>Parameters</H3>
+<title>Boost Graph Library: Copy Graph</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>copy_graph</tt></h1>
+
+<pre>template &lt;class <a href="./VertexListGraph.html">VertexListGraph</a>, class <a href="./MutableGraph.html">MutableGraph</a>&gt; <br>void copy_graph(const VertexListGraph&amp; G, MutableGraph&amp; G_copy,<br> const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)<br></pre>该函数将所有顶点和边从图 +<tt>G</tt> 复制至 <tt>G_copy</tt>。它同时还复制了顶点属性和边属性,使用 <tt>vertex_all</tt> 和
+<tt>edge_all</tt> 属性映射,或是通过用户提供的复制函数。
+
+<h3>Where Defined 定义于</h3>
+
+<p>
+<a href="../../../boost/graph/copy.hpp"><tt>boost/graph/copy.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Parameters 参数</h3>

 IN: <tt>const VertexListGraph&amp; G</tt>
-<blockquote>
-A directed or undirected graph. The graph type must be a model of <a href="./VertexListGraph.html">Vertex List Graph</a>. +<blockquote>一个有向图或无向图。图的类型必须符合 <a href="./VertexListGraph.html">点列表图Vertex List Graph</a>。
 </blockquote>

 OUT: <tt>MutableGraph&amp; G_copy</tt>
-<blockquote>
-The resulting copy of the graph.  The graph type must be a model of <a
-href="./MutableGraph.html">Mutable Graph</a>.
+<blockquote>图的复制结果。图的类型必须符合 <a href="./MutableGraph.html">可 变图Mutable Graph</a>。
 </blockquote>

-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>

 IN: <tt>vertex_copy(VertexCopier vc)</tt>
-<blockquote>
-This is a <a href="http://www.sgi.com/tech/stl/BinaryFunction.html";>Binary Function</a> that copies the properties of a vertex in the original graph
-into the corresponding vertex in the copy.<br>
-
-<b>Default:</b> <tt>vertex_copier&lt;VertexListGraph, MutableGraph&gt;</tt>
-which uses the property tag <tt>vertex_all</tt> to access a property
-map from the graph.
+<blockquote>这是一个 <a href="http://www.sgi.com/tech/stl/BinaryFunction.html";>二元函数</a>,将原图 的顶点属性复制至拷贝中的对应顶点。<br>
+
+<b>缺省值:</b><tt>vertex_copier&lt;VertexListGraph, MutableGraph&gt;</tt>,它使用属性标签 <tt>vertex_all</tt> 来访问图的属性映 射。
 </blockquote>

 IN: <tt>edge_copy(EdgeCopier ec)</tt>
-<blockquote>
-This is a <a href="http://www.sgi.com/tech/stl/BinaryFunction.html";>Binary Function</a> that copies the properties of an edge in the original graph
-into the corresponding edge in the copy.<br>
-
-<b>Default:</b> <tt>edge_copier&lt;VertexListGraph, MutableGraph&gt;</tt>
-which uses the property tag <tt>edge_all</tt> to access a property
-map from the graph.
+<blockquote>这是一个 <a href="http://www.sgi.com/tech/stl/BinaryFunction.html";>二元函数</a>,将原图 的边属性复制至拷贝中的对应边。<br>
+
+<b>缺省值:</b><tt>edge_copier&lt;VertexListGraph, MutableGraph&gt;</tt>,它使用属性标签&nbsp;<tt>edge</tt><tt>_all</tt> 来访问 图的属性映射。
 </blockquote>

 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
-<blockquote>
-The vertex index map type must be a model of <a
-href="../../property_map/ReadablePropertyMap.html">Readable Property
-Map</a> and must map the vertex descriptors of <tt>G</tt> to the
-integers in the half-open range <tt>[0,num_vertices(G))</tt>.<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>顶点索引映射类型必须符合 <a href="../../property_map/ReadablePropertyMap.html">可读属性映射</a>,且必须 将 <tt>G</tt> 的顶点描述符映射至半开区间 <tt>[0,num_vertices(G))</tt> 中的整 数。<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> 属性。 &nbsp;
 </blockquote>


 UTIL/OUT: <tt>orig_to_copy(Orig2CopyMap c)</tt>
-<blockquote>
-This maps vertices in the original graph to vertices in the copy.
-
-<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 output graph's vertex descriptor type of size
-  <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
-  map.
+<blockquote>它将原图中的顶点映射至拷贝中的顶点。<br><b>缺省值:</b>一个 &nbsp;<a href="../../property_map/iterator_property_map.html"> + iterator_property_map</a><a href="http://alai04.kmip.net/boost_doc/libs/property_map/iterator_property_map.html";><tt></tt></a>,创 建自一个大小为&nbsp;<tt>num_vertices(g)</tt> 的输出图的边描述符类型的 <tt>std::vector</tt>,且以 <tt>i_map</tt> 作为索引映射。
 </blockquote>

-<H3>Complexity</H3>
-
-<P>
-The time complexity is <i>O(V + E)</i>.
+<h3>Complexity 复杂度</h3>
+
+<p>时间复杂度为 <i>O(V + E)</i>.



 <br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 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><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright (c) 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/cuthill_mckee_ordering.html Mon Mar 30 07:58:04 2009 +++ /trunk/libs/graph/doc/cuthill_mckee_ordering.html Thu Aug 13 22:58:12 2009
@@ -1,247 +1,135 @@
-<HTML>
-
-<!--   Copyright (c) Jeremy Siek 2000 -->
-
-  -- Distributed under the Boost Software License, Version 1.0.
+<!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 --><title>Boost Graph Library: Cuthill-Mckee Ordering</title></head>
+
+
+
+ <body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b">-- 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: Cuthill-Mckee Ordering</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>
-
-<H1>
-<img src="figs/python.gif" alt="(Python)"/>
-<TT>cuthill_mckee_ordering</TT>
-</H1>
-
-
-<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">color, degree</TD>
-</TR>
-<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
-<TD ALIGN="LEFT">time: <i>O(m log(m)|V|)</i> where <i>m = max { degree(v) | v in V }</i> </TD>
-</TR>
-</TABLE>
-</DIV>
-
-
-<pre>
-  (1)
-  template &lt;class IncidenceGraph, class OutputIterator,
-            class ColorMap, class DegreeMap&gt;
-  OutputIterator
-  cuthill_mckee_ordering(const IncidenceGraph&amp; g,
- typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s,
-                         OutputIterator inverse_permutation,
-                         ColorMap color, DegreeMap degree)
-
-  (2)
-  template &lt;class VertexListGraph, class OutputIterator&gt;
-  OutputIterator
- cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation);
-
- template &lt;class VertexListGraph, class OutputIterator, class VertexIndexMap&gt;
-  OutputIterator
- cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation,
-                         VertexIndexMap index_map);
-
-  template &lt;class VertexListGraph, class OutputIterator,
-            class ColorMap, class DegreeMap&gt;
-  OutputIterator
- cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation,
-                         ColorMap color, DegreeMap degree)
-
-  (3)
-  template &lt;class IncidenceGraph, class OutputIterator,
-            class ColorMap, class DegreeMap&gt;
-  OutputIterator
-  cuthill_mckee_ordering(const IncidenceGraph&amp; g,
-                        std::deque&lt; typename
- graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor &gt; vertex_queue,
-                         OutputIterator inverse_permutation,
-                         ColorMap color, DegreeMap degree)
-</pre>
-
-The goal of the Cuthill-Mckee (and reverse Cuthill-Mckee) ordering
-algorithm[<A
-HREF="bibliography.html#george81:__sparse_pos_def">14</A>, <A
-HREF="bibliography.html#cuthill69:reducing_bandwith">43</A>, <a
-href="bibliography.html#liu75:anal_cm_rcm">44</a>, <a
-href="bibliography.html#george71:fem">45</a> ] is to reduce the <a
-href="./bandwidth.html">bandwidth</a> of a graph by reordering the
-indices assigned to each vertex.  The Cuthill-Mckee ordering algorithm
-works by a local minimization of the i-th bandwidths. The vertices are
-basically assigned a breadth-first search order, except that at each
-step, the adjacent vertices are placed in the queue in order of
-increasing degree.
-
-<p>
-Version 1 of the algorithm lets the user choose the ``starting
-vertex'', version 2 finds a good starting vertex using the
-pseudo-peripheral pair heuristic (among each component), while version 3
-contains the starting nodes for each vertex in the deque. The choice of the
-``starting vertex'' can have a significant effect on the quality of the
-ordering. For versions 2 and 3, <tt>find_starting_vertex</tt> will be called
-for each component in the graph, increasing run time significantly.
+
+
+
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+
+<br clear="">
+
+<h1>
+<img src="figs/python.gif" alt="(Python)">
+<tt>cuthill_mckee_ordering</tt>
+</h1>
+
+
+<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(m log(m)|V|)</i> 其中 <i>m = max { degree(v) | v in V }</i> </td>
+</tr>
+</tbody></table>
+</div>
+
+
+<pre> (1)<br> template &lt;class IncidenceGraph, class OutputIterator,<br> class ColorMap, class DegreeMap&gt;<br> OutputIterator<br> cuthill_mckee_ordering(const IncidenceGraph&amp; g,<br> typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s,<br> OutputIterator inverse_permutation, <br> ColorMap color, DegreeMap degree)<br><br> (2)<br> template &lt;class VertexListGraph, class OutputIterator&gt;<br> OutputIterator<br> cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation); <br><br> template &lt;class VertexListGraph, class OutputIterator, class VertexIndexMap&gt;<br> OutputIterator<br> cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation, <br> VertexIndexMap index_map); <br> <br> template &lt;class VertexListGraph, class OutputIterator, <br> class ColorMap, class DegreeMap&gt;<br> OutputIterator<br> cuthill_mckee_ordering(const VertexListGraph&amp; g, OutputIterator inverse_permutation, <br> ColorMap color, DegreeMap degree)<br> <br> (3)<br> template &lt;class IncidenceGraph, class OutputIterator,<br> class ColorMap, class DegreeMap&gt;<br> OutputIterator<br> cuthill_mckee_ordering(const IncidenceGraph&amp; g,<br> std::deque&lt; typename<br> graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor &gt; vertex_queue,<br> OutputIterator inverse_permutation, <br> ColorMap color, DegreeMap degree)<br></pre>Cuthill-Mckee (和逆 Cuthill-Mckee)排序算法[<a href="bibliography.html#george81:__sparse_pos_def">14</a>, <a href="bibliography.html#cuthill69:reducing_bandwith">43</a>, <a href="bibliography.html#liu75:anal_cm_rcm">44</a>, <a href="bibliography.html#george71:fem">45</a> ]的目的是通过重排各顶点的索 引,来减少一个图的 <a href="./bandwidth.html">带宽bandwidth</a>。 Cuthill-Mckee 排序算法通过局部最小化第 i 个带宽来实现。基本上,顶点被按广度 优先搜索来赋予顺序,除了在每一步,邻接顶点被按照其度数的递增序放入队列中。
+
+<p>该算法的版本1由用户选择"开始顶点",版本2则使用
+pseudo-peripheral pair 策略(对于每个分支)查找优良的开始顶点,而版本3则将作 为开始点的各个顶点放在一个 deque 中。"开始顶点"的选择可以显著影响排序的质 量。对于版本2和3,会对图中各分支调用 <tt>find_starting_vertex</tt>,会显著增 加运行的时间。
 </p>

-<p>
-The output of the algorithm are the vertices in the new ordering.
-Depending on what kind of output iterator you use, you can get either
-the Cuthill-Mckee ordering or the reverse Cuthill-McKee ordering.  For
-example, if you store the output into a vector using the vector's
-reverse iterator, then you get the reverse Cuthill-McKee ordering.
+<p>该算法的输出是以新顺序排列的顶点。根据你所使用的输出迭代器种类,你可以得 到 Cuthill-Mckee 顺序或逆 +Cuthill-McKee 顺序。例如,如果你使用一个vector的反向迭代器将输出保存到 vector中,那么你将得到逆
+Cuthill-McKee 顺序。
 </p>

-<pre>
-  std::vector&lt;vertex_descriptor&gt; inv_perm(num_vertices(G));
-  cuthill_mckee_ordering(G, inv_perm.rbegin(), ...);
-</pre>
-
-<p>
-Either way, storing the output into a vector gives you the
-permutation from the new ordering to the old ordering.
+<pre> std::vector&lt;vertex_descriptor&gt; inv_perm(num_vertices(G));<br> cuthill_mckee_ordering(G, inv_perm.rbegin(), ...);<br></pre>
+
+<p>另一方面,将输出保存在vector中给了你从新顺序到旧顺序的排列。
 </p>

-<pre>
-  inv_perm[new_index[u]] == u
-</pre>
-
-<p>
-Often times, it is the opposite permutation that you want, the
-permutation from the old index to the new index. This can easily be
-computed in the following way.
+<pre>  inv_perm[new_index[u]] == u<br></pre>
+
+<p>通常,这是你所想要的逆排列,从旧索引到新索引的排列。这可以按以下方法很容 易地计算得到。
 </p>

-<pre>
-  for (size_type i = 0; i != inv_perm.size(); ++i)
-    perm[old_index[inv_perm[i]]] = i;
-</pre>
+<pre> for (size_type i = 0; i != inv_perm.size(); ++i)<br> perm[old_index[inv_perm[i]]] = i;<br></pre>



-<h3>Parameters</h3>
-
-For version 1:
+<h3>Parameters 参数</h3>对于版本1:

 <ul>

-<li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>
-  An undirected graph. The graph's type must be a model of <a
-  href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
-  <b>Python</b>: The parameter is named <tt>graph</tt>.
-
-<li> <tt>vertex_descriptor s</tt> &nbsp(IN) <br>
-  The starting vertex.<br>
-  <b>Python</b>: Unsupported parameter.
-
-<li> <tt>OutputIterator inverse_permutation</tt> &nbsp(OUT) <br>
-  The new vertex ordering. The vertices are written to the <a
-  href="http://www.sgi.com/tech/stl/OutputIterator.html";>output
-  iterator</a> in their new order.<br>
-  <b>Python</b>: This parameter is unused in Python. The new vertex
-  ordering is returned as a Python <tt>list</tt>.
-
-<li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
-  Used internally to keep track of the progress of the algorithm
-  (to avoid visiting the same vertex twice).<br>
-  <b>Python</b>: Unsupported parameter.
-
-<li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
-  This must map vertices to their degree.<br>
-  <b>Python</b>: Unsupported parameter.
-</ul>
-
-
-For version 2:
+<li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类型必须 符合 <a href="./IncidenceGraph.html">关联图IncidenceGraph</a>。<br>
+  <b>Python</b>: 该参数名为 <tt>graph</tt>.
+
+</li><li> <tt>vertex_descriptor s</tt> &nbsp;(IN) <br>开始顶点。<br>
+  <b>Python</b>: 不支持该参数。
+
+</li><li> <tt>OutputIterator inverse_permutation</tt> &nbsp;(OUT) <br>新的 顶点顺序。这些顶点被按它们的新顺序写出到 <a href="http://www.sgi.com/tech/stl/OutputIterator.html";>输出迭代器</a>。<br> + <b>Python</b>: 这个参数在Python中无用。新的顶点顺序作为一个 Python <tt>list</tt> 返回。
+
+</li><li> <tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
+  在内部使用,以跟踪算法的处理过程(避免重复访问同一个顶点两次)。<br>
+  <b>Python</b>: 不支持该参数。
+
+</li><li> <tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>它必须将顶点映射至它 们的度数。<br>
+  <b>Python</b>: 不支持该参数。
+</li></ul>对于版本2:

 <ul>

-<li> <tt>VertexListGraph&amp; g</tt> &nbsp;(IN) <br>
-  An undirected graph. The graph's type must be a model of <a
- href="./VertexListGraph.html">VertexListGraph</a> and <a href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
-  <b>Python</b>: The parameter is named <tt>graph</tt>.
-
-<li> <tt><a href="http://www.sgi.com/tech/stl/OutputIterator.html";>
-  OutputIterator</a> inverse_permutation</tt> &nbsp(OUT) <br>
-  The new vertex ordering. The vertices are written to the
-  output iterator in their new order.<br>
-  <b>Python</b>: This parameter is unused in Python. The new vertex
-  ordering is returned as a Python <tt>list</tt>.
-
-<li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
-  Used internally to keep track of the progress of the algorithm
-  (to avoid visiting the same vertex twice).<br>
-  <b>Python</b>: Unsupported parameter.
-
-<li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
-  This must map vertices to their degree.<br>
-  <b>Python</b>: Unsupported parameter.
-</ul>
-
-
-For version 3:
+<li> <tt>VertexListGraph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类型必 须符合 <a href="./VertexListGraph.html">点列表图VertexListGraph</a> 和 <a href="./IncidenceGraph.html">关联图IncidenceGraph</a>。<br>
+  <b>Python</b>: 该参数名为 <tt>graph</tt>.
+
+</li><li> <tt><a href="http://www.sgi.com/tech/stl/OutputIterator.html";>
+ OutputIterator</a> inverse_permutation</tt> &nbsp;(OUT) <br>新的顶点顺 序。这些顶点被按它们的新顺序写出到输出迭代器。<br> + <b>Python</b>: 这个参数在Python中无用。新的顶点顺序作为一个 Python <tt>list</tt> 返回。&nbsp;
+
+</li><li> <tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
+  在内部使用,以跟踪算法的处理过程(避免重复访问同一个顶点两次)。<br>
+  <b>Python</b>: 不支持该参数。&nbsp;
+
+</li><li> <tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>它必须将顶点映射至它 们的度数。<br>
+  <b>Python</b>: 不支持该参数。
+</li></ul>对于版本3:

 <ul>

-<li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>
-  An undirected graph. The graph's type must be a model of <a
-  href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
-  <b>Python</b>: The parameter is named <tt>graph</tt>.
-
-<li> <tt> std::deque&lt; typename graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue </tt> &nbsp(IN) <br>
-  The deque containing the starting vertices for each component.<br>
-  <b>Python</b>: Unsupported parameter.
-
-<li> <tt>OutputIterator inverse_permutation</tt> &nbsp(OUT) <br>
-  The new vertex ordering. The vertices are written to the <a
-  href="http://www.sgi.com/tech/stl/OutputIterator.html";>output
-  iterator</a> in their new order.<br>
-  <b>Python</b>: This parameter is unused in Python. The new vertex
-  ordering is returned as a Python <tt>list</tt>.
-
-<li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
-  Used internally to keep track of the progress of the algorithm
-  (to avoid visiting the same vertex twice).<br>
-  <b>Python</b>: Unsupported parameter.
-
-<li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
-  This must map vertices to their degree.<br>
-  <b>Python</b>: Unsupported parameter.
-</ul>
+<li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类型必须 符合 <a href="IncidenceGraph.html">关联图IncidenceGraph</a>。<br>
+  <b>Python</b>: 该参数名为 <tt>graph</tt>.&nbsp;
+
+</li><li> <tt> std::deque&lt; typename graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue </tt> &nbsp;(IN) <br>包含每个分支的开始顶点的 deque。<br>
+  <b>Python</b>: 不支持该参数。
+
+</li><li> <tt>OutputIterator inverse_permutation</tt> &nbsp;(OUT) <br>新的 顶点顺序。这些顶点被按它们的新顺序写出到 <a href="http://www.sgi.com/tech/stl/OutputIterator.html";>输出迭代器</a>。<br> + <b>Python</b>: 这个参数在Python中无用。新的顶点顺序作为一个 Python <tt>list</tt> 返回。&nbsp;
+
+</li><li> <tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
+  在内部使用,以跟踪算法的处理过程(避免重复访问同一个顶点两次)。<br>
+  <b>Python</b>: 不支持该参数。&nbsp;
+
+</li><li> <tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>它必须将顶点映射至它 们的度数。<br>
+  <b>Python</b>: 不支持该参数。
+</li></ul>



-<h3>Example</h3>
-
-See <a
-href="../example/cuthill_mckee_ordering.cpp"><tt>example/cuthill_mckee_ordering.cpp</tt></a>.
-
-<h3>See Also</h3>
-
-<a href="./bandwidth.html">bandwidth</tt></a>,
-and <tt>degree_property_map</tt> in <tt>boost/graph/properties.hpp</tt>.
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 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>Example 示例</h3>见 <a href="../example/cuthill_mckee_ordering.cpp"><tt>example/cuthill_mckee_ordering.cpp</tt></a>.
+
+<h3>See Also 参见</h3>
+
+<a href="./bandwidth.html">bandwidth</a>, 及 <tt>boost/graph/properties.hpp</tt> 中的 <tt>degree_property_map</tt>。<br>
+<hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright (c) 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/isomorphism.html      Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/isomorphism.html      Thu Aug 13 22:58:12 2009
@@ -1,33 +1,27 @@
-<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: Isomorphism</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>
-<img src="figs/python.gif" alt="(Python)"/>
-<TT>isomorphism</TT>
-</H1>
+<title>Boost Graph Library: Isomorphism</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>
+<img src="figs/python.gif" alt="(Python)">
+<tt>isomorphism</tt>
+</h1>


-<PRE>
-<i>// named parameter version</i>
+<pre><i>// 命名参数版本</i>
 template &lt;class Graph1, class Graph2, class P, class T, class R&gt;
 bool isomorphism(const Graph1&amp; g1, const Graph2&amp; g2,
- const bgl_named_params&lt;P,T,R&gt;&amp; params = <i>all defaults</i>)
-
-<i>// non-named parameter version</i>
+ const bgl_named_params&lt;P,T,R&gt;&amp; params = <i>all defaults</i>)<br><br><i>// 非命名参数版本</i>
 template &lt;typename Graph1, typename Graph2, typename IsoMap,
           typename VertexInvariant1, typename VertexInvariant2,
           typename V1Map, typename V2Map&gt;
@@ -37,164 +31,97 @@
 </pre>

 <p>
-An <b><i>isomorphism</i></b> is a 1-to-1 mapping of the vertices in
-one graph to the vertices of another graph such that adjacency is
-preserved. Another words, given graphs <i>G<sub>1</sub> =
-(V<sub>1</sub>,E<sub>1</sub>)</i> and <i>G<sub>2</sub> =
-(V<sub>2</sub>,E<sub>2</sub>)</i> an isomorphism is a function
-<i>f</i> such that for all pairs of vertices <i>a,b</i> in
-<i>V<sub>1</sub></i>, edge <i>(a,b)</i> is in <i>E<sub>1</sub></i> if
-and only if edge <i>(f(a),f(b))</i> is in <i>E<sub>2</sub></i>.
+<b><i>同构isomorphism</i></b> 是一个图的顶点到另一个图的顶点之间的一种 1-对 -1 映射,它保持了顶点的邻接关系。换句话说,给定两个图 <i>G<sub>1</sub> =
+(V<sub>1</sub>,E<sub>1</sub>)</i> 和 <i>G<sub>2</sub> =
+(V<sub>2</sub>,E<sub>2</sub>)</i>,同构就是一个函数
+<i>f</i>,满足对于
+<i>V<sub>1</sub></i> 中的所有顶点对 <i>a,b</i>,边 <i>(a,b)</i> 属于 <i>E<sub>1</sub></i> 当且仅当边 <i>(f(a),f(b))</i> 属于 <i>E<sub>2</sub></i>。
 </p>

-<p>
-This function returns <tt>true</tt> if there exists an isomorphism
-between graph 1 and graph 2 and <tt>false</tt> otherwise. Also, if a
-isomorphism map named parameter is provided then an isomorphism is
-recorded in the map.
+<p>如果图1和图2之间存在同构关系,则本函数返回 <tt>true</tt>,否则返回 <tt>false</tt>。此外,如果给定了一个同构映射命名参数,则同构关系被记录在该映 射中。
 </p>

-<p>
-The current implementation is based on descriptions of a backtracking
-algorithm in [<a
-href="./bibliography.html#fortin96:_graph_iso_prob">46</a>,<a
-href="./bibliography.html#reingold77:_combin_algo">48</a>].  The file
-<a href="./isomorphism-impl.pdf">isomorphism-impl.pdf</a> contains a
-&quot;literate&quot; description of the implementation.  The algorithm
-used is simple but slow. A more efficient (and much more complex)
-algorithm is described in [<a
-href="./bibliography.html#mckay81:_pract_graph_iso">47</a>]. When (and
-if) a version of this algorithm is ported to the BGL interface it
-should replace the current algorithm.
+<p>当前的实现是基于[<a href="./bibliography.html#fortin96:_graph_iso_prob">46</a>,<a href="./bibliography.html#reingold77:_combin_algo">48</a>]中的回溯算法的。文 +<a href="./isomorphism-impl.pdf">isomorphism-impl.pdf</a> 包含了该实现的一 个"文字"说明。所用的算法简单但较慢。一个更为高效(也更为复杂)的算法在[<a href="./bibliography.html#mckay81:_pract_graph_iso">47</a>]中给出。当(且如果 )该算法的一个版本被移植至BGL接口,将会替代当前算法。
 </p>

-<H3>Where Defined</H3>
-
-<a href="../../../boost/graph/isomorphism.hpp"><TT>boost/graph/isomorphism.hpp</TT></a>
-
-<h3>Parameters</h3>
+<h3>Where Defined 定义于</h3>
+
+<a href="../../../boost/graph/isomorphism.hpp"><tt>boost/graph/isomorphism.hpp</tt></a>
+
+<h3>Parameters 参数</h3>

 IN: <tt>const Graph1&amp; g1</tt>
-<blockquote>
-A directed or undirected graph. The graph type must model of <a
-href="./VertexListGraph.html">Vertex List Graph</a> and <a
-href="./EdgeListGraph.html">Edge List Graph</a>.
+<blockquote>一个有向图或无向图。图的类型必须符合 <a href="./VertexListGraph.html">点列表图Vertex List Graph</a> 和 <a href="./EdgeListGraph.html">边列表图Edge List Graph</a>。
 </blockquote>

 IN: <tt>const Graph2&amp; g2</tt>
-<blockquote>
-A directed or undirected graph. The graph type must model <a
-href="./BidirectionalGraph.html">Bidirectional Graph</a> and <a
-href="./VertexListGraph.html">Vertex List Graph</a>.
+<blockquote>一个有向图或无向图。图的类型必须符合 <a href="./BidirectionalGraph.html">双向图Bidirectional Graph</a> 和 <a href="./VertexListGraph.html">点列表图Vertex List Graph</a>。
 </blockquote>

-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>

 OUT: <tt>isomorphism_map(IsoMap f)</tt>
-<blockquote>
-The mapping from vertices in graph 1 to vertices in graph 2. This must
-be a <a href="../../property_map/ReadWritePropertyMap.html">Read/Write
-Property Map</a>.<br> <b>Default:</b> an <a
-href="../../property_map/iterator_property_map.html"><tt>iterator_property_map</tt></a>
-constructed from a <tt>std::vector</tt> of graph 2's vertex
-descriptor type and the vertex index map for graph 1.<br>
-<b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the first graph.
+<blockquote>该映射从图1的顶点至图2的顶点。它必须是一个 <a href="../../property_map/ReadWritePropertyMap.html">读/写属性映射</a>。<br> <b>缺省值:</b>一个 <a href="../../property_map/iterator_property_map.html"><tt>iterator_property_map</tt></a>,创 建自图2的顶点描述符类型的 <tt>std::vector</tt> 和图1的顶点索引映射。<br>
+<b>Python</b>: 必须是第一个图的一个 <tt>vertex_vertex_map</tt>。
 </blockquote>

 IN: <tt>vertex_invariant1(VertexInvariant1 i)</tt>
-<blockquote>
-A mapping <i>i</i> from vertices to integers such that if there is
-some isomorphism that maps <i>v</i> onto <i>v'</i> then <i>i(v) ==
-i(v')</i>. The <tt>VertexInvariant</tt> type must be a <a
-href="http://www.sgi.com/tech/stl/BinaryFunction.html";>BinaryFunction</a>
-where the first argument is a vertex descriptor, the second argument is a
-graph, and the result type is an integer. The vertex invariant must
-work with the types for graph 1.
-<br>
-<b>Default:</b> <tt>degree_vertex_invariant</tt><br>
-<b>Python</b>: Unsupported parameter.
+<blockquote>从顶点至整数的一个映射 <i>i</i>,满足如果存在同构将 <i>v</i> 映 射至 <i>v'</i> 则 <i>i(v) == +i(v')</i>。类型 <tt>VertexInvariant</tt> 必须是一个 <a href="http://www.sgi.com/tech/stl/BinaryFunction.html";>二元函数</a>,其中第 一个参数是一个顶点描述符,第二个参数是一个图,结果类型是一个整数。这个顶点不 变式必须与图1的类型一起使用。<br>
+<b>缺省值:</b><tt>degree_vertex_invariant</tt><br>
+<b>Python</b>: 不支持该参数。
 </blockquote>

 IN: <tt>vertex_invariant2(VertexInvariant2 i)</tt>
-<blockquote>
-A mapping <i>i</i> from vertices to integers such that if there is
-some isomorphism that maps <i>v</i> onto <i>v'</i> then <i>i(v) ==
-i(v')</i>. The <tt>VertexInvariant</tt> type must be a <a
-href="http://www.sgi.com/tech/stl/BinaryFunction.html";>BinaryFunction</a>
-where the first argument is a vertex descriptor, the second argument is a
-graph, and the result type is an integer. The vertex invariant must
-work with the types for both graph 2.
-<br>
-<b>Default:</b> <tt>degree_vertex_invariant</tt><br>
-<b>Python</b>: Unsupported parameter.
+<blockquote>从顶点至整数的一个映射 <i>i</i>,满足如果存在同构将 <i>v</i> 映 射至 <i>v'</i> 则 <i>i(v) == +i(v')</i>。类型 <tt>VertexInvariant</tt> 必须是一个 <a href="http://www.sgi.com/tech/stl/BinaryFunction.html";>二元函数</a>,其中第 一个参数是一个顶点描述符,第二个参数是一个图,结果类型是一个整数。这个顶点不 变式必须与图2的类型一起使用。<br>
+<b>缺省值:</b><tt>degree_vertex_invariant</tt><br>
+<b>Python</b>: 不支持该参数。
 </blockquote>

 IN: <tt>vertex_max_invariant(std::size_t max_invariant)</tt>
-<blockquote>
-An upper bound on the possible values returned from either
-vertex_invariant1 or vertex_invariant2.
-<br>
-<b>Default:</b> <tt>vertex_invariant2.max()</tt>. The default
-<tt>vertex_invariant2</tt> parameter, an instance of
-<tt>degree_vertex_invariant</tt>, defines this function to
-return <tt>num_vertices(g2) * (num_vertices(g2)+1)</tt>.<br>
-<b>Python</b>: Unsupported parameter.
+<blockquote>从
+vertex_invariant1 或 vertex_invariant2 返回的可能值的上界。<br>
+<b>缺省值:</b><tt>vertex_invariant2.max()</tt>. 缺省的
+<tt>vertex_invariant2</tt> 参数,一个
+<tt>degree_vertex_invariant</tt> 实例,定义了这个函数返回 <tt>num_vertices(g2) * (num_vertices(g2)+1)</tt>.<br>
+<b>Python</b>: 不支持该参数。
 </blockquote>

 IN: <tt>vertex_index1_map(VertexIndex1Map i1_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>VertexIndex1Map</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 graph 1 needs to be usable as the key type of the
-map.<br>
-<b>Default:</b> <tt>get(vertex_index, g1)</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>VertexIndex1Map</tt> 必须符合 <a href="../../property_map/ReadablePropertyMap.html">可读属性映射</a>。该映射 的值类型必须是整数类型。图1的顶点描述符类型必须可用作该映射的键类型。<br>
+<b>缺省值:</b><tt>get(vertex_index, g1)</tt>
+ 注意:如果你使用该缺省值,请确认你的图具有一个内部的 <tt>vertex_index</tt> 属性。例如,带 <tt>VertexList=listS</tt> 的
+    <tt>adjacenty_list</tt> 并不具有内部的 <tt>vertex_index</tt> 属性。
+<br>
+<b>Python</b>: 不支持该参数。
 </blockquote>

 IN: <tt>vertex_index2_map(VertexIndex2Map i2_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>VertexIndex2Map</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 graph 2 needs to be usable as the key type of the
-map.<br>
-<b>Default:</b> <tt>get(vertex_index, g2)</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>VertexIndex2Map</tt> 必须符合 <a href="../../property_map/ReadablePropertyMap.html">可读属性映射</a>。该映射 的值类型必须是整数类型。图2的顶点描述符类型必须可用作该映射的键类型。<br>
+<b>缺省值:</b><tt>get(vertex_index, g1)</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>
-
-The worst-case time complexity is <i>O(|V|!)</i>.
-
-<h3>Example</h3>
-
-See <a href="../example/isomorphism.cpp"><tt>libs/graph/example/isomorphism.cpp</tt></a>.
+<h3>Complexity 复杂度</h3>最坏情况下的时间复杂度为 <i>O(|V|!)</i>。
+
+<h3>Example 示例</h3>见 <a href="../example/isomorphism.cpp"><tt>libs/graph/example/isomorphism.cpp</tt></a>.

 <br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 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 (c) 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/king_ordering.html    Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/king_ordering.html    Thu Aug 13 22:58:12 2009
@@ -1,235 +1,116 @@
-<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)
--->
+-->
+<title>Boost Graph Library: King Ordering</title></head>
+


-<Head>
-<Title>Boost Graph Library: King Ordering</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>
-<img src="figs/python.gif" alt="(Python)"/>
-<TT>king_ordering</TT>
-</H1>
+<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>
+<img src="figs/python.gif" alt="(Python)">
+<tt>king_ordering</tt>
+</h1>


-<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">color, degree</TD>
-</TR>
-<TR><TH ALIGN="LEFT"><B>Complexity:</B></TH>
-<TD ALIGN="LEFT">time: <i>O(m<sup>2</sup>log(m)|E|)</i> where <i>m = max { degree(v) | v in V }</i> </TD>
-</TR>
-</TABLE>
-</DIV>
+<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(m<sup>2</sup>log(m)|E|)</i> 其中 <i>m = max { degree(v) | v in V }</i> </td>
+</tr>
+</tbody></table>
+</div>


-<pre>
-  (1)
-  template &lt;class IncidenceGraph, class OutputIterator,
-            class ColorMap, class DegreeMap, class VertexIndexMap&gt;
-  OutputIterator
-  king_ordering(const IncidenceGraph&amp; g,
-                typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
-                OutputIterator inverse_permutation,
- ColorMap color, DegreeMap degree, VertexIndexMap index_map);
-
-  (2)
-  template &lt;class IncidenceGraph, class OutputIterator&gt;
-  OutputIterator
- king_ordering(const IncidenceGraph&amp; g, OutputIterator inverse_permutation);
-
- template &lt;class IncidenceGraph, class OutputItrator, class VertexIndexMap&gt;
-  OutputIterator
- king_ordering(const IncidenceGraph&amp; g, OutputIterator inverse_permutation,
-                VertexIndexMap index_map);
-
-  template &lt;class VertexListGraph, class OutputIterator,
-            class ColorMap, class DegreeMap, class VertexIndexMap&gt;
-  OutputIterator
- king_ordering(const VertexListGraph&amp; G, OutputIterator inverse_permutation, - ColorMap color, DegreeMap degree, VertexIndexMap index_map);
-
-  (3)
-  template &lt;class IncidenceGraph, class OutputIterator,
-            class ColorMap, class DegreeMap, class VertexIndexMap&gt;
-  OutputIterator
-  king_ordering(const IncidenceGraph&amp; g,
-               std::deque&lt; typename
-               graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue,
-                OutputIterator permutation,
- ColorMap color, DegreeMap degree, VertexIndexMap index_map);
-</pre>
+<pre> (1)<br> template &lt;class IncidenceGraph, class OutputIterator,<br> class ColorMap, class DegreeMap, class VertexIndexMap&gt;<br> OutputIterator<br> king_ordering(const IncidenceGraph&amp; g,<br> typename graph_traits&lt;Graph&gt;::vertex_descriptor s,<br> OutputIterator inverse_permutation, <br> ColorMap color, DegreeMap degree, VertexIndexMap index_map);<br><br> (2)<br> template &lt;class IncidenceGraph, class OutputIterator&gt;<br> OutputIterator<br> king_ordering(const IncidenceGraph&amp; g, OutputIterator inverse_permutation);<br><br> template &lt;class IncidenceGraph, class OutputItrator, class VertexIndexMap&gt;<br> OutputIterator<br> king_ordering(const IncidenceGraph&amp; g, OutputIterator inverse_permutation,<br> VertexIndexMap index_map);<br><br> template &lt;class VertexListGraph, class OutputIterator, <br> class ColorMap, class DegreeMap, class VertexIndexMap&gt;<br> OutputIterator<br> king_ordering(const VertexListGraph&amp; G, OutputIterator inverse_permutation, <br> ColorMap color, DegreeMap degree, VertexIndexMap index_map);<br> <br> (3)<br> template &lt;class IncidenceGraph, class OutputIterator,<br> class ColorMap, class DegreeMap, class VertexIndexMap&gt;<br> OutputIterator<br> king_ordering(const IncidenceGraph&amp; g,<br> std::deque&lt; typename<br> graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue,<br> OutputIterator permutation, <br> ColorMap color, DegreeMap degree, VertexIndexMap index_map);<br></pre>

<!-- King, I.P. An automatic reordering scheme for simultaneous equations derived from network analysis. Int. J. Numer. Methods Engrg. 2 (1970), 523-533 -->

-The goal of the King ordering
-algorithm [<a href="bibliography.html#king70">62</a>]is to reduce the <a
-href="./bandwidth.html">bandwidth</a> of a graph by reordering the
-indices assigned to each vertex.  The King ordering algorithm
-works by a local minimization of the i-th bandwidths. The vertices are
-basically assigned a breadth-first search order, except that at each
-step, the adjacent vertices are placed in the queue in order of
-increasing pseudo-degree, where pseudo-degree is defined as the number of
-outgoing edges with white endpoints (vertices yet to be examined).
-
-<p>
-Version 1 of the algorithm lets the user choose the ``starting
-vertex'', version 2 finds a good starting vertex using the
-pseudo-peripheral pair heuristic (among each component), while version 3
-contains the starting nodes for each vertex in the deque. The choice of the ``starting
-vertex'' can have a significant effect on the quality of the ordering.
-</p>
-
-<p>
-The output of the algorithm are the vertices in the new ordering.
-Storing the output into a vector gives you the
-permutation from the new ordering to the old ordering.
-
-<pre>
-  inv_perm[new_index[u]] == u
-</pre>
-
-<p>
-Often times, it is the opposite permutation that you want, the
-permutation from the old index to the new index. This can easily be
-computed in the following way.
-</p>
-
-<pre>
-  for (size_type i = 0; i != inv_perm.size(); ++i)
-    perm[old_index[inv_perm[i]]] = i;
-</pre>
-
-
-
-<h3>Parameters</h3>
-
-For version 1:
-
-<ul>
-
-<li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>
-  An undirected graph. The graph's type must be a model of <a
-  href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
-  <b>Python</b>: The parameter is named <tt>graph</tt>.
-
-<li> <tt>vertex_descriptor s</tt> &nbsp(IN) <br>
-  The starting vertex.<br>
-  <b>Python</b>: Unsupported parameter.
-
-<li> <tt>OutputIterator permutation</tt> &nbsp(OUT) <br>
-  The new vertex ordering. The vertices are written to the <a
-  href="http://www.sgi.com/tech/stl/OutputIterator.html";>output
-  iterator</a> in their new order. <br>
-  <b>Python</b>: This parameter is unused in Python. The new vertex
-  ordering is returned as a Python <tt>list</tt>.
-
-
-<li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
-  Used internally to keep track of the progress of the algorithm
-  (to avoid visiting the same vertex twice).<br>
-  <b>Python</b>: Unsupported parameter.
-
-<li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
-  This must map vertices to their degree.<br>
-  <b>Python</b>: Unsupported parameter.
-
-</ul>
-
-
-For version 2:
-
-<ul>
-
-<li> <tt>VertexListGraph&amp; g</tt> &nbsp;(IN) <br>
-  An undirected graph. The graph's type must be a model of <a
-  href="./VertexListGraph.html">VertexListGraph</a>.<br>
-  <b>Python</b>: The name of this parameter is <tt>graph</tt>.
-
-<li> <tt><a href="http://www.sgi.com/tech/stl/OutputIterator.html";>
-  OutputIterator</a> permutation</tt> &nbsp(OUT) <br>
-  The new vertex ordering. The vertices are written to the
-  output iterator in their new order.<br>
-  <b>Python</b>: This parameter is unused in Python. The new vertex
-  ordering is returned as a Python <tt>list</tt>.
-
-<li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
-  Used internally to keep track of the progress of the algorithm
-  (to avoid visiting the same vertex twice).<br>
-  <b>Python</b>: Unsupported parameter.
-
-<li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
-  This must map vertices to their degree.<br>
-  <b>Python</b>: Unsupported parameter.
-</ul>
-
-
-For version 3:
-
-<ul>
-
-<li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>
-  An undirected graph. The graph's type must be a model of <a
-  href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
-  <b>Python</b>: The parameter is named <tt>graph</tt>.
-
-<li> <tt> std::deque&lt; typename graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue </tt> &nbsp(IN) <br>
-  The deque containing the starting vertices for each component.<br>
-  <b>Python</b>: This parameter is unused in Python. The new vertex
-  ordering is returned as a Python <tt>list</tt>.
-
-<li> <tt>OutputIterator permutation</tt> &nbsp(OUT) <br>
-  The new vertex ordering. The vertices are written to the <a
-  href="http://www.sgi.com/tech/stl/OutputIterator.html";>output
-  iterator</a> in their new order.<br>
-  <b>Python</b>: This parameter is unused in Python. The new vertex
-  ordering is returned as a Python <tt>list</tt>.
-
-<li> <tt>ColorMap color_map</tt> &nbsp(WORK) <br>
-  Used internally to keep track of the progress of the algorithm
-  (to avoid visiting the same vertex twice).<br>
-  <b>Python</b>: Unsupported parameter.
-
-<li> <tt>DegreeMap degree_map</tt> &nbsp(IN) <br>
-  This must map vertices to their degree.<br>
-  <b>Python</b>: Unsupported parameter.
-</ul>
-
-
-
-<h3>Example</h3>
-
-See <a
-href="../example/king_ordering.cpp"><tt>example/king_ordering.cpp</tt></a>.
-
-<h3>See Also</h3>
-
-<a href="./bandwidth.html">bandwidth</tt></a>,
-and <tt>degree_property_map</tt> in <tt>boost/graph/properties.hpp</tt>.
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy; 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>
+King 排序算法[<a href="bibliography.html#king70">62</a>]的目的是通过重排各 顶点的索引,来减少一个图的 <a href="bandwidth.html">带宽bandwidth</a>。King 排序算法通过局部最小化第 i 个带宽来实现。基本上,顶点被按广度优先搜索来赋予 顺序,除了在每一步,邻接顶点被按照其伪度数的递增序放入队列中,伪度数是指白色 终点(尚未检查的顶点)的出边数量。
+
+<p>该算法的版本1由用户选择"开始顶点",版本2则使用
+pseudo-peripheral pair 策略(对于每个分支)查找优良的开始顶点,而版本3则将作 为开始点的各个顶点放在一个 deque 中。"开始顶点"的选择可以显著影响排序的质 量。</p><p>该算法的输出是以新顺序排列的顶点。将输出保存在vector中给了你从新 顺序到旧顺序的排列。&nbsp;
+
+</p><pre>  inv_perm[new_index[u]] == u<br></pre>
+
+<p>通常,这是你所想要的逆排列,从旧索引到新索引的排列。这可以按以下方法很容 易地计算得到。</p><pre> for (size_type i = 0; i != inv_perm.size(); ++i)<br> perm[old_index[inv_perm[i]]] = i;<br></pre>
+
+
+
+<h3>Parameters 参数</h3>对于版本1:
+
+<ul><li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类型 必须符合 <a href="IncidenceGraph.html">关联图IncidenceGraph</a>。<br>
+  <b>Python</b>: 该参数名为 <tt>graph</tt>.
+
+</li><li> <tt>vertex_descriptor s</tt> &nbsp;(IN) <br>开始顶点。<br>
+  <b>Python</b>: 不支持该参数。
+
+</li><li> <tt>OutputIterator&nbsp;permutation</tt> &nbsp;(OUT) <br>新的顶点 顺序。这些顶点被按它们的新顺序写出到 <a href="http://www.sgi.com/tech/stl/OutputIterator.html";>输出迭代器</a>。<br> + <b>Python</b>: 这个参数在Python中无用。新的顶点顺序作为一个 Python <tt>list</tt> 返回。
+
+</li><li> <tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
+  在内部使用,以跟踪算法的处理过程(避免重复访问同一个顶点两次)。<br>
+  <b>Python</b>: 不支持该参数。
+
+</li><li> <tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>它必须将顶点映射至它 们的度数。<br>
+  <b>Python</b>: 不支持该参数。</li></ul>对于版本2:
+
+<ul><li> <tt>VertexListGraph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类 型必须符合 <a href="VertexListGraph.html">点列表图VertexListGraph</a>。<br>
+  <b>Python</b>: 该参数名为 <tt>graph</tt>.
+
+</li><li> <tt><a href="http://www.sgi.com/tech/stl/OutputIterator.html";>
+ OutputIterator</a>&nbsp;permutation</tt> &nbsp;(OUT) <br>新的顶点顺序。这 些顶点被按它们的新顺序写出到输出迭代器。<br> + <b>Python</b>: 这个参数在Python中无用。新的顶点顺序作为一个 Python <tt>list</tt> 返回。&nbsp;
+
+</li><li> <tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
+  在内部使用,以跟踪算法的处理过程(避免重复访问同一个顶点两次)。<br>
+  <b>Python</b>: 不支持该参数。&nbsp;
+
+</li><li> <tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>它必须将顶点映射至它 们的度数。<br>
+  <b>Python</b>: 不支持该参数。</li></ul>对于版本3:
+
+<ul><li> <tt>IncidenceGraph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类型 必须符合 <a href="IncidenceGraph.html">关联图IncidenceGraph</a>。<br>
+  <b>Python</b>: 该参数名为 <tt>graph</tt>.&nbsp;
+
+</li><li> <tt> std::deque&lt; typename graph_traits&lt;Graph&gt;::vertex_descriptor &gt; vertex_queue </tt> &nbsp;(IN) <br>包含每个分支的开始顶点的 deque。<br>
+  <b>Python</b>: 不支持该参数。
+
+</li><li> <tt>OutputIterator&nbsp;permutation</tt> &nbsp;(OUT) <br>新的顶点 顺序。这些顶点被按它们的新顺序写出到 <a href="http://www.sgi.com/tech/stl/OutputIterator.html";>输出迭代器</a>。<br> + <b>Python</b>: 这个参数在Python中无用。新的顶点顺序作为一个 Python <tt>list</tt> 返回。&nbsp;
+
+</li><li> <tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
+  在内部使用,以跟踪算法的处理过程(避免重复访问同一个顶点两次)。<br>
+  <b>Python</b>: 不支持该参数。&nbsp;
+
+</li><li> <tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>它必须将顶点映射至它 们的度数。<br> + <b>Python</b>: 不支持该参数。</li></ul><h3>Example 示例</h3>见 <a href="../example/king_ordering.cpp"><tt>example/king_ordering.cpp</tt></a>.
+
+<h3>See Also 参见</h3>
+
+<a href="./bandwidth.html">bandwidth</a>,
+
+
+及 <tt>boost/graph/properties.hpp</tt> 中的 <tt>degree_property_map</tt>。 <br>
+<hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright (c) 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/metric_tsp_approx.html        Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/metric_tsp_approx.html        Thu Aug 13 22:58:12 2009
@@ -1,40 +1,25 @@
-<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) Matyas Egyhazy 2008
   --
   -- 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: Metric Traveling Salesperson Approximation</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: Metric Traveling Salesperson Approximation</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:metric_tsp_approx"></A>
-<TT>metric_tsp_approx</TT>
-</H1>
-
-<P>
-<PRE>
-template &lt;typename VertexListGraph,
-          typename WeightMap,
-          typename VertexIndexMap,
-          typename TSPVertexVisitor&gt;
-void metric_tsp_approx_from_vertex(
-        const VertexListGraph&amp; g,
- typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor start,
-        WeightMap weightmap,
-        VertexIndexMap indexmap,
-        TSPVertexVisitor vis)
-
-<i>// Overloads</i>
+<h1><a name="sec:metric_tsp_approx"></a>
+<tt>metric_tsp_approx</tt>
+</h1>
+
+<p>
+</p><pre>template &lt;typename VertexListGraph,<br> typename WeightMap,<br> typename VertexIndexMap,<br> typename TSPVertexVisitor&gt;<br>void metric_tsp_approx_from_vertex(<br> const VertexListGraph&amp; g,<br> typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor start,<br> WeightMap weightmap,<br> VertexIndexMap indexmap,<br> TSPVertexVisitor vis)<br><br><i>// 重载</i>
 template&lt;typename VertexListGraph, typename OutputIterator&gt;
 void metric_tsp_approx_tour(VertexListGraph&amp; g, OutputIterator o)

@@ -53,7 +38,7 @@
     typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor start,
     WeightMap w, OutputIterator o)

-<i>// visitor versions</i>
+<i>// 遍历器版本</i>
 template&lt;typename VertexListGraph, typename TSPVertexVisitor&gt;
 void metric_tsp_approx(VertexListGraph&amp; g, TSPVertexVisitor vis)

@@ -73,132 +58,90 @@
     typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor start,
     WeightMap w, TSPVertexVisitor vis)

-</PRE>
-
-<P>
-This is a traveling salesperson heuristic for generating a tour of vertices
-for a fully connected undirected graph with weighted edges that obey the triangle inequality. -The current implementation is based off of the algorithm presented in <i>Introduction to Algorithms</i> -on page 1029. This implementation generates solutions that are twice as long as the optimal tour in the worst case.
-The pseudo-code is listed below.
+</pre>
+
+<p>这是一个旅行商问题的解法,为一个带边权的、满足三角不等式的全连通无向图生 成一个顶点的巡回路径。当前的实现基于 <i>Introduction to Algorithms</i> +一书中第1029页介绍的算法。该实现生成的解答在最坏情况下为最优巡回的两倍。伪 代码列出如下。
 </p>

 <table>
-<tr>
+<tbody><tr>
 <td valign="top">
-<pre>
-TSP-APPROX(<i>G</i>, <i>w</i>)
-  select a vertex <i>r</i> <i>in</i> <i>V[G]</i>
-  compute a minimum spanning tree <i>T</i> for <i>G</i> from root <i>r</i>
-    using PRIM-MST(<i>G</i>, <i>r</i>, <i>w</i>)
- let <i>L</i> be the list of vertices visited in a preorder traversal of <i>T</i> - <b>return</b> (the Hamiltonian cycle <i>H</i> that visites the vertices in the order <i>L</i>)
-</pre>
+<pre>TSP-APPROX(<i>G</i>, <i>w</i>)<br> 在 <i>V[G]</i> 中选择一个顶点 <i>r</i><i></i><br> 计算 <i>G</i> 中根顶点 <i>r</i> 的最小生成树 <i>T</i> <i></i><i></i> + 调用 PRIM-MST(<i>G</i>, <i>r</i>, <i>w</i>)<br> 令 <i>L</i> 为 <i>T</i> 的先序遍历中对访问各顶点的列表<i></i> + <b>return</b> (访问顺序 <i>L</i> 中各顶点的哈密顿回路 <i>H</i> )<br></pre>
 </td>
 </tr>
-</table>
+</tbody></table>


-<H3>Where Defined</H3>
-
-<P>
-<a href="../../../boost/graph/metric_tsp_approx.hpp"><TT>boost/graph/metric_tsp_approx.hpp</TT></a>
-
-<P>
-
-<h3>Parameters</h3>
+<h3>Where Defined 定义于</h3>
+
+<p>
+<a href="../../../boost/graph/metric_tsp_approx.hpp"><tt>boost/graph/metric_tsp_approx.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Parameters 参数</h3>

 IN: <tt>const Graph&amp; 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> <a href="#2">[2]</a>.<br> +<blockquote>一个无向图。类型 <tt>Graph</tt> 必须符合 <a href="./VertexListGraph.html">点列表图Vertex List Graph</a> 和 <a href="./IncidenceGraph.html">关联图Incidence Graph</a> <a href="#2">[2]</a>。<br>
 </blockquote>

 IN: <tt>vertex_descriptor start</tt>
-<blockquote>
-  The vertex that will be the start (and end) of the tour.<br>
-  <b>Default:</b> <tt>*vertices(g).first</tt>
+<blockquote>开始(及结束)巡游的顶点。<br>
+  <b>缺省值:</b><tt>*vertices(g).first</tt>
 </blockquote>

 IN: <tt>WeightMap weightmap</tt>
-<blockquote>
-  The weight 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.<br>
-  <b>Default:</b>  <tt>get(edge_weight, g)</tt><br>
+<blockquote>图中各边的权重。类型 <tt>WeightMap</tt> 必须符合
+ <a href="../../property_map/ReadablePropertyMap.html">可读属性映射</a>。 图的边描述符类型必须可用作该权重映射的键类型。<br>
+  <b>缺省值:</b><tt>get(edge_weight, g)</tt><br>
 </blockquote>

 IN: <tt>VertexIndexMap indexmap</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>
+<blockquote>它将每个顶点映射至区间 <tt>[0,
+ num_vertices(g))</tt> 中的某个整数。在边松驰时,为了对堆数据结构进行高 效的更新,需要该映射。类型 + <tt>VertexIndexMap</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>

 OUT: <tt>OutputIterator o</tt>
-<blockquote>
-  The OutputIterator holds the vertices of the tour.
-  The type <tt>OutputIterator</tt> must be a model of the
-  OutputIterator concept.
+<blockquote>该输出迭代器用于保存巡游的顶点。类型 <tt>OutputIterator</tt> 必 须符合输出迭代器的概念。
 </blockquote>

 OUT: <tt>TSPTourVisitor vis</tt>
-<blockquote>
-  Use this to specify actions that you would like to happen
-  when the algorithm visits a vertex of the tour.
- The type <tt>TSPTourVisitor</tt> must be a model of the <a href="./TSPTourVisitor.html">TSP Tour Visitor</a>
-  concept.
-  The visitor object is passed by value <a
-  href="#1">[1]</a>.<br>
+<blockquote>用于指定你想在该算法访问巡游中某个顶点时发生的动作。类型 <tt>TSPTourVisitor</tt> 必须符合 <a href="./TSPTourVisitor.html">TSP 巡游遍 历器</a>
+  概念。该遍历器对象以值的方式传递<a href="#1">[1]</a>。<br>
 </blockquote>

-<H3>Complexity</H3>
-
-<P>
-The time complexity is <i>O(E log V)</i>.
-
-<P>
-
-<H3>Example</H3>
-
-<P>
-The file <a
-href="../test/metric_tsp_approx_example.cpp"><TT>test/metric_tsp_approx_example.cpp</TT></a>
-contains an example of using this TSP approximation algorithm.
+<h3>Complexity 复杂度</h3>
+
+<p>时间复杂度为 <i>O(E log V)</i>.
+
+</p><p>
+
+</p><h3>Example 示例</h3>
+
+<p>文件 <a href="../test/metric_tsp_approx_example.cpp"><tt>test/metric_tsp_approx_example.cpp</tt></a>
+包含了一个使用该TSP近似算法的例子。


-<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.
+ 由于 visitor 参数是以值方式传递的,所以如果你的遍历器含有状态,则在算法中 对该状态的所有修改都是针对该遍历器对象的一个拷贝,而不对传入的遍历器对象进行 的。因此你应该让该遍历器以指针或引用的方式保存该状态。
 </p>
-<p><a name="2">[2]</a>
- Passing an <tt>adjacency_list</tt> with a vertex <em>not</em> set selected by
-  <tt>vecS</tt> will result in <i>O(n<sup>2</sup>)</i> performance.
+<p><a name="2">[2]</a> 传入一个顶点不是设定为
+ <tt>vecS</tt> 的 <tt>adjacency_list</tt> 将导致 <i>O(n<sup>2</sup>)</i> 的性能。
 </p>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 2008</TD><TD>
+<hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright (c) 2008</td><td>
 Matyas Egyhazy
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+</td></tr></tbody></table>
+
+</body></html>
=======================================
--- /trunk/libs/graph/doc/minimum_degree_ordering.html Mon Mar 30 07:58:04 2009 +++ /trunk/libs/graph/doc/minimum_degree_ordering.html Thu Aug 13 22:58:12 2009
@@ -1,178 +1,87 @@
-<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) Lie-Quan Lee and Jeremy Siek, 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: Minimum Degree Ordering</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:mmd">
-<img src="figs/python.gif" alt="(Python)"/>
-<TT>minimum_degree_ordering</TT>
-</H1>
+<title>Boost Graph Library: Minimum Degree Ordering</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:mmd">
+<img src="figs/python.gif" alt="(Python)">
+<tt>minimum_degree_ordering</tt>
+</a></h1>


-<pre>
-  template &lt;class AdjacencyGraph, class OutDegreeMap,
-           class InversePermutationMap,
- class PermutationMap, class SuperNodeSizeMap, class VertexIndexMap&gt;
-  void minimum_degree_ordering
-    (AdjacencyGraph& G,
-     OutDegreeMap outdegree,
-     InversePermutationMap inverse_perm,
-     PermutationMap perm,
-     SuperNodeSizeMap supernode_size, int delta, VertexIndexMap id)
-</pre>
-
-<p>The minimum degree ordering algorithm&nbsp;[<A
-HREF="bibliography.html#LIU:MMD">21</A>, <A
-href="bibliography.html#George:evolution">35</a>] is a fill-in
-reduction matrix reordering algorithm.  When solving a system of
-equations such as <i>A x = b</i> using a sparse version of Cholesky
-factorization (which is a variant of Gaussian elimination for
-symmetric matrices), often times elements in the matrix that were once
-zero become non-zero due to the elimination process. This is what is
-referred to as &quot;fill-in&quot;, and fill-in is bad because it
-makes the matrix less sparse and therefore consume more time and space
-in later stages of the elimintation and in computations that use the
-resulting factorization. Now it turns out that reordering the rows of
-a matrix can have a dramatic affect on the amount of fill-in that
-occurs. So instead of solving <i>A x = b</i>, we instead solve the
-reordered (but equivalent) system <i>(P A P<sup>T</sup>)(P x) = P
-b</i>. Finding the optimal ordering is an NP-complete problem (e.i.,
-it can not be solved in a reasonable amount of time) so instead we
-just find an ordering that is &quot;good enough&quot; using
-heuristics. The minimum degree ordering algorithm is one such
-approach.
-
-<p>
-A symmetric matrix <TT>A</TT> is typically represented with an
-undirected graph, however for this function we require the input to be
-a directed graph.  Each nonzero matrix entry <TT>A(i, j)</TT> must be
-represented by two directed edges (<TT>e(i,j)</TT> and
-<TT>e(j,i)</TT>) in <TT>G</TT>.
-
-<p>
-The output of the algorithm are the vertices in the new ordering.
-<pre>
-  inverse_perm[new_index[u]] == old_index[u]
-</pre>
-<p> and the permutation from the old index to the new index.
-<pre>
-  perm[old_index[u]] == new_index[u]
-</pre>
-<p>The following equations are always held.
-<pre>
-  for (size_type i = 0; i != inverse_perm.size(); ++i)
-    perm[inverse_perm[i]] == i;
-</pre>
-
-<h3>Parameters</h3>
+<pre><a name="sec:mmd"> template &lt;class AdjacencyGraph, class OutDegreeMap,<br> class InversePermutationMap, <br> class PermutationMap, class SuperNodeSizeMap, class VertexIndexMap&gt;<br> void minimum_degree_ordering<br> (AdjacencyGraph&amp; G,<br> OutDegreeMap outdegree,<br> InversePermutationMap inverse_perm,<br> PermutationMap perm, <br> SuperNodeSizeMap supernode_size, int delta, VertexIndexMap id) <br></a></pre>
+
+<p><a name="sec:mmd">最小度排序算法[</a><a href="bibliography.html#LIU:MMD">21</a>, <a href="bibliography.html#George:evolution">35</a>]是一个减少填充的矩阵重排算 法。在使用稀疏版本的&nbsp;Cholesky 分解(这是高斯消去法针对对称矩阵的一个变 种)来求解形如 <i>A x = b</i> +的方程组时,矩阵中的那些原本是零的元素常常会由于消去过程而变为非零。这就被 称为"填充",填充是不好的,因为它令矩阵变得不稀疏,从而在使用该分解结 +果进行后续消去和计算时耗费更多的时间和空间。现在事实证明,通过重排矩阵中的 行,可以显著影响发生填充的数量。因此,我们不求解 <i>A x = b</i>,换为求解重 排(但等价)的方程组 <i>(P A P<sup>T</sup>)(P x) = P +b</i>。找出最优的排序是一个NP完全问题(即,不能在合理时间内解出),所以我们换 为只使用启发式策略找出一个"足够好"的排序。最小度排序算法就是这样一个方法。
+
+</p><p>通常,对称矩阵 <tt>A</tt> 表示一个无向图,但是对于这个函数,我们要求 输入的是一个有向图。矩阵中的每个非零项 <tt>A(i, j)</tt> 必须由 G 中的两条有 向边 (<tt>e(i,j)</tt> and
+<tt>e(j,i)</tt>) 来表示。
+
+</p><p>该算法的输出是按新顺序排列的顶点。
+</p><pre>  inverse_perm[new_index[u]] == old_index[u]<br></pre>
+<p>以及从旧索引至新索引的排列。
+</p><pre>  perm[old_index[u]] == new_index[u]<br></pre>
+<p>以下等式总是被保持。
+</p><pre> for (size_type i = 0; i != inverse_perm.size(); ++i)<br> perm[inverse_perm[i]] == i;<br></pre>
+
+<h3>Parameters 参数</h3>

 <ul>

-<li> <tt>AdjacencyGraph&amp; G</tt> &nbsp;(IN) <br>
-  A directed graph. The graph's type must be a model of <a
-  href="./AdjacencyGraph.html">Adjacency Graph</a>,
-  <a
-  href="./VertexListGraph.html">Vertex List Graph</a>,
-  <a href="./IncidenceGraph.html">Incidence Graph</a>,
-  and <a href="./MutableGraph.html">Mutable Graph</a>.
-  In addition, the functions <tt>num_vertices()</tt> and
-  <TT>out_degree()</TT> are required.
-
-<li> <tt>OutDegreeMap outdegree</tt> &nbsp(WORK) <br>
-  This is used internally to store the out degree of vertices.  This
-  must be a <a href="../../property_map/LvaluePropertyMap.html">
-  LvaluePropertyMap</a> with key type the same as the vertex
-  descriptor type of the graph, and with a value type that is an
-  integer type.
-
-<li> <tt>InversePermutationMap inverse_perm</tt> &nbsp(OUT) <br>
-  The new vertex ordering, given as the mapping from the
-  new indices to the old indices (an inverse permutation).
-  This must be an <a href="../../property_map/LvaluePropertyMap.html">
-  LvaluePropertyMap</a> with a value type and key type a signed integer.
-
-<li> <tt>PermutationMap perm</tt> &nbsp(OUT) <br>
-  The new vertex ordering, given as the mapping from the
-  old indices to the new indices (a permutation).
-  This must be an <a href="../../property_map/LvaluePropertyMap.html">
-  LvaluePropertyMap</a> with a value type and key type a signed integer.
-
-<li> <tt>SuperNodeSizeMap supernode_size</tt> &nbsp(WORK/OUT) <br>
-  This is used internally to record the size of supernodes and is also
-  useful information to have. This is a <a
-  href="../../property_map/LvaluePropertyMap.html">
-  LvaluePropertyMap</a> with an unsigned integer value type and key
-  type of vertex descriptor.
-
-<li> <tt>int delta</tt> &nbsp(IN) <br>
-  Multiple elimination control variable. If it is larger than or equal
-  to zero then multiple elimination is enabled. The value of
-  <tt>delta</tt> specifies the difference between the minimum degree
-  and the degree of vertices that are to be eliminated.
-
-<li> <tt>VertexIndexMap id</tt> &nbsp(IN) <br>
-  Used internally to map vertices to their indices. This must be a <a
-  href="../../property_map/ReadablePropertyMap.html"> Readable
-  Property Map</a> with key type the same as the vertex descriptor of
-  the graph and a value type that is some unsigned integer type.
-
-</ul>
+<li> <tt>AdjacencyGraph&amp; G</tt> &nbsp;(IN) <br>一个有向图。图的类型必须 符合 <a href="./AdjacencyGraph.html">邻接图Adjacency Graph</a>,
+  <a href="./VertexListGraph.html">点列表图Vertex List Graph</a>,
+ <a href="./IncidenceGraph.html">关联图Incidence Graph</a>, 和 <a href="./MutableGraph.html">可变图Mutable Graph</a>。此外,要求具有函数 <tt>num_vertices()</tt> 和
+  <tt>out_degree()</tt>。
+
+</li><li> <tt>OutDegreeMap outdegree</tt> &nbsp;(WORK) <br>内部使用以保存顶 点的出度。它必须是 <a href="../../property_map/LvaluePropertyMap.html">
+  左值属性映射</a>,且键类型与图的顶点描述符类型相同,值类型为整数类型。
+
+</li><li> <tt>InversePermutationMap inverse_perm</tt> &nbsp;(OUT) <br>新的 顶点顺序,以从新索引至旧索引的映射(一个逆排列)方式给出。它必须是 <a href="../../property_map/LvaluePropertyMap.html">
+  左值属性映射</a>,值类型和键类型均为有符号整数。
+
+</li><li> <tt>PermutationMap perm</tt> &nbsp;(OUT) <br>新的顶点顺序,以从旧 索引至新索引的映射(一个排列)方式给出。它必须是 <a href="../../property_map/LvaluePropertyMap.html">
+  左值属性映射</a>,值类型和键类型均为有符号整数。
+
+</li><li> <tt>SuperNodeSizeMap supernode_size</tt> &nbsp;(WORK/OUT) <br>内 部使用以记录超级节点的大小及所带的有用信息。这是一个 <a href="../../property_map/LvaluePropertyMap.html">
+  左值属性映射</a>,值类型为无符号整数,键类型为顶点描述符。
+
+</li><li> <tt>int delta</tt> &nbsp;(IN) <br>多消去控制变量。如果它大于或等 于零,则激活多消去。<tt>delta</tt> 的值指定最小度与被消去顶点的度之间的差 异。
+
+</li><li> <tt>VertexIndexMap id</tt> &nbsp;(IN) <br>内部使用以将顶点映射至 它们的索引。它必须是一个 <a href="../../property_map/ReadablePropertyMap.html"> 可读属性映射</a>,键类型 与图的顶点描述符相同,值类型为某个无符号整数类型。
+
+</li></ul>


-<h3>Example</h3>
-
-See <a
-href="../example/minimum_degree_ordering.cpp"><tt>example/minimum_degree_ordering.cpp</tt></a>.
-
-
-<h3>Implementation Notes</h3>
-
-<p>UNDER CONSTRUCTION
-
-<p>It chooses the vertex with minimum degree in the graph at each step of
-simulating Gaussian elimination process.
-
-<p>This implementation provided a number of enhancements
-including mass elimination, incomplete degree update, multiple
-elimination, and external degree. See&nbsp;[<A
-href="bibliography.html#George:evolution">35</a>] for a historical
-survey of the minimum degree algorithm.
-
-<p>
-An <b>elimination graph</b> <i>G<sub>v</sub></i> is obtained from the
-graph <i>G</i> by removing vertex <i>v</i> and all of its incident
-edges and by then adding edges to make all of the vertices adjacent to
-<i>v</i> into a clique (that is, add an edge between each pair of
-adjacent vertices if an edge doesn't already exist).
-
-Suppose that graph <i>G</i> is the graph representing the nonzero
-structure of a matrix <i>A</i>. Then performing a step of Guassian
-elimination on row <i>i</i> of matrix <i>A</i> is equivalent to
-
-
-
-
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 2001</TD><TD>
-<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.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>Example 示例</h3>见 <a href="../example/minimum_degree_ordering.cpp"><tt>example/minimum_degree_ordering.cpp</tt></a>.
+
+
+<h3>Implementation Notes 实现说明</h3>
+
+<p>建设中
+
+</p><p>在模拟高斯消去法过程的每一步中,选择最小度数的顶点。
+
+</p><p>该实现提供了一些增强,包括:大规模消去、不完整度数更新、多消去,以及 外部度。有关最小度算法的历史考察,请见[<a href="bibliography.html#George:evolution">35</a>]。
+
+</p><p><b>消去图</b> <i>G<sub>v</sub></i> 通过从图 <i>G</i> 中移除顶点 <i>v</i> 及其所有关联边,然后加入一些边令邻接于 +<i>v</i> 的顶点形成一个clique(即,对于这些邻接顶点中的每一对,如果它们之间 没有边的话,加入一条)而得到。假设图 <i>G</i> 是表示矩阵 <i>A</i> 的非零结构 的图。则在矩阵 <i>A</i> 的第 <i>i</i> 行执行一步高斯消去,相当于<br>
+</p><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright (c) 2001</td><td>
+<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.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/profile.htm   Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/profile.htm   Thu Aug 13 22:58:12 2009
@@ -1,44 +1,31 @@
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
-<!-- saved from url=(0050)http://www.boost.org/libs/graph/doc/bandwidth.html -->
-<HTML><HEAD><TITLE>Boost Graph Library: Bandwidth</TITLE>
-<META http-equiv=Content-Type content="text/html; charset=windows-1252"><!-- +<html><head><!-- saved from url=(0050)http://www.boost.org/libs/graph/doc/bandwidth.html --><title>Boost Graph Library: Bandwidth</title>
+<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><!--
   -- 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)
   -->
-<META content="MSHTML 6.00.2715.400" name=GENERATOR></HEAD>
-<BODY text=#000000 vLink=#551a8b aLink=#ff0000 link=#0000ee bgColor=#ffffff>
-<IMG SRC="../../../boost.png"
-     ALT="C++ Boost" width="277" height="86"> <BR>
-<H1><A name=sec:bandwidth></a><tt>profile</tt> </H1>
-<PRE>  (1)
-  template &lt;typename Graph&gt;
-  typename graph_traits&lt;Graph&gt;::vertices_size_type
-  profile(const Graph&amp; g)
-
-  (2)
-  template &lt;typename Graph, typename VertexIndexMap&gt;
-  typename graph_traits&lt;Graph&gt;::vertices_size_type
-  profile(const Graph&amp; g, VertexIndexMap index_map)
-</PRE>
-<p>The<b> profile</b> is the sum of all the maximum distances between the <i>i-th</i>
-  vertex and any of its neighbors with an index <i>j&gt;i</i>.</p>
-<p><BR>
-  <I>B(G) = max { |index[u] - index[v]|&nbsp;&nbsp;| (u,v) in E }</I><BR>
+<meta content="MSHTML 6.00.2715.400" name="GENERATOR"></head>
+
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277"> <br>
+<h1><a name="sec:bandwidth"></a><tt>profile</tt> </h1>
+<pre> (1)<br> template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> profile(const Graph&amp; g)<br><br> (2)<br> template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> profile(const Graph&amp; g, VertexIndexMap index_map)<br></pre> +<p><b>轮廓profile</b> 是指,第 <i>i-th</i> 顶点与其任一满足索引 <i>j&gt;i</i> 的邻接点间的最大距离之和。</p>
+<p><br>
+  <i>B(G) = max { |index[u] - index[v]|&nbsp;&nbsp;| (u,v) in E }</i><br>
 </p>
-<H3>Defined in</H3>
-<A
-href="http://www.boost.org/boost/graph/bandwidth.hpp";><TT>boost/graph/profile.hpp</TT></A>
-<BR>
-<HR>
-
-<TABLE width="677">
-  <TBODY>
-  <TR vAlign=top>
-    <TD noWrap>Copyright (c) 2001-2002</TD>
-    <TD>Marc Wintermantel, ETH Zurich (<A
- href="mailto:wintermantel@xxxxxxxxxxxxxxxxx";>wintermantel@xxxxxxxxxxxxxxxxx</a>)
-    </TD>
-  </TR></TBODY></TABLE></BODY></HTML>
+<h3>Defined in 定义于</h3>
+<a href="http://www.boost.org/boost/graph/bandwidth.hpp";><tt>boost/graph/profile.hpp</tt></a>
+<br>
+<hr>
+
+<table width="677">
+  <tbody>
+  <tr valign="top">
+    <td nowrap="nowrap">Copyright (c) 2001-2002</td>
+ <td>Marc Wintermantel, ETH Zurich (<a href="mailto:wintermantel@xxxxxxxxxxxxxxxxx";>wintermantel@xxxxxxxxxxxxxxxxx</a>)
+    </td>
+  </tr></tbody></table></body></html>
=======================================
--- /trunk/libs/graph/doc/sequential_vertex_coloring.html Mon Jun 1 21:27:33 2009 +++ /trunk/libs/graph/doc/sequential_vertex_coloring.html Thu Aug 13 22:58:12 2009
@@ -1,101 +1,55 @@
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html>
-<!--
+<html><head><meta content="text/html; charset=UTF-8" http-equiv="content-type"><!--
   -- Copyright (c) 2005 Trustees of Indiana University
   --
   -- Distributed under the Boost Software License, Version 1.0.
   -- (See accompanying file LICENSE_1_0.txt or copy at
   -- http://www.boost.org/LICENSE_1_0.txt)
   -->
-  <head>
-    <title>Boost Graph Library: Sequential Vertex Coloring</title>
-  </head>
+    <title>Boost Graph Library: Sequential Vertex Coloring</title></head>
+

   <body>
-    <IMG SRC="../../../boost.png"
-     ALT="C++ Boost" width="277" height="86">
-<h1><img src="figs/python.gif" alt="(Python)"/><tt>sequential_vertex_coloring</tt></h1>
+    <img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+<h1><img src="figs/python.gif" alt="(Python)"><tt>sequential_vertex_coloring</tt></h1>

     <p>
-    <pre>
-template&lt;class VertexListGraph, class OrderPA, class ColorMap&gt;
-typename property_traits&lt;ColorMap&gt;::value_type
-sequential_vertex_coloring(const VertexListGraph&amp; g, OrderPA order,
-                           ColorMap color);
-
-template&lt;class VertexListGraph, class ColorMap&gt;
-typename property_traits&lt;ColorMap&gt;::value_type
-sequential_vertex_coloring(const VertexListGraph&amp; g, ColorMap color);
-    </pre>
-
-<p>Computes a <a href="graph_coloring.html">vertex coloring</a> for
-the vertices in the graph, using a simple algorithm [<a
-href="bibliography.html#coleman83">59</a>]. Given vertices
-ordered v<sub>1</sub>, v<sub>2</sub>, ... , v<sub>n</sub>, for k = 1,
-2, ..., n the algorithm assigns v<sub>k</sub> to the smallest possible
-color. The algorithm does not guarantee an optimum coloring.
-
-<p>Here is the coloring that would be produced on a graph given the
-vertex ordering A, B, C, D, E.
-
-<p><img src="figs/sequential_vertex_coloring.png">,
-
-<h3>Where Defined</h3>
+ </p><pre>template&lt;class VertexListGraph, class OrderPA, class ColorMap&gt;<br>typename property_traits&lt;ColorMap&gt;::value_type<br>sequential_vertex_coloring(const VertexListGraph&amp; g, OrderPA order, <br> ColorMap color);<br><br>template&lt;class VertexListGraph, class ColorMap&gt;<br>typename property_traits&lt;ColorMap&gt;::value_type<br>sequential_vertex_coloring(const VertexListGraph&amp; g, ColorMap color);<br> </pre>
+
+<p>为图中的各顶点计算一个 <a href="graph_coloring.html">顶点着色方案 </a>,使用简单的算法[<a href="bibliography.html#coleman83">59</a>]。给定顺序 为 v<sub>1</sub>, v<sub>2</sub>, ... , v<sub>n</sub> 的顶点,对于 k = 1, +2, ..., n 该算法为 v<sub>k</sub> 赋值为最小的可能颜色。该算法不保证得到最优 的着色方案。
+
+</p><p>以下是以顶点顺序 A, B, C, D, E 处理一个图所得的着色方案。
+
+</p><p><img src="figs/sequential_vertex_coloring.png">,
+
+</p><h3>Where Defined 定义于</h3>
<a href="../../../boost/graph/sequential_vertex_coloring.hpp"><tt>boost/graph/sequential_vertex_coloring.hpp</tt></a>

-<h3>Parameters</h3>
+<h3>Parameters 参数</h3>
 IN: <tt>const Graph&amp; g</tt>
-<blockquote>
-  The graph object on which the algorithm will be applied.  The type
-  <tt>Graph</tt> must be a model of <a
-  href="VertexListGraph.html">Vertex List Graph</a> and <a
-  href="AdjacencyGraph.html">Adjacency Graph</a>.<br>
-<b>Python</b>: The parameter is named <tt>graph</tt>.
+<blockquote>该算法所应用的图对象。类型
+ <tt>Graph</tt> 必须符合 <a href="VertexListGraph.html">点列表图Vertex List Graph</a> 和 <a href="AdjacencyGraph.html">邻接图Adjacency Graph</a>。 <br>
+<b>Python</b>: 该参数名为 <tt>graph</tt>.
 </blockquote>

 OUT: <tt>ColorMap color</tt>
-<blockquote>
-  This property map records the colors of each vertex. It must be a
-  model of
-  <a href="../../property_map/WritablePropertyMap.html">Writeable
-  Property Map</a> whose key type is the same as the vertex descriptor
-  type of the graph and whose value type is an integral type that can
-  store all values of the graph's <tt>vertices_size_type</tt>.<br>
-  <b>Python</b>: Must be an <tt>vertex_int_map</tt> for the graph.
+<blockquote>该属性映射记录每个顶点的颜色。它必须符合 <a href="../../property_map/WritablePropertyMap.html">可写属性映射</a> 且其键类 型与图的顶点描述符类型相同,其值类型为可保存图的 <tt>vertices_size_type</tt> 的所有值的整数类型。<br>
+  <b>Python</b>: 必须是该图的一个 <tt>vertex_int_map</tt>。
 </blockquote>

 IN: <tt>OrderPA order</tt>
-<blockquote>
-  A mapping from integers in the range <em>[0, num_vertices(g))</em>
-  to the vertices of the graph.<br>
-
-  <b>Default:</b> A property map ordering the vertices in the same way
-  they are ordered by <tt>vertices(g)</tt>.<br>
-  <b>Python</b>: Unsupported parameter.
+<blockquote>从区间 <em>[0, num_vertices(g))</em>
+  中的整数至图的顶点的一个映射。<br>
+
+ <b>缺省值:</b>一个属性映射,以与 <tt>vertices(g)</tt> 相同的方式对顶点进 行排序。<br>
+  <b>Python</b>: 不支持该参数。
 </blockquote>

-<h3>Complexity</h3>
-
-The time complexity is <em>O(V(d+k))</em>, where <em>V</em> is the
-number of vertices, <em>d</em> is the maximum degree of the vertices
-in the graph, and <em>k</em> is the number of colors used.
-
-<h3>Example</h3>
-<pre>
-  typedef adjacency_list&lt;listS, vecS, undirectedS&gt; Graph;
-  typedef graph_traits&lt;Graph&gt;::vertex_descriptor vertex_descriptor;
-  typedef graph_traits&lt;Graph&gt;::vertices_size_type vertices_size_type;
- typedef property_map&lt;Graph, vertex_index_t&gt;::const_type vertex_index_map;
-
-  typedef std::pair&lt;int, int&gt; Edge;
-  enum nodes {A, B, C, D, E, n};
-  Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
-                        Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A),
-                        Edge(E, B) };
-  int m = sizeof(edge_array) / sizeof(Edge);
-  Graph g(edge_array, edge_array + m, n);
-
-  <em>// Test with the normal order</em>
+<h3>Complexity 复杂度</h3>时间复杂度为 <em>O(V(d+k))</em>,其中 <em>V</em> 为顶点数量,<em>d</em> 为图中各顶点的最大度数,<em>k</em> 为所用颜色数量。
+
+<h3>Example 示例</h3>
+<pre> typedef adjacency_list&lt;listS, vecS, undirectedS&gt; Graph;<br> typedef graph_traits&lt;Graph&gt;::vertex_descriptor vertex_descriptor;<br> typedef graph_traits&lt;Graph&gt;::vertices_size_type vertices_size_type;<br> typedef property_map&lt;Graph, vertex_index_t&gt;::const_type vertex_index_map;<br><br> typedef std::pair&lt;int, int&gt; Edge;<br> enum nodes {A, B, C, D, E, n};<br> Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E), <br> Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), <br> Edge(E, B) };<br> int m = sizeof(edge_array) / sizeof(Edge);<br> Graph g(edge_array, edge_array + m, n);<br><br> <em>// 以正常序列测试</em>
   std::vector&lt;vertices_size_type&gt; color_vec(num_vertices(g));
   iterator_property_map&lt;vertices_size_type*, vertex_index_map&gt;
     color(&amp;color_vec.front(), get(vertex_index, g));
@@ -104,13 +58,11 @@

     <hr>

-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 1997-2004</TD><TD>
-<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
-Indiana University (<A
-HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)<br>
-<A HREF="http://www.boost.org/people/doug_gregor.html";>Douglas Gregor</A>, Indiana University (dgregor -at- cs.indiana.edu)</A>)
-</TD></TR></TABLE>
-  </body>
-</html>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright (c) 1997-2004</td><td>
+<a href="http://www.osl.iu.edu/%7Elums";>Andrew Lumsdaine</a>,
+Indiana University (<a href="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</a>)<br> +<a href="http://www.boost.org/people/doug_gregor.html";>Douglas Gregor</a>, Indiana University (dgregor -at- cs.indiana.edu))
+</td></tr></tbody></table>
+  </body></html>
=======================================
--- /trunk/libs/graph/doc/sloan_ordering.htm    Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/sloan_ordering.htm    Thu Aug 13 22:58:12 2009
@@ -1,224 +1,104 @@
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
-<!-- saved from url=(0063)http://www.boost.org/libs/graph/doc/cuthill_mckee_ordering.html -->
-<HTML><HEAD><TITLE>Boost Graph Library: Sloan Ordering</TITLE>
-<META http-equiv=Content-Type content="text/html; charset=windows-1252"><!-- +<html><head><!-- saved from url=(0063)http://www.boost.org/libs/graph/doc/cuthill_mckee_ordering.html --><title>Boost Graph Library: Sloan Ordering</title>
+<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><!--
   -- 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)
   -->
-<META content="MSHTML 6.00.2715.400" name=GENERATOR></HEAD>
-<BODY text=#000000 vLink=#551a8b aLink=#ff0000 link=#0000ee bgColor=#ffffff>
-<IMG SRC="../../../boost.png"
-     ALT="C++ Boost" width="277" height="86"> <BR>
-<H1><A name=sec:bfs></a><tt>sloan_ordering</tt></H1>
-<P>
-<DIV align=left>
-<TABLE cellPadding=3 border=1>
-  <TBODY>
-  <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>color, degree, current_degree, priority</TD>
-    </TR>
-  <TR>
-    <TH align=left><B>Complexity:</B></TH>
- <TD align=left>time: <I>O(log(m)|E|)</I> where <I>m = max { degree(v) | v
-      in V }</I> </TD></TR></TBODY></TABLE></DIV>
-<PRE>  (1)
-  template &lt;class Graph, class OutputIterator,
-                  class ColorMap, class DegreeMap,
-                  class PriorityMap, class Weight&gt;
-  OutputIterator
-  sloan_ordering(Graph&amp; g,
-                 typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
-                 typename graph_traits&lt;Graph&gt;::vertex_descriptor e,
-                 OutputIterator permutation,
-                 ColorMap color,
-                 DegreeMap degree,
-                 PriorityMap priority,
-                 Weight W1,
-                 Weight W2 )
-
-  (2)
-   template &lt;class Graph, class OutputIterator,
-                  class ColorMap, class DegreeMap,
-                  class PriorityMap, class Weight&gt;
-  OutputIterator
-  sloan_ordering(Graph&amp; g,
-                 OutputIterator permutation,
-                 ColorMap color,
-                 DegreeMap degree,
-                 PriorityMap priority,
-                 Weight W1,
-                 Weight W2 )
-
-
-(3)
- template &lt;class Graph, class OutputIterator,
-                  class ColorMap, class DegreeMap,
-                  class PriorityMap&gt;
-  OutputIterator
-  sloan_ordering(Graph&amp; g,
-                 typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
-                 typename graph_traits&lt;Graph&gt;::vertex_descriptor e,
-                 OutputIterator permutation,
-                 ColorMap color,
-                 DegreeMap degree,
-                 PriorityMap priority )
-
-
-(4)
- template &lt;class Graph, class OutputIterator,
-                  class ColorMap, class DegreeMap,
-                  class PriorityMap&gt;
-  OutputIterator
-  sloan_ordering(Graph&amp; g,
-                 OutputIterator permutation,
-                 ColorMap color,
-                 DegreeMap degree,
-                 PriorityMap priority )</PRE>
-<p>The goal of the Sloan ordering algorithm[1, 2] is to reduce the profile and - the wavefront of a graph by reordering the indices assigned to each vertex. - The Sloan algorithm needs a start and an end vertex. These vertices can be asigned - manually. But there is also an algorithm sloan_starting_nodes that provides - usually quite good start and end vertices. Each vertex is asigned with a priority. - This priority is a weighted sum of the distance of the vector to the end vertex - (a global criterion) and is called the current degree of vertex. This current - degree basically reflects the status of the renumbering in the neighborhood - of a vertex (a local criterion). Therefore the Sloan algorithm (in contrast - to-McKee) takes into account local as well as global criteria for the renumbering - sequence. One can play around with the relative weights, but the default values - proposed by Sloan (weight1/weight2=1/2) turn out to be pretty good in most cases.
-</p>
-<P>Version 1 of the algorithm lets the user choose the start- and end-vertex whereas - version 2 finds a good starting vertex using the already mentioned sloan_starting_node - algorithm. The choice of these vertices can have a significant effect on the - quality of the ordering. Version 3 and 4 are identical to version 1 and 2 respectively,
-  except that for the weights the standard weights W1=1 and W2=2 are used.
-<P>The output of the algorithm are the vertices in the new ordering. Depending - on what kind of output iterator you use, you can get either the Sloan ordering - or the reverse Sloan ordering. For example, if you store the output into a vector - using the vector's reverse iterator, then you get the reverse Sloan ordering.
-<PRE>  std::vector&lt;vertex_descriptor&gt; inv_perm(num_vertices(G));
-  sloan_ordering(G, inv_perm.rbegin());
-</PRE>
-<P>Either way, storing the output into a vector gives you the permutation from
-the new ordering to the old ordering. <PRE>  inv_perm[new_index[u]] == u
-</PRE>
-<P>Sometimes, it is the opposite permutation that you want, the permutation from
+<meta content="MSHTML 6.00.2715.400" name="GENERATOR"></head>
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277"> <br>
+<h1><a name="sec:bfs"></a><tt>sloan_ordering</tt></h1>
+<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">color, degree, current_degree, priority</td>
+    </tr>
+  <tr>
+    <th align="left"><b>复杂度:</b></th>
+ <td align="left">时间:<i>O(log(m)|E|)</i> 其中 <i>m = max { degree(v) | v
+      in V }</i> </td></tr></tbody></table></div>
+<pre> (1)<br> template &lt;class Graph, class OutputIterator,<br> class ColorMap, class DegreeMap, <br> class PriorityMap, class Weight&gt;<br> OutputIterator<br> sloan_ordering(Graph&amp; g,<br> typename graph_traits&lt;Graph&gt;::vertex_descriptor s,<br> typename graph_traits&lt;Graph&gt;::vertex_descriptor e,<br> OutputIterator permutation, <br> ColorMap color, <br> DegreeMap degree, <br> PriorityMap priority, <br> Weight W1, <br> Weight W2 )<br><br> (2)<br> template &lt;class Graph, class OutputIterator,<br> class ColorMap, class DegreeMap, <br> class PriorityMap, class Weight&gt;<br> OutputIterator<br> sloan_ordering(Graph&amp; g,<br> OutputIterator permutation, <br> ColorMap color, <br> DegreeMap degree, <br> PriorityMap priority, <br> Weight W1, <br> Weight W2 )<br><br><br>(3)<br> template &lt;class Graph, class OutputIterator,<br> class ColorMap, class DegreeMap, <br> class PriorityMap&gt;<br> OutputIterator<br> sloan_ordering(Graph&amp; g,<br> typename graph_traits&lt;Graph&gt;::vertex_descriptor s,<br> typename graph_traits&lt;Graph&gt;::vertex_descriptor e,<br> OutputIterator permutation, <br> ColorMap color, <br> DegreeMap degree, <br> PriorityMap priority )<br><br><br>(4)<br> template &lt;class Graph, class OutputIterator,<br> class ColorMap, class DegreeMap, <br> class PriorityMap&gt;<br> OutputIterator<br> sloan_ordering(Graph&amp; g,<br> OutputIterator permutation, <br> ColorMap color, <br> DegreeMap degree, <br> PriorityMap priority )</pre> +<p>Sloan 排序算法[1, 2]的目的是通过重排各个顶点的索引值来减少一个图的轮廓和 波前。Sloan
+算法需要一个开始顶点和一个结束顶点。这些顶点可以手工赋值。不过也有一个算法
+sloan_starting_nodes
+可以提供非常好的开始和结束顶点。每个顶点被赋予一个优先级。这个优先级是该顶 点至结束顶点距离的一个加权和(全局指标),被称为顶点的当前度 +current degree。这个当前度基本上反映了在一个顶点的邻接点间的重编号状态(局部 指标)。因此,Sloan +算法(与McKee算法相反)统筹考虑局部和全局的指标,来对序列进行重编号。你可以使 用相对权重,不过 Sloan
+提供的缺省值(weight1/weight2=1/2)已被证明在大多数情况下是非常好的。 </p>
+<p>该算法的版本1让用户选择开始和结束顶点,而版本2则使用前面提到的 sloan_starting_node + 算法来找出一个好的开始顶点。这些顶点的选择对于排序的质量有重要影响。版本 3和4分别等同于版本1和2,除了使用标准权重 W1=1 和 W2=2。 +</p><p>该算法的输出是按新顺序排列的顶点。取决于你用的是哪种输出迭代器,你可 以获得 Sloan 序或逆 Sloan 序。例如,如果你使用一个 vector
+  的反向迭代器来将输出保存到该 vector,则你就得到逆 Sloan 序。
+</p><pre> std::vector&lt;vertex_descriptor&gt; inv_perm(num_vertices(G));<br> sloan_ordering(G, inv_perm.rbegin());<br></pre> +<p>另一方面,将输出保存在vector中给了你从新顺序到旧顺序的排列。</p><pre> inv_perm[new_index[u]] == u<br></pre> +<p>有时,这是你想要的是反向排列,即从旧索引到新索引的排列。这可以按以下方法 很容易地计算得到。 +</p><p>Sometimes, it is the opposite permutation that you want, the permutation from the old index to the new index. This can easily be computed in the following
   way.
-<PRE>  for (size_type i = 0; i != inv_perm.size(); ++i)
-    perm[old_index[inv_perm[i]]] = i;
-</PRE>
-<p>Usually you need the reversed ordering with the Cuthill-McKee algorithm and
-  the direct ordering with the Sloan algorithm.</p>
-<H3>Parameters</H3>
-For version 1:
-<UL>
-  <LI><TT>Graph&amp; g</TT> &nbsp;(IN) <BR>
-    An undirected graph. The graph's type must be a model of <A
-  href="./IncidenceGraph.html">IncidenceGraph</a>.
-  <LI><TT>vertex_descriptor s</TT> &nbsp;(IN) <BR>
-    The starting vertex.
-  <LI><tt>vertex_descriptor e</tt>&nbsp;(IN)<br>
-    The ending vertex<br>
-  <LI><TT>OutputIterator permutation</TT> &nbsp;(OUT) <BR>
-    The new vertex ordering. The vertices are written to the <a
- href="http://www.sgi.com/tech/stl/OutputIterator.html";>output iterator</a> in
-    their new order.
-  <LI><TT>ColorMap color_map</TT> &nbsp;(WORK) <BR>
- Used internally to keep track of the progress of the algorithm (to avoid visiting
-    the same vertex twice).
-  <LI><tt>PriorityMap priority_map</tt> &nbsp;(IN)<br>
- Used internally to store the priority for renumbering of each vertex. </LI>
-  <LI><TT>DegreeMap degree_map</TT> &nbsp;(IN) <BR>
-    This must map vertices to their degree. </LI>
-  <LI><tt>Weight W1 &amp; W2</tt> &nbsp;(IN) <br>
-    Heuristical weights for the Sloan algorithm. </LI>
-</UL>
-<p>For version 2: </p>
+</p><pre> for (size_type i = 0; i != inv_perm.size(); ++i)<br> perm[old_index[inv_perm[i]]] = i;<br></pre> +<p>通常,你需要 Cuthill-McKee 算法的反向顺序,以及 Sloan 算法的正向顺序。 </p>
+<h3>Parameters 参数</h3>对于版本1:
 <ul>
-  <li><tt>Graph&amp; g</tt> &nbsp;(IN) <br>
-    An undirected graph. The graph's type must be a model of <a
-  href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
-  <li><tt>OutputIterator permutation</tt> &nbsp;(OUT) <br>
-    The new vertex ordering. The vertices are written to the <a
- href="http://www.sgi.com/tech/stl/OutputIterator.html";>output iterator</a> in
-    their new order.
-  <li><tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
- Used internally to keep track of the progress of the algorithm (to avoid visiting
-    the same vertex twice).
-  <li><tt>PriorityMap priority_map</tt> &nbsp;(IN)<br>
- Used internally to store the priority for renumbering of each vertex. </li>
-  <li><tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>
-    This must map vertices to their degree. </li>
-  <li><tt>Weight W1 &amp; W2</tt> &nbsp;(IN) <br>
-    Heuristical weights for the Sloan algorithm. </li>
+ <li><tt>Graph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类型必须符合 <a href="./IncidenceGraph.html">关联图IncidenceGraph</a>。
+  </li><li><tt>vertex_descriptor s</tt> &nbsp;(IN) <br>开始顶点。
+  </li><li><tt>vertex_descriptor e</tt>&nbsp;(IN)<br>结束顶点。<br>
+ </li><li><tt>OutputIterator permutation</tt> &nbsp;(OUT) <br>新的顶点顺 序。这些顶点被按它们的新顺序写出到 <a href="http://www.sgi.com/tech/stl/OutputIterator.html";>输出迭代器</a>。
+  </li><li><tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
+  在内部使用,以跟踪算法的处理过程(避免重复访问同一个顶点两次)。
+  </li><li><tt>PriorityMap priority_map</tt> &nbsp;(IN)<br>
+  在内部使用,以保存每个顶点重编号的优先级。 </li>
+ <li><tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>它必须将顶点映射至它们的 度数。 </li> + <li><tt>Weight W1 &amp; W2</tt> &nbsp;(IN) <br>用于 Sloan 算法的启发式权 重。 </li>
 </ul>
-<p>For version 3: </p>
+<p>对于版本2: </p>
 <ul>
-  <li><tt>Graph&amp; g</tt> &nbsp;(IN) <br>
-    An undirected graph. The graph's type must be a model of <a
-  href="./IncidenceGraph.html">IncidenceGraph</a>.
-  <li><tt>vertex_descriptor s</tt> &nbsp;(IN) <br>
-    The starting vertex.
-  <li><tt>vertex_descriptor e</tt>&nbsp;(IN)<br>
-    The ending vertex<br>
-  <li><tt>OutputIterator permutation</tt> &nbsp;(OUT) <br>
-    The new vertex ordering. The vertices are written to the <a
- href="http://www.sgi.com/tech/stl/OutputIterator.html";>output iterator</a> in
-    their new order.
-  <li><tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
- Used internally to keep track of the progress of the algorithm (to avoid visiting
-    the same vertex twice).
-  <li><tt>PriorityMap priority_map</tt> &nbsp;(IN)<br>
- Used internally to store the priority for renumbering of each vertex. </li>
-  <li><tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>
-    This must map vertices to their degree. </li>
-</ul>
-<p>For version 4: </p>
+ <li><tt>Graph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类型必须符合 <a href="IncidenceGraph.html">关联图IncidenceGraph</a>。 </li><li><tt>OutputIterator permutation</tt> &nbsp;(OUT) <br>新的顶点顺序。 这些顶点被按它们的新顺序写出到 <a href="http://www.sgi.com/tech/stl/OutputIterator.html";>输出迭代器</a>。
+  </li><li><tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
+  在内部使用,以跟踪算法的处理过程(避免重复访问同一个顶点两次)。
+  </li><li><tt>PriorityMap priority_map</tt> &nbsp;(IN)<br>
+ 在内部使用,以保存每个顶点重编号的优先级。 </li><li><tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>它必须将顶点映射至它们的度数。 </li><li><tt>Weight W1 &amp; W2</tt> &nbsp;(IN) <br>用于 Sloan 算法的启发式 权重。</li></ul>
+<p>对于版本3: </p>
 <ul>
-  <li><tt>Graph&amp; g</tt> &nbsp;(IN) <br>
-    An undirected graph. The graph's type must be a model of <a
-  href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
-  <li><tt>OutputIterator permutation</tt> &nbsp;(OUT) <br>
-    The new vertex ordering. The vertices are written to the <a
- href="http://www.sgi.com/tech/stl/OutputIterator.html";>output iterator</a> in
-    their new order.
-  <li><tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
- Used internally to keep track of the progress of the algorithm (to avoid visiting
-    the same vertex twice).
-  <li><tt>PriorityMap priority_map</tt> &nbsp;(IN)<br>
- Used internally to store the priority for renumbering of each vertex. </li>
-  <li><tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>
-    This must map vertices to their degree. </li>
-</ul>
+ <li><tt>Graph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类型必须符合 <a href="IncidenceGraph.html">关联图IncidenceGraph</a>。
+  </li><li><tt>vertex_descriptor s</tt> &nbsp;(IN) <br>开始顶点。
+  </li><li><tt>vertex_descriptor e</tt>&nbsp;(IN)<br>结束顶点。<br>
+ </li><li><tt>OutputIterator permutation</tt> &nbsp;(OUT) <br>新的顶点顺 序。这些顶点被按它们的新顺序写出到 <a href="http://www.sgi.com/tech/stl/OutputIterator.html";>输出迭代器</a>。
+  </li><li><tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
+  在内部使用,以跟踪算法的处理过程(避免重复访问同一个顶点两次)。
+  </li><li><tt>PriorityMap priority_map</tt> &nbsp;(IN)<br>
+ 在内部使用,以保存每个顶点重编号的优先级。 </li><li><tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>它必须将顶点映射至它们的度数。</li></ul>
+<p>对于版本4: </p>
+<ul>
+ <li><tt>Graph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类型必须符合 <a href="IncidenceGraph.html">关联图IncidenceGraph</a>。 </li><li><tt>OutputIterator permutation</tt> &nbsp;(OUT) <br>新的顶点顺序。 这些顶点被按它们的新顺序写出到 <a href="http://www.sgi.com/tech/stl/OutputIterator.html";>输出迭代器</a>。
+  </li><li><tt>ColorMap color_map</tt> &nbsp;(WORK) <br>
+  在内部使用,以跟踪算法的处理过程(避免重复访问同一个顶点两次)。
+  </li><li><tt>PriorityMap priority_map</tt> &nbsp;(IN)<br>
+ 在内部使用,以保存每个顶点重编号的优先级。 </li><li><tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>它必须将顶点映射至它们的度数。</li></ul>
 <p>&nbsp;</p>
-<H3>Example</H3>
-See <A
-href="../example/sloan_ordering.cpp"><TT>example/sloan_ordering.cpp</TT></A>.
-<H3>See Also</H3>
+<h3>Example 示例</h3>见&nbsp;<a href="../example/sloan_ordering.cpp"><tt>example/sloan_ordering.cpp</tt></a>.
+<h3>See Also 参见</h3>
 <p><a href="./sloan_start_end_vertices.htm">sloan_start_end_vertices</a>,
-  <A
-href="./bandwidth.html">bandwidth</a>, <a href="./profile.htm">profile</a>, <a href="./wavefront.htm">wavefront</a> - and <TT>degree_property_map</TT> in <TT>boost/graph/properties.hpp</TT>. </p> + <a href="./bandwidth.html">bandwidth</a>, <a href="./profile.htm">profile</a>, <a href="./wavefront.htm">wavefront</a> 和 <tt>boost/graph/properties.hpp</tt> 中的 <tt>degree_property_map</tt>。 </p> <p>[1] S. W. Sloan, <i>An algorithm for profile and wavefront reduction of sparse matrices</i>, Int. j. numer. methods eng., <b>23</b>, 239 - 251 (1986)</p> <p>[2] S. W. Sloan, <i>A fortran program for profile and wavefront reduction</i>,
-  Int. j. numer. methods eng., <b>28</b>, 2651 - 2679 (1989)<BR>
+  Int. j. numer. methods eng., <b>28</b>, 2651 - 2679 (1989)<br>
 </p>
-<HR>
-
-<TABLE width="718">
-  <TBODY>
-  <TR vAlign=top>
-    <TD noWrap>Copyright (c) 2001-2002</TD>
-    <TD>Marc Wintermantel, ETH Zurich (<A
- href="mailto:wintermantel@xxxxxxxxxxxxxxxxx";>wintermantel@xxxxxxxxxxxxxxxxx</a>)
-    </TD>
-  </TR></TBODY></TABLE></BODY></HTML>
+<hr>
+
+<table width="718">
+  <tbody>
+  <tr valign="top">
+    <td nowrap="nowrap">Copyright (c) 2001-2002</td>
+ <td>Marc Wintermantel, ETH Zurich (<a href="mailto:wintermantel@xxxxxxxxxxxxxxxxx";>wintermantel@xxxxxxxxxxxxxxxxx</a>)
+    </td>
+  </tr></tbody></table></body></html>
=======================================
--- /trunk/libs/graph/doc/sloan_start_end_vertices.htm Mon Mar 30 07:58:04 2009 +++ /trunk/libs/graph/doc/sloan_start_end_vertices.htm Thu Aug 13 22:58:12 2009
@@ -1,86 +1,63 @@
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
-<!-- saved from url=(0063)http://www.boost.org/libs/graph/doc/cuthill_mckee_ordering.html -->
-<HTML><HEAD><TITLE>Boost Graph Library: Cuthill-Mckee Ordering</TITLE>
-<META http-equiv=Content-Type content="text/html; charset=windows-1252"><!-- +<html><head><!-- saved from url=(0063)http://www.boost.org/libs/graph/doc/cuthill_mckee_ordering.html --><title>Boost Graph Library: Cuthill-Mckee Ordering</title>
+<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><!--
   -- 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)
   -->
-<META content="MSHTML 6.00.2715.400" name=GENERATOR></HEAD>
-<BODY text=#000000 vLink=#551a8b aLink=#ff0000 link=#0000ee bgColor=#ffffff><IMG
-height=86 alt="C++ Boost"
-src="../../../boost.png" width=277>
-<BR>
-<H1><A name=sec:bfs></a><tt>sloan_start_end_vertices</tt></H1>
-<P>
-<DIV align=left>
-<TABLE cellPadding=3 border=1>
-  <TBODY>
-  <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>color, degree</TD>
-    </TR>
-  <TR>
-    <TH align=left><B>Complexity:</B></TH>
-      <TD align=left>&nbsp;</TD>
-    </TR></TBODY></TABLE></DIV>
-<PRE>  (1)
-  template &lt;class Graph, class ColorMap, class DegreeMap&gt;
-  typename graph_traits&lt;Graph&gt;::vertex_descriptor
-  sloan_start_end_vertices(Graph&amp; G,
- typename graph_traits&lt;Graph&gt;::vertex_descriptor &amp;s,
-                           ColorMap color,
-                           DegreeMap degree )
-</PRE>
-<p>The goal of the sloan_start_end_vertices algorithm[1, 2] is to find good start- - and end-vertices for the profile and wavefront reduction algorithm sloan_ordering. - The algorithm is similar to pseudo_peripheral_pair and also based on breadth_first_search. - With this breadth_first_search function a so-called rooted level structure (RLS) - is formed, where the vertices with the same distance to the starting vertex - are grouped together. The maximum number of vertices in one group is called - the width of the RLS. Sloan_start_end_vertices tries to find a pseudoperipheral
-  pair with a minimum RLS-width.</p>
-<H3>Parameters</H3>
-For version 1:
-<UL>
-  <LI><TT>Graph&amp; g</TT> &nbsp;(IN) <BR>
-    An undirected graph. The graph's type must be a model of <A
- href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html";>IncidenceGraph</A>.
-  <LI><TT>vertex_descriptor s</TT> &nbsp;(IN) <BR>
-    The starting vertex.
-  <LI><TT>ColorMap color_map</TT> &nbsp;(WORK) <BR>
- Used internally to keep track of the progress of the algorithm (to avoid visiting
-    the same vertex twice).
-  <LI><TT>DegreeMap degree_map</TT> &nbsp;(IN) <BR>
-    This must map vertices to their degree. </LI>
-</UL>
+<meta content="MSHTML 6.00.2715.400" name="GENERATOR"></head>
+
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b"><img alt="C++ Boost" src="../../../boost.png" height="86" width="277">
+<br>
+<h1><a name="sec:bfs"></a><tt>sloan_start_end_vertices</tt></h1>
+<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">color, degree</td>
+    </tr>
+  <tr>
+    <th align="left"><b>复杂度</b></th>
+      <td align="left">&nbsp;</td>
+    </tr></tbody></table></div>
+<pre> (1)<br> template &lt;class Graph, class ColorMap, class DegreeMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertex_descriptor<br> sloan_start_end_vertices(Graph&amp; G,<br> typename graph_traits&lt;Graph&gt;::vertex_descriptor &amp;s,<br> ColorMap color, <br> DegreeMap degree )<br></pre> +<p>sloan_start_end_vertices 算法[1, 2]的目标是,为轮廓及波前压缩算法 sloan_ordering +查找一个好的开始和结束顶点。该算法类似于 pseudo_peripheral_pair,也是基于 breadth_first_search
+的。通过这个 breadth_first_search
+函数,会形成一个所谓的有根分层结构(RLS),其中距开始顶点相同距离的顶点被组织 在一起。在同一个组中的顶点的最大数量被称为该RLS的宽度。
+Sloan_start_end_vertices 尝试找出具有最小RLS-宽度的一对伪边缘。&nbsp;</p>
+<h3>Parameters 参数</h3>对于版本1:
+<ul>
+ <li><tt>Graph&amp; g</tt> &nbsp;(IN) <br>一个无向图。图的类型必须符合 <a href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html";>关联图 IncidenceGraph</a>。
+  </li><li><tt>vertex_descriptor s</tt> &nbsp;(IN) <br>开始顶点。
+ </li><li><tt>ColorMap color_map</tt> &nbsp;(WORK) <br>内部使用,以跟踪算 法的处理过程(避免访问同一个顶点两次)。 + </li><li><tt>DegreeMap degree_map</tt> &nbsp;(IN) <br>必须将顶点映射至它 们的度数。 </li>
+</ul>
 <p>&nbsp;</p>
-<H3>Example</H3>
-See <A
-href="http://www.boost.org/libs/graph/example/cuthill_mckee_ordering.cpp";><TT>example/sloan_ordering.cpp</TT></A>.
-<H3>See Also</H3>
+<h3>Example 示例</h3>见 <a href="http://www.boost.org/libs/graph/example/cuthill_mckee_ordering.cpp";><tt>example/sloan_ordering.cpp</tt></a>.
+<h3>See Also 参见</h3>
<p><a href="http://www.boost.org/libs/graph/doc/sloan_start_end_vertices.htm";>sloan_start_end_vertices</a>,
-  <A
-href="http://www.boost.org/libs/graph/doc/bandwidth.html";>bandwidth</A>, <a href="http://www.boost.org/libs/graph/doc/profile.htm";>profile</a>, - <a href="http://www.boost.org/libs/graph/doc/wavefront.htm";>wavefront</a> and
-  <TT>degree_property_map</TT> in <TT>boost/graph/properties.hpp</TT>. </p>
+ <a href="http://www.boost.org/libs/graph/doc/bandwidth.html";>bandwidth</a>, <a href="http://www.boost.org/libs/graph/doc/profile.htm";>profile</a>, + <a href="http://www.boost.org/libs/graph/doc/wavefront.htm";>wavefront</a> 和 <tt>boost/graph/properties.hpp</tt> 中的
+  <tt>degree_property_map</tt>。 </p>
<p>[1] S. W. Sloan, <i>An algorithm for profile and wavefront reduction of sparse matrices</i>, Int. j. numer. methods eng., <b>23</b>, 239 - 251 (1986)</p> <p>[2] S. W. Sloan, <i>A fortran program for profile and wavefront reduction</i>,
-  Int. j. numer. methods eng., <b>28</b>, 2651 - 2679 (1989)<BR>
+  Int. j. numer. methods eng., <b>28</b>, 2651 - 2679 (1989)<br>
 </p>
-<HR>
-
-<TABLE width="663">
-  <TBODY>
-  <TR vAlign=top>
-    <TD noWrap>Copyright (c) 2001-2002</TD>
-    <TD>Marc Wintermantel, ETH Zurich(<A
- href="mailto:wintermantel@xxxxxxxxxxxxxxxxx";>wintermantel@xxxxxxxxxxxxxxxxx</a>)
-    </TD>
-  </TR></TBODY></TABLE></BODY></HTML>
+<hr>
+
+<table width="663">
+  <tbody>
+  <tr valign="top">
+    <td nowrap="nowrap">Copyright (c) 2001-2002</td>
+ <td>Marc Wintermantel, ETH Zurich(<a href="mailto:wintermantel@xxxxxxxxxxxxxxxxx";>wintermantel@xxxxxxxxxxxxxxxxx</a>)
+    </td>
+  </tr></tbody></table></body></html>
=======================================
--- /trunk/libs/graph/doc/topological_sort.html Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/topological_sort.html Thu Aug 13 22:58:12 2009
@@ -1,156 +1,93 @@
-<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: Topological Sort</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:topological-sort">
-<img src="figs/python.gif" alt="(Python)"/>
-<TT>topological_sort</TT>
-</H1>
-
-<PRE>
-template &lt;typename VertexListGraph, typename OutputIterator,
-          typename P, typename T, typename R&gt;
-void topological_sort(VertexListGraph&amp; g, OutputIterator result,
- const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
-</PRE>
-
-<P>
-The topological sort algorithm creates a linear ordering of the
-vertices such that if edge <i>(u,v)</i> appears in the graph, then
-<i>v</i> comes before <i>u</i> in the ordering. The graph must be a
-directed acyclic graph (DAG). The implementation consists mainly of a
-call to <a
-href="./depth_first_search.html"><tt>depth_first_search()</tt></a>.
+<title>Boost Graph Library: Topological Sort</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:topological-sort">
+<img src="figs/python.gif" alt="(Python)">
+<tt>topological_sort</tt>
+</a></h1>
+
+<pre><a name="sec:topological-sort">template &lt;typename VertexListGraph, typename OutputIterator,<br> typename P, typename T, typename R&gt;<br>void topological_sort(VertexListGraph&amp; g, OutputIterator result,<br> const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)<br></a></pre>
+
+<p>
+<a name="sec:topological-sort">拓朴排序算法创建各顶点的一个线性顺序,满足如 果边 <i>(u,v)</i> 出现在图中,则在此顺序中 +<i>v</i> 出现在 <i>u</i> 之前。该图必须是一个有向无环图(DAG)。该实现主要是 对 </a><a href="./depth_first_search.html"><tt>depth_first_search()</tt></a> 的调用。
 </p>

-<h3>Where Defined:</h3>
-<a href="../../../boost/graph/topological_sort.hpp"><TT>boost/graph/topological_sort.hpp</TT></a>
-
-<h3>Parameters</h3>
+<h3>Where Defined 定义于</h3>
+<a href="../../../boost/graph/topological_sort.hpp"><tt>boost/graph/topological_sort.hpp</tt></a>
+
+<h3>Parameters 参数</h3>

 IN: <tt>VertexListGraph&amp; g</tt>
-<blockquote>
-  A directed acylic graph (DAG). The graph type must
-  be a model of <a href="./VertexListGraph.html">Vertex List Graph</a>
-  and <a href="./IncidenceGraph.html">Incidence Graph</a>.
- If the graph is not a DAG then a <a href="./exception.html#not_a_dag"><tt>not_a_dag</tt></a>
-  exception will be thrown and the
-  user should discard the contents of <tt>result</tt> range.<br>
-  <b>Python</b>: The parameter is named <tt>graph</tt>.
+<blockquote>一个有向无环图(DAG)。图的类型必须符合 <a href="./VertexListGraph.html">点列表图Vertex List Graph</a> 和 <a href="./IncidenceGraph.html">关联图Incidence Graph</a>。如果该图不是DAG,则 会抛出一个 <a href="./exception.html#not_a_dag"><tt>not_a_dag</tt></a>
+  异常,且用户应忽略所得区间的内容。<br>
+  <b>Python</b>: 该参数名为 <tt>graph</tt>.
 </blockquote>

 OUT: <tt>OutputIterator result</tt>
-<blockquote>
-The vertex descriptors of the graph will be output to the
-<TT>result</TT> output iterator in <b>reverse</b> topological order.  The
-iterator type must model <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 the vertices in topological order is
-returned.
+<blockquote>图的顶点描述符将被以<span style="font-weight: bold;">逆 </span>拓朴顺序输出至 +<tt>result</tt> 输出迭代器。该迭代器类型必须符合 <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>

 UTIL/OUT: <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">颜色值</a>。<br>
+
+
+ <b>缺省值:</b>一个 <a href="http://alai04.kmip.net/boost_doc/libs/property_map/iterator_property_map.html";> + <tt>iterator_property_map</tt></a>,创建自一个大小为 &nbsp;<tt>num_vertices(g)</tt> 的 <tt>default_color_type</tt> 的 <tt>std::vector</tt>,且以 <tt>i_map</tt> 作为索引映射。&nbsp;<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>
-
-The time complexity is <i>O(V + E)</i>.
-
-
-<H3>Example</H3>
-
-<P>
-Calculate a topological ordering of the vertices.
-
-<P>
-<PRE>
- typedef adjacency_list&lt; vecS, vecS, directedS, color_property&lt;&gt; &gt; Graph;
-  typedef boost::graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
-  Pair edges[6] = { Pair(0,1), Pair(2,4),
-                    Pair(2,5),
-                    Pair(0,3), Pair(1,4),
-                    Pair(4,3) };
-  Graph G(6, edges, edges + 6);
-
-  typedef std::vector&lt; Vertex &gt; container;
-  container c;
-  topological_sort(G, std::back_inserter(c));
-
-  cout &lt;&lt; "A topological ordering: ";
-  for ( container::reverse_iterator ii=c.rbegin(); ii!=c.rend(); ++ii)
-    cout &lt;&lt; index(*ii) &lt;&lt; " ";
-  cout &lt;&lt; endl;
-</PRE>
-The output is:
-<PRE>
-  A topological ordering: 2 5 0 1 4 3
-</PRE>
+<h3>Complexity 复杂度</h3>时间复杂度为 <i>O(V + E)</i>.
+
+
+<h3>Example 示例</h3>
+
+<p>计算顶点的拓朴顺序。
+
+</p><p>
+</p><pre> typedef adjacency_list&lt; vecS, vecS, directedS, color_property&lt;&gt; &gt; Graph;<br> typedef boost::graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;<br> Pair edges[6] = { Pair(0,1), Pair(2,4),<br> Pair(2,5),<br> Pair(0,3), Pair(1,4),<br> Pair(4,3) };<br> Graph G(6, edges, edges + 6);<br><br> typedef std::vector&lt; Vertex &gt; container;<br> container c;<br> topological_sort(G, std::back_inserter(c));<br><br> cout &lt;&lt; "A topological ordering: ";<br> for ( container::reverse_iterator ii=c.rbegin(); ii!=c.rend(); ++ii)<br> cout &lt;&lt; index(*ii) &lt;&lt; " ";<br> cout &lt;&lt; endl;<br></pre>输出为:
+<pre>  A topological ordering: 2 5 0 1 4 3<br></pre>


 <br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 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 (c) 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/transitive_closure.html       Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/transitive_closure.html       Thu Aug 13 22:58:12 2009
@@ -1,223 +1,133 @@
-<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 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: Transitive Closure</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:transitive_closure">
-<img src="figs/python.gif" alt="(Python)"/>
-<TT>transitive_closure</TT>
-</H1>
-
-<P>
-<PRE>
-template &lt;typename Graph, typename GraphTC,
-  typename P, typename T, typename R&gt;
-void transitive_closure(const Graph&amp; g, GraphTC&amp; tc,
-  const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
-
-template &lt;typename Graph, typename GraphTC,
-  typename G_to_TC_VertexMap, typename VertexIndexMap&gt;
-void transitive_closure(const Graph&amp; g, GraphTC&amp; tc,
- G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)
-</PRE>
-
-The transitive closure of a graph <i>G = (V,E)</i> is a graph <i>G* =
-(V,E*)</i> such that <i>E*</i> contains an edge <i>(u,v)</i> if and
-only if <i>G</i> contains a <a
-href="graph_theory_review.html#def:path">path</a> (of at least one
-edge) from <i>u</i> to <i>v</i>. The <tt>transitive_closure()</tt>
-function transforms the input graph <tt>g</tt> into the transitive
-closure graph <tt>tc</tt>.
-
-<p>
-Thanks to Vladimir Prus for the implementation of this algorithm!
+<title>Boost Graph Library: Transitive Closure</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:transitive_closure">
+<img src="figs/python.gif" alt="(Python)">
+<tt>transitive_closure</tt>
+</a></h1>
+
+<p>
+</p><pre><a name="sec:transitive_closure">template &lt;typename Graph, typename GraphTC,<br> typename P, typename T, typename R&gt;<br>void transitive_closure(const Graph&amp; g, GraphTC&amp; tc,<br> const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)<br><br>template &lt;typename Graph, typename GraphTC,<br> typename G_to_TC_VertexMap, typename VertexIndexMap&gt;<br>void transitive_closure(const Graph&amp; g, GraphTC&amp; tc,<br> G_to_TC_VertexMap g_to_tc_map, VertexIndexMap index_map)<br></a></pre>
+
+<a name="sec:transitive_closure">图 <i>G = (V,E)</i> 的传递闭包是指一个图 <i>G* = +(V,E*)</i>,其中 <i>E*</i> 包含边 <i>(u,v)</i> 当且仅当 <i>G</i> 有一条从 <i>u</i> 到 <i>v</i> 的 </a><a href="graph_theory_review.html#def:path">路径 </a>(至少一条边)。函数 <tt>transitive_closure()</tt>
+将输入图 <tt>g</tt> 转变为它的传递闭包图 <tt>tc</tt>。
+
+<p>感谢 Vladimir Prus 提供了本算法的实现!
+


-
-<H3>Where Defined</H3>
-
-<P>
-<a href="../../../boost/graph/transitive_closure.hpp"><TT>boost/graph/transitive_closure.hpp</TT></a>
-
-<h3>Parameters</h3>
+</p><h3>Where Defined 定义于</h3>
+
+<p>
+<a href="../../../boost/graph/transitive_closure.hpp"><tt>boost/graph/transitive_closure.hpp</tt></a>
+
+</p><h3>Parameters 参数</h3>

 IN: <tt>const Graph&amp; g</tt>
-<blockquote>
- A directed graph, where the <tt>Graph</tt> type must model the
- <a href="./VertexListGraph.html">Vertex List Graph</a>
- and <a href="./AdjacencyGraph.html">Adjacency Graph</a> concepts.<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="./AdjacencyGraph.html">邻接图Adjacency Graph</a> 概念。<b>Python</b>: 该参数名为 <tt>graph</tt>.
 </blockquote>

 OUT: <tt>GraphTC&amp; tc</tt>
-<blockquote>
- A directed graph, where the <tt>GraphTC</tt> type must model the
- <a href="./VertexMutableGraph.html">Vertex Mutable Graph</a>
- and <a href="./EdgeMutableGraph.html">Edge Mutable Graph</a> concepts.<br>
-
- <b>Python</b>: This parameter is not used in Python. Instead, a new
- graph of the same type is returned.
+<blockquote>一个有向图,其中 <tt>GraphTC</tt> 类型必须符合 <a href="./VertexMutableGraph.html">点可变图Vertex Mutable Graph</a> 和 <a href="./EdgeMutableGraph.html">边可变图Edge Mutable Graph</a> 概念。<br>
+
+ <b>Python</b>: 该参数在Python中未用。而是返回一个相同类型的新图。
 </blockquote>

-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>

 UTIL/OUT: <tt>orig_to_copy(G_to_TC_VertexMap g_to_tc_map)</tt>
-<blockquote>
-  This maps each vertex in the input graph to the new matching
-  vertices in the output transitive closure graph.<br>
-
-  <b>Python</b>: This must be a <tt>vertex_vertex_map</tt> of the graph.
+<blockquote>它将输入图的每个顶点映射至输出的传递闭包图的新的匹配顶点。<br>
+
+  <b>Python</b>: 它必须是该图的一个 <tt>vertex_vertex_map</tt>。
 </blockquote>

 IN: <tt>vertex_index_map(VertexIndexMap&amp; index_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="../../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>
-
-The time complexity (worst-case) is <i>O(|V||E|)</i>.
-
-<h3>Example</h3>
-
-The following is the graph from the example <tt><a
-href="../example/transitive_closure.cpp">example/transitive_closure.cpp</a></tt>
-and the transitive closure computed by the algorithm.
+<h3>Complexity 复杂度</h3>时间复杂度(最坏情况)为 <i>O(|V||E|)</i>.
+
+<h3>Example 示例</h3>以下是来自于例子 <tt><a href="../example/transitive_closure.cpp">example/transitive_closure.cpp</a></tt>
+的图,以及由本算法计算得到的传递闭包。

 <table>
-  <tr>
-    <td><img src="tc.gif" width="173" height="264" ></td>
-    <td><img src="tc-out.gif" width="200" height="360"></td>
+  <tbody><tr>
+    <td><img src="tc.gif" height="264" width="173"></td>
+    <td><img src="tc-out.gif" height="360" width="200"></td>
   </tr>
-</table>
+</tbody></table>


-<h3>Implementation Notes</h3>
-
-<p>
-The algorithm used to implement the <tt>transitive_closure()</tt>
-function is based on the detection of strong components[<a
-href="bibliography.html#nuutila95">50</a>, <a
-href="bibliography.html#purdom70">53</a>]. The following discussion
-describes the algorithm (and some relevant background theory).
-
-<p>
-A <a name="def:successor-set"><i><b>successor set</b></i></a> of a
-vertex <i>v</i>, denoted by <i>Succ(v)</i>, is the set of vertices
-that are <a
-href="graph_theory_review.html#def:reachable">reachable</a> from
-vertex <i>v</i>. The set of vertices adjacent to <i>v</i> in the
-transitive closure <i>G*</i> is the same as the successor set of
-<i>v</i> in the original graph <i>G</i>. Computing the transitive
-closure is equivalent to computing the successor set for every vertex
-in <i>G</i>.
-
-<p>
-All vertices in the same strong component have the same successor set
-(because every vertex is reachable from all the other vertices in the
-component). Therefore, it is redundant to compute the successor set
-for every vertex in a strong component; it suffices to compute it for
-just one vertex per component.
-
-<p>
-The following is the outline of the algorithm:
-
-<ol>
-<li>Compute <a
-href="strong_components.html#def:strongly-connected-component">strongly
-connected components</a> of the graph.
-
-<li> Construct the condensation graph.  A <a
-name="def:condensation-graph"><i><b>condensation graph</b></i></a> is
-a a graph <i>G'=(V',E')</i> based on the graph <i>G=(V,E)</i> where
-each vertex in <i>V'</i> corresponds to a strongly connected component
-in <i>G</i> and edge <i>(u,v)</i> is in <i>E'</i> if and only if there
-exists an edge in <i>E</i> connecting any of the vertices in the
-component of <i>u</i> to any of the vertices in the component of
-<i>v</i>.
-
-<li> Compute transitive closure on the condensation graph.
-  This is done using the following algorithm:
-<pre>
- for each vertex u in G' in reverse topological order
-   for each vertex v in Adj[u]
-     if (v not in Succ(u))
- Succ(u) = Succ(u) U { v } U Succ(v) // &quot;U&quot; means set union
-</pre>
-  The vertices are considered in reverse topological order to
-  ensure that the when computing the successor set for a vertex
-  <i>u</i>, the successor set for each vertex in <i>Adj[u]</i>
-  has already been computed.
-
-  <p>An optimized implementation of the set union operation improves
-   the performance of the algorithm. Therefore this implementation
-   uses <a name="def:chain-decomposition"><i><b>chain
-   decomposition</b></i></a> [<a
-   href="bibliography.html#goral79">51</a>,<a
-   href="bibliography.html#simon86">52</a>]. The vertices of <i>G</i>
-   are partitioned into chains <i>Z<sub>1</sub>, ...,
-   Z<sub>k</sub></i>, where each chain <i>Z<sub>i</sub></i> is a path
-   in <i>G</i> and the vertices in a chain have increasing topological
-   number.  A successor set <i>S</i> is then represented by a
-   collection of intersections with the chains, i.e., <i>S =
-   U<sub>i=1...k</sub> (Z<sub>i</sub> &amp; S)</i>. Each intersection
-   can be represented by the first vertex in the path
-   <i>Z<sub>i</sub></i> that is also in <i>S</I>, since the rest of
-   the path is guaranteed to also be in <i>S</i>. The collection of
-   intersections is therefore represented by a vector of length
-   <i>k</i> where the ith element of the vector stores the first
-   vertex in the intersection of <i>S</i> with <i>Z<sub>i</sub></i>.
-
-   <p>Computing the union of two successor sets, <i>S<sub>3</sub> =
-   S<sub>1</sub> U S<sub>2</sub></i>, can then be computed in
-   <i>O(k)</i> time with the following operation:
-<pre>
-  for i = 0...k
- S3[i] = min(S1[i], S2[i]) // where min compares the topological number of the vertices
-</pre>
-
-<li>Create the graph <i>G*</i> based on the transitive closure of
- the condensation graph <i>G'*</i>.
-
-</ol>
+<h3>Implementation Notes 实现说明</h3>
+
+<p>用于实现 <tt>transitive_closure()</tt>
+函数的算法是基于强连通分支的检测的[<a href="bibliography.html#nuutila95">50</a>, <a href="bibliography.html#purdom70">53</a>]。以下的讨论描述了该算法(及一些相关 背景理论)。
+
+</p><p>顶点 <i>v</i> 的 <a name="def:successor-set"><i><b>后继集successor set</b></i></a>,记为 <i>Succ(v)</i>,是指从顶点 <i>v</i> <a href="graph_theory_review.html#def:reachable">可达</a> 的顶点的集合。在传递 闭包 <i>G*</i> 中邻接于 <i>v</i> 的顶点集,与原图 <i>G</i> 中
+<i>v</i> 的后继集相同。计算传递闭包等价于计算 <i>G</i> 中每个顶点的后继集。
+
+</p><p>同一个强连通分支中的所有顶点具有相同的后继集(因为每个顶点都是从本分 支的所有其它顶点可达的)。因此,为同一个强连通分支中的每个顶点计算后续集是多 余的;只要为每个分支计算一个顶点就足够了。
+
+</p><p>以下是该算法的大概:
+
+</p><ol>
+<li>计算该图的 <a href="strong_components.html#def:strongly-connected-component">强连通分支 </a>。
+
+</li><li>构造压缩图。<a name="def:condensation-graph"><i><b>压缩图 condensation graph</b></i></a> 是指一个基于图 <i>G=(V,E)</i> 的图 <i>G'=(V',E')</i>,其中 <i>V'</i> 中的每个顶点对应于 <i>G</i> 中的一个强连通 分支,<i>E'</i> 中的边 <i>(u,v)</i> 当且仅当 <i>E</i> 中有一条边连接 <i>u</i> 对应的分支中的任一顶点至
+<i>v</i> 对应的分支中的任一顶点。
+
+</li><li>计算压缩图的传递闭包。用以下算法完成:
+<pre> for each vertex u in G' in reverse topological order<br> for each vertex v in Adj[u]<br> if (v not in Succ(u))<br> Succ(u) = Succ(u) U { v } U Succ(v) // "U" 表示并集<br></pre>以反拓朴顺序处理各顶 点,可确保在计算顶点
+  <i>u</i> 的后继集时,<i>Adj[u]</i>
+  中各顶点的后继集已完成计算。
+
+ <p>并集操作的优化实现可以提高该算法的性能。因此该实现使用了 <a name="def:chain-decomposition"><i><b>链分解chain + decomposition</b></i></a> [<a href="bibliography.html#goral79">51</a>,<a href="bibliography.html#simon86">52</a>]。<i>G</i>
+   的顶点被分至链 <i>Z<sub>1</sub>, ...,
+ Z<sub>k</sub></i> 中,其中每个链 <i>Z<sub>i</sub></i> 是 <i>G</i> 中的一 条路径,且链中的顶点具有递增的拓朴序号。然后可以用与这些链的交集的组合来表示 一个后继集 <i>S</i>,即 <i>S =
+   U<sub>i=1...k</sub> (Z<sub>i</sub> &amp; S)</i>。每个交集可以由路径
+ <i>Z<sub>i</sub></i> 中第一个同时也属于 <i>S</i> 的顶点来代表,因为路径 中的剩余顶点保证也是属于 <i>S</i>。因此这些交集的组合可以由一个长度为 + <i>k</i> 的向量来表示,其中该向量中第 i 个元素保存了 <i>S</i> 与 <i>Z<sub>i</sub></i> 的交集的第一个顶点。
+
+   </p><p>计算两个后继集的并集,<i>S<sub>3</sub> =
+   S<sub>1</sub> U S<sub>2</sub></i>,可以在
+   <i>O(k)</i> 时间内用以下操作计算:
+</p><pre> for i = 0...k<br> S3[i] = min(S1[i], S2[i]) // 其中 min 用于 比较顶点的拓朴序号<br></pre>
+
+</li><li>基于压缩图 <i>G'*</i> 的传递闭包创建图 <i>G*</i>。
+
+</li></ol>

 <br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>, Indiana Univ.(<A HREF="mailto:jsiek@xxxxxxxxxxxxxx";>jsiek@xxxxxxxxxxxxxx</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+<hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright (c) 2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>, Indiana Univ.(<a href="mailto:jsiek@xxxxxxxxxxxxxx";>jsiek@xxxxxxxxxxxxxx</a>)
+</td></tr></tbody></table>
+
+</body></html>
=======================================
--- /trunk/libs/graph/doc/transpose_graph.html  Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/transpose_graph.html  Thu Aug 13 22:58:12 2009
@@ -1,127 +1,88 @@
-<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: Transpose Graph</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
-        ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
-     ALT="C++ Boost" width="277" height="86">
-
-<BR Clear>
-
-<H1><TT>transpose_graph</TT></H1>
-
-<PRE>
-template &lt;class <a href="./VertexListGraph.html">VertexListGraph</a>, class <a href="./MutableGraph.html">MutableGraph</a>&gt;
-void transpose_graph(const VertexListGraph&amp; G, MutableGraph&amp; G_T,
- const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
-</PRE>
-
-<P>
-This function computes the transpose of a directed graph. The
-transpose of a directed graph <i>G = (V, E)</i>is the graph
-<i>G<sup>T</sup> = (V, E<sup>T</sup>)</i> , where <i>E<sup>T</sup> =
-{(v, u) in V x V: (u, v) in E}</i> . i.e., <i>G<sup>T</sup></i> is
-<i>G</i> with all its edges reversed.  Graph <TT>G_T</TT> passed into
-the algorithm must have no vertices and
-no edges. The vertices and edges will be added by <tt>transpose_graph()</tt> by
-calling <tt>add_vertex</tt> and  <tt>add_edge</tt> as follows for each edge
-<i>(u,v)</i> in <tt>G</tt>.
-
-<H3>Example</H3>
-
-Here's an example of transposing a graph:
-<a href="../example/transpose-example.cpp"><tt>example/transpose-example.cpp</tt></a>.
-
-<H3>Where Defined</H3>
-
-<P>
-<a href="../../../boost/graph/transpose_graph.hpp"><TT>boost/graph/transpose_graph.hpp</TT></a>
-
-<P>
-
-<H3>Parameters</H3>
+<title>Boost Graph Library: Transpose Graph</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>transpose_graph</tt></h1>
+
+<pre>template &lt;class <a href="./VertexListGraph.html">VertexListGraph</a>, class <a href="./MutableGraph.html">MutableGraph</a>&gt; <br>void transpose_graph(const VertexListGraph&amp; G, MutableGraph&amp; G_T,<br> const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)<br></pre>
+
+<p>该函数计算一个有向图的转置。有向图 <i>G = (V, E)</i> 的转置是指图
+<i>G<sup>T</sup> = (V, E<sup>T</sup>)</i>,其中 <i>E<sup>T</sup> =
+{(v, u) in V x V: (u, v) in E}</i> . 即,<i>G<sup>T</sup></i> 将
+<i>G</i> 的所有边反向。传入该算法的图 <tt>G_T</tt> 必须没有顶点和边。它的顶 点和边将由 <tt>transpose_graph()</tt> 通过调用 <tt>add_vertex</tt> 和 <tt>add_edge</tt> 根据 <tt>G</tt> 中的每条边
+<i>(u,v)</i> 加进去。
+
+</p><h3>Example 示例</h3>以下是对一个图进行转置的例子:<a href="../example/transpose-example.cpp"><tt>example/transpose-example.cpp</tt></a>.
+
+<h3>Where Defined 定义于</h3>
+
+<p>
+<a href="../../../boost/graph/transpose_graph.hpp"><tt>boost/graph/transpose_graph.hpp</tt></a>
+
+</p><p>
+
+</p><h3>Parameters 参数</h3>

 IN: <tt>const VertexListGraph&amp; G</tt>
-<blockquote>
-A directed graph. The graph type must be a model of <a href="./VertexListGraph.html">Vertex List Graph</a>. +<blockquote>一个有向图。图的类型必须符合 <a href="./VertexListGraph.html">点列表图Vertex List Graph</a>。
 </blockquote>

 OUT: <tt>const MutableGraph&amp; G_T</tt>
-<blockquote>
-The transposed graph.  The graph type must be a model of <a
-href="./MutableGraph.html">Mutable Graph</a>.
+<blockquote>转置后的图。图的类型必须符合 <a href="./MutableGraph.html">可变 图Mutable Graph</a>。
 </blockquote>

-<h3>Named Parameters</h3>
+<h3>Named Parameters 命名参数</h3>

 IN: <tt>vertex_copy(VertexCopier vc)</tt>
-<blockquote>
-This is a <a href="http://www.sgi.com/tech/stl/BinaryFunction.html";>Binary Function</a> that copies the properties of a vertex in the original graph
-into the corresponding vertex in the copy.<br>
-
-<b>Default:</b> <tt>vertex_copier&lt;VertexListGraph, MutableGraph&gt;</tt>
-which uses the property tag <tt>vertex_all</tt> to access a property
-map from the graph.
+<blockquote>这是一个 <a href="http://www.sgi.com/tech/stl/BinaryFunction.html";>二元函数</a>,将原图 的顶点属性复制至拷贝中的对应顶点。<br>
+
+<b>缺省值:</b><tt>vertex_copier&lt;VertexListGraph, MutableGraph&gt;</tt>,它使用属性标签 <tt>vertex_all</tt> 来访问图的属性映 射。
+
 </blockquote>

 IN: <tt>edge_copy(EdgeCopier ec)</tt>
-<blockquote>
-This is a <a href="http://www.sgi.com/tech/stl/BinaryFunction.html";>Binary Function</a> that copies the properties of an edge in the original graph
-into the corresponding edge in the copy.<br>
-
-<b>Default:</b> <tt>edge_copier&lt;VertexListGraph, MutableGraph&gt;</tt>
-which uses the property tag <tt>edge_all</tt> to access a property
-map from the graph.
+<blockquote>这是一个 <a href="http://www.sgi.com/tech/stl/BinaryFunction.html";>二元函数</a>,将原图 的边属性复制至拷贝中的对应边。<br>
+
+<b>缺省值:</b><tt>edge_copier&lt;VertexListGraph, MutableGraph&gt;</tt>,它使用属性标签&nbsp;<tt>edge</tt><tt>_all</tt> 来访问 图的属性映射。&nbsp;
 </blockquote>

 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
-<blockquote>
-The vertex index map type must be a model of <a
-href="../../property_map/ReadablePropertyMap.html">Readable Property
-Map</a> and must map the vertex descriptors of <tt>G</tt> to the
-integers from 0 to <tt>num_vertices(G)</tt>.<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>顶点索引映射类型必须符合 <a href="../../property_map/ReadablePropertyMap.html">可读属性映射</a>,且必须 将 <tt>G</tt> 的顶点描述符映射至&nbsp;<tt>0 到 num_vertices(G))</tt>&nbsp;的 整数。<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>


 UTIL/OUT: <tt>orig_to_copy(Orig2CopyMap c)</tt>
-<blockquote>
-This maps vertices in the original graph to vertices in the copy.
-
-<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 output graph's vertex descriptor type of size
-  <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
-  map.
+<blockquote>它将原图中的顶点映射至拷贝中的顶点。<br><b>缺省值:</b>一个 &nbsp;<a href="../../property_map/iterator_property_map.html"> + iterator_property_map</a>,创建自一个大小为 &nbsp;<tt>num_vertices(g)</tt> 的输出图的边描述符类型的 <tt>std::vector</tt>,且以 <tt>i_map</tt> 作为索引映射。&nbsp;
 </blockquote>

-<H3>Complexity</H3>
-
-<P>
-The time complexity is <i>O(V + E)</i>.
+<h3>Complexity 复杂度</h3>
+
+<p>时间复杂度为 <i>O(V + E)</i>.



 <br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 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><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright (c) 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/wavefront.htm Mon Mar 30 07:58:04 2009
+++ /trunk/libs/graph/doc/wavefront.htm Thu Aug 13 22:58:12 2009
@@ -1,78 +1,52 @@
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
-<!-- saved from url=(0050)http://www.boost.org/libs/graph/doc/wavefront.html -->
-<HTML><HEAD><TITLE>Boost Graph Library: Wavefront</TITLE>
-<META http-equiv=Content-Type content="text/html; charset=windows-1252"><!-- +<html><head><!-- saved from url=(0050)http://www.boost.org/libs/graph/doc/wavefront.html --><title>Boost Graph Library: Wavefront</title>
+<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><!--
   -- 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)
   -->
-<META content="MSHTML 6.00.2715.400" name=GENERATOR></HEAD>
-<BODY text=#000000 vLink=#551a8b aLink=#ff0000 link=#0000ee bgColor=#ffffff>
-<IMG SRC="../../../boost.png"
-     ALT="C++ Boost" width="277" height="86"> <BR>
-<H1><A name=sec:wavefront></a><tt>ith_wavefront</tt> </H1>
-<PRE>  (1)
- template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> ith_wavefront(typename graph_traits&lt;Graph&gt;::vertex_descriptor i,<br> const Graph&amp; g)
-
-  (2)
- template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> ith_wavefront(typename graph_traits&lt;Graph&gt;::vertex_descriptor i,<br> const Graph&amp; g,<br> VertexIndexMap index)</PRE>
+<meta content="MSHTML 6.00.2715.400" name="GENERATOR"></head>
+
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277"> <br>
+<h1><a name="sec:wavefront"></a><tt>ith_wavefront</tt> </h1>
+<pre> (1)<br> template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> ith_wavefront(typename graph_traits&lt;Graph&gt;::vertex_descriptor i,<br> const Graph&amp; g)<br><br> (2)<br> template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> ith_wavefront(typename graph_traits&lt;Graph&gt;::vertex_descriptor i,<br> const Graph&amp; g,<br> VertexIndexMap index)</pre>
 <p>&nbsp;</p>
-<p>Calculates the wavefront of the <i>ith</i>-vertex.<BR>
-  <BR>
+<p>计算第<i>ith</i>-顶点的波前wavefront。<br>
+  <br>
 </p>
-<H3>Defined in</H3>
-<A
-href="http://www.boost.org/boost/graph/wavefront.hpp";><TT>boost/graph/wavefront.hpp</TT></A>
-<HR>
-
-<H1><A name=sec:ith-wavefront></a><tt>max_wavefront</tt></H1>
-<PRE>  (1)
- template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> max_wavefront(const Graph&amp; g)
-
-  (2)
- template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> max_wavefront(const Graph&amp; g, VertexIndexMap index)</PRE>
-Calculates the maximum wavefront a graph.<BR>
-<BR>
-<H3>Defined in</H3>
-<p><A
-href="http://www.boost.org/boost/graph/wavefront.hpp";><TT>boost/graph/wavefront.hpp</TT></A>
+<h3>Defined in 定义于</h3>
+<a href="http://www.boost.org/boost/graph/wavefront.hpp";><tt>boost/graph/wavefront.hpp</tt></a>
+<hr>
+
+<h1><a name="sec:ith-wavefront"></a><tt>max_wavefront</tt></h1>
+<pre> (1)<br> template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> max_wavefront(const Graph&amp; g)<br><br> (2)<br> template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> max_wavefront(const Graph&amp; g, VertexIndexMap index)</pre>计算一个图的最大波前。<br>
+<br>
+<h3>Defined in 定义于</h3>
+<p><a href="http://www.boost.org/boost/graph/wavefront.hpp";><tt>boost/graph/wavefront.hpp</tt></a>
 </p>
 <hr>
-<h1><a name=sec:ith-wavefront></a><tt>aver_wavefront</tt></h1>
-<pre>  (1)
- template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> aver_wavefront(const Graph&amp; g)
-
-  (2)
- template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> aver_wavefront(const Graph&amp; g, VertexIndexMap index)</pre> -Calculates the average wavefront of a graph (sum of all wavefronts devided by
-the number ob vertices).<br>
+<h1><a name="sec:ith-wavefront"></a><tt>aver_wavefront</tt></h1>
+<pre> (1)<br> template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> aver_wavefront(const Graph&amp; g)<br><br> (2)<br> template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> aver_wavefront(const Graph&amp; g, VertexIndexMap index)</pre>计算一个图的平均波前(所有波前的总和 除以顶点数量)。<br>
 <br>
-<h3>Defined in</h3>
-<a
-href="http://www.boost.org/boost/graph/wavefront.hpp";><tt>boost/graph/wavefront.hpp</tt></a>
-<p><BR>
+<h3>Defined in 定义于</h3>
+<a href="http://www.boost.org/boost/graph/wavefront.hpp";><tt>boost/graph/wavefront.hpp</tt></a>
+<p><br>
 </p>
 <hr>
-<h1><a name=sec:ith-wavefront></a><tt>rms_wavefront</tt></h1>
-<pre>  (1)
- template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> rms_wavefront(const Graph&amp; g)
-
-  (2)
- template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> rms_wavefront(const Graph&amp; g, VertexIndexMap index)</pre>
-Calculates the root mean square of all wavefronts.<br>
+<h1><a name="sec:ith-wavefront"></a><tt>rms_wavefront</tt></h1>
+<pre> (1)<br> template &lt;typename Graph&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> rms_wavefront(const Graph&amp; g)<br><br> (2)<br> template &lt;typename Graph, typename VertexIndexMap&gt;<br> typename graph_traits&lt;Graph&gt;::vertices_size_type<br> rms_wavefront(const Graph&amp; g, VertexIndexMap index)</pre>计算所有波前的均方根。<br>
 <br>
-<h3>Defined in</h3>
-<a
-href="http://www.boost.org/boost/graph/wavefront.hpp";><tt>boost/graph/wavefront.hpp</tt></a>
+<h3>Defined in 定义于</h3>
+<a href="http://www.boost.org/boost/graph/wavefront.hpp";><tt>boost/graph/wavefront.hpp</tt></a>
 <p>&nbsp; </p>
-<HR>
-<TABLE>
-  <TBODY>
-  <TR vAlign=top>
-    <TD noWrap>Copyright (c) 2001-2002</TD>
-    <TD>Marc Wintermantel, ETH Zurich(<A
- href="mailto:wintermantel@xxxxxxxxxxxxxxxxx";>wintermantel@xxxxxxxxxxxxxxxxx</a>)
-    </TD>
-  </TR></TBODY></TABLE></BODY></HTML>
+<hr>
+<table>
+  <tbody>
+  <tr valign="top">
+    <td nowrap="nowrap">Copyright (c) 2001-2002</td>
+ <td>Marc Wintermantel, ETH Zurich(<a href="mailto:wintermantel@xxxxxxxxxxxxxxxxx";>wintermantel@xxxxxxxxxxxxxxxxx</a>)
+    </td>
+  </tr></tbody></table></body></html>

Other related posts:

  • » [boost-doc-zh] r286 committed - graph 库文档第21.3.5-21.3.15节 - codesite-noreply