[boost-doc-zh commit] r277 - graph 库文档第8-9章
- From: codesite-noreply@xxxxxxxxxx
- To: boost-doc-zh-notify@xxxxxxxxxxxxx
- Date: Fri, 03 Jul 2009 03:37:39 +0000
Author: alai04
Date: Thu Jul 2 20:26:08 2009
New Revision: 277
Modified:
trunk/libs/graph/doc/file_dependency_example.html
trunk/libs/graph/doc/graph_coloring.html
trunk/libs/graph/doc/graph_theory_review.html
trunk/libs/graph/doc/kevin_bacon.html
trunk/libs/graph/doc/sparse_matrix_ordering.html
trunk/libs/graph/doc/using_adjacency_list.html
trunk/libs/graph/doc/using_property_maps.html
Log:
graph 库文档第8-9章
Modified: trunk/libs/graph/doc/file_dependency_example.html
==============================================================================
--- trunk/libs/graph/doc/file_dependency_example.html (original)
+++ trunk/libs/graph/doc/file_dependency_example.html Thu Jul 2 20:26:08
2009
@@ -1,363 +1,109 @@
-<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>File Dependency Example</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:file-depend-eg"></A>
-File Dependency Example
-</H1>
-
-<P>
-One of the most common uses of the graph abstraction in computer
-science is to track dependencies. An example of dependency tracking
-that we deal with on a day to day basis is the compilation
-dependencies for files in programs that we write. These dependencies
-are used inside programs such as <TT>make</TT> or in an IDE such as
-Visual C++ to minimize the number of files that must be recompiled
-after some changes have been made.
-
-<P>
-<A HREF="#fig:file-dep">Figure 1</A> shows a graph that has a vertex
-for each source file, object file, and library that is used in the
-<TT>killerapp</TT> program. The edges in the graph show which files
-are used in creating other files. The choice of which direction to
-point the arrows is somewhat arbitrary. As long as we are consistent
-in remembering that the arrows mean ``used by'' then things will work
-out. The opposite direction would mean ``depends on''.
-
-<P>
-
-<P></P>
-<DIV ALIGN="CENTER"><A NAME="fig:file-dep"></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG>
-A graph representing file dependencies.</CAPTION>
-<TR><TD><IMG SRC="./figs/file_dep.gif" width="331" height="351"></TD></TR>
-</TABLE>
-</DIV><P></P>
-
-<P>
-A compilation system such as <TT>make</TT> has to be able to answer a
-number of questions:
-
-<P>
-
-<OL>
-<LI>If we need to compile (or recompile) all of the files, what order
- should that be done it?
-</LI>
-<LI>What files can be compiled in parallel?
-</LI>
-<LI>If a file is changed, which files must be recompiled?
-</LI>
-<LI>Are there any cycles in the dependencies? (which means the user
- has made a mistake and an error should be emitted)
-</LI>
-</OL>
-
-<P>
-In the following examples we will formulate each of these questions in
-terms of the dependency graph, and then find a graph algorithm to
-provide the solution. The graph in <A HREF="#fig:file-dep">Figure
-1</A> will be used in all of the following examples. The source code
-for this example can be found in the file <a
-href="../example/file_dependencies.cpp"><TT>examples/file_dependencies.cpp</TT></a>.
-
-<P>
-
-<H2>Graph Setup</H2>
-
-<P>
-Here we show the construction of the graph. First, these are the required
-header files:
-
-<P>
-<PRE>
-#include <iostream> // std::cout
-#include <utility> // std::pair
-#include <boost/graph/graph_traits.hpp>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/topological_sort.hpp>
-</PRE>
-
-<P>
-For simplicity we have
-constructed the graph "by-hand". A compilation system such
-as <TT>make</TT> would instead parse a <TT>Makefile</TT> to get the
-list of files and to set-up the dependencies. We use the
-<TT>adjacency_list</TT> class to represent the graph. The
-<TT>vecS</TT> selector means that a <TT>std::vector</TT> will be used
-to represent each edge-list, which provides efficient traversal. The
-<TT>bidirectionalS</TT> selector means we want a directed graph with
access to both the edges outgoing from each vertex and the edges incoming
to each vertex, and the
-<TT>color_property</TT> attaches a color property to each vertex of the
-graph. The color property will be used in several of the algorithms in
-the following sections.
-
-<P>
-<PRE>
- enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp,
- foo_o, bar_cpp, bar_o, libfoobar_a,
- zig_cpp, zig_o, zag_cpp, zag_o,
- libzigzag_a, killerapp, N };
- const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp",
- "foo.o", "bar.cpp", "bar.o", "libfoobar.a",
- "zig.cpp", "zig.o", "zag.cpp", "zag.o",
- "libzigzag.a", "killerapp" };
-
- typedef std::pair<int, int> Edge;
- Edge used_by[] = {
- Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h, yow_h),
- Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),
- Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),
- Edge(zow_h, foo_cpp),
- Edge(foo_cpp, foo_o),
- Edge(foo_o, libfoobar_a),
- Edge(bar_cpp, bar_o),
- Edge(bar_o, libfoobar_a),
- Edge(libfoobar_a, libzigzag_a),
- Edge(zig_cpp, zig_o),
- Edge(zig_o, libzigzag_a),
- Edge(zag_cpp, zag_o),
- Edge(zag_o, libzigzag_a),
- Edge(libzigzag_a, killerapp)
- };
-
- using namespace boost;
- typedef adjacency_list<vecS, vecS, bidirectionalS,
- property<vertex_color_t, default_color_type>
- > Graph;
- Graph g(used_by, used_by + sizeof(used_by) / sizeof(Edge), N);
- typedef graph_traits<Graph>::vertex_descriptor Vertex;
-</PRE>
-
-<P>
-
-<H2>Compilation Order (All Files)</H2>
-
-<P>
-On the first invocation of <TT>make</TT> for a particular project, all
-of the files must be compiled. Given the dependencies between the
-various files, what is the correct order in which to compile and link
-them? First we need to formulate this in terms of a graph. Finding a
-compilation order is the same as ordering the vertices in the graph.
-The constraint on the ordering is the file dependencies which we have
-represented as edges. So if there is an edge <i>(u,v)</i> in the graph
-then <i>v</i> better not come before <i>u</i> in the ordering. It
-turns out that this kind of constrained ordering is called a
-<I>topological sort</I>. Therefore, answering the question of
-compilation order is as easy as calling the BGL algorithm <a
-href="./topological_sort.html"><TT>topological_sort()</TT></a>. The
-traditional form of the output for topological sort is a linked-list
-of the sorted vertices. The BGL algorithm instead puts the sorted
-vertices into any <a
-href="http://www.sgi.com/tech/stl/OutputIterator.html";>OutputIterator</a>,
-which allows for much more flexibility. Here we use the
-<TT>std::front_insert_iterator</TT> to create an output iterator that
-inserts the vertices on the front of a linked list. Other possible
-options are writing the output to a file or inserting into a different
-STL or custom-made container.
-
-<P>
-<PRE>
- typedef std::list<Vertex> MakeOrder;
- MakeOrder make_order;
- boost::topological_sort(g, std::front_inserter(make_order));
-
- std::cout << "make ordering: ";
- for (MakeOrder::iterator i = make_order.begin();
- i != make_order.end(); ++i)
- std::cout << name[*i] << " ";
- std::cout << std::endl;
-</PRE>
-The output of this is:
-<PRE>
- make ordering: zow.h boz.h zig.cpp zig.o dax.h yow.h zag.cpp \
- zag.o bar.cpp bar.o foo.cpp foo.o libfoobar.a libzigzag.a killerapp
-</PRE>
-
-<P>
-
-<H2><A NAME="sec:parallel-compilation"></A>
-Parallel Compilation
-</H2>
-
-<P>
-Another question the compilation system might need to answer is: what
-files can be compiled simultaneously? This would allow the system to
-spawn threads and utilize multiple processors to speed up the build.
-This question can also be put in a slightly different way: what is the
-earliest time that a file can be built assuming that an unlimited
-number of files can be built at the same time? The main criteria for
-when a file can be built is that all of the files it depends on must
-already be built. To simplify things for this example, we'll assume
-that each file takes 1 time unit to build (even header files). For
-parallel compilation, we can build all of the files corresponding to
-vertices with no dependencies, e.g., those that have
-an <i>in-degree</i> of 0, in the first step. For all other files, the
-main observation for determining the ``time slot'' for a file is that
-the time slot must be one more than the maximum time-slot of the files
-it depends on.
-
-<P>We start be creating a vector <code>time</code> that will store the
- time step at which each file can be built. We initialize every value
- with time step zero.</p>
-
-<P>
-<PRE>
- std::vector<int> time(N, 0);
-</PRE>
-
-<p>Now, we want to visit the vertices against in topological order,
- from those files that need to be built first until those that need
- to be built last. However, instead of printing out the order
- immediately, we will compute the time step in which each file should
- be built based on the time steps of the files it depends on. We
- only need to consider those files whose in-degree is greater than
- zero.</p>
-
-<pre>
- for (i = make_order.begin(); i != make_order.end(); ++i) {
- if (in_degree (*i, g) > 0) {
- Graph::in_edge_iterator j, j_end;
- int maxdist = 0;
- for (tie(j, j_end) = in_edges(*i, g); j != j_end; ++j)
- maxdist = std::max(time[source(*j, g)], maxdist);
- time[*i]=maxdist+1;
- }
- }
-</pre>
-
-<P>
-Last, we output the time-slot that we've calculated for each vertex.
-
-<P>
-<PRE>
- std::cout << "parallel make ordering, " << std::endl
- << " vertices with same group number" << std::endl
- << " can be made in parallel" << std::endl <<
std::endl;
- for (boost::tie(i, iend) = vertices(g); i != iend; ++i)
- std::cout << "time_slot[" << name[*i] << "] = "
<< time[*i] << std::endl;
-</PRE>
-The output is:
-<PRE>
- parallel make ordering,
- vertices with same group number
- can be made in parallel
- time_slot[dax.h] = 0
- time_slot[yow.h] = 1
- time_slot[boz.h] = 0
- time_slot[zow.h] = 0
- time_slot[foo.cpp] = 1
- time_slot[foo.o] = 2
- time_slot[bar.cpp] = 2
- time_slot[bar.o] = 3
- time_slot[libfoobar.a] = 4
- time_slot[zig.cpp] = 1
- time_slot[zig.o] = 2
- time_slot[zag.cpp] = 2
- time_slot[zag.o] = 3
- time_slot[libzigzag.a] = 5
- time_slot[killerapp] = 6
-</PRE>
-
-<P>
-
-<H2><A NAME="SECTION001014000000000000000"></A>
-<A NAME="sec:cycles"></A>
-<BR>
-Cyclic Dependencies
-</H2>
-
-<P>
-Another question the compilation system needs to be able to answer is
-whether there are any cycles in the dependencies. If there are cycles,
-the system will need to report an error to the user so that the cycles
-can be removed. One easy way to detect a cycle is to run a <a
-href="./depth_first_search.html">depth-first search</a>, and if the
-search runs into an already discovered vertex (of the current search
-tree), then there is a cycle. The BGL graph search algorithms (which
-includes
-<TT>depth_first_search()</TT>) are all extensible via the
-<I>visitor</I> mechanism. A visitor is similar to a function object,
-but it has several methods instead of just the one
-<TT>operator()</TT>. The visitor's methods are called at certain
-points within the algorithm, thereby giving the user a way to extend
-the functionality of the graph search algorithms. See Section <A
-HREF="visitor_concepts.html">Visitor Concepts</A>
-for a detailed description of visitors.
-
-<P>
-We will create a visitor class and fill in the <TT>back_edge()</TT>
-method, which is the <a href="./DFSVisitor.html">DFSVisitor</a> method
-that is called when DFS explores an edge to an already discovered
-vertex. A call to this method indicates the existence of a
-cycle. Inheriting from <TT>dfs_visitor<></TT>
-provides the visitor with empty versions of the other visitor methods.
-Once our visitor is created, we can construct and object and pass it
-to the BGL algorithm. Visitor objects are passed by value inside of
-the BGL algorithms, so the <TT>has_cycle</TT> flag is stored by
-reference in this visitor.
-
-<P>
-<PRE>
- struct cycle_detector : public dfs_visitor<>
- {
- cycle_detector( bool& has_cycle)
- : _has_cycle(has_cycle) { }
-
- template <class Edge, class Graph>
- void back_edge(Edge, Graph&) {
- _has_cycle = true;
- }
- protected:
- bool& _has_cycle;
- };
-</PRE>
-
-<P>
-We can now invoke the BGL <TT>depth_first_search()</TT>
-algorithm and pass in the cycle detector visitor.
-
-<P>
-<PRE>
- bool has_cycle = false;
- cycle_detector vis(has_cycle);
- boost::depth_first_search(g, visitor(vis));
- std::cout << "The graph has a cycle? " << has_cycle <<
std::endl;
-</PRE>
-
-<P>
-The graph in <A HREF="#fig:file-dep">Figure 1</A> (ignoring the dotted
-line) did not have any cycles, but if we add a dependency between
-<TT>bar.cpp</TT> and <TT>dax.h</TT> there there will be. Such a
-dependency would be flagged as a user error.
-
-<P>
-<PRE>
- add_edge(bar_cpp, dax_h, g);
-</PRE>
+<title>File Dependency Example</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:file-depend-eg"></a>
+File Dependency Example 文件依赖关系示例
+</h1>
+
+<p>图抽象在计算机科学中最常见的用途是跟踪依赖相关。一个我们每天基本上都会遇
到的有关依赖关系跟踪的例子就是，在我们所编写的程序中的文件编译依赖关系。这些
依赖关系会在象 <tt>make</tt> 这样的程序或是象
+Visual C++ 这些IDE内部用于在某些文件发生变化后找出必须要重编译的最小文件数
量。
+
+</p><p>
+<a href="#fig:file-dep">图1</a> 画出了一个图，<tt>killerapp</tt> 程序中的每
个源文件、目标文件和库文件分别对应一个顶点。图中的边则表示了哪个文件在创建其
它文件时被用到。而箭头所指方向的选择则有些随意。只要我们始终记得箭头表示的
是"被...使用"，那么就没问题了。相反的方向则表示"依赖于"。</p>
+<div align="center"><a name="fig:file-dep"></a>
+<table>
+<caption align="bottom"><strong>图 1:</strong>
+表示文件依赖关系的图</caption>
+<tbody><tr><td><img src="./figs/file_dep.gif" height="351"
width="331"></td></tr>
+</tbody></table>
+</div>
+
+<p>一个象 <tt>make</tt> 那样的编译系统必须可以回答一系列问题：</p><ol>
+<li>如果我们需要编译(或重编译)所有文件，那么要按怎样的顺序来做？
+</li>
+<li>哪些文件可以并行地编译？
+</li>
+<li>如果某个文件发生了变化，哪些文件必须要重编译？
+</li>
+<li>依赖关系中存在循环吗？(这将意味着用户犯了某个错误，并将引发错误)
+</li>
+</ol>
+
+<p>在下面的例子中，我们将依据依赖关系图逐个阐述以上的问题，然后找出提供解决
方案的图算法。在以下所有例子中都将使用<a href="#fig:file-dep">图1</a>中的
图。这个例子的源代码可以在文件 <a
href="../example/file_dependencies.cpp"><tt>examples/file_dependencies.cpp</tt></a>
中找到。</p><h2>Graph Setup 图的建立</h2>
+
+<p>以下我们示范该图的构造。首先，需要以下头文件：</p><pre>#include
<iostream> // std::cout<br>#include <utility> //
std::pair<br>#include <boost/graph/graph_traits.hpp><br>#include
<boost/graph/adjacency_list.hpp><br>#include
<boost/graph/topological_sort.hpp><br></pre>
+
+<p>为简单起见，我们来"手工"构造这个图。而象 <tt>make</tt> 这样的一个编译系
统则会对 <tt>Makefile</tt> 进行分析，取出文件列表并建立依赖关系。我们用
+<tt>adjacency_list</tt> 类来表示这个图。使用表示 <tt>std::vector</tt> 的
+<tt>vecS</tt> 选择符来表示每个边列表，这可以提供高效遍历。而
+<tt>bidirectionalS</tt> 选择符则表示我们要的是一个有向图，可以同时访问每个
顶点的出边和入边，并且
+<tt>color_property</tt> 将一个颜色属性关联至图中的每个顶点。该颜色属性将在
后面章节中多个算法中使用。</p><pre> enum files_e { dax_h, yow_h, boz_h,
zow_h, foo_cpp, <br> foo_o, bar_cpp, bar_o,
libfoobar_a,<br> zig_cpp, zig_o, zag_cpp, zag_o,
<br> libzigzag_a, killerapp, N };<br> const char* name[] =
{ "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp",<br> "foo.o", "bar.cpp", "bar.o", "libfoobar.a",<br> "zig.cpp", "zig.o", "zag.cpp", "zag.o",<br> "libzigzag.a", "killerapp"
};<br><br> typedef std::pair<int, int> Edge;<br> Edge used_by[] =
{<br> Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h,
yow_h),<br> Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),<br>
Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),<br>
Edge(zow_h, foo_cpp), <br> Edge(foo_cpp, foo_o),<br> Edge(foo_o,
libfoobar_a),<br> Edge(bar_cpp, bar_o),<br> Edge(bar_o,
libfoobar_a),<br> Edge(libfoobar_a, libzigzag_a),<br> Edge(zig_cpp,
zig_o),<br> Edge(zig_o, libzigzag_a),<br> Edge(zag_cpp,
zag_o),<br> Edge(zag_o, libzigzag_a),<br> Edge(libzigzag_a,
killerapp)<br> };<br><br> using namespace boost;<br> typedef
adjacency_list<vecS, vecS, bidirectionalS, <br>
property<vertex_color_t, default_color_type><br> > Graph;<br>
Graph g(used_by, used_by + sizeof(used_by) / sizeof(Edge), N);<br> typedef
graph_traits<Graph>::vertex_descriptor Vertex;<br></pre>
+
+<h2>Compilation Order (All Files) 编译顺序(所有文件)</h2>
+
+<p>对某个特定项目首次执行 <tt>make</tt> 时，所有文件都必须被编译。给定各文
件间的依赖关系，编译和链接它们的正确顺序是怎样的呢？首先我们必须制定这样的一
张图。编译的顺序与图中顶点的顺序是一样的。其顺序上的约束就是文件依赖关系的顺
序，我们用边来表示它。如果图中有一条边<i>(u,v)</i>，则 <i>v</i> 最好不要排
在 <i>u</i> 之前。事实上，这种顺序的约束被称为<i>拓朴排序</i>。因此，回答编
译顺序的问题非常容易，只需调用BGL算法 <a
href="./topological_sort.html"><tt>topological_sort()</tt></a>。拓朴排序的传
统输出格式是被排序顶点的一个链表。但BGL算法则可将已排序的顶点写入任意的 <a
href="http://www.sgi.com/tech/stl/OutputIterator.html";>输出迭代器</a>，这样
更为灵活。以下我们将用
+<tt>std::front_insert_iterator</tt> 来创建一个输出迭代器，将顶点插入到一个
链表的前端。其它可能的选项是，将输出写至文件，或是插入到另一个STL或定制的容
器中。</p><pre> typedef std::list<Vertex> MakeOrder;<br> MakeOrder
make_order;<br> boost::topological_sort(g,
std::front_inserter(make_order));<br> <br> std::cout << "make
ordering: ";<br> for (MakeOrder::iterator i =
make_order.begin();<br> i != make_order.end(); ++i)<br> std::cout
<< name[*i] << " ";<br> std::cout <<
std::endl;<br></pre>以上程序的输出为：
+<pre> make ordering: zow.h boz.h zig.cpp zig.o dax.h yow.h zag.cpp \<br>
zag.o bar.cpp bar.o foo.cpp foo.o libfoobar.a libzigzag.a
killerapp<br></pre>
+
+<h2><a name="sec:parallel-compilation"></a>
+Parallel Compilation 并行编译
+</h2>
+
+
+
+<p>关于编译系统的另一个可能需要回答的问题是：哪些文件可以同时编译？这样可以
让系统生成多个进程并利用多处理器来提高构建的速度。这个问题也可以以
+另一种稍微不同的方式提出：假如可以同时构建不限数量的文件，那么某个文件最早
可以在什么时候构建？一个文件什么时候可以构建的主要标准是，它所依赖的所
+有文件都已完成构建。为简单起见，在这个例子中，我们假设每个文件需要1个时间单
元来构建(即使是头文件)。为了并行编译，我们可以同时构建所对应的顶点
+相互间没有依赖关系的所有文件，例如，在第一步时，构建所有<i>入度</i>为0的文
件。对于其它文件，决定某个文件的"构建时间点"的主要标准就是，构建的时间点必须
比它所依赖的文件的最大时间点大一个时间单元。
+
+</p><p>我们先创建一个 vector <code>time</code> 用于保存每个文件的构建时间
点。我们要将其中的每个值初始化为零。</p><pre> std::vector<int>
time(N, 0);<br></pre>
+
+<p>现在，我们要按拓朴顺序访问各顶点，从需要首先构建的哪些文件开始，到最后要
被构造的文件为止。不过，我们不是立即打印这个文件顺序，而是基于各个文件所依赖
的文件的构建时间点，来计算每个文件的构建时间点。我们只需要考虑那些入度大于零
的文件。</p>
+
+<pre> for (i = make_order.begin(); i != make_order.end(); ++i) {
<br> if (in_degree (*i, g) > 0) {<br>
Graph::in_edge_iterator j, j_end;<br> int maxdist = 0;<br>
for (tie(j, j_end) = in_edges(*i, g); j != j_end; ++j)<br> maxdist
= std::max(time[source(*j, g)], maxdist);<br>
time[*i]=maxdist+1;<br> }<br> }<br></pre>
+
+<p>最后，我们输出为每个标点计算得到的时间点。</p><pre> std::cout
<< "parallel make ordering, " << std::endl<br>
<< " vertices with same group number" << std::endl<br>
<< " can be made in parallel" << std::endl <<
std::endl;<br> for (boost::tie(i, iend) = vertices(g); i != iend;
++i)<br> std::cout << "time_slot[" << name[*i] << "]
= " << time[*i] << std::endl;<br></pre>输出如下：
+<pre> parallel make ordering, <br> vertices with same group number
<br> can be made in parallel<br> time_slot[dax.h] = 0<br>
time_slot[yow.h] = 1<br> time_slot[boz.h] = 0<br> time_slot[zow.h] =
0<br> time_slot[foo.cpp] = 1<br> time_slot[foo.o] = 2<br>
time_slot[bar.cpp] = 2<br> time_slot[bar.o] = 3<br>
time_slot[libfoobar.a] = 4<br> time_slot[zig.cpp] = 1<br>
time_slot[zig.o] = 2<br> time_slot[zag.cpp] = 2<br> time_slot[zag.o] =
3<br> time_slot[libzigzag.a] = 5<br> time_slot[killerapp] = 6<br></pre>
+
+<h2><a name="SECTION001014000000000000000"></a>
+<a name="sec:cycles"></a>
+<br>
+Cyclic Dependencies 循环依赖
+</h2>
+
+<p>对于编译系统，需要回答的另一个问题是，在其依赖关系中是否存在循环。如果有
循环，系统应能向用户报告一个错误，以便可以去掉该循环。一个较为容易的检测循环
的方法是，运行 <a href="./depth_first_search.html">深度优先搜索</a>，如果搜
索遇到一个已发现的顶点(属于当前搜索树的顶点)，则存在一个循环。BGL的图搜索算
法(其中包括了
+<tt>depth_first_search()</tt>)都可以通过
+<i>遍历器visitor</i> 机制来扩展。遍历器类似于函数对象，但它有多个方法代替单
个的
+<tt>operator()</tt>。遍历器的方法在算法的某些特定点被调用，由此给用户一种办
法来扩展图搜索算法的功能。有关遍历器的详细说明，请见 <a
href="visitor_concepts.html">遍历器概念Visitor Concepts</a> 一节。
+
+</p><p>我们将创建一个遍历器类，并填入 <tt>back_edge()</tt>
+方法，该方法是DFS遇到一条连至某个已发现顶点的边时进行调用的 <a
href="./DFSVisitor.html">DFSVisitor</a> 方法。对该方法的调用表明存在某个循
环。继承自 <tt>dfs_visitor<></tt> 为这个遍历器中的其它遍历器方法提供了
一个空版本。创建了我们的遍历器后，就可以构造一个对象并将它传递给BGL算法。遍
历器对象被以值的方式传入BGL算法，所以 <tt>has_cycle</tt> 标志要以引用的方式
保存在该遍历器中。</p><pre> struct cycle_detector : public
dfs_visitor<><br> {<br> cycle_detector( bool& has_cycle)
<br> : _has_cycle(has_cycle) { }<br><br> template <class Edge,
class Graph><br> void back_edge(Edge, Graph&) {<br>
_has_cycle = true;<br> }<br> protected:<br> bool&
_has_cycle;<br> };<br></pre>
+
+<p>现在我们可以调用BGL的 <tt>depth_first_search()</tt>
+算法，并传入这个循环检测遍历器。</p><pre> bool has_cycle = false;<br>
cycle_detector vis(has_cycle);<br> boost::depth_first_search(g,
visitor(vis));<br> std::cout << "The graph has a cycle? " <<
has_cycle << std::endl;<br></pre>
+
+<p><a href="#fig:file-dep">图1</a> (忽略其中的点线) 中的图不存在循环，但是
如果我们在
+<tt>bar.cpp</tt> 和 <tt>dax.h</tt> 之间增加一个依赖关系，就有了循环。这个依
赖关系被标识为一个用户错误。</p><pre> add_edge(bar_cpp, dax_h,
g);<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 © 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_coloring.html
==============================================================================
--- trunk/libs/graph/doc/graph_coloring.html (original)
+++ trunk/libs/graph/doc/graph_coloring.html Thu Jul 2 20:26:08 2009
@@ -1,191 +1,67 @@
-<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>Graph Coloring Example</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>Graph Coloring</H1>
-
-The graph (or vertex) coloring problem, which involves assigning
-colors to vertices in a graph such that adjacenct vertices have
-distinct colors, arises in a number of scientific and engineering
-applications such as scheduling , register allocation ,
-optimization and parallel numerical computation.
-
-<P>
-Mathmatically, a proper vertex coloring of an undirected graph
-<i>G=(V,E)</i> is a map <i>c: V -> S</i> such that <i>c(u) != c(v)</i>
-whenever there exists an edge <i>(u,v)</i> in <i>G</i>. The elements
-of set <i>S</i> are called the available colors. The problem is often
-to determine the minimum cardinality (the number of colors) of
-<i>S</i> for a given graph <i>G</i> or to ask whether it is able to
-color graph <i>G</i> with a certain number of colors. For example, how
-many color do we need to color the United States on a map in such a
-way that adjacent states have different color? A compiler needs to
-decide whether variables and temporaries could be allocated in fixed
-number of registers at some point. If a target machine has <i>K</i>
-registers, can a particular interference graph be colored with
-<i>K</i> colors? (Each vertex in the interference graph represents a
-temporary value; each edge indicates a pair of temporaries that cannot
-be assigned to the same register.)
-
-<P>
-Another example is in the estimation of sparse Jacobian matrix by
-differences in large scale nonlinear problems in optimization and
-differential equations. Given a nonlinear function <i>F</i>, the
-estimation of Jacobian matrix <i>J</i> can be obtained by estimating
-<i>Jd</i> for suitable choices of vector <i>d</i>. Curtis, Powell and
-Reid [<a href="bibliography.html#curtis74:_jacob">9</a>] observed
that a group of columns of <i>J</i> can be
-determined by one evaluation of <i>Jd</i> if no two columns in this
-group have a nonzero in the same row position. Therefore, a question
-is emerged: what is the number of function evaluations need to compute
-approximate Jacobian matrix? As a matter of fact this question is the
-same as to compute the minimum numbers of colors for coloring a graph
-if we construct the graph in the following matter: A vertex represents
-a column of <i>J</i> and there is an edge if and only if the two
-column have a nonzero in the same row position.
-
-<P>
-However, coloring a general graph with the minimum number of colors
-(the cardinality of set <i>S</i>) is known to be an NP-complete
-problem [<a
-href="bibliography.html#garey79:computers-and-intractability">30</a>].
-One often relies on heuristics to find a solution. A widely-used
-general greedy based approach is starting from an ordered vertex
-enumeration <i>v<sub>1</sub>, ..., v<sub>n</sub></i> of <i>G</i>, to
-assign <i>v<sub>i</sub></i> to the smallest possible color for
-<i>i</i> from <i>1</i> to <i>n</i>. In section <a
-href="constructing_algorithms.html">Constructing graph
-algorithms with BGL</a> we have shown how to write this algorithm in
-the generic programming paradigm. However, the ordering of the
-vertices dramatically affects the coloring. The arbitrary order may
-perform very poorly while another ordering may produces an optimal
-coloring. Several ordering algorithms have been studied to help the
-greedy coloring heuristics including largest-first ordering,
-smallest-last ordering and incidence degree ordering.
-
-<P>
-In the BGL framework, the process of constructing/prototyping such a
-ordering is fairly easy because writing such a ordering follows the
-algorithm description closely. As an example, we present the
-smallest-last ordering algorithm.
-
-<P>
-The basic idea of the smallest-last ordering [<a
-href="bibliography.html#matula72:_graph_theory_computing">29</a>] is
-as follows: Assuming that the vertices <i>v<sub>k+1</sub>, ...,
-v<sub>n</sub></i> have been selected, choose <i>v<sub>k</sub></i> so
-that the degree of <i>v<sub>k</sub></i> in the subgraph induced by
-<i>V - {v<sub>k+1</sub>, ..., v<sub>n</sub>}</i> is minimal.
-
-<P>
-The algorithm uses a bucket sorter for the vertices in the graph where
-bucket is the degree. Two vertex property maps, <TT>degree</TT> and
-<TT>marker</TT>, are used in the algorithm. The former is to store
-degree of every vertex while the latter is to mark whether a vertex
-has been ordered or processed during traversing adjacent vertices. The
-ordering is stored in the <TT>order</TT>. The algorithm is as follows:
-
-<UL>
-<LI>put all vertices in the bucket sorter
-</LI>
-<LI>find the vertex <tt>node</tt> with smallest degree in the bucket sorter
-</LI>
-<LI>number <tt>node</tt> and traverse through its adjacent vertices to
- update its degree and the position in the bucket sorter.
-</LI>
-<LI>go to the step 2 until all vertices are numbered.
-</LI>
-</UL>
-
-<P>
-<PRE>
-namespace boost {
- template <class VertexListGraph, class Order, class Degree,
- class Marker, class BucketSorter>
- void
- smallest_last_ordering(const VertexListGraph& G, Order order,
- Degree degree, Marker marker,
- BucketSorter& degree_buckets) {
- typedef typename graph_traits<VertexListGraph> GraphTraits;
-
- typedef typename GraphTraits::vertex_descriptor Vertex;
- //typedef typename GraphTraits::size_type size_type;
- typedef size_t size_type;
-
- const size_type num = num_vertices(G);
-
- typename GraphTraits::vertex_iterator v, vend;
- for (tie(v, vend) = vertices(G); v != vend; ++v) {
- put(marker, *v, num);
- put(degree, *v, out_degree(*v, G));
- degree_buckets.push(*v);
- }
-
- size_type minimum_degree = 1;
- size_type current_order = num - 1;
-
- while ( 1 ) {
- typedef typename BucketSorter::stack MDStack;
- MDStack minimum_degree_stack = degree_buckets[minimum_degree];
- while (minimum_degree_stack.empty())
- minimum_degree_stack = degree_buckets[++minimum_degree];
-
- Vertex node = minimum_degree_stack.top();
- put(order, current_order, node);
-
- if ( current_order == 0 ) //find all vertices
- break;
-
- minimum_degree_stack.pop();
- put(marker, node, 0); //node has been ordered.
-
- typename GraphTraits::adjacency_iterator v, vend;
- for (tie(v,vend) = adjacent_vertices(node, G); v != vend; ++v)
-
- if ( get(marker, *v) > current_order ) { //*v is unordered
vertex
- put(marker, *v, current_order); //mark the columns adjacent to
node
-
- //It is possible minimum degree goes down
- //Here we keep tracking it.
- put(degree, *v, get(degree, *v) - 1);
- minimum_degree = std::min(minimum_degree, get(degree, *v));
-
- //update the position of *v in the bucket sorter
- degree_buckets.update(*v);
- }
-
- current_order--;
- }
- //at this point, get(order, i) == vertex(i, g);
- }
-} // namespace boost
-</PRE>
+<title>Graph Coloring Example</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>Graph Coloring 图着色</h1>图(或顶点)的着色问题，即为图中的顶点指定颜
色，使得相邻的顶点具有不同的颜色，该问题在很多科学和工程应用中出现，如调度、
寄存器分配、优化和并行数值计算。
+
+<p>数学上，一个无向图
+<i>G=(V,E)</i> 的一个正确的顶点着色是指一个映射 <i>c: V -> S</i>，满足
<i>c(u) != c(v)</i>
+如果在 <i>G</i> 中有一条边 <i>(u,v)</i><i></i>。集合 <i>S</i> 中的颜色被称
为可用色。问题通常是，对于一个给定图 <i>G</i>，确定
+<i>S</i> 的最小基数(即颜色数)，或者是问，能否对图 <i>G</i> 以特定数量的颜色
着色。例如，我们需要多少种颜色才可以在地图上对美国进行着色，令相邻州具有不同
的颜色？编译器常常需要确定在同一点上，变量和临时值是否可以被分配到固定数量的
寄存器中。如果目标机器有 <i>K</i>
+个寄存器，则一个特定的干涉图能否以
+<i>K</i> 种颜色着色？(干涉图中的每个顶点表示一个临时值；每条边则表示不能赋
给同一个寄存器的一对临时值)。
+
+</p><p>另一个例子是，在优化和微分方程的大规模非线性问题中以差分对稀疏
Jacobian矩阵进行估算。给定一个非线性函数 <i>F</i>，Jacobian矩阵 <i>J</i> 的
估算可以通过对向量 <i>d</i> 的合适选择估算
+<i>Jd</i> 得到。Curtis, Powell 和
+Reid [<a href="bibliography.html#curtis74:_jacob">9</a>]指出，可以通过
对 <i>Jd</i> 的求值来确定 <i>J</i> 的列组，如果在该图中没有两列在同一行的位
置为非零。因此，问题被归结为：计算近似的Jacobian矩阵需要求值的函数数量？其实
这个问题和计算一个图的最小着色数量是一样的，如果我们以如下方式构造这个图：每
个顶点表示 <i>J</i> 的一列，当且仅当在同一行的位置上具有非零值时，两点间有
边。
+
+</p><p>但是，对一个通用图以最小数量颜色(集合 <i>S</i> 的基数)进行着色，已知
是一个NP-完全问题[<a
href="bibliography.html#garey79:computers-and-intractability">30</a>]。人们
通常依赖于启发式来寻找答案。一种广泛使用的通用的贪心法是，从 <i>G</i> 的一个
有序顶点枚举 <i>v<sub>1</sub>, ..., v<sub>n</sub></i> 开始，对于从 <i>1</i>
到 <i>n</i> 的
+<i>i</i>，给 <i>v<sub>i</sub></i> 赋一个最小的可用颜色。在 <a
href="constructing_algorithms.html">Constructing graph
+algorithms with BGL</a> 一节中，我们示范了以泛型编程的范式来编写这样的算
法。但是，顶点的顺序显著地影响着色结果。某个顺序可能会执行得非常糟糕，而另一
种顺序又可能得到最优的着色方案。目前已研究了多个对贪心着色法有帮助的排序算
法，包括：最大优先顺序、最小最后顺序和关联度顺序。
+
+</p><p>在BGL框架中，这种顺序的构造/原型过程非常简单，因为编写这种顺序是非常
符合这个算法说明的。作为一个示例，我们给出最小最后顺序的算法。
+
+</p><p>最小最后顺序[<a
href="bibliography.html#matula72:_graph_theory_computing">29</a>]的基本思路
如下：假定顶点 <i>v<sub>k+1</sub>, ...,
+v<sub>n</sub></i> 已被选中，选出 <i>v<sub>k</sub></i> 满足
<i>v<sub>k</sub></i> 在由
+<i>V - {v<sub>k+1</sub>, ..., v<sub>n</sub>}</i> 给出的子图中的度是最小的。
+
+</p><p>该算法针对图中的顶点使用了一个桶排序器，其中以顶点的度数为桶。在算法
中还使用了两个顶点属性映射，<tt>degree</tt> 和
+<tt>marker</tt>。前者保存了每个顶点的度数，而后者用于标记某个顶点在遍历邻接
顶点时是否已被排序或已处理。序号被保存在 <tt>order</tt> 中。算法如下：
+
+</p><ul>
+<li>将所有顶点放入桶排序器
+</li>
+<li>在桶排序器中找出最小度数的顶点节点
+</li>
+<li>对节点编号并遍历它的邻接顶点更新顶点度数和在桶排序器中的位置。
+</li>
+<li>跳至第2步，直至所有顶点被编号。
+</li>
+</ul>
+
+<pre>namespace boost {<br> template <class VertexListGraph, class
Order, class Degree, <br> class Marker, class
BucketSorter><br> void <br> smallest_last_ordering(const
VertexListGraph& G, Order order, <br> Degree
degree, Marker marker, <br> BucketSorter&
degree_buckets) {<br> typedef typename
graph_traits<VertexListGraph> GraphTraits;<br><br> typedef
typename GraphTraits::vertex_descriptor Vertex;<br> //typedef typename
GraphTraits::size_type size_type;<br> typedef size_t
size_type;<br><br> const size_type num = num_vertices(G);<br> <br>
typename GraphTraits::vertex_iterator v, vend;<br> for (tie(v, vend) =
vertices(G); v != vend; ++v) {<br> put(marker, *v, num);<br>
put(degree, *v, out_degree(*v, G));<br>
degree_buckets.push(*v);<br> }<br> <br> size_type minimum_degree =
1;<br> size_type current_order = num - 1;<br> <br> while ( 1 )
{<br> typedef typename BucketSorter::stack MDStack;<br> MDStack
minimum_degree_stack = degree_buckets[minimum_degree];<br> while
(minimum_degree_stack.empty())<br> minimum_degree_stack =
degree_buckets[++minimum_degree];<br> <br> Vertex node =
minimum_degree_stack.top();<br> put(order, current_order,
node);<br> <br> if ( current_order == 0 ) //查找所有顶点
<br> break;<br> <br> minimum_degree_stack.pop();<br>
put(marker, node, 0); //node 已排序。<br> <br> typename
GraphTraits::adjacency_iterator v, vend;<br> for (tie(v,vend) =
adjacent_vertices(node, G); v != vend; ++v)<br> <br> if (
get(marker, *v) > current_order ) { //*v 是未排序的顶点<br>
put(marker, *v, current_order); //标记与节点相邻的列<br>
<br> //有可能最小度数降低了，我们在此跟踪它。<br>
put(degree, *v, get(degree, *v) - 1); <br> minimum_degree =
std::min(minimum_degree, get(degree, *v)); <br> <br> //更
新桶排序中的 *v 位置<br> degree_buckets.update(*v);<br>
}<br><br> current_order--;<br> }<br> //在此，get(order, i) ==
vertex(i, g);<br> }<br>} // namespace boost<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 © 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_theory_review.html
==============================================================================
--- trunk/libs/graph/doc/graph_theory_review.html (original)
+++ trunk/libs/graph/doc/graph_theory_review.html Thu Jul 2 20:26:08 2009
@@ -1,9 +1,7 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
-<meta content="text/html; charset=UTF-8" http-equiv="content-type">
-<!-- -- Copyright (c) Jeremy Siek 2000 -- -- Distributed under the Boost
Software License, Version 1.0. -- (See accompanying file LICENSE_1_0.txt or
copy at -- http://www.boost.org/LICENSE_1_0.txt) --><title>Boost Graph
Library: Graph Theory Review</title>
-
-</head>
+<meta content="text/html; charset=UTF-8" http-equiv="content-type"><!-- --
Copyright (c) Jeremy Siek 2000 -- -- Distributed under the Boost Software
License, Version 1.0. -- (See accompanying file LICENSE_1_0.txt or copy at
-- http://www.boost.org/LICENSE_1_0.txt) -->
+<title>Boost Graph Library: Graph Theory Review</title></head>
<body style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255);"
alink="#ff0000" link="#0000ee" vlink="#551a8b">
<img src="../../../boost.png" alt="C++ Boost" height="86" width="277"> <br
clear="">
<h1>图论基础回顾<br>
@@ -165,7 +163,7 @@
<p>
树边是指通过图搜索算法遍历一个图时(隐式或显式地)建立的搜索树(或森林)中的
边。如果在遍历（对应于<a href="visitor_concepts.html"> visitor </a>的explore
()方法）边（u，v）时，点v首先被遍历到，那么边（u，v）就是一条树边。后向边将
顶点连接到他们在搜索树中的祖先。因此对于反向边（u，v），点v
-一定是点u的祖先。自环被认为是反向边。前向边是指将点u连接到它在搜索树中的子
孙节点v的一条非树边（u，v）。交叉边为不属于前面定义的三种边之一的
+一定是点u的祖先。自环被认为是反向边。前向边是指将点u连接到它在搜索树中的后
代节点v的一条非树边（u，v）。交叉边为不属于前面定义的三种边之一的
边。<br>
</p>
<h2><a name="sec:bfs-algorithm"></a> 广度优先搜索</h2>
@@ -197,7 +195,7 @@
问的邻接顶点时，才会选择下一个未访问邻接顶点。该算法会回溯到前面顶点继续沿
着未被访问的边来遍历顶点。DFS算法从一点遍历
完所有能够到达的顶点后，将选择仍未被发现的顶点来继续进行搜索。搜索的过程将
建立了一组深度优先树（depth-first
trees），这些树合起来就成了深度优先森林（depth-first
-forest）。一次DFS会把图中的边分为三类：树边，反向边，正向边或交叉边（这两种
边不能区分）。一个给定的图可以有多个有效的深度优先森林，所以
+forest）。一次DFS会把图中的边分为三类：树边，反向边，正向边或交叉边（不能确
定是哪一种）。一个给定的图可以有多个有效的深度优先森林，所以
对于图的边也有多种不同的(也是同样有效的)分类方法。<br>
<p>DFS一个比较有意思的特性是每个点的发现和结束时间会形成对称结构。如果我们
在发现一个顶点时加一个左括号，在结束一个顶点时加一个
右括号，那么结果就是一个正确嵌套的括号集。<a
href="graph_theory_review.html#fig:dfs-example">图七</a>示
Modified: trunk/libs/graph/doc/kevin_bacon.html
==============================================================================
--- trunk/libs/graph/doc/kevin_bacon.html (original)
+++ trunk/libs/graph/doc/kevin_bacon.html Thu Jul 2 20:26:08 2009
@@ -1,312 +1,106 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek 2000
--
-- 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>Kevin Bacon Example</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>Six Degrees of Kevin Bacon</H1>
-
-<P>
-A fun application of graph theory comes up in the popular game ``Six
-Degrees of Kevin Bacon''. The idea of the game is to connect an actor
-to Kevin Bacon through a trail of actors who appeared together in
-movies, and do so in less than six steps. For example, Theodore
-Hesburgh (President Emeritus of the University of Notre Dame) was in
-the movie ``Rudy'' with the actor Gerry Becker, who was in the movie
-``Sleepers'' with Kevin Bacon. Why Kevin Bacon? For some reason the
-three students who invented the game, Mike Ginelli, Craig Fass, and
-Brian Turtle decided that Kevin Bacon is the center of the
-entertainment world. The Kevin Bacon game is quite similar to the <a
-href="http://www.oakland.edu/~grossman/erdoshp.html";>Erdös
-Number</a> which has ``been a part of the folklore of
-mathematicians throughout the world for many years''.
-
-<P>
-The ``Six Degrees of Kevin Bacon'' game is really a graph problem. If
-you assign each actor to a vertex, and add an edge between two actors
-if they have appeared together in a movie, then you have a graph that
-represents the data for this game. Then the problem of finding a trail
-of actors to Kevin Bacon becomes a traditional graph problem: that of
-finding a <I>path</I> between two vertices. Since we wish to find a
-path that is shorter than six steps, ideally we would find the
-<I>shortest path</I> between the vertices. One might think to apply
-Dijkstra's shortest path algorithm to this problem, but that would be
-overkill since Dijkstra's algorithm is meant for situations when each
-edge has an associated length (or weight) and the goal is to find the
-path with the shortest cumulative length. Since we are only concerned
-with finding the shortest paths in terms of the number of edges the
-breadth-first search algorithm will solve the problem (and use less
-time than Dijkstra's).
-
-<P>
-
-<H2>Input File and Graph Setup</H2>
-
-<P>
-For this example we will use a much smaller graph than all movies and
-all actors. The full source code for this example is in <a
-href="../example/kevin-bacon.cpp"><TT>examples/kevin-bacon.cpp</TT></a>.
-We have supplied a file <TT>kevin-bacon.dat</TT> which contains a list
-of actor pairs who appeared in the same movie. Each line of the file
-contains an actor's name, a movie, and another actor that appeared in
-the movie. The ``;'' character is used as a separator. Here is an
-excerpt.
-
-<P>
-<PRE>
-Patrick Stewart;Prince of Egypt, The (1998);Steve Martin
-</PRE>
-
-<P>
-Our first task will be to read in the file and create a graph from
-it. We use a <TT>std::ifstream</TT> to input the file.
-
-<P>
-<PRE>
- std::ifstream datafile("./kevin-bacon.dat");
- if (!datafile) {
- std::cerr << "No ./kevin-bacon.dat file" << std::endl;
- return EXIT_FAILURE;
- }
-</PRE>
-
-<P>
-We will want to attach the actor's names to the vertices in the graph,
-and the movie names to the edges. We use the <TT>property</TT> class to
-specify the addition of these vertex and edge properties to the graph.
-We choose to use an undirected graph, because the relationship of
-actors appearing together in a movie is symmetric.
-
-<P>
-<PRE>
- using namespace boost;
- typedef adjacency_list<vecS, vecS, undirectedS,
- property<vertex_name_t, string>,
- property<edge_name_t, string > >
- > Graph;
-</PRE>
-
-<P>
-To access the properties, we will need to obtain property map
-objects from the graph. The following code shows how this is done.
-
-<P>
-<PRE>
- property_map<Graph, vertex_name_t>::type actor_name =
get(vertex_name, g);
- property_map<Graph, edge_name_t>::type connecting_movie =
get(edge_name, g);
-</PRE>
-
-<P>
-Next we can start to loop through the file, parsing each line into a
-sequence of tokens using the <a href="../../tokenizer/index.html">Boost
-Tokenizer Library</a>.
-
-<P>
-<PRE>
- for (std::string line; std::getline(datafile, line);) {
- char_delimiters_separator<char> sep(false, "", ";");
- tokenizer<> line_toks(line, sep);
- ...
- }
-</PRE>
-
-<P>
-Each line of the input corresponds to an edge in the graph, with the
-two actors as the vertices incident to the edge, and the movie name
-will be a property attached to the edge. One challenge in creating the
-graph from this format of input is that the edges are specified by a
-pair of actor names. As we add vertices to the graph, we'll need to
-create a map from actor names to their vertices so that later
-appearances of the same actor (on a different edge) can be linked with
-the correct vertex in the graph. The <a
-href="http://www.sgi.com/tech/stl/Map.html";><TT>std::map</TT></a>
-can be used to implement this mapping.
-
-<P>
-<PRE>
- typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef std::map<string, Vertex> NameVertexMap;
- NameVertexMap actors;
-</PRE>
-
-<P>
-The first token will be an actor's name. If the actor is not already
-in our actor's map we will add a vertex to the graph, set the name
-property of the vertex, and record the vertex descriptor in the map.
-If the actor is already in the graph, we will retrieve the vertex
-descriptor from the map's <TT>pos</TT> iterator.
-
-<P>
-<PRE>
- NameVertexMap::iterator pos;
- bool inserted;
- Vertex u, v;
-
- tokenizer<>::iterator i = line_toks.begin();
- std::string actors_name = *i++;
-
- tie(pos, inserted) = actors.insert(std::make_pair(actors_name,
Vertex()));
- if (inserted) {
- u = add_vertex(g);
- actor_name[u] = actors_name;
- pos->second = u;
- } else
- u = pos->second;
-</PRE>
-
-<P>
-The second token is the name of the movie, and the third token is the
-other actor. We use the same technique as above to insert the second
-actor into the graph.
-
-<P>
-<PRE>
- std::string movie_name = *i++;
-
- tie(pos, inserted) = actors.insert(std::make_pair(*i, Vertex()));
- if (inserted) {
- v = add_vertex(g);
- actor_name[v] = *i;
- pos->second = v;
- } else
- v = pos->second;
-</PRE>
-
-<P>
-The final step is to add an edge connecting the two actors, and record
-the name of the connecting movie.
-
-<P>
-<PRE>
- graph_traits<Graph>::edge_descriptor e;
- tie(e, inserted) = add_edge(u, v, g);
- if (inserted)
- connecting_movie[e] = movie_name;
-</PRE>
-
-<P>
-
-<H2>A Custom Visitor Class</H2>
-
-<P>
-We create a custom visitor class to record the Kevin Bacon
-numbers. The Kevin Bacon number will be the shortest distances from
-each actor to Kevin Bacon. This distance has also been referred to as
-the ``Bacon Number'' in memory of the ``Erdos Number'' used to rank
-mathematicians according to how many publications separate them from
-Paul Erdos. The shortest distance to from Kevin Bacon to each actor
-will follow the breadth-first tree. The BFS algorithm identifies edges
-that belong to the breadth-first tree and calls our visitor's
-<tt>tree_edge</tt> function. We record the distance to the target
-vertex as one plus the distance to the source vertex.
-
-
-<PRE>
- template <typename DistanceMap>
- class bacon_number_recorder : public default_bfs_visitor
- {
- public:
- bacon_number_recorder(DistanceMap dist) : d(dist) { }
-
- template <typename Edge, typename Graph>
- void tree_edge(Edge e, const Graph& g) const
- {
- typename graph_traits<Graph>::vertex_descriptor
- u = source(e, g), v = target(e, g);
- d[v] = d[u] + 1;
- }
- private:
- DistanceMap d;
- };
- // Convenience function
- template <typename DistanceMap>
- bacon_number_recorder<DistanceMap>
- record_bacon_number(DistanceMap d)
- {
- return bacon_number_recorder<DistanceMap>(d);
- }
-</PRE>
-
-<P>
-We will use a vector to store the bacon numbers.
-
-<P>
-<PRE>
- std::vector<int> bacon_number(num_vertices(g));
-</PRE>
-
-<H2>Apply the Breadth-First Search</H2>
-
-<P>
-The BFS algorithm requires a source vertex as input; of course this
-will be Kevin Bacon. We now call the BGL BFS algorithm, passing in the
-graph, source vertex, and the visitor.
-
-<P>
-<PRE>
- Vertex src = actors["Kevin Bacon"];
- bacon_number[src] = 0;
-
- breadth_first_search(g, src,
visitor(record_bacon_number(&bacon_number[0])));
-</PRE>
-
-<P>
-We can output the Bacon number for each actor simply by looping
-through all the vertices in the graph and use them to index into the
-<TT>bacon_number</TT> vector.
-
-<P>
-<PRE>
- graph_traits<Graph>::vertex_iterator i, end;
- for (boost::tie(i, end) = vertices(g); i != end; ++i)
- std::cout << actor_name[*i] << "'s bacon number is "
- << bacon_number[*i] << std::endl;
-</PRE>
-
-<P>
-Note that vertex descriptor objects can not always be used as indices
-into vectors or arrays such as <TT>bacon_number</TT>. This is valid
-with the <TT>adjacency_list</TT> class with <TT>VertexList=vecS</TT>,
-but not with other variations of <TT>adjacency_list</TT>. A more
-generic way to index based on vertices is to use the ID property
-map (<TT>vertex_index_t</TT>) in coordination with the <A
-HREF="../../property_map/iterator_property_map.html"><TT>iterator_property_map</TT></a>.
-
-<P>
-Here are some excepts from the output of the program.
-<PRE>
-William Shatner's bacon number is 2
-Denise Richards's bacon number is 1
-Kevin Bacon's bacon number is 0
-Patrick Stewart's bacon number is 2
-Steve Martin's bacon number is 1
-...
-</PRE>
+<title>Kevin Bacon Example</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>Six Degrees of Kevin Bacon 六度分离理论</h1>
+
+<p>图论的一个有趣的应用出现在一个名为"Kevin Bacon 六度理论"的流行游戏中。这
个游戏的思路是这样的，通过追溯两个在同一部电影中出现的演员，可以将任一演员
与 Kevin Bacon 联系起来，最多不超过六步。例如，Theodore
+Hesburgh(Notre Dame 大学的名誉主席)在电影 ``Rudy'' 中和演员 Gerry Becker 一
起出现，后者又在电影
+``Sleepers'' 中与 Kevin Bacon 一起出现。为什么要用 Kevin Bacon? 由于某些原
因，发明这个游戏的的三名学生，Mike Ginelli, Craig Fass, 和
+Brian Turtle 认为 Kevin Bacon 是娱乐世界的中心。这个 Kevin Bacon 游戏很象
<a href="http://www.oakland.edu/%7Egrossman/erdoshp.html";>Erdös
+Number</a>，它已经"是多年以来世界各地的数学家的传统活动的一部分"。
+
+</p><p>这个"Kevin Bacon
+六度理论"游戏其实就是一个图论问题。如果你将每个演员对应为一个顶点，如果两个
演员曾在同一部电影中出现就在他们之间增加一条边，这样你就得到了这个游
+戏的一个数据表示。然后，这个查找从某个演员到 Kevin Bacon 的联系就变为一个经
典的图论问题：查找两个顶点间的<i>路径</i>。因为我们要找到一条长度短于六步的
路径，最好就是找出两点间的<i>最短路径</i>。
+你可能想对这个问题应用Dijkstra最短路径算法，但是这样有点大材小用，因为
Dijkstra算法是用于那些每条边带有长度(或权重)的情形的，其
+目标是找到总长度最短的路径。因为我们只需要按边数来查找最短路径，所以广度优
先搜索算法就可以解决这个问题了(并且它的用时要少于Dijkstra算
+法)。
+</p><h2>Input File and Graph Setup 输入文件与图的建立</h2>
+
+<p>在这个例子中，我们将使用一个比所有电影和所有演员小得多的图。该例子的完整
源代码在 <a
href="../example/kevin-bacon.cpp"><tt>examples/kevin-bacon.cpp</tt></a> 中。
我们还提供了一个名为 <tt>kevin-bacon.dat</tt> 的文件，其中包含有一个列表，记
录了哪些演员在同一部电影中出现的演员对。该文件的每一行包含一个演员名字、一部
电影和在该电影中的另一位演员。以";"字符作为分隔符。以下是一个例子。
</p><pre>Patrick Stewart;Prince of Egypt, The (1998);Steve Martin<br></pre>
+
+<p>我们第一个任务是读入这个文件并从它创建一个图。我们用一个
<tt>std::ifstream</tt> 来输入这个文件。</p><pre> std::ifstream
datafile("./kevin-bacon.dat");<br> if (!datafile) {<br> std::cerr
<< "No ./kevin-bacon.dat file" << std::endl;<br> return
EXIT_FAILURE;<br> }<br></pre>
+
+<p>我们想把演员的名字关联到图中的顶点上，把电影的名字关联到边上。我们用
<tt>property</tt> 类来指定这些附加到图上的顶点属性和边属性。我们选择使用无向
图，因为演员在同一部电影中出现的关系是对称的。</p><pre> using namespace
boost;<br> typedef adjacency_list<vecS, vecS, undirectedS, <br>
property<vertex_name_t, string>,<br> property<edge_name_t,
string > ><br> > Graph;<br></pre>
+
+<p>要访问这些属性，我们需要从图中获得属性映射无明。以下代码示范了该怎么做。
</p><pre> property_map<Graph, vertex_name_t>::type actor_name =
get(vertex_name, g);<br> property_map<Graph, edge_name_t>::type
connecting_movie = get(edge_name, g);<br></pre>
+
+<p>接下来我们就可以开始遍历输入文件，使用 <a
href="../../tokenizer/index.html">Boost
+Tokenizer 库</a> 对每一行进行分析，存入一个记号序列。
+
+</p><pre> for (std::string line; std::getline(datafile, line);) {<br>
char_delimiters_separator<char> sep(false, "", ";");<br>
tokenizer<> line_toks(line, sep);<br> ...<br> }<br></pre>
+
+<p>输入的每一行对应图中的一条边，两个演员作为该边的顶点，而电影名则是附着到
这条边上的一个属性。从这种输入格式创建相关图的一个挑战是，边是用一
+对演员名来指定的。由于我们是把顶点加到图中，所以我们需要创建一个从演员名到
其对应顶点的映射，这样才可能在同一个演员(在另一条边上)再次出现时，把
+它链接到图中正确的顶点上。<a
href="http://www.sgi.com/tech/stl/Map.html";><tt>std::map</tt></a>
+可以用于实现这个映射。
+
+</p><pre> typedef graph_traits<Graph>::vertex_descriptor
Vertex;<br> typedef std::map<string, Vertex> NameVertexMap;<br>
NameVertexMap actors;<br></pre>
+
+<p>每行的第一个记号是一个演员名。如果该演员尚未存在于我们的演员映射中，我们
将往图中增加一个顶点，设置该顶点的名字属性，并将该顶点描述符记录在这个
map中。如果该演员已经在图中，我们就从这个map的 <tt>pos</tt> 迭代器取出这个顶
点的描述符。
+
+</p><pre> NameVertexMap::iterator pos; <br> bool inserted;<br> Vertex
u, v;<br><br> tokenizer<>::iterator i = line_toks.begin();<br>
std::string actors_name = *i++;<br><br> tie(pos, inserted) =
actors.insert(std::make_pair(actors_name, Vertex()));<br> if (inserted)
{<br> u = add_vertex(g);<br> actor_name[u] = actors_name;<br>
pos->second = u;<br> } else<br> u = pos->second;<br></pre>
+
+<p>第二个记号是电影名，第三个记号则是另一位演员。我们使用同样的技术将第二个
演员插入到图中。
+
+</p><pre> std::string movie_name = *i++;<br> <br> tie(pos,
inserted) = actors.insert(std::make_pair(*i, Vertex()));<br> if (inserted)
{<br> v = add_vertex(g);<br> actor_name[v] = *i;<br>
pos->second = v;<br> } else<br> v = pos->second;<br></pre>
+
+<p>最后一步是增加一条连接这两个演员的边，并记下形成这个连接的电影名。
+
+</p><pre> graph_traits<Graph>::edge_descriptor e;<br> tie(e,
inserted) = add_edge(u, v, g);<br> if (inserted)<br>
connecting_movie[e] = movie_name;<br></pre>
+
+<h2>A Custom Visitor Class 定制的遍历器类</h2>
+
+<p>现在我们创建一个定制的遍历器类来记录 Kevin Bacon
+数。Kevin Bacon 数是指从一个演员到 Kevin Bacon 的最短距离。这个距离也被称
为"Bacon 数"，记得"Erdos 数"就被用于按照数学家与
+Paul Erdos 相差的出版物数量来对数学家进行排名。从 Kevin Bacon 到每个演员的
最短距离符合广度优先树。BFS算法可以标识出属于广度优先树的边，并调用我们的遍
历器的
+<tt>tree_edge</tt> 函数。我们把到目标顶点的距离记录为到源顶点的距离加一。
+
+
+</p><pre> template <typename DistanceMap><br> class
bacon_number_recorder : public default_bfs_visitor<br> {<br>
public:<br> bacon_number_recorder(DistanceMap dist) : d(dist) {
}<br><br> template <typename Edge, typename Graph><br> void
tree_edge(Edge e, const Graph& g) const<br> {<br> typename
graph_traits<Graph>::vertex_descriptor<br> u = source(e, g), v =
target(e, g);<br> d[v] = d[u] + 1;<br> }<br> private:<br>
DistanceMap d;<br> };<br> // 便利函数<br> template <typename
DistanceMap><br> bacon_number_recorder<DistanceMap><br>
record_bacon_number(DistanceMap d)<br> {<br> return
bacon_number_recorder<DistanceMap>(d);<br> }<br></pre>
+
+<p>我们用一个 vector 来保存 bacon 数。
+
+</p><pre> std::vector<int> bacon_number(num_vertices(g));<br></pre>
+
+<h2>Apply the Breadth-First Search 使用广度优先搜索</h2>
+
+<p>BFS算法要求用一个源顶点作为输入；当然就是 Kevin Bacon 了。现在我们调用
BGL BFS 算法，传入该图、源顶点和遍历器。
+
+</p><pre> Vertex src = actors["Kevin Bacon"];<br> bacon_number[src] =
0;<br><br> breadth_first_search(g, src,
visitor(record_bacon_number(&bacon_number[0])));<br></pre>
+
+<p>我们只需遍历图中的所有顶点并以它们作为
+<tt>bacon_number</tt> 向量的下标，就可以对每个演员输出 Bacon 数。
+
+</p><pre> graph_traits<Graph>::vertex_iterator i, end;<br> for
(boost::tie(i, end) = vertices(g); i != end; ++i)<br> std::cout <<
actor_name[*i] << "'s bacon number is " <br> <<
bacon_number[*i] << std::endl;<br></pre>
+
+<p>请注意，顶点描述符对象并不总是可以被用作象 <tt>bacon_number</tt> 这样的
向量或数组的下标。对于指定了 <tt>VertexList=vecS</tt> 的
<tt>adjacency_list</tt> 类是可以的，但对于其它 <tt>adjacency_list</tt> 就不
可以。基于顶点来索引的更为通用的方法是使用ID属性映射
(<tt>vertex_index_t</tt>)和 <a
href="../../property_map/iterator_property_map.html"><tt>iterator_property_map</tt></a>。
+
+</p><p>以下是该程序输出中的一部分。
+</p><pre>William Shatner's bacon number is 2<br>Denise Richards's bacon
number is 1<br>Kevin Bacon's bacon number is 0<br>Patrick Stewart's bacon
number is 2<br>Steve Martin's bacon number is 1 <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 © 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>
<!-- LocalWords: gif Hesburgh Ginelli Fass Erd vertices cerr namespace
vecS
-->
<!-- LocalWords: undirectedS Tokenizer sep tokenizer toks NameVertexMap
pos
@@ -315,3 +109,4 @@
-->
<!-- LocalWords: indices Shatner's Richards's siek htm
-->
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/sparse_matrix_ordering.html
==============================================================================
--- trunk/libs/graph/doc/sparse_matrix_ordering.html (original)
+++ trunk/libs/graph/doc/sparse_matrix_ordering.html Thu Jul 2 20:26:08
2009
@@ -1,377 +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>Sparse Matrix Ordering Example</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:sparse-matrix-ordering"></A>
-Sparse Matrix Ordering
-</H1>
-
-<P>
-Graph theory was identified as a powerful tool for sparse matrix
-computation when Seymour Parter used undirected graphs to model
-symmetric Gaussian elimination more than 30 years ago [<A
HREF="bibliography.html#parter61:_gauss">28</A>].
-Graphs can be used to model symmetric matrices, factorizations and
-algorithms on non-symmetric matrices, such as fill paths in Gaussian
-elimination, strongly connected components in matrix irreducibility,
-bipartite matching, and alternating paths in linear dependence and
-structural singularity. Not only do graphs make it easier to
-understand and analyze sparse matrix algorithms, but they broaden the
-area of manipulating sparse matrices using existing graph algorithms
-and techniques [<A
- HREF="bibliography.html#george93:graphtheory">13</A>]. In this section,
we are
-going to illustrate how to use BGL in sparse matrix computation such
-as ordering algorithms. Before we go further into the sparse matrix
-algorithms, let us take a step back and review a few things.
-
-<P>
-
-<H2>Graphs and Sparse Matrices</H2>
-
-<P>
-A graph is fundamentally a way to represent a binary relation between
-objects. The nonzero pattern of a sparse matrix also describes a
-binary relation between unknowns. Therefore the nonzero pattern of a
-sparse matrix of a linear system can be modeled with a graph
-<I>G(V,E)</I>, whose <I>n</I> vertices in <I>V</I> represent the
-<I>n</I> unknowns, and where there is an edge from vertex <I>i</I> to
-vertex <I>j</I> when <i>A<sub>ij</sub></i> is nonzero. Thus, when a
-matrix has a symmetric nonzero pattern, the corresponding graph is
-undirected.
-
-<P>
-
-<H2>Sparse Matrix Ordering Algorithms</H2>
-
-<P>
-The process for solving a sparse symmetric positive definite linear
-system, <i>Ax=b</i>, can be divided into four stages as follows:
-<DL>
-<DT><STRONG>Ordering:</STRONG></DT>
-<DD>Find a permutation <i>P</i> of matrix <i>A</i>,
-</DD>
-<DT><STRONG>Symbolic factorization:</STRONG></DT>
-<DD>Set up a data structure for the Cholesky
- factor <i>L</i> of <i>PAP<sup>T</sup></i>,
-</DD>
-<DT><STRONG>Numerical factorization:</STRONG></DT>
-<DD>Decompose <i>PAP<sup>T</sup></i> into <i>LL<sup>T</sup></i>,
-</DD>
-<DT><STRONG>Triangular system solution:</STRONG></DT>
-<DD>Solve <i>LL<sup>T</sup>Px=Pb</i> for <i>x</i>.
-</DD>
-</DL>
-Because the choice of permutation <i>P</i> will directly determine the
-number of fill-in elements (elements present in the non-zero structure
-of <i>L</i> that are not present in the non-zero structure of
-<i>A</i>), the ordering has a significant impact on the memory and
-computational requirements for the latter stages. However, finding
-the optimal ordering for <i>A</i> (in the sense of minimizing fill-in)
-has been proven to be NP-complete [<a
-href="bibliography.html#garey79:computers-and-intractability">30</a>]
-requiring that heuristics be used for all but simple (or specially
-structured) cases.
-
-<P>
-A widely used but rather simple ordering algorithm is a variant of the
-Cuthill-McKee orderings, the reverse Cuthill-McKee ordering algorithm.
-This algorithm can be used as a preordering method to improve ordering
-in more sophisticated methods such as minimum degree
-algorithms [<a href="bibliography.html#LIU:MMD">21</a>].
-
-<P>
-
-<H3><A NAME="SECTION001032100000000000000">
-Reverse Cuthill-McKee Ordering Algorithm</A>
-</H3>
-The original Cuthill-McKee ordering algorithm is primarily designed to
-reduce the profile of a matrix [<A
- HREF="bibliography.html#george81:__sparse_pos_def">14</A>].
-George discovered that the reverse ordering often turned out to be
-superior to the original ordering in 1971. Here we describe the
-Reverse Cuthill-McKee algorithm in terms of a graph:
-
-<OL>
-<LI><I>Finding a starting vertex</I>: Determine a starting vertex
- <I>r</I> and assign <i>r</i> to <I>x<sub>1</sub></I>.
-</LI>
-<LI><I>Main part</I>: For <I>i=1,...,N</I>, find all
- the unnumbered neighbors of the vertex <I>x<sub>i</sub></I> and number
them
- in increasing order of degree.
-</LI>
-<LI><I>Reversing ordering</I>: The reverse Cuthill-McKee ordering
- is given by <I>y<sub>1</sub>,...,y<sub>N</sub></I> where
- <I>y<sub>i</sub></I> is <I>x<sub>N-i+1</sub></I> for <I>i = 1,...,N</I>.
-</LI>
-</OL>
-In the first step a good starting vertex needs to be determined. The
-study by George and Liu [<A
-HREF="bibliography.html#george81:__sparse_pos_def">14</A>] showed that
-a pair of vertices which are at maximum or near maximum ``distance''
-apart are good ones. They also proposed an algorithm to find such a
-starting vertex in [<A
-HREF="bibliography.html#george81:__sparse_pos_def">14</A>], which we
-show in <A
-HREF="#fig:ggcl_find_starting_vertex">Figure
-1</A> implemented using the BGL interface.
-
-<P>
-<P></P>
-<DIV ALIGN="CENTER"><A NAME="fig:ggcl_find_starting_vertex"></A>
-<table border><tr><td>
-<pre>
-namespace boost {
- template <class Graph, class Vertex, class Color, class Degree>
- Vertex
- pseudo_peripheral_pair(Graph& G, const Vertex& u, int& ecc,
- Color color, Degree degree)
- {
- typename property_traits<Color>::value_type c = get(color, u);
+<title>Sparse Matrix Ordering Example</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:sparse-matrix-ordering"></a>
+Sparse Matrix Ordering 稀疏矩阵排序
+</h1>
+
+<p>当 Seymour Parter 在30年前使用无向图来为对称高斯消除法建模[<a
href="bibliography.html#parter61:_gauss">28</a>]时，
+图论就是认为是稀疏矩阵计算的一个有力工具。图可以用于模拟对称矩阵、非对称矩
阵的分解和算法，如在高斯消除法中填充路径，矩阵不可还原性的强连通部分，
+双向匹配，以及线性相关和结构奇异中的交替路径。使用图不仅更易于理解和分析稀
疏矩阵算法，还可以扩大至用已有的图算法和技术[<a
href="bibliography.html#george93:graphtheory">13</a>]来处理稀疏矩阵。在本节
中，我们将说明如何在稀疏矩阵计算中使用BGL，如排序算法。在进一步深入到稀疏矩
阵算法之前，我们先退后一步，回顾一些东西。
+
+</p><h2>Graphs and Sparse Matrices 图与稀疏矩阵</h2>
+
+<p>从根本上说，图是对象间某种二元关系的一种表示法。而稀疏矩阵的非零模式也是
某些未知对象间的二元关系。因此，一个线性系统的稀疏矩阵的非零模式可以用一个图
+<i>G(V,E)</i> 来建模，其中 <i>V</i> 的 <i>n</i> 个顶点表示<i></i>
+<i>n</i> 个未知物，当 <i>A<sub>ij</sub></i> 为非零时，从顶点 <i>i</i> 到顶
点 <i>j</i> 之间有一条边。<i><sub></sub></i>因此，当一个矩阵具有对称非零模式
时，对应的图就是无向的。
+
+</p><h2>Sparse Matrix Ordering Algorithms 稀疏矩阵排序算法</h2>
+
+<p>一个稀疏对称正定线性系统 <i>Ax=b</i> 的解答过程，可以分为以下四个阶段：
+</p><dl>
+<dt><strong>排序：</strong></dt>
+<dd>找到矩阵 <i>A</i> 的一个排列 <i>P</i><i></i>,
+</dd>
+<dt><strong>符号分解：</strong></dt>
+<dd>为 <i>PAP<sup>T</sup></i> 的 Cholesky 因子 <i>L</i> 建立一个数据
结构，
+</dd>
+<dt><strong>数字分解：</strong></dt>
+<dd>将 <i>PAP<sup>T</sup></i> 分解至 <i>LL<sup>T</sup></i>,
+</dd>
+<dt><strong>三角系统求解：</strong></dt>
+<dd>对 <i>x</i> 求解 <i>LL<sup>T</sup>Px=Pb</i> <i></i>.
+</dd>
+</dl>因为排列 <i>P</i> 的选择会直接决定注入元素(在非零结构 <i>L</i> 中而不
在非零结构
+<i>A</i> 中的元素)的数量，其顺序对于后面阶段的内存及计算需求有着重大的影
响。但是，找到 <i>A</i> 的优化顺序(即最小注入)已被证明是 NP-完全的[<a
href="bibliography.html#garey79:computers-and-intractability">30</a>]，除了
简单的(或特殊构造的)情况外，都需要使用启发法。
+
+<p>一个广泛使用而非简单排序的算法是
+Cuthill-McKee 排序的一个变体，反 Cuthill-McKee 排序算法。该算法可以被用作预
排序方法，来改进更高一级方法的排序，如最小度数算法[<a
href="bibliography.html#LIU:MMD">21</a>]。
+
+</p><h3><a name="SECTION001032100000000000000">
+Reverse Cuthill-McKee Ordering Algorithm 反Cuthill-McKee排序算法</a>
+</h3>原本的 Cuthill-McKee 排序算法主要是为降低矩阵的规模[<a
href="bibliography.html#george81:__sparse_pos_def">14</a>]而设计的。在
1971年，George 发现它的反序常常比原序更优。下面我们按图论的方法给出反
Cuthill-McKee 算法的描述：
+
+<ol>
+<li><i>找出开始顶点</i>: 确定一个开始顶点
+ <i>r</i> 并将 <i>r</i> 赋给 <i>x<sub>1</sub></i>.
+</li>
+<li><i>主要部分</i>: 对于 <i>i=1,...,N</i>, 找出顶点 <i>x<sub>i</sub></i>
的所有未标数邻居，<i><sub></sub></i>以递增的度数对它们标数。
+</li>
+<li><i>反序</i>: 反 Cuthill-McKee 序由
<i>y<sub>1</sub>,...,y<sub>N</sub></i> 给出，其中
+ <i>y<sub>i</sub></i> 为 <i>x<sub>N-i+1</sub></i>，<i>i = 1,...,N</i>.
+</li>
+</ol>在第一步中需要确定一个好的开始顶点。George 和 Liu [<a
href="bibliography.html#george81:__sparse_pos_def">14</a>]的研究表明，一对最
远或接近最远"距离"的顶点是不错的选择。他们还建议了一个算法来找出这样的一个开
始顶点[<a href="bibliography.html#george81:__sparse_pos_def">14</a>]，我们
在 <a href="#fig:ggcl_find_starting_vertex">图
+1</a> 中给出了用BGL接口的实现。
+<div align="center"><a name="fig:ggcl_find_starting_vertex"></a>
+<table border="1"><tbody><tr><td>
+<pre>namespace boost {<br> template <class Graph, class Vertex, class
Color, class Degree><br> Vertex <br> pseudo_peripheral_pair(Graph&
G, const Vertex& u, int& ecc,<br> Color
color, Degree degree)<br> {<br> typename
property_traits<Color>::value_type c = get(color, u);<br><br>
rcm_queue<Vertex, Degree> Q(degree);<br> <br> typename
boost::graph_traits<Graph>::vertex_iterator ui, ui_end;<br> for
(tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)<br> put(color,
*ui, white(c));<br> breadth_first_search(G, u, Q, bfs_visitor<>(),
color);<br><br> ecc = Q.eccentricity(); <br> return Q.spouse();<br>
}<br> <br> template <class Graph, class Vertex, class Color, class
Degree> <br> Vertex find_starting_node(Graph& G, Vertex r, Color c,
Degree d) {<br> int eccen_r, eccen_x;<br> Vertex x =
pseudo_peripheral_pair(G, r, eccen_r, c, d);<br> Vertex y =
pseudo_peripheral_pair(G, x, eccen_x, c, d);<br><br> while (eccen_x >
eccen_r) {<br> r = x;<br> eccen_r = eccen_x;<br> x =
y;<br> y = pseudo_peripheral_pair(G, x, eccen_x, c, d);<br>
}<br> return x;<br> }<br>} // namespace boost<br></pre>
+</td></tr></tbody></table>
+
+<table><tbody><tr><td>
+<strong>图 1:</strong> <tt>find_starting_node</tt> 的BGL实现。关键部
分 <tt>pseudo_peripheral_pair</tt> 实际上是带有定制队列类型的BFS.
+</td></tr></tbody></table>
+</div>
+<p>第一步的关键部分是BFS的定制队列类型，如 <a
href="#fig:ggcl_find_starting_vertex">图
+1</a> 中所示的。在 <a
href="sparse_matrix_ordering.html#fig:cuthill-mckee">图 2</a> 中所示的主
Cuthill-McKee 算法是一个带通用BFS的被保护的优先队列。如果
+<tt>inverse_permutation</tt> 是一个普通的迭代器，则所保存的结果是原
Cuthill-McKee 序的反排列。另一方面，如果 <tt>inverse_permutation</tt> 是一个
反向迭代器，则所保存的结果是反向 Cuthill-McKee
+序的反向排列。我们的实现十分简单，因为可以重用BGL中的许多组件。
+
+
+</p>
+<div align="center"><a name="fig:cuthill-mckee"></a><a name="6261"></a>
+<table border="1"><tbody><tr><td>
+<pre> template < class Graph, class Vertex, class OutputIterator,
<br> class Color, class Degree ><br> inline void <br>
cuthill_mckee_ordering(Graph& G, <br> Vertex
s,<br> OutputIterator inverse_permutation,
<br> Color color, Degree degree)<br> {<br>
typedef typename property_traits<Degree>::value_type DS;<br>
typename property_traits<Color>::value_type c = get(color, s);<br>
typedef indirect_cmp<Degree, std::greater<DS> > Compare;<br>
Compare comp(degree);<br> fenced_priority_queue<Vertex, Compare >
Q(comp);<br><br> typedef cuthill_mckee_visitor<OutputIterator>
CMVisitor;<br> CMVisitor cm_visitor(inverse_permutation);<br> <br>
typename boost::graph_traits<Graph>::vertex_iterator ui,
ui_end;<br> for (tie(ui, ui_end) = vertices(G); ui != ui_end;
++ui)<br> put(color, *ui, white(c));<br> breadth_first_search(G, s,
Q, cm_visitor, color);<br> } <br></pre>
+</td></tr></tbody></table>
+
+<table>
+<tbody><tr><td> <span style="font-weight: bold;">图
</span><strong> 2:</strong> Cuthill-McKee 算法的BGL实现。 </td></tr>
</tbody></table> </div><br><h3>Minimum Degree Ordering Algorithm 最小度数排
序算法</h3>
- rcm_queue<Vertex, Degree> Q(degree);
-
- typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
- for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
- put(color, *ui, white(c));
- breadth_first_search(G, u, Q, bfs_visitor<>(), color);
-
- ecc = Q.eccentricity();
- return Q.spouse();
- }
-
- template <class Graph, class Vertex, class Color, class Degree>
- Vertex find_starting_node(Graph& G, Vertex r, Color c, Degree d) {
- int eccen_r, eccen_x;
- Vertex x = pseudo_peripheral_pair(G, r, eccen_r, c, d);
- Vertex y = pseudo_peripheral_pair(G, x, eccen_x, c, d);
-
- while (eccen_x > eccen_r) {
- r = x;
- eccen_r = eccen_x;
- x = y;
- y = pseudo_peripheral_pair(G, x, eccen_x, c, d);
- }
- return x;
- }
-} // namespace boost
-</pre>
-</td></tr></table>
-<CAPTION ALIGN="BOTTOM">
-<table><tr><td>
-<STRONG>Figure 1:</STRONG>
-The BGL implementation of <TT>find_starting_node</TT>. The key
-part <TT>pseudo_peripheral_pair</TT> is BFS with a custom queue
- type virtually.
-</td></tr></table></CAPTION>
-</DIV>
-<P></P>
-
-The key part of step one is a custom queue type with BFS as shown in
-<A
-HREF="#fig:ggcl_find_starting_vertex">Figure
-1</A>. The main Cuthill-McKee algorithm shown in Figure <A
-HREF="#fig:cuthill-mckee">Figure 2</A>
-is a fenced priority queue with a generalized BFS. If
-<TT>inverse_permutation</TT> is a normal iterator, the result stored
-is the inverse permutation of original Cuthill-McKee ordering. On the
-other hand, if <TT>inverse_permutation</TT> is a reverse iterator, the
-result stored is the inverse permutation of reverse Cuthill-McKee
-ordering. Our implementation is quite concise because many components
-from BGL can be reused.
-
-
-<P></P>
-<DIV ALIGN="CENTER"><A NAME="fig:cuthill-mckee"></A><A NAME="6261"></A>
-<table border><tr><td>
-<pre>
- template < class Graph, class Vertex, class OutputIterator,
- class Color, class Degree >
- inline void
- cuthill_mckee_ordering(Graph& G,
- Vertex s,
- OutputIterator inverse_permutation,
- Color color, Degree degree)
- {
- typedef typename property_traits<Degree>::value_type DS;
- typename property_traits<Color>::value_type c = get(color, s);
- typedef indirect_cmp<Degree, std::greater<DS> > Compare;
- Compare comp(degree);
- fenced_priority_queue<Vertex, Compare > Q(comp);
+<p>另一类广泛使用的高质量排序算法的模式是基于贪心法，即所选的顺序是在模拟对
称高斯消去过程中的每一步令某些数量最小化。使用这种方法的算法通常以它们的贪心
法所针对的最小化目标来命名[<a href="bibliography.html#ng-raghavan">34</a>]。
- typedef cuthill_mckee_visitor<OutputIterator> CMVisitor;
- CMVisitor cm_visitor(inverse_permutation);
-
- typename boost::graph_traits<Graph>::vertex_iterator ui, ui_end;
- for (tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
- put(color, *ui, white(c));
- breadth_first_search(G, s, Q, cm_visitor, color);
- }
-</pre>
-</td></tr></table>
-<CAPTION ALIGN="BOTTOM">
-<TABLE>
-<TR><TD> <STRONG>Figure 2:</STRONG> The BGL implementation of
-Cuthill-McKee algoithm. </TD></TR> </TABLE></CAPTION> </DIV><P></P>
-<P>
-
-
-<P>
-
-<H3>Minimum Degree Ordering Algorithm</H3>
-
-<P>
-The pattern of another category of high-quality ordering algorithms in
-wide use is based on a greedy approach such that the ordering is
-chosen to minimize some quantity at each step of a simulated -step
-symmetric Gaussian elimination process. The algorithms using such an
-approach are typically distinguished by their greedy minimization
-criteria [<a href="bibliography.html#ng-raghavan">34</a>].
-
-<P>
-In graph terms, the basic ordering process used by most greedy
-algorithms is as follows:
-
-<OL>
-<LI><EM>Start:</EM> Construct undirected graph <i>G<sup>0</sup></i>
- corresponding to matrix <i>A</i>
+</p><p>用图论的术语来说，多数贪心算法所使用的基本排序过程如下：
+
+</p><ol>
+<li><em>开始：</em>构造与矩阵 <i>A</i> 对应的无向图
<i>G<sup>0</sup></i> <i></i>
-</LI>
-<LI><EM>Iterate:</EM> For <i>k = 1, 2, ... </i> until
- <i>G<sup>k</sup> = { }</i> do:
+</li>
+<li><em>迭代：</em>对于 <i>k = 1, 2, ... </i> 做以下操作，直至
<i>G<sup>k</sup> = { }</i> ：
-<UL>
-<LI>Choose a vertex <i>v<sup>k</sup></i> from <i>G<sup>k</sup></i>
- according to some criterion
-</LI>
-<LI>Eliminate <i>v<sup>k</sup></i> from <i>G<sup>k</sup></i> to form
+<ul>
+<li>依据某个标准从 <i>G<sup>k</sup></i> 中选出一个顶点
<i>v<sup>k</sup></i> <i><sup></sup></i>
+</li>
+<li>从 <i>G<sup>k</sup></i> 中消去
<i>v<sup>k</sup></i> <i><sup></sup></i>以形成
<i>G<sup>k+1</sup></i>
-</LI>
-</UL>
-</LI>
-</OL>
-The resulting ordering is the sequence of vertices <i>{v<sup>0</sup>,
-v<sup>1</sup>,...}</i> selected by the algorithm.
-
-<P>
-One of the most important examples of such an algorithm is the
-<I>Minimum Degree</I> algorithm. At each step the minimum degree
-algorithm chooses the vertex with minimum degree in the corresponding
-graph as <i>v<sup>k</sup></i>. A number of enhancements to the basic
-minimum degree algorithm have been developed, such as the use of a
-quotient graph representation, mass elimination, incomplete degree
-update, multiple elimination, and external degree. See [<A
-href="bibliography.html#George:evolution">35</a>] for a historical
-survey of the minimum degree algorithm.
-
-<P>
-The BGL implementation of the Minimum Degree algorithm closely follows
-the algorithmic descriptions of the one in [<A
-HREF="bibliography.html#LIU:MMD">21</A>]. The implementation presently
-includes the enhancements for mass elimination, incomplete degree
-update, multiple elimination, and external degree.
-
-<P>
-In particular, we create a graph representation to improve the
-performance of the algorithm. It is based on a templated ``vector of
-vectors.'' The vector container used is an adaptor class built on top
-the STL <TT>std::vector</TT> class. Particular characteristics of this
-adaptor class include the following:
-
-<UL>
-<LI>Erasing elements does not shrink the associated memory.
- Adding new elements after erasing will not need to allocate
- additional memory.
-</LI>
-<LI>Additional memory is allocated efficiently on demand when new
- elements are added (doubling the capacity every time it is
- increased). This property comes from STL vector.
-</LI>
-</UL>
-
-<P>
-Note that this representation is similar to that used in Liu's
-implementation, with some important differences due to dynamic memory
-allocation. With the dynamic memory allocation we do not need to
-over-write portions of the graph that have been eliminated,
-allowing for a more efficient graph traversal. More importantly,
-information about the elimination graph is preserved allowing for
-trivial symbolic factorization. Since symbolic factorization can be
-an expensive part of the entire solution process, improving its
-performance can result in significant computational savings.
-
-<P>
-The overhead of dynamic memory allocation could conceivably compromise
-performance in some cases. However, in practice, memory allocation
-overhead does not contribute significantly to run-time for our
-implementation as shown in [] because it is not
-done very often and the cost gets amortized.
-
-<P>
-
-<H2>Proper Self-Avoiding Walk</H2>
-
-<P>
-The finite element method (FEM) is a flexible and attractive numerical
-approach for solving partial differential equations since it is
-straightforward to handle geometrically complicated domains. However,
-unstructured meshes generated by FEM does not provide an obvious
-labeling (numbering) of the unknowns while it is vital to have it for
-matrix-vector notation of the underlying algebraic equations. Special
-numbering techniques have been developed to optimize memory usage and
-locality of such algorithms. One novel technique is the self-avoiding
-walk [].
-
-<P>
-If we think a mesh is a graph, a self-avoiding walk(SAW) over an
-arbitrary unstructured two-dimensional mesh is an enumeration of all
-the triangles of the mesh such that two successive triangles shares an
-edge or a vertex. A proper SAW is a SAW where jumping twice over the
-same vertex is forbidden for three consecutive triangles in the walk.
-it can be used to improve parallel efficiency of several irregular
-algorithms, in particular issues related to reducing runtime memory
-access (improving locality) and interprocess communications. The
-reference [] has proved the existence
-of A PSAW for any arbitrary triangular mesh by extending an existing
-PSAW over a small piece of mesh to a larger part. The proof
-effectively provides a set of rules to construct a PSAW.
-
-<P>
-The algorithm family of constructing a PSAW on a mesh is to start from
-any random triangle of the mesh, choose new triangles sharing an edge
-with the current sub-mesh and extend the existing partial PSAW over
-the new triangles.
-
-<P>
-Let us define a dual graph of a mesh. Let a triangle in the mesh be a
-vertex and two triangles sharing an edge in the mesh means there is an
-edge between two vertices in the dual graph. By using a dual graph of
-a mesh, one way to implement the algorithm family of constructing a
-PSAW is to reuse BGL algorithms such as BFS and DFS with a customized
-visitor to provide operations during
-traversal. The customized visitor has the function <TT>tree_edge()</TT>
-which is to extend partial PSAW in case by case and function
-<TT>start_vertex()</TT> which is to set up the PSAW for the starting
vertex.
-
-<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>
+</li>
+</ul>
+</li>
+</ol>得到的顺序是由该算法选出的一个顶点序列 <i>{v<sup>0</sup>,
+v<sup>1</sup>,...}</i>。
+
+<p>这类算法的一个最重要的例子是
+<i>最小度数</i> 算法。该算法在每一步选出对应图中具有最小度数的顶点，作为
<i>v<sup>k</sup></i>。目前已开发出基本最小度数算法的多个增强版，如使用商数图
表示法、大规模消去法、不完整度数更新、多道消去法和外部度。有关最小度数算法的
发展历史，请参见 [<a
href="bibliography.html#George:evolution">35</a>]。
+
+</p><p>最小度数算法的BGL实现与[<a
href="bibliography.html#LIU:MMD">21</a>]中描述的算法非常相近。目前的实现包括
了大规模消去、不完整度数更新、多道消去和外部度。
+
+</p><p>特别是，我们创建一个图表示法，来提高该算法的性能。它基于模板化
的"vector of
+vectors"。所用的vector容器是一个适配器类，它构建于 STL
<tt>std::vector</tt> 类之上。这个适配器类的具体特点包括：
+
+</p><ul>
+<li>元素删除不会缩减相关内存。在删除后加入新的元素不需要分配额外内存。
+</li>
+<li>在加入新元素时，按需高效地分配额外内存(每次增加内存时将容量番翻)。该特
性来自于 STL vector。
+</li>
+</ul>
+
+<p>注意，这种表示法类似于在Liu的
+实现中所使用的方法，但有一些在动态内存分配上的重要差异。有了动态内存分
配，我们就不需要为图的已消去部分过份关注，从而可以更高效地进行图遍历。更重
+要的是，保留了关于消去图的信息，允许小的符号分解。因为符号分解是整个解答过
程中代价较高的部分，提高其性能可以显著减少计算量。
+</p><p>在某些情形下，可以把动态内存分配的开销想象为性能折衷。不过在实践
中，内存分配的开销对于我们的实现并不占主要的运行时间，因为它并不是经常运
行，成本得到了分摊。
+
+</p><h2>Proper Self-Avoiding Walk 正确的自回避行走</h2>
+
+<p>有限元法(FEM)是求解偏微分方程的一种灵活且具有吸引力的方法，因为它直接明
了地处理复杂的几何领域。但是，FEM所生成的非结构化网格不能提
+供未知物的一个明确标记(编号)，而对于基本代数方程的矩阵矢量符号来说，有明确
标记是很重要的。已开发出特殊的编号技术以优化这类算法的内存使用和局部
+性。一种新型的技术就是自回避行走[]。
+</p><p>如果我们把网格想象为图，那么在任意一个非结构化二维网格上的自回避行走
(SAW)就是这个网格的所有三角形的一个枚举，满足两个相连的
+三角形共享一条边或一个顶点。一个正确的SAW是这样一个SAW，对于行走中的三个连
续三角形，不能跳过同一个顶点两次。它可以被用于改进几个非常规算法
+的并行效率，尤其是与降低运行期内存访问(提高局部性)以及进程间通信相关的问
题。参考资料[]已证明，对于任意三角形网格都存在一个PSAW，通过对一
+小片网格的PSAW进行扩展，可以得到更大的部分。该证明还有效地提供了一套规则来
构造一个 PSAW。
+</p><p>在网格上构造PSAW的算法族是从网格中任一随机三角形开始，选择一个与当前
子网格共享一条边的新三角形，并以这个新三角形扩展已有的部分PSAW。
+
+</p><p>我们来定义一个网格的偶图。令网格中每个三角形作为顶点，网格中有共享边
的两个三角形表示在偶图中的两个对应顶点间有一条边。通过使用网格
+的偶图，实现构造PSAW的算法族的一个方法就是，重用BFS和DFS这样的BGL算法，给定
一个定制的遍历器以提供遍历期间的操作。定制的遍历器应带有
+函数 <tt>tree_edge()</tt>，用于按具体情况扩展部分PSAW，还有函数
+<tt>start_vertex()</tt>，用于为开始顶点设置PSAW。<br>
+</p><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright © 2000-2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,
Indiana University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
-</BODY>
-</HTML>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/graph/doc/using_adjacency_list.html
==============================================================================
--- trunk/libs/graph/doc/using_adjacency_list.html (original)
+++ trunk/libs/graph/doc/using_adjacency_list.html Thu Jul 2 20:26:08 2009
@@ -1,788 +1,248 @@
-<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>Using the Boost Graph Library</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="SECTION00830000000000000000"></A>
-<A NAME="sec:using-adjacency-list"></A>
-<BR>
-Using <TT>adjacency_list</TT>
-</H1>
-
-This section describes the details of how use the
-<tt>adjacency_list</tt> class. The presentation is divided into the
-following topics:
-
-<OL>
-<li><A href="#sec:choosing-graph-type">Choosing the <TT>Edgelist</TT> and
<TT>VertexList</TT></A>
-<li><a href="#sec:directed-and-undirected">Directed and Undirected
-Adjacency Lists</a>
-<li><A href="#sec:adjacency-list-properties">Internal Properties</A>
-<li><A href="#sec:custom-storage">Customizing the Adjacency List
Storage</A>
-</ol>
-
-<P>
-
-<H2><A NAME="SECTION00831000000000000000"></A>
-<A NAME="sec:choosing-graph-type"></A>
-<BR>
-Choosing the <TT>Edgelist</TT> and <TT>VertexList</TT>
-</H2>
-
-<P>
-This section focuses on how to decide which version of the <a
-href="./adjacency_list.html"><TT>adjacency_list</TT></a> class to use
-in different situations. The <TT>adjacency_list</TT> is like a
-swiss-army knife in that it can be configured in many ways. The
-parameters that we will focus on in this section are <TT>OutEdgeList</TT>
-and <TT>VertexList</TT>, which control the underlying data structures
-that will be used to represent the graph. The choice of
-<TT>OutEdgeList</TT> and <TT>VertexList</TT> affects the time complexity
-of many of the graph operations and the space complexity of the graph
-object.
-
-<P>
-BGL uses containers from the STL such as
-<a href="http://www.sgi.com/tech/stl/Vector.html";><TT>std::vector</TT></a>,
-<a href="http://www.sgi.com/tech/stl/List.html";><TT>std::list</TT></a>,
-and <a href="http://www.sgi.com/tech/stl/set.html";><TT>std::set</TT></a>
-to represent the set of vertices and the adjacency structure
-(out-edges and in-edges) of the graph. There are several selector
-types that are used to specify the choice of container for
-<TT>OutEdgeList</TT> and <TT>VertexList</TT>.
-
-<P>
-
-<UL>
-<LI><TT>vecS</TT> selects <TT>std::vector</TT>.</LI>
-<LI><TT>listS</TT> selects <TT>std::list</TT>.</LI>
-<LI><TT>slistS</TT> selects <TT>std::slist</TT>.</LI>
-<LI><TT>setS</TT> selects <TT>std::set</TT>.</LI>
-<LI><TT>multisetS</TT> selects <TT>std::multiset</TT>.</LI>
-<LI><TT>hash_setS</TT> selects <TT>std::hash_set</TT>.</LI>
-</UL>
-
-<P>
-
-<H3>Choosing the <TT>VertexList</TT> type</A></H3>
-
-<P>
-The <TT>VertexList</TT> parameter determines what kind of container
-will be used to represent the vertex set, or two-dimensional structure
-of the graph. The container must model <a
-href="http://www.sgi.com/tech/stl/Sequence.html";>Sequence</a> or
-<a
-href="http://www.sgi.com/tech/stl/RandomAccessContainer.html";>RandomAccessContainer</a>.
In
-general, <TT>listS</TT> is a good choice if you need to add and remove
-vertices quickly. The price for this is extra space overhead compared
-to choosing <TT>vecS</TT>.
-
-<P>
-
-<H4>Space Complexity</H4>
-
-<P>
-The <TT>std::list</TT> has a higher per-vertex space overhead than the
-<TT>std::vector</TT>, storing three extra pointers per vertex.
-
-<P>
-
-<H4>Time Complexity</H4>
-
-<P>
-The choice of <TT>VertexList</TT> affects the time complexity of the
-following operations.
+<title>Using the Boost Graph Library</title></head>
+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"
vlink="#551a8b">
+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
-<ul>
+<br clear="">
-<li>
-<pre>
-add_vertex()
-</PRE>
-This operation is amortized constant time for both <TT>vecS</TT> and
-<TT>listS</TT> (implemented with <TT>push_back()</TT>). However, when
-the <TT>VertexList</TT> type is <TT>vecS</TT> the time for this
-operation is occasionally large because the vector will be
-reallocated and the whole graph copied.
-<P></p>
+<h1><a name="SECTION00830000000000000000"></a>
+<a name="sec:using-adjacency-list"></a>
+<br>
+Using <tt>adjacency_list 使用 adjacency_list</tt>
+</h1>本节详细介绍如何使用
+<tt>adjacency_list</tt> 类。讲解分为以下主题：
+
+<ol>
+<li><a href="#sec:choosing-graph-type">选用 <tt>Edgelist</tt> 和
<tt>VertexList</tt></a>
+</li><li><a href="#sec:directed-and-undirected">有向和无向的邻接列表</a>
+</li><li><a href="#sec:adjacency-list-properties">内部属性</a>
+</li><li><a href="#sec:custom-storage">定制邻接列表的存储</a>
+</li></ol>
-<li>
-<PRE>
-remove_vertex()
-</PRE>
-This operation is constant time for <TT>listS</TT> and <i>O(V + E)</i> for
-<TT>vecS</TT>. The large time complexity for <TT>vecS</TT> is because
-the vertex descriptors (which in this case are indices that correspond
-to the vertices' place in the vertex list) must be adjusted in the
-out-edges for the whole graph.
-<P></P>
+<h2><a name="SECTION00831000000000000000"></a>
+<a name="sec:choosing-graph-type"></a>
+<br>
+Choosing the <tt>Edgelist</tt> and <tt>VertexList 选用 Edgelist 和
VertexList</tt>
+</h2>
-<li>
-<PRE>
-vertex()
-</PRE>
-This operation is constant time for <TT>vecS</TT> and for
-<TT>listS</TT>.
+<p>本节专注于在不同的情形下如何决定使用哪一个版本的 <a
href="./adjacency_list.html"><tt>adjacency_list</tt></a> 类。
<tt>adjacency_list</tt> 就象一把瑞士军刀，它可以按多种方式来配置。在本节中我
们所关注的参数是 <tt>OutEdgeList</tt> 和 <tt>VertexList</tt>，它们控制了用来
表示一个图的底层数据结构。选择
+<tt>OutEdgeList</tt> 或 <tt>VertexList</tt> 会影响到许多图操作的时间复杂度
和图对象的空间复杂度。
+</p><p>
+BGL使用来自于STL的容器，如
+<a href="http://www.sgi.com/tech/stl/Vector.html";><tt>std::vector</tt></a>,
+<a href="http://www.sgi.com/tech/stl/List.html";><tt>std::list</tt></a>, 和
<a href="http://www.sgi.com/tech/stl/set.html";><tt>std::set</tt></a>
+来表示顶点集以及图的邻接结构(出边和入边)。有几个选择符类型用来指定对
+<tt>OutEdgeList</tt> 和 <tt>VertexList</tt> 容器的选择。</p><ul>
+<li><tt>vecS</tt> 选用 <tt>std::vector</tt>.</li>
+<li><tt>listS</tt> 选用 <tt>std::list</tt>.</li>
+<li><tt>slistS</tt> 选用 <tt>std::slist</tt>.</li>
+<li><tt>setS</tt> 选用 <tt>std::set</tt>.</li>
+<li><tt>multisetS</tt> 选用 <tt>std::multiset</tt>.</li>
+<li><tt>hash_setS</tt> 选用 <tt>std::hash_set</tt>.</li>
</ul>
-
-<P>
+<h3>选择 <tt>VertexList</tt> 类型</h3>
-<H3><A NAME="SECTION00831200000000000000">
-Choosing the <TT>OutEdgeList</TT> type</A>
-</H3>
-
-<P>
-The <TT>OutEdgeList</TT> parameter determines what kind of container will
-be used to store the out-edges (and possibly in-edges) for each vertex
-in the graph. The containers used for edge lists must either satisfy
-the requirements for <a
-href="http://www.sgi.com/tech/stl/Sequence.html";>Sequence</a> or for
-<a
-href="http://www.sgi.com/tech/stl/AssociativeContainer.html";>AssociativeContainer</a>.
-
-<P>
-One of the first things to consider when choosing the
-<TT>OutEdgeList</TT> is whether you want <TT>adjacency_list</TT> to
-enforce the absence of parallel edges in the graph (that is, enforce
-that the graph not become a multi-graph). If you want this enforced
-then use the <TT>setS</TT> or <TT>hash_setS</TT> selectors. If you
-want to represent a multi-graph, or know that you will not be
-inserting parallel edges into the graph, then choose one of the <a
-href="http://www.sgi.com/tech/stl/Sequence.html";>Sequence</a>
-types: <TT>vecS</TT>, <TT>listS</TT>, or <TT>slistS</TT>.
-You will also want to take into account the differences in time and space
-complexity for the various graph operations. Below we use <i>V</i> for
-the total number of vertices in the graph and <i>E</i> for the total
-number of edges. Operations not discussed here are constant time.
-
-<P>
-
-<H4>Space Complexity</H4>
-
-<P>
-The selection of the <TT>OutEdgeList</TT> affects the amount of space
-overhead per edge in the graph object. In the order of least space to
-most space, the selectors are <TT>vecS</TT>, <TT>slistS</TT>,
-<TT>listS</TT>, and <TT>setS</TT>.
-
-<P>
-
-<H4>Time Complexity</H4>
-
-<P>
-In the following description of the time complexity for various
-operations, we use <i>E/V</i> inside of the ``big-O'' notation to
-express the length of an out-edge list. Strictly speaking this is not
-accurate because <i>E/V</i> merely gives the average number of edges
-per vertex in a random graph. The worst-case number of out-edges for a
-vertex is <i>V</i> (unless it is a multi-graph). For sparse graphs
-<i>E/V</i> is typically much smaller than <i>V</i> and can be
-considered a constant.
+<p>参数 <tt>VertexList</tt> 决定选择哪一种容器表示顶点集或图的二维结
构。这个容器必须符合 <a href="http://www.sgi.com/tech/stl/Sequence.html";>序
列Sequence</a> 或
+<a href="http://www.sgi.com/tech/stl/RandomAccessContainer.html";>随机访问容
器RandomAccessContainer</a>。通常，<tt>listS</tt> 是一个不错的选择，如果你需
要快速地增加或移除顶点。其代价是，与选用 <tt>vecS</tt> 相比，需要额外的空间
开销。
-<P>
-
-<P> <P>
-<UL>
-<LI>
-<PRE>
-add_edge()
-</PRE>
-When the <TT>OutEdgeList</TT> is a <a
-href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html";>UniqueAssociativeContainer</a>
-like <TT>std::set</TT> the absence of parallel edges is enforced when
-an edge is added. The extra lookup involved has time complexity
-<i>O(log(E/V))</i>. The <TT>OutEdgeList</TT> types that model <a
-href="http://www.sgi.com/tech/stl/Sequence.html";>Sequence</a> do
-not perform this check and therefore <TT>add_edge()</TT> is amortized
-constant time. This means that it if you don't care whether the graph
-has parallel edges, or know that the input to the graph does not
-contain them, then it is better to use the sequence-based
-<TT>OutEdgeList</TT>. The <TT>add_edge()</TT> for the sequence-based
-<TT>OutEdgeList</TT> is implemented with <TT>push_front()</TT> or
-<TT>push_back()</TT>. However, for <TT>std::list</TT> and
-<TT>std::slist</TT> this operation will typically be faster than with
-<TT>std::vector</TT> which occasionally reallocates and copies all
-elements.
-<p></p>
+</p><h4>空间复杂度</h4>
-<li>
-<PRE>
-remove_edge()
-</PRE>
-For sequence-based <TT>OutEdgeList</TT> types this operation is
-implemented with <TT>std::remove_if()</TT> which means the average
-time is <i>E/V</i>. For set-based <TT>OutEdgeList</TT> types this is
-implemented with the <TT>erase()</TT> member function, which has
-average time <i>log(E/V)</i>.
-<p></p>
+<p>
+<tt>std::list</tt> 具有比
+<tt>std::vector</tt> 更高的每顶点空间开销，对于每个顶点，它要保存三个额外的
指针。
-<li>
-<PRE>
-edge()
-</PRE>
-The time complexity for this operation is <i>O(E/V)</i> when the
-<TT>OutEdgeList</TT> type is a <a
-href="http://www.sgi.com/tech/stl/Sequence.html";>Sequence</a> and it
-is <i>O(log(E/V))</i> when the <TT>OutEdgeList</TT> type is an <a
-href="http://www.sgi.com/tech/stl/AssociativeContainer.html";>AssociativeContainer</a>.
-<p></p>
+</p><h4>时间复杂度</h4>
-<li>
-<PRE>
-clear_vertex()
-</PRE>
-For directed graphs with sequence-based <TT>OutEdgeList</TT> types the time
-complexity is <i>O(V + E)</i>, while for associative container based
-<TT>OutEdgeList</TT> types the operation is faster, with time complexity
-<i>O(V log(E/V))</i>. For undirected graphs this operation is
-<i>O(E<sup>2</sup>/V<sup>2</sup>)</i> or <i>O(E/V log(E/V))</i>.
-<p></p>
+<p><tt>VertexList</tt> 的选择会影响以下操作的时间复杂度。
-<li>
-<PRE>
-remove_vertex()
-</PRE>
-The time complexity for this operation is <i>O(V + E)</i> regardless of the
-<TT>OutEdgeList</TT> type.
-<p></p>
+</p><ul>
<li>
-<PRE>
-out_edge_iterator::operator++()
-</PRE>
-This operation is constant time for all the <TT>OneD</TT> types.
-However, there is a significant constant factor time difference
-between the various types, which is important since this operation is
-the work-horse of most graph algorithms. The speed of
-this operation in order of fastest to slowest is
-<TT>vecS</TT>, <TT>slistS</TT>, <TT>listS</TT>, <TT>setS</TT>,
-<TT>hash_setS</TT>.
-<p></p>
+<pre>add_vertex()<br></pre>对于 <tt>vecS</tt> 和
+<tt>listS</tt>，该操作是分期常量时间复杂度(用<tt>push_back()</tt>实现)。但
是，如果 <tt>VertexList</tt> 类型为 <tt>vecS</tt>，则该操作的时间偶尔会变
大，因为vector可能会被重新分配且整个图被复制。
-<li>
-<PRE>
-in_edge_iterator::operator++()
-</PRE>
-This operation is constant time and exhibits a similar speed
-ordering as the <TT>out_edge_iterator</TT> with respect to
-the <TT>OutEdgeList</TT> selection.
-<p></p>
+</li><li>
+<pre>remove_vertex()<br></pre>对于 <tt>listS</tt>，该操作是常量时间，对于
<tt>vecS</tt>，则是 <i>O(V + E)</i>。对于 <tt>vecS</tt> 有较大的时间复杂度是
因为必须对整个图的顶点描述符(这种情况下它们是对应于顶点列表中的顶点的索引)调
整出边。
-<li>
-<PRE>
-vertex_iterator::operator++()
-</PRE>
-This operation is constant time and fast (same speed as incrementing a
-pointer). The selection of <TT>OneD</TT> does not affect the speed of
-this operation.
-<p></p>
+</li><li>
+<pre>vertex()<br></pre>对于 <tt>vecS</tt> 和
+<tt>listS</tt>，该操作是常量时间。</li></ul>
-<li>
-<PRE>
-edge_iterator::operator++()
-</PRE>
-This operation is constant time and exhibits a similar speed ordering
-as the <TT>out_edge_iterator</TT> with respect to the <TT>OutEdgeList</TT>
-selection. Traversing through the whole edge set is <i>O(V + E)</i>.
-<p></p>
+
+<h3><a name="SECTION00831200000000000000">
+选择 <tt>OutEdgeList</tt> 类型</a>
+</h3>
+
+<p>参数 <tt>OutEdgeList</tt> 决定对于图中每个顶点，使用哪一种容器来保存其出
边(也可能是入边)。用于边列表的容器必须符合 <a
href="http://www.sgi.com/tech/stl/Sequence.html";>序列Sequence</a> 或
+<a href="http://www.sgi.com/tech/stl/AssociativeContainer.html";>关联容器
AssociativeContainer</a> 的要求。
+
+</p><p>选择
+<tt>OutEdgeList</tt> 时要考虑的第一件事情是，你是否希望
<tt>adjacency_list</tt> 强制在图中不会出现平行边(即，强制该图不会变为复图
multi-graph)。如果你希望如此，则使用 <tt>setS</tt> 或 <tt>hash_setS</tt> 选
择符。如果你想表示一个复图，或者你知道不会往图中插入平行边，则选择以下 <a
href="http://www.sgi.com/tech/stl/Sequence.html";>序列Sequence</a>
+类型之一：<tt>vecS</tt>, <tt>listS</tt>, 或 <tt>slistS</tt>。你还要考虑不同
的图操作的时间复杂度和空间复杂度。下面，我们用 <i>V</i> 表示图中的顶点数
量，用 <i>E</i> 表示边的数量。这里没有列出的操作都是常量时间的。</p><h4>空间
复杂度</h4>
+<p>对 <tt>OutEdgeList</tt> 的选择会影响在图对象中每条边的空间开销。按最小空
间到最大空间的顺序，相应的选择符依次为 <tt>vecS</tt>, <tt>slistS</tt>,
+<tt>listS</tt>, 和 <tt>setS</tt>.</p><h4>时间复杂度</h4>
+
+<p>在以下对于不同操作的时间复杂度的描述中，我们用含有 <i>E/V</i> 的"大O"表
示法来表示一个出边列表的长度。严格来说，这是不准确的，因为 <i>E/V</i> 只是一
个随机图中每个顶点的平均边数。最坏情况下，一个顶点的出边数是 <i>V</i> (除非
它是一个复图)。对于稀疏图来说，<i>E/V</i> 通常远小于 <i>V</i> 且可以被视为常
数。</p><ul>
<li>
-<PRE>
-adjacency_iterator::operator++()
-</PRE>
-This operation is constant time and exhibits a similar speed
-ordering as the <TT>out_edge_iterator</TT> with respect to
-the <TT>OutEdgeList</TT> selection.
-<p></p>
+<pre>add_edge()<br></pre>如果 <tt>OutEdgeList</tt> 是一个<a
href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html";>唯一关联
式容器UniqueAssociativeContainer</a>，如 <tt>std::set</tt>，则在增加边时会阻
止平行边的加入。这个额外的查找具有
+<i>O(log(E/V))</i> 的时间复杂度。而模仿 <a
href="http://www.sgi.com/tech/stl/Sequence.html";>序列Sequence</a> 的
<tt>OutEdgeList</tt> 类型则不会执行这样的检查，因此其 <tt>add_edge()</tt> 是
分期常数时间的。这意味着如果你不关心图是否有平行边，或者你知道图的输入不会包
含平行边，则最好选择基于序列的
+<tt>OutEdgeList</tt>。基于序列的
+<tt>OutEdgeList</tt> 的 <tt>add_edge()</tt> 是以 <tt>push_front()</tt> 或
+<tt>push_back()</tt> 实现的。不过，对于 <tt>std::list</tt> 和
+<tt>std::slist</tt>，该操作通常快于
+<tt>std::vector</tt>，因为后者偶尔会需要重新分配并复制所有元素。
-</ul>
+</li><li>
+<pre>remove_edge()<br></pre>对于基于序列的 <tt>OutEdgeList</tt> 类型，该操
作是以 <tt>std::remove_if()</tt> 实现的，这意味着平均时间为 <i>E/V</i>。而对
于基于集合的 <tt>OutEdgeList</tt> 类型，该操作是以 <tt>erase()</tt> 成员函数
实现的，其平均时间为 <i>log(E/V)</i>。
-<P>
-
-<P>
+</li><li>
+<pre>edge()<br></pre>如果
+<tt>OutEdgeList</tt> 类型是一个<a
href="http://www.sgi.com/tech/stl/Sequence.html";>序列Sequence</a>，该操作的
时间复杂度为 <i>O(E/V)</i>，如果 <tt>OutEdgeList</tt> 类型是一个<a
href="http://www.sgi.com/tech/stl/AssociativeContainer.html";>关联式容器
AssociativeContainer</a>，则为 <i>O(log(E/V))</i>。
-<H2><a name="sec:directed-and-undirected">Directed and Undirected
Adjacency Lists</H2>
+</li><li>
+<pre>clear_vertex()<br></pre>对于带有基于序列的 <tt>OutEdgeList</tt> 类型的
有向图，时间复杂度为 <i>O(V + E)</i>，而对于基于关联式容器的
+<tt>OutEdgeList</tt> 类型，该操作会快些，其时间复杂度为
+<i>O(V log(E/V))</i>。对于无向图来说，该操作的时间复杂度为
+<i>O(E<sup>2</sup>/V<sup>2</sup>)</i> 或 <i>O(E/V log(E/V))</i>。
-<P>
-The <TT>adjacency_list</TT> class can be used to represent both
-directed and undirected graphs, depending on the argument passed to
-the <TT>Directed</TT> template parameter. Selecting <TT>directedS</TT>
-or <TT>bidirectionalS</TT> choose a directed graph, whereas
-<TT>undirectedS</TT> selects the representation for an undirected
-graph. See Section <A
-HREF="graph_concepts.html#sec:undirected-graphs">Undirected Graphs</A>
-for a description of the difference between directed and undirected
-graphs in BGL. The <TT>bidirectealS</TT> selector specifies that the
-graph will provide the <TT>in_edges()</TT> function as well as the
-<TT>out_edges()</TT> function. This imposes twice as much space
-overhead per edge, which is why <TT>in_edges()</TT> is optional.
-
-<P>
-
-<H2><A NAME="sec:adjacency-list-properties"></A>
-Internal Properties
-</H2>
-
-<P>
-Properties can be attached to the vertices or edges of an
-<TT>adjacency_list</TT> graph via the property interface. The template
-parameters <TT>VertexProperty</TT> and <TT>EdgeProperty</TT> of the
-<TT>adjacency_list</TT> class are meant to be filled by these interior
- properties.
-
-<p><b>NOTE</b>: The Boost Graph Library supports two interchangeable
methods for
-specifying interior properties: <a href="bundles.html">bundled
properties</a>
-and property lists. The former is easier to use and requires less effort,
-whereas the latter is compatible with older, broken compilers and is
-backward-compatible with Boost versions prior to 1.32.0. If you absolutely
-require these compatibility features, read on to learn about property
lists.
-Otherwise, we strongly suggest that you read about the <a
href="bundles.html">bundled
-properties</a> mechanism.
-
-<p>One may specify internal properties via property lists, which are build
from instances of the
-property class declared as follows.
-
-<P>
-<PRE>
-template <class PropertyTag, class T, class NextProperty =
no_property>
-struct property;
-</PRE>
-
-<P>
-The <a href="./PropertyTag.html"><TT>PropertyTag</TT></a> template
-parameter is a tag class that simply identifies or gives a unique name
-to the property. There are several predefined tags, and it is easy to
-add more.
-
-<P>
-<PRE>
- struct vertex_index_t { };
- struct vertex_index1_t { };
- struct vertex_index2_t { };
- struct edge_index_t { };
- struct graph_name_t { };
- struct vertex_name_t { };
- struct edge_name_t { };
- struct edge_weight_t { };
- struct edge_weight2_t { };
- struct edge_capacity_t { };
- struct edge_residual_capacity_t { };
- struct edge_reverse_t { };
- struct vertex_distance_t { };
- struct vertex_root_t { };
- struct vertex_all_t { };
- struct edge_all_t { };
- struct graph_all_t { };
- struct vertex_color_t { };
- struct vertex_rank_t { };
- struct vertex_predecessor_t { };
- struct vertex_isomorphism_t { };
- struct vertex_invariant_t { };
- struct vertex_invariant1_t { };
- struct vertex_invariant2_t { };
- struct vertex_degree_t { };
- struct vertex_out_degree_t { };
- struct vertex_in_degree_t { };
- struct vertex_discover_time_t { };
- struct vertex_finish_time_t { };
-</PRE>
-
-<P>
-The <b><TT>T</TT></b> template parameter of <TT>property</TT>
-specifies the type of the property values. The type <tt>T</tt> must be
-<a
-href="http://www.sgi.com/tech/stl/DefaultConstructible.html";>Default
-Constructible</a>, <a
-href="../../utility/Assignable.html">Assignable</a>, and <a
-href="../../utility/CopyConstructible.html">Copy Constructible</a>.
-Like the containers of the C++ Standard Library, the property objects
-of type <tt>T</tt> are held by-value inside of the graph.
+</li><li>
+<pre>remove_vertex()<br></pre>该操作的时间复杂度为 <i>O(V + E)</i>，无论采
用何种
+<tt>OutEdgeList</tt> 类型。
+
+</li><li>
+<pre>out_edge_iterator::operator++()<br></pre>对于所有 <tt>OneD</tt> 类
型，该操作都是常量时间。不过，对于不同的类型，其常量因子有显著的差异，这是很
重要的，因为这个操作是大多数图算法的主要操作。该操作的速度按从快到慢的顺序排
列，依次为
+<tt>vecS</tt>, <tt>slistS</tt>, <tt>listS</tt>, <tt>setS</tt>,
+<tt>hash_setS</tt>.
+
+</li><li>
+<pre>in_edge_iterator::operator++()<br></pre>该操作为常量时间，依照
<tt>OutEdgeList</tt> 的不同选择，其速度的顺序与 <tt>out_edge_iterator</tt>
类似。
+
+</li><li>
+<pre>vertex_iterator::operator++()<br></pre>该操作为常量时间，且非常快(和递
增一个指针的速度相同)。<tt>OneD</tt> 的选择不影响该操作的速度。
+
+</li><li>
+<pre>edge_iterator::operator++()<br></pre>该操作为常量时间，依照
<tt>OutEdgeList</tt> 的不同选择，其速度的顺序与 <tt>out_edge_iterator</tt>
类似。遍历整个边集的时间复杂度为 <i>O(V + E)</i>.
+
+</li><li>
+<pre>adjacency_iterator::operator++()<br></pre>该操作为常量时间，依照
<tt>OutEdgeList</tt> 的不同选择，其速度的顺序与 <tt>out_edge_iterator</tt>
类似。</li></ul>
+
+<h2><a name="sec:directed-and-undirected">Directed and Undirected
Adjacency Lists 有向的和无向的邻接列表</a></h2>
<p>
-The <b><TT>NextProperty</TT></b> parameter allows <TT>property</TT>
-types to be nested, so that an arbitrary number of properties can be
-attached to the same graph.
-
-<P>
-The following code shows how a vertex and edge property type can be
-assembled and used to create a graph type. We have attached a distance
-property with values of type <TT>float</TT> and a name property with
-values of type <TT>std::string</TT> to the vertices of the graph. We
-have attached a weight property with values of type <TT>float</TT> to
-the edges of the graph.
-
-<P>
-<PRE>
- typedef property<vertex_distance_t, float,
- property<vertex_name_t, std::string> > VertexProperty;
- typedef property<edge_weight_t, float> EdgeProperty;
-
- typedef adjacency_list<mapS, vecS, undirectedS,
- VertexProperty, EdgeProperty> Graph;
-
- Graph g(num_vertices); // construct a graph object
-</PRE>
-
-<P>
-The property values are then read from and written to using property
-maps. See Section <A
HREF="using_property_maps.html#sec:interior-properties">Interior
-Properties</A> for a description of how to obtain property maps
-from a graph, and read Section <A
-HREF="./using_property_maps.html">Property Maps</A> for how
-to use property maps.
-
-<P>
-
-<H3><A NAME="sec:custom-edge-properties"></A>
-Custom Edge Properties
-</H3>
-
-<P>
-Creating your own property types and properties is easy; just define
-a tag class for your new property. The property tag class will need to
-define <tt>num</tt> with a unique integer ID, and <tt>kind</tt> which
-should be either <tt>edge_property_tag</tt>,
-<tt>vertex_property_tag</tt>, or <tt>graph_property_tag</tt>.
-
-<P>
-<PRE>
-struct flow_t {
- typedef edge_property_tag kind;
-};
-
-struct capacity_t {
- typedef edge_property_tag kind;
-};
-</PRE>
+<a name="sec:directed-and-undirected"><tt>adjacency_list</tt> 类可用于表示
有向图或无向图，这取决于传给 <tt>Directed</tt> 模板参数的实参。选择
<tt>directedS</tt> 或 <tt>bidirectionalS</tt> 则为有向图，而
+<tt>undirectedS</tt> 则表示为无向图。有关BGL中无向图与有向图之间差异的描
述，请见 </a><a href="graph_concepts.html#sec:undirected-graphs">无向图
Undirected Graphs</a>
+一节。<tt>bidirectealS</tt> 选择符指定，该图同时提供 <tt>in_edges()</tt> 函
数和 <tt>out_edges()</tt> 函数。这使得每条边要占用两倍的空间，这正是为什么
<tt>in_edges()</tt> 是可选项的原因。</p><h2><a
name="sec:adjacency-list-properties"></a>
+Internal Properties 内部属性
+</h2>
+
+<p>通常属性接口，可以将属性附着到一个
+<tt>adjacency_list</tt> 图的顶点或边上。<tt>adjacency_list</tt> 类的模板参
数 <tt>VertexProperty</tt> 和 <tt>EdgeProperty</tt> 正是为了填写这些内部属
性。
+
+</p><p><b>备注：</b>BGL支持两种可互换的方法，以指定内部属性：<a
href="bundles.html">绑定属性bundled properties</a>
+和属性列表。前者更易使用且要求较少动作，后者则兼容于较老的、不符合标准的编
译器，并且后向兼容于1.32.0以前的Boost版本。如果你绝对要求兼容性，则继续往下
学习属性列表。否则，我们强烈建议你学习 <a href="bundles.html">绑定属性
bundled
+properties</a> 机制。
+
+</p><p>你可以通过属性列表来指定内部属性，属性列表是从如下定义的
+property 类的实例构建而来的。</p><pre>template <class PropertyTag,
class T, class NextProperty = no_property><br>struct property;<br></pre>
<p>
-You can also use enum's instead of struct's to create tag types.
-Create an enum type for each property. The first part of the name of
-the enum type must be <tt>edge</tt>, <tt>vertex</tt>, or
-<tt>graph</tt> followed by an underscore, the new property name, and
-a <tt>_t</tt> at the
-end. Inside the enum, define a value with the same name minus the
-<tt>_t</tt>. Then invoke the <tt>BOOST_INSTALL_PROPERTY</tt> macro.
-
-<pre>
-enum edge_flow_t { edge_flow };
-enum edge_capacity_t { edge_capacity };
-
-namespace boost {
- BOOST_INSTALL_PROPERTY(edge, flow);
- BOOST_INSTALL_PROPERTY(edge, capacity);
-}
-</pre>
-
-<P>
-Now you can use your new property tag in the definition of properties
-just as you would one of the builtin tags.
-
-<P>
-<PRE>
- typedef property<capacity_t, int> Cap;
- typedef property<flow_t, int, Cap> EdgeProperty;
- typedef adjacency_list<vecS, vecS, no_property, EdgeProperty>
Graph;
-</PRE>
-
-<P>
-Just as before, the property maps for these properties can be
-obtained from the graph via the
-<TT>get(Property, g)</TT> function.
-
-<P>
-<PRE>
- property_map<Graph, capacity_t>::type capacity
- = get(capacity_t(), G);
- property_map<Graph, flow_t>::type flow
- = get(flow_t(), G);
-</PRE>
-
-<P>
-The file <TT>edge_property.cpp</TT> shows the complete source
-code for this example.
-
-<P>
-
-<H3><A NAME="SECTION00833200000000000000"></A>
-<A NAME="sec:custom-vertex-properties"></A>
-<BR>
-Custom Vertex Properties
-</H3>
-
-<P>
-Creating your own properties to attach to vertices is just as easy as
-for edges. Here we want to attach people's first names to the vertices
-in the graph.
-
-<P>
-<PRE>
- struct first_name_t {
- typedef vertex_property_tag kind;
- };
-</PRE>
-
-<P>
-Now we can use the new tag in the <TT>property</TT> class and use that in
-the assembly of a graph type. The following code shows creating the
-graph type, and then creating the graph object. We fill in the edges
-and also assign names to the vertices. The edges will represent ``who
-owes who''.
-
-<P>
-<PRE>
- typedef property<first_name_t, std::string> FirstNameProperty;
- typedef adjacency_list<vecS, vecS, directedS,
- FirstNameProperty> MyGraphType;
-
- typedef pair<int,int> Pair;
- Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3),
- Pair(0,4), Pair(2,0), Pair(3,0),
- Pair(2,4), Pair(3,1), Pair(3,4),
- Pair(4,0), Pair(4,1) };
-
- MyGraphType G(5);
- for (int i = 0; i < 11; ++i)
- add_edge(edge_array[i].first, edge_array[i].second, G);
-
- property_map<MyGraphType, first_name_t>::type
- name = get(first_name_t(), G);
-
- boost::put(name, 0, "Jeremy");
- boost::put(name, 1, "Rich");
- boost::put(name, 2, "Andrew");
- boost::put(name, 3, "Jeff");
- name[4] = "Kinis"; // you can use operator[] too
-
- who_owes_who(edges(G).first, edges(G).second, G);
-</PRE>
-
-<P>
-The <TT>who_owes_who()</TT> function written for this example was
-implemented in a generic style. The input is templated so we do not
-know the actual graph type. To find out the type of the property
-map for our first-name property, we need to use the
-<TT>property_map</TT> traits class. The <TT>const_type</TT>
-is used since the graph parameter is const. Once we have the property
-map type, we can deduce the value type of the property using the
-<TT>property_traits</TT> class. In this example, we know that the
-property's value type will be <TT>std::string</TT>, but written in this
-generic fashion the <TT>who_owes_who()</TT> function could work with
-other property value types.
-
-<P>
-<PRE>
- template <class EdgeIter, class Graph>
- void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G)
- {
- // Access the propety acessor type for this graph
- typedef typename property_map<Graph,
- first_name_t>::const_type NameMap;
- NameMap name = get(first_name, G);
-
- typedef typename boost::property_traits<NameMap>
- ::value_type NameType;
-
- NameType src_name, targ_name;
-
- while (first != last) {
- src_name = boost::get(name, source(*first, G));
- targ_name = boost::get(name, target(*first, G));
- cout << src_name << " owes "
- << targ_name << " some money" << endl;
- ++first;
- }
-</PRE>
-
-The output is:
-<PRE>
-Jeremy owes Rich some money
-Jeremy owes Andrew some money
-Jeremy owes Jeff some money
-Jeremy owes Kinis some money
-Andrew owes Jeremy some money
-Andrew owes Kinis some money
-Jeff owes Jeremy some money
-Jeff owes Rich some money
-Jeff owes Kinis some money
-Kinis owes Jeremy some money
-Kinis owes Rich some money
-</PRE>
-
-The complete source code to this example is in the file
-<TT>interior_property_map.cpp</TT>.
-
-<P>
-
-<H2><A NAME="sec:custom-storage"></A>
-Customizing the Adjacency List Storage
-</H2>
-
-<P>
-The <TT>adjacency_list</TT> is constructed out of two kinds of
-containers. One type of container to hold all the vertices in the
-graph, and another type of container for the out-edge list (and
-potentially in-edge list) for each vertex. BGL provides selector
-classes that allow the user to choose between several of the containers
-from the STL. It is also possible to use your own container types.
-When customizing the <TT>VertexList</TT> you need to define a container
-generator as described below. When customizing the <TT>OutEdgeList</TT> you
-will need to define a container generator and the parallel edge
-traits. The file <TT>container_gen.cpp</TT> has an example of
-how to use a custom storage type.
-
-<P>
-
-<H3><A NAME="SECTION00834100000000000000">
-Container Generator</A>
-</H3>
-
-<P>
-The <TT>adjacency_list</TT> class uses a traits class called
-<TT>container_gen</TT> to map the <TT>OutEdgeList</TT> and
<TT>VertexList</TT>
-selectors to the actual container types used for the graph storage.
-The default version of the traits class is listed below, along with an
-example of how the class is specialized for the <TT>listS</TT> selector.
-
-<P>
-<PRE>
-namespace boost {
- template <class Selector, class ValueType>
- struct container_gen { };
-
- template <class ValueType>
- struct container_gen<listS, ValueType> {
- typedef std::list<ValueType> type;
- };
-}
-</PRE>
-
-<P>
-To use some other container of your choice, define a
-selector class and then specialize the <TT>container_gen</TT>
-for your selector.
-
-<P>
-<PRE>
- struct custom_containerS { }; // your selector
-
- namespace boost {
- // the specialization for your selector
- template <class ValueType>
- struct container_gen<custom_containerS, ValueType> {
- typedef custom_container<ValueType> type;
- };
- }
-</PRE>
-
-<P>
-There may also be situations when you want to use a container that has
-more template parameters than just <TT>ValueType</TT>. For instance,
-you may want to supply the allocator type. One way to do this is to
-hard-code in the extra parameters within the specialization of
-<TT>container_gen</TT>. However, if you want more flexibility then you
-can add a template parameter to the selector class. In the code below
-we show how to create a selector that lets you specify the allocator
-to be used with the <TT>std::list</TT>.
-
-<P>
-<PRE>
- template <class Allocator>
- struct list_with_allocatorS { };
-
- namespace boost {
- template <class Alloc, class ValueType>
- struct container_gen<list_with_allocatorS<Alloc>,
ValueType>
- {
- typedef typename Alloc::template rebind<ValueType>::other
Allocator;
- typedef std::list<ValueType, Allocator> type;
- };
- }
-
- // now you can define a graph using std::list
- // and a specific allocator
- typedef adjacency_list< list_with_allocatorS<
std::allocator<int> >, vecS, directedS> MyGraph;
-</PRE>
-
-<P>
-
-<H3><A NAME="SECTION00834300000000000000">
-Push and Erase for the Custom Container</A>
-</H3>
-
-<P>
-You must also tell the <TT>adjacency_list</TT> how elements can be
-efficiently added and removed from the custom container. This is
-accomplished by overloading the <TT>push()</TT> and <TT>erase()</TT>
-functions for the custom container type. The <TT>push()</TT> function
-should return an iterator pointing to the newly inserted element and a
-<TT>bool</TT> flag saying whether the edge was inserted.
-
-<PRE>
- template <class T>
- std::pair<typename custom_container<T>::iterator, bool>
- push(custom_container<T>& c, const T& v)
- {
- // this implementation may need to change for your container
- c.push_back(v);
- return std::make_pair(boost::prior(c.end()), true);
- }
-
- template <class T>
- void erase(custom_container<T>& c, const T& x)
- {
- // this implementation may need to change for your container
- c.erase(std::remove(c.begin(), c.end(), x), c.end());
- }
-</PRE>
-
-
-<P> There are default <TT>push()</TT> and <TT>erase()</TT> functions
-implemented for the STL container types.
-
-
-<H3><A NAME="SECTION00834200000000000000">
-Parallel Edge Traits</A>
-</H3>
-
-<P>
-When customizing the <TT>OutEdgeList</TT>, you must also specialize
-the <TT>parallel_edge_traits</TT> class to specify whether the
-container type allows parallel edges (and is a <a
-href="http://www.sgi.com/tech/stl/Sequence.html";>Sequence</a>) or if
-the container does not allow parallel edges (and is an <a
-href="http://www.sgi.com/tech/stl/AssociativeContainer.html";>AssociativeContainer</a>).
-
-<P>
-<PRE>
- template <>
- struct parallel_edge_traits<custom_containerS> {
- typedef allow_parallel_edge_tag type;
- };
-</PRE>
+模板参数 <a href="./PropertyTag.html"><tt>PropertyTag</tt></a> 是一个标签
类，它只是标识或给出属性的唯一名称。有一些预定义的标签，也很容易增加新的。
<br></p><pre> struct vertex_index_t { };<br> struct vertex_index1_t {
};<br> struct vertex_index2_t { };<br> struct edge_index_t { };<br>
struct graph_name_t { };<br> struct vertex_name_t { };<br> struct
edge_name_t { };<br> struct edge_weight_t { };<br> struct edge_weight2_t
{ };<br> struct edge_capacity_t { };<br> struct edge_residual_capacity_t
{ };<br> struct edge_reverse_t { };<br> struct vertex_distance_t {
};<br> struct vertex_root_t { };<br> struct vertex_all_t { };<br> struct
edge_all_t { };<br> struct graph_all_t { };<br> struct vertex_color_t {
};<br> struct vertex_rank_t { };<br> struct vertex_predecessor_t {
};<br> struct vertex_isomorphism_t { };<br> struct vertex_invariant_t {
};<br> struct vertex_invariant1_t { };<br> struct vertex_invariant2_t {
};<br> struct vertex_degree_t { };<br> struct vertex_out_degree_t {
};<br> struct vertex_in_degree_t { };<br> struct vertex_discover_time_t {
};<br> struct vertex_finish_time_t { };<br></pre>
+
+<p><tt>property</tt> 的模板参数 <b><tt>T</tt></b> 给定属性值的类型。类型
<tt>T</tt> 必须是
+<a href="http://www.sgi.com/tech/stl/DefaultConstructible.html";>可缺省构造
的</a>、<a href="../../utility/Assignable.html">可赋值的</a> 和 <a
href="../../utility/CopyConstructible.html">可复制构造的</a>。和C++标准库的
容器一样，类型 <tt>T</tt> 的属性对象是以值的方式保存在图内的。
+
+</p><p>参数 <b><tt>NextProperty</tt></b> 允许属性类型被嵌套，这样就可以对同
一个图附加任意数量的属性。
+
+</p><p>以下代码示范了如何组装一个顶点属性类型或边属性类型，并用它来创建一个
图类型。我们把一个值类型为float的距离属性和一个值类型为
<tt>std::string</tt>的名称属性附加到图的顶点。我们还把一个值类型为float的权
重属性附加到图的边。</p><pre> typedef property<vertex_distance_t,
float, <br> property<vertex_name_t, std::string> >
VertexProperty;<br> typedef property<edge_weight_t, float>
EdgeProperty;<br><br> typedef adjacency_list<mapS, vecS, undirectedS,
<br> VertexProperty, EdgeProperty>
Graph;<br><br> Graph g(num_vertices); // 构造一个图对象<br></pre>
+
+<p>接下来，就可以用属性映射来读入或写出这些属性值。有关如何从一个图获得属性
映射的说明，请见 <a
href="using_property_maps.html#sec:interior-properties">内部属性Interior
+Properties</a> 一节，有关如何使用属性映射的说明，则请见 <a
href="./using_property_maps.html">属性映射Property Maps</a> 一节。
</p><h3><a name="sec:custom-edge-properties"></a>
+Custom Edge Properties 定制边的属性
+</h3>
+
+<p>创建你自己的属性类型和属性非常容易；只需要为你的新属性定义一个标签类。这
个属性标签类需要用一个唯一的整数ID定义 <tt>num</tt>，并定义 <tt>kind</tt>
为 <tt>edge_property_tag</tt>,
+<tt>vertex_property_tag</tt>, 或
<tt>graph_property_tag</tt>.</p><pre>struct flow_t {<br> typedef
edge_property_tag kind;<br>};<br><br>struct capacity_t { <br> typedef
edge_property_tag kind;<br>};<br></pre>
+
+<p>你也可以用 enum's 代替 struct's 来创建标签类型。为每个属性创建一个枚举类
型。枚举类型名字的第一个部分必须是 <tt>edge</tt>, <tt>vertex</tt>, 或
+<tt>graph</tt>，后跟一个下划符和新属性的名字，最后是一个 <tt>_t</tt>。在枚
举类型中，定义一个值，其名字为枚举类型名减去
+<tt>_t</tt>。然后调用 <tt>BOOST_INSTALL_PROPERTY</tt> 宏。
+
+</p><pre>enum edge_flow_t { edge_flow };<br>enum edge_capacity_t {
edge_capacity };<br><br>namespace boost {<br> BOOST_INSTALL_PROPERTY(edge,
flow);<br> BOOST_INSTALL_PROPERTY(edge, capacity);<br>}<br></pre>
+
+<p>现在你可以象使用内建标签那样在属性定义中使用这个新的属性标签。
</p><pre> typedef property<capacity_t, int> Cap;<br> typedef
property<flow_t, int, Cap> EdgeProperty;<br> typedef
adjacency_list<vecS, vecS, no_property, EdgeProperty> Graph;<br></pre>
+
+<p>和前面一样，这些属性的属性映射可以通过
+<tt>get(Property, g)</tt> 函数从图中取得。</p><pre>
property_map<Graph, capacity_t>::type capacity<br> =
get(capacity_t(), G);<br> property_map<Graph, flow_t>::type
flow<br> = get(flow_t(), G);<br></pre>
+
+<p>文件 <tt>edge_property.cpp</tt> 列出了这个例子的完整源代码。</p><h3><a
name="SECTION00833200000000000000"></a>
+<a name="sec:custom-vertex-properties"></a>
+<br>
+Custom Vertex Properties 定制顶点的属性
+</h3>
+
+<p>创建你自己的属性关联至顶点和创建边属性一样容易。下面我们将某人的姓关联至
图中的顶点。</p><pre> struct first_name_t {<br> typedef
vertex_property_tag kind;<br> };<br></pre>
+
+<p>现在我们可以在 <tt>property</tt> 类中使用这个新标签，并在组装一个图类型
时使用它。以下代码示范了图类型的创建，然后再创建一个图对象。我们把边填入，并
将名字赋给顶点。这些边表示的是"谁欠了谁"。</p><pre> typedef
property<first_name_t, std::string> FirstNameProperty;<br> typedef
adjacency_list<vecS, vecS, directedS, <br>
FirstNameProperty> MyGraphType;<br><br> typedef pair<int,int>
Pair;<br> Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3),
<br> Pair(0,4), Pair(2,0), Pair(3,0),
<br> Pair(2,4), Pair(3,1), Pair(3,4),
<br> Pair(4,0), Pair(4,1) };<br> <br>
MyGraphType G(5);<br> for (int i = 0; i < 11; ++i)<br>
add_edge(edge_array[i].first, edge_array[i].second, G);<br><br>
property_map<MyGraphType, first_name_t>::type<br> name =
get(first_name_t(), G);<br> <br> boost::put(name, 0, "Jeremy");<br>
boost::put(name, 1, "Rich");<br> boost::put(name, 2, "Andrew");<br>
boost::put(name, 3, "Jeff");<br> name[4] = "Kinis"; // you can use
operator[] too<br> <br> who_owes_who(edges(G).first, edges(G).second,
G);<br></pre>
+
+<p>为这个例子所写的函数 <tt>who_owes_who()</tt> 是以泛型的方式实现的。输入
是模板化的，因为我们不知道实际的图类型。要针对我们的姓氏属性找出其属性映射类
型，我们要用
+<tt>property_map</tt> traits 类。因为 graph 参数是常量性的，所以要使
用 <tt>const_type</tt>。我们有了这个属性映射类型后，就可以用
+<tt>property_traits</tt> 类推导出属性的值类型。在这个例子中，我们知道该属性
的类型是 <tt>std::string</tt>，不过，以泛型的方式来编写的
<tt>who_owes_who()</tt> 函数也可以用于其它的属性值类型。</p><pre> template
<class EdgeIter, class Graph><br> void who_owes_who(EdgeIter first,
EdgeIter last, const Graph& G)<br> {<br> // 访问该图的属性访问器类型
<br> typedef typename property_map<Graph, <br>
first_name_t>::const_type NameMap;<br> NameMap name = get(first_name,
G);<br><br> typedef typename
boost::property_traits<NameMap><br> ::value_type
NameType;<br><br> NameType src_name, targ_name;<br><br> while
(first != last) {<br> src_name = boost::get(name, source(*first,
G));<br> targ_name = boost::get(name, target(*first, G));<br>
cout << src_name << " owes " <br> << targ_name
<< " some money" << endl;<br> ++first;<br> }<br></pre>输
出如下：
+<pre>Jeremy owes Rich some money<br>Jeremy owes Andrew some
money<br>Jeremy owes Jeff some money<br>Jeremy owes Kinis some
money<br>Andrew owes Jeremy some money<br>Andrew owes Kinis some
money<br>Jeff owes Jeremy some money<br>Jeff owes Rich some money<br>Jeff
owes Kinis some money<br>Kinis owes Jeremy some money<br>Kinis owes Rich
some money<br></pre>该例子的完整源代码在文件
+<tt>interior_property_map.cpp</tt> 中。<h2><a
name="sec:custom-storage"></a>
+Customizing the Adjacency List Storage 定制邻接列表的存储
+</h2>
+
+<p>
+<tt>adjacency_list</tt> 由两类容器构造而成。一类容器用于保存图中的所有顶
点，另一类容器则用于保存每个顶点的出边列表(可能还有入边列表)。BGL提供了选择
符类，允许用户在STL提供的几种容器中进行选择。你也可以使用你自己的容器类型。
在定制 <tt>VertexList</tt> 时，你需要如下文所说那样定义一个容器生成器。在定
制 <tt>OutEdgeList</tt> 时则需要定义一个容器生成器以及平行边
+traits。文件 <tt>container_gen.cpp</tt> 中有一个关于如何使用定制的存储类型
的例子。</p><h3><a name="SECTION00834100000000000000">
+Container Generator 容器生成器</a>
+</h3>
+
+<p><tt>adjacency_list</tt> 类用一个名为
+<tt>container_gen</tt> 的 traits 类来将 <tt>OutEdgeList</tt> 和
<tt>VertexList</tt>
+选择符映射至图存储实际使用的容器类型。这个 traits 类的缺省版本列出如下，还
有一个关于如何为 <tt>listS</tt> 选择符对该类进行特化的例子。
</p><pre>namespace boost {<br> template <class Selector, class
ValueType><br> struct container_gen { };<br><br> template <class
ValueType><br> struct container_gen<listS, ValueType> {<br>
typedef std::list<ValueType> type;<br> };<br>}<br></pre>
+
+<p>要使用你选择的其它容器，就定义一个选择符类，然后为你的选择符特化
<tt>container_gen</tt>。</p><pre> struct custom_containerS { }; // 你的选择
符<br><br> namespace boost {<br> // 针对你的选择符的特化<br>
template <class ValueType><br> struct
container_gen<custom_containerS, ValueType> {<br> typedef
custom_container<ValueType> type;<br> };<br> }<br></pre>
+
+<p>可能有些时候，你想对容器指定更多的模板参数，不仅仅是
<tt>ValueType</tt>。例如，你可能想指定分配器类型。一个方法是，将额外参数硬编
码到
+<tt>container_gen</tt> 的特化版中。不过，如果你想要更多的灵活性，你可以为选
择符类增加一个模板参数。在以下代码中，我们示范了如何创建一个选择符，可以让你
指定 <tt>std::list</tt> 所使用的分配器。</p><pre> template <class
Allocator><br> struct list_with_allocatorS { };<br><br> namespace
boost {<br> template <class Alloc, class ValueType><br> struct
container_gen<list_with_allocatorS<Alloc>, ValueType><br>
{<br> typedef typename Alloc::template rebind<ValueType>::other
Allocator;<br> typedef std::list<ValueType, Allocator>
type;<br> };<br> }<br><br> // 现在你可以用 std::list 和特定的分配器定义
一个图<br> typedef adjacency_list< list_with_allocatorS<
std::allocator<int> >, vecS, directedS> MyGraph;<br></pre>
+
+<h3><a name="SECTION00834300000000000000">
+Push and Erase for the Custom Container 定制容器的压入和删除</a>
+</h3>
+
+<p>你还必须告诉 <tt>adjacency_list</tt>，元素可以如何高效地加入到定制容器中
和从中删除。这可以通过为定制容器类型重载 <tt>push()</tt> 和 <tt>erase()</tt>
+函数来完成。<tt>push()</tt> 函数应返回一个指向新插入元素的迭代器，以及一个
表示是否插入成功的布尔标志。
+
+</p><pre> template <class T><br> std::pair<typename
custom_container<T>::iterator, bool><br>
push(custom_container<T>& c, const T& v)<br> {<br> // 对于
你的容器，可能需要修改该实现<br> c.push_back(v);<br> return
std::make_pair(boost::prior(c.end()), true);<br> }<br><br> template
<class T><br> void erase(custom_container<T>& c, const
T& x)<br> {<br> // 对于你的容器，可能需要修改该实现<br>
c.erase(std::remove(c.begin(), c.end(), x), c.end());<br> }<br></pre>
+
+
+<p>以上是用于STL容器类型的 <tt>push()</tt> 和 <tt>erase()</tt> 函数的缺省实
现。
+
+
+</p><h3><a name="SECTION00834200000000000000">
+Parallel Edge Traits 平行边 Traits</a>
+</h3>
+
+<p>在定制 <tt>OutEdgeList</tt> 时，你还必须特化
<tt>parallel_edge_traits</tt> 类，以指定该容器类型是允许平行边(且是一个 <a
href="http://www.sgi.com/tech/stl/Sequence.html";>序列Sequence</a>)，或是不允
许平行边(且是一个 <a
href="http://www.sgi.com/tech/stl/AssociativeContainer.html";>关联容器
AssociativeContainer</a>)。</p><pre> template <><br> struct
parallel_edge_traits<custom_containerS> { <br> typedef
allow_parallel_edge_tag type;<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 © 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/using_property_maps.html
==============================================================================
--- trunk/libs/graph/doc/using_property_maps.html (original)
+++ trunk/libs/graph/doc/using_property_maps.html Thu Jul 2 20:26:08 2009
@@ -1,480 +1,113 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head><meta content="text/html; charset=UTF-8"
http-equiv="content-type"><!--
-- Copyright (c) Jeremy Siek 2000
--
-- Distributed under the Boost Software License, Version 1.0.
-- (See accompanying file LICENSE_1_0.txt or copy at
-- http://www.boost.org/LICENSE_1_0.txt)
-->
-<Head>
-<Title>Boost Graph Library: Using Property Maps</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:property-maps"></A>
-Property Maps
-</H1>
-
-<P>
-The main link between the abstract mathematical nature of graphs and
-the concrete problems they are used to solve is the properties that
-are attached to the vertices and edges of a graph, things like
-distance, capacity, weight, color, etc. There are many ways to attach
-properties to graph in terms of data-structure implementation, but
-graph algorithms should not have to deal with the implementation
-details of the properties. The <I>property map</I> interface
-defined in Section <A
-HREF="../../property_map/property_map.html">Property
-Map Concepts</A> provides a generic method for accessing
-properties from graphs. This is the interface used in the BGL
-algorithms to access properties.
-
-<P>
-
-<H2>Property Map Interface</H2>
-
-<P>
-The property map interface specifies that each property is
-accessed using a separate property map object. In the following
-example we show an implementation of the <TT>relax()</TT> function used
-inside of Dijkstra's shortest paths algorithm. In this function, we
-need to access the weight property of an edge, and the distance
-property of a vertex. We write <TT>relax()</TT> as a template function
-so that it can be used in many difference situations. Two of the
-arguments to the function, <TT>weight</TT> and <TT>distance</TT>, are the
-property map objects. In general, BGL algorithms explicitly pass
-property map objects for every property that a function will
-need. The property map interface defines several functions, two
-of which we use here: <TT>get()</TT> and <TT>put()</TT>. The <TT>get()</TT>
-function takes a property map object, such as <TT>distance</TT> and
-a <I>key</I> object. In the case of the distance property we are using
-the vertex objects <TT>u</TT> and <TT>v</TT> as keys. The <TT>get()</TT>
-function then returns the property value for the vertex.
-
-<P>
-<PRE>
- template <class Edge, class Graph,
- class WeightPropertyMap,
- class DistancePropertyMap>
- bool relax(Edge e, const Graph& g,
- WeightPropertyMap weight,
- DistancePropertyMap distance)
- {
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- Vertex u = source(e,g), v = target(e,g);
- if ( get(distance, u) + get(weight, e) < get(distance, v)) {
- put(distance, v, get(distance, u) + get(weight, e));
- return true;
- } else
- return false;
- }
-</PRE>
-
-The function <TT>get()</TT> returns a copy of the property value. There
-is a third function in the property map interface, <TT>at()</TT>,
-that returns a reference to the property value (a const reference if
-the map is not mutable).
-
-<P>
-Similar to the <TT>iterator_traits</TT> class of the STL, there is a
-<TT>property_traits</TT> class that can be used to deduce the types
-associated with a property map type: the key and value types, and
-the property map category (which is used to tell whether the
-map is readable, writeable, or both). In the <TT>relax()</TT>
-function we could have used <TT>property_traits</TT> to declare local
-variables of the distance property type.
-
-<P>
-<PRE>
- {
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- Vertex u = source(e,g), v = target(e,g);
- typename property_traits<DistancePropertyMap>::value_type
- du, dv; // local variables of the distance property type
- du = get(distance, u);
- dv = get(distance, v);
- if (du + get(weight, e) < dv) {
- put(distance, v, du + get(weight, e));
- return true;
- } else
- return false;
- }
-</PRE>
-
-<P>
-There are two kinds of graph properties: interior and exterior.
-
-<P>
-<DL>
-<DT><STRONG>Interior Properties</STRONG></DT>
-<DD>are stored ``inside'' the graph object
-in some way, and the lifetime of the property value objects is the
-same as that of the graph object.
-
-<P>
-</DD>
-<DT><STRONG>Exterior Properties</STRONG></DT>
-<DD>are stored ``outside'' of the graph
-object and the lifetime of the property value objects is independent
-of the graph. This is useful for properties that are only needed
-temporarily, perhaps for the duration of a particular algorithm such
-as the color property used in <TT>breadth_first_search()</TT>. When
-using exterior properties with a BGL algorithm a property map
-object for the exterior property must be passed as an argument to the
-algorithm.
-</DD>
-</DL>
-
-<P>
-
-<H2><A NAME="sec:interior-properties"></A>
-Interior Properties
-</H2>
-
-<P>
-A graph type that supports interior property storage (such as
-<TT>adjacency_list</TT>) provides access to its property map
-objects through the interface defined in <a
-href="./PropertyGraph.html">PropertyGraph</a>. There is a function
-<TT>get(Property, g)</TT> that get property map objects from a
-graph. The first argument is the property type to specify which
-property you want to access and the second argument is the graph
-object. A graph type must document which properties (and therefore
-tags) it provides access to. The type of the property map depends on
-the type of graph and the property being mapped. A trait class is
-defined that provides a generic way to deduce the property map type:
-<TT>property_map</TT>. The following code shows how one can obtain the
-property map for the distance and weight properties of some graph
-type.
-
-<P>
-<PRE>
- property_map<Graph, vertex_distance_t>::type d
- = get(vertex_distance, g);
-
- property_map<Graph, edge_weight_t>::type w
- = get(edge_weight, g);
-</PRE>
-
-<P>
-In general, the BGL algorithms require all property maps needed
-by the algorithm to be explicitly passed to the algorithm. For
-example, the BGL Dijkstra's shortest paths algorithm requires four
-property maps: distance, weight, color, and vertex ID.
-
-<P>
-Often times some or all of the properties will be interior to the
-graph, so one would call Dijkstra's algorithm in the following way
-(given some graph <TT>g</TT> and source vertex <TT>src</TT>).
-
-<P>
-<PRE>
- dijkstra_shortest_paths(g, src,
- distance_map(get(vertex_distance, g)).
- weight_map(get(edge_weight, g)).
- color_map(get(vertex_color, g)).
- vertex_index_map(get(vertex_index, g)));
-</PRE>
-
-<P>
-Since it is somewhat cumbersome to specify all of the property maps,
-BGL provides defaults that assume some of the properties are interior
-and can be accessed via <TT>get(Property, g)</TT> from the graph, or
-if the property map is only used internally, then the algorithm will
-create a property map for itself out of an array and using the graph's
-vertex index map as the offset into the array. Below we show a call to
-<TT>dijkstra_shortest_paths</TT> algorithm using all defaults for the
-named parameters. This call is equivalent to the previous call to
-Dijkstra's algorithm.
-
-<P>
-<PRE>
- dijkstra_shortest_paths(g, src);
-</PRE>
-
-<P>
-The next question is: how do interior properties become attached to a
-graph object in the first place? This depends on the graph class that
-you are using. The <TT>adjacency_list</TT> graph class of BGL uses a
-property mechanism (see Section <A
-HREF="using_adjacency_list.html#sec:adjacency-list-properties">Internal
-Properties</A>) to allow an arbitrary number of properties to be
-stored on the edges and vertices of the graph.
-
-<P>
-
-<H2><A NAME="sec:exterior-properties"></A>
-Exterior Properties
-</H2>
-
-<P>
-In this section we will describe two methods for constructing exterior
-property maps, however there is an unlimited number of ways that
-one could create exterior properties for a graph.
-
-<P>
-The first method uses the adaptor class
-<TT>random_access_iterator_property_map</TT>. This
-class wraps a random access iterator, creating a property map out
-of it. The random access iterator must point to the beginning of a
-range of property values, and the length of the range must be the
-number of vertices or edges in the graph (depending on whether it is a
-vertex or edge property map). The adaptor must also be supplied
-with an ID property map, which will be used to map the vertex or
-edge descriptor to the offset of the property value (offset from the
-random access iterator). The ID property map will typically be an
-interior property map of the graph. The following example shows
-how the <TT>random_access_iterator_property_map</TT>
-can be used to create exterior property maps for the capacity and flow
properties, which are stored in arrays. The arrays are
-indexed by edge ID. The edge ID is added to the graph using a property,
-and the values of the ID's are given when each edge is added to the
-graph. The complete source code for this example is in
-<TT>example/exterior_edge_properties.cpp</TT>. The
-<TT>print_network()</TT> function prints out the graph with
-the flow and capacity values.
-
-<P>
-<PRE>
- typedef adjacency_list<vecS, vecS, bidirectionalS,
- no_property, property<edge_index_t, std::size_t> > Graph;
-
- const int num_vertices = 9;
- Graph G(num_vertices);
-
- int capacity_array[] = { 10, 20, 20, 20, 40, 40, 20, 20, 20, 10 };
- int flow_array[] = { 8, 12, 12, 12, 12, 12, 16, 16, 16, 8 };
-
- // Add edges to the graph, and assign each edge an ID number.
- add_edge(0, 1, 0, G);
- // ...
-
- typedef graph_traits<Graph>::edge_descriptor Edge;
- typedef property_map<Graph, edge_index_t>::type EdgeID_Map;
- EdgeID_Map edge_id = get(edge_index, G);
-
- random_access_iterator_property_map
- <int*, int, int&, EdgeID_Map>
- capacity(capacity_array, edge_id),
- flow(flow_array, edge_id);
-
- print_network(G, capacity, flow);
-</PRE>
-
-<P>
-The second method uses a pointer type (a pointer to an array of
-property values) as a property map. This requires the key type to
-be an integer so that it can be used as an offset to the pointer. The
-<TT>adjacency_list</TT> class with template parameter
-<TT>VertexList=vecS</TT> uses integers for vertex descriptors (indexed
-from zero to the number of vertices in the graph), so they are
-suitable as the key type for a pointer property map. When the
-<TT>VertexList</TT> is not <TT>vecS</TT>, then the vertex descriptor is
-not an integer, and cannot be used with a pointer property map.
-Instead the method described above of using a
-<TT>random_access_iterator_property_map</TT> with an ID
-property must be used. The <TT>edge_list</TT> class may also use an
-integer type for the vertex descriptor, depending on how the adapted
-edge iterator is defined. The example in
-<TT>example/bellman_ford.cpp</TT> shows <TT>edge_list</TT> being used
-with pointers as vertex property maps.
-
-<P>
-The reason that pointers can be used as property maps is that
-there are several overloaded functions and a specialization of
-<TT>property_traits</TT> in the header <a
-href="../../../boost/property_map.hpp"><TT>boost/property_map.hpp</TT></a>
-that implement the property map interface in terms of
-pointers. The definition of those functions is listed here.
-
-<P>
-<PRE>
-namespace boost {
- template <class T>
- struct property_traits<T*> {
- typedef T value_type;
- typedef ptrdiff_t key_type;
- typedef lvalue_property_map_tag category;
- };
-
- template <class T>
- void put(T* pa, std::ptrdiff_t key, const T& value) { pa[key] =
value; }
-
- template <class T>
- const T& get(const T* pa, std::ptrdiff_t key) { return pa[key]; }
-
- template <class T>
- const T& at(const T* pa, std::ptrdiff_t key) { return pa[key]; }
-
- template <class T>
- T& at(T* pa, std::ptrdiff_t key) { return pa[key]; }
-}
-</PRE>
-
-<P>
-In the following example, we use an array to store names of cities for
-each vertex in the graph, and a <TT>std::vector</TT> to store vertex
-colors which will be needed in a call to
-<TT>breadth_first_search()</TT>. Since the iterator of a
-<TT>std::vector</TT> (obtained with a call to <TT>begin()</TT>) is a
-pointer, the pointer property map method also works for
-<TT>std::vector::iterator</TT>. The complete source code for this
-example is in <a
-href="../example/city_visitor.cpp"><TT>example/city_visitor.cpp</TT></a>.
-
-<P>
-<PRE>
-// Definition of city_visitor omitted...
-
-int main(int,char*[])
-{
- enum { SanJose, SanFran, LA, SanDiego, Fresno, LosVegas, Reno,
- Sacramento, SaltLake, Pheonix, N };
-
- // An array of vertex name properties
- std::string names[] = { "San Jose", "San
Francisco", "San Jose",
- "San Francisco", "Los
Angeles", "San Diego",
- "Fresno", "Los Vegas",
"Reno", "Sacramento",
- "Salt Lake City", "Pheonix"
};
-
- // Specify all the connecting roads between cities.
- typedef std::pair<int,int> E;
- E edge_array[] = { E(Sacramento, Reno), ... };
-
- // Specify the graph type.
- typedef adjacency_list<vecS, vecS, undirectedS> Graph;
- // Create the graph object, based on the edges in edge_array.
- Graph G(N, edge_array, edge_array + sizeof(edge_array)/sizeof(E));
-
- // DFS and BFS need to "color" the vertices.
- // Here we use std::vector as exterior property storage.
- std::vector<default_color_type> colors(N);
-
- cout << "*** Depth First ***" << endl;
- depth_first_search(G, city_visitor(names), colors.begin());
- cout << endl;
-
- // Get the source vertex
- boost::graph_traits<Graph>::vertex_descriptor
- s = vertex(SanJose, G);
-
- cout << "*** Breadth First ***" << endl;
- breadth_first_search(G, s, city_visitor(names), colors.begin());
-
- return 0;
-}
-</PRE>
-
-<P>
-
-<H2><A NAME="sec:custom-exterior-property-maps"></A>
-Constructing an Exterior Property Map
-</H2>
-
-<P>
-Implementing your own exterior property maps is not very
-difficult. You simply need to overload the functions required by the
-<a href="property_map.html">property map concept</a>
-that you want your class to model. At most, this means overloading the
-<TT>put()</TT> and <TT>get()</TT> functions and implementing
-<TT>operator[]</TT>. Also, your property map class will need to have
-nested typedefs for all the types defined in <TT>property_traits</TT>,
-or you can create a specialization of <TT>property_traits</TT> for
-your new property map type.
-
-<P>
-The implementation of the
-<TT>random_access_iterator_property_map</TT> class
-serves as a good example for how to build and exterior property
-map. Here we present a simplified implementation of the
-<TT>random_access_iterator_property_map</TT> class
-which we will name <TT>iterator_pa</TT>.
-
-<P>
-We start with the definition of the <TT>iterator_map</TT> class
-itself. This adaptor class is templated on the adapted <TT>Iterator</TT>
-type and the ID property map. The job of the ID property map
-is to map the key object (which will typically be a vertex or edge
-descriptor) to an integer offset. The <TT>iterator_map</TT> class will
-need the three necessary typedefs for a property map:
-<TT>key_type</TT>, <TT>value_type</TT>, and <TT>category</TT>. We can use
-<TT>property_traits</TT> to find the key type of <TT>IDMap</TT>, and
-we can use <TT>iterator_traits</TT> to determine the value type of
-<TT>Iterator</TT>. We choose
-<TT>boost::lvalue_property_map_tag</TT> for the category
-since we plan on implementing the <TT>at()</TT> function.
-
-<P>
-<PRE>
- template <class Iterator, class IDMap>
- class iterator_map
- {
- public:
- typedef typename boost::property_traits<IDMap>::key_type
key_type;
- typedef typename std::iterator_traits<Iterator>::value_type
value_type;
- typedef boost::lvalue_property_map_tag category;
-
- iterator_map(Iterator i = Iterator(),
- const IDMap& id = IDMap())
- : m_iter(i), m_id(id) { }
- Iterator m_iter;
- IDMap m_id;
- };
-</PRE>
-
-<P>
-Next we implement the three property map functions, <TT>get()</TT>,
-<TT>put()</TT>, and <TT>at()</TT>. In each of the functions, the
-<TT>key</TT> object is converted to an integer offset using the
-<TT>m_id</TT> property map, and then that is used as an offset
-to the random access iterator <TT>m_iter</TT>.
-
-<P>
-<PRE>
- template <class Iter, class ID>
- typename std::iterator_traits<Iter>::value_type
- get(const iterator_map<Iter,ID>& i,
- typename boost::property_traits<ID>::key_type key)
- {
- return i.m_iter[i.m_id[key]];
- }
- template <class Iter, class ID>
- void
- put(const iterator_map<Iter,ID>& i,
- typename boost::property_traits<ID>::key_type key,
- const typename std::iterator_traits<Iter>::value_type&
value)
- {
- i.m_iter[i.m_id[key]] = value;
- }
- template <class Iter, class ID>
- typename std::iterator_traits<Iter>::reference
- at(const iterator_map<Iter,ID>& i,
- typename boost::property_traits<ID>::key_type key)
- {
- return i.m_iter[i.m_id[key]];
- }
-</PRE>
-
-<P>
-That is it. The <TT>iterator_map</TT> class is complete and could be
-used just like the
-<TT>random_access_iterator_property_map</TT> in the
-previous section.
-
-<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>)
-</TD></TR></TABLE>
+<title>Boost Graph Library: Using Property Maps</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:property-maps"></a>
+Property Maps 属性映射
+</h1>
+
+<p>在图的数学抽象与要解决的问题之间，最主要的联系就是那些关联到图的顶点和边
上的属性，如距离、容量、权重、颜色等等。根据不同的数据结构实现，可以有多种方
法来把属性关联到图上，但是图算法不应该要去处理这些属性的实现细节。在 <a
href="../../property_map/property_map.html">属性映射概念Property
+Map Concepts</a> 一节中所定义的 <i>属性映射property map</i> 提供了一种通用
的方法来访问图中的属性。这就是在BGL算法中用于访问属性的接口。
</p><h2>Property Map Interface 属性映射接口</h2>
+
+<p>属性映射接口规定，每个被访问的属性都要使用独立的属性映射对象。在以下凳子
中，我们将示范一个在Dijkstra最短路径算法内使用的 <tt>relax()</tt> 函数的实
现。在这个函数中，我们需要访问一条边的权重属性，以及一个顶点的距离属性。我们
将 <tt>relax()</tt> 写成一个模板函数，这样它就可以用于多种不同的情形。该函数
的两个参数，权重和距离，都是属性映射对象。通常，BGL算法为函数所需的每个属性
显式传递一个属性映射对象。属性映射接口定义了几个函数，我们在这里用到其中两
个：<tt>get()</tt> 和 <tt>put()</tt>。函数 <tt>get()</tt>
+接受一个属性映射对象如距离，以及一个<i>key键值</i>对象。在距离属性的例子
中，我们以顶点对象 <tt>u</tt> 和 <tt>v</tt> 作为键值。函数 <tt>get()</tt>
+会为该顶点返回属性值。</p><pre> template <class Edge, class
Graph,<br> class WeightPropertyMap, <br> class
DistancePropertyMap><br> bool relax(Edge e, const Graph& g,
<br> WeightPropertyMap weight, <br>
DistancePropertyMap distance)<br> {<br> typedef typename
graph_traits<Graph>::vertex_descriptor Vertex;<br> Vertex u =
source(e,g), v = target(e,g);<br> if ( get(distance, u) + get(weight, e)
< get(distance, v)) {<br> put(distance, v, get(distance, u) +
get(weight, e));<br> return true;<br> } else<br> return
false;<br> }<br></pre>函数 <tt>get()</tt> 返回属性值的一份拷贝。属性映射接
口中还有一个函数 <tt>at()</tt>，它返回属性值的一个引用(如果映射是不可变的则
返回常量引用)。
+
+<p>类似于STL中的 <tt>iterator_traits</tt> 类，这里也有一个
+<tt>property_traits</tt> 类可用于推导与某个属性映射类型相关的类型：键类型和
值类型，以及属性映射的类别(被用于告知映射是否为可读的、可写的、或均可)。在函
数 <tt>relax()</tt>
+中，我们就可以用 <tt>property_traits</tt> 来声明一个距离属性类型的局部变
量。</p><pre> {<br> typedef typename
graph_traits<Graph>::vertex_descriptor Vertex;<br> Vertex u =
source(e,g), v = target(e,g);<br> typename
property_traits<DistancePropertyMap>::value_type<br> du, dv; //
距离属性类型的局部变量<br> du = get(distance, u);<br> dv =
get(distance, v);<br> if (du + get(weight, e) < dv) {<br>
put(distance, v, du + get(weight, e));<br> return true;<br> }
else<br> return false;<br> }<br></pre>
+
+<p>共有两类图属性：内部的和外部的。</p><dl>
+<dt><strong>Interior Properties 内部属性</strong></dt>
+<dd>是指以某种方式保存在图对象"内部"的属性，其属性值对象的生存期与图对象一
样。</dd><dt><strong>Exterior Properties 外部属性</strong></dt>
+<dd>是指保存在图对象"外部"的属性，其属性值对象的生存期与图对象无关。这对于
那些只是临时需要的属性比较有用，可能只用于某个特定算法执行期间，如在
<tt>breadth_first_search()</tt> 中使用的颜色属性。当对一个BGL算法使用外部属
性时，该外部属性的属性映射对象必须作为参数传递给这个算法。</dd>
+</dl>
+
+<h2><a name="sec:interior-properties"></a>
+Interior Properties 内部属性
+</h2>
+
+<p>支持内部属性存储的图类型(如
+<tt>adjacency_list</tt>)通过在 <a
href="PropertyGraph.html">PropertyGraph</a> 中定义的接口来提供对其属性映射对
象的访问。有一个函数
+<tt>get(Property, g)</tt>
+用于从图中获取属性映射对象。第一个参数是属性类型，指定你要访问的是哪个属
性，第二个参数则是图对象。图对象必须在文档中标明它提供了对哪些属性的访问
+(以及相关标签)。属性映射的类型依赖于图的类型以及被映射的属性。我们定义了一
个 trait 类以提供一个通用的方法来推导属性映射类型：<tt>property_map</tt>。以
下代码示范了你可以如何获得对应于某种图类型的距离和权重属性的属性映射。
</p><pre> property_map<Graph, vertex_distance_t>::type d<br> =
get(vertex_distance, g);<br><br> property_map<Graph,
edge_weight_t>::type w<br> = get(edge_weight, g);<br></pre>
+
+<p>总的来说，BGL算法要求它所需的所有属性映射必须显式传入。例如，BGL的
Dijkstra最短路径算法要求四个属性映射：距离、权重、颜色和顶点ID。
+
+</p><p>通常，这些属性的部分或全部会是图的内部属性，因此你可以用以下方法调用
Dijkstra算法(给定图 <tt>g</tt> 和源顶点 <tt>src</tt>)。</p><pre>
dijkstra_shortest_paths(g, src, <br> distance_map(get(vertex_distance,
g)).<br> weight_map(get(edge_weight, g)).<br>
color_map(get(vertex_color, g)).<br> vertex_index_map(get(vertex_index,
g)));<br></pre>
+
+<p>因为指定所有属性映射会有些麻烦，所以BGL提供了缺省值，假定有些属性是内部
的且可以通过 <tt>get(Property, g)</tt> 来从图中访问，或者如果该属性映射仅在
内部使用，则算法将会为它自己由一个数据来创建属性映射，并使用图的顶点索引映射
作为数组中的偏移量。下面我们将示范一个对
+<tt>dijkstra_shortest_paths</tt> 算法的调用，对命名参数全部使用缺省值。这个
调用与前一个对
+Dijkstra算法的调用是相同的。</p><pre> dijkstra_shortest_paths(g,
src);<br></pre>
+
+<p>下一个问题是：在第一个例子中，内部属性是如何关联到图对象的呢？这取决于你
所使用的图类。BGL的 <tt>adjacency_list</tt> 图类使用了一个属性机制(参见 <a
href="using_adjacency_list.html#sec:adjacency-list-properties">内部属性
Internal
+Properties</a> 一节)，它允许在图的边和顶点中保存任意数量的属性。</p><h2><a
name="sec:exterior-properties"></a>
+Exterior Properties 外部属性
+</h2>
+
+<p>在这一节中，我们将讨论两个构造外部属性映射的方法，不过，为一个图创建外部
的属性的方法是无限的。
+
+</p><p>第一个方法使用适配器类
+<tt>random_access_iterator_property_map</tt>。这个类封装了一个随机访问迭代
器，由它来创建属性映射。这
+个随机访问迭代器必须指向一个属性值区间的始端，且区间的长度必须等于图中的顶
点或边(视乎该属性是一个顶点属性映射还是边属性映射)的数量。该适配器还
+必须支持一个ID属性映射，它将会被用于将顶点或边描述符映射至属性值的偏移量(从
该随机访问迭代器起算的偏移量)。这个ID属性映射通常会是图的一个内
+部属性。以下例子示范了如何使用 <tt>random_access_iterator_property_map</tt>
+来为容量属性和流量属性创建外部属性映射，这些属性以数组方式保存。这些数组通
过边ID来索引。边ID被增加至使用属性的图中，且ID的值在每条边被增加至图中时给
定。这个例子的完整代码在 <tt>example/exterior_edge_properties.cpp</tt>。函数
+<tt>print_network()</tt> 打印出这个图的流量和容量值。</p><pre> typedef
adjacency_list<vecS, vecS, bidirectionalS, <br> no_property,
property<edge_index_t, std::size_t> > Graph;<br><br> const int
num_vertices = 9;<br> Graph G(num_vertices);<br><br> int capacity_array[]
= { 10, 20, 20, 20, 40, 40, 20, 20, 20, 10 };<br> int flow_array[] = { 8,
12, 12, 12, 12, 12, 16, 16, 16, 8 };<br><br> // Add edges to the graph,
and assign each edge an ID number. 向图中增加边，并为每条边赋予ID数。<br>
add_edge(0, 1, 0, G);<br> // ...<br><br> typedef
graph_traits<Graph>::edge_descriptor Edge;<br> typedef
property_map<Graph, edge_index_t>::type EdgeID_Map;<br> EdgeID_Map
edge_id = get(edge_index, G);<br><br>
random_access_iterator_property_map<br> <int*, int, int&,
EdgeID_Map> <br> capacity(capacity_array, edge_id), <br>
flow(flow_array, edge_id);<br><br> print_network(G, capacity,
flow);<br></pre>
+
+<p>第二种方法使用一个指针类型(指向一个属性值数组的指针)作为属性映射。这要求
键类型是一个整数，这样它可以被作为距该指针的偏移量来使用。带有模板参数
+<tt>VertexList=vecS</tt> 的 <tt>adjacency_list</tt> 类是以整数作为顶点描述
符的(从零至图中的顶点数)，因此它们适合于用作指针属性映射的键类型。如果
+<tt>VertexList</tt> 不是 <tt>vecS</tt>，则顶点描述符不是整数，不可以和指针
属性映射一起使用。相反，前面所介绍的
+<tt>random_access_iterator_property_map</tt> 方法则必须使用ID属性。
<tt>edge_list</tt> 类也可以用整数来作顶点描述符，这取决于如何定义适配边的迭
代器。<tt>example/bellman_ford.cpp</tt> 中的例子所示范的 <tt>edge_list</tt>
就是用指针来作顶点属性映射的。
+
+</p><p>指针可以被用作属性映射的原因是，在头文件 <a
href="../../../boost/property_map.hpp"><tt>boost/property_map.hpp</tt></a>
中有几个重载的函数和一个特化的
+<tt>property_traits</tt>，它们实现了使用指针的属性映射接口。这些函数的定义
列出如下。</p><pre>namespace boost {<br> template <class T><br>
struct property_traits<T*> {<br> typedef T value_type;<br>
typedef ptrdiff_t key_type;<br> typedef lvalue_property_map_tag
category;<br> };<br><br> template <class T><br> void put(T* pa,
std::ptrdiff_t key, const T& value) { pa[key] = value; }<br><br>
template <class T><br> const T& get(const T* pa, std::ptrdiff_t
key) { return pa[key]; }<br><br> template <class T><br> const
T& at(const T* pa, std::ptrdiff_t key) { return pa[key]; }<br><br>
template <class T><br> T& at(T* pa, std::ptrdiff_t key) { return
pa[key]; }<br>}<br></pre>
+
+<p>在以下例子中，我们用一个数组来为图中的每一个顶点保存一个城市名，再用一
个 <tt>std::vector</tt> 来保存在调用
+<tt>breadth_first_search()</tt> 时要用到的顶点颜色。因为
+<tt>std::vector</tt> (通过调用 <tt>begin()</tt> 获得)的迭代器是一个指针，所
以指针属性映射也适用于
+<tt>std::vector::iterator</tt>。该例子的完整代码在 <a
href="../example/city_visitor.cpp"><tt>example/city_visitor.cpp</tt></a>。
</p><pre>// Definition of city_visitor omitted... 忽略 city_visitor 的定义
<br><br>int main(int,char*[])<br>{<br> enum { SanJose, SanFran, LA,
SanDiego, Fresno, LosVegas, Reno,<br> Sacramento, SaltLake,
Pheonix, N };<br><br> // An array of vertex name properties 顶点的名字属性
数组<br> std::string names[] = { "San Jose", "San Francisco", "San
Jose",<br> "San Francisco", "Los Angeles", "San
Diego", <br> "Fresno", "Los
Vegas", "Reno", "Sacramento",<br> "Salt Lake
City", "Pheonix" };<br><br> // Specify all the connecting roads between
cities. 指定城市间的所有相连道路<br> typedef std::pair<int,int>
E;<br> E edge_array[] = { E(Sacramento, Reno), ... };<br><br> // Specify
the graph type. 指定图类型<br> typedef adjacency_list<vecS, vecS,
undirectedS> Graph;<br> // Create the graph object, based on the edges
in edge_array. 基于edge_array中的边创建图对象<br> Graph G(N, edge_array,
edge_array + sizeof(edge_array)/sizeof(E));<br><br> // DFS and BFS need
to "color" the vertices. DFS和BFS需要顶点的"颜色"<br> // Here we use
std::vector as exterior property storage. 我们用 std::vector 作为外部属性存
储<br> std::vector<default_color_type> colors(N);<br><br> cout
<< "*** Depth First ***" << endl;<br> depth_first_search(G,
city_visitor(names), colors.begin());<br> cout << endl;<br><br> //
Get the source vertex 取出源顶点<br>
boost::graph_traits<Graph>::vertex_descriptor <br> s =
vertex(SanJose, G);<br><br> cout << "*** Breadth First ***" <<
endl;<br> breadth_first_search(G, s, city_visitor(names),
colors.begin());<br><br> return 0;<br>}<br></pre>
+
+<h2><a name="sec:custom-exterior-property-maps"></a>
+Constructing an Exterior Property Map 构造一个外部属性映射
+</h2>
+
+<p>实现你自己的外部属性映射并不困难。你只需要重载你的类想要遵循的
+<a href="property_map.html">属性映射概念</a> 所要求的函数即可。多数情况
下，就是重载
+<tt>put()</tt> 和 <tt>get()</tt> 函数并实现
+<tt>operator[]</tt>。另外，你的属性映射类还需要带有针对
<tt>property_traits</tt> 中所定义的所有类型的嵌套 typedefs，或者你可以为你的
新属性映射类型创建一个特化的 <tt>property_traits</tt>。
+
+</p><p><tt>random_access_iterator_property_map</tt> 类的实现就是一个关于如
何构建外部属性映射的很好的例子。以下我们给出
+<tt>random_access_iterator_property_map</tt> 类的一个简化实现<tt></tt>，名
为 <tt>iterator_map</tt>。
+
+</p><p>我们从 <tt>iterator_map</tt> 类本身的定义开始。这个适配器类按被适配
的迭代器类型和ID属性映射来模板化。ID属性映射的任务是，将键对象(通常是一个顶
点描述符或边描述符)映射至一个整数偏移量。<tt>iterator_map</tt> 类需要三个有
关属性映射的 typedefs，分别为：<tt>key_type</tt>, <tt>value_type</tt>, 和
<tt>category</tt>。我们可以用
+<tt>property_traits</tt> 来找出 <tt>IDMap</tt> 的键类型，也可以用
<tt>iterator_traits</tt> 来确定
+<tt>Iterator</tt> 的值类型。我们选用
+<tt>boost::lvalue_property_map_tag</tt> 作为 category，因为我们计划实现
<tt>at()</tt> 函数。</p><pre> template <class Iterator, class
IDMap><br> class iterator_map<br> {<br> public:<br> typedef
typename boost::property_traits<IDMap>::key_type key_type; <br>
typedef typename std::iterator_traits<Iterator>::value_type
value_type;<br> typedef boost::lvalue_property_map_tag
category;<br><br> iterator_map(Iterator i = Iterator(),
<br> const IDMap& id = IDMap()) <br> : m_iter(i),
m_id(id) { }<br> Iterator m_iter;<br> IDMap m_id;<br> };<br></pre>
+
+<p>接下来，我们实现三个属性映射函数：<tt>get()</tt>,
+<tt>put()</tt>, 和 <tt>at()</tt>。在每个函数中，使用
+<tt>m_id</tt> 属性映射将键对象转换为整数偏移量，然后将此偏移量作为到随机访
问迭代器 <tt>m_iter</tt> 的偏移。</p><pre> template <class Iter, class
ID><br> typename std::iterator_traits<Iter>::value_type<br>
get(const iterator_map<Iter,ID>& i,<br> typename
boost::property_traits<ID>::key_type key)<br> {<br> return
i.m_iter[i.m_id[key]];<br> }<br> template <class Iter, class
ID><br> void<br> put(const iterator_map<Iter,ID>&
i,<br> typename boost::property_traits<ID>::key_type
key,<br> const typename
std::iterator_traits<Iter>::value_type& value)<br> {<br>
i.m_iter[i.m_id[key]] = value;<br> }<br> template <class Iter, class
ID><br> typename std::iterator_traits<Iter>::reference<br>
at(const iterator_map<Iter,ID>& i,<br> typename
boost::property_traits<ID>::key_type key)<br> {<br> return
i.m_iter[i.m_id[key]];<br> }<br></pre>
+
+<p>就是这样了。<tt>iterator_map</tt> 类已经完成了，可以象上一节中的
+<tt>random_access_iterator_property_map</tt> 那样使用了。<br>
+</p><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright © 2000-2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,
Indiana University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)
+</td></tr></tbody></table>
-</BODY>
-</HTML>
+</body></html>
\ No newline at end of file
Other related posts:
- » [boost-doc-zh commit] r277 - graph 库文档第8-9章 - codesite-noreply
