[boost-doc-zh commit] r280 - graph 库文档第10-13章
- From: codesite-noreply@xxxxxxxxxx
- To: boost-doc-zh-notify@xxxxxxxxxxxxx
- Date: Wed, 08 Jul 2009 16:05:46 +0000
Author: alai04
Date: Wed Jul 8 07:54:49 2009
New Revision: 280
Modified:
trunk/libs/graph/doc/AdjacencyGraph.html
trunk/libs/graph/doc/BidirectionalGraph.html
trunk/libs/graph/doc/EdgeListGraph.html
trunk/libs/graph/doc/Graph.html
trunk/libs/graph/doc/IncidenceGraph.html
trunk/libs/graph/doc/MutableGraph.html
trunk/libs/graph/doc/MutablePropertyGraph.html
trunk/libs/graph/doc/PropertyGraph.html
trunk/libs/graph/doc/VertexAndEdgeListGraph.html
trunk/libs/graph/doc/VertexListGraph.html
trunk/libs/graph/doc/constructing_algorithms.html
trunk/libs/graph/doc/graph_concepts.html
trunk/libs/graph/doc/leda_conversion.html
trunk/libs/graph/doc/python.html
trunk/libs/graph/doc/table_of_contents.html
trunk/libs/libraries.htm
Log:
graph 库文档第10-13章
Modified: trunk/libs/graph/doc/AdjacencyGraph.html
==============================================================================
--- trunk/libs/graph/doc/AdjacencyGraph.html (original)
+++ trunk/libs/graph/doc/AdjacencyGraph.html Wed Jul 8 07:54:49 2009
@@ -1,168 +1,101 @@
-<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>AdjacencyGraph</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<title>AdjacencyGraph</title></head>
-<BR Clear>
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+<br clear="">
-<H2><A NAME="concept:AdjacencyGraph"></A>
-AdjacencyGraph
-</H2>
-The AdjacencyGraph concept provides and interface for efficient access
-of the adjacent vertices to a vertex in a graph. This is quite similar
-to the <a href="./IncidenceGraph.html">IncidenceGraph</a> concept (the
-target of an out-edge is an adjacent vertex). Both concepts are
-provided because in some contexts there is only concern for the
-vertices, whereas in other contexts the edges are also important.
+<h2><a name="concept:AdjacencyGraph"></a>
+AdjacencyGraph 邻接图
+</h2>邻接图(AdjacencyGraph)概念提供了一个接口，用以对图中的某个顶点的邻接顶
点进行高效的访问。这与 <a href="./IncidenceGraph.html">关联图
IncidenceGraph</a> 的概念非常相似(一条出边的目标就是一个邻接顶点)。同时提供
这两个概念是因为，在某些上下文中，只需要关心顶点，而在另一些正文中，边也是相
当重要的。
-<H3>Refinement of</H3>
+<h3>Refinement of 精化自</h3>
-<a href="Graph.html">Graph</a>
+<a href="Graph.html">图Graph</a>
-<h3>Notation</h3>
+<h3>Notation 记号</h3>
-<Table>
-<TR>
-<TD><tt>G</tt></TD>
-<TD>A type that is a model of Graph.</TD>
-</TR>
+<table>
+<tbody><tr>
+<td><tt>G</tt></td>
+<td>一个以 Graph 为模的类型。</td>
+</tr>
-<TR>
-<TD><tt>g</tt></TD>
-<TD>An object of type <tt>G</tt>.</TD>
-</TR>
+<tr>
+<td><tt>g</tt></td>
+<td>一个类型为 <tt>G</tt> 的对象。</td>
+</tr>
-<TR>
-<TD><tt>v</tt></TD>
-<TD>An object of type
<tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
-</TR>
+<tr>
+<td><tt>v</tt></td>
+<td>一个类型为 <tt>boost::graph_traits<G>::vertex_descriptor</tt> 的
对象。</td>
+</tr>
-</table>
+</tbody></table>
-<H3>Associated Types</H3>
+<h3>Associated Types 关联类型</h3>
-<Table border>
+<table border="1">
-<tr>
-<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br>
- This tag type must be convertible to <tt>adjacency_graph_tag</tt>.
+<tbody><tr>
+<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br>这个标
签类型必须可转换为 <tt>adjacency_graph_tag</tt>.
</td>
</tr>
-<TR>
-<TD><pre>boost::graph_traits<G>::adjacency_iterator</pre>
-An adjacency iterator for a vertex <i>v</i> provides access to the
-vertices adjacent to <i>v</i>. As such, the value type of an
-adjacency iterator is the vertex descriptor type of its graph. An
-adjacency iterator must meet the requirements of <a
-href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
-</TD>
-</TR>
-
-</table>
+<tr>
+<td><pre>boost::graph_traits<G>::adjacency_iterator</pre>顶点
<i>v</i> 的邻接迭代器提供了对邻接于 <i>v</i> 的顶点的访问。因此，邻接迭代器
的值类型应为图的顶点描述类型。邻接迭代器必须满足 <a
href="../../utility/MultiPassInputIterator.html">多遍输入迭代器
MultiPassInputIterator</a> 的要求。
+</td>
+</tr>
-<h3>Valid Expressions</h3>
+</tbody></table>
+<h3>Valid Expressions 有效表达式</h3>
-<table border>
-<tr>
-<td><a
name="sec:adjacent-vertices"><TT>adjacent_vertices(v, g)</TT></a></TD>
-<TD>
-Returns an iterator-range providing access to the vertices adjacent to
-vertex <TT>v</TT> in graph <TT>g</TT>.<a
-href="#1">[1]</a>
+<table border="1">
-<br> Return type:
-<TT>std::pair<adjacency_iterator, adjacency_iterator></TT>
-</TD>
-</TR>
+<tbody><tr>
+<td><a
name="sec:adjacent-vertices"><tt>adjacent_vertices(v, g)</tt></a></td>
+<td>返回一个迭代器区间，提供对图 <tt>g</tt> 中与顶点 <tt>v</tt> 相邻接的顶
点的访问。<tt></tt><a href="#1">[1]</a>
-</table>
+<br>返回类
型：<tt>std::pair<adjacency_iterator, adjacency_iterator></tt>
+</td>
+</tr>
-<H3>Complexity guarantees</H3>
+</tbody></table>
-The <TT>adjacent_vertices()</TT> function must return in constant time.
+<h3>Complexity guarantees 复杂度保证</h3><tt>adjacent_vertices()</tt> 函数
必须在常数时间内返回。
-<H3>See Also</H3>
+<h3>See Also 参见</h3>
-<a href="./graph_concepts.html">Graph concepts</a>,
+<a href="./graph_concepts.html">图概念 Graph concepts</a>,
<a href="./adjacency_iterator.html"><tt>adjacency_iterator</tt></a>
-<H3>Concept Checking Class</H3>
+<h3>Concept Checking Class 概念检查类</h3>
-<PRE>
- template <class G>
- struct AdjacencyGraphConcept
- {
- typedef typename boost::graph_traits<G>::adjacency_iterator
- adjacency_iterator;
- void constraints() {
- function_requires< IncidenceGraphConcept<G> >();
- function_requires<
MultiPassInputIteratorConcept<adjacency_iterator> >();
-
- p = adjacent_vertices(v, g);
- v = *p.first;
- const_constraints(g);
- }
- void const_constraints(const G& g) {
- p = adjacent_vertices(v, g);
- }
- std::pair<adjacency_iterator,adjacency_iterator> p;
- typename boost::graph_traits<G>::vertex_descriptor v;
- G g;
- };
-</PRE>
-
-<h3>Design Rationale</h3>
-
-The AdjacencyGraph concept is somewhat frivolous since <a
-href="./IncidenceGraph.html">IncidenceGraph</a> really covers the same
-functionality (and more). The AdjacencyGraph concept exists because
-there are situations when <tt>adjacent_vertices()</tt> is more
-convenient to use than <tt>out_edges()</tt>. If you are constructing a
-graph class and do not want to put in the extra work of creating an
-adjacency iterator, have no fear. There is an adaptor class named <a
-href="./adjacency_iterator.html"> <tt>adjacency_iterator</tt></a> that
-you can use to create an adjacency iterator out of an out-edge
-iterator.
-
-<h3>Notes</h3>
-
-<a name="1">[1]</a> The case of a
-<I>multigraph</I> (where multiple edges can connect the same two
-vertices) brings up an issue as to whether the iterators returned by
-the <TT>adjacent_vertices()</TT> function access a range that
-includes each adjacent vertex once, or whether it should match the
-behavior of the <TT>out_edges()</TT> function, and access a
-range that may include an adjacent vertex more than once. For now the
-behavior is defined to match that of <TT>out_edges()</TT>,
-though this decision may need to be reviewed in light of more
-experience with graph algorithm implementations.
+<pre> template <class G><br> struct AdjacencyGraphConcept<br>
{<br> typedef typename
boost::graph_traits<G>::adjacency_iterator<br>
adjacency_iterator;<br> void constraints() {<br>
function_requires< IncidenceGraphConcept<G> >();<br>
function_requires<
MultiPassInputIteratorConcept<adjacency_iterator>
>();<br><br> p = adjacent_vertices(v, g);<br> v =
*p.first;<br> const_constraints(g);<br> }<br> void
const_constraints(const G& g) {<br> p = adjacent_vertices(v,
g);<br> }<br> std::pair<adjacency_iterator,adjacency_iterator>
p;<br> typename boost::graph_traits<G>::vertex_descriptor
v;<br> G g;<br> };<br></pre>
+<h3>Design Rationale 设计原理</h3>邻接图AdjacencyGraph的概念好象有点没有必
要，因为 <a href="./IncidenceGraph.html">关联图IncidenceGraph</a> 确实提供了
相同的功能(甚至更多)。邻接图AdjacencyGraph概念的存在是因为，在某些情况下，使
用 <tt>adjacent_vertices()</tt> 要比 <tt>out_edges()</tt> 更方便。如果你正在
构造一个图类，且不想增加额外的工作以创建邻接迭代器，不要害怕。有一个名为 <a
href="./adjacency_iterator.html"> <tt>adjacency_iterator</tt></a> 的适配器
类，你可以用它来从出边迭代器创建邻接迭代器。
+<h3>Notes 备注</h3>
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<a name="1">[1]</a> 在<i>复图</i>(即相同的两个顶点间允许多条边连接)的情况下
会带来一个问题，即由 <tt>adjacent_vertices()</tt> 函数返回的迭代器所代表的区
间是否只包含每个邻接顶点一次，或是应该与 <tt>out_edges()</tt> 函数的行为相匹
配，其区间中可以多次包含同一个邻接顶点。目前，它的行为被定义为与
<tt>out_edges()</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>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/BidirectionalGraph.html
==============================================================================
--- trunk/libs/graph/doc/BidirectionalGraph.html (original)
+++ trunk/libs/graph/doc/BidirectionalGraph.html Wed Jul 8 07:54:49 2009
@@ -1,175 +1,115 @@
-<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>Bidirectional</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>
-
-
-<H2>
-<A NAME="concept:BidirectionalGraph"></A>
-BidirectionalGraph
-</H2>
-
-<P>
-The BidirectionalGraph concept refines <a
-href="./IncidenceGraph.html">IncidenceGraph</a> and adds the
-requirement for efficient access to the in-edges of each vertex. This
-concept is separated from <a
-href="./IncidenceGraph.html">IncidenceGraph</a> because for directed
-graphs efficient access to in-edges typically requires more storage
-space, and many algorithms do not require access to in-edges. For
-undirected graphs this is not an issue, since the <TT>in_edges()</TT>
-and <TT>out_edges()</TT> functions are the same, they both return the
-edges incident to the vertex.
-
-<H3>Refinement of</H3>
-
-<a href="./IncidenceGraph.html">IncidenceGraph</a>
-
-<h3>Notation</h3>
-
-<Table>
-<TR>
-<TD><tt>G</tt></TD>
-<TD>A type that is a model of Graph.</TD>
-</TR>
-
-<TR>
-<TD><tt>g</tt></TD>
-<TD>An object of type <tt>G</tt>.</TD>
-</TR>
-
-<TR>
-<TD><tt>v</tt></TD>
-<TD>An object of type
<tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
-</TR>
+<title>Bidirectional</title></head>
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
-</table>
+<br clear="">
-<H3>Associated Types</H3>
-<Table border>
+<h2>
+<a name="concept:BidirectionalGraph"></a>
+BidirectionalGraph 双向图
+</h2>
+
+<p>双向图(BidirectionalGraph)概念精化了 <a href="./IncidenceGraph.html">关
联图IncidenceGraph</a> 概念，增加了对每个顶点的入边进行高效访问的要求。从
<a href="./IncidenceGraph.html">关联图IncidenceGraph</a> 中将这个概念单独提
出来的原因是，对于有向图，要高效地访问入边通常需要更多的存储空间，而许多算法
并不需要访问入边。对于无向图则没有这个问题，因为 <tt>in_edges()</tt> 和
<tt>out_edges()</tt> 函数是相同的，它们都是返回与顶点相关联的边。
+
+</p><h3>Refinement of 精化自</h3>
+
+<a href="./IncidenceGraph.html">关联图IncidenceGraph</a>
+
+<h3>Notation 记号</h3>
+
+<table>
+<tbody><tr>
+<td><tt>G</tt></td>
+<td>一个以 Graph 为模的类型。</td>
+</tr>
+
+<tr>
+<td><tt>g</tt></td>
+<td>一个类型为 <tt>G</tt> 的对象。</td>
+</tr>
<tr>
+<td><tt>v</tt></td>
+<td>一个类型为 <tt>boost::graph_traits<G>::vertex_descriptor</tt> 的
对象。</td>
+</tr>
+
+</tbody></table>
+
+<h3>Associated Types 关联类型</h3>
+
+<table border="1">
+
+<tbody><tr>
<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br>
- This tag type must be convertible to <tt>bidirectional_graph_tag</tt>.
+ 这个标签类型必须可以转换为 <tt>bidirectional_graph_tag</tt>.
</td>
</tr>
-<TR>
-<TD><pre>boost::graph_traits<G>::in_edge_iterator</pre>
-An in-edge iterator for a vertex <i>v</i> provides access to the
-in-edges of <i>v</i>. As such, the value type of an in-edge iterator
-is the edge descriptor type of its graph. An in-edge iterator must
-meet the requirements of <a
href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
-</TD>
-</TR>
+<tr>
+<td><pre>boost::graph_traits<G>::in_edge_iterator</pre>顶点 <i>v</i>
的入边迭代器提供了对 <i>v</i> 的所有入边的访问。因此，入边迭代器值类型为该图
的边描述符。入边迭代器必须满足 <a
href="../../utility/MultiPassInputIterator.html">多遍输入迭代器
MultiPassInputIterator</a> 的要求。
+</td>
+</tr>
-</Table>
+</tbody></table>
-<h3>Valid Expressions</h3>
+<h3>Valid Expressions 有效表达式</h3>
-<Table border>
+<table border="1">
-<tr>
-<td><a name="sec:in-edges"><TT>in_edges(v, g)</TT></a></TD>
-<TD>
-Returns an iterator-range providing access to the
-in-edges (for directed graphs) or incident edges (for
-undirected graphs) of vertex <TT>v</TT> in graph <TT>g</TT>.
-For both directed and undirected graphs, the target of
-an out-edge is required to be vertex <tt>v</tt> and the
-source is required to be a vertex that is adjacent to <tt>v</tt>.
-<br>
-Return type: <TT>std::pair<in_edge_iterator, in_edge_iterator></TT>
-</TD>
-</TR>
+<tbody><tr>
+<td><a name="sec:in-edges"><tt>in_edges(v, g)</tt></a></td>
+<td>返回一个迭代器区间，提供对图 <tt>g</tt> 中的顶点 <tt>v</tt> 的所有入边
(对于有向图)或关联边(对于无向图)的访问。对于有向图和无向图，出边的目标都要求
是顶点 <tt>v</tt> 而源都要求是与 <tt>v</tt> 相邻的顶点。
+<br>返回类型：<tt>std::pair<in_edge_iterator, in_edge_iterator></tt>
+</td>
+</tr>
<tr>
-<TD><TT>in_degree(v, g)</TT></TD>
-<TD>
-Returns the number of in-edges (for directed graphs) or the
-number of incident edges (for undirected graphs) of vertex <TT>v</TT>
-in graph <TT>g</TT>.<br>
-Return type: <TT>degree_size_type</TT>
-</TD>
-</TR>
+<td><tt>in_degree(v, g)</tt></td>
+<td>返回图 <tt>g</tt> 中顶点 <tt>v</tt> 的入边数量(对于有向图)或关联边数量
(对于无向图)。<br>返回类型：<tt>degree_size_type</tt>
+</td>
+</tr>
<tr>
-<TD><TT>degree(v, g)</TT></TD>
-<TD>Returns the number of in-edges plus out-edges (for directed graphs) or
the
-number of incident edges (for undirected graphs) of vertex <TT>v</TT>
-in graph <TT>g</TT>.<br>
-Return type: <TT>degree_size_type</TT>
-</TD>
-</TR>
+<td><tt>degree(v, g)</tt></td>
+<td>返回图 <tt>g</tt> 中顶点 <tt>v</tt> 的入度加出度之和(对于有向图)或关联
边数量(对于无向图)。<br>返回类型：<tt>degree_size_type</tt>
+</td>
+</tr>
-</Table>
+</tbody></table>
-<H3>Models</H3>
+<h3>Models 模型</h3>
<ul>
-<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> with
<tt>Directed=bidirectionalS</tt></li>
-<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> with
<tt>Directed=undirectedS</tt></li>
+<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> 带
<tt>Directed=bidirectionalS</tt></li>
+<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> 带
<tt>Directed=undirectedS</tt></li>
</ul>
-<H3>Complexity guarantees</H3>
+<h3>Complexity guarantees 复杂度保证</h3><tt>in_edges()</tt> 函数要求是常数
时间的。<tt>in_degree()</tt> 和 <tt>degree()</tt> 函数则必须是入边数量(对于
有向图)或关联边数量(对于无向图)的线性时间。
+
+<h3>See Also 参见</h3>
+
+<a href="./graph_concepts.html">图概念 Graph concepts</a>
+
+<h3>Concept Checking Class 概念检查类</h3>
-The <TT>in_edges()</TT> function is required to be constant time. The
-<tt>in_degree()</tt> and <tt>degree()</tt> functions must be linear in
-the number of in-edges (for directed graphs) or incident edges (for
-undirected graphs).
-
-<H3>See Also</H3>
-
-<a href="./graph_concepts.html">Graph concepts</a>
-
-<H3>Concept Checking Class</H3>
-
-<PRE>
- template <class G>
- struct BidirectionalGraphConcept
- {
- typedef typename boost::graph_traits<G>::in_edge_iterator
- in_edge_iterator;
- void constraints() {
- function_requires< IncidenceGraphConcept<G> >();
- function_requires<
MultiPassInputIteratorConcept<in_edge_iterator> >();
-
- p = in_edges(v, g);
- e = *p.first;
- const_constraints(g);
- }
- void const_constraints(const G& g) {
- p = in_edges(v, g);
- e = *p.first;
- }
- std::pair<in_edge_iterator, in_edge_iterator> p;
- typename boost::graph_traits<G>::vertex_descriptor v;
- typename boost::graph_traits<G>::edge_descriptor e;
- G g;
- };
-</PRE>
+<pre> template <class G><br> struct BidirectionalGraphConcept<br>
{<br> typedef typename
boost::graph_traits<G>::in_edge_iterator<br>
in_edge_iterator;<br> void constraints() {<br>
function_requires< IncidenceGraphConcept<G> >();<br>
function_requires< MultiPassInputIteratorConcept<in_edge_iterator>
>();<br><br> p = in_edges(v, g);<br> e = *p.first;<br>
const_constraints(g);<br> }<br> void const_constraints(const G&
g) {<br> p = in_edges(v, g);<br> e = *p.first;<br> }<br>
std::pair<in_edge_iterator, in_edge_iterator> p;<br> typename
boost::graph_traits<G>::vertex_descriptor v;<br> typename
boost::graph_traits<G>::edge_descriptor e;<br> G g;<br>
};<br></pre>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/EdgeListGraph.html
==============================================================================
--- trunk/libs/graph/doc/EdgeListGraph.html (original)
+++ trunk/libs/graph/doc/EdgeListGraph.html Wed Jul 8 07:54:49 2009
@@ -1,184 +1,124 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek 2000
--
-- Distributed under the Boost Software License, Version 1.0.
-- (See accompanying file LICENSE_1_0.txt or copy at
-- http://www.boost.org/LICENSE_1_0.txt)
-->
-<Head>
-<Title>EdgeListGraph</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<title>EdgeListGraph</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>
+<br clear="">
-<H2><A NAME="concept:EdgeListGraph"></A>
-EdgeListGraph
-</H2>
+<h2><a name="concept:EdgeListGraph"></a>
+EdgeListGraph 边列表图
+</h2>边列表图(EdgeListGraph)概念精化了<a href="./Graph.html">图Graph</a>的
概念，增加了对图中所有边进行高效访问的要求。
-The EdgeListGraph concept refines the <a href="./Graph.html">Graph</a>
-concept, and adds the requirement for efficient access to all the
-edges in the graph.
+<h3>Refinement of 精化自</h3>
-<H3>Refinement of</H3>
+<a href="./Graph.html">图Graph</a>
-<a href="./Graph.html">Graph</a>
+<h3>Notation 记号</h3>
-<h3>Notation</h3>
-
-<Table>
-<TR>
-<TD><tt>G</tt></TD>
-<TD>A type that is a model of EdgeListGraph.</TD>
-</TR>
+<table>
+<tbody><tr>
+<td><tt>G</tt></td>
+<td>一个以 EdgeListGraph 为模的类型。</td>
+</tr>
-<TR>
-<TD><tt>g</tt></TD>
-<TD>An object of type <tt>G</tt>.</TD>
-</TR>
+<tr>
+<td><tt>g</tt></td>
+<td>一个类型为 <tt>G</tt> 的对象。</td>
+</tr>
-<TR>
-<TD><tt>e</tt></TD>
-<TD>An object of type
<tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD>
-</TR>
+<tr>
+<td><tt>e</tt></td>
+<td>一个类型为 <tt>boost::graph_traits<G>::edge_descriptor</tt> 的类
型。</td>
+</tr>
-</table>
+</tbody></table>
-<H3>Associated Types</H3>
+<h3>Associated Types 关联类型</h3>
-<table border>
+<table border="1">
-<tr>
-<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br>
- This tag type must be convertible to <tt>edge_list_graph_tag</tt>.
+<tbody><tr>
+<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br>这个标
签类型必须可转换为 <tt>edge_list_graph_tag</tt>.
</td>
</tr>
<tr>
-<td><pre>boost::graph_traits<G>::edge_iterator</pre>
-An edge iterator (obtained via <TT>edges(g)</TT>) provides access to
-all of the edges in a graph. An edge iterator type must meet the
-requirements of <a
-href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
The
-value type of the edge iterator must be the same as the edge
-descriptor of the graph.
+<td><pre>boost::graph_traits<G>::edge_iterator</pre>边迭代器(通过
<tt>edges(g)</tt> 获得)提供了对图中所有边的访问。边迭代器类型必须满足 <a
href="../../utility/MultiPassInputIterator.html">多遍输入迭代器
MultiPassInputIterator</a> 的要求。边迭代器的值类型必须与图的边描述符相同。
-<tr>
-<td><pre>boost::graph_traits<G>::edges_size_type</pre>
-The unsigned integer type used to represent the number of edges in the
-graph.
+</td></tr><tr>
+<td><pre>boost::graph_traits<G>::edges_size_type</pre>用于表示图中边
数的无符号整数类型。
</td>
</tr>
-</table>
+</tbody></table>
-<h3>Valid Expressions</h3>
+<h3>Valid Expressions 有效表达式</h3>
-<table border>
+<table border="1">
-<tr>
-<TD><a name="sec:edges"><TT>edges(g)</TT></a></TD>
-<TD>Returns an iterator-range providing access to all
- the edges in the graph <TT>g</TT>.<br>
-Return type: <TT>std::pair<edge_iterator, edge_iterator></TT>
+<tbody><tr>
+<td><a name="sec:edges"><tt>edges(g)</tt></a></td>
+<td>返回一个迭代器区间，提供对图 <tt>g</tt> 中所有边的访问。<br>返回类
型：<tt>std::pair<edge_iterator, edge_iterator></tt>
</td>
-</TR>
+</tr>
<tr>
-<TD><TT>num_edges(g)</TT></TD>
-<TD>Returns the number of edges in the graph <TT>g</TT>.<br>
-Return type: <TT>edges_size_type</TT>
+<td><tt>num_edges(g)</tt></td>
+<td>返回图 <tt>g</tt> 中的边数。<br>返回类型：<tt>edges_size_type</tt>
</td>
-</TR>
+</tr>
<tr>
-<TD><TT>source(e, g)</TT></TD>
-<TD>
-Returns the vertex descriptor for <i>u</i> of the edge <i>(u,v)</i>
-represented by <TT>e</TT>.<br>
-Return type: <TT>vertex_descriptor</TT>
+<td><tt>source(e, g)</tt></td>
+<td>返回 <tt>e</tt> 所表示的边 <i>(u,v)</i> 中的 <i>u</i> 顶点描述符。
<i></i><br>返回类型：<tt>vertex_descriptor</tt>
</td>
</tr>
<tr>
-<TD><TT>target(e, g)</TT></TD>
-<TD>
-Returns the vertex descriptor for
-<i>v</i> of the edge <i>(u,v)</i> represented by <TT>e</TT>.<br>
-Return type: <TT>vertex_descriptor</TT>
-</TD>
-</TR>
-
-</TABLE>
-
+<td><tt>target(e, g)</tt></td>
+<td>返回 <tt>e</tt> 所表示的边 <i>(u,v)</i> 中的 <i>v</i> 顶点描述符。
<br>返回类型：<tt>vertex_descriptor</tt>
+</td>
+</tr>
-<H3>Models</H3>
+</tbody></table>
-<UL>
-<LI><a href="./adjacency_list.html"><TT>adjacency_list</TT></a></LI>
-<LI><a href="./edge_list.html"><TT>edge_list</TT></a></LI>
-</UL>
+<h3>Models 模型</h3>
-<H3>Complexity guarantees</H3>
+<ul>
+<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a></li>
+<li><a href="./edge_list.html"><tt>edge_list</tt></a></li>
+</ul>
-The <TT>edges()</TT>, <TT>source()</TT>, and <TT>target()</TT> functions
-must all return in constant time.
+<h3>Complexity guarantees 复杂度保证</h3>函数 <tt>edges()</tt>,
<tt>source()</tt>, 和 <tt>target()</tt> 必须全部在常数时间内返回。
-<H3>See Also</H3>
-<a href="./graph_concepts.html">Graph concepts</a>
+<h3>See Also 参见</h3>
-<H3>Concept Checking Class</H3>
+<a href="./graph_concepts.html">图概念 Graph concepts</a>
-<P>
-<PRE>
- template <class G>
- struct EdgeListGraphConcept
- {
- typedef typename boost::graph_traits<G>::edge_iterator
- edge_iterator;
- void constraints() {
- function_requires< GraphConcept<G> >();
- function_requires<
MultiPassInputIteratorConcept<edge_iterator> >();
+<h3>Concept Checking Class 概念检查类</h3>
- p = edges(g);
- E = num_edges(g);
- e = *p.first;
- u = source(e, g);
- v = target(e, g);
- const_constraints(g);
- }
- void const_constraints(const G& g) {
- p = edges(g);
- E = num_edges(g);
- e = *p.first;
- u = source(e, g);
- v = target(e, g);
- }
- std::pair<edge_iterator,edge_iterator> p;
- typename boost::graph_traits<G>::vertex_descriptor u, v;
- typename boost::graph_traits<G>::edge_descriptor e;
- typename boost::graph_traits<G>::edges_size_type E;
- G g;
- };
-</PRE>
+<pre> template <class G><br> struct EdgeListGraphConcept<br>
{<br> typedef typename boost::graph_traits<G>::edge_iterator
<br> edge_iterator;<br> void constraints() {<br>
function_requires< GraphConcept<G> >();<br>
function_requires< MultiPassInputIteratorConcept<edge_iterator>
>();<br><br> p = edges(g);<br> E = num_edges(g);<br> e =
*p.first;<br> u = source(e, g);<br> v = target(e, g);<br>
const_constraints(g);<br> }<br> void const_constraints(const G&
g) {<br> p = edges(g);<br> E = num_edges(g);<br> e =
*p.first;<br> u = source(e, g);<br> v = target(e, g);<br>
}<br> std::pair<edge_iterator,edge_iterator> p;<br> typename
boost::graph_traits<G>::vertex_descriptor u, v;<br> typename
boost::graph_traits<G>::edge_descriptor e;<br> typename
boost::graph_traits<G>::edges_size_type E;<br> G g;<br>
};<br></pre>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/Graph.html
==============================================================================
--- trunk/libs/graph/doc/Graph.html (original)
+++ trunk/libs/graph/doc/Graph.html Wed Jul 8 07:54:49 2009
@@ -1,149 +1,102 @@
-<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>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>
-
-<H2><A NAME="concept:Graph"></A>
-Graph
-</H2>
-
-<P>
-The Graph concept contains a few requirements that are common to all
-the graph concepts. These include some associated types for
-<tt>vertex_descriptor</tt>, <tt>edge_descriptor</tt>, etc. One should
-note that a model of Graph is <B>not</B> required to be a model of <a
-href="http://www.sgi.com/tech/stl/Assignable.html";>Assignable</a>,
-so algorithms should pass graph objects by reference.
-
-<P>
-
-<h3>Notation</h3>
-
-<Table>
-<TR>
-<TD><tt>G</tt></TD>
-<TD>A type that is a model of Graph.</TD>
-</TR>
-
-<TR>
-<TD><tt>g</tt></TD>
-<TD>An object of type <tt>G</tt>.</TD>
-</TR>
-</table>
+<title>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">
-<H3>Associated Types</H3>
+<br clear="">
+
+<h2><a name="concept:Graph"></a>
+Graph 图
+</h2>
+
+<p>图(Graph)的概念包含了一些对于所有图概念都适用的要求。其中包括一些关联类
型
+<tt>vertex_descriptor</tt>, <tt>edge_descriptor</tt>, 等等。应该注意，以
Graph 为模并<b>不</b>要求满足 <a
href="http://www.sgi.com/tech/stl/Assignable.html";>可赋值Assignable</a>，因
此算法应该通过引用来传递图对象。
+
+</p><h3>Notation 记号</h3>
+
+<table>
+<tbody><tr>
+<td><tt>G</tt></td>
+<td>以 Graph 为模的一个类型。</td>
+</tr>
-<table border>
<tr>
-<td><pre>boost::graph_traits<G>::vertex_descriptor</pre>
-A vertex descriptor corresponds to a unique vertex in an abstract
-graph instance. A vertex descriptor must be
-<a
-href="http://www.sgi.com/tech/stl/DefaultConstructible.html";>Default
Constructible</a>,
-<a href="http://www.sgi.com/tech/stl/Assignable.html";>Assignable</a>, and
-<a href="http://www.sgi.com/tech/stl/EqualityComparable.html";>Equality
Comparable</a>.
+<td><tt>g</tt></td>
+<td>一个类型为 <tt>G</tt> 的对象。</td>
+</tr>
+</tbody></table>
+
+<h3>Associated Types 关联类型</h3>
+
+<table border="1">
+<tbody><tr>
+<td><pre>boost::graph_traits<G>::vertex_descriptor</pre>顶点描述
符，对应于一个抽象图实例中的单个顶点。顶点描述符必须符合
+<a href="http://www.sgi.com/tech/stl/DefaultConstructible.html";>可缺省构造
</a>,
+<a href="http://www.sgi.com/tech/stl/Assignable.html";>可赋值</a>, 以及
+<a href="http://www.sgi.com/tech/stl/EqualityComparable.html";>可比较相等性
</a>。
</td>
</tr>
<tr>
-<td><pre>boost::graph_traits<G>::edge_descriptor</pre>
-An edge descriptor corresponds to a unique edge <i>(u,v)</i> in a
-graph. An edge descriptor must be <a
-href="http://www.sgi.com/tech/stl/DefaultConstructible.html";>Default
Constructible</I>,
-<a
-href="http://www.sgi.com/tech/stl/Assignable.html";>Assignable</a>,
-and <a href="http://www.sgi.com/tech/stl/EqualityComparable.html";>Equality
Comparable</a>.
+<td><pre>boost::graph_traits<G>::edge_descriptor</pre>边描述符，对应
于一个图中的一条边 <i>(u,v)</i>。边描述符必须符合 <a
href="http://www.sgi.com/tech/stl/DefaultConstructible.html";>可缺省构造,
+</a><a href="http://www.sgi.com/tech/stl/Assignable.html";>可赋值</a>, 以及
<a href="http://www.sgi.com/tech/stl/EqualityComparable.html";>可比较相等性
</a>。
</td>
</tr>
<tr>
-<td><pre>boost::graph_traits<G>::directed_category</pre>
-This type shall be convertible to <TT>directed_tag</TT> or
<TT>undirected_tag</TT>.
+<td><pre>boost::graph_traits<G>::directed_category</pre>这个类型应该
可以转换为 <tt>directed_tag</tt> 或 <tt>undirected_tag</tt>。
</td>
</tr>
<tr>
-<td><pre>boost::graph_traits<G>::edge_parallel_category</pre>
-This describes whether the graph class allows the insertion of
-parallel edges (edges with the same source and target). The two tags
-are <TT>allow_parallel_edge_tag</TT> and
<TT>disallow_parallel_edge_tag</TT>.
+<td><pre>boost::graph_traits<G>::edge_parallel_category</pre>用于指定
该图类是否允许插入平行边(即具有相同源和目标的边)。两个标签分别为
<tt>allow_parallel_edge_tag</tt> 和 <tt>disallow_parallel_edge_tag</tt>。
</td>
</tr>
<tr>
-<td><pre>boost::graph_traits<G>::traversal_category</pre>
-This describes the ways in which the vertices and edges of the
-graph can be visited. The choices are <TT>incidence_graph_tag</TT>,
-<TT>adjacency_graph_tag</TT>, <TT>bidirectional_graph_tag</TT>,
-<TT>vertex_list_graph_tag</TT>, <TT>edge_list_graph_tag</TT>, and
-<TT>adjacency_matrix_tag</TT>.
+<td><pre>boost::graph_traits<G>::traversal_category</pre>用于指定以何
种方式可以访问图中的顶点和边。选择包括有 <tt>incidence_graph_tag</tt>,
+<tt>adjacency_graph_tag</tt>, <tt>bidirectional_graph_tag</tt>,
+<tt>vertex_list_graph_tag</tt>, <tt>edge_list_graph_tag</tt>, 和
+<tt>adjacency_matrix_tag</tt>。
</td>
</tr>
-</table>
+</tbody></table>
-<H3>Valid Expressions</H3>
+<h3>Valid Expressions 有效表达式</h3>
-<table border>
+<table border="1">
+
+<tbody><tr>
+<td><pre>boost::graph_traits<G>::null_vertex()</pre></td>
+<td>返回一个特殊的
<tt>boost::graph_traits<G>::vertex_descriptor</tt> 对象，该对象不引向
任一个类型为 <tt>G</tt> 的图对象的顶点。
+</td><td>
+</td></tr>
+</tbody></table>
-<tr>
-<td><pre>boost::graph_traits<G>::null_vertex()</pre></td></TD>
-<td>
-Returns a special <tt>boost::graph_traits<G>::vertex_descriptor</tt>
object which does not refer to
-any vertex of graph object which type is <tt>G</tt>.
-<td>
-</tr>
-</table>
+<h3>Concept Checking Class 概念检查类</h3>
-<H3>Concept Checking Class</H3>
-
-<PRE>
- template <class G>
- struct GraphConcept
- {
- typedef typename boost::graph_traits<G>::vertex_descriptor
vertex_descriptor;
- typedef typename boost::graph_traits<G>::edge_descriptor
edge_descriptor;
- typedef typename boost::graph_traits<G>::directed_category
directed_category;
- typedef typename boost::graph_traits<G>::edge_parallel_category
edge_parallel_category;
- typedef typename boost::graph_traits<G>::traversal_category
traversal_category;
-
- void constraints() {
- function_requires<
DefaultConstructibleConcept<vertex_descriptor> >();
- function_requires<
EqualityComparableConcept<vertex_descriptor> >();
- function_requires< AssignableConcept<vertex_descriptor>
>();
- function_requires<
DefaultConstructibleConcept<edge_descriptor> >();
- function_requires<
EqualityComparableConcept<edge_descriptor> >();
- function_requires< AssignableConcept<edge_descriptor>
>();
- }
- G g;
- };
-</PRE>
+<pre> template <class G><br> struct GraphConcept<br> {<br>
typedef typename boost::graph_traits<G>::vertex_descriptor
vertex_descriptor;<br> typedef typename
boost::graph_traits<G>::edge_descriptor edge_descriptor;<br>
typedef typename boost::graph_traits<G>::directed_category
directed_category;<br> typedef typename
boost::graph_traits<G>::edge_parallel_category
edge_parallel_category;<br> typedef typename
boost::graph_traits<G>::traversal_category
traversal_category;<br><br> void constraints() {<br>
function_requires< DefaultConstructibleConcept<vertex_descriptor>
>();<br> function_requires<
EqualityComparableConcept<vertex_descriptor> >();<br>
function_requires< AssignableConcept<vertex_descriptor>
>();<br> function_requires<
DefaultConstructibleConcept<edge_descriptor> >();<br>
function_requires< EqualityComparableConcept<edge_descriptor>
>();<br> function_requires<
AssignableConcept<edge_descriptor> >();<br> }<br> G g;<br>
};<br></pre>
-<H3>See Also</H3>
+<h3>See Also 参见</h3>
-<a href="./graph_concepts.html">Graph concepts</a>
+<a href="./graph_concepts.html">图概念 Graph concepts</a>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/IncidenceGraph.html
==============================================================================
--- trunk/libs/graph/doc/IncidenceGraph.html (original)
+++ trunk/libs/graph/doc/IncidenceGraph.html Wed Jul 8 07:54:49 2009
@@ -1,202 +1,140 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
--
-- Distributed under the Boost Software License, Version 1.0.
-- (See accompanying file LICENSE_1_0.txt or copy at
-- http://www.boost.org/LICENSE_1_0.txt)
-->
-<Head>
-<Title>IncidenceGraph</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<title>IncidenceGraph</title></head>
-<BR Clear>
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
-<H1><A NAME="concept:IncidenceGraph"></A>
-IncidenceGraph
-</H1>
+<br clear="">
-The IncidenceGraph concept provides an interface for
-efficient access to the out-edges of each vertex in the graph.
+<h1><a name="concept:IncidenceGraph"></a>
+IncidenceGraph 关联图
+</h1>关联图(IncidenceGraph)概念提供了一个接口，可以对图中每个顶点的出边进行
高效的访问。
-<H3>Refinement of</H3>
+<h3>Refinement of 精化自</h3>
-<a href="./Graph.html">Graph</a>
+<a href="./Graph.html">图 Graph</a>
-<h3>Notation</h3>
+<h3>Notation 记号</h3>
-<Table>
-<TR>
-<TD><tt>G</tt></TD>
-<TD>A type that is a model of IncidenceGraph.</TD>
-</TR>
+<table>
+<tbody><tr>
+<td><tt>G</tt></td>
+<td>一个以 IncidenceGraph 为模的类型。</td>
+</tr>
-<TR>
-<TD><tt>g</tt></TD>
-<TD>An object of type <tt>G</tt>.</TD>
-</TR>
+<tr>
+<td><tt>g</tt></td>
+<td>一个类型为 <tt>G</tt> 的对象。</td>
+</tr>
-<TR>
-<TD><tt>e</tt></TD>
-<TD>An object of type
<tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD>
-</TR>
+<tr>
+<td><tt>e</tt></td>
+<td>一个类型为 <tt>boost::graph_traits<G>::edge_descriptor</tt> 的对
象。</td>
+</tr>
-<TR>
-<TD><tt>u, v</tt></TD>
-<TD>Are objects of type
<tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
-</TR>
+<tr>
+<td><tt>u, v</tt></td>
+<td>均为类型 <tt>boost::graph_traits<G>::vertex_descriptor</tt> 的对
象。</td>
+</tr>
-</table>
+</tbody></table>
-<H3>Associated Types</H3>
+<h3>Associated Types 关联类型</h3>
-<Table border>
+<table border="1">
-<tr>
-<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br>
- This tag type must be convertible to <tt>incidence_graph_tag</tt>.
+<tbody><tr>
+<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br>这是一
个标签类型，必须可转换为 <tt>incidence_graph_tag</tt>.
</td>
</tr>
-<TR>
-<TD>
-<pre>boost::graph_traits<G>::out_edge_iterator</pre>
-An out-edge iterator for a vertex <i>v</i> provides access to the
-out-edges of the vertex. As such, the value type of an out-edge
-iterator is the edge descriptor type of its graph. An out-edge
-iterator must meet the requirements of <a
-href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
-</TD>
-</TR>
+<tr>
+<td>
+<pre>boost::graph_traits<G>::out_edge_iterator</pre>顶点 <i>v</i> 的
出边迭代器提供了到该顶点所有出边的访问。因此，出边迭代器的值类型应为该图的边
描述符类型。出边迭代器必须满足 <a
href="../../utility/MultiPassInputIterator.html">多遍输入迭代器
MultiPassInputIterator</a> 的要求。
+</td>
+</tr>
-<TR>
-<TD><pre>boost::graph_traits<G>::degree_size_type</pre>
-The unsigned intergral type used for representing the number
-out-edges or incident edges of a vertex.
-</TD>
-</TR>
+<tr>
+<td><pre>boost::graph_traits<G>::degree_size_type</pre>用于表示一个顶
点的出边或关联边数量的无符号整数类型。
+</td>
+</tr>
-</table>
+</tbody></table>
-<h3>Valid Expressions</h3>
+<h3>Valid Expressions 有效表达式</h3>
-<Table border>
+<table border="1">
-<tr>
-<td><a name="sec:source"><TT>source(e, g)</TT></a></TD>
-<TD>Returns the vertex descriptor for <i>u</i> of the edge <i>(u,v)</i>
represented by <TT>e</TT>.<br>
-Return type: <TT>vertex_descriptor</TT>
-</TD>
-</TR>
+<tbody><tr>
+<td><a name="sec:source"><tt>source(e, g)</tt></a></td>
+<td>设 <tt>e</tt> 表示边 <i>(u,v)</i>，返回 <i>u</i> 的顶点描述符。
<i></i><br>返回类型：<tt>vertex_descriptor</tt>
+</td>
+</tr>
<tr>
-<td><a name="sec:target"><TT>target(e, g)</TT></a></TD>
-<TD>Returns the vertex descriptor for <i>v</i> of the edge <i>(u,v)</i>
represented by <TT>e</TT>.<br>
-Return type: <TT>vertex_descriptor</TT>
+<td><a name="sec:target"><tt>target(e, g)</tt></a></td>
+<td>设 <tt>e</tt> 表示边 <i>(u,v)</i>，返回 <i>v</i> 的顶点描述符。<br>返回
类型：<tt>vertex_descriptor</tt>
</td></tr>
<tr>
-<td><a name="sec:out-edges"><TT>out_edges(u, g)</TT></a></TD>
-<TD>Returns an iterator-range providing access to the out-edges (for
-directed graphs) or incident edges (for undirected graphs) of vertex
-<TT>u</TT> in graph <TT>g</TT>. The source vertex of an edge obtained
-via an out edge iterator is guaranteed (for both directed and
-undirected graphs) to be the vertex <tt>u</tt> used in the call to
-<tt>out_edges(u, g)</tt> and the target vertex must the a vertex
-adjacent to <tt>u</tt>.<a href="#1">[1]</a>
-<br>
-Return type: <TT>std::pair<out_edge_iterator, out_edge_iterator></TT>
-</TD>
+<td><a name="sec:out-edges"><tt>out_edges(u, g)</tt></a></td>
+<td>返回一个迭代器区间，以提供对图 <tt>g</tt> 中的顶点
+<tt>u</tt> 的所有出边(对于有向图)或关联边(对于无向图)的访问。通过出边迭代器
所获得的一条边，其源顶点保证(不论是有向图或无向图)等于用于调用
+<tt>out_edges(u, g)</tt> 的顶点 <tt>u</tt>，而目标顶点则必须为 <tt>u</tt>
相邻的顶点。<a href="#1">[1]</a>
+<br>返回类型：<tt>std::pair<out_edge_iterator,
out_edge_iterator></tt>
+</td>
</tr>
<tr>
-<TD><TT>out_degree(u, g)</TT></TD>
-<TD>Returns the number of out-edges (for directed graphs) or the
-number of incident edges (for undirected graphs) of vertex <TT>u</TT>
-in graph <TT>g</TT>.<br>
-Return type: <TT>degree_size_type</TT>
-</TD>
-</TR>
-
-</TABLE>
-
-<P>
-
-<H3>Complexity guarantees</H3>
-
-<P>
-The <TT>source()</TT>, <TT>target()</TT>, and <TT>out_edges()</TT>
-functions must all be constant time. The <tt>out_degree()</tt>
-function must be linear in the number of out-edges.
-
-<P>
-
-<H3>See Also</H3>
-
-<a href="./graph_concepts.html">Graph concepts</a>
-
-<H3>Notes</H3>
-
-<a name="1">[1]</a> For undirected graphs, the edge <tt>(u,v)</tt> is
-the same as edge <tt>(v,u)</tt>, so without some extra guarantee an
-implementation would be free use any ordering for the pair of vertices
-in an out-edge. For example, if you call <tt>out_edges(u, g)</tt>, and
-<tt>v</tt> is one of the vertices adjacent to <tt>u</tt>, then the
-implementation would be free to return <tt>(v,u)</tt> as an out-edge
-which would be non-intuitive and cause trouble for algorithms.
-Therefore, the extra requirement is added that the out-edge connecting
-<tt>u</tt> and <tt>v</tt> must be given as <tt>(u,v)</tt> and not
-<tt>(v,u)</tt>.
-
-<H3>Concept Checking Class</H3>
-
-<PRE>
- template <class G>
- struct IncidenceGraphConcept
- {
- typedef typename boost::graph_traits<G>::out_edge_iterator
out_edge_iterator;
- void constraints() {
- function_requires< GraphConcept<G> >();
- function_requires<
MultiPassInputIteratorConcept<out_edge_iterator> >();
-
- p = out_edges(u, g);
- e = *p.first;
- u = source(e, g);
- v = target(e, g);
- }
- void const_constraints(const G& g) {
- p = out_edges(u, g);
- e = *p.first;
- u = source(e, g);
- v = target(e, g);
- }
- std::pair<out_edge_iterator, out_edge_iterator> p;
- typename boost::graph_traits<G>::vertex_descriptor u, v;
- typename boost::graph_traits<G>::edge_descriptor e;
- G g;
- };
-</PRE>
+<td><tt>out_degree(u, g)</tt></td>
+<td>返回图 <tt>g</tt> 中顶点 <tt>u</tt> 的出边数量(对于有向图)或关联边数量
(对于无向图)。<br>返回类型：<tt>degree_size_type</tt>
+</td>
+</tr>
+
+</tbody></table>
+
+<h3>Complexity guarantees 复杂度保证</h3>
+
+<p>函数 <tt>source()</tt>, <tt>target()</tt>, 和 <tt>out_edges()</tt>
+的复杂度必须均为常量时间。<tt>out_degree()</tt>
+函数则必须为出边数量的线性时间。
+
+</p><h3>See Also 参见</h3>
+
+<a href="./graph_concepts.html">图概念 Graph concepts</a>
+
+<h3>Notes 备注</h3>
+
+<a name="1">[1]</a> 对于无向图来说，边 <tt>(u,v)</tt> 与 <tt>(v,u)</tt> 是
相同的，所以如果没有额外的限制，具体实现可以自由地以两个顶点的任意顺序来返回
出边。例如，如果你调用 <tt>out_edges(u, g)</tt>，且
+<tt>v</tt> 是 <tt>u</tt> 的一个邻接顶点，则实现可以自由地返回
<tt>(v,u)</tt> 作为一条出边，这是非直观的，会引起算法上的麻烦。因此，增加了
这一要求，连接
+<tt>u</tt> 和 <tt>v</tt> 的出边必须用 <tt>(u,v)</tt> 而不是
+<tt>(v,u)</tt> 给出。
+
+<h3>Concept Checking Class 概念检查类</h3>
+
+<pre> template <class G><br> struct IncidenceGraphConcept<br>
{<br> typedef typename boost::graph_traits<G>::out_edge_iterator
out_edge_iterator;<br> void constraints() {<br>
function_requires< GraphConcept<G> >();<br>
function_requires<
MultiPassInputIteratorConcept<out_edge_iterator> >();<br><br>
p = out_edges(u, g);<br> e = *p.first;<br> u = source(e,
g);<br> v = target(e, g);<br> }<br> void const_constraints(const
G& g) {<br> p = out_edges(u, g);<br> e = *p.first;<br> u
= source(e, g);<br> v = target(e, g);<br> }<br>
std::pair<out_edge_iterator, out_edge_iterator> p;<br> typename
boost::graph_traits<G>::vertex_descriptor u, v;<br> typename
boost::graph_traits<G>::edge_descriptor e;<br> G g;<br>
};<br></pre>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
-Indiana University (<A
-HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
-<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>,
Indiana University (<A
HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
-Indiana University (<A
-HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>)<br>
+<a href="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</a>,
Indiana University (<a
href="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</a>)<br>
+<a href="http://www.osl.iu.edu/%7Elums";>Andrew Lumsdaine</a>,
+Indiana University (<a href="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
-</BODY>
-</HTML>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/MutableGraph.html
==============================================================================
--- trunk/libs/graph/doc/MutableGraph.html (original)
+++ trunk/libs/graph/doc/MutableGraph.html Wed Jul 8 07:54:49 2009
@@ -1,299 +1,172 @@
-<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>MutableGraph</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>
-
-
-<H2><A NAME="sec:MutableGraph"></A>
-MutableGraph
-</H2>
-
-A MutableGraph can be changed via the addition or removal of
-edges and vertices.
-
-<H3>Refinement of</H3>
-
-<a href="./Graph.html">Graph</a>
-
-<h3>Notation</h3>
-
-<Table>
-<TR>
-<TD><tt>G</tt></TD>
-<TD>A type that is a model of Graph.</TD>
-</TR>
-
-<TR>
-<TD><tt>g</tt></TD>
-<TD>An object of type <tt>G</tt>.</TD>
-</TR>
-
-<TR>
-<TD><tt>e</tt></TD>
-<TD>An object of type
<tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD>
-</TR>
-
-<TR>
-<TD><tt>u,v</tt></TD>
-<TD>are objects of type
<tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
-</TR>
-
-<TR>
-<TD><tt>iter</tt></TD>
-<TD>is an object of type
<tt>boost::graph_traits<G>::out_edge_iterator</tt>.</TD>
-</TR>
-
-<TR>
-<TD><tt>p</tt></TD>
-<TD>is an object of a type that models <a
-href="http://www.sgi.com/tech/stl/Predicate.html";>Predicate</a>
-and whose argument type matches the <tt>edge_descriptor</tt> type.
-</TR>
-
-</table>
-
-<H3>Valid Expressions</H3>
-
-<table border>
-
-<tr>
-<TD><a name="sec:add-edge"><TT>add_edge(u, v, g)</TT></a></TD>
-<TD>
-Inserts the edge <i>(u,v)</i> into the graph, and returns an edge
-descriptor pointing to the new edge. If the graph disallows parallel
-edges, and the edge <i>(u,v)</i> is already in the graph, then the
-<tt>bool</tt> flag returned is <tt>false</tt> and the returned edge
-descriptor points to the already existing edge. Note that for
-undirected graphs, <i>(u,v)</i> is the same edge as <i>(v,u)</i>, so
-after a call to the function <tt>add_edge()</tt>, this implies that
-edge <i>(u,v)</i> will appear in the out-edges of <i>u</i> and
-<i>(u,v)</i> (or equivalently <i>(v,u)</i>) will appear in the
-out-edges of <i>v</i>. Put another way, <i>v</i> will be adjacent to
-<i>u</i> and <i>u</i> will be adjacent to <i>v</i>.
-<br>
-Return type: <TT>std::pair<edge_descriptor, bool></TT>
-</TD>
+<title>MutableGraph</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="">
+
+
+<h2><a name="sec:MutableGraph"></a>
+MutableGraph 可变图
+</h2>可变图(MutableGraph)可以通过增加或移除边和顶点来修改。
+
+<h3>Refinement of 精化自</h3>
+
+<a href="./Graph.html">图Graph</a>
+
+<h3>Notation 记号</h3>
+
+<table>
+<tbody><tr>
+<td><tt>G</tt></td>
+<td>一个以 Graph 为模的类型。</td>
+</tr>
+
+<tr>
+<td><tt>g</tt></td>
+<td>一个类型为 <tt>G</tt> 的对象。</td>
+</tr>
+
+<tr>
+<td><tt>e</tt></td>
+<td>一个类型为 <tt>boost::graph_traits<G>::edge_descriptor</tt> 的对
象。</td>
+</tr>
+
+<tr>
+<td><tt>u,v</tt></td>
+<td>均为类型 <tt>boost::graph_traits<G>::vertex_descriptor</tt> 的对
象。</td>
+</tr>
+
+<tr>
+<td><tt>iter</tt></td>
+<td>一个类型为 <tt>boost::graph_traits<G>::out_edge_iterator</tt> 的
对象。</td>
+</tr>
+
+<tr>
+<td><tt>p</tt></td>
+<td>一个以 <a href="http://www.sgi.com/tech/stl/Predicate.html";>谓词
Predicate</a>
+为模的类型的对象，其参数类型与 <tt>edge_descriptor</tt> 类型匹配。
+</td></tr>
+
+</tbody></table>
+
+<h3>Valid Expressions 有效表达式</h3>
+
+<table border="1">
+
+<tbody><tr>
+<td><a name="sec:add-edge"><tt>add_edge(u, v, g)</tt></a></td>
+<td>将表 <i>(u,v)</i> 插入到图中，并返回指向新边的边描述符。如果该图不允许
平行边，且边 <i>(u,v)</i> 已存在于图中，则返回的
+<tt>bool</tt> 标志为 <tt>false</tt> 且返回指向已有边的边描述符。注意，对于
无向图，<i>(u,v)</i> 与 <i>(v,u)</i> 是同一条边，所以在调用了函数
<tt>add_edge()</tt> 后，边 <i>(u,v)</i> 将会在 <i>u</i> 的出边中出现，同时
+<i>(u,v)</i> (或者说 <i>(v,u)</i>) 也会在 <i>v</i> 的出边中出现。换句话
说，<i>v</i> 邻接于
+<i>u</i> 且 <i>u</i> 邻接于 <i>v</i>。
+<br>返回类型：<tt>std::pair<edge_descriptor, bool></tt>
+</td>
+</tr>
+
+<tr>
+<td><a
name="sec:remove_edge"><tt>remove_edge(u, v, g)</tt></a></td>
+<td>
+从图中移除边 <i>(u,v)</i>。如果该图允许平行边，则会移除所有
+<i>(u,v)</i>。<br>返回类型：<tt>void</tt><br>先验条件：<i>u</i> 和
<i>v</i> 均为图中的顶点。<br>
+后验条件：<i>(u,v)</i> 不再属于
+<tt>g</tt> 的边集。<br>
+</td>
+</tr>
+
+
+<tr>
+<td><tt>remove_edge(e, g)</tt></td>
+<td>从图中移除 <i>e</i>。<br>返回类型：<tt>void</tt><br>先验条件：<i>e</i>
为图中的一条边。<br>
+后验条件：<i>e</i> 不再属于 <tt>g</tt> 的边集。
+</td>
+</tr>
+
+<tr>
+<td><tt>remove_edge(iter, g)</tt></td>
+<td>从图中移除由 <tt>iter</tt> 所指的边。该表达式仅当该图符合 <a
href="./IncidenceGraph.html">关联图IncidenceGraph</a> 的时候才被要求。<br>返
回类型：<tt>void</tt><br>先验条件：<tt>*iter</tt> 为图中的一条边。<br>后验条
件：<tt>*iter</tt> 不再属于 <tt>g</tt> 的边集。
+</td>
+</tr>
+
+<tr>
+<td><tt>remove_edge_if(p, g)</tt></td>
+<td>从图 <tt>g</tt> 中移除所有令谓词 <tt>p</tt> 为 true 的边。<br>返回类
型：<tt>void</tt>
+</td>
+</tr>
+
+<tr>
+<td><tt>remove_out_edge_if(u, p, g)</tt></td>
+<td>删除顶点 <tt>u</tt> 的所有令谓词 <tt>p</tt> 为 true 的出边。该表达式仅
当该图符合 <a href="./IncidenceGraph.html">关联图IncidenceGraph</a> 的时候才
被要求。<br>返回类型：<tt>void</tt>
+</td>
+</tr>
+
+<tr>
+<td><tt>remove_in_edge_if(u, p, g)</tt></td>
+<td>删除顶点 <tt>u</tt> 的所有令谓词 <tt>p</tt> 为 true 的入边。该表达式仅
当该图符合 <a href="IncidenceGraph.html">关联图IncidenceGraph</a> 的时候才被
要求。<br>返回类型：<tt>void</tt>
+</td>
+</tr>
+
+
+<tr>
+<td><a name="sec:add-vertex"><tt>add_vertex(g)</tt></a></td>
+<td>增加一个新顶点到图中。新顶点的 <tt>vertex_descriptor</tt> 被返回。
<br>返回类型：<tt>vertex_descriptor</tt>
+</td>
+</tr>
+
+
+<tr>
+<td><tt>clear_vertex(u, g)</tt></td>
+<td>从图中移除顶点 <tt>u</tt> 的所有出边和入边。<br>返回类
型：<tt>void</tt><br>先验条件：<tt>u</tt> 为 <tt>g</tt> 的一个有效的顶点描述
符。<br>后验条件：<tt>u</tt> 不是 <tt>g</tt> 中任一条边的源或目标顶点。
+</td>
</tr>
<tr>
-<TD><a
name="sec:remove_edge"><TT>remove_edge(u, v, g)</TT></a></TD>
-<TD>
-Remove the edge <i>(u,v)</i> from the graph. If the
-graph allows parallel edges this remove all occurrences of
-<i>(u,v)</i>.<br>
-Return type: <TT>void</TT><br>
-Precondition: <i>u</i> and <i>v</i> are vertices in the graph.<br>
-Postcondition: <i>(u,v)</i> is no longer in the edge set for
-<TT>g</TT>.<br>
-</TD>
-</TR>
-
-
-<tr>
-<TD><TT>remove_edge(e, g)</TT></TD>
-<TD>Remove the edge <i>e</i> from the graph.<br>
-Return type: <TT>void</TT><br>
-Precondition: <i>e</i> is an edge in the graph.<br>
-Postcondition: <i>e</i> is no longer in the edge set for <TT>g</TT>.
-</TD>
-</TR>
-
-<tr>
-<TD><TT>remove_edge(iter, g)</TT></TD>
-<TD>Remove the edge pointed to be <tt>iter</tt> from the graph. This
-expression is only required when the graph also models <a
-href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
-Return type: <TT>void</TT><br>
-Precondition: <tt>*iter</tt> is an edge in the graph.<br>
-Postcondition: <tt>*iter</tt> is no longer in the edge set for <TT>g</TT>.
-</TD>
-</TR>
-
-<tr>
-<TD><TT>remove_edge_if(p, g)</TT></TD>
-<TD>Remove all the edges from graph <tt>g</tt> for which
-the predicate <tt>p</tt> returns true.<br>
-Return type: <TT>void</TT>
-</TD>
-</TR>
-
-<tr>
-<TD><TT>remove_out_edge_if(u, p, g)</TT></TD>
-<TD>Remove all the out-edges of vertex <tt>u</tt> for which the
-predicate <tt>p</tt> returns true. This expression is only required
-when the graph also models <a
-href="./IncidenceGraph.html">IncidenceGraph</a>.<br>
-Return type: <TT>void</TT>
-</TD>
-</TR>
-
-<tr>
-<TD><TT>remove_in_edge_if(u, p, g)</TT></TD>
-<TD>Remove all the in-edges of vertex <tt>u</tt> for which the
-predicate <tt>p</tt> returns true. This expression is only required when
the
-graph also models <a
-href="./BidirectionalGraph.html">BidirectionalGraph</a>.<br>
-Return type: <TT>void</TT>
-</TD>
-</TR>
-
-
-<tr>
-<TD><a name="sec:add-vertex"><TT>add_vertex(g)</TT></a></TD>
-<TD>
-Add a new vertex to the graph. The <TT>vertex_descriptor</TT> for the
-new vertex is returned.<br>
-Return type: <TT>vertex_descriptor</TT>
-</TD>
-</TR>
-
-
-<tr>
-<TD><TT>clear_vertex(u, g)</TT></TD>
-<TD>
-Remove all edges to and from vertex <tt>u</tt> from the graph.<br>
-Return type: <TT>void</TT><br>
-Precondition: <tt>u</tt> is a valid vertex descriptor of <TT>g</TT>.<br>
-Postcondition: <tt>u</tt> does not appear as a source or target of
-any edge in <TT>g</TT>.
-</TD>
-</TR>
-
-<tr>
-<TD><a name="sec:remove-vertex"><TT>remove_vertex(u, g)</TT></a></TD>
-<TD>
-Remove <i>u</i> from the vertex set of the graph. Note that undefined
-behavior may result if there are edges remaining in the graph who's
-target is <i>u</i>. Typically the <TT>clear_vertex()</TT> function
-should be called first.<br>
-Return type: <TT>void</TT><br>
-Precondition: <TT>u</TT> is a valid vertex descriptor of <TT>g</TT>.<br>
-Postcondition: <TT>num_vertices(g)</TT> is one less, <TT>u</TT>
-no longer appears in the vertex set of the graph and it
-is no longer a valid vertex descriptor.
-</TD>
-</TR>
-</TABLE>
-
-<P>
-</LI>
-</UL>
-
-<P>
-
-<H3>Complexity Guarantees</H3>
-
-<P>
-
-<UL>
-<LI>Edge insertion must be either amortized constant time or it
- can be <i>O(log(E/V))</i> if the insertion also checks to
- prevent the addition of parallel edges (which is a ``feature'' of
- some graph types).
-</LI>
-<LI>Edge removal is guaranteed to be <i>O(E)</i>.</LI>
-<LI>Vertex insertion is guaranteed to be amortized constant time.</LI>
-<LI>Clearing a vertex is <i>O(E + V)</i>.</LI>
-<LI>Vertex removal is <i>O(E + V)</i>.</LI>
-</UL>
-
-<H3>Models</H3>
-
-<UL>
-<LI><TT>adjacency_list</TT>
-</LI>
-</UL>
-
-
-<H3>Concept Checking Class</H3>
-
-<PRE>
- template <class G>
- struct MutableGraphConcept
- {
- typedef typename boost::graph_traits<G>::edge_descriptor
edge_descriptor;
- void constraints() {
- v = add_vertex(g);
- clear_vertex(v, g);
- remove_vertex(v, g);
- e_b = add_edge(u, v, g);
- remove_edge(u, v, g);
- remove_edge(e, g);
- }
- G g;
- edge_descriptor e;
- std::pair<edge_descriptor, bool> e_b;
- typename boost::graph_traits<G>::vertex_descriptor u, v;
- typename boost::graph_traits<G>::out_edge_iterator iter;
- };
-
- template <class edge_descriptor>
- struct dummy_edge_predicate {
- bool operator()(const edge_descriptor& e) const {
- return false;
- }
- };
-
- template <class G>
- struct MutableIncidenceGraphConcept
- {
- void constraints() {
- function_requires< MutableGraph<G> >();
- remove_edge(iter, g);
- remove_out_edge_if(u, p, g);
- }
- G g;
- typedef typename boost::graph_traits<G>::edge_descriptor
edge_descriptor;
- dummy_edge_predicate<edge_descriptor> p;
- typename boost::graph_traits<G>::vertex_descriptor u;
- typename boost::graph_traits<G>::out_edge_iterator iter;
- };
-
- template <class G>
- struct MutableBidirectionalGraphConcept
- {
- void constraints() {
- function_requires< MutableIncidenceGraph<G> >();
- remove_in_edge_if(u, p, g);
- }
- G g;
- typedef typename boost::graph_traits<G>::edge_descriptor
edge_descriptor;
- dummy_edge_predicate<edge_descriptor> p;
- typename boost::graph_traits<G>::vertex_descriptor u;
- };
-
- template <class G>
- struct MutableEdgeListGraphConcept
- {
- void constraints() {
- function_requires< MutableGraph<G> >();
- remove_edge_if(p, g);
- }
- G g;
- typedef typename boost::graph_traits<G>::edge_descriptor
edge_descriptor;
- dummy_edge_predicate<edge_descriptor> p;
- };
-</PRE>
+<td><a name="sec:remove-vertex"><tt>remove_vertex(u, g)</tt></a></td>
+<td>将 <i>u</i> 从图的顶点集中删除。注意，如果图中还有以 <i>u</i> 为目标的
边，则可能得到未定义行为。通常 <tt>clear_vertex()</tt> 函数应先被调用。
<br>返回类型：<tt>void</tt><br>先验条件：<tt>u</tt> 为 <tt>g</tt> 的一个有效
的顶点描述符。<br>后验条件：<tt>num_vertices(g)</tt> 减一，<tt>u</tt>
+不再属于图的顶点集且不再是一个有效的顶点描述符。
+</td>
+</tr>
+</tbody></table>
+
+<p>
+
+</p><h3>Complexity Guarantees 复杂度保证</h3>
+
+<ul>
+<li>边插入必须是分摊常数时间，或者如果插入操作要进行平行边检查(这是某些图类
型的"特性")，则为 <i>O(log(E/V))</i>。
+</li>
+<li>边删除保证是 <i>O(E)</i> 的。</li>
+<li>点插入保证是分摊常数时间。</li>
+<li>顶点清除为 <i>O(E + V)</i>.</li>
+<li>顶点移除为 <i>O(E + V)</i>.</li>
+</ul>
+
+<h3>Models 模型</h3>
+
+<ul>
+<li><tt>adjacency_list</tt>
+</li>
+</ul>
+
+
+<h3>Concept Checking Class 概念检查类</h3>
+
+<pre> template <class G><br> struct MutableGraphConcept<br>
{<br> typedef typename boost::graph_traits<G>::edge_descriptor
edge_descriptor;<br> void constraints() {<br> v =
add_vertex(g);<br> clear_vertex(v, g);<br> remove_vertex(v,
g);<br> e_b = add_edge(u, v, g);<br> remove_edge(u, v,
g);<br> remove_edge(e, g);<br> }<br> G g;<br> edge_descriptor
e;<br> std::pair<edge_descriptor, bool> e_b;<br> typename
boost::graph_traits<G>::vertex_descriptor u, v;<br> typename
boost::graph_traits<G>::out_edge_iterator iter;<br> };<br><br>
template <class edge_descriptor><br> struct dummy_edge_predicate
{<br> bool operator()(const edge_descriptor& e) const {<br>
return false;<br> }<br> };<br><br> template <class G><br>
struct MutableIncidenceGraphConcept<br> {<br> void constraints()
{<br> function_requires< MutableGraph<G> >();<br>
remove_edge(iter, g);<br> remove_out_edge_if(u, p, g);<br> }<br>
G g;<br> typedef typename boost::graph_traits<G>::edge_descriptor
edge_descriptor;<br> dummy_edge_predicate<edge_descriptor>
p;<br> typename boost::graph_traits<G>::vertex_descriptor
u;<br> typename boost::graph_traits<G>::out_edge_iterator
iter;<br> };<br><br> template <class G><br> struct
MutableBidirectionalGraphConcept<br> {<br> void constraints()
{<br> function_requires< MutableIncidenceGraph<G>
>();<br> remove_in_edge_if(u, p, g);<br> }<br> G g;<br>
typedef typename boost::graph_traits<G>::edge_descriptor
edge_descriptor;<br> dummy_edge_predicate<edge_descriptor>
p;<br> typename boost::graph_traits<G>::vertex_descriptor u;<br>
};<br><br> template <class G><br> struct
MutableEdgeListGraphConcept<br> {<br> void constraints() {<br>
function_requires< MutableGraph<G> >();<br>
remove_edge_if(p, g);<br> }<br> G g;<br> typedef typename
boost::graph_traits<G>::edge_descriptor edge_descriptor;<br>
dummy_edge_predicate<edge_descriptor> p;<br> };<br></pre>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/MutablePropertyGraph.html
==============================================================================
--- trunk/libs/graph/doc/MutablePropertyGraph.html (original)
+++ trunk/libs/graph/doc/MutablePropertyGraph.html Wed Jul 8 07:54:49 2009
@@ -1,150 +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)
-->
-<Head>
-<Title>MutablePropertyGraph</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<title>MutablePropertyGraph</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>
+<br clear="">
-<H2>
-<A NAME="sec:MutablePropertyGraph"></A>
-MutablePropertyGraph
-</H2>
+<h2>
+<a name="sec:MutablePropertyGraph"></a>
+MutablePropertyGraph 可变属性图
+</h2>可变属性图(MutablePropertyGraph)是一个带有关联至顶点或边的属性的 <a
href="./MutableGraph.html">可变图MutableGraph</a>。在增加顶点或边时，可以指
定属性值。
-A MutablePropertyGraph is a <a
-href="./MutableGraph.html">MutableGraph</a> with properties attached
-internally to the vertices and edges. When adding vertices and edges
-the value of the properties can be given.
+<h3>Refinement of 精化自</h3>
-<H3>Refinement of</H3>
+<a href="./MutableGraph.html">可变图MutableGraph</a> 和
+<a href="./PropertyGraph.html">属性图PropertyGraph</a>
-<a href="./MutableGraph.html">MutableGraph</a> and
-<a href="./PropertyGraph.html">PropertyGraph</a>
+<h3>Notation 记号</h3>
-<H3>Notation</H3>
+<table>
-<TABLE>
-
-<TR>
-<TD><tt>G</tt></TD>
-<TD>A type that is a model of Graph.</TD>
-</TR>
-
-<TR>
-<TD><tt>g</tt></TD>
-<TD>An object of type <tt>G</tt>.</TD>
-</TR>
+<tbody><tr>
+<td><tt>G</tt></td>
+<td>一个以 Graph 为模的类型。</td>
+</tr>
-<TR>
-<TD><tt>e</tt></TD>
-<TD>An object of type
<tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD>
-</TR>
+<tr>
+<td><tt>g</tt></td>
+<td>一个类型为 <tt>G</tt> 的对象。</td>
+</tr>
-<TR>
-<TD><tt>u,v</tt></TD>
-<TD>are objects of type
<tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
-</TR>
+<tr>
+<td><tt>e</tt></td>
+<td>一个类型为 <tt>boost::graph_traits<G>::edge_descriptor</tt> 的对
象。</td>
+</tr>
-<TR>
-<TD><TT>ep</TT></TD><TD>is an object of type
<TT>G::edge_property_type</TT></TD>
-</TR>
+<tr>
+<td><tt>u,v</tt></td>
+<td>均为类型 <tt>boost::graph_traits<G>::vertex_descriptor</tt> 的对
象。</td>
+</tr>
-<TR>
-<TD><TT>vp</TT></TD><TD>is an object of type
<TT>G::vertex_property_type</TT></TD>
-</TR>
+<tr>
+<td><tt>ep</tt></td><td>一个类型为 <tt>G::edge_property_type</tt> 的对象
<tt></tt></td>
+</tr>
-</TABLE>
+<tr>
+<td><tt>vp</tt></td><td>一个类型为 <tt>G::vertex_property_type</tt> 的对象
<tt></tt></td>
+</tr>
-<P>
+</tbody></table>
-<H3>Associated Types</H3>
+<h3>Associated Types 关联类型</h3>
-<table border>
+<table border="1">
-<tr>
-<td>Edge Property Type </td>
-<td><TT>graph_traits<G>::edge_property_type</TT></td>
+<tbody><tr>
+<td>边属性类型 </td>
+<td><tt>graph_traits<G>::edge_property_type</tt></td>
</tr>
<tr>
-<td>Vertex Property Type </td>
-<td><TT>graph_traits<G>::vertex_property_type</TT> </td>
+<td>顶点属性类型 </td>
+<td><tt>graph_traits<G>::vertex_property_type</tt> </td>
</tr>
-</table>
+</tbody></table>
-<H3>Valid Expressions</h3>
+<h3>Valid Expressions 有效表达式</h3>
-<table border>
+<table border="1">
-<tr>
-<TD><TT>add_edge(u, v, ep, g)</TT></TD>
-<TD>Inserts the edge <i>(u,v)</i> into the graph, and
-copies object <TT>ep</TT> into the property for that edge.<br>
-Return type: <TT>std::pair<edge_descriptor, bool></TT></TD>
-</TR>
+<tbody><tr>
+<td><tt>add_edge(u, v, ep, g)</tt></td>
+<td>将边 <i>(u,v)</i> 插入到图中，并将对象 <tt>ep</tt> 复制为该边的属性。
<br>返回类型：<tt>std::pair<edge_descriptor, bool></tt></td>
+</tr>
<tr>
-<TD><TT>add_vertex(vp, g)</TT></TD>
-<TD>
-Add a new vertex to the graph and copy <TT>vp</TT> into the
-property for the new vertex. The <TT>vertex_descriptor</TT> for the new
-vertex is returned.<br>
-Return type: <TT>vertex_descriptor</TT>
-</TD>
-</TR>
+<td><tt>add_vertex(vp, g)</tt></td>
+<td>增加一个新的顶点到图中，并复制 <tt>vp</tt> 至该新顶点的属性。返回新顶点
的 <tt>vertex_descriptor</tt>。<br>返回类型：<tt>vertex_descriptor</tt>
+</td>
+</tr>
-</TABLE>
+</tbody></table>
-<H3>Models</H3>
+<h3>Models 模型</h3>
-<UL>
-<LI><TT>adjacency_list</TT></LI>
-</UL>
+<ul>
+<li><tt>adjacency_list</tt></li>
+</ul>
-<H3>Concept Checking Class</H3>
+<h3>Concept Checking Class 概念检查类</h3>
-<P>
-<PRE>
- template <class G>
- struct MutablePropertyGraphConcept
- {
- typedef typename boost::graph_traits<G>::edge_descriptor
edge_descriptor;
- void constraints() {
- function_requires< MutableGraphConcept<G> >();
- v = add_vertex(vp, g);
- p = add_edge(u, v, ep, g);
- }
- G g;
- std::pair<edge_descriptor, bool> p;
- typename boost::graph_traits<G>::vertex_descriptor u, v;
- typename boost::graph_traits<G>::vertex_property_type vp;
- typename boost::graph_traits<G>::edge_property_type ep;
- };
-</PRE>
+<pre> template <class G><br> struct
MutablePropertyGraphConcept<br> {<br> typedef typename
boost::graph_traits<G>::edge_descriptor edge_descriptor;<br> void
constraints() {<br> function_requires< MutableGraphConcept<G>
>();<br> v = add_vertex(vp, g);<br> p = add_edge(u, v, ep,
g);<br> }<br> G g;<br> std::pair<edge_descriptor, bool>
p;<br> typename boost::graph_traits<G>::vertex_descriptor u,
v;<br> typename boost::graph_traits<G>::vertex_property_type
vp;<br> typename boost::graph_traits<G>::edge_property_type
ep;<br> };<br></pre>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/PropertyGraph.html
==============================================================================
--- trunk/libs/graph/doc/PropertyGraph.html (original)
+++ trunk/libs/graph/doc/PropertyGraph.html Wed Jul 8 07:54:49 2009
@@ -1,210 +1,154 @@
-<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>PropertyGraph</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<title>PropertyGraph</title></head>
-<BR Clear>
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
-<H2><A NAME="concept:PropertyGraph"></A>
-PropertyGraph
-</H2>
+<br clear="">
-A PropertyGraph is a graph that has some property associated with each
-of the vertices or edges in the graph. As a given graph may have
-several properties associated with each vertex or edge, a tag is used
-to identity which property is being accessed. The graph provides a
-function which returns a property map object.
+<h2><a name="concept:PropertyGraph"></a>
+PropertyGraph 属性图
+</h2>属性图(PropertyGraph)是有某些属性被关联至其每个顶点或每条边的图。因为
一个给定的图可能有多个属性被关联至各个顶点或边，所以要使用标签来标识要访问的
是哪个属性。图提供了一个返回属性映射对象的函数。
-<P>
+<h3>Refinement of 精化自</h3>
-<H3>Refinement of</H3>
+<a href="./Graph.html">图Graph</a>
-<a href="./Graph.html">Graph</a>
+<h3>Notation 记号</h3>
-<h3>Notation</h3>
-
-<Table>
-<TR>
-<TD><tt>G</tt></TD>
-<TD>A type that is a model of PropertyGraph.</TD>
-</TR>
+<table>
+<tbody><tr>
+<td><tt>G</tt></td>
+<td>一个以 PropertyGraph 为模的类型。</td>
+</tr>
-<TR>
-<TD><tt>g</tt></TD>
-<TD>An object of type <tt>G</tt>.</TD>
-</TR>
+<tr>
+<td><tt>g</tt></td>
+<td>一个类型为 <tt>G</tt> 的对象。</td>
+</tr>
-<TR>
-<TD><tt>X</tt></TD>
-<TD>Either the vertex or edge descriptor type for <tt>G</tt>.</TD>
-</TR>
+<tr>
+<td><tt>X</tt></td>
+<td><tt>G</tt> 的顶点或边描述符类型。</td>
+</tr>
-<TR>
-<TD><tt>x</tt></TD>
-<TD>An object of type <tt>X</tt>.</TD>
-</TR>
+<tr>
+<td><tt>x</tt></td>
+<td>一个类型为 <tt>X</tt> 的对象。</td>
+</tr>
-<TR>
-<TD><tt>Map</tt></TD>
-<TD>The type <tt>boost::property_map<G,
Property>::const_type</tt>.</TD>
-</TR>
+<tr>
+<td><tt>Map</tt></td>
+<td>类型 <tt>boost::property_map<G,
Property>::const_type</tt>.</td>
+</tr>
-<TR>
-<TD><tt>v</tt></TD>
-<TD>An object of type
<tt>boost::property_traits<Map>::value_type</tt>.</TD>
-</TR>
+<tr>
+<td><tt>v</tt></td>
+<td>一个类型为 <tt>boost::property_traits<Map>::value_type</tt> 的对
象。</td>
+</tr>
-<TR>
-<TD><tt>PropertyTag</tt></TD>
-<TD>A type that models the <a href="./PropertyTag.html">PropertyTag</a>
concept.</TD>
-</TR>
+<tr>
+<td><tt>PropertyTag</tt></td>
+<td>一个以 <a href="./PropertyTag.html">PropertyTag</a> 概念为模的类型。
</td>
+</tr>
-<TR>
-<TD><tt>p</tt></TD>
-<TD>An object of type <tt>PropertyTag</tt>.</td>
-</TR>
+<tr>
+<td><tt>p</tt></td>
+<td>一个类型为 <tt>PropertyTag</tt> 的对象。</td>
+</tr>
-<TR>
-<TD><tt>pmap</tt></TD>
-<TD>An object of type <tt>Map</tt>.</td>
-</TR>
+<tr>
+<td><tt>pmap</tt></td>
+<td>一个类型为 <tt>Map</tt> 的对象。</td>
+</tr>
-</table>
+</tbody></table>
-<H3>Associated types</H3>
+<h3>Associated types 关联类型</h3>
-<table border>
+<table border="1">
-<tr>
-<td><pre>boost::property_map<G, PropertyTag>::type</pre>
-The type of the property map for the property specified by
-<TT>PropertyTag</TT>. This type must be a model of <a
-href="../../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>
-with a key type the same as the graph's vertex or edge descriptor type.
+<tbody><tr>
+<td><pre>boost::property_map<G, PropertyTag>::type</pre>由
+<tt>PropertyTag</tt> 指定的属性的属性映射类型。该类型必须符合 <a
href="../../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>，其
键类型与图的顶点或边描述符相同。
</td>
</tr>
<tr>
<td><pre>boost::property_map<G, PropertyTag>::const_type</pre>
-The type of the const property map for the property specified by
-<TT>PropertyTag</TT>. This type must be a model of <a
-href="../../property_map/ReadablePropertyMap.html">ReadablePropertyMap</a>
-with a key type the same as the graph's vertex or edge descriptor type.
+由
+<tt>PropertyTag</tt> 所指定的属性的常量属性映射类型。该类型必须符合 <a
href="../../property_map/ReadablePropertyMap.html">ReadablePropertyMap</a>，其
键类型与图的顶点或边描述符相同。
</td>
</tr>
-</table>
+</tbody></table>
-<h3>Valid Expressions</h3>
+<h3>Valid Expressions 有效表达式</h3>
-<table border>
+<table border="1">
-<tr>
-<td> <TT>get(p, g)</TT> </td>
-<td>
-Returns the property map for the property specified by the
-<tt>PropertyTag</tt> type. The object <tt>p</tt> is only used to
-carry the type.<br>
-Return type: <TT>boost::property_map<G, PropertyTag>::type</TT>
if <TT>g</TT> is mutable and
<br><TT>boost::property_map<G, PropertyTag>::const_type</TT>
otherwise.
+<tbody><tr>
+<td> <tt>get(p, g)</tt> </td>
+<td>返回由
+<tt>PropertyTag</tt> 指定的属性的属性映射。对象 <tt>p</tt> 只是用于获取其类
型。<br>返回类
型：<tt>boost::property_map<G, PropertyTag>::type</tt> if
<tt>g</tt> is mutable and
<br><tt>boost::property_map<G, PropertyTag>::const_type</tt>
otherwise.
</td>
-</TR>
+</tr>
<tr>
-<td> <TT>get(p, g, x)</TT> </td>
-<td>
-Returns the property value (specified by the <tt>PropertyTag</tt> type)
-associated with object <tt>x</tt> (a vertex or edge).
-The object <tt>p</tt> is only used to carry the type.
-This function is equivalent to:<br>
-<tt>get(get(p, g), x)</tt><br>
-Return type: <tt>boost::property_traits<Map>::value_type</tt>
+<td> <tt>get(p, g, x)</tt> </td>
+<td>返回与对象 <tt>x</tt> (一个顶点或一条边)相关联的属性?(由
<tt>PropertyTag</tt> 给定)。对象 <tt>p</tt> 只是用于获取其类型。该函数等价
于：<br>
+<tt>get(get(p, g), x)</tt><br>返回类
型：<tt>boost::property_traits<Map>::value_type</tt>
</td>
-</TR>
+</tr>
<tr>
-<td> <TT>put(p, g, x, v)</TT> </td>
-<td>
-Set the property (specified by the <tt>PropertyTag</tt> type)
-associated with object <tt>x</tt> (a vertex or edge) to
-the value <tt>v</tt>. The object <tt>p</tt> is only used to carry the type.
-This function is equivalent to:<br>
+<td> <tt>put(p, g, x, v)</tt> </td>
+<td>将与对象 <tt>x</tt> (一个顶点或一条边)相关联的属性?(由
<tt>PropertyTag</tt> 给定)设置为 <tt>v</tt>。对象 <tt>p</tt> 只是用于获取其
类型。该函数等价于：<br>
<tt>
pmap = get(p, g);<br>
put(pmap, x, v)
-</tt><br>
-Return type: <TT>void</TT>
+</tt><br>返回类型：<tt>void</tt>
</td>
-</TR>
-
-
-</TABLE>
+</tr>
-<H3>Complexity</H3>
-The <tt>get()</tt> property map function must be constant time.
+</tbody></table>
+<h3>Complexity 复杂度</h3><tt>get()</tt> 属性映射函数必须为常数时间。
-<H3>Models</H3>
+<h3>Models 模型</h3>
-<UL>
-<LI><tt>adjacency_list</tt> with
<tt>VertexProperty=property<vertex_distance_t,int,property<vertex_in_degree_t,int>
></tt> and <tt>PropertyTag=vertex_distance_t</tt>.</li>
-<li><tt>adjacency_list</tt> with
<tt>VertexPropertyTag=property<vertex_distance_t,int,property<vertex_in_degree_t,int>
></TT> and <tt>PropertyTag=vertex_in_degree_t</tt>.</li>
-</UL>
+<ul>
+<li><tt>adjacency_list</tt> 其中
<tt>VertexProperty=property<vertex_distance_t,int,property<vertex_in_degree_t,int>
></tt> 和 <tt>PropertyTag=vertex_distance_t</tt>.</li>
+<li><tt>adjacency_list</tt> 其中
<tt>VertexPropertyTag=property<vertex_distance_t,int,property<vertex_in_degree_t,int>
></tt> 和 <tt>PropertyTag=vertex_in_degree_t</tt>.</li>
+</ul>
-<H3>Concept Checking Class</H3>
-<PRE>
- template <class Graph, class X, class PropertyTag>
- struct PropertyGraphConcept
- {
- typedef typename property_map<G, PropertyTag>::type Map;
- typedef typename property_map<G, PropertyTag>::const_type
const_Map;
- void constraints() {
- function_requires< GraphConcept<G> >();
- function_requires< ReadWritePropertyMapConcept<Map, X>
>();
- function_requires< ReadablePropertyMapConcept<const_Map, X>
>();
+<h3>Concept Checking Class 概念检查类</h3>
- Map pmap = get(PropertyTag(), g);
- pval = get(PropertyTag(), g, x);
- put(PropertyTag(), g, x, pval);
- ignore_unused_variable_warning(pmap);
- }
- void const_constraints(const G& g) {
- const_Map pmap = get(PropertyTag(), g);
- pval = get(PropertyTag(), g, x);
- ignore_unused_variable_warning(pmap);
- }
- G g;
- X x;
- typename property_traits<Map>::value_type pval;
- };
-</PRE>
+<pre> template <class Graph, class X, class PropertyTag><br>
struct PropertyGraphConcept<br> {<br> typedef typename
property_map<G, PropertyTag>::type Map;<br> typedef typename
property_map<G, PropertyTag>::const_type const_Map;<br> void
constraints() {<br> function_requires< GraphConcept<G>
>();<br> function_requires< ReadWritePropertyMapConcept<Map,
X> >();<br> function_requires<
ReadablePropertyMapConcept<const_Map, X> >();<br><br> Map
pmap = get(PropertyTag(), g);<br> pval = get(PropertyTag(), g,
x);<br> put(PropertyTag(), g, x, pval);<br>
ignore_unused_variable_warning(pmap);<br> }<br> void
const_constraints(const G& g) {<br> const_Map pmap =
get(PropertyTag(), g);<br> pval = get(PropertyTag(), g, x);<br>
ignore_unused_variable_warning(pmap);<br> }<br> G g;<br> X
x;<br> typename property_traits<Map>::value_type pval;<br>
};<br></pre>
-<h3>See Also</h3>
+<h3>See Also 参见</h3>
<a href="./property_map.html"><tt>property_map</tt></a>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/VertexAndEdgeListGraph.html
==============================================================================
--- trunk/libs/graph/doc/VertexAndEdgeListGraph.html (original)
+++ trunk/libs/graph/doc/VertexAndEdgeListGraph.html Wed Jul 8 07:54:49
2009
@@ -1,70 +1,49 @@
-<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>VertexAndEdgeListGraph</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<title>VertexAndEdgeListGraph</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>
+<br clear="">
-<H2><A NAME="concept:VertexAndEdgeListGraph"></A>
-VertexAndEdgeListGraph
-</H2>
+<h2><a name="concept:VertexAndEdgeListGraph"></a>
+VertexAndEdgeListGraph 点边列表图
+</h2>点边列表图(VertexAndEdgeListGraph)概念精化自 <a
href="./VertexListGraph.html">点列表图VertexListGraph</a> 和 <a
href="./EdgeListGraph.html">边列表图EdgeListGraph</a> 概念。没有增加其它要
求。
-The VertexAndEdgeListGraph concept refines the <a
-href="./VertexListGraph.html">VertexListGraph</a> and the <a
-href="./EdgeListGraph.html">EdgeListGraph</a> concepts. No further
-requirements are added.
+<h3>Refinement of 精化自</h3>
-<H3>Refinement of</H3>
+<a href="./VertexListGraph.html">点列表图VertexListGraph</a>,
+<a href="./EdgeListGraph.html">边列表图EdgeListGraph</a>
-<a href="./VertexListGraph.html">VertexListGraph</a>,
-<a href="./EdgeListGraph.html">EdgeListGraph</a>
+<h3>Models 模型</h3>
-<H3>Models</H3>
+<ul>
+<li><tt>adjacency_list</tt></li>
+</ul>
-<UL>
-<LI><TT>adjacency_list</TT></LI>
-</UL>
+<h3>See Also 参见</h3>
-<P>
+<a href="./graph_concepts.html">图概念 Graph concepts</a>
-<H3>See Also</H3>
+<h3>Concept Checking Class 概念检查类</h3>
-<a href="./graph_concepts.html">Graph concepts</a>
-
-<H3>Concept Checking Class</H3>
-
-<P>
-<PRE>
- template <class G>
- struct VertexAndEdgeListGraphConcept
- {
- void constraints() {
- function_requires< VertexListGraphConcept<G> >();
- function_requires< EdgeListGraphConcept<G> >();
- }
- };
-</PRE>
+<pre> template <class G><br> struct
VertexAndEdgeListGraphConcept<br> {<br> void constraints() {<br>
function_requires< VertexListGraphConcept<G> >();<br>
function_requires< EdgeListGraphConcept<G> >();<br> }<br>
};<br></pre>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/VertexListGraph.html
==============================================================================
--- trunk/libs/graph/doc/VertexListGraph.html (original)
+++ trunk/libs/graph/doc/VertexListGraph.html Wed Jul 8 07:54:49 2009
@@ -1,154 +1,99 @@
-<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>VertexListGraph</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<title>VertexListGraph</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>
+<br clear="">
-<H2><A NAME="concept:VertexListGraph">
-VertexListGraph
-</H2>
+<h2><a name="concept:VertexListGraph">
+VertexListGraph 点列表图
+</a></h2>
-The <I>VertexListGraph</I> concept refines the <a
-href="./Graph.html">Graph</a> concept, and adds the requirement for
-efficient traversal of all the vertices in the graph.
+<a name="concept:VertexListGraph">点列表图(<i>VertexListGraph</i>)的概念精
化自</a><a href="./Graph.html">图Graph</a>概念，增加了对图中所有顶点进行高效
遍历的要求。
-<H3>Refinement of</H3>
+<h3>Refinement of 精化自</h3>
-<a href="./Graph.html">Graph</a>
+<a href="./Graph.html">图Graph</a>
-<H3>Associated Types</H3>
+<h3>Associated Types 关联类型</h3>
-<Table border>
+<table border="1">
-<tr>
-<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br>
- This tag type must be convertible to <tt>vertex_list_graph_tag</tt>.
+<tbody><tr>
+<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br>这个标
签类型必须可转换为 <tt>vertex_list_graph_tag</tt>.
</td>
</tr>
-<TR>
-<TD><tt>boost::graph_traits<G>::vertex_iterator</tt><br><br>
-A vertex iterator (obtained via <TT>vertices(g)</TT>) provides access
-to all of the vertices in a graph. A vertex iterator type must meet
-the requirements of <a
-href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
The
-value type of the vertex iterator must be the vertex descriptor of the
-graph.
-</TD>
-</TR>
+<tr>
+<td><tt>boost::graph_traits<G>::vertex_iterator</tt><br><br>顶点迭代
器(通过 <tt>vertices(g)</tt> 取得)提供了对图中所有顶点的访问。顶点迭代器类型
必须满足 <a href="../../utility/MultiPassInputIterator.html">多遍输入迭代器
MultiPassInputIterator</a> 的要求。顶点迭代器的值类型必须为图的顶点描述符。
+</td>
+</tr>
<tr>
-<td><tt>boost::graph_traits<G>::vertices_size_type</tt><br><br>
-The unsigned integer type used to represent the number of vertices
-in the graph.
+<td><tt>boost::graph_traits<G>::vertices_size_type</tt><br><br>用于表
示图中顶点数量的无符号整数类型。
</td>
</tr>
-</table>
+</tbody></table>
-<h3>Valid Expressions</h3>
+<h3>Valid Expressions 有效表达式</h3>
-<table border>
+<table border="1">
-<tr>
+<tbody><tr>
<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
</tr>
<tr>
-<td>Vertex Set of the Graph</td>
-<td><a name="sec:vertices"><TT>vertices(g)</TT></a></TD>
-<TD><TT>std::pair<vertex_iterator, vertex_iterator></TT></TD>
-<TD>
-Returns an iterator-range providing access to all the vertices in the
-graph<TT>g</TT>.
-</TD>
-</TR>
+<td>图的顶点集</td>
+<td><a name="sec:vertices"><tt>vertices(g)</tt></a></td>
+<td><tt>std::pair<vertex_iterator, vertex_iterator></tt></td>
+<td>
+返回一个迭代器区间，提供对图 <tt>g</tt> 的所有顶点的访问。
+</td>
+</tr>
<tr>
-<td>Number of Vertices in the Graph </td>
-<td><TT>num_vertices(g)</TT></TD>
-<TD><TT>vertices_size_type</TT></TD>
-<TD>Returns the number of vertices in the graph <TT>g</TT>.</TD>
-</TR>
-
-</TABLE>
-
-
-<H3>Complexity guarantees</H3>
-
-<P>
-The <TT>vertices()</TT> function must return in constant time.
-
-<H3>See Also</H3>
-
-<a href="./graph_concepts.html">Graph concepts</a>
-
-
-<H3>Design Rationale</H3>
-
-One issue in the design of this concept is whether to include the
-refinement from the <a href="./IncidenceGraph.html">IncidenceGraph</a>
-and <a href="./AdjacencyGraph.html">AdjacencyGraph</a> concepts. The
-ability to traverse the vertices of a graph is orthogonal to
-traversing out-edges, so it would make sense to have a VertexListGraph
-concept that only includes vertex traversal. However, such a concept
-would no longer really be a graph, but would just be a set, and the
-STL already has concepts for dealing with such things. However, there
-are many BGL algorithms that need to traverse the vertices and
-out-edges of a graph, so for convenience a concept is needed that
-groups these requirements together, hence the VertexListGraph concept.
-
-
-<H3>Concept Checking Class</H3>
-
-<P>
-<PRE>
- template <class G>
- struct VertexListGraphConcept
- {
- typedef typename boost::graph_traits<G>::vertex_iterator
- vertex_iterator;
- void constraints() {
- function_requires< IncidenceGraphConcept<G> >();
- function_requires< AdjacencyGraphConcept<G> >();
- function_requires<
MultiPassInputIteratorConcept<vertex_iterator> >();
-
- p = vertices(g);
- V = num_vertices(g);
- v = *p.first;
- const_constraints(g);
- }
- void const_constraints(const G& g) {
- p = vertices(g);
- V = num_vertices(g);
- v = *p.first;
- }
- std::pair<vertex_iterator, vertex_iterator> p;
- typename boost::graph_traits<G>::vertex_descriptor v;
- typename boost::graph_traits<G>::vertices_size_type V;
- G g;
- };
-</PRE>
+<td>图中的顶点数 </td>
+<td><tt>num_vertices(g)</tt></td>
+<td><tt>vertices_size_type</tt></td>
+<td>返回图 <tt>g</tt> 的顶点数量。</td>
+</tr>
+
+</tbody></table>
+
+
+<h3>Complexity guarantees 复杂度保证</h3>
+
+<p><tt>vertices()</tt> 函数必须在常数时间内返回。
+
+</p><h3>See Also 参见</h3>
+
+<a href="./graph_concepts.html">图概念 Graph concepts</a>
+
+
+<h3>Design Rationale 设计原理</h3>在这个概念的设计当中，有一个问题，即是否
要包含来自 <a href="./IncidenceGraph.html">IncidenceGraph</a> 和 <a
href="./AdjacencyGraph.html">AdjacencyGraph</a> 概念的精化。遍历图中顶点的能
力与遍历出边的能力是正交的，因此有一个只包含顶点遍历能力的 VertexListGraph
+概念是合理的。不过，这样的一个概念不再是一个真正的图，而只是一个集合，而
STL已经有一个处理这类东西的概念。但还是有很多BGL算法需要需要遍历图的顶点和出
边，所以为了方便起见，还是需要把这些要求集中起来，这就是 VertexListGraph 概
念。
+
+
+<h3>Concept Checking Class 概念检查类</h3>
+
+<pre> template <class G><br> struct VertexListGraphConcept<br>
{<br> typedef typename boost::graph_traits<G>::vertex_iterator
<br> vertex_iterator;<br> void constraints() {<br>
function_requires< IncidenceGraphConcept<G> >();<br>
function_requires< AdjacencyGraphConcept<G> >();<br>
function_requires< MultiPassInputIteratorConcept<vertex_iterator>
>();<br><br> p = vertices(g);<br> V =
num_vertices(g);<br> v = *p.first;<br>
const_constraints(g);<br> }<br> void const_constraints(const G&
g) {<br> p = vertices(g);<br> V = num_vertices(g);<br> v =
*p.first;<br> }<br> std::pair<vertex_iterator, vertex_iterator>
p;<br> typename boost::graph_traits<G>::vertex_descriptor
v;<br> typename boost::graph_traits<G>::vertices_size_type
V;<br> G g;<br> };<br></pre>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/constructing_algorithms.html
==============================================================================
--- trunk/libs/graph/doc/constructing_algorithms.html (original)
+++ trunk/libs/graph/doc/constructing_algorithms.html Wed Jul 8 07:54:49
2009
@@ -1,183 +1,62 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
--
-- Distributed under the Boost Software License, Version 1.0.
-- (See accompanying file LICENSE_1_0.txt or copy at
-- http://www.boost.org/LICENSE_1_0.txt)
-->
-<Head>
-<Title>Boost Graph Library: Constructing Graph Algorithms</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>Constructing graph algorithms with BGL</H1>
-
-<P>
-The <I>main</I> goal of BGL is not to provide a nice graph class, or
-to provide a comprehensive set of reusable graph algorithms (though
-these are goals). The main goal of BGL is to encourage others to
-write reusable graph algorithms. By reusable we mean maximally
-reusable. Generic programming is a methodology for making algorithms
-maximally reusable, and in this section we will discuss how to apply
-generic programming to constructing graph algorithms.
-
-<P>
-To illustrate the generic programming process we will step though the
-construction of a graph coloring algorithm. The graph coloring problem
-(or more specifically, the vertex coloring problem) is to label each
-vertex in a graph <i>G</i> with a color such that no two adjacent
-vertices are labeled with the same color and such that the minimum
-number of colors are used. In general, the graph coloring problem is
-NP-complete, and therefore it is impossible to find an optimal
-solution in a reasonable amount of time. However, there are many
-algorithms that use heuristics to find colorings that are close to the
-minimum.
-
-<P>
-The particular algorithm we present here is based on the linear time
-<TT>SEQ</TT> subroutine that is used in the estimation of sparse
-Jacobian and Hessian matrices [<A
-HREF="bibliography.html#curtis74:_jacob">9</A>,<A
-HREF="bibliography.html#coleman84:_estim_jacob">7</A>,<A
-HREF="bibliography.html#coleman85:_algor">6</A>]. This algorithm
-visits all of the vertices in the graph according to the order defined
-by the input order. At each vertex the algorithm marks the colors of
-the adjacent vertices, and then chooses the smallest unmarked color
-for the color of the current vertex. If all of the colors are already
-marked, a new color is created. A color is considered marked if its
-mark number is equal to the current vertex number. This saves the
-trouble of having to reset the marks for each vertex. The
-effectiveness of this algorithm is highly dependent on the input
-vertex order. There are several ordering algorithms, including the
-<I>largest-first</I> [<A HREF="bibliography.html#welsch67">31</A>],
-<I>smallest-last</I> [<a
-href="bibliography.html#matula72:_graph_theory_computing">29</a>], and
-<I>incidence degree</I> [<a
-href="bibliography.html#brelaz79:_new">32</a>] algorithms, which
-improve the effectiveness of this coloring algorithm.
-
-<P>
-The first decision to make when constructing a generic graph algorithm
-is to decide what graph operations are necessary for implementing the
-algorithm, and which graph concepts the operations map to. In this
-algorithm we will need to traverse through all of the vertices to
-intialize the vertex colors. We also need to access the adjacent
-vertices. Therefore, we will choose the <a
-href="./VertexListGraph.html">VertexListGraph</a> concept because it
-is the minimum concept that includes these operations. The graph type
-will be parameterized in the template function for this algorithm. We
-do not restrict the graph type to a particular graph class, such as
-the BGL <a href="./adjacency_list.html"><TT>adjacency_list</TT></a>,
-for this would drastically limit the reusability of the algorithm (as
-most algorithms written to date are). We do restrict the graph type to
-those types that model <a
-href="./VertexListGraph.html">VertexListGraph</a>. This is enforced by
-the use of those graph operations in the algorithm, and furthermore by
-our explicit requirement added as a concept check with
-<TT>function_requires()</TT> (see Section <A
-HREF="../../concept_check/concept_check.htm">Concept
-Checking</A> for more details about concept checking).
-
-<P>
-Next we need to think about what vertex or edge properties will be
-used in the algorithm. In this case, the only property is vertex
-color. The most flexible way to specify access to vertex color is to
-use the propery map interface. This gives the user of the
-algorithm the ability to decide how they want to store the properties.
-Since we will need to both read and write the colors we specify the
-requirements as <a
-href="../../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>.
The
-<TT>key_type</TT> of the color map must be the
-<TT>vertex_descriptor</TT> from the graph, and the <TT>value_type</TT>
-must be some kind of integer. We also specify the interface for the
-<TT>order</TT> parameter as a property map, in this case a <a
-href="../../property_map/ReadablePropertyMap.html">ReadablePropertyMap</a>.
For
-order, the <TT>key_type</TT> is an integer offset and the
-<TT>value_type</TT> is a <TT>vertex_descriptor</TT>. Again we enforce
-these requirements with concept checks. The return value of this
-algorithm is the number of colors that were needed to color the graph,
-hence the return type of the function is the graph's
-<TT>vertices_size_type</TT>. The following code shows the interface for our
-graph algorithm as a template function, the concept checks, and some
-typedefs. The implementation is straightforward, the only step not
-discussed above is the color initialization step, where we set the
-color of all the vertices to ``uncolored''.
-
-<P>
-<PRE>
-namespace boost {
- template <class VertexListGraph, class Order, class Color>
- typename graph_traits<VertexListGraph>::vertices_size_type
- sequential_vertex_color_ting(const VertexListGraph& G,
- Order order, Color color)
- {
- typedef graph_traits<VertexListGraph> GraphTraits;
- typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
- typedef typename GraphTraits::vertices_size_type size_type;
- typedef typename property_traits<Color>::value_type ColorType;
- typedef typename property_traits<Order>::value_type OrderType;
-
- function_requires< VertexListGraphConcept<VertexListGraph>
>();
- function_requires< ReadWritePropertyMapConcept<Color,
vertex_descriptor> >();
- function_requires< IntegerConcept<ColorType> >();
- function_requires< size_type,
ReadablePropertyMapConcept<Order> >();
- typedef typename same_type<OrderType, vertex_descriptor>::type
req_same;
-
- size_type max_color = 0;
- const size_type V = num_vertices(G);
- std::vector<size_type>
- mark(V, numeric_limits_max(max_color));
-
- typename GraphTraits::vertex_iterator v, vend;
- for (tie(v, vend) = vertices(G); v != vend; ++v)
- color[*v] = V - 1; // which means "not colored"
-
- for (size_type i = 0; i < V; i++) {
- vertex_descriptor current = order[i];
-
- // mark all the colors of the adjacent vertices
- typename GraphTraits::adjacency_iterator ai, aend;
- for (tie(ai, aend) = adjacent_vertices(current, G); ai != aend; ++ai)
- mark[color[*ai]] = i;
-
- // find the smallest color unused by the adjacent vertices
- size_type smallest_color = 0;
- while (smallest_color < max_color && mark[smallest_color]
== i)
- ++smallest_color;
-
- // if all the colors are used up, increase the number of colors
- if (smallest_color == max_color)
- ++max_color;
-
- color[current] = smallest_color;
- }
- return max_color;
- }
-} // namespace boost
-</PRE>
+<title>Boost Graph Library: Constructing Graph Algorithms</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>Constructing graph algorithms with BGL 用BGL构建图算法</h1>
+
+<p>BGL的<i>主要</i>目标不是提供一个漂亮的图类，也不是提供一套全面的可复用的
图算法(虽然这些也是目标之一)。BGL的主要目标是鼓励其
+它人写出可复用的图算法。我们所指的可复用是最大程度的可复用。泛型编程是令算
法最大程度可复用的一种方法，本节我们将讨论如何将泛型编程应用于图算法的
+构造。
+</p><p>为了示范泛型编程的过程，我们将一步步地构造一个图着色算法。图的着色问
题(或者更具体地说，顶点着色问题)是指，对图 <i>G</i> 中的每个顶点标识一种颜
色，使得没有两个相邻的顶点被标以相同的颜色，且只使用最小数量的颜色。一般来
说，图着色问题是NP-完全的，因此不可能在合理的时间内找到最优解。但是，有许多
算法可以使用启发式方法找到接近最小数量的颜色。
+
+</p><p>我们在这里介绍的具体算法是基于线性时间的<tt>SEQ子程序的，该子程序用
于稀疏 </tt>Jacobian 和 Hessian 矩阵[<a
href="bibliography.html#curtis74:_jacob">9</a>,<a
href="bibliography.html#coleman84:_estim_jacob">7</a>,<a
href="bibliography.html#coleman85:_algor">6</a>]
+的估算。该算法根据由输入顺序所确定的次序遍历图中所有顶点。对于每个顶点，该
算法标记其相邻顶点的颜色，然后选择最小的未标记颜色作为当前顶点的颜色。
+如果所有颜色都已被标记，则创建一种新颜色。如果一种颜色的标记号等于当前顶点
号，则认为该颜色是已被标记的。这样可以减少麻烦，不必重设每个顶点的标
+记。该算法的效率高度依赖于输入顶点的顺序。有多种顺序算法，包括
+<i>最大优先</i>[<a href="bibliography.html#welsch67">31</a>],
+<i>最小最后</i>[<a
href="bibliography.html#matula72:_graph_theory_computing">29</a>], 和
+<i>关联度</i>[<a href="bibliography.html#brelaz79:_new">32</a>] 算法，它们
可以改进这个着色算法的效率。
+
+</p><p>在构造一个泛型的图算法时，首先要做的决定是，实现该算法需要哪些图操
作，以及这些操作映射到哪些图概念。在这个算法中，我们需要遍历所有顶点，以初始
化顶点的颜色。我们还需要访问邻接顶点。因此，我们选择了 <a
href="./VertexListGraph.html">VertexListGraph</a> 概念，因为它是包含这些操作
的最小概念。图的类型将在该算法的模板函数中参数化。我们不将图的类型局限于某个
特定的图类，如 BGL <a
href="./adjacency_list.html"><tt>adjacency_list</tt></a>，因为这样会大大局限
了算法的可重用性(正如当前多数算法所写的那样)。我们对于图的类型，只限制了它必
须符合 <a href="./VertexListGraph.html">VertexListGraph</a>。这样才可以在算
法中使用所需的图操作，此外，我们的明确要求是通过
+<tt>function_requires()</tt> 这样的概念检查来施加的(关于概念检查的详细说
明，参见 <a href="../../concept_check/concept_check.htm">概念检查Concept
+Checking</a> 章节)。
+
+</p><p>下一步我们需要考虑，在算法中要使用哪些顶点属性或边属性。在这个例子
中，唯一的属性是顶点颜色。指定访问顶点颜色的最灵活方式是，使用属性映射接口。
这使得该算法的用户能够决定他们想如何保存该属性。因为我们既要读出也要写入颜
色，所以我们给出 <a
href="../../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>
的要求。这个颜色映射的
+<tt>key_type</tt> 必须是来自于图的
+<tt>vertex_descriptor</tt>，而 <tt>value_type</tt>
+则必须是某种整数。我们还指定
+<tt>order</tt> 参数的接口是一个属性映射，在这个例子中是 <a
href="../../property_map/ReadablePropertyMap.html">ReadablePropertyMap</a>。
对于
+order，其 <tt>key_type</tt> 是一个整数偏移量，而
+<tt>value_type</tt> 是一个 <tt>vertex_descriptor</tt>。同样，我们用概念检查
来施加这些要求。该算法的返回值是我们对该图进行着色所需要的颜色数量，因此函数
的返回类型是图的
+<tt>vertices_size_type</tt>。以下代码用一个模板函数、概念检查和一些
+typedef 来给出我们的图算法的接口。实现是简单明了的，前面没有讨论到的唯一步
骤是颜色初始化步骤，我们将所有顶点的颜色设为"未着色"。
-<P>
+</p><pre>namespace boost {<br> template <class VertexListGraph, class
Order, class Color><br> typename
graph_traits<VertexListGraph>::vertices_size_type<br>
sequential_vertex_color_ting(const VertexListGraph& G, <br> Order
order, Color color)<br> {<br> typedef
graph_traits<VertexListGraph> GraphTraits;<br> typedef typename
GraphTraits::vertex_descriptor vertex_descriptor;<br> typedef typename
GraphTraits::vertices_size_type size_type;<br> typedef typename
property_traits<Color>::value_type ColorType;<br> typedef typename
property_traits<Order>::value_type OrderType;<br><br>
function_requires< VertexListGraphConcept<VertexListGraph>
>();<br> function_requires< ReadWritePropertyMapConcept<Color,
vertex_descriptor> >();<br> function_requires<
IntegerConcept<ColorType> >();<br> function_requires<
size_type, ReadablePropertyMapConcept<Order> >();<br> typedef
typename same_type<OrderType, vertex_descriptor>::type
req_same;<br> <br> size_type max_color = 0;<br> const size_type V
= num_vertices(G);<br> std::vector<size_type> <br> mark(V,
numeric_limits_max(max_color));<br> <br> typename
GraphTraits::vertex_iterator v, vend;<br> for (tie(v, vend) =
vertices(G); v != vend; ++v)<br> color[*v] = V - 1; // 表示 "未着
色"<br> <br> for (size_type i = 0; i < V; i++) {<br>
vertex_descriptor current = order[i];<br><br> // 标记邻接顶点的所有颜色
<br> typename GraphTraits::adjacency_iterator ai, aend;<br> for
(tie(ai, aend) = adjacent_vertices(current, G); ai != aend;
++ai)<br> mark[color[*ai]] = i; <br><br> // 找出邻接顶点未使用的
最小颜色<br> size_type smallest_color = 0;<br> while
(smallest_color < max_color && mark[smallest_color] == i)
<br> ++smallest_color;<br><br> // 如果所有颜色都被用，则递增颜色
数量<br> if (smallest_color == max_color)<br>
++max_color;<br><br> color[current] = smallest_color;<br> }<br>
return max_color;<br> }<br>} // namespace boost<br></pre>
+
+<p>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
-Indiana University (<A
-HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
-<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>,
Indiana University (<A
HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
-Indiana University (<A
-HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+</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>)<br>
+<a href="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</a>,
Indiana University (<a
href="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</a>)<br>
+<a href="http://www.osl.iu.edu/%7Elums";>Andrew Lumsdaine</a>,
+Indiana University (<a href="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
-</BODY>
-</HTML>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/graph_concepts.html
==============================================================================
--- trunk/libs/graph/doc/graph_concepts.html (original)
+++ trunk/libs/graph/doc/graph_concepts.html Wed Jul 8 07:54:49 2009
@@ -1,493 +1,361 @@
-<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 Concepts</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="chapter:graph-concepts"></A>
-Graph Concepts
-</H1>
-
-<P>
-The heart of the Boost Graph Library (BGL) is the interface, or
-concepts (in the parlance of generic programming), that define how a
-graph can be examined and manipulated in a data-structure neutral
-fashion. In fact, the BGL interface need not even be implemented using
-a data-structure, as for some problems it is easier or more efficient
-to define a graph implicitly based on some functions.
-
-<P>
-The BGL interface does not appear as a single graph concept. Instead
-it is factored into much smaller peices. The reason for this is that
-the purpose of a concept is to summarize the requirements for
-<i>particular</i> algorithms. Any one algorithm does not need every
-kind of graph operation, typically only a small subset. Furthermore,
-there are many graph data-structures that can not provide efficient
-implementations of all the operations, but provide highly efficient
-implementations of the operations necessary for a particular algorithm
-. By factoring the graph interface into many smaller concepts we
-provide the graph algorithm writer with a good selection from which to
-choose the concept that is the closest match for their algorithm.
-
-<H2>Graph Structure Concepts Overview</H2>
-
-<P>
-<A HREF="#fig:graph-concepts">Figure 1</A> shows the refinements
-relations between the graph concepts. The reason for factoring the
-graph interface into so many concepts is to encourage algorithm
-interfaces to require and use only the minimum interface of a graph,
-thereby increasing the reusability of the algorithm.
+<title>Boost Graph Concepts</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="chapter:graph-concepts"></a>
+Graph Concepts 图的概念
+</h1>
+
+<p>Boost图库(BGL)的核心在于接口，或者说概念(用泛型编程的话说)，它定义了如何
以数据结构中立的方式来验证和处理一个图。事实上，BGL接口甚至不必用一个数据结
构去实现，对于某些问题来说，基于某些函数来隐式地定义一个图可能更容易也更高
效。
+
+</p><p>BGL接口不是作为单一的图的概念出现的。相反，它被分解为小得多的碎片。
其原因在于，概念的目的是概括某些特定算法的要求。任何一个算法
+都不需要所有类型的图操作，通常只需要其中一个小的子集。此外，有许多图数据结
构不能为所有操作提供高效的实现，而对于特定算法而言，提供某些操作的高效
+实现是必需的。通过将图接口分解为很多小的概念，我们为图算法的作者提供了好的
选择，他可以选择与其算法最为匹配的概念。
+</p><h2>Graph Structure Concepts Overview 图结构概念介绍</h2>
+
+<p>
+<a href="#fig:graph-concepts">图 1</a> 给出了各种图概念间的精化关系。将图的
接口分解为这么多的概念，其原因是鼓励算法的接口只要求和使用最小的图接口，从而
增加算法的复用性。
+
+
+</p>
+<div align="center"><a name="fig:graph-concepts"></a>
+<table>
+<caption align="bottom"><strong>图 1:</strong>
+图的概念和精化关系。
+</caption>
+<tbody><tr><td><img src="./figs/concepts.gif"></td></tr>
+</tbody></table>
+</div>
<p></p>
-<DIV ALIGN="CENTER"><A NAME="fig:graph-concepts"></A></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG>
-The graph concepts and refinement relationships.
-</CAPTION>
-<TR><TD><IMG SRC="./figs/concepts.gif"></TD></TR>
-</TABLE>
-</DIV>
-<p></p>
-<A HREF="#tab:graph-concept-reqs">Table 1</A>
-gives a summary of the valid expressions and associated types for the
-graph concepts and provides links to the detailed descriptions of
-each of the concepts. The notation used in the table is as follows.
-
-<h3>Notation</h3>
-
-<Table>
-<TR>
-<TD><tt>G</tt></TD>
-<TD>A type that is a model of Graph.</TD>
-</TR>
-
-<TR>
-<TD><tt>g</tt></TD>
-<TD>An object of type <tt>G</tt>.</TD>
-</TR>
-
-<TR>
-<TD><tt>e</tt></TD>
-<TD>An object of type
<tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD>
-</TR>
-
-<TR>
-<TD><tt>e_iter</tt></TD>
-<TD>An object of type
<tt>boost::graph_traits<G>::out_edge_iterator</tt>.</TD>
-</TR>
-
-<TR>
-<TD><tt>u,v</tt></TD>
-<TD>Are objects of type
<tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
-</TR>
-
-<TR>
-<TD><TT>ep</TT></TD><TD>is an object of type
<TT>G::edge_property_type</TT></TD>
-</TR>
-
-<TR>
-<TD><TT>vp</TT></TD><TD>is an object of type
<TT>G::vertex_property_type</TT></TD>
-</TR>
-
-<TR>
-<TD><tt>Property</tt></TD>
-<TD>A type used to specify a vertex or edge property.</TD>
-</TR>
-
-<TR>
-<TD><tt>property</tt></TD>
-<TD>An object of type <tt>Property</tt>.</td>
-</TR>
-
-</table>
-
-
-
-
-<P>
-<BR><P></P>
-<DIV ALIGN="CENTER"><A NAME="tab:graph-concept-reqs"></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Table 1:</STRONG>
- Summary of the graph concepts.
- </CAPTION>
-<TR><TD>
-<TABLE border>
-<TR><TH ALIGN="LEFT">
-<B>Expression</B> </TH>
-<TH ALIGN="LEFT" VALIGN="TOP"> <B>Return Type or Description</B> </TH>
-</TR>
-<TR><TD ALIGN="LEFT" COLSPAN=2>
- <a href="./Graph.html">Graph</a> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::vertex_descriptor</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> The type for
- vertex representative objects. </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::edge_descriptor</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> The type for
- edge representative objects. </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::directed_category</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> Directed or undirected? </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::edge_parallel_category</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> Allow parallel edges? </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::traversal_category</TT> </TD> <TD
-ALIGN="LEFT" VALIGN="TOP">The ways in which the vertices and edges of
-the graph can be visited.</TD>
-</TR>
+<a href="#tab:graph-concept-reqs">表 1</a>
+概括了各个图概念的有效表达式和关联类型，并提供了到各个概念的详细说明的链
接。表中所使用的记号如下。
+
+<h3>Notation 记号</h3>
+
+<table>
+<tbody><tr>
+<td><tt>G</tt></td>
+<td>一个符合 Graph 的类型。</td>
+</tr>
+
+<tr>
+<td><tt>g</tt></td>
+<td>一个类型为 <tt>G</tt> 的对象。</td>
+</tr>
+
+<tr>
+<td><tt>e</tt></td>
+<td>一个类型为 <tt>boost::graph_traits<G>::edge_descriptor</tt> 的对
象。</td>
+</tr>
+
+<tr>
+<td><tt>e_iter</tt></td>
+<td>一个类型为 <tt>boost::graph_traits<G>::out_edge_iterator</tt> 的
对象。</td>
+</tr>
+
+<tr>
+<td><tt>u,v</tt></td>
+<td>类型为 <tt>boost::graph_traits<G>::vertex_descriptor</tt> 的对
象。</td>
+</tr>
+
+<tr>
+<td><tt>ep</tt></td><td>一个类型为 <tt>G::edge_property_type 的对象
</tt></td>
+</tr>
+
+<tr>
+<td><tt>vp</tt></td><td>一个类型为 <tt>G::vertex_property_type 的对象
</tt></td>
+</tr>
+
+<tr>
+<td><tt>Property</tt></td>
+<td>用于指定顶点属性或边属性的一个类型。</td>
+</tr>
+
+<tr>
+<td><tt>property</tt></td>
+<td>一个类型为 <tt>Property</tt> 的对象。</td>
+</tr>
+
+</tbody></table>
+
+
+
+
+<p></p>
+<div align="center"><a name="tab:graph-concept-reqs"></a>
+<table>
+<caption align="bottom"><strong>表 1:</strong>
+ 图概念的概括。
+ </caption>
+<tbody><tr><td>
+<table border="1">
+<tbody><tr><th align="left">
+<b>Expression 表达式</b> </th>
+<th align="left" valign="top"> <b>Return Type or Description 返回类型或说明
</b> </th>
+</tr>
+<tr><td colspan="2" align="left">
+ <a href="./Graph.html">Graph</a> </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::vertex_descriptor</tt> </td>
+<td align="left" valign="top">代表顶点的对象的类型。 </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::edge_descriptor</tt> </td>
+<td align="left" valign="top">代表边的对象的类型。 </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::directed_category</tt> </td>
+<td align="left" valign="top">有向的或是无向的？ </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::edge_parallel_category</tt> </td>
+<td align="left" valign="top">是否允许平行边？ </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::traversal_category</tt> </td> <td
align="left" valign="top">图的哪些顶点和边可被访问的方式。</td>
+</tr>
<!---------------------------------------------------------------->
-<TR><TD ALIGN="LEFT" COLSPAN=2>
- <a href="./IncidenceGraph.html">IncidenceGraph</a> refines Graph </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::out_edge_iterator</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> Iterate through
- the out-edges. </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::degree_size_type</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> The integer type for
-vertex degee. </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>out_edges(v, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<out_edge_iterator,
out_edge_iterator></TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>source(e, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>target(e, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>out_degree(v, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD>
-</TR>
+<tr><td colspan="2" align="left">
+ <a href="./IncidenceGraph.html">IncidenceGraph</a> 精化自 Graph </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::out_edge_iterator</tt> </td>
+<td align="left" valign="top">对出边进行迭代。 </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::degree_size_type</tt> </td>
+<td align="left" valign="top">用于表示顶点度数的整数类型。 </td>
+</tr>
+<tr><td align="left">
+<tt>out_edges(v, g)</tt> </td>
+<td align="left" valign="top"> <tt>std::pair<out_edge_iterator,
out_edge_iterator></tt> </td>
+</tr>
+<tr><td align="left">
+<tt>source(e, g)</tt> </td>
+<td align="left" valign="top"> <tt>vertex_descriptor</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>target(e, g)</tt> </td>
+<td align="left" valign="top"> <tt>vertex_descriptor</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>out_degree(v, g)</tt> </td>
+<td align="left" valign="top"> <tt>degree_size_type</tt> </td>
+</tr>
<!---------------------------------------------------------------->
-<TR><TD ALIGN="LEFT" COLSPAN=2>
- <a href="./BidirectionalGraph.html">BidirectionalGraph</a> refines
- IncidenceGraph </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::in_edge_iterator</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the in-edges. </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>in_edges(v, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<in_edge_iterator,
in_edge_iterator></TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>in_degree(v, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>degree(e, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD>
-</TR>
+<tr><td colspan="2" align="left">
+ <a href="./BidirectionalGraph.html">BidirectionalGraph</a> 精化自
+ IncidenceGraph </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::in_edge_iterator</tt> </td>
+<td align="left" valign="top">对入边进行迭代。 </td>
+</tr>
+<tr><td align="left">
+<tt>in_edges(v, g)</tt> </td>
+<td align="left" valign="top"> <tt>std::pair<in_edge_iterator,
in_edge_iterator></tt> </td>
+</tr>
+<tr><td align="left">
+<tt>in_degree(v, g)</tt> </td>
+<td align="left" valign="top"> <tt>degree_size_type</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>degree(e, g)</tt> </td>
+<td align="left" valign="top"> <tt>degree_size_type</tt> </td>
+</tr>
<!---------------------------------------------------------------->
-<TR><TD ALIGN="LEFT" COLSPAN=2>
-<a href="./AdjacencyGraph.html">AdjacencyGraph</a> refines Graph</TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::adjacency_iterator</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> Iterate through
- adjacent vertices. </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>adjacent_vertices(v, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"><TT>std::pair<adjacency_iterator,
adjacency_iterator></TT> </TD>
-</TR>
+<tr><td colspan="2" align="left">
+<a href="./AdjacencyGraph.html">AdjacencyGraph</a> 精化自 Graph</td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::adjacency_iterator</tt> </td>
+<td align="left" valign="top">对邻接顶点进行迭代。 </td>
+</tr>
+<tr><td align="left">
+<tt>adjacent_vertices(v, g)</tt> </td>
+<td align="left" valign="top"><tt>std::pair<adjacency_iterator,
adjacency_iterator></tt> </td>
+</tr>
<!---------------------------------------------------------------->
-<TR><TD ALIGN="LEFT" COLSPAN=2>
-<a href="./VertexListGraph.html">VertexListGraph</a> refines
- IncidenceGraph and AdjacencyGraph </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::vertex_iterator</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the
- graph's vertex set. </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::vertices_size_type</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> The unsigned integer type for
-number of vertices in the graph. </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>vertices(g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"><TT>std::pair<vertex_iterator,
vertex_iterator></TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>num_vertices(g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertices_size_type</TT> </TD>
-</TR>
+<tr><td colspan="2" align="left">
+<a href="./VertexListGraph.html">VertexListGraph</a> 精化自
+ IncidenceGraph 和 AdjacencyGraph </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::vertex_iterator</tt> </td>
+<td align="left" valign="top">对图的顶点集进行迭代。 </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::vertices_size_type</tt> </td>
+<td align="left" valign="top">用于表示图中顶点数的无符号整数类型。 </td>
+</tr>
+<tr><td align="left">
+<tt>vertices(g)</tt> </td>
+<td align="left" valign="top"><tt>std::pair<vertex_iterator,
vertex_iterator></tt> </td>
+</tr>
+<tr><td align="left">
+<tt>num_vertices(g)</tt> </td>
+<td align="left" valign="top"> <tt>vertices_size_type</tt> </td>
+</tr>
<!---------------------------------------------------------------->
-<TR><TD ALIGN="LEFT" COLSPAN=2>
-<a href="./EdgeListGraph.html">EdgeListGraph</a> refines Graph</TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::edge_iterator</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the graph's
- edge set. </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::graph_traits<G>::edges_size_type</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> The unsigned integer type for
-number of edges in the graph. </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>edges(g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<edge_iterator,
edge_iterator></TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>num_edges(g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>edges_size_type</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>source(e, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>target(e, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
-</TR>
+<tr><td colspan="2" align="left">
+<a href="./EdgeListGraph.html">EdgeListGraph</a> 精化自 Graph</td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::edge_iterator</tt> </td>
+<td align="left" valign="top">对图的边集进行迭代。 </td>
+</tr>
+<tr><td align="left">
+<tt>boost::graph_traits<G>::edges_size_type</tt> </td>
+<td align="left" valign="top">用于表示图中边数的无符号整数类型。 </td>
+</tr>
+<tr><td align="left">
+<tt>edges(g)</tt> </td>
+<td align="left" valign="top"> <tt>std::pair<edge_iterator,
edge_iterator></tt> </td>
+</tr>
+<tr><td align="left">
+<tt>num_edges(g)</tt> </td>
+<td align="left" valign="top"> <tt>edges_size_type</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>source(e, g)</tt> </td>
+<td align="left" valign="top"> <tt>vertex_descriptor</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>target(e, g)</tt> </td>
+<td align="left" valign="top"> <tt>vertex_descriptor</tt> </td>
+</tr>
<!---------------------------------------------------------------->
-<TR><TD ALIGN="LEFT" COLSPAN=2>
-<a href="./AdjacencyMatrix.html">AdjacencyMatrix</a> refines Graph</TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>edge(u, v, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<edge_descriptor,
bool></TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT" COLSPAN=2>
-<a href="./MutableGraph.html">MutableGraph</a> refines
- Graph</TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>add_vertex(g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>clear_vertex(v, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>remove_vertex(v, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>add_edge(u, v, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<edge_descriptor,
bool></TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>remove_edge(u, v, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>remove_edge(e, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>remove_edge(e_iter, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
-</TR>
+<tr><td colspan="2" align="left">
+<a href="./AdjacencyMatrix.html">AdjacencyMatrix</a> 精化自 Graph</td>
+</tr>
+<tr><td align="left">
+<tt>edge(u, v, g)</tt> </td>
+<td align="left" valign="top"> <tt>std::pair<edge_descriptor,
bool></tt> </td>
+</tr>
+<tr><td colspan="2" align="left">
+<a href="./MutableGraph.html">MutableGraph</a> 精化自
+ Graph</td>
+</tr>
+<tr><td align="left">
+<tt>add_vertex(g)</tt> </td>
+<td align="left" valign="top"> <tt>vertex_descriptor</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>clear_vertex(v, g)</tt> </td>
+<td align="left" valign="top"> <tt>void</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>remove_vertex(v, g)</tt> </td>
+<td align="left" valign="top"> <tt>void</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>add_edge(u, v, g)</tt> </td>
+<td align="left" valign="top"> <tt>std::pair<edge_descriptor,
bool></tt> </td>
+</tr>
+<tr><td align="left">
+<tt>remove_edge(u, v, g)</tt> </td>
+<td align="left" valign="top"> <tt>void</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>remove_edge(e, g)</tt> </td>
+<td align="left" valign="top"> <tt>void</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>remove_edge(e_iter, g)</tt> </td>
+<td align="left" valign="top"> <tt>void</tt> </td>
+</tr>
<!---------------------------------------------------------------->
-<TR><TD ALIGN="LEFT" COLSPAN=2>
-<a href="./MutablePropertyGraph.html">MutablePropertyGraph</a> refines
- Graph</TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>add_vertex(vp, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>add_edge(u, v, ep, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair<edge_descriptor,
- bool></TT> </TD>
-</TR>
+<tr><td colspan="2" align="left">
+<a href="./MutablePropertyGraph.html">MutablePropertyGraph</a> 精化自
+ Graph</td>
+</tr>
+<tr><td align="left">
+<tt>add_vertex(vp, g)</tt> </td>
+<td align="left" valign="top"> <tt>vertex_descriptor</tt> </td>
+</tr>
+<tr><td align="left">
+<tt>add_edge(u, v, ep, g)</tt> </td>
+<td align="left" valign="top"> <tt>std::pair<edge_descriptor,
+ bool></tt> </td>
+</tr>
<!---------------------------------------------------------------->
-<TR>
-<TD ALIGN="LEFT" COLSPAN=2>
-<a href="./PropertyGraph.html">PropertyGraph</a> refines Graph</TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::property_map<G, Property>::type</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP">Type for a mutable property map.</TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>boost::property_map<G, Property>::const_type</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP">Type for a non-mutable property map.</TD>
-</TR>
-<TR><TD ALIGN="LEFT">
-<TT>get(property, g)</TT> </TD>
-<TD ALIGN="LEFT" VALIGN="TOP"> Function to get a property map. </TD>
-</TR>
-
-<TR><TD ALIGN="LEFT">
-<TT>get(property, g, x)</TT>
-</TD>
-<TD ALIGN="LEFT" VALIGN="TOP">Get property value for vertex or edge
<tt>x</tt>. </TD>
-</TR>
-
-<TR><TD ALIGN="LEFT">
-<TT>put(property, g, x, v)</TT>
-</TD>
-<TD ALIGN="LEFT" VALIGN="TOP">Set property value for vertex or edge
-<tt>x</tt> to <tt>v</tt>. </TD>
-</TR>
-
-</table>
-</table>
-</DIV><P></P>
-<BR>
-
-<P>
-
-<H2><A NAME="sec:undirected-graphs"></A>
-Undirected Graphs
-</H2>
-
-<P>
-The interface that the BGL provides for accessing and manipulating an
-undirected graph is the same as the interface for directed graphs
-described in the following sections, however there are some
-differences in the behaviour and semantics. For example, in a
-directed graph we can talk about out-edges and in-edges of a vertex.
-In an undirected graph there is no ``in'' and ``out'', there are just
-edges incident to a vertex. Nevertheless, in the BGL we still use the
-<TT>out_edges()</TT> function (or <TT>in_edges()</TT>) to access the
-incident edges in an undirected graph. Similarly, an undirected edge
-has no ``source'' and ``target'' but merely an unordered pair of
-vertices, but in the BGL we still use <TT>source()</TT> and
-<TT>target()</TT> to access these vertices. The reason the BGL does
-not provide a separate interface for undirected graphs is that many
-algorithms on directed graphs also work on undirected graphs, and it
-would be inconvenient to have to duplicate the algorithms just because
-of an interface difference. When using undirected graphs just mentally
-disregard the directionality in the function names. The example below
-demonstrates using the <TT>out_edges()</TT>, <TT>source()</TT>, and
-<TT>target()</TT> with an undirected graph. The source code for this
-example and the following one can be found in <a
-href="../example/undirected.cpp"><TT>examples/undirected.cpp</TT></a>.
-
-<P>
-<PRE>
- const int V = 2;
- typedef ... UndirectedGraph;
- UndirectedGraph undigraph(V);
-
- std::cout << "the edges incident to v: ";
- boost::graph_traits<UndirectedGraph>::out_edge_iterator e, e_end;
- boost::graph_traits<UndirectedGraph>::vertex_descriptor
- s = vertex(0, undigraph);
- for (tie(e, e_end) = out_edges(s, undigraph); e != e_end; ++e)
- std::cout << "(" << source(*e, undigraph)
- << "," << target(*e, undigraph) << ")"
<< endl;
-</PRE>
-
-<P>
-Even though the interface is the same for undirected graphs, there are
-some behavioral differences because edge equality is defined
-differently. In a directed graph, edge <i>(u,v)</i> is never equal to edge
-<i>(v,u)</i>, but in an undirected graph they may be equal. If the
-undirected graph is a multigraph then <i>(u,v)</i> and <i>(v,u)</i> might
be
-parallel edges. If the graph is not a multigraph then <i>(u,v)</i> and
-<i>(v,u)</i> must be the same edge.
-
-<P>
-In the example below the edge equality test will return <TT>false</TT>
-for the directed graph and <TT>true</TT> for the undirected graph. The
-difference also affects the meaning of <TT>add_edge()</TT>. In the
-example below, if we had also written <TT>add_add(v, u,
-undigraph)</TT>, this would have added a parallel edge between
-<i>u</i> and <i>v</i> (provided the graph type allows parallel
-edges). The difference in edge equality also affects the association
-of edge properties. In the directed graph, the edges <i>(u,v)</i> and
-<i>(v,u)</i> can have distinct weight values, whereas in the
-undirected graph the weight of <i>(u,v)</i> is the same as the weight
-of <i>(v,u)</i> since they are the same edge.
-
-<P>
-<PRE>
- typedef ... DirectedGraph;
- DirectedGraph digraph(V);
- {
- boost::graph_traits<DirectedGraph>::vertex_descriptor u, v;
- u = vertex(0, digraph);
- v = vertex(1, digraph);
- add_edge(digraph, u, v, Weight(1.2));
- add_edge(digraph, v, u, Weight(2.4));
- boost::graph_traits<DirectedGraph>::edge_descriptor e1, e2;
- bool found;
- tie(e1, found) = edge(u, v, digraph);
- tie(e2, found) = edge(v, u, digraph);
- std::cout << "in a directed graph is ";
- std::cout << "(u,v) == (v,u) ? " << (e1 == e2) <<
std::endl;
-
- property_map<DirectedGraph, edge_weight_t>::type
- weight = get(edge_weight, digraph);
- cout << "weight[(u,v)] = " << get(weight, e1) <<
endl;
- cout << "weight[(v,u)] = " << get(weight, e2) <<
endl;
- }
- {
- boost::graph_traits<UndirectedGraph>::vertex_descriptor u, v;
- u = vertex(0, undigraph);
- v = vertex(1, undigraph);
- add_edge(undigraph, u, v, Weight(3.1));
- boost::graph_traits<UndirectedGraph>::edge_descriptor e1, e2;
- bool found;
- tie(e1, found) = edge(u, v, undigraph);
- tie(e2, found) = edge(v, u, undigraph);
- std::cout << "in an undirected graph is ";
- std::cout << "(u,v) == (v,u) ? " << (e1 == e2) <<
std::endl;
-
- property_map<UndirectedGraph, edge_weight_t>::type
- weight = get(edge_weight, undigraph);
- cout << "weight[(u,v)] = " << get(weight, e1) <<
endl;
- cout << "weight[(v,u)] = " << get(weight, e2) <<
endl;
- }
-</PRE>
-The output is:
-<PRE>
-in a directed graph is (u,v) == (v,u) ? 0
-weight[(u,v)] = 1.2
-weight[(v,u)] = 2.4
-in an undirected graph is (u,v) == (v,u) ? 1
-weight[(u,v)] = 3.1
-weight[(v,u)] = 3.1
-</PRE>
+<tr>
+<td colspan="2" align="left">
+<a href="./PropertyGraph.html">PropertyGraph</a> 精化自 Graph</td>
+</tr>
+<tr><td align="left">
+<tt>boost::property_map<G, Property>::type</tt> </td>
+<td align="left" valign="top">用于可变属性映射的类型。</td>
+</tr>
+<tr><td align="left">
+<tt>boost::property_map<G, Property>::const_type</tt> </td>
+<td align="left" valign="top">用于不可变属性映射的类型。</td>
+</tr>
+<tr><td align="left">
+<tt>get(property, g)</tt> </td>
+<td align="left" valign="top">获得一个属性映射的函数。 </td>
+</tr>
+
+<tr><td align="left">
+<tt>get(property, g, x)</tt>
+</td>
+<td align="left" valign="top">获得顶点或边 <tt>x</tt> 的属性值。 </td>
+</tr>
+
+<tr><td align="left">
+<tt>put(property, g, x, v)</tt>
+</td>
+<td align="left" valign="top">设置顶点或边
+<tt>x</tt> 的属性值为 <tt>v</tt>。 </td>
+</tr>
+
+</tbody></table>
+</td></tr></tbody></table>
+</div><h2><a name="sec:undirected-graphs"></a>
+Undirected Graphs 无向图
+</h2>
+
+<p>BGL所提供的用于访问和处理一个无向图的接口与在后续章节中所描述的用于有向
图的接口是一样的，不过在行为和语义方面会有些差异。例如，在一个有
+向图中，我们可以讨论一个顶点的出边和入边。而在一个无向图中，是没
有"入"和"出"的概念的，只有与一个顶点相对应的边。虽然如此，但是在BGL中我们
+还是用
+<tt>out_edges()</tt> 函数(或 <tt>in_edges()</tt>)来访问一个无向图中的边。同
样，无向图的边也没有"源"和"目标"，它仅仅是一个无序的顶点对，不过在BGL中我们
还是用 <tt>source()</tt> 和
+<tt>target()</tt> 来访问边的顶点。BGL没有为无向图提供单独的接口的原因是，有
向图上的许多算法也可以用于无向图，如果仅仅因为接口的不同而不得不对算法进行复
制，是很不方便的。在使用无向图，我们只要忽略函数名中的方向性就可以了。以下的
例子示范了对一个无向图使用 <tt>out_edges()</tt>, <tt>source()</tt>, 和
+<tt>target()</tt> 函数。这个例子和下一个例子的源代码可以 <a
href="../example/undirected.cpp"><tt>examples/undirected.cpp</tt></a> 中找
到。
+
+</p><pre> const int V = 2;<br> typedef ... UndirectedGraph;<br>
UndirectedGraph undigraph(V);<br><br> std::cout << "the edges
incident to v: ";<br>
boost::graph_traits<UndirectedGraph>::out_edge_iterator e,
e_end;<br> boost::graph_traits<UndirectedGraph>::vertex_descriptor
<br> s = vertex(0, undigraph);<br> for (tie(e, e_end) = out_edges(s,
undigraph); e != e_end; ++e)<br> std::cout << "(" <<
source(*e, undigraph) <br> << "," << target(*e,
undigraph) << ")" << endl;<br></pre>
+
+<p>虽然用于无向图的接口是一样的，但是其行为有些不同，因为对于边的相等性的定
义是不同的。在有向图中，边 <i>(u,v)</i> 永远不会等于边
+<i>(v,u)</i>，但是在无向图中它们则是相等的。如果无向图是一个复图，则
<i>(u,v)</i> 和 <i>(v,u)</i> 可能是平行边。如果不是复图，则 <i>(u,v)</i> 和
+<i>(v,u)</i> 必须是同一条边。
+
+</p><p>在下面例子的边等价性测试中，对于有向图会返回 <tt>false</tt>，而对于
无向图则返回 <tt>true</tt>。这种差异也会影响 <tt>add_edge()</tt> 的意义。在
下例中，如果我们再写一个 <tt>add_add(v, u,
+undigraph)</tt>，则会在
+<i>u</i> 和 <i>v</i> 之间加入一条平行边(假设这个图类型允许平行边)。边等价性
的不同还会影响边属性的关联性。在有向图中，边 <i>(u,v)</i> 和
+<i>(v,u)</i> 可以有不同的权重值，而在无向图中 <i>(u,v)</i> 的权重和
<i>(v,u)</i> 的权重是一样的，因为它们是同一条边。
+
+</p><pre> typedef ... DirectedGraph;<br> DirectedGraph digraph(V);<br>
{<br> boost::graph_traits<DirectedGraph>::vertex_descriptor u,
v;<br> u = vertex(0, digraph);<br> v = vertex(1, digraph);<br>
add_edge(digraph, u, v, Weight(1.2));<br> add_edge(digraph, v, u,
Weight(2.4));<br>
boost::graph_traits<DirectedGraph>::edge_descriptor e1, e2;<br>
bool found;<br> tie(e1, found) = edge(u, v, digraph);<br> tie(e2,
found) = edge(v, u, digraph);<br> std::cout << "in a directed
graph is ";<br> std::cout << "(u,v) == (v,u) ? " << (e1 ==
e2) << std::endl;<br><br> property_map<DirectedGraph,
edge_weight_t>::type<br> weight = get(edge_weight, digraph);<br>
cout << "weight[(u,v)] = " << get(weight, e1) <<
endl;<br> cout << "weight[(v,u)] = " << get(weight, e2)
<< endl;<br> }<br> {<br>
boost::graph_traits<UndirectedGraph>::vertex_descriptor u, v;<br>
u = vertex(0, undigraph);<br> v = vertex(1, undigraph);<br>
add_edge(undigraph, u, v, Weight(3.1));<br>
boost::graph_traits<UndirectedGraph>::edge_descriptor e1, e2;<br>
bool found;<br> tie(e1, found) = edge(u, v, undigraph);<br> tie(e2,
found) = edge(v, u, undigraph);<br> std::cout << "in an undirected
graph is ";<br> std::cout << "(u,v) == (v,u) ? " << (e1 ==
e2) << std::endl;<br><br> property_map<UndirectedGraph,
edge_weight_t>::type<br> weight = get(edge_weight,
undigraph);<br> cout << "weight[(u,v)] = " << get(weight,
e1) << endl;<br> cout << "weight[(v,u)] = " <<
get(weight, e2) << endl;<br> }<br></pre>输出如下：
+<pre>in a directed graph is (u,v) == (v,u) ? 0<br>weight[(u,v)] =
1.2<br>weight[(v,u)] = 2.4<br>in an undirected graph is (u,v) == (v,u) ?
1<br>weight[(u,v)] = 3.1<br>weight[(v,u)] = 3.1<br></pre>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/leda_conversion.html
==============================================================================
--- trunk/libs/graph/doc/leda_conversion.html (original)
+++ trunk/libs/graph/doc/leda_conversion.html Wed Jul 8 07:54:49 2009
@@ -1,263 +1,86 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
--
-- Distributed under the Boost Software License, Version 1.0.
-- (See accompanying file LICENSE_1_0.txt or copy at
-- http://www.boost.org/LICENSE_1_0.txt)
-->
-<Head>
-<Title>Boost Graph Library: Converting Existing Graphs to BGL</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:leda-conversion">How to Convert Existing Graphs to
BGL</H1>
-
-<P>
-Though the main goal of BGL is to aid the development of new
-applications and graph algorithms, there are quite a few existing codes
-that could benefit from using BGL algorithms. One way to use the BGL
-algorithms with existing graph data structures is to copy data from
-the older graph format into a BGL graph which could then be used in
-the BGL algorithms. The problem with this approach is that it can be
-expensive to make this copy. Another approach is to wrap the existing
-graph data structure with a BGL interface.
-
-<P>
-The Adaptor pattern [<A
- HREF="bibliography.html#gamma95:_design_patterns">12</A>] typically
requires
-that the adaptee object be contained inside a new class that provides the
-desired interface. This containment is not required when wrapping a
-graph for BGL because the BGL graph interface consists solely of
-free (global) functions. Instead of creating a new graph class, you
-need to overload all the free functions required by the interface. We
-call this free function wrapper approach <I>external adaptation</I>.
-
-<P>
-One of the more commonly used graph classes is the LEDA parameterized
-<a
-href="http://www.mpi-sb.mpg.de/LEDA/MANUAL/bgraph.html";><TT>GRAPH</TT></a>
-class [<A HREF="bibliography.html#mehlhorn99:_leda">22</A>]. In
-this section we will show how to create a BGL interface for this
-class. The first question is which BGL interfaces (or concepts) we
-should implement. The following concepts are straightforward and easy
-to implement on top of LEDA: <a
-href="./VertexListGraph.html">VertexListGraph</a>, <a
-href="./BidirectionalGraph.html">BidirectionalGraph</a>, and <a
-href="./MutableGraph.html">MutableGraph</a>.
-
-<P>
-All types associated with a BGL graph class are accessed though the
-<TT>graph_traits</TT> class. We can partially specialize this traits
-class for the LEDA <TT>GRAPH</TT> class in the following way. The
-<TT>node</TT> and <TT>edge</TT> are the LEDA types for representing
-vertices and edges. The LEDA <TT>GRAPH</TT> is for directed graphs, so
-we choose <TT>directed_tag</TT> for the <TT>directed_category</TT>.
-The LEDA <TT>GRAPH</TT> does not automatically prevent the insertion
-of parallel edges, so we choose <TT>allow_parallel_edge_tag</TT> for
-the <TT>edge_parallel_category</TT>. The return type for the LEDA
-function <TT>number_of_nodes()</TT> and <TT>number_of_edges()</TT> is
-<TT>int</TT>, so we choose that type for the
-<TT>vertices_size_type</TT> and <tt>edges_size_type</tt> of the
-graph. The iterator types will be more complicated, so we leave that
-for later.
-
-<P>
-<PRE>
-namespace boost {
- template <class vtype, class etype>
- struct graph_traits< GRAPH<vtype,etype> > {
- typedef node vertex_descriptor;
- typedef edge edge_descriptor;
-
- // iterator typedefs...
-
- typedef directed_tag directed_category;
- typedef allow_parallel_edge_tag edge_parallel_category;
- typedef int vertices_size_type;
- typedef int edges_size_type;
- };
-} // namespace boost
-</PRE>
-
-<P>
-First we will write the <TT>source()</TT> and <TT>target()</TT>
-functions of the <a href="./IncidenceGraph.html">IncidenceGraph</a>
-concept, which is part of the <a
-href="./VertexListGraph.html">VertexListGraph</a> concept. We use the
-LEDA <TT>GRAPH</TT> type for the graph parameter, and use
-<TT>graph_traits</TT> to specify the edge parameter and the vertex
-return type. We could also just use the LEDA types <TT>node</TT> and
-<TT>edge</TT> here, but it is better practice to always use
-<TT>graph_traits</TT>. If there is a need to change the associated
-vertex or edge type, you will only need to do it in one place, inside
-the specialization of <TT>graph_traits</TT> instead of throughout your
-code. LEDA provides <TT>source()</TT> and <TT>target()</TT> functions,
-so we merely call them.
-
-<P>
-<PRE>
-namespace boost {
- template <class vtype, class etype>
- typename graph_traits< GRAPH<vtype,etype>
>::vertex_descriptor
- source(
- typename graph_traits< GRAPH<vtype,etype>
>::edge_descriptor e,
- const GRAPH<vtype,etype>& g)
- {
- return source(e);
- }
-
- template <class vtype, class etype>
- typename graph_traits< GRAPH<vtype,etype>
>::vertex_descriptor
- target(
- typename graph_traits< GRAPH<vtype,etype>
>::edge_descriptor e,
- const GRAPH<vtype,etype>& g)
- {
- return target(e);
- }
-} // namespace boost
-</PRE>
-
-<P>
-The next function from <a
-href="./IncidenceGraph.html">IncidenceGraph</a> that we need to
-implement is <TT>out_edges()</TT>. This function returns a pair of
-out-edge iterators. Since LEDA does not use STL-style iterators we
-need to implement some. There is a very handy boost utility for
-implementing iterators, called <TT>iterator_adaptor</TT>. Writing a
-standard conforming iterator classes is actually quite difficult,
-harder than you may think. With the <TT>iterator_adaptor</TT> class,
-you just implement a policy class and the rest is taken care of. The
-following code is the policy class for our out-edge iterator. In LEDA,
-the edge object itself is used like an iterator. It has functions
-<TT>Succ_Adj_Edge()</TT> and <TT>Pred_Adj_Edge()</TT> to move to the
-next and previous (successor and predecessor) edge. One gotcha in
-using the LEDA <TT>edge</TT> as an iterator comes up in the
-<TT>dereference()</TT> function, which merely returns the edge
-object. The dereference operator for standard compliant iterators must
-be a const member function, which is why the edge argument is
-const. However, the return type should not be const, hence the need
-for <TT>const_cast</TT>.
-
-<P>
-<PRE>
-namespace boost {
- struct out_edge_iterator_policies
- {
- static void increment(edge& e)
- { e = Succ_Adj_Edge(e,0); }
-
- static void decrement(edge& e)
- { e = Pred_Adj_Edge(e,0); }
-
- template <class Reference>
- static Reference dereference(type<Reference>, const edge& e)
- { return const_cast<Reference>(e); }
-
- static bool equal(const edge& x, const edge& y)
- { return x == y; }
- };
-} // namespace boost
-</PRE>
-
-<P>
-Now we go back to the <TT>graph_traits</TT> class, and use
-<TT>iterator_adaptor</TT> to fill in the
-<TT>out_edge_iterator</TT>. We use the <TT>iterator</TT> type
-to specify the associated types of the iterator, including iterator
-category and value type.
-
-<P>
-<PRE>
- namespace boost {
- template <class vtype, class etype>
- struct graph_traits< GRAPH<vtype,etype> > {
- // ...
- typedef iterator_adaptor<edge,
- out_edge_iterator_policies,
- iterator<std::bidirectional_iterator_tag,edge>
- > out_edge_iterator;
- // ...
- };
- } // namespace boost
-</PRE>
-
-<P>
-With the <TT>out_edge_iterator</TT> defined in <TT>graph_traits</TT> we
-are ready to define the <TT>out_edges()</TT> function. The following
-definition looks complicated at first glance, but it is really quite
-simple. The return type should be a pair of out-edge iterators, so we
-use <TT>std::pair</TT> and then <TT>graph_traits</TT> to access the
-out-edge iterator types. In the body of the function we construct the
-out-edge iterators by passing in the first adjacenct edge for the
-begin iterator, and 0 for the end iterator (which is used in LEDA as
-the end sentinel). The 0 argument to <TT>First_Adj_Edge</TT> tells
-LEDA we want out-edges (and not in-edges).
-
-<P>
-<PRE>
-namespace boost {
- template <class vtype, class etype>
- inline std::pair<
- typename graph_traits< GRAPH<vtype,etype>
>::out_edge_iterator,
- typename graph_traits< GRAPH<vtype,etype>
>::out_edge_iterator >
- out_edges(
- typename graph_traits< GRAPH<vtype,etype>
>::vertex_descriptor u,
- const GRAPH<vtype,etype>& g)
- {
- typedef typename graph_traits< GRAPH<vtype,etype> >
- ::out_edge_iterator Iter;
- return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
- }
-} // namespace boost
-</PRE>
-
-<P>
-The rest of the iterator types and interface functions are constructed
-using the same techniques as above. The complete code for the LEDA
-wrapper interface is in <a
-href="../../../boost/graph/leda_graph.hpp"><TT>boost/graph/leda_graph.hpp</TT></a>.
In
-the following code we use the BGL concept checks to make sure that we
-correctly implemented the BGL interface. These checks do not test the
-run-time behaviour of the implementation; that is tested in <a
-href="../test/graph.cpp"><TT>test/graph.cpp</TT></a>.
-
-<P>
-<PRE>
- #include <boost/graph/graph_concepts.hpp>
- #include <boost/graph/leda_graph.hpp>
-
- int
- main(int,char*[])
- {
- typedef GRAPH<int,int> Graph;
- function_requires< VertexListGraphConcept<Graph> >();
- function_requires< BidirectionalGraphConcept<Graph> >();
- function_requires< MutableGraphConcept<Graph> >();
- return 0;
- }
-</PRE>
+<title>Boost Graph Library: Converting Existing Graphs to
BGL</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:leda-conversion">How to Convert Existing Graphs to BGL 如
果把已有图转换至BGL</a></h1>
+
+<p>
+<a name="sec:leda-conversion">虽然BGL的主要目标是帮助开发新的应用和图算
法，但是还有不少的已有代码可以受益于
+BGL算法。将BGL算法用于已有的图数据结构的一种方法是，从旧的图格式中将数据复
制至一个可以在BGL算法中使用的BGL图中。这种方法的问题是，进
+行复制的代价可能是昂贵的。另一种方法就是，在已有的图数据结构外面包一层BGL接
口。
+</a></p><p>
+<a name="sec:leda-conversion">适配器模式[</a><a
href="bibliography.html#gamma95:_design_patterns">12</a>]通常要求将适配对象
包含在一个新类中，以提供所需的接口。在将一个图针对BGL进行包装时，并没有这种
限制，因为BGL图接口纯粹是自由(全局)函数。你不用创建一个新的图类，而是重载接
口所需要的所有自由函数。我们称这种自由函数的包装方法为<i>外部适配</i>。
+
+</p><p>一种最常见的图类是 LEDA 参数化的
+<a
href="http://www.mpi-sb.mpg.de/LEDA/MANUAL/bgraph.html";><tt>GRAPH</tt></a>
+类[<a href="bibliography.html#mehlhorn99:_leda">22</a>]。在本节中，我们将示
范如何为这个类创建一个BGL接口。第一个问题是，我们应实现哪些BGL接口(或概念)。
以下概念非常简单，可以很容易地在LEDA之上实现：<a
href="./VertexListGraph.html">VertexListGraph</a>, <a
href="./BidirectionalGraph.html">BidirectionalGraph</a>, 和 <a
href="./MutableGraph.html">MutableGraph</a>。
+
+</p><p>与一个BGL图类相关的所有类型都是通过
+<tt>graph_traits</tt> 类来访问的。我们可以用以下方式为 LEDA GRAPH 类偏特化
这个 traits
+类。<tt>node</tt> 和 <tt>edge</tt> 是表示顶点和边的 LEDA 类型。LEDA
<tt>GRAPH</tt> 是用于有向图的，所以我们选择 <tt>directed_tag</tt> 作为
<tt>directed_category</tt>。LEDA <tt>GRAPH</tt> 不能自动阻止平行边的插入，所
以我们选择 <tt>allow_parallel_edge_tag</tt> 作为
<tt>edge_parallel_category</tt>。LEDA 函数 <tt>number_of_nodes()</tt> 和
<tt>number_of_edges()</tt> 的返回类型为
+<tt>int</tt>，所以我们选择该类型作为图的
+<tt>vertices_size_type</tt> 和 <tt>edges_size_type</tt>。迭代器类型比较复
杂，所以我们晚一些再处理。
+
+</p><pre>namespace boost {<br> template <class vtype, class
etype><br> struct graph_traits< GRAPH<vtype,etype> >
{<br> typedef node vertex_descriptor;<br> typedef edge
edge_descriptor;<br><br> // 迭代器的 typedefs...<br><br> typedef
directed_tag directed_category;<br> typedef allow_parallel_edge_tag
edge_parallel_category;<br> typedef int vertices_size_type;<br>
typedef int edges_size_type;<br> };<br>} // namespace boost<br></pre>
+
+<p>首先，我们要编写 <a href="IncidenceGraph.html">IncidenceGraph</a> 概念
的 <tt>source()</tt> 和 <tt>target()</tt>
+函数，<a href="./IncidenceGraph.html"></a>该概念是 <a
href="./VertexListGraph.html">VertexListGraph</a> 概念的一部分。我们用
+LEDA <tt>GRAPH</tt> 类型作为 graph 参数，并使用
+<tt>graph_traits</tt> 来指定 edge 参数和 vertex
+返回类型。在这里，我们也可以直接使用 LEDA 类型 <tt>node</tt> 和
+<tt>edge</tt>，不过始终使用
+<tt>graph_traits</tt> 是更好的做法。如果需要修改相关的
+vertex 或 edge 类型，你只需要在一个地方作出修改，即特化
<tt>graph_traits</tt> 的内部，而不是在你代码的多处地方。LEDA 提供了
<tt>source()</tt> 和 <tt>target()</tt> 函数，所以我们只要调用它们就行了。
+
+</p><pre>namespace boost {<br> template <class vtype, class
etype><br> typename graph_traits< GRAPH<vtype,etype>
>::vertex_descriptor<br> source(<br> typename graph_traits<
GRAPH<vtype,etype> >::edge_descriptor e,<br> const
GRAPH<vtype,etype>& g)<br> {<br> return source(e);<br>
}<br><br> template <class vtype, class etype><br> typename
graph_traits< GRAPH<vtype,etype> >::vertex_descriptor<br>
target(<br> typename graph_traits< GRAPH<vtype,etype>
>::edge_descriptor e,<br> const GRAPH<vtype,etype>& g)<br>
{<br> return target(e);<br> }<br>} // namespace boost<br></pre>
+
+<p>我们需要实现的下一个 <a href="./IncidenceGraph.html">IncidenceGraph</a>
的函数是 <tt>out_edges()</tt>。该函数一对出边迭代器。因为 LEDA 没有使用STL风
格的迭代器，所以我们要来实现一个。实现迭代器有一个非常有用的boost工具，名为
<tt>iterator_adaptor</tt>。编写一个符合标准的迭代器类实际上相当困难，难度要
比你想象的高。而有了 <tt>iterator_adaptor</tt> 类，你只需要实现一个策略
类，剩下的就不用管了。以下代码是我们的出边迭代器的策略类。在 LEDA 中，边对象
本身是被当作迭代器来使用的。它有两个函数
+<tt>Succ_Adj_Edge()</tt> 和 <tt>Pred_Adj_Edge()</tt>，分别移至下一条边和前
一条边(后继与前导)。把 LEDA <tt>edge</tt> 用作迭代器的一个例子出现在
+<tt>dereference()</tt> 函数中，它仅仅是返回这个 edge
+对象。符合标准的迭代器的解引用操作符必须是一个 const 成员函数，这就是为什
么 edge 参数为
+const 的原因。不过，返回类型不应为 const, 因此需要用到
<tt>const_cast</tt>。
+
+</p><pre>namespace boost {<br> struct out_edge_iterator_policies<br>
{<br> static void increment(edge& e)<br> { e =
Succ_Adj_Edge(e,0); }<br><br> static void decrement(edge& e)<br>
{ e = Pred_Adj_Edge(e,0); }<br><br> template <class
Reference><br> static Reference dereference(type<Reference>,
const edge& e)<br> { return const_cast<Reference>(e);
}<br><br> static bool equal(const edge& x, const edge& y)<br>
{ return x == y; }<br> };<br>} // namespace boost<br></pre>
+
+<p>现在我们回到 <tt>graph_traits</tt> 类，用
+<tt>iterator_adaptor</tt> 来完成
+<tt>out_edge_iterator</tt>。我们用这个迭代器类型来指定与该迭代器相关的类
型，包括迭代器种类和值类型。
+
+</p><pre> namespace boost {<br> template <class vtype, class
etype><br> struct graph_traits< GRAPH<vtype,etype> >
{<br> // ...<br> typedef iterator_adaptor<edge,<br>
out_edge_iterator_policies, <br>
iterator<std::bidirectional_iterator_tag,edge><br> >
out_edge_iterator;<br> // ...<br> };<br> } // namespace
boost<br></pre>
+
+<p>有了在 <tt>graph_traits</tt> 中定义的 <tt>out_edge_iterator</tt>，我们就
可以定义 <tt>out_edges()</tt> 函数了。以下定义乍一看有点复杂，但其实相当简
单。返回类型应为一对出边迭代器，所以我们用了 <tt>std::pair</tt> 和
<tt>graph_traits</tt> 来获得出边迭代器类型。在函数体中，我们这样来构造两个出
边迭代器，通过传入第一条相邻边来构造始端迭代器，传入0来构造末端迭代器(在
LEDA 中作为结束哨兵使用)。传给 <tt>First_Adj_Edge</tt> 的参数0告诉
+LEDA 我们要的是出边(而非入边)。
+
+</p><pre>namespace boost {<br> template <class vtype, class
etype><br> inline std::pair<<br> typename graph_traits<
GRAPH<vtype,etype> >::out_edge_iterator,<br> typename
graph_traits< GRAPH<vtype,etype> >::out_edge_iterator >
<br> out_edges(<br> typename graph_traits< GRAPH<vtype,etype>
>::vertex_descriptor u, <br> const GRAPH<vtype,etype>&
g)<br> {<br> typedef typename graph_traits< GRAPH<vtype,etype>
><br> ::out_edge_iterator Iter;<br> return std::make_pair(
Iter(First_Adj_Edge(u,0)), Iter(0) );<br> }<br>} // namespace
boost<br></pre>
+
+<p>其余的迭代器类型和接口函数都可以用同样的技术来构造。LEDA
+包装器接口的完整代码在 <a
href="../../../boost/graph/leda_graph.hpp"><tt>boost/graph/leda_graph.hpp</tt></a>。
以下代码中，我们用BGL概念检查来确认是否正确地实现了BGL接口。这些检查并不是测
试该实现的运行期行为；运行期行为在 <a
href="../test/graph.cpp"><tt>test/graph.cpp</tt></a> 中测试。
+
+</p><pre> #include <boost/graph/graph_concepts.hpp><br> #include
<boost/graph/leda_graph.hpp><br><br> int<br> main(int,char*[])<br>
{<br> typedef GRAPH<int,int> Graph;<br> function_requires<
VertexListGraphConcept<Graph> >();<br> function_requires<
BidirectionalGraphConcept<Graph> >();<br> function_requires<
MutableGraphConcept<Graph> >();<br> return 0;<br> }<br></pre>
<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright © 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
-Indiana University (<A
-HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
-<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>,
Indiana University (<A
HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
-Indiana University (<A
-HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<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>)<br>
+<a href="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</a>,
Indiana University (<a
href="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</a>)<br>
+<a href="http://www.osl.iu.edu/%7Elums";>Andrew Lumsdaine</a>,
+Indiana University (<a href="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
-</BODY>
-</HTML>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/python.html
==============================================================================
--- trunk/libs/graph/doc/python.html (original)
+++ trunk/libs/graph/doc/python.html Wed Jul 8 07:54:49 2009
@@ -1,14 +1,13 @@
-<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) 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: Python Bindings (Experimental)</title>
- <script language="JavaScript" type="text/JavaScript">
+
+ <title>Boost Graph Library: Python Bindings
(Experimental)</title><script language="JavaScript" type="text/JavaScript">
<!--
function address(host, user) {
var atchar = '@';
@@ -17,35 +16,22 @@
document.write(thingy);
}
//-->
- </script>
- </head>
- <body BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <img SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <h1><img src="figs/python.gif" alt="(Python)"/>Boost Graph Library:
Python Bindings (<b>Experimental</b>)</h1>
- <p>The Boost Graph Library offers a wealth of graph algorithms and
- data types for C++. These algorithms are flexible and efficient,
- but the mechanisms employed to achieve this goal can result in
- long compile times that slow the development cycle.</p>
+ </script></head>
- <p>The Python bindings are build using the <a
- href="../../python/doc/index.html">Boost.Python</a> library. The
bindings are
- meant to strike a balance of usability, flexibility, and
- efficiency, making it possible to rapidly develop useful systems
- using the BGL in Python.</p>
+ <body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+ <img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
+ <h1><img src="figs/python.gif" alt="(Python)">Boost Graph Library:
Python 绑定 (实验中)</h1>
+ <p>BGL提供了用于C++的大量图算法和数据类型。这些算法非常灵活也很高效，但
是达到这一目标所采用的机制可能会导致较长的编译时间，从而令开发周期过慢。</p>
- <p>The Python bindings for the BGL are now part of a <a
- href="http://www.osl.iu.edu/~dgregor/bgl-python/";>separate
- project</a>. They are no longer available within the Boost
- tree.</p>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2005</TD><TD>
- <A HREF="http://www.boost.org/people/doug_gregor.html";>Doug
Gregor</A>, Indiana University (<script
language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
- <A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
+ <p>Python绑定是用 <a
href="../../python/doc/index.html">Boost.Python</a> 库构建的。该绑定的目的是
在可用性、灵活性和效率间取得平衡，使我们能够在Python里用BGL快速开发有用的系
统。</p>
+
+ <p>BGL的Python绑定目前是一个<a
href="http://www.osl.iu.edu/%7Edgregor/bgl-python/";>独立项目</a>的组成部分。
它们不再出现在Boost开发树中。</p>
+ <hr>
+ <table>
+ <tbody><tr valign="top">
+ <td nowrap="nowrap">Copyright (c) 2005</td><td>
+ <a href="http://www.boost.org/people/doug_gregor.html";>Doug
Gregor</a>, Indiana University (<script
language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
+ <a href="http://www.osl.iu.edu/%7Elums";>Andrew Lumsdaine</a>,
Indiana University (<script
language="Javascript">address("osl.iu.edu", "lums")</script>)
- </TD></TR></TABLE>
- </body>
-</html>
+ </td></tr></tbody></table>
+ </body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html (original)
+++ trunk/libs/graph/doc/table_of_contents.html Wed Jul 8 07:54:49 2009
@@ -59,9 +59,9 @@
<li><a href="./AdjacencyGraph.html">Adjacency
Graph 邻接图</a> </li>
<li><a href="./VertexListGraph.html">Vertex
-List Graph 点表图</a> </li>
+List Graph 点列表图</a> </li>
<li><a href="./EdgeListGraph.html">Edge List
-Graph 边表图</a> </li>
+Graph 边列表图</a> </li>
<li><a href="./VertexAndEdgeListGraph.html">Vertex
and Edge List Graph 点边列表图</a> </li>
<li><a href="./MutableGraph.html">Mutable
@@ -69,12 +69,11 @@
<li><a href="./PropertyGraph.html">Property
Graph 属性图</a> </li>
<li><a href="./MutablePropertyGraph.html">Mutable
-Property Graph 可变特性图</a> </li>
+Property Graph 可变属性性图</a> </li>
</ol>
</li>
<li><a href="../../property_map/property_map.html">The
-Property Map Library 特性映射库</a> (technically not part of the graph
-library, but used a lot here) </li>
+Property Map Library 特性映射库</a> (技术上这不是本库的一部分，但在本库中大
量使用) </li>
<li><img src="figs/python_ico.gif" alt="(Python)"><a
href="python.html">Python bindings</a></li>
<li><a href="./visitor_concepts.html">Visitor
Concepts 遍历器概念</a>
Modified: trunk/libs/libraries.htm
==============================================================================
--- trunk/libs/libraries.htm (original)
+++ trunk/libs/libraries.htm Wed Jul 8 07:54:49 2009
@@ -631,7 +631,7 @@
<p>Distributed under the Boost Software License, Version 1.0.
(See file <a href="../LICENSE_1_0.txt">LICENSE_1_0.txt</a>
or <a
href="http://www.boost.org/LICENSE_1_0.txt";>www.boost.org/LICENSE_1_0.txt</a>)</p>
-<p>本译文更新于 2009年6月24日，由 alai04, fatalerror99, felurkinda,
farproc,
+<p>本译文更新于 2009年7月8日，由 alai04, fatalerror99, felurkinda, farproc,
hzjboost, blackjazz07, xuwaters, jinq0123,
totti, jANA_cOVA, pterosaur, xiaq, zhaohongchao, leo, sidle,
luckycat06, lixin, evy.wang, 元维，水的影子 等人翻译，各人贡献了以下译
文：</p>
<p>alai04：<a href="accumulators/index.html">accumulators</a>, <a
href="any/index.html">any</a>, <a href="assign/index.html">assign</a>, <a
href="bimap/index.html">bimap</a>, <a
href="utility/call_traits.htm">call_traits</a>, <a
href="circular_buffer/index.html">circular_buffer</a>,
@@ -654,7 +654,7 @@
<p>hzjboost：<a href="tuple/doc/tuple_users_guide.html">tuple</a> </p>
<p>xuwaters：<span class="library"><a
href="parameter/doc/html/index.html">parameter</a></span>,
<a href="timer/index.html">timer</a> </p>
-<p>jinq0123：<a href="python/doc/index.html">python</a>, <a
href="signals/index.html">signals</a> </p>
+<p>jinq0123：<a href="python/doc/index.html">python</a>, <a
href="signals/index.html">signals</a>, <a
href="signals2/index.html">signals2</a> </p>
<p>xiaq：<a href="random/index.html">random</a> </p><p>zhaohongchao:
<a href="exception/doc/boost-exception.html">exception</a>, <a
href="gil/doc/index.html">gil</a> </p><p> luckycat06：<a
href="numeric/interval/doc/interval.htm">interval</a>, <a
href="math/doc/index.html">math</a>, <a
href="math/doc/complex/html/index.html">math/complex
number algorithms</a>, <a
href="math/doc/common_factor.html">math/common_factor</a>, <a
href="math/doc/octonion/html/index.html">math/octonion</a>, <a
href="math/doc/quaternion/html/index.html">math/quaternion</a>, <a
href="math/doc/sf_and_dist/html/index.html">math/special_functions</a>, <a
href="math/doc/sf_and_dist/html/index.html">math/statistical
distributions</a>, <a
href="numeric/ublas/doc/index.htm">uBLAS</a> </p><p>lixin: <a
href="regex/index.html">regex</a>, <a
href="test/doc/html/index.html">test</a>, <a
href="units/index.html">units</a> </p><p>felurkinda: <a
href="graph/doc/table_of_contents.html">graph</a>(部分
)</p><p>hzjboost: <a href="spirit/index.html">spirit</a>(部分
)</p><p>evy.wang：<a href="thread/doc/index.html">thread</a></p><p>水的影
子：<a href="flyweight/doc/index.html">flyweight</a> <a
href="thread/doc/index.html"></a> </p>
Other related posts:
- » [boost-doc-zh commit] r280 - graph 库文档第10-13章 - codesite-noreply
