[boost-doc-zh commit] r276 - graph 库文档第1-7章，由felurkinda翻译，alai04校验。

From: codesite-noreply@xxxxxxxxxx
To: boost-doc-zh-notify@xxxxxxxxxxxxx
Date: Fri, 26 Jun 2009 07:13:07 +0000

Author: alai04
Date: Fri Jun 26 00:01:13 2009
New Revision: 276

Added:
   trunk/libs/graph/example/edmonds-karp-eg.cpp
   trunk/libs/graph/example/graph-thingie.cpp
   trunk/libs/graph/example/r_c_shortest_paths_example.cpp
Removed:
   trunk/libs/graph/example/edmunds-karp-eg.cpp
Modified:
   trunk/libs/graph/doc/acknowledgements.html
   trunk/libs/graph/doc/graph_theory_review.html
   trunk/libs/graph/doc/history.html
   trunk/libs/graph/doc/index.html
   trunk/libs/graph/doc/publications.html
   trunk/libs/graph/doc/quick_tour.html
   trunk/libs/graph/doc/table_of_contents.html
   trunk/libs/graph/doc/users.html
   trunk/libs/graph/example/accum-compile-times.cpp
   trunk/libs/graph/example/actor_clustering.cpp
   trunk/libs/graph/example/adj_list_ra_edgelist.cpp
   trunk/libs/graph/example/adjacency_list.cpp
   trunk/libs/graph/example/adjacency_list.expected
   trunk/libs/graph/example/adjacency_list_io.cpp
   trunk/libs/graph/example/adjacency_matrix.cpp
   trunk/libs/graph/example/astar-cities.cpp
   trunk/libs/graph/example/bcsstk01
   trunk/libs/graph/example/bcsstk01.rsa
   trunk/libs/graph/example/bellman-example.cpp
   trunk/libs/graph/example/bellman-ford-internet.cpp
   trunk/libs/graph/example/bellman_ford.expected
   trunk/libs/graph/example/bfs-example.cpp
   trunk/libs/graph/example/bfs-example2.cpp
   trunk/libs/graph/example/bfs-name-printer.cpp
   trunk/libs/graph/example/bfs.cpp
   trunk/libs/graph/example/bfs.expected
   trunk/libs/graph/example/bfs_basics.expected
   trunk/libs/graph/example/bfs_neighbor.cpp
   trunk/libs/graph/example/biconnected_components.cpp
   trunk/libs/graph/example/boost_web.dat
   trunk/libs/graph/example/boost_web_graph.cpp
   trunk/libs/graph/example/boost_web_graph.expected
   trunk/libs/graph/example/bucket_sorter.cpp
   trunk/libs/graph/example/canonical_ordering.cpp
   trunk/libs/graph/example/cc-internet.cpp
   trunk/libs/graph/example/city_visitor.cpp
   trunk/libs/graph/example/components_on_edgelist.cpp
   trunk/libs/graph/example/components_on_edgelist.expected
   trunk/libs/graph/example/connected-components.cpp
   trunk/libs/graph/example/connected_components.cpp
   trunk/libs/graph/example/connected_components.expected
   trunk/libs/graph/example/container_gen.cpp
   trunk/libs/graph/example/copy-example.cpp
   trunk/libs/graph/example/csr-example.cpp
   trunk/libs/graph/example/cuthill_mckee_ordering.cpp
   trunk/libs/graph/example/cuthill_mckee_ordering.expected
   trunk/libs/graph/example/cycle-file-dep.cpp
   trunk/libs/graph/example/cycle-file-dep2.cpp
   trunk/libs/graph/example/cycle_ratio_example.cpp
   trunk/libs/graph/example/dag_shortest_paths.cpp
   trunk/libs/graph/example/data1.txt
   trunk/libs/graph/example/data2.txt
   trunk/libs/graph/example/data3.txt
   trunk/libs/graph/example/dave.cpp
   trunk/libs/graph/example/dave.expected
   trunk/libs/graph/example/default-constructor.cpp
   trunk/libs/graph/example/default-constructor2.cpp
   trunk/libs/graph/example/dfs-example.cpp
   trunk/libs/graph/example/dfs-parenthesis.cpp
   trunk/libs/graph/example/dfs.cpp
   trunk/libs/graph/example/dfs.expected
   trunk/libs/graph/example/dfs_basics.expected
   trunk/libs/graph/example/dfs_parenthesis.cpp
   trunk/libs/graph/example/dfs_parenthesis.expected
   trunk/libs/graph/example/dijkstra-example-listS.cpp
   trunk/libs/graph/example/dijkstra-example.cpp
   trunk/libs/graph/example/dijkstra.expected
   trunk/libs/graph/example/edge-connectivity.cpp
   trunk/libs/graph/example/edge-function.cpp
   trunk/libs/graph/example/edge-iter-constructor.cpp
   trunk/libs/graph/example/edge_basics.cpp
   trunk/libs/graph/example/edge_basics.expected
   trunk/libs/graph/example/edge_connectivity.cpp
   trunk/libs/graph/example/edge_iterator_constructor.cpp
   trunk/libs/graph/example/edge_iterator_constructor.dat
   trunk/libs/graph/example/edge_property.cpp
   trunk/libs/graph/example/edge_property.expected
   trunk/libs/graph/example/exterior_properties.cpp
   trunk/libs/graph/example/exterior_properties.expected
   trunk/libs/graph/example/exterior_property_map.cpp
   trunk/libs/graph/example/exterior_property_map.expected
   trunk/libs/graph/example/family-tree-eg.cpp
   trunk/libs/graph/example/family_tree.expected
   trunk/libs/graph/example/fibonacci_heap.cpp
   trunk/libs/graph/example/fibonacci_heap.expected
   trunk/libs/graph/example/figs/cc-internet.dot
   trunk/libs/graph/example/figs/dfs-example.dot
   trunk/libs/graph/example/figs/edge-connectivity.dot
   trunk/libs/graph/example/figs/ospf-graph.dot
   trunk/libs/graph/example/figs/scc.dot
   trunk/libs/graph/example/figs/telephone-network.dot
   trunk/libs/graph/example/file_dependencies.cpp
   trunk/libs/graph/example/file_dependencies.expected
   trunk/libs/graph/example/filtered-copy-example.cpp
   trunk/libs/graph/example/filtered_graph.cpp
   trunk/libs/graph/example/filtered_graph.expected
   trunk/libs/graph/example/filtered_graph_edge_range.cpp
   trunk/libs/graph/example/filtered_vec_as_graph.cpp
   trunk/libs/graph/example/fr_layout.cpp
   trunk/libs/graph/example/gerdemann.cpp
   trunk/libs/graph/example/gerdemann.expected
   trunk/libs/graph/example/girth.cpp
   trunk/libs/graph/example/graph-assoc-types.cpp
   trunk/libs/graph/example/graph-property-iter-eg.cpp
   trunk/libs/graph/example/graph.cpp
   trunk/libs/graph/example/graph_as_tree.cpp
   trunk/libs/graph/example/graph_property.cpp
   trunk/libs/graph/example/graphviz.cpp
   trunk/libs/graph/example/graphviz_example.dot
   trunk/libs/graph/example/graphviz_test.dot
   trunk/libs/graph/example/in_edges.cpp
   trunk/libs/graph/example/in_edges.expected
   trunk/libs/graph/example/incremental-components-eg.cpp
   trunk/libs/graph/example/incremental_components.cpp
   trunk/libs/graph/example/incremental_components.expected
   trunk/libs/graph/example/interior_pmap_bundled.cpp
   trunk/libs/graph/example/interior_property_map.cpp
   trunk/libs/graph/example/interior_property_map.expected
   trunk/libs/graph/example/iohb.c
   trunk/libs/graph/example/iohb.h
   trunk/libs/graph/example/isomorphism.cpp
   trunk/libs/graph/example/iteration_macros.cpp
   trunk/libs/graph/example/iterator-property-map-eg.cpp
   trunk/libs/graph/example/johnson-eg.cpp
   trunk/libs/graph/example/johnson.expected
   trunk/libs/graph/example/kevin-bacon.cpp
   trunk/libs/graph/example/kevin-bacon.dat
   trunk/libs/graph/example/kevin-bacon2.cpp
   trunk/libs/graph/example/kevin-bacon2.expected
   trunk/libs/graph/example/kevin_bacon.expected
   trunk/libs/graph/example/king_ordering.cpp
   trunk/libs/graph/example/knights-tour.cpp
   trunk/libs/graph/example/knights_tour.expected
   trunk/libs/graph/example/kolmogorov-eg.cpp
   trunk/libs/graph/example/kruskal-example.cpp
   trunk/libs/graph/example/kruskal-telephone.cpp
   trunk/libs/graph/example/kruskal.expected
   trunk/libs/graph/example/kuratowski_subgraph.cpp
   trunk/libs/graph/example/last-mod-time.cpp
   trunk/libs/graph/example/leda-concept-check.cpp
   trunk/libs/graph/example/leda-graph-eg.cpp
   trunk/libs/graph/example/leda-regression.cfg
   trunk/libs/graph/example/loops_dfs.cpp
   trunk/libs/graph/example/make_biconnected_planar.cpp
   trunk/libs/graph/example/make_connected.cpp
   trunk/libs/graph/example/make_maximal_planar.cpp
   trunk/libs/graph/example/makefile-dependencies.dat
   trunk/libs/graph/example/makefile-target-names.dat
   trunk/libs/graph/example/matching_example.cpp
   trunk/libs/graph/example/max_flow.cpp
   trunk/libs/graph/example/max_flow.dat
   trunk/libs/graph/example/max_flow.expected
   trunk/libs/graph/example/max_flow2.dat
   trunk/libs/graph/example/max_flow3.dat
   trunk/libs/graph/example/max_flow4.dat
   trunk/libs/graph/example/max_flow5.dat
   trunk/libs/graph/example/max_flow6.dat
   trunk/libs/graph/example/max_flow7.dat
   trunk/libs/graph/example/max_flow8.dat
   trunk/libs/graph/example/max_flow9.dat
   trunk/libs/graph/example/miles_span.cpp
   trunk/libs/graph/example/miles_span.expected
   trunk/libs/graph/example/min_max_paths.cpp
   trunk/libs/graph/example/minimum_degree_ordering.cpp
   trunk/libs/graph/example/modify_graph.cpp
   trunk/libs/graph/example/neighbor_bfs.cpp
   trunk/libs/graph/example/ordered_out_edges.cpp
   trunk/libs/graph/example/ordered_out_edges.expected
   trunk/libs/graph/example/ospf-example.cpp
   trunk/libs/graph/example/parallel-compile-time.cpp
   trunk/libs/graph/example/planar_face_traversal.cpp
   trunk/libs/graph/example/prim-example.cpp
   trunk/libs/graph/example/prim-telephone.cpp
   trunk/libs/graph/example/prim.expected
   trunk/libs/graph/example/print-adjacent-vertices.cpp
   trunk/libs/graph/example/print-edges.cpp
   trunk/libs/graph/example/print-in-edges.cpp
   trunk/libs/graph/example/print-out-edges.cpp
   trunk/libs/graph/example/property-map-traits-eg.cpp
   trunk/libs/graph/example/property_iterator.cpp
   trunk/libs/graph/example/push-relabel-eg.cpp
   trunk/libs/graph/example/put-get-helper-eg.cpp
   trunk/libs/graph/example/quick-tour.cpp
   trunk/libs/graph/example/quick_tour.cpp
   trunk/libs/graph/example/quick_tour.expected
   trunk/libs/graph/example/reachable-loop-head.cpp
   trunk/libs/graph/example/reachable-loop-tail.cpp
   trunk/libs/graph/example/read_graphviz.cpp
   trunk/libs/graph/example/read_write_dimacs-eg.cpp
   trunk/libs/graph/example/regression.cfg
   trunk/libs/graph/example/remove_edge_if_bidir.cpp
   trunk/libs/graph/example/remove_edge_if_bidir.expected
   trunk/libs/graph/example/remove_edge_if_dir.cpp
   trunk/libs/graph/example/remove_edge_if_dir.expected
   trunk/libs/graph/example/remove_edge_if_undir.cpp
   trunk/libs/graph/example/remove_edge_if_undir.expected
   trunk/libs/graph/example/reverse-graph-eg.cpp
   trunk/libs/graph/example/reverse_graph.expected
   trunk/libs/graph/example/roget_components.cpp
   trunk/libs/graph/example/scc.cpp
   trunk/libs/graph/example/scc.dot
   trunk/libs/graph/example/sgb-regression.cfg
   trunk/libs/graph/example/simple_planarity_test.cpp
   trunk/libs/graph/example/sloan_ordering.cpp
   trunk/libs/graph/example/straight_line_drawing.cpp
   trunk/libs/graph/example/strong-components.cpp
   trunk/libs/graph/example/strong_components.cpp
   trunk/libs/graph/example/strong_components.expected
   trunk/libs/graph/example/subgraph.cpp
   trunk/libs/graph/example/subgraph.expected
   trunk/libs/graph/example/subgraph_properties.cpp
   trunk/libs/graph/example/target-compile-costs.dat
   trunk/libs/graph/example/tc.dot
   trunk/libs/graph/example/test-astar-cities.dot
   trunk/libs/graph/example/topo-sort-file-dep.cpp
   trunk/libs/graph/example/topo-sort-file-dep2.cpp
   trunk/libs/graph/example/topo-sort-with-leda.cpp
   trunk/libs/graph/example/topo-sort-with-sgb.cpp
   trunk/libs/graph/example/topo-sort1.cpp
   trunk/libs/graph/example/topo-sort2.cpp
   trunk/libs/graph/example/topo_sort.cpp
   trunk/libs/graph/example/topo_sort.expected
   trunk/libs/graph/example/transitive_closure.cpp
   trunk/libs/graph/example/transpose-example.cpp
   trunk/libs/graph/example/undirected.cpp
   trunk/libs/graph/example/undirected.expected
   trunk/libs/graph/example/undirected_dfs.cpp
   trunk/libs/graph/example/vector-as-graph.cpp
   trunk/libs/graph/example/vector_as_graph.expected
   trunk/libs/graph/example/vertex-name-property.cpp
   trunk/libs/graph/example/vertex_basics.cpp
   trunk/libs/graph/example/vertex_basics.expected
   trunk/libs/graph/example/visitor.cpp
   trunk/libs/graph/example/visitor.expected
   trunk/libs/graph/example/write_graphviz.cpp

Log:
graph 库文档第1-7章，由felurkinda翻译，alai04校验。
更新 example 目录

Modified: trunk/libs/graph/doc/acknowledgements.html
==============================================================================
--- trunk/libs/graph/doc/acknowledgements.html  (original)
+++ trunk/libs/graph/doc/acknowledgements.html  Fri Jun 26 00:01:13 2009
@@ -1,22 +1,20 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

+<html><head><meta content="text/html; charset=UTF-8"http-equiv="content-type"><!--

   -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
   --
   -- Distributed under the Boost Software License, Version 1.0.
   -- (See accompanying file LICENSE_1_0.txt or copy at
   -- http://www.boost.org/LICENSE_1_0.txt)
   -->
-<Head>
-<Title>Boost Graph Library: Acknowledgements</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
-        ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
-     ALT="C++ Boost" width="277" height="86">
+<title>Boost Graph Library: Acknowledgements</title></head>

-<BR Clear>

+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"vlink="#551a8b">

+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">

+<br clear="">

-<h1>Acknowledgements</h1>
+
+<h1>Acknowledgements 鸣谢</h1>

 We owe many debts of thanks to a number of individuals who both
 inspired and encouraged us in developing the Boost Graph Library.
@@ -26,32 +24,32 @@
 work in generic programming, for his encouragement, and for his
 algorithm contributions to the BGL.  We thank Matthew Austern for his
 work on documenting the concepts of STL which provided a foundation
-for creating the concepts in the BGL. We thank Dietmar K&uuml;hl for
+for creating the concepts in the BGL. We thank Dietmar Kühl for
 his work on generic graph algorithms and design patterns; especially
 for the property map abstraction.

-<p>
+</p><p>
 Dave Abrahams, Jens Maurer, Beman Dawes, Gary Powell, Greg Colvin,
 Valentin Bonnard, and the rest of the group at Boost provided valuable
 input to the BGL interface, numerous suggestions for improvement,
 proof reads of the documentation, and help with polishing the code.  A
 special thanks to Dave Abrahams for managing the formal review.

-<p>
+</p><p>
 We also thank the following BGL users whose questions helped to
 improve the BGL: Gordon Woodhull, Dave Longhorn, Joel Phillips, and
 Edward Luke.

-<p>
+</p><p>
 A special thanks to Jeffrey Squyres for editing and proof reading
 of the documentation.

-<p>
+</p><p>
 Our original work on the Boost Graph Library was supported in part by
 NSF grant ACI-9982205 and by the Director, Office of Science, Division
 of Mathematical, Information, and Computational Sciences of the U.S.
 Department of Energy under contract number DE-AC03-76SF00098.
-<p>
+</p><p>
 In our work we also used resources of the National Energy Research
 Scientific Computing Center, which is supported by the Office of
 Science of the U.S. Department of Energy.
@@ -59,18 +57,15 @@


 <br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
-Indiana University (<A
-HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>

-<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>,Indiana University (<AHREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>) 

-<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
-Indiana University (<A
-HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+</p><hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright (c) 2000-2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,

+Indiana University (<ahref="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>) +<a href="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</a>,Indiana University (<ahref="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</a>) 

+<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       Fri Jun 26 00:01:13 2009
@@ -1,590 +1,315 @@
-<HTML>
-<!--
-  -- 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: Graph Theory Review</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>Review of Elementary Graph Theory</H1>
-
-<P>
-
-<P>
-This chapter is meant as a refresher on elementary graph theory. If
-the reader has some previous acquaintance with graph algorithms, this
-chapter should be enough to get started.  If the reader has no
-previous background in graph algorithms we suggest a more thorough
-introduction such as <a
-href="http://toc.lcs.mit.edu/~clr/";>Introduction to Algorithms</a>
-by Cormen, Leiserson, and Rivest.
-
-<P>
-
-<H1>The Graph Abstraction</H1>
-
-<P>
-A graph is a mathematical abstraction that is useful for solving many
-kinds of problems. Fundamentally, a graph consists of a set of
-vertices, and a set of edges, where an edge is something that connects
-two vertices in the graph. More precisely, a <a
-name="def:graph"><I>graph</I></a> is a pair <i>(V,E)</i>, where
-<i>V</i> is a finite set and <i>E</i> is a binary relation on
-<i>V</i>. <i>V</i> is called a <a name="def:vertex-set"><I>vertex
-set</I></a> whose elements are called <I>vertices</I>.  <i>E</i> is a
-collection of edges, where an <a name="def:edge"><I>edge</I></a> is a
-pair <i>(u,v)</i> with <i>u,v</i> in <i>V</i>.  In a <a
-name="def:directed-graph"><I>directed graph</I></a>, edges are ordered
-pairs, connecting a <a name="def:source"><I>source</I></a> vertex to a
-<a name="def:target"><I>target</I></a> vertex. In an <a
-name="def:undirected-graph"><I>undirected graph</I></a> edges are
-unordered pairs and connect the two vertices in both directions, hence
-in an undirected graph <i>(u,v)</i> and <i>(v,u)</i> are two ways of
-writing the same edge.
-
-<P>
-This definition of a graph is vague in certain respects; it does not
-say what a vertex or edge represents. They could be cities with
-connecting roads, or web-pages with hyperlinks. These details are left
-out of the definition of a graph for an important reason; they are not
-a necessary part of the graph <I>abstraction</I>. By leaving out the
-details we can construct a theory that is reusable, that can help us
-solve lots of different kinds of problems.
-
-<P>
-Back to the definition: a graph is a set of vertices and edges.  For
-purposes of demonstration, let us consider a graph where we have
-labeled the vertices with letters, and we write an edge simply as a
-pair of letters. Now we can write down an example of a directed graph
-as follows:
-
-<P>
-<BR>
-<DIV ALIGN="center">
-<table><tr><td><tt>
-V = {v, b, x, z, a, y } <br>
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>
+<meta content="text/html; charset=UTF-8" http-equiv="content-type">

+<title>Boost GraphLibrary: Graph Theory Review</title>

+
+</head>

+<h1>图论基础回顾<br>
+</h1>

+本章将回顾一下图论的基本理论。如果读者以前接触过图算法，那么可以便可以马上开始本章的学习；如果读者以前没有相关图算法背景知识，+我们建议最好还是对其有一个了解，可以去看Cormen, Leiserson, 和Rivest写的<ahref="http://toc.lcs.mit.edu/%7Eclr/";>Introduction to

+Algorithms</a>(《算法导论》)。</p>
+<h1>图抽象<br>
+</h1>

+图是用来解决各种实际问题的数学抽象。从根本上说，一个图是由一组顶点集合和一组边集合组成的，其中，一条边连接图中两个顶点。更准确的描述是，一个图是+一个（V，E）对，V是一个有限集，e是表示V的二元关系。V被称作顶点集,其中的元素统称为vertices。E是边的集合，一条边是一个(u,v)+对，u,v分别是顶点集V中的元素。在一个有向图中，边是一个连接源点和目标点的有序对。在一个无向图中，边是一个无序对，仅仅连接两个顶点，因此在无向

+图
+中（u，v）和（v，u）是相同的。<br>
+<br>

+以上对于图的定义在某些方面有点含糊不清，例如，没有说清顶点和边到底表示什么。他们可能是城市和连接城市的公路；亦或是网页和链接网页的超链接。这些细+节不被考虑到定义中是有原因的，它们不属于图抽象的部分。通过省略这些细节，我们能够建立一个可复用的原理，它能够帮我们解决各种不同的问题。 

+<br>

+回到我们的定义：图是一组顶点和边的集合。演示一下，我们来建立一个图，该图顶点已经用字母标好，因此边可以简单的写成一个字母对。现在我们可以写出一个

+有向图，如下：<br>
+<div align="center">
+<table>
+<tbody>
+<tr>
+<td><tt>V = {v, b, x, z, a, y } <br>
 E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) } <br>
-G = (V, E)
-</tt></td></tr></table>
-</DIV>
-<BR CLEAR="ALL"><P></P>
-
-
-<P>
-<A HREF="#fig:directed-graph">Figure 1</A> gives a pictorial view of
-this graph.  The edge <i>(x,x)</i> is called a <a
-name="def:self-loop"><I>self-loop</I></a>.  Edges <i>(b,y)</i> and
-<i>(b,y)</i> are <I>parallel edges</I>, which are allowed in a <a
-name="def:multigraph"><I>multigraph</I></a> (but are normally not
-allowed in a directed or undirected graph).
-
-<P>
-
-<P></P>
-<DIV ALIGN="center"><A NAME="fig:directed-graph"></A><A NAME="1509"></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG>
-Example of a directed graph.</CAPTION>
-<TR><TD><IMG SRC="./figs/digraph.gif" width="124" height="163"></TD></TR>
-</TABLE>
-</DIV><P></P>
-
-<P>
-Next we have a similar graph, though this time it is undirected.  <A
-HREF="#fig:undirected-graph">Figure 2</A> gives the pictorial view.
-Self loops are not allowed in undirected graphs. This graph is the <a
-name="def:undirected-version"><I>undirected version</i></a. of the the
-previous graph (minus the parallel edge <i>(b,y)</i>), meaning it has
-the same vertices and the same edges with their directions removed.
-Also the self edge has been removed, and edges such as <i>(a,z)</i>
-and <i>(z,a)</i> are collapsed into one edge. One can go the other
-way, and make a <a name="def:directed-version"><I>directed version</i>
-of an undirected graph be replacing each edge by two edges, one
-pointing in each direction.
-
-<P>
-<BR>
-<DIV ALIGN="CENTER">
-<table><tr><td><tt>
-V = {v, b, x, z, a, y }<br>
+G = (V, E) </tt></td>
+</tr>
+</tbody>
+</table>
+</div>
+<br>
+<p>
+<a href="#fig:directed-graph">图一</a>

+是该图的图示版。边（x，x）叫做自环。边（b，y）和另一条（b，y）边是平行边，平行边仅仅出现在多重图中（一般有向图和无向图是不允许出现的）。

+<div align="center"><a name="fig:directed-graph"></a><a name="1509"></a>
+<table>
+<caption align="bottom"><strong>图 1:</strong>
+一个有向图的例子</caption> <tbody>
+<tr>
+<td><img src="./figs/digraph.gif" height="163" width="124"></td>
+</tr>
+</tbody>
+</table>
+</div>

+下面我们将演示一个与图一相似的图，不过这次是无向的。<ahref="graph_theory_review.html#fig:undirected-graph">图二</a>是+该图的图示。自环是不允许出现在无向图中的。该图是边（b，y）的无向版本，相同的顶点和去除方向的边。相同的边被删除，有些边被合并，比如（a，z）和

+（z，a）。无向图的有向版本是把其中每条边换成两条，每一条指向一个方向。<br>
+</p>
+<div align="center">
+<table>
+<tbody>
+<tr>
+<td><tt>V = {v, b, x, z, a, y }<br>
 E = { (b,y), (y,v), (z,a), (b,x), (x,v) }<br>
-G = (V, E)
-</tt></td></tr></table>
-</DIV>
-<BR CLEAR="ALL"><P></P>
-
-<P>
-
-<P></P>
-<DIV ALIGN="CENTER"><A NAME="fig:undirected-graph"></A><A NAME="1524"></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Figure 2:</STRONG>
-Example of an undirected graph.</CAPTION>
-<TR><TD><IMG SRC="./figs/undigraph.gif" width="103" height="163"></TD></TR>
-</TABLE>
-</DIV><P></P>
-
-<P>
-Now for some more graph terminology. If some edge <i>(u,v)</i> is in
-graph , then vertex <i>v</i> is <a
-name="def:adjacent"><I>adjacent</I></a> to vertex <i>u</i>.  In a
-directed graph, edge <i>(u,v)</i> is an <a
-name="def:out-edge"><I>out-edge</I></a> of vertex <i>u</i> and an <a
-name="def:in-edge"><I>in-edge</I></a> of vertex <i>v</i>. In an
-undirected graph edge <i>(u,v)</i> is <a
-name="def:incident-on"><I>incident on</I></a> vertices <i>u</i> and
-<i>v</i>.
-
-<P>
-In <A HREF="#fig:directed-graph">Figure 1</A>,
- vertex <i>y</i> is adjacent to vertex <i>b</i> (but <i>b</i> is not
- adjacent to <i>y</i>). The edge <i>(b,y)</i> is an out-edge of
- <i>b</i> and an in-edge of <i>y</i>. In <A
- HREF="#fig:undirected-graph">Figure 2</A>,
- <i>y</i> is adjacent to <i>b</i> and vice-versa. The edge
- <i>(y,b)</i> is incident on vertices <i>y</i> and <i>b</i>.
-
-<P>
-In a directed graph, the number of out-edges of a vertex is its <a
-name="def:out-degree"><I>out-degree</I></a> and the number of in-edges
-is its <a name="def:in-degree"><I>in-degree</I></a>.  For an
-undirected graph, the number of edges incident to a vertex is its <a
-name="def:degree"><I>degree</I></a>. In <A
-HREF="#fig:directed-graph">Figure 1</A>, vertex <i>b</i> has an
-out-degree of 3 and an in-degree of zero. In <A
-HREF="#fig:undirected-graph">Figure 2</A>, vertex <i>b</i> simply has
-a degree of 2.
-
-<P>
-Now a <a name="def:path"><i>path</i></a> is a sequence of edges in a
-graph such that the target vertex of each edge is the source vertex of
-the next edge in the sequence. If there is a path starting at vertex
-<i>u</i> and ending at vertex <i>v</i> we say that <i>v</i> is <a
-name="def:reachable"><i>reachable</i></a> from <i>u</i>.  A path is <a
-name="def:simple-path"><I>simple</I></a> if none of the vertices in
-the sequence are repeated. The path &lt;(b,x), (x,v)&gt; is simple,
-while the path &lt;(a,z), (z,a)&gt; is not. Also, the path &lt;(a,z),
-(z,a)&gt; is called a <a name="def:cycle"><I>cycle</I></a> because the
-first and last vertex in the path are the same. A graph with no cycles
-is <a name="def:acyclic"><I>acyclic</I></a>.
-
-<P>
-A <a name="def:planar-graph"><I>planar graph</I></a> is a graph that
-can be drawn on a plane without any of the edges crossing over each
-other. Such a drawing is called a <I>plane graph</I>. A <a
-name="def:face"><I>face</I></a> of a plane graph is a connected region
-of the plane surrounded by edges. An important property of planar
-graphs is that the number of faces, edges, and vertices are related
-through Euler's formula: <i>|F| - |E| + |V| = 2</i>. This means that a
-simple planar graph has at most <i>O(|V|)</i> edges.
-
-<P>
-
-<P>
-
-<H1>Graph Data Structures</H1>
-
-<P>
-The primary property of a graph to consider when deciding which data
-structure to use is <I>sparsity</I>, the number of edges relative to
-the number of vertices in the graph. A graph where <i>E</i> is close
-to </i>V<sup>2</sup></i> is a <I>dense</I> graph, whereas a graph
-where <i>E = alpha V</i> and <i>alpha</i> is much smaller than
-<i>V</i> is a <I>sparse</I> graph. For dense graphs, the
-<I>adjacency-matrix representation</I> is usually the best choice,
-whereas for sparse graphs the <I>adjacency-list representation</I> is
-a better choice. Also the <I>edge-list representation</I> is a space
-efficient choice for sparse graphs that is appropriate in some
-situations.
-
-<P>
-
-<H2>Adjacency Matrix Representation</H2>
-
-<P>
-An adjacency-matrix representation of a graph is a 2-dimensional <i>V
-x V</i> array. Each element in the array <i>a<sub>uv</sub></i> stores
-a Boolean value saying whether the edge <i>(u,v)</i> is in the graph.
-<A HREF="#fig:adj-matrix">Figure 3</A> depicts an adjacency matrix for
-the graph in <A HREF="#fig:directed-graph">Figure 1</A> (minus the
-parallel edge <i>(b,y)</i>).  The ammount of space required to store
-an adjacency-matrix is <i>O(V<sup>2</sup>)</i>. Any edge can be
-accessed, added, or removed in <i>O(1)</i> time.  To add or remove a
-vertex requires reallocating and copying the whole graph, an
-<i>O(V<sup>2</sup>)</i> operation.  The <a
-href="./adjacency_matrix.html"><tt>adjacency_matrix</tt></a> class
-implements the BGL graph interface in terms of the adjacency-matrix
-data-structure.
-
-
-<P>
-
-<P></P>
-<DIV ALIGN="CENTER"><A NAME="fig:adj-matrix"></A><A NAME="1701"></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Figure 3:</STRONG>
-The Adjacency Matrix Graph Representation.</CAPTION>

-<TR><TD><IMG SRC="./figs/adj_matrix.gif" width="136"height="135"></TD></TR>

-</TABLE>
-</DIV><P></P>
-
-<P>
-
-<H2><A NAME="sec:adjacency-list-representation"></A>
-Adjacency List Representation
-</H2>
-
-<P>
-An adjacency-list representation of a graph stores an out-edge
-sequence for each vertex. For sparse graphs this saves space since
-only <i>O(V + E)</i> memory is required. In addition, the out-edges
-for each vertex can be accessed more efficiently. Edge insertion is
-<i>O(1)</i>, though accessing any given edge is <i>O(alpha)</i>, where
-<i>alpha</i> is the sparsity factor of the matrix (which is equal to
-the maximum number of out-edges for any vertex in the graph).  <A
-HREF="#fig:adj-list">Figure 4</A> depicts an
-adjacency-list representation of the graph in <A
-HREF="#fig:directed-graph">Figure 1</A>. The
-<a href="./adjacency_list.html"><TT>adjacency_list</TT></a> class is
-an implementation of the adjacency-list representation.
-
-<P>
-
-<P></P>
-<DIV ALIGN="CENTER"><A NAME="fig:adj-list"></A><A NAME="1713"></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Figure 4:</STRONG>
-The Adjacency List Graph Representation.</CAPTION>
-<TR><TD><IMG SRC="./figs/adj_list.gif" width="108" height="122"></TD></TR>
-</TABLE>
-</DIV><P></P>
-
-<P>
-
-<H2>Edge List Representation</H2>
-
-<P>
-An edge-list representation of a graph is simply a sequence of edges,
-where each edge is represented as a pair of vertex ID's.  The memory
-required is only <i>O(E)</i>. Edge insertion is typically <i>O(1)</i>,
-though accessing a particular edge is <i>O(E)</i> (not efficient).  <A
-HREF="#fig:edge-list">Figure 5</A> shows an
-edge-list representation of the graph in <A
-HREF="#fig:directed-graph">Figure 1</A>. The
-<a href="./edge_list.html"><TT>edge_list</TT></a> adaptor class can be
-used to create implementations of the edge-list representation.
-
-<P>
-
-<P></P>
-<DIV ALIGN="CENTER"><A NAME="fig:edge-list"></A><A NAME="1724"></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Figure 5:</STRONG>
-The Edge List Graph Representation.</CAPTION>
-<TR><TD><IMG SRC="./figs/edge_list.gif" width="322" height="22"></TD></TR>
-</TABLE>
-</DIV><P></P>
-
-
-<P>
-
-<H1>Graph Algorithms</H1>
-
-<P>
-
-<H2>Graph Search Algorithms</H2>
-
-<P>
-<I>Tree edges</I> are edges in the search tree (or forest) constructed
-(implicitly or explicitly) by running a graph search algorithm over a
-graph.  An edge <i>(u,v)</i> is a tree edge if <i>v</i> was first
-discovered while exploring (corresponding to the <a
-href="./visitor_concepts.html">visitor</a> <TT>explore()</TT> method)
-edge <i>(u,v)</i>. <I>Back edges</I> connect vertices to their
-ancestors in a search tree. So for edge <i>(u,v)</i> the vertex
-<i>v</i> must be the ancestor of vertex <i>u</i>. Self loops are
-considered to be back edges. <I>Forward edges</I> are non-tree edges
-<i>(u,v)</i> that connect a vertex <i>u</i> to a descendant <i>v</i>
-in a search tree.  <I>Cross edges</I> are edges that do not fall into
-the above three categories.
-
-<P>
-
-<H2><A NAME="sec:bfs-algorithm"></A>
-Breadth-First Search
-</H2>
-
-<P>
-Breadth-first search is a traversal through a graph that touches all
-of the vertices reachable from a particular source vertex. In
-addition, the order of the traversal is such that the algorithm will
-explore all of the neighbors of a vertex before proceeding on to the
-neighbors of its neighbors. One way to think of breadth-first search
-is that it expands like a wave emanating from a stone dropped into a
-pool of water.  Vertices in the same ``wave'' are the same distance
-from the source vertex. A vertex is <I>discovered</I> the first time
-it is encountered by the algorithm. A vertex is <I>finished</I> after
-all of its neighbors are explored. Here's an example to help make this
-clear. A graph is shown in <A
-HREF="#fig:bfs-example">Figure 6</A> and the
-BFS discovery and finish order for the vertices is shown below.
-
-<P>
-
-<P></P>
-<DIV ALIGN="CENTER"><A NAME="fig:bfs-example"></A><A NAME="1826"></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Figure 6:</STRONG>
-Breadth-first search spreading through a graph.</CAPTION>

-<TR><TD><IMG SRC="./figs/bfs_example.gif" width="242"height="143"></TD></TR>

-</TABLE>
-</DIV><P></P>
-
-<P>
-<PRE>
-  order of discovery: s r w v t x u y
-  order of finish: s r w v t x u y
-</PRE>
-
-<P>
-We start at vertex , and first visit <i>r</i> and <i>w</i> (the two
-neighbors of ). Once both neighbors of are visited, we visit the
-neighbor of <i>r</i> (vertex <i>v</i>), then the neighbors of <i>w</i>
-(the discovery order between <i>r</i> and <i>w</i> does not matter)
-which are <i>t</i> and <i>x</i>. Finally we visit the neighbors of
-<i>t</i> and <i>x</i>, which are <i>u</i> and <i>y</i>.
-
-<P>
-For the algorithm to keep track of where it is in the graph, and which
-vertex to visit next, BFS needs to color the vertices (see the section
-on <a href="./using_property_maps.html">Property Maps</a>
-for more details about attaching properties to graphs). The place to
-put the color can either be inside the graph, or it can be passed into
-the algorithm as an argument.
-
-<P>
-
-<H2><A NAME="sec:dfs-algorithm"></A>
-Depth-First Search
-</H2>
-
-<P>
-A depth first search (DFS) visits all the vertices in a graph. When
-choosing which edge to explore next, this algorithm always chooses to
-go ``deeper'' into the graph. That is, it will pick the next adjacent
-unvisited vertex until reaching a vertex that has no unvisited
-adjacent vertices. The algorithm will then backtrack to the previous
-vertex and continue along any as-yet unexplored edges from that
-vertex. After DFS has visited all the reachable vertices from a
-particular source vertex, it chooses one of the remaining undiscovered
-vertices and continues the search. This process creates a set of
-<I>depth-first trees</I> which together form the <I>depth-first
- forest</I>. A depth-first search categorizes the edges in the graph
-into three categories: tree-edges, back-edges, and forward or
-cross-edges (it does not specify which).  There are typically many
-valid depth-first forests for a given graph, and therefore many
-different (and equally valid) ways to categorize the edges.
-
-<P>
-One interesting property of depth-first search is that the discover
-and finish times for each vertex form a parenthesis structure.  If we
-use an open-parenthesis when a vertex is discovered, and a
-close-parenthesis when a vertex is finished, then the result is a
-properly nested set of parenthesis.  <A
-HREF="#fig:dfs-example">Figure 7</A> shows
-DFS applied to an undirected graph, with the edges labeled in the
-order they were explored.  Below we list the vertices of the graph

-ordered by discover and finish time, as well as show the parenthesisstructure. DFS is used as the kernel for several other graph

-algorithms, including topological sort and two of the connected
-component algorithms. It can also be used to detect cycles (see the <A
-HREF="file_dependency_example.html#sec:cycles">Cylic Dependencies </a>
-section of the File Dependency Example).
-
-<P>
-
-<P></P>
-<DIV ALIGN="CENTER"><A NAME="fig:dfs-example"></A><A NAME="1841"></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Figure 7:</STRONG>
-Depth-first search on an undirected graph.</CAPTION>
-<TR><TD><IMG SRC="./figs/dfs.gif" width="141" height="204"></TD></TR>
-</TABLE>
-</DIV><P></P>
-
-<P>
-<PRE>
-  order of discovery: a b e d c f g h i
-  order of finish: d f c e b a
-  parenthesis: (a (b (e (d d) (c (f f) c) e) b) a) (g (h (i i) h) g)
-</PRE>
-
-<P>
-

-<H2><a name="sec:minimum-spanning-tree">Minimum Spanning TreeProblem</a></H2>

-
-<P>
-The <I>minimum-spanning-tree problem</I> is defined as follows: find
-an acyclic subset <i>T</i> of <i>E</i> that connects all of the vertices
-in the graph and whose total weight is minimized, where the
-total weight is given by
-<P></P>
-<DIV ALIGN="left">
-<i>w(T)</i> = sum of <i>w(u,v)</i> over all <i>(u,v)</i> in <i>T</i>,
-where <i>w(u,v)</i> is the weight on the edge <i>(u,v)</i>
-</DIV>
-<BR CLEAR="ALL">
-<P></P>
-<i>T</i> is called the <I>spanning tree</I>.
-
-<!--
-<P>
-Kruskal's algorithm&nbsp;[<A
- HREF="bibliography.html#kruskal56">18</A>]
-for solving the minimum spanning tree problem. This is a greedy
-algorithm to calculate the minimum spanning tree for an undirected
-graph with weighted edges.
-
-<P>
-This is Prim's algorithm&nbsp;[<A
- HREF="bibliography.html#prim57:_short">25</A>] for solving the
- minimum spanning tree problem for an undirected graph with weighted
- edges. The implementation is simply a call to <a

-href="./dijkstra_shortest_paths.html"><TT>dijkstra_shortest_paths()</TT></a>

- with the appropriate choice of comparison and combine functors.
--->
-
-<P>
-

-<H2><a name="sec:shortest-paths-algorithms">Shortest-PathsAlgorithms</a></H2>

-
-<P>
-One of the classic problems in graph theory is to find the shortest
-path between two vertices in a graph. Formally, a <I>path</I> is a

-sequence of vertices<v0,v1,...,vk>

-in a graph <i>G = (V, E)</i> such that each vertex is connected to the
-next vertex in the sequence (the edges
-<i>(v<sub>i</sub>,v<sub>i+1</sub>)</i> for <i>i=0,1,...,k-1</i> are in
-the edge set <i>E</i>). In the shortest-path problem, each edge is
-given a real-valued weight. We can therefore talk about the <I>weight
-of a path</I><BR>
-
+G = (V, E) </tt></td>
+</tr>
+</tbody>
+</table>
+</div>
+<a name="def:directed-version"><br clear="all">
+</a>
+<div align="center"><a name="fig:undirected-graph"></a><a name="1524"></a>
+<table>
+<caption align="bottom"><strong>图 2:</strong>
+一个无向图的例子</caption> <tbody>
+<tr>
+<td><img src="./figs/undigraph.gif" height="163" width="103"></td>
+</tr>
+</tbody>
+</table>
+</div>
 <p></p>
-<DIV ALIGN="left">

+现在开始讲讲图的专业术语吧。如果边（u，v）属于一个图，那么顶点v是顶点u的邻接点。在一个有向图中，边（u，v）是顶点u的出边、顶点v的入边。在

+一个无向图中，边（u，v）是与u，v关联的。<br>
+<p>在<a href="graph_theory_review.html#fig:directed-graph">图

+一</a>中，顶点y是顶点b的邻接点（但是b不是y的邻接）。边（b，y）是b的出边，是y的入边。在 <a href="graph_theory_review.html#fig:undirected-graph">图二</a>中，

+y是b的邻接点，反之亦然。边（y，b）是与y和b关联的。<br>
+</p>

+在有向图中，一个顶点出边的数量叫做该点的出度，入边的数量叫做该点的入度。无向图中，点关联的边的数量叫做该点的度。在<ahref="graph_theory_review.html#fig:directed-graph">图一</a>中，+顶点b的出度是3，入度是0。在<ahref="graph_theory_review.html#fig:undirected-graph">图二</a>中，

+顶点b的度仅为2。<br>
+<br>

+路径是图中边的序列，该序列中，每条边的目标顶点是下一条边的源顶点。如果一条路径起始于顶点u终止于顶点v，那么我们便说v是从u可到达的。如果一条路+径中没有重复顶点，我们便称该路径是简单的。路径<(b,x),(x,v)>是简单的，但是<(a,z),

+(z,a)&gt;不是。路

+径<(a,z),(z,a)>叫做环，因为路径中起点和终点是同一个点。一个没有环的图被称作无环的。 

+<br>

+可平面图是指一个图能够被画到一个平面上，并且其中没有边相互交叉。能够用上面方法画出的图叫做平面图。一个平面图的面是指被边环绕的平面的连通区域。可

+平面

+图的一个重要性质是：面、边和顶点的数量关系遵循欧拉公式：|F|-|E|+|V|=2。这意味着简单的可平面图最多有O(|V|)条边。

+<h1>图的数据结构<br>
+</h1>

+在图中，考虑使用什么数据结构时，最重要的一个属性是稀疏性，稀疏性是指边的数量相对于点的数量。一个图中，边的数量接近于顶点平方，该图就是稠密图，反

+之，

+一个图中E=α×V，并且α比V小得多的时候称该图为稀疏图。表示稠密图，邻接矩阵表示法是最佳选择；邻接列表表示+法是稀疏图的最佳选择。某些情况下，对于稀疏图，边-列表的表示法在空间效率选择上更加合适。 

+<h2>邻接矩阵表示法<br>
+</h2>

+图的邻接矩阵表示的就是一个V×V的2维数组。数组中的每一个元素auv存储一个布尔值，该值表示边（u，v）是否出现在图中。<ahref="graph_theory_review.html#fig:adj-matrix">图三</a>表示

+的是<a href="graph_theory_review.html#fig:directed-graph">图一</a>的

+邻接矩阵（删除了平行边（b，y））。存储一个邻接矩阵需要的空间是O(V2)。访问、增加、删除一条边的复杂度是O(1)。增加或者删除一个顶点需要重+新分配空间并且拷贝整张图到新的空间，负责度是O(V2)。 <ahref="adjacency_matrix.html"><tt>adjacency_matrix</tt></a>

+类实现了按照BGL的图接口规范实现了邻接矩阵数据结构。<br>
+</p>
+<div align="center"><a name="fig:adj-matrix"></a><a name="1701"></a>
+<table>
+<caption align="bottom"><strong>图 3:</strong>
+图的邻接矩阵表示法</caption> <tbody>
+<tr>
+<td><img src="./figs/adj_matrix.gif" height="135" width="136"></td>
+</tr>
+</tbody>
+</table>
+</div>
+<h2><a name="sec:adjacency-list-representation"></a>&amp;
+nbsp;邻接表表示法
+</h2>

+图的邻接列表表示的是每个顶点的出边序列。对于一个稀疏图来讲，该表示法节省了空间，因为仅需了O(V ++E)大小的内存。而且，访问顶点出边更加有效率。边得插入操作复杂度是O(1)，但是访问制定边的效率是O(α)，α表示矩阵的+稀疏因子（稀疏因子等于最大的顶点出度）。<ahref="graph_theory_review.html#fig:adj-list">图

+四</a>表示的是<a href="graph_theory_review.html#fig:directed-graph">图
+一</a>的邻接列表。
+<a href="adjacency_list.html"><tt>adjacency_list</tt></a>
+类是邻接列表表示法的一个实现。</p>
+<div align="center"><a name="fig:adj-list"></a><a name="1713"></a>
+<table>
+<caption align="bottom"><strong>图 4:</strong>
+图的邻接表表示法</caption> <tbody>
+<tr>
+<td><img src="./figs/adj_list.gif" height="122" width="108"></td>
+</tr>
+</tbody>
+</table>
+</div>
+<h2>边列表表示法<br>
+</h2>

+图的边列表表示就是一个边的序列，其中每条边使用一个顶点ID对来表示的。该表示法仅需要O(E)大小的内存。边插入复杂度是O+(1)，但是访问一个指定边的复杂度是O(E)（效率低下）。<ahref="graph_theory_review.html#fig:edge-list">图五</a>表示了

+&nbsp;<a href="graph_theory_review.html#fig:directed-graph">图
+一</a>的边列表表示。
+<a href="edge_list.html"><tt>edge_list</tt></a>适
+配器类内被用来实现边列表表示。<br>
+</p>
+<div align="center"><a name="fig:edge-list"></a><a name="1724"></a>
+<table>
+<caption align="bottom"><strong>图 5:</strong>
+图的边列表表示法</caption> <tbody>
+<tr>
+<td><img src="./figs/edge_list.gif" height="22" width="322"></td>
+</tr>
+</tbody>
+</table>
+</div>
+<h1>图相关算法<br>
+</h1>
+<h2>图搜索算法<br>
+</h2>
+<p>

+树边是指通过图搜索算法遍历一个图时(隐式或显式地)建立的搜索树(或森林)中的边。如果在遍历（对应于<a href="visitor_concepts.html"> visitor </a>的explore+()方法）边（u，v）时，点v首先被遍历到，那么边（u，v）就是一条树边。后向边将顶点连接到他们在搜索树中的祖先。因此对于反向边（u，v），点v+一定是点u的祖先。自环被认为是反向边。前向边是指将点u连接到它在搜索树中的子孙节点v的一条非树边（u，v）。交叉边为不属于前面定义的三种边之一的

+边。<br>
+</p>
+<h2><a name="sec:bfs-algorithm"></a> 广度优先搜索</h2>

+广度优先搜索（BFS）是指从某点开始遍历整张图，到达所有可以到达的点。遍历的顺序满足以下条件，在遍历了某点的所有邻接结点后，才+开始处理其邻接节点的邻接节点图。可以把广度优先遍历想像成石子落入水中时激起的涟漪。在同一个"波"中的顶点和源点的距离是相同的。顶点在被算法首次遇

+到时被"发现"。顶点在其所

+有邻接点被遍历完后称为"结束"。下面的例子可以让你弄明白。<ahref="graph_theory_review.html#fig:bfs-example">图六</a>中+展示了一幅图，并且在图下面列出了BFS（广度优先搜索）的算法中顶点的发现和结束顺序。

+<div align="center"><a name="fig:bfs-example"></a><a name="1826"></a>
+<table>
+<caption align="bottom"><strong>图 6:</strong>
+图遍历的广度优先搜索</caption> <tbody>
+<tr>
+<td><img src="./figs/bfs_example.gif" height="143" width="242"></td>
+</tr>
+</tbody>
+</table>
+</div>
+<pre> 发现顺序：s r w v t x u y <br> 结束顺序：s r w v t x u y<br></pre>

+我们从s点开始，首先访问的是r和w（s的两个邻居）。它的两个邻居都被访问过后，我们将访问r的邻居（顶点v），然后访问w的邻居（r和w的发现顺序无

+所谓）t和x。最后，我们访问t和x的邻居u和y。

+为了让算法跟踪在图中的位置以及哪个顶点将要访问下一个点，BFS算法需要对顶点进行着色（color）（请参考 <a href="using_property_maps.html">PropertyMaps</a>一节来了解更+多关于图属性的细节）。颜色值既可以放在图结构的内部，也可以作为参数传入到算法中。 

+</p>
+<h2><a name="sec:dfs-algorithm"></a> 深度优先搜索
+</h2>

+深度优先搜索（DFS）访问图中所有的顶点。在选择接下来要遍历哪条边时，该算法会始终选择图中"较深"的边来遍历。也就是说，DFS会在一个顶点已没有

+未被访

+问的邻接顶点时，才会选择下一个未访问邻接顶点。该算法会回溯到前面顶点继续沿着未被访问的边来遍历顶点。DFS算法从一点遍历+完所有能够到达的顶点后，将选择仍未被发现的顶点来继续进行搜索。搜索的过程将建立了一组深度优先树（depth-first

+trees），这些树合起来就成了深度优先森林（depth-first

+forest）。一次DFS会把图中的边分为三类：树边，反向边，正向边或交叉边（这两种边不能区分）。一个给定的图可以有多个有效的深度优先森林，所以

+对于图的边也有多种不同的(也是同样有效的)分类方法。<br>

+DFS一个比较有意思的特性是每个点的发现和结束时间会形成对称结构。如果我们在发现一个顶点时加一个左括号，在结束一个顶点时加一个+右括号，那么结果就是一个正确嵌套的括号集。<ahref="graph_theory_review.html#fig:dfs-example">图七</a>示+范了将DFS应用于一个无向图，该图边上已经标记了遍历的顺序。下面我们按照发现和结束的顺序列出图的顶点，以及嵌套的括号结构。DFS是其他一些算法的+核心，比如拓朴排序和连通分量算法。DFS算法还能检测是图中是否存在环（参考文件依赖例子中的<a href="file_dependency_example.html#sec:cycles">Cylic

+Dependencies</a>（循环依赖）一节）。<br>
+</p>
+<div align="center"><a name="fig:dfs-example"></a><a name="1841"></a>
+<table>
+<caption align="bottom"><strong>图 7:</strong>
+无向图的深度优先搜索</caption> <tbody>
+<tr>
+<td><img src="./figs/dfs.gif" height="204" width="141"></td>
+</tr>
+</tbody>
+</table>
+</div>

+<pre> order of discovery: a b e d c f g h i order of finish: d f c e ba parenthesis: (a (b (e (d d) (c (f f) c) e) b) a) (g (h (i i) h)g) </pre>

+<h2><a name="sec:minimum-spanning-tree">最小生成树问题</a></h2>

+最小生成树（minimum-spanning-tree）的定义如下：从E中找到一个无环子集T，E连接图中的所有顶点，且T的总权值最小，权值给定如

+下：<br>
+<div align="left">
+<div align="left"><i>w(T)</i> = 对 <i>T</i>
+中所有 <i>(u,v)</i> 的 <i>w(u,v)</i> 总和,
+其中 <i>w(u,v)</i> 为边 <i>(u,v)</i> 的权重
+</div>
+</div>
+<br clear="all">

+这样的T称为最小生成树。 

+<h2><a name="sec:shortest-paths-algorithms">最短路径算法</a></h2>

+图论中的一个经典问题是找出两点之间的最短路径。在图G中，一条路径是一个顶点序列<v0,v1,....,Vk>，使得序

+列中的每个顶点都

+和下一个顶点相连(边（vi，vi+1）i=0,1,....k-1属于边集E)。在最短路径问题中，每条边都会给定一个实数值作为权值。因此，我们可以

+说一条路
+径的权值是：<br>
+<div align="left">
 <i>w(p) = sum from i=1..k of w(v<sub>i-1</sub>,v<sub>i</sub>)</i>
-</DIV>
-<BR CLEAR="ALL"><P></P>
-
-The <I>shortest path weight</I> from vertex <i>u</i> to <i>v</i> is then
-
-<BR>
-<p></p>
-<DIV ALIGN="left">
-<i>delta (u,v) = min { w(p) : u --> v }</i> if there is a path from
+</div>
+<br clear="all">
+顶点u到v的最短路径权值是：
+<div align="left"><i>delta (u,v) = min { w(p) : u
+--&gt; v }</i> if there is a path from
 <i>u</i> to <i>v</i> <br>
 <i>delta (u,v) = infinity</i> otherwise.
-</DIV>
-<BR CLEAR="ALL"><P></P>
-
-A <I>shortest path</I> is any path who's path weight is equal to the
-<I>shortest path weight</I>.
-
-<P>
-There are several variants of the shortest path problem. Above we
-defined the <I>single-pair</I> problem, but there is also the
-<I>single-source problem</I> (all shortest paths from one vertex to
-every other vertex in the graph), the equivalent
-<I>single-destination problem</I>, and the <I>all-pairs problem</I>.
-It turns out that there are no algorithms for solving the single-pair
-problem that are asymptotically faster than algorithms that solve the
-single-source problem.
-
-<P>
-A <I>shortest-paths tree</I> rooted at vertex in graph <i>G=(V,E)</i>
-is a directed subgraph <G'> where <i>V'</i> is a subset
-of <i>V</i> and <i>E'</i> is a subset of <i>E</i>, <i>V'</i> is the
-set of vertices reachable from , <i>G'</i> forms a rooted tree with
-root , and for all <i>v</i> in <i>V'</i> the unique simple path from
-to <i>v</i> in <i>G'</i> is a shortest path from to <i>v</i> in . The
-result of a single-source algorithm is a shortest-paths tree.
-
-<P>
-
-<H2><a name="sec:network-flow-algorithms">Network Flow Algorithms</H2>
-
+</div>
+<br clear="all">
+最短路径是权值等于最短路径权值的任何一条路径。<br>
+<br>

+还有一些最短路径的衍生问题。上面我们定义了单-点对single-pair问题，但是还有一个单-源single-source问题(求图中从一个顶点+出发到所有其它顶点的最短路径)，同样还有单-目标single-destination问题和全-点对all-pairs问题。已知单-点对问题没有比

+单-源问题更快的算法。<br>
+<br>

+在图G=(V,E)中，以某点为根的最短路径树是该图的一个有向子图G'=(V',E')，其中V'是V的子集，E'是E的子集，而且V'是该点能够+到达的顶点的集合。G'形成是一棵带根的有根树，从V'中一点v到G'中一点u的唯一简单路径就是G中从v到u的最短路径。单-源算法的结果就是一棵最短

+路径树。<br>
+<h2><a name="sec:network-flow-algorithms">网络流算法</a></h2>
 <p>
-A flow network is a directed graph <i>G=(V,E)</i> with a
-<b><i>source</i></b> vertex <i>s</i> and a <b><i>sink</i></b> vertex
-<i>t</i>. Each edge has a positive real valued <b><i>capacity</i></b>
-function <i>c</i> and there is a <b><i>flow</i></b> function <i>f</i>
-defined over every vertex pair. The flow function must satisfy three
-contraints:
-

+<a name="sec:network-flow-algorithms">一个流网络是指一个以顶点s为源点，以顶点t+为接受点的有向图G=(V,E)。每条边e均具有一个非负实数值的容量函数c，而且每个顶点对还有一个流函数f。流函数要满足以下三个约束条件：

+</a></p>
 <p>
-<i>f(u,v) <= c(u,v) for all (u,v) in V x V</i> (Capacity constraint) <br>
-<i>f(u,v) = - f(v,u) for all (u,v) in V x V</i> (Skew symmetry)<br>

-sumv in V f(u,v) = 0 for all u in V - {s,t} (Flowconservation)

-
+<a name="sec:network-flow-algorithms"><i>容量约束
+(Capacity constraint)：对于V*V中所有顶点对(u, v)有：f(u,v) &lt;= c(u,v)<br>
+斜对称性(Skew symmetry):对于V*V中所有顶点对(u, v)有：f(u,v) = - f(v,u)<br>
+流守恒(Flow conservation)：对于V -
+{s,t}中的所有u，sum<sub>v
+in V</sub> f(u,v) = 0<br>
+</i>
+</a></p>
 <p>
-The <b><i>flow</i></b> of the network is the net flow entering the
-sink vertex <i>t</i> (which is equal to the net flow leaving the
-source vertex <i>s</i>).<p>
-
-<i>|f| = sum<sub>u in V</sub> f(u,t) = sum<sub>v in V</sub> f(s,v)</i>
-

+<a name="sec:network-flow-algorithms">该网络的流量是指流向接收点t的净流量（等效于流出源点

+s的净流量）。</a></p>
 <p>
-The <b><i>residual capacity</i></b> of an edge is <i>r(u,v) = c(u,v) -
-f(u,v)</i>. The edges with <i>r(u,v) > 0</i> are residual edges
-<i>E<sub>f</sub></i> which induce the residual graph <i>G<sub>f</sub>
-= (V, E<sub>f</sub>)</i>. An edge with <i>r(u,v) = 0</i> is
-<b><i>saturated</i></b>.
-
+<a name="sec:network-flow-algorithms"><i>|f| = sum<sub>u
+in V</sub> f(u,t) = sum<sub>v in V</sub> f(s,v)</i>
+</a></p>
 <p>
-The <b><i>maximum flow problem</i></b> is to determine the maximum
-possible value for <i>|f|</i> and the corresponding flow values for
-every vertex pair in the graph.
-
+<a name="sec:network-flow-algorithms">一条边的剩余容量为：r(u,v) =
+c(u,v) -

+f(u,v)。如果r(u,v)>0则称该边为剩余边，剩余边组成的图为剩余图。如果r(u,v)=0，则称该边是饱和的。

+</a></p>
 <p>
-A flow network is shown in <a href="#fig:max-flow">Figure
-8</a>. Vertex <i>A</i> is the source vertex and <i>H</i> is the target
-vertex.
-
-<P></P>
-<DIV ALIGN="center"><A NAME="fig:max-flow"></A><A NAME="1509"></A>
-<TABLE>
-<CAPTION ALIGN="BOTTOM"><STRONG>Figure 8:</STRONG> A Maximum Flow
-Network.<br> Edges are labeled with the flow and capacity
-values.</CAPTION>
-<TR><TD><IMG SRC="./figs/max-flow.gif" width="578" height="240"></TD></TR>
-</TABLE>
-</DIV><P></P>

+<a name="sec:network-flow-algorithms">最大流问题是指确定|f|的最大值以及图中每个

+顶点对的相应流量是多少。
+</a></p>

 <p>
-There is a long history of algorithms for solving the maximum flow
-problem, with the first algorithm due to <a
-href="./bibliography.html#ford56:_maxim">Ford and Fulkerson</a>. The
-best general purpose algorithm to date is the push-relabel algorithm
-of <a
-href="./bibliography.html#goldberg85:_new_max_flow_algor">Goldberg</a>
-which is based on the notion of a <b><i>preflow</i></b> introduced by
-<a href="./bibliography.html#karzanov74:_deter">Karzanov</a>.
-
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 2000-2001</TD><TD>

-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,Indiana University (<A HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)

-</TD></TR></TABLE>
-
-</BODY>
-</HTML>

+<a name="sec:network-flow-algorithms"> </a><ahref="graph_theory_review.html#fig:max-flow">图八</a><aname="sec:network-flow-algorithms">表示一个流网络，顶点A为源点，顶点H为终点。</a>

+<div align="center"><a name="fig:max-flow"></a><a name="1509"></a>
+<table>
+<caption align="bottom"><strong>Figure 8:</strong>&amp;
+nbsp;一个最大流网络<br>
+边已经被标上流和容量值</caption> <tbody>
+<tr>
+<td><img src="./figs/max-flow.gif" height="240" width="578"></td>
+</tr>
+</tbody>
+</table>
+</div>
+

+解决最大流问题的算法已经有很长历史了，最早的算法来自于 <ahref="bibliography.html#ford56:_maxim">Ford 和 Fulkerson</a>。而最通用的算法则是<ahref="bibliography.html#goldberg85:_new_max_flow_algor">Goldberg</a>提+出的push-relabel算法，该算法基于<ahref="bibliography.html#karzanov74:_deter">Karzanov</a>提

+出的预流量(preflow)概念。</p>
+<hr>
+<table>
+<tbody>
+<tr valign="top">
+<td nowrap="nowrap">Copyright (c) 2000-2001</td>
+<td> <a href="../../../people/jeremy_siek.htm">Jeremy

+Siek</a>, Indiana University (<ahref="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)

+</td>
+</tr>
+</tbody>
+</table>
+</body></html>
\ No newline at end of file

Modified: trunk/libs/graph/doc/history.html
==============================================================================
--- trunk/libs/graph/doc/history.html   (original)
+++ trunk/libs/graph/doc/history.html   Fri Jun 26 00:01:13 2009
@@ -1,208 +1,217 @@
-<HTML>
-<!--
-  -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
-  --
-  -- Distributed under the Boost Software License, Version 1.0.
-  -- (See accompanying file LICENSE_1_0.txt or copy at
-  -- http://www.boost.org/LICENSE_1_0.txt)
-  -->
-<Head>
-<Title>Boost Graph Library: History</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>History of the Boost Graph Library</h1>
-
-The Boost Graph Library began its life as the Generic Graph Component
-Library (GGCL), a software project at the <a
-href="http://www.lsc.nd.edu";>Lab for Scientific Computing (LSC)</a> at
-the University of Notre Dame, under the direction of Professor <a
-href="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</a>. The Lab's
-research directions include numerical linear algebra, parallel
-computing, and software engineering (including generic programming).
-
-<p>
-Soon after the Standard Template Library was released, work began at
-the LSC to apply generic programming to scientific computing.  The <a
-href="http://www.lsc.nd.edu/research/mtl";>Matrix Template Library</a>
-(Jeremy Siek's masters thesis) was one of the first projects. Many of
-the lessons learned during construction of the MTL were applied to the
-design and implementation of the GGCL.
-
-<p>
-Graph algorithms play an important role in sparse matrix computations,
-so the LSC had a need for a good graph library. However, none of the
-available graph libraries (LEDA, GTL, Stanford GraphBase) were
-written using the generic programming style of the STL, and hence did
-not fulfill the flexibility and high-performance requirements of the
-LSC. Others were also expressing interest in a generic C++ graph
-library. During a meeting with Bjarne Stroustrup we were introduced to
-several people at AT\&T who needed such a library. There had also been
-earlier work in the area of generic graph algorithms, including some
-codes written by Alexander Stepanov, and Dietmar K&uuml;hl's masters
-thesis.
-
-<p>
-With this in mind, and motivated by homework assignments in his
-algorithms class, Jeremy began prototyping an interface and some graph
-classes in the spring on 1998. Lie-Quan Lee then developed the first
-version of GGCL, which became his masters thesis project.
-
-<p>
-The following year, Jeremy went to work for SGI with Alexander
-Stepanov and Matt Austern. During this time Alex's disjoint-sets based
-connected components algorithm was added to GGCL, and Jeremy began
-working on the concept documentation for GGCL similar to Matt's STL
-documentation.
-
-<p>
-While working at SGI, Jeremy heard about Boost and was excited to find
-a group of people interested in creating high-quality C++
-libraries. At boost there were several people interested in generic
-graph algorithms, most notably Dietmar K&uuml;hl.  Some discussions
-about generic interfaces for graph structures resulted in the a
-revision of GGCL which closely resembles the current Boost Graph
-Library interface.
-
-<p>
-On September 4, 2000 GGCL passed the Boost formal review and became
-the Boost Graph Library (BGL). The first release of BGL was
-September 27, 2000.
-
-<h2>Changes by version</h2>
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>

+<meta content="text/html; charset=UTF-8" http-equiv="content-type">

+<title>Boost Graph Library: History</title></head>

+<h1>Boost图库的历史</h1>

+Boost图库最开始是作为通用图组件库(GGCL)出现的，它是Notre Dame大学 <ahref="http://www.lsc.nd.edu";>科学计算实验室 (LSC)</a> 由 <ahref="http://www.osl.iu.edu/%7Elums";>Andrew Lumsdaine</a>+教授带领的一个项目。该实验室的研究方向还包括：数值线性代数，并行计算，以及软件工程（包括范型编程）。+标准模板库出现后不久，LSC实验室就开始采用泛型编程来进行科学计算。<ahref="http://www.lsc.nd.edu/research/mtl";>矩阵模板库(Matrix

+Template Library</a>&nbsp;（Jeremy

+Siek的硕士学位论文）就是最早采用泛型编程的项目之一。同时，构建MTL过程中的一些经验被引入到GGCL的设计和实现当中。

+</p>

+由于图算法在稀疏矩阵计算当中起着非常重要的作用，所以LSC需要一个优秀的图库。然而，没有一个图库(LEDA, GTL,

+Stanford

+GraphBase)是用STL的泛型编程风格去编写的，并且已有库也不能很好的适应LSC对于灵活和高性能方面的需求。另外也有一些人非常需要用C++实

+现的泛型库。在一次会议期间Bjarne

+Stroustrup被介绍给了一些需要这些库的人。其实在泛型图算法方面已经做了一些前期工作，比如Alexander

+Stepanov写的一些代码，以及Dietmar Kühl的硕士论文。
+</p>

+在这种思想的驱动下，同时为了完成算法课的作业，Jeremy于1998年春开始实现一套接口原型和一些图相关类。随后，Lie-

+Quan Lee开发了GGCL的第一个版本，并且以该项目作为他的硕士论文项目。
+</p>
+<p>接下去的一年，Jeremy和Alexander Stepanov 以及Matt

+Austern一起到了SGI工作。其间Alex的基于连通分支的不相交集合算法被加入到GGCL中，并且Jeremy开始给GGCL编写概念文档了，该文

+档类似于Matt给STL写的文档。
+</p>

+在SGI工作期间，Jeremy听说了Boost并且找到了一群对创造一套高质量C++库感兴趣的人。Boost成员中，有很多人对泛

+型图算法都很
+感兴趣，最有名的是Dietmar

+Kühl。关于图结构的泛型接口的一些讨论被加入到了GGCL中，它们已经非常接近现在的Boost图库接口了。

+</p>

+在2000年9月4日，GGCL通过了Boost的正式评审并且成为了Boost图库（BGL）。BGL的第一个发行版是2000年9月27日发行的。

+</p>
+<h2>版本变更</h2>
 <a name="by-version">
+</a>
 <ul>

- <a name="1.35.0"></a><li>Version 1.35.0 New algorithms andcomponents

-    <ul>

- <li><ahref="kolmogorov_max_flow.html"><tt>kolmogorov_max_flow</tt></a>, fromStephan Diederich as part of the <a href="http://code.google.com/soc/";>2006Google Summer of Code</a>.</li>- <li><a href="read_dimacs.html">read_dimacs_max_flow</a> and <ahref="write_dimacs.html">write_dimacs_max_flow</a> for max-flow problems,from Stephan Diederich.</li>- <li><a href="read_graphml.html">read_graphml</a> and <ahref="write_graphml.html">write_graphml</a> for <ahref="http://graphml.graphdrawing.org/";>GraphML</a> input/output, fromTiago de Paula Peixoto.</li>- <li><a href="howard_cycle_ratio.html"><tt>minimum_cycle_ratio</tt>and <tt>maximum_cycle_ratio</tt></a>, from Dmitry Bufistov and AndreyParfenov.</li>- <li><ahref="boyer_myrvold.html"><tt>boyer_myrvold_planarity_test</tt></a>, alongwith a suite of <a href="planar_graphs.html">algorithms for planargraphs</a>, from Aaron Windsor.</li>

-    </ul><br><b>Enhancements</b><br>
-    <ul>

- <li><a href="leda_conversion.html">LEDA Adaptor</a> improvements,from Jens Müller.</li>

-    </ul>
-  </li><br>
-
-  <a name="1.34.1"></a><li>Version 1.34.1</br><b>Bug Fixes</b><br>
-  <ul>

- <li><ahref="bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths</tt></a>:fixed a bug where certain negative cycles were not correctly detected.</li>

-  </ul>

- <a name="1.34.0"></a><li>Version 1.34.0 New algorithms andcomponents

-    <ul>

- <li><ahref="maximum_matching.html"><tt>edmonds_maximum_cardinality_matching</tt></a>,from Aaron Windsor.</li>- <li><ahref="lengauer_tarjan_dominator.htm"><tt>lengauer_tarjan_dominator_tree</tt></a>,from JongSoo Park.</li>- <li><ahref="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a>,from Jeremiah Willcock and Douglas Gregor of Indiana University.</li>- <li><ahref="sorted_erdos_renyi_gen.html"><tt>sorted_erdos_renyi_iterator</tt></a>,from Jeremiah Willcock of Indiana University.</li>

-    </ul><br><b>Enhancements</b><br>
-    <ul>

- <li>Note: the name of the compiled library for GraphViz reading isnow called <code>boost_graph</code> rather than <code>bgl-viz</code>.</li>- <li><ahref="biconnected_components.html"><tt>biconnected_components</tt></a> nowhas a visitor parameter and supports named parameters, from JanuszPiwowarski.</li>- <li><a href="adjacency_matrix.html"><tt>adjacency_matrix</tt></a>now models the <a href="BidirectionalGraph.html">Bidirectional Graph</a>concept.</li>- <li><ahref="adjacency_list.html"><tt>adjacency_list</tt></a> is now <ahref="../../serialization/doc/index.html">Serializable</a>, from JeremySiek of Rice University.</li>- <li>Added <tt>edges_size_type</tt> and <tt>vertices_size_type</tt>to <tt>adjacency_list_traits</tt>, from Jeremy Siek of Rice University.</li>- <li>Added <tt>operator< </tt>, etc. to the edge descriptor of<tt>adjacency_list</tt>,

-             from Jeremy Siek of Rice University.</li>
-    </ul>
-    <br><b>Bug Fixes</b><br>
-    <ul>

- <li>Fixed a bug that causes the relaxed heap to fail on x86Linux.</li>

-      <li>Bundled properties now work with adjacency list I/O.</li>

- <li><ahref="floyd_warshall_shortest.html"><tt>floyd_warshall_all_pairs_shortest_paths</tt></a>now properly uses its <tt>compare</tt>, <tt>inf</tt>, and <tt>zero</tt>parameters.</li>- <li><ahref="johnson_all_pairs_shortest.html"><tt>johnson_all_pairs_shortest_paths</tt></a>now supports <tt>compare</tt>, <tt>combine</tt>, <tt>inf</tt>, and<tt>zero</tt>.</li>- <li>Fixed a bug in smallest_last_vertex_ordering.hpp which couldcause a vertex to be moved to the wrong bucket during an BucketSorterupdate.

-    </ul>
-    <br>
-  </li>
-
-  <li>Version 1.33.1<br><b>Bug Fixes</b>
-    <ul>

- <li><ahref="fruchterman_reingold.html"><TT>fruchterman_reingold_force_directed_layout</TT></A>:Fixed enumeration of grid-force pairs, which caused some odd graphformations along grid lines.</li>

-      <li><a href="king_ordering.html"><tt>king_ordering</tt></a> and <a

-href="cuthill_mckee_ordering.html"><tt>cuthill_mckee_ordering</tt></a>:Fixed bug that caused failures with the multi-component version of thesealgorithms.</li>

-    </ul></li>
-
-  <li>Version 1.33.0<br><b>New algorithms and components</b>
-    <ul>

- <li><a href="python.html">Experimental Python bindings</a>, fromDoug Gregor and Indiana University.</li>- <LI><Ahref="floyd_warshall_shortest.html"><TT>floyd_warshall_all_pairs_shortest_paths</TT></A>,from Lauren Foutz and Scott Hill.</LI>- <LI><A href="astar_search.html"><TT>astar_search</TT></A>, fromKristopher Beevers and Jufeng Peng.</LI>- <LI><Ahref="fruchterman_reingold.html"><TT>fruchterman_reingold_force_directed_layout</TT></A>,from Doug Gregor and Indiana University.</a></LI>- <LI><Ahref="biconnected_components.html"><tt>biconnected_components</tt> and<tt>articulation_points</tt></a>, from Indiana University.</a></li>- <li><ahref="gursoy_atun_layout.html"><tt>gursoy_atun_layout</tt></a>, fromJeremiah Willcock and Doug Gregor of Indiana University.</li>

-      <li><a href="king_ordering.html"><tt>king_ordering</tt></a>, from
-      D. Kevin McGrath of Indiana University.</li>

- <li><ahref="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a></li>

-      <li><a href="plod_generator.html"><tt>plod_iterator</tt></a></li>

- <li><ahref="small_world_generator.html"><tt>small_world_iterator</tt></a></li>

-    </ul><br><b>Enhancements</b><br>
-    <ul>

- <li><ahref="bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths</tt></a>now permits one to specify the starting vertex, so that it will perform itsown initialization.</li>- <li><a href="undirected_dfs.html"><tt>undirected_dfs</tt></a> is nowdata-recursive, resulting in improved performance in some cases, from SyngeTodo.</li>- <li><ahref="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths</tt></a>now uses a relaxed heap [<A- HREF="bibliography.html#driscoll88">61</A>] as its priority queue,improving its complexity to O(V log V) and improving real-worldperformance for larger graphs.</li>- <li><a href="read_graphviz.html"><code>read_graphviz</code></a> nowhas a new, Spirit-based parser that works for all graph types and supportsarbitrary properties on the graph, from Ron Garcia. The old, Bison-basedGraphViz reader has been deprecated and will be removed in a future Boostrelease.</li>

-
-      <li><a
-      href="write-graphviz.html"><code>write_graphviz</code></a> now
-      supports output of dynamic properties (as read in through the
-      new <code>read_graphviz</code>).</li>
-
-      <li><a

-href="cuthill_mckee_ordering.html"><tt>cuthill_mckee_ordering</tt></a>

-      has been recast as an invocation of
-      <tt>breadth_first_search</tt> and now supports graphs with
-      multiple components.</li>
-
-      <li><a href="subgraph.html"><tt>subgraph</tt></a> now supports
-      <a href="bundles.html">bundled
-      properties</a>. <code>get_property</code> now refers to the
-      subgraph property, not the root graph's property.</li></li>
-
-      <li><a href="filtered_graph.html"><tt>filtered_graph</tt></a> now
-      supports <a href="bundles.html">bundled properties</a>.</li>
-
-      <li><a href="reverse_graph.html"><tt>reverse_graph</tt></a> now
-      supports <a href="bundles.html">bundled properties</a>,
-      <tt>set_property</tt>, and <tt>get_property</tt>.</li>
-
-    </ul><br><b>Bug fixes</b><br>
-    <ul>

- <li><ahref="bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths</tt></a>now deals with unreachable vertices better.</li>- <li><a href="adjacency_list.html"><tt>adjacency_list</tt></a>:parallel edge removal with <tt>OutEdgeListS = listS</tt> has been fixed.Copying and swapping has been fixed.</li>- <li><a href="incremental_components.html">Incremental connectedcomponents</a>: fixed a bug in the <tt>incremental_components</tt> routinethat may have caused incorrect results.</li>- <li>The <tt>remove_out_edge_if</tt> function for an undirected <ahref="adjacency_list.html"><tt>adjacency_list</tt></a> has been rewrittenand should no longer dereference singular iterators.</li>- <li><a href="write-graphviz.html"><tt>write_graphviz</tt></a> nowaccepts a <tt>vertex_id</tt> parameter that is used to name the nodes.</li>- <li><a href="read_graphviz.html"><tt>read_graphviz</tt></a> nowaccepts empty attribute lists.</li>- <li><ahref="sequential_vertex_coloring.html"><tt>sequential_vertex_coloring</tt></a>has been updated, tested, and documented.</li>

-    </ul>
-  </li>
-</ul>
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
-Indiana University (<A
-HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>

-<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>,Indiana University (<AHREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>) 

-<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
-Indiana University (<A
-HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>

-<!-- LocalWords: gif ALT GGCL LSC Lumsdaine Siek's MTL LEDA GTLGraphBase STL

- -->

-<!-- LocalWords: Bjarne Stroustrup hl's Quan SGI Stepanov Austern Alex'shl

- -->
-<!--  LocalWords:  Dietmar BGL siek htm Univ
- -->
+<a name="1.35.0"></a><li>Version 1.35.0<br><b>新的算法和组件</b>
+<ul>

+<li><a href="kolmogorov_max_flow.html"><tt>kolmogorov_max_flow</tt></a>, 来自 Stephan Diederich，作为 <a href="http://code.google.com/soc/";>2006Google Summer of Code</a> 的一部分。</li>+<li><a href="read_dimacs.html">read_dimacs_max_flow</a> 和 <ahref="write_dimacs.html">write_dimacs_max_flow</a> 用于 max-flow 问题，来自Stephan Diederich.</li>+<li><a href="read_graphml.html">read_graphml</a> 和 <ahref="write_graphml.html">write_graphml</a> 用于 <ahref="http://graphml.graphdrawing.org/";>GraphML</a> 输入/输出同，来自 Tiagode Paula Peixoto.</li>+<li><a href="howard_cycle_ratio.html"><tt>minimum_cycle_ratio</tt> and<tt>maximum_cycle_ratio</tt></a>, 来自 Dmitry Bufistov 和 AndreyParfenov.</li>+<li><ahref="boyer_myrvold.html"><tt>boyer_myrvold_planarity_test</tt></a>，以及一套 <a href="planar_graphs.html">用于 planar 图的算法</a>，来自 AaronWindsor.</li>

+</ul><br><b>增强</b><br>
+<ul>

+<li><a href="leda_conversion.html">LEDA Adaptor</a> 的改进，来自 JensMüller.</li>

+</ul>
+</li><br>
+<a name="by-version"> </a><a name="1.34.1"></a><li>1.34.1
+版<br>
+<b>BUG修复</b><br>
+<ul>

+<li><ahref="bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths</tt></a>:

+修复了某些负回路不能被正确识别的BUG。</li>
+</ul>
+<a name="1.34.0"></a></li>
+<li>1.34.0版<br>
+<b>新算法和新组件</b>
+<ul>

+<li><ahref="maximum_matching.html"><tt>edmonds_maximum_cardinality_matching</tt></a>, 

+Aaron Windsor 提供</li>

+<li><ahref="lengauer_tarjan_dominator.htm"><tt>lengauer_tarjan_dominator_tree</tt></a>, JongSoo

+Park&nbsp;提供</li>

+<li><ahref="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a>,

+印第安纳大学的Jeremiah Willcock 和 Douglas Gregor提供</li>

+<li><ahref="sorted_erdos_renyi_gen.html"><tt>sorted_erdos_renyi_iterator</tt></a>,

+印第安纳大学的Jeremiah Willcock提供</li>
+</ul>
+<br>
+<b>改善</b><br>
+<ul>

+<li>注意：GraphViz编译出来的名字现在叫boost_graph了，比起bgl-viz来更好读；</li>+<li><ahref="biconnected_components.html"><tt>biconnected_components</tt></a>+现在有了一个遍历器（visitor）参数并且支持命名参数了，Janusz Piwowarski提供；</li>

+<li><a href="adjacency_matrix.html"><tt>adjacency_matrix</tt></a>
+现在宿模 <a href="BidirectionalGraph.html">Bidirectional Graph</a>
+概念.</li>
+<li><a href="adjacency_list.html"><tt>adjacency_list</tt></a>
+现在可序列化 <a href="../../serialization/doc/index.html">Serializable</a>,
+Rice大学的Jeremy Siek提供；</li>

+<li>将 <tt>edges_size_type</tt> 和 <tt>vertices_size_type</tt> 增加至<tt>adjacency_list_traits，来自</tt> Jeremy Siek of

+Rice University.</li>

+<li>将 <tt>operator< </tt>, 等等增加至 <tt>adjacency_list</tt> 的边描述字，来自

+Jeremy Siek of Rice University.</li>
+</ul>
+<br>
+<b>Bug修复</b><br>
+<ul>
+<li>Fixed a bug that causes the relaxed heap to fail on x86
+Linux.</li>
+<li>Bundled properties now work with adjacency list I/O.</li>

+<li><ahref="floyd_warshall_shortest.html"><tt>floyd_warshall_all_pairs_shortest_paths</tt></a>

+now properly uses its <tt>compare</tt>, <tt>inf</tt>,
+and <tt>zero</tt> parameters.</li>

+<li><ahref="johnson_all_pairs_shortest.html"><tt>johnson_all_pairs_shortest_paths</tt></a>

+now supports <tt>compare</tt>, <tt>combine</tt>,
+<tt>inf</tt>, and <tt>zero</tt>.</li>
+<li>Fixed a bug in smallest_last_vertex_ordering.hpp which
+could cause a vertex to be moved to the wrong bucket during an
+BucketSorter update. </li>
+</ul>
+<br>
+</li>
+<li>Version 1.33.1<br>
+<b>Bug Fixes</b>
+<ul>

+<li><ahref="fruchterman_reingold.html"><tt>fruchterman_reingold_force_directed_layout</tt></a>:

+Fixed enumeration of grid-force pairs, which caused some odd graph
+formations along grid lines.</li>
+<li><a href="king_ordering.html"><tt>king_ordering</tt></a>

+and <ahref="cuthill_mckee_ordering.html"><tt>cuthill_mckee_ordering</tt></a>:

+Fixed bug that caused failures with the multi-component version of
+these algorithms.</li>
+</ul>
+</li>
+<li>Version 1.33.0<br>
+<b>New algorithms and components</b>
+<ul>
+<li><a href="python.html">Experimental Python
+bindings</a>, from Doug Gregor and Indiana University.</li>

+<li><ahref="floyd_warshall_shortest.html"><tt>floyd_warshall_all_pairs_shortest_paths</tt></a>,

+from Lauren Foutz and Scott Hill.</li>
+<li><a href="astar_search.html"><tt>astar_search</tt></a>,
+from Kristopher Beevers and Jufeng Peng.</li>

+<li><ahref="fruchterman_reingold.html"><tt>fruchterman_reingold_force_directed_layout</tt></a>,

+from Doug Gregor and Indiana University.</li>
+<li><a href="biconnected_components.html"><tt>biconnected_components</tt>
+and <tt>articulation_points</tt></a>, from Indiana
+University.</li>
+<li><a href="gursoy_atun_layout.html"><tt>gursoy_atun_layout</tt></a>,
+from Jeremiah Willcock and Doug Gregor of Indiana University.</li>
+<li><a href="king_ordering.html"><tt>king_ordering</tt></a>,
+from D. Kevin McGrath of Indiana University.</li>

+<li><ahref="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a></li>

+<li><a href="plod_generator.html"><tt>plod_iterator</tt></a></li>

+<li><ahref="small_world_generator.html"><tt>small_world_iterator</tt></a></li>

+</ul>
+<br>
+<b>Enhancements</b><br>
+<ul>

+<li><ahref="bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths</tt></a>

+now permits one to specify the starting vertex, so that it will perform
+its own initialization.</li>
+<li><a href="undirected_dfs.html"><tt>undirected_dfs</tt></a>
+is now data-recursive, resulting in improved performance in some cases,
+from Synge Todo.</li>

+<li><ahref="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths</tt></a>+now uses a relaxed heap [<ahref="bibliography.html#driscoll88">61</a>] as its

+priority queue, improving its complexity to <em>O(V log V)</em>
+and improving real-world performance for larger graphs.</li>
+<li><a href="read_graphviz.html"><code>read_graphviz</code></a>
+now has a new, Spirit-based parser that works for all graph types and
+supports arbitrary properties on the graph, from Ron Garcia. The old,
+Bison-based GraphViz reader has been deprecated and will be removed in
+a future Boost release.</li>
+<li><a href="write-graphviz.html"><code>write_graphviz</code></a>

+now supports output of dynamic properties (as read in through the new<code>read_graphviz</code>).</li>+<li><ahref="cuthill_mckee_ordering.html"><tt>cuthill_mckee_ordering</tt></a>

+has been recast as an invocation of <tt>breadth_first_search</tt>
+and now supports graphs with multiple components.</li>
+<li><a href="subgraph.html"><tt>subgraph</tt></a>
+now supports <a href="bundles.html">bundled properties</a>.
+<code>get_property</code> now refers to the
+subgraph property, not the root graph's property.</li>
+<li><a href="filtered_graph.html"><tt>filtered_graph</tt></a>
+now supports <a href="bundles.html">bundled properties</a>.</li>
+<li><a href="reverse_graph.html"><tt>reverse_graph</tt></a>
+now supports <a href="bundles.html">bundled properties</a>,
+<tt>set_property</tt>, and <tt>get_property</tt>.</li>
+</ul>
+<br>
+<b>Bug fixes</b><br>
+<ul>

+<li><ahref="bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths</tt></a>

+now deals with unreachable vertices better.</li>
+<li><a href="adjacency_list.html"><tt>adjacency_list</tt></a>:
+parallel edge removal with <tt>OutEdgeListS = listS</tt>
+has been fixed. Copying and swapping has been fixed.</li>
+<li><a href="incremental_components.html">Incremental

+connected components</a>: fixed a bug in the<tt>incremental_components</tt>

+routine that may have caused incorrect results.</li>
+<li>The <tt>remove_out_edge_if</tt> function
+for an undirected <a href="adjacency_list.html"><tt>adjacency_list</tt></a>

+has been rewritten and should no longer dereference singulariterators.</li>

+<li><a href="write-graphviz.html"><tt>write_graphviz</tt></a>
+now accepts a <tt>vertex_id</tt> parameter that is used to
+name the nodes.</li>
+<li><a href="read_graphviz.html"><tt>read_graphviz</tt></a>
+now accepts empty attribute lists.</li>

+<li><ahref="sequential_vertex_coloring.html"><tt>sequential_vertex_coloring</tt></a>

+has been updated, tested, and documented.</li>
+</ul>
+</li>
+</ul>
+<br>
+<hr>
+<table>
+<tbody>
+<tr valign="top">
+<td nowrap="nowrap">Copyright (c) 2000-2001</td>
+<td> <a href="../../../people/jeremy_siek.htm">Jeremy
+Siek</a>,

+Indiana University (<ahref="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>) 

+<a href="../../../people/liequan_lee.htm">Lie-Quan

+Lee</a>, Indiana University (<ahref="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</a>) 

+<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>
\ No newline at end of file

Modified: trunk/libs/graph/doc/index.html
==============================================================================
--- trunk/libs/graph/doc/index.html     (original)
+++ trunk/libs/graph/doc/index.html     Fri Jun 26 00:01:13 2009
@@ -1,302 +1,372 @@
-<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>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>
+
+
+
+
+  <title>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">
+
+<br clear="">
+
+
+

 <h1>The Boost Graph Library (BGL)
 <a href="http://www.awprofessional.com/title/0201729148";>
-<img src="bgl-cover.jpg" ALT="BGL Book" ALIGN="RIGHT"></a>
+<img src="bgl-cover.jpg" alt="BGL Book" align="right"></a>
 </h1>

-<P>
-Graphs are mathematical abstractions that are useful for solving many
-types of problems in computer science. Consequently, these
-abstractions must also be represented in computer programs.  A
-standardized generic interface for traversing graphs is of utmost
-importance to encourage reuse of graph algorithms and data structures.
-Part of the Boost Graph Library is a generic interface that allows
-access to a graph's structure, but hides the details of the
-implementation.  This is an ``open'' interface in the sense that any
-graph library that implements this interface will be interoperable
-with the BGL generic algorithms and with other algorithms that also
-use this interface. The BGL provides some general purpose graph classes
-that conform to this interface, but they are not meant to be the
-``only'' graph classes; there certainly will be other graph classes
-that are better for certain situations.  We believe that the main
-contribution of the The BGL is the formulation of this interface.
-
-<P>
-The BGL graph interface and graph components are <I>generic</I>, in the
-same sense as the the Standard Template Library (STL)&nbsp;[<A
-HREF="bibliography.html#austern99:_gener_progr_stl">2</A>].
-
-In the following sections, we review the role that generic programming
-plays in the STL and compare that to how we applied generic
-programming in the context of graphs.
-
-<P>
-Of course, if you are already are familiar with generic programming,
-please dive right in! Here's the <a
-href="./table_of_contents.html">Table of Contents</a>.
-
-<P>
-The source for the BGL is available as part of the Boost distribution,

-which you can <ahref="http://sourceforge.net/project/showfiles.php?group_id=7586";>

-download from here</a>.
-
-<H2>How to Build the BGL</H2>
-<p><b>DON'T!</b> The Boost Graph Library is a header-only library and
-does not need to be built to be used. The only exception is the <a
-href="read_graphviz.html">GraphViz input parser</a>.</p>
-
-<p>When compiling programs that use the BGL, <b>be sure to compile
-with optimization</b>. For instance, select "Release" mode with
-Microsoft Visual C++ or supply the flag <tt>-O2</tt> or <tt>-O3</tt>
-to GCC. </p>
-
-<H2>Genericity in STL</H2>
-
-<P>
-There are three ways in which the STL is generic.
-
-<P>
-
-<H3>Algorithm/Data-Structure Interoperability</H3>
-
-<P>
-First, each algorithm is written in a data-structure neutral way,
-allowing a single template function to operate on many different
-classes of containers. The concept of an iterator is the key
-ingredient in this decoupling of algorithms and data-structures.  The
-impact of this technique is a reduction in the STL's code size from
-<i>O(M*N)</i> to <i>O(M+N)</i>, where <i>M</i> is the number of
-algorithms and <i>N</i> is the number of containers. Considering a
-situation of 20 algorithms and 5 data-structures, this would be the
-difference between writing 100 functions versus only 25 functions! And
-the differences continues to grow faster and faster as the number of
-algorithms and data-structures increase.
-
-<P>
-
-<H3>Extension through Function Objects</H3>
-
-<P>
-The second way that STL is generic is that its algorithms and containers
-are extensible. The user can adapt and customize the STL through the
-use of function objects. This flexibility is what makes STL such a
-great tool for solving real-world problems. Each programming problem
-brings its own set of entities and interactions that must be
-modeled. Function objects provide a mechanism for extending the STL to
-handle the specifics of each problem domain.
-
-<P>
-
-<H3>Element Type Parameterization</H3>
-
-<P>
-The third way that STL is generic is that its containers are
-parameterized on the element type. Though hugely important, this is
-perhaps the least ``interesting'' way in which STL is generic.
-Generic programming is often summarized by a brief description of

-parameterized lists such as <TT>std::list<T></TT>. This hardlyscratches

-the surface!
-
-<P>
-
-<H2>Genericity in the Boost Graph Library</A>
-</H2>
-
-<P>
-Like the STL, there are three ways in which the BGL is generic.
-
-<P>
-
-<H3>Algorithm/Data-Structure Interoperability</H3>
-
-<P>
-First, the graph algorithms of the BGL are written to an interface that
-abstracts away the details of the particular graph data-structure.
-Like the STL, the BGL uses iterators to define the interface for
-data-structure traversal. There are three distinct graph traversal
-patterns: traversal of all vertices in the graph, through all of the
-edges, and along the adjacency structure of the graph (from a vertex
-to each of its neighbors). There are separate iterators for each
-pattern of traversal.
-
-<P>
-This generic interface allows template functions such as <a
-href="./breadth_first_search.html"><TT>breadth_first_search()</TT></a>
-to work on a large variety of graph data-structures, from graphs
-implemented with pointer-linked nodes to graphs encoded in
-arrays. This flexibility is especially important in the domain of
-graphs. Graph data-structures are often custom-made for a particular
-application. Traditionally, if programmers want to reuse an
-algorithm implementation they must convert/copy their graph data into
-the graph library's prescribed graph structure.  This is the case with
-libraries such as LEDA, GTL, Stanford GraphBase; it is especially true
-of graph algorithms written in Fortran. This severely limits the reuse
-of their graph algorithms.
-
-<P>
-In contrast, custom-made (or even legacy) graph structures can be used
-as-is with the generic graph algorithms of the BGL, using <I>external
-adaptation</I> (see Section <A HREF="./leda_conversion.html">How to
-Convert Existing Graphs to the BGL</A>).  External adaptation wraps a new
-interface around a data-structure without copying and without placing
-the data inside adaptor objects.  The BGL interface was carefully
-designed to make this adaptation easy. To demonstrate this, we have
-built interfacing code for using a variety of graph dstructures (LEDA
-graphs, Stanford GraphBase graphs, and even Fortran-style arrays) in
-BGL graph algorithms.
-
-<P>
-
-<H3>Extension through Visitors</H3>
-
-<P>

-Second, the graph algorithms of the BGL are extensible. The BGL introducesthe

-notion of a <I>visitor</I>, which is just a function object with
-multiple methods.  In graph algorithms, there are often several key
-``event points'' at which it is useful to insert user-defined
-operations. The visitor object has a different method that is invoked
-at each event point. The particular event points and corresponding
-visitor methods depend on the particular algorithm.  They often
-include methods like <TT>start_vertex()</TT>,
-<TT>discover_vertex()</TT>, <TT>examine_edge()</TT>,
-<tt>tree_edge()</tt>, and <TT>finish_vertex()</TT>.
-
-<P>
-
-<H3>Vertex and Edge Property Multi-Parameterization</H3>
-
-<P>
-The third way that the BGL is generic is analogous to the parameterization
-of the element-type in STL containers, though again the story is a bit
-more complicated for graphs. We need to associate values (called
-"properties") with both the vertices and the edges of the graph.
-In addition, it will often be necessary to associate
-multiple properties with each vertex and edge; this is what we mean
-by multi-parameterization.
-The STL <tt>std::list&lt;T&gt;</tt> class has a parameter <tt>T</tt>
-for its element type. Similarly, BGL graph classes have template
-parameters for vertex and edge ``properties''. A
-property specifies the parameterized type of the property and also assigns
-an identifying tag to the property. This tag is used to distinguish
-between the multiple properties which an edge or vertex may have. A
-property value that is attached to a
-particular vertex or edge can be obtained via a <I>property
-map</I>. There is a separate property map for each property.
-
-<P>
-Traditional graph libraries and graph structures fall down when it
-comes to the parameterization of graph properties. This is one of the
-primary reasons that graph data-structures must be custom-built for
-applications. The parameterization of properties in the  BGL graph
-classes makes them well suited for re-use.
+
+
+

+在计算机科学中，图是一些用来解决各种问题的数学抽象概念。所以，这些抽象的概念一定可以用计算机程序表示。一个标准化的用来遍历图的通用接口，对+于图的算法和数据结构来说是相当重要的。Boost图库中专门有一些用来访问图数据结构的通用接口，它们隐藏了繁杂的内部实现。这是一套"开放"的接口，一些+用其它图库实现的接口也能够使用BGL中的通用算法，而且这套接口也能使用BGL中其它算法。BGL提供了一些遵守这套接口的通用类，但是不要以为这是"唯+一"的图类；BGL中当然还有一些能够更好地解决特定问题的类。我们相信BGL最大的贡献就是规范化了这套接口。

+</p>
+
+

+与STL[<a href="bibliography.html#austern99:_gener_progr_stl">2</a>]相类似，BGL中的接口和组件也是泛型的。接下来的几节，我们将回顾一下范型编程在STL中扮演的角色，以及比较一下我们如何把泛型编程应用到图的环境中。 

+
+</p>
+

 <p>

+当然，如果你已经对范型编程很熟悉了，那么请跳到<ahref="table_of_contents.html">目录</a>继续阅读下面章节。

+
+</p>
+
+
+<p>

+BGL的源代码是随着Boost一起发布的，到这<ahref="http://sourceforge.net/project/showfiles.php?group_id=7586";>下载</a>。

+
+</p>
+
+
+<h2>如何编译BGL<br>
+
+
+</h2>
+
+
+

+不需要！Boost图库仅仅是一些头文件，所以不需要编译。唯一的例外是： <a href="read_graphviz.html">GraphViz 输入分析器</a>。

+
+

+在编译的时候，别忘了开启编译优化选项。比如，在Ms Visual C++中选择"Release"模式；在GCC中使用-o2或者-o3标志。

+<h2>STL中的泛型<br>
+
+
+</h2>
+
+
+
+
+
+
+
+<p>STL中用三种方法来实现泛型化</p>
+
+
+<h3>算法/数据结构互通性<br>
+
+
+</h3>
+
+
+
+
+
+
+

+首先，每一个算法都是用数据结构无关的方法写出的，允许一个单独的函数模版处理多种不同的容器类。迭代器的概念是实现算法和数据结构解耦的关键因

+素。

+这个方法最明显的效果就是缩小了STL的代码尺寸，使其从O(M*N)变成了O(M+N)，其中M是算法个数，N是容器个数。试想，如果有20个算法、5+个数据结构，采用泛型编程与不采用的区别是：由写100个函数变成写25个函数！随着算法和数据结构数量的增加这个差距会越来越大。

+
+
+<h3>通过函数对象扩展<br>
+
+
+</h3>
+
+

+STL泛型化的第二种方法是算法和容器可扩展。用户能够通过函数对象改写和定制STL。这样的灵活性使STL成为解决现实问题的有力工具。每一个编程问题对应它自己的一组实体和被规范化的接口。函数对象提供了一种机制，它能够扩展STL以处理特定领域的问题。

+<h3>元素类型参数化<br>
+
+
+</h3>
+
+

+STL泛型化的第三种方法是参数化容器的元素类型。虽然也很重要，但这种方法在STL泛型化中可能是最不"被感兴趣"的方法。泛型编程中经常简写参数化列表，例如：std::list<T>。以上仅仅是泛型编程的冰山一角。

+<h2>Boost图库中的泛型
+</h2>
+
+
+
+
+
+
+
+<p>与STL一样，BGL中也有3种泛型方法</p>
+
+
+<h3>算法/数据结构的互操作性<br>
+</h3>
+
+
+
+

+第一种，BGL中的图算法被写成了一种把具体数据结构细节抽象出来的接口。与STL相同，BGL也是用迭代器(iterator)来定义遍历相关数+据结构的接口。有3种完全不同的遍历模式：遍历图中所有的顶点，遍历图中所有的边，以及沿相邻结构进行遍历（从一个顶点到它的每一相邻顶点）。每一种遍历方式

+需要一种迭代器。<br>
+</p>
+
+

+这种泛型接口能够使模板函数（例如： <ahref="./breadth_first_search.html"><tt>breadth_first_search()</tt></a>+函数）接受各种图数据结构，从链表表示的图到数组表示的图都可以。在图领域这种灵活性是相当重要的。图数据结构经常为了某些特殊需求而进行定制。传统上，如果+程序员想要复用一个算法，他们一定要把自己的数据结构转换/拷贝成图库所规定的数据结构才行。比如LEDA，GTL，Stanford+GraphBase就是这种情况；特别是用Fortran写成的图算法更需要这种转换。这种转换严重地限制了图算法的复用性。

+</p>
+
+
+
+
+

+相比之下，定制的图数据结构能够被BGL中的泛型算法统一对待，BGL使用一种叫做外部适配（external adaptation）（参考 <a href="./leda_conversion.html">如何把已有的图转换到BGL中</a>一+节）的方法来实现该技术。外部适配封装了一个新的接口，得使数据结构不用进行拷贝，也不用把数据置于适配对象内部。BGL相关接口使这种转换变得很容易。举例来

+说，在BGL中，我们已为使经用各种图数据结构（比如：LEDA图，Stanford
+GraphBase图，甚是还有Fortran风格的数组）建立了相应的接口代码。</p>
+
+
+<h3>用遍历器（vistitor）进行扩展</h3>
+
+
+
+
+
+
+

+第二种，BGL中的图算法是可扩展的。BGL引入了遍历器（visitor）的概念，遍历器就是一个有多个方法的功能实体。在图算法中，经常会有几+个关键的"事件点"使用户插入一些操作。在每个"事件点"，遍历器对象会有不同的方法被调用。+"事件点"以及对应的遍历器方法都依赖于相应的算法。遍历器经常包括的方法有：start_vertex(), discover_vertex(), examine_edge(), tree_edge(), 以及finish_vertex().

+
+
+<h3>点、边属性的多重参数化</h3>
+
+
+
+

+BGL中的第三种泛型方法与STL容器中的元素类型参数化相似，虽然这点对于图来说有些复杂。我们需要给图的边、点赋予相关含义（属性）。另外，有

+时候需要给各个点、边赋予多重属性；这意味这需要多重参数化。STL的

+std::list<T>类有一个参数T作为它的元素类型。类似地，BGL中的图类也有模板参数作为边、点的属性。一个属性详细说明了该属性的+参数化类型，并且分配了标识该属性的标签。标签用来区分边或点的多重属性。附着到特定的点或边的属性能够通过属性映射（property

+map）获得。每一个属性有一个单独的属性映射。
+
+</p>
+
+
+
+
+

+传统的图库和图数据结构在图属性的参数化方面做得不是很好。这也是图数据结构一定要针对应用进行定制的主要原因之一。BGL中的属性参数化能够使BGL中的图类更适于复用。

+
+
+<h2>算法</h2>
+
+
+
+
+
+
+

+BGL中的算法由一组核心算法模型（用泛型算法实现）和一组较大的图算法组成。核心算法模型是：

+
+
+<ul>
+
+
+
+  <li>广度优先搜索
+  </li>
+
+
+
+  <li>深度优先搜索
+  </li>
+
+
+
+  <li>均匀开销搜索
+  </li>
+
+
+
+</ul>

+图算法模型本身并不进行任何有意义的计算，它们只是用于构建图算法的积木。当前，BGL中的图算法包括有：

+<ul>
+
+
+
+  <li>Dijkstra最短路径</li>
+
+
+
+  <li>Bellman-Ford最短路径</li>
+
+
+
+  <li>Johnson任意两点间最短路径</li>
+
+
+
+  <li>Kruskal最小生成树</li>
+
+
+
+  <li>Prim最小生成树</li>
+
+
+
+  <li>连通分支</li>
+
+
+
+  <li>强连通分支</li>
+
+
+
+  <li>动态连通分支（使用不相交集合）</li>
+
+
+
+  <li>拓扑排序</li>
+
+
+
+  <li>转置</li>
+
+
+
+  <li>逆Cuthill Mckee排序</li>
+
+
+
+  <li>Smallest Last Vertex Ordering</li>
+
+
+
+  <li>顺序顶点染色</li>
+
+
+
+</ul>
+
+
+
+
+
+
+
+<h2>数据结构</h2>
+
+
+
+
+
+
+
+<p>BGL当前提供2个图类和一个边列表适配器：</p>
+
+
+<ul>
+
+
+
+  <li><a href="adjacency_list.html"><tt>adjacency_list</tt></a></li>
+
+
+
+  <li><a href="adjacency_matrix.html"><tt>adjacency_matrix</tt></a></li>
+
+
+
+  <li><a href="edge_list.html"><tt>edge_list</tt></a></li>
+
+
+
+</ul>
+
+
+
+

+adjacency_list类好比图类中的"瑞士军刀"。它高度参数化，以致于能够为各种情况优化，例如：有向图还是无向图，允许还是不允许平行边，仅出边能有效访问还是出入边都可以，是否以空间为代价进行快速顶点插入或移出，等等。

+
+</p>
+
+
+
+
+

+adjacency_matrix类把边存储在一个|V|x|V|的矩阵中（其中，|V|表示顶点个数）。矩阵元素表示图中的边。邻接矩阵尤其适合表示稠密图（dense graphs），比如,有|V|2条边的图。 +edge_list类是一个能接受任何边迭代器的适配器，实现了一个<ahref="./EdgeListGraph.html">边列表图(Edge List Graph</a>)。 

+
+
+
+</p>
+
+
+<hr>
+<table>
+
+
+
+  <tbody>
+
+
+    <tr valign="top">
+
+
+
+      <td nowrap="nowrap">Copyright (c) 2000-2001</td>
+
+
+      <td>
+      <a href="../../../people/jeremy_siek.htm">Jeremy Siek</a>,

+Indiana University (<ahref="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>) 

+
+
+

+ <a href="../../../people/liequan_lee.htm">Lie-Quan Lee</a>, IndianaUniversity (<ahref="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</a>) 

+
+
+
+      <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>
+

-<H2>Algorithms</H2>

-<P>
-The BGL algorithms consist of a core set of algorithm <I>patterns</I>
-(implemented as generic algorithms) and a larger set of graph
-algorithms. The core algorithm patterns are
-
-<P>
-
-<UL>
-<LI>Breadth First Search
-</LI>
-<LI>Depth First Search
-</LI>
-<LI>Uniform Cost Search
-</LI>
-</UL>
-
-<P>
-By themselves, the algorithm patterns do not compute any meaningful
-quantities over graphs; they are merely building blocks for
-constructing graph algorithms. The graph algorithms in the BGL currently
-include
-
-<P>
-
-<UL>
-<LI>Dijkstra's Shortest Paths</LI>
-<LI>Bellman-Ford Shortest Paths</LI>
-<LI>Johnson's All-Pairs Shortest Paths</LI>
-<LI>Kruskal's Minimum Spanning Tree</LI>
-<LI>Prim's Minimum Spanning Tree</LI>
-<LI>Connected Components</LI>
-<LI>Strongly Connected Components</LI>
-<LI>Dynamic Connected Components (using Disjoint Sets)</LI>
-<LI>Topological Sort</LI>
-<LI>Transpose</LI>
-<LI>Reverse Cuthill Mckee Ordering</LI>
-<LI>Smallest Last Vertex Ordering</LI>
-<LI>Sequential Vertex Coloring</LI>
-</UL>
-
-<P>
-
-<H2>Data Structures</H2>
-
-<P>
-The BGL currently provides two graph classes and an edge list adaptor:
-<P>
-
-<UL>
-<LI><a href="adjacency_list.html"><TT>adjacency_list</TT></a></LI>
-<LI><a href="adjacency_matrix.html"><TT>adjacency_matrix</TT></a></LI>
-<LI><a href="edge_list.html"><TT>edge_list</TT></a></LI>
-</UL>
-
-<P>
-The <TT>adjacency_list</TT> class is the general purpose ``swiss army
-knife'' of graph classes. It is highly parameterized so that it can be
-optimized for different situations: the graph is directed or
-undirected, allow or disallow parallel edges, efficient access to just
-the out-edges or also to the in-edges, fast vertex insertion and
-removal at the cost of extra space overhead, etc.
-
-<P>
-The <tt>adjacency_matrix</tt> class stores edges in a <i>|V| x |V|</i>
-matrix (where <i>|V|</i> is the number of vertices). The elements of
-this matrix represent edges in the graph. Adjacency matrix
-representations are especially suitable for very dense graphs, i.e.,
-those where the number of edges approaches <i>|V|<sup>2</sup></i>.
-
-<P>
-The <TT>edge_list</TT> class is an adaptor that takes any kind of edge

-iterator and implements an <a href="./EdgeListGraph.html">Edge ListGraph</a>.

-
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
-Indiana University (<A
-HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>

-<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>,Indiana University (<AHREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>) 

-<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
-Indiana University (<A
-HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
-</TD></TR></TABLE>

-</BODY>
-</HTML>
+</body></html>
\ No newline at end of file

Modified: trunk/libs/graph/doc/publications.html
==============================================================================
--- trunk/libs/graph/doc/publications.html      (original)
+++ trunk/libs/graph/doc/publications.html      Fri Jun 26 00:01:13 2009
@@ -1,46 +1,41 @@
-<HTML>
-<!--
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

+<html><head><meta content="text/html; charset=UTF-8"http-equiv="content-type"><!--

   -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
   --
   -- Distributed under the Boost Software License, Version 1.0.
   -- (See accompanying file LICENSE_1_0.txt or copy at
   -- http://www.boost.org/LICENSE_1_0.txt)
   -->
-<Head>
-<Title>Boost Graph Library: Publications</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
-        ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
-     ALT="C++ Boost" width="277" height="86">
+<title>Boost Graph Library: Publications</title></head>

-<BR Clear>

+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"vlink="#551a8b">

+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">

-<h1>Boost Graph Library Related Publications</h1>
+<br clear="">
+
+<h1>Boost Graph Library Related Publications 与BGL相关的出版物</h1>

 <ul>

-<li><a href="http://www.ddj.com/articles/2000/0009/0009toc.htm";>Dr. Dobb'sSept. 2000 Article</a></a></li>+<li><a href="http://www.ddj.com/articles/2000/0009/0009toc.htm";>Dr. Dobb'sSept. 2000 Article</a></li><li><ahref="http://www.acm.org/pubs/citations/proceedings/oops/320384/p399-siek/";>OOPSLA'99GGCL Paper</a></li><li>Lie-Quan Lee's Master's Thesis about GGCL<ahref="http://www.lsc.nd.edu/downloads/research/ggcl/papers/thesis.ps";>(ps)</a><ahref="http://www.lsc.nd.edu/downloads/research/ggcl/papers/thesis.pdf";>(pdf)</a></li>-<li><ahref="http://www.dietmar-kuehl.de/generic-graph-algorithms.pdf";>DietmarKühl's Master's Thesis: Design Pattern for the Implementation of GraphAlgorithms</a></li>+<li><ahref="http://www.dietmar-kuehl.de/generic-graph-algorithms.pdf";>DietmarKühl's Master's Thesis: Design Pattern for the Implementation of GraphAlgorithms</a></li><li>ISCOPE'99 Sparse Matrix Ordering <ahref="./iscope99.pdf">(pdf)</a></li><li><a href="http://www.oonumerics.org/tmpw00/";>C++ Template Workshop2000</a>, Concept Checking</li>

 </ul>


 <br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
-Indiana University (<A
-HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>

-<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>,Indiana University (<AHREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>) 

-<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
-Indiana University (<A
-HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
+<hr>
+<table>
+<tbody><tr valign="top">
+<td nowrap="nowrap">Copyright (c) 2000-2001</td><td>
+<a href="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</a>,

+<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/quick_tour.html
==============================================================================
--- trunk/libs/graph/doc/quick_tour.html        (original)
+++ trunk/libs/graph/doc/quick_tour.html        Fri Jun 26 00:01:13 2009
@@ -1,6 +1,8 @@
-<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.
@@ -8,600 +10,730 @@
   -- http://www.boost.org/LICENSE_1_0.txt)
   -->

-<head>
-<title>Quick Tour of Boost Graph Library</title>
-<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
-<meta name="ProgId" content="FrontPage.Editor.Document">
-</head>
-

-<body bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b"alink="#ff0000">

-<img src="../../../boost.png" alt="C++ Boost" width="277" height="86"><brclear>

-<h1>A Quick Tour of the Boost Graph Library</h1>

-The domain of graph data structures and algorithms is in some respectsmore-complicated than that of containers. The abstract iterator interface usedby STL-is not sufficiently rich to encompass the numerous ways that graphalgorithms-may traverse a graph. Instead, we formulate an abstract interface thatserves

-the same purpose for graphs that iterators do for basic containers (though

-iterators still play a large role). <a href="#fig:analogy">Figure 1</a>depicts

-the analogy between the STL and the BGL.
-<p>&nbsp;</p>
-<div align="CENTER">
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+

+ <title>Quick Tour of Boost Graph Library</title><meta name="GENERATOR"content="Microsoft FrontPage 4.0">

+
+
+
+
+
+
+
+
+
+
+
+  <meta name="ProgId" content="FrontPage.Editor.Document"></head>

+<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000"vlink="#551a8b">

+
+
+
+
+
+
+

+<img src="../../../boost.png" alt="C++ Boost" height="86" width="277"><brclear="">

+
+
+
+
+
+
+<h1>Boost图库快速指南<br>
+
+
+
+
+
+</h1>
+
+
+
+
+
+
+
+

+图数据结构和算法在某些方面比容器更加复杂。STL中使用的抽象迭代器不能完全适用于图算法中的各种遍历方法。因此，我们专门有一个抽象接口给图使用，该接口就像基本容器中的迭代器（迭代器仍然占有很重要的角色）。为此，<ahref="#fig:analogy">图1</a>对BGL和STL做了比较。 

+
+
+
+&nbsp;</p>
+
+
+
+
+
+
+<div align="center">
   <a name="fig:analogy"></a><a name="752"></a>
-  <table>

- <caption valign="bottom">Figure 1: The analogybetween the

-      STL and the BGL.</caption>
+
+<table>
+
+
+
+
+
+
+    <caption valign="bottom"><strong>图1：BGL和STL比较</strong></caption>
+    <tbody>
+
+
+
+
+
     <tr>
-      <td><img src="figs/analogy.gif" width="518" height="335"></td>
+
+
+
+
+
+
+      <td><img src="figs/analogy.gif" height="335" width="518"></td>
+
+
+
+
+
+
     </tr>
-  </table>
+
+
+
+
+
+
+
+
+
+
+
+
+  </tbody>
+</table>
+
+
+
+
+
+
 </div>
+
+
+
+
+
+
 <p>&nbsp;</p>

-The graph abstraction consists of a set of vertices (or nodes), and a setof-edges (or arcs) that connect the vertices. <ahref="#fig:quick-start">Figure 2</a>-depicts a directed graph with five vertices (labeled 0 through 4) and 11edges.-The edges leaving a vertex are called the out-edges of the vertex.The

-edges <tt>{(0,1),(0,2),(0,3),(0,4)}</tt> are all out-edges of vertex 0. The

-edges entering a vertex are called the in-edges of the vertex. Theedges <tt>{(0,4),(2,4),(3,4)}</tt>

-are all in-edges of vertex 4.
+
+

+图的抽象表示是由一组顶点（或称：节点）和一组连接顶点的边（或称：弧）组成的。 <a href="#fig:quick-start">图2</a>+表示的是一个由5个顶点（标号：0－4）和11条边组成的有向图。从一个顶点出去的边叫做该顶点的出边。边{(0,1),(0,2),(0,3),+(0,4)}全都是顶点0的出边。进入一点的边叫做该点的入边。边{(0,4),(2,4),(3,4)}全都是顶点4的入边。

 <p>&nbsp;</p>
-<div align="CENTER">
+
+
+
+
+
+
+<div align="center">
   <a name="fig:quick-start"></a>
-  <table>

- <caption valign="bottom">Figure 2: An example of adirected

-      graph.</caption>
+
+<table>
+
+
+
+
+
+
+    <caption valign="bottom"><strong>图2：一个有向图例子</strong></caption>
+    <tbody>
+
+
+
+
+
     <tr>
-      <td><img src="figs/quick_start.gif" width="103" height="124"></td>
+
+
+
+
+
+
+      <td><img src="figs/quick_start.gif" height="124" width="103"></td>
+
+
+
+
+
+
     </tr>
-  </table>
+
+
+
+
+
+
+
+
+
+
+
+
+  </tbody>
+</table>
+
+
+
+
+
+
 </div>
+
+
+
+
+
+
 <p>&nbsp;</p>

-In the following sections we will use the BGL to construct this examplegraph-and manipulate it in various ways. The complete source code for thisexample can-be found in <ahref="../example/quick_tour.cpp"><tt>examples/quick_tour.cpp</tt></a>.-Each of the following sections discusses a "slice" of thisexample

-file. Excerpts from the output of the example program will also be listed.
-<p>&nbsp;
-<h2>Constructing a Graph</h2>

-In this example we will use the BGL <ahref="adjacency_list.html"><tt>adjacency_list</tt></a>-class to demonstrate the main ideas in the BGL interface. The<tt>adjacency_list</tt>-class provides a generalized version of the classic "adjacencylist"

-data structure. The <tt>adjacency_list</tt> is a template class with six

-template parameters, though here we only fill in the first threeparameters and-use the defaults for the remaining three. The first two template arguments(<tt>vecS,-vecS</tt>) determine the data structure used to represent the out-edgesfor each-vertex in the graph and the data structure used to represent the graph'svertex-set (see section <ahref="using_adjacency_list.html#sec:choosing-graph-type">Choosing

-the <tt>Edgelist</tt> and <tt>VertexList</tt></a> for information about the

-tradeoffs of the different data structures). The third argument,<tt>bidirectionalS</tt>,

-selects a directed graph that provides access to both out and in-edges. The
-other options for the third argument are <tt>directedS</tt> which selects a

-directed graph with only out-edges, and <tt>undirectedS</tt> which selectsan

-undirected graph.

-Once we have the graph type selected, we can create the graph in <ahref="#fig:quick-start">Figure-2</a> by declaring a graph object and filling in edges using the <ahref="MutableGraph.html#sec:add-edge"><tt>add_edge()</tt></a>-function of the <a href="MutableGraph.html">MutableGraph</a> interface(which <tt>adjacency_list</tt>

-implements). We use the array of pairs <tt>edge_array</tt> merely as a
-convenient way to explicitly create the edges for this example.
-<p>&nbsp;
-<pre>
-  #include &lt;iostream&gt;                  // for std::cout
-  #include &lt;utility&gt;                   // for std::pair
-  #include &lt;algorithm&gt;                 // for std::for_each
-  #include &lt;boost/graph/graph_traits.hpp&gt;
-  #include &lt;boost/graph/adjacency_list.hpp&gt;
-  #include &lt;boost/graph/dijkstra_shortest_paths.hpp&gt;
-
-  using namespace boost;
-
-  int main(int,char*[])
-  {
-    // create a typedef for the Graph type
-    typedef adjacency_list&lt;vecS, vecS, bidirectionalS&gt; Graph;
-
-    // Make convenient labels for the vertices
-    enum { A, B, C, D, E, N };
-    const int num_vertices = N;
-    const char* name = "ABCDE";
-
-    // writing out the edges in the graph
-    typedef std::pair&lt;int, int&gt; Edge;
-    Edge edge_array[] =
-    { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
-      Edge(C,E), Edge(B,D), Edge(D,E) };
-    const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
-
-    // declare a graph object
-    Graph g(num_vertices);
-
-    // add the edges to the graph object
-    for (int i = 0; i &lt; num_edges; ++i)
-      add_edge(edge_array[i].first, edge_array[i].second, g);
-    ...
-    return 0;
-  }
-</pre>

-Instead of calling the <tt>add_edge()</tt> function for each edge, wecould-use the <a href="adjacency_list.html#sec:iterator-constructor">edgeiterator-constructor</a> of the graph. This is typically more efficient than using<tt>add_edge()</tt>.-Pointers to the <tt>edge_array</tt> can be viewed as iterators, so we cancall-the iterator constructor by passing pointers to the beginning and end ofthe

-array.
-<pre>

- Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge),num_vertices);

-</pre>

-Instead of creating a graph with a certain number of vertices to beginwith,-it is also possible to add and remove vertices with the <ahref="MutableGraph.html#sec:add-vertex"><tt>add_vertex()</tt></a>-and <ahref="MutableGraph.html#sec:remove-vertex"><tt>remove_vertex()</tt></a>-functions, also of the <a href="MutableGraph.html">MutableGraph</a>interface.

-<h2>Accessing the Vertex Set</h2>

-Now that we have created a graph, we can use the graph interface toaccess-the graph data in different ways. First we can access all of the verticesin the-graph using the <ahref="VertexListGraph.html#sec:vertices"><tt>vertices()</tt></a>-function of the <a href="VertexListGraph.html">VertexListGraph</a>interface.-This function returns a <tt>std::pair</tt> of vertex iterators (the<tt>first</tt>-iterator points to the "beginning" of the vertices and the<tt>second</tt>-iterator points "past the end"). Dereferencing a vertex iteratorgives-a vertex object. The type of the vertex iterator is given by the <ahref="graph_traits.html"><tt>graph_traits</tt></a>-class. Note that different graph classes can have different associatedvertex-iterator types, which is why we need the <tt>graph_traits</tt> class.Given some-graph type, the <tt>graph_traits</tt> class will provide access to the<tt>vertex_iterator</tt>

-type.

-The following example prints out the index for each of the vertices inthe

-graph. All vertex and edge properties, including index, are accessed via

-property map objects. The <ahref="property_map.html"><tt>property_map</tt></a>-class is used to obtain the property map type for a specific property(specified-by <tt>vertex_index_t</tt>, one of the BGL predefined properties) andfunction

-call <tt>get(vertex_index, g)</tt> returns the actual property map object.
-<p>&nbsp;
-<pre>
-  // ...
-  int main(int,char*[])
-  {
-    // ...
-
-    // get the property map for vertex indices
-    typedef property_map&lt;Graph, vertex_index_t&gt;::type IndexMap;
-    IndexMap index = get(vertex_index, g);
-
-    std::cout &lt;&lt; &quot;vertices(g) = &quot;;
-    typedef graph_traits&lt;Graph&gt;::vertex_iterator vertex_iter;
-    std::pair&lt;vertex_iter, vertex_iter&gt; vp;
-    for (vp = vertices(g); vp.first != vp.second; ++vp.first)
-      std::cout &lt;&lt; index[*vp.first] &lt;&lt;  &quot; &quot;;
-    std::cout &lt;&lt; std::endl;
-    // ...
-    return 0;
-  }
-</pre>
-The output is:
-<pre>
-  vertices(g) = 0 1 2 3 4
-</pre>
-<p>&nbsp;
-<h2>Accessing the Edge Set</h2>

-The set of edges for a graph can be accessed with the <ahref="EdgeListGraph.html#sec:edges"><tt>edges()</tt></a>

-function of the <a href="EdgeListGraph.html">EdgeListGraph</a> interface.

-Similar to the <tt>vertices()</tt> function, this returns a pair ofiterators,-but in this case the iterators are edge iterators. Dereferencing anedge

-iterator gives an edge object. The <tt>source()</tt> and <tt>target()</tt>

-functions return the two vertices that are connected by the edge. Insteadof-explicitly creating a <tt>std::pair</tt> for the iterators, this time wewill-use the <ahref="../../tuple/doc/tuple_users_guide.html#tiers"><tt>tie()</tt></a>helper function.-This handy function can be used to assign the parts of a<tt>std::pair</tt> into-two separate variables, in this case <tt>ei</tt> and <tt>ei_end</tt>. Thisis-usually more convenient than creating a <tt>std::pair</tt> and is ourmethod of

-choice for the BGL.
-<p>&nbsp;
-<pre>
-  // ...
-  int main(int,char*[])
-  {
-    // ...
-    std::cout &lt;&lt; &quot;edges(g) = &quot;;
-    graph_traits&lt;Graph&gt;::edge_iterator ei, ei_end;
-    for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
-        std::cout &lt;&lt; &quot;(&quot; &lt;&lt; index[source(*ei, g)]

- << "," << index[target(*ei, g)]<< ") ";

-    std::cout &lt;&lt; std::endl;
-    // ...
-    return 0;
-  }
-</pre>
-The output is:
-<pre>
-  edges(g) = (0,1) (0,2) (0,3) (0,4) (2,0) (2,4) (3,0)
-    (3,1) (3,4) (4,0) (4,1)
-</pre>
-<p>&nbsp;
-<h2>The Adjacency Structure</h2>

-In the next few examples we will explore the adjacency structure of thegraph-from the point of view of a particular vertex. We will look at thevertices'-in-edges, out-edges, and its adjacent vertices. We will encapsulate thisin an-"exercise vertex" function, and apply it to each vertex in thegraph.-To demonstrate the STL-interoperability of BGL, we will use the STL<tt>for_each()</tt>

-function to iterate through the vertices and apply the function.
-<p>&nbsp;
-<pre>
-  //...
-  int main(int,char*[])
-  {
-    //...
-    std::for_each(vertices(g).first, vertices(g).second,
-                  exercise_vertex&lt;Graph&gt;(g));
-    return 0;
-  }
-</pre>
-<p>We use a functor for <tt>exercise_vertex</tt> instead of just a function

-because the graph object will be needed when we access information abouteach-vertex; using a functor gives us a place to keep a reference to the graphobject

-during the execution of the <tt>std::for_each()</tt>. Also we template the

-functor on the graph type so that it is reusable with different graphclasses.

-Here is the start of the <tt>exercise_vertex</tt> functor:
-<p>&nbsp;
-<pre>
-  template &lt;class Graph&gt; struct exercise_vertex {
-    exercise_vertex(Graph&amp; g_) : g(g_) {}
-    //...
-    Graph&amp; g;
-  };
-</pre>
-<p>&nbsp;
-<h3>Vertex Descriptors</h3>

-The first thing we need to know in order to write the<tt>operator()</tt>

-method of the functor is the type for the vertex objects of the graph. The
-vertex type will be the parameter to the <tt>operator()</tt> method. To be

-precise, we do not deal with actual vertex objects, but rather withvertex-descriptors. Many graph representations (such as adjacency lists) donot-store actual vertex objects, while others do (e.g., pointer-linkedgraphs). This

-difference is hidden underneath the &quot;black-box&quot; of the vertex

-descriptor object. The vertex descriptor is something provided by eachgraph-type that can be used to access information about the graph via the<tt>out_edges()</tt>,-<tt>in_edges()</tt>, <tt>adjacent_vertices()</tt>, and property mapfunctions-that are described in the following sections. The<tt>vertex_descriptor</tt>-type is obtained through the <tt>graph_traits</tt> class. The<tt>typename</tt>-keyword used below is necessary because the type on the left hand side ofthe

-scope <tt>::</tt> operator (the <tt>graph_traits&lt;Graph&gt;</tt> type) is
-dependent on a template parameter (the <tt>Graph</tt> type). Here is how we
-define the functor's apply method:
-<p>&nbsp;
-<pre>
-  template &lt;class Graph&gt; struct exercise_vertex {
-    //...
-    typedef typename graph_traits&lt;Graph&gt;
-      ::vertex_descriptor Vertex;
-
-    void operator()(const Vertex&amp; v) const
-    {
-      //...
-    }
-    //...
-  };
-</pre>
-<p>&nbsp;
-<h3>Out-Edges, In-Edges, and Edge Descriptors</h3>

-The out-edges of a vertex are accessed with the <ahref="IncidenceGraph.html#sec:out-edges"><tt>out_edges()</tt></a>-function of the <a href="IncidenceGraph.html">IncidenceGraph</a>interface. The <tt>out_edges()</tt>-function takes two arguments: the first argument is the vertex and thesecond is-the graph object. The function returns a pair of iterators which provideaccess

-to all of the out-edges of a vertex (similar to how the <tt>vertices()</tt>

-function returned a pair of iterators). The iterators are calledout-edge

-iterators</i> and dereferencing one of these iterators gives an <i>edge

-descriptor object. An edge descriptor plays the same kind of role asthe-vertex descriptor object, it is a "black box" provided by thegraph

-type. The following code snippet prints the source-target pairs for each
-out-edge of vertex <tt>v</tt>.
-<p>&nbsp;
-<pre>
-  template &lt;class Graph&gt; struct exercise_vertex {
-    //...
-    void operator()(const Vertex&amp; v) const
-    {
-      typedef graph_traits&lt;Graph&gt; GraphTraits;
-      typename property_map&lt;Graph, vertex_index_t&gt;::type
-        index = get(vertex_index, g);
-
-      std::cout &lt;&lt; &quot;out-edges: &quot;;
-      typename GraphTraits::out_edge_iterator out_i, out_end;
-      typename GraphTraits::edge_descriptor e;
-      for (tie(out_i, out_end) = out_edges(v, g);
-           out_i != out_end; ++out_i) {
-        e = *out_i;
-        Vertex src = source(e, g), targ = target(e, g);

- std::cout << "(" << index[src] <<","

-                  &lt;&lt; index[targ] &lt;&lt; &quot;) &quot;;
-      }
-      std::cout &lt;&lt; std::endl;
-      //...
-    }
-    //...
-  };
-</pre>
-For vertex 0 the output is:
-<pre>
-  out-edges: (0,1) (0,2) (0,3) (0,4)
-</pre>

-The <ahref="BidirectionalGraph.html#sec:in-edges"><tt>in_edges()</tt></a>

-function of the <a href="BidirectionalGraph.html">BidirectionalGraph</a>

-interface provides access to all the in-edges of a vertex throughin-edge-iterators. The <tt>in_edges()</tt> function is only available for the<tt>adjacency_list</tt>

-if <tt>bidirectionalS</tt> is supplied for the <tt>Directed</tt> template
-parameter. There is an extra cost in space when <tt>bidirectionalS</tt> is
-specified instead of <tt>directedS</tt>.
-<p>&nbsp;
-<pre>
-  template &lt;class Graph&gt; struct exercise_vertex {
-    //...
-    void operator()(const Vertex&amp; v) const
-    {
-      //...
-      std::cout &lt;&lt; &quot;in-edges: &quot;;
-      typedef typename graph_traits&lt;Graph&gt; GraphTraits;
-      typename GraphTraits::in_edge_iterator in_i, in_end;
-      for (tie(in_i, in_end) = in_edges(v,g);
-           in_i != in_end; ++in_i) {
-        e = *in_i;
-        Vertex src = source(e, g), targ = target(e, g);

- std::cout << "(" << index[src] <<"," << index[targ] << ") ";

-      }
-      std::cout &lt;&lt; std::endl;
-      //...
-    }
-    //...
-  };
-</pre>
-For vertex 0 the output is:
-<pre>
-  in-edges: (2,0) (3,0) (4,0)
-</pre>
-<p>&nbsp;
-<h3>Adjacent Vertices</h3>

-Given the out-edges of a vertex, the target vertices of these edges areadjacent-to the source vertex. Sometimes an algorithm does not need to look at theedges-of the graph and only cares about the vertices. Therefore the graphinterface-also includes the <ahref="AdjacencyGraph.html#sec:adjacent-vertices"><tt>adjacent_vertices()</tt></a>-function of the <a href="AdjacencyGraph.html">AdjacencyGraph</a> interfacewhich-provides direct access to the adjacent vertices. This function returns apair of-adjacency iterators. Dereferencing an adjacency iterator gives avertex

-descriptor for an adjacent vertex.
-<p>&nbsp;
-<pre>
-  template &lt;class Graph&gt; struct exercise_vertex {
-    //...
-    void operator()(Vertex v) const
-    {
-      //...
-      std::cout &lt;&lt; &quot;adjacent vertices: &quot;;
-      typename graph_traits&lt;Graph&gt;::adjacency_iterator ai;
-      typename graph_traits&lt;Graph&gt;::adjacency_iterator ai_end;
-      for (tie(ai, ai_end) = adjacent_vertices(v, g);
-           ai != ai_end; ++ai)
-        std::cout &lt;&lt; index[*ai] &lt;&lt;  &quot; &quot;;
-      std::cout &lt;&lt; std::endl;
-    }
-    //...
-  };
-</pre>
-For vertex 4 the output is:
-<pre>
-  adjacent vertices: 0 1
-</pre>
-<p>&nbsp;
-<h2>Adding Some Color to your Graph</h2>
-<p>BGL attempts to be as flexible as possible in terms of accommodating how

-properties are attached to a graph. For instance, a property such as edgeweight-may need to be used throughout a graph object's lifespan and therefore itwould-be convenient to have the graph object also manage the property storage.On the-other hand, a property like vertex color may only be needed for theduration of

-a single algorithm, and it would be better to have the property stored

-separately from the graph object. The first kind of property is called aninternally

-stored property</i> while the second kind is called an <i>externally stored

-property. BGL uses a uniform mechanism to access both kinds ofproperties-inside its graph algorithms called the property map interface,described-in Section <a href="property_map.html">Property Map Concepts</a>. Inaddition,-the <a href="PropertyGraph.html">PropertyGraph</a> concept defines theinterface

-for obtaining a property map object for an internally stored property.
-<p>The BGL <tt>adjacency_list</tt> class allows users to specify internally

-stored properties through plug-in template parameters of the graph class.How to-do this is discussed in detail in Section <ahref="using_adjacency_list.html#sec:adjacency-list-properties">Internal-Properties</a>. Externally stored properties can be created in manydifferent-ways, although they are ultimately passed as separate arguments to thegraph-algorithms. One straightforward way to store properties is to create anarray-indexed by vertex or edge index. In the <tt>adjacency_list</tt> with<tt>vecS</tt>

-specified for the <tt>VertexList</tt> template parameter, vertices are

-automatically assigned indices, which can be accessed via the property mapfor

-the <tt>vertex_index_t</tt>. Edges are not automatically assigned indices.

-However the property mechanism can be used to attach indices to the edgeswhich

-can be used to index into other externally stored properties.

-In the following example, we construct a graph and apply <ahref="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths()</tt></a>.-The complete source code for the example is in <ahref="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>.-Dijkstra's algorithm computes the shortest distance from the startingvertex to

-every other vertex in the graph.

-Dijkstra's algorithm requires that a weight property is associated witheach-edge and a distance property with each vertex. Here we use an internalproperty

-for the weight and an external property for the distance. For the weight

-property we use the <tt>property</tt> class and specify <tt>int</tt> asthe type-used to represent weight values and <tt>edge_weight_t</tt> for theproperty tag-(which is one of the BGL predefined property tags). The weight property isthen

-used as a template argument for <tt>adjacency_list</tt>.

-The <tt>listS</tt> and <tt>vecS</tt> types are selectors that determinethe-data structure used inside the <tt>adjacency_list</tt> (see Section <ahref="using_adjacency_list.html#sec:choosing-graph-type">Choosing-the <tt>Edgelist</tt> and <tt>VertexList</tt></a>). The <tt>directedS</tt>type-specifies that the graph should be directed (versus undirected). Thefollowing-code shows the specification of the graph type and then the initializationof-the graph. The edges and weights are passed to the graph constructor inthe form-of iterators (a pointer qualifies as a <ahref="http://www.sgi.com/tech/stl/RandomAccessIterator.html";>RandomAccessIterator</a>).

-<p>&nbsp;
-<pre>
-  typedef adjacency_list&lt;listS, vecS, directedS,

- no_property, property<edge_weight_t, int>> Graph;

-  typedef graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
-  typedef std::pair&lt;int,int&gt; E;
-
-  const int num_nodes = 5;
-  E edges[] = { E(0,2),
-                E(1,1), E(1,3), E(1,4),
-                E(2,1), E(2,3),
-                E(3,4),
-                E(4,0), E(4,1) };
-  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1};
-
-  Graph G(edges + sizeof(edges) / sizeof(E), weights, num_nodes);
-</pre>

-For the external distance property we will use a <tt>std::vector</tt>for-storage. BGL algorithms treat random access iterators as property maps, sowe

-can just pass the beginning iterator of the distance vector to Dijkstra's

-algorithm. Continuing the above example, the following code shows thecreation-of the distance vector, the call to Dijkstra's algorithm (implicitly usingthe

-internal edge weight property), and then the output of the results.
-<p>&nbsp;
-<pre>
-  // vector for storing distance property
-  std::vector&lt;int&gt; d(num_vertices(G));
-
-  // get the first vertex
-  Vertex s = *(vertices(G).first);
-  // invoke variant 2 of Dijkstra's algorithm
-  dijkstra_shortest_paths(G, s, distance_map(&amp;d[0]));
-

- std::cout << "distances from start vertex:" <<std::endl;

-  graph_traits&lt;Graph&gt;::vertex_iterator vi;
-  for(vi = vertices(G).first; vi != vertices(G).second; ++vi)

- std::cout << "distance(" << index(*vi) <<") = "

-              &lt;&lt; d[*vi] &lt;&lt; std::endl;
-  std::cout &lt;&lt; std::endl;
-</pre>
-The output is:
-<pre>
-  distances from start vertex:
-  distance(0) = 0
-  distance(1) = 6
-  distance(2) = 1
-  distance(3) = 4
-  distance(4) = 5
-</pre>
-<p>&nbsp;
-<h2>Extending Algorithms with Visitors</h2>

-Often times an algorithm in a library almost does what you need,but-not quite. For example, in the previous section we used Dijkstra'salgorithm to-calculate the shortest distances to each vertex, but perhaps we alsowanted to

-record the tree of shortest paths. One way to do this is to record the
-predecessor (parent) for each node in the shortest-paths tree.

-It would be nice if we could avoid rewriting Dijkstra's algorithm, andjust-add that little bit extra needed to record the predecessors <ahref="#1">[1]</a>. In the STL, this-kind of extensibility is provided by functors, which are optionalparameters to

-each algorithm. In the BGL this role is fulfilled by <i>visitors</i>.

-A visitor is like a functor, but instead of having just one"apply"

-method, it has several. Each of these methods get invoked at certain

-well-defined points within the algorithm. The visitor methods areexplained in-detail in Section <a href="visitor_concepts.html">Visitor Concepts</a>.The BGL

-provides a number of visitors for some common tasks including a predecessor

-recording visitor. The user is encouraged to write his or her own visitorsas a-way of extending the BGL. Here we will take a quick look at theimplementation-and use of the predecessor recorder. Since we will be using the <ahref="dijkstra_shortest_paths.html">dijkstra_shortest_paths()</a>-algorithm, the visitor we create must be a <ahref="DijkstraVisitor.html">Dijkstra Visitor</a>.-The functionality of the <tt>record_predecessors</tt> visitor isseparated-into two parts. For the storage and access of the predecessor property, wewill

-use a <a href="../../property_map/property_map.html">property map</a>. The

-predecessor visitor will then only be responsible for what parent torecord. To-implement this, we create a <tt>record_predecessors</tt> class andtemplate it-on the predecessor property map <tt>PredecessorMap</tt>. Since thisvisitor will-only be filling in one of the visitor methods, we will inherit from <ahref="dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a>-which will provide empty methods for the rest. The constructor of the<tt>predecessor_recorder</tt>

-will take the property map object and save it away in a data member.
-<p>&nbsp;
-<pre>
-  template &lt;class PredecessorMap&gt;
-  class record_predecessors : public dijkstra_visitor&lt;&gt;
-  {
-  public:
-    record_predecessors(PredecessorMap p)
-      : m_predecessor(p) { }
-
-    template &lt;class Edge, class Graph&gt;
-    void edge_relaxed(Edge e, Graph&amp; g) {
-      // set the parent of the target(e) to source(e)
-      put(m_predecessor, target(e, g), source(e, g));
-    }
-  protected:
-    PredecessorMap m_predecessor;
-  };
-</pre>
-<p>The job of recording the predecessors is quite simple. When Dijkstra's

-algorithm relaxes an edge (potentially adding it to the shortest-pathstree) we-record the source vertex as the predecessor of the target vertex. Later,if the-edge is relaxed again the predecessor property will be overwritten by thenew

-predecessor. Here we use the <tt>put()</tt> function associated with the

-property map to record the predecessor. The <tt>edge_filter</tt> of thevisitor-tells the algorithm when to invoke the <tt>explore()</tt> method. In thiscase-we only want to be notified about edges in the shortest-paths tree so wespecify

-<tt>tree_edge_tag</tt>.

-As a finishing touch, we create a helper function to make it moreconvenient-to create predecessor visitors. All BGL visitors have a helper functionlike

-this.
-<p>&nbsp;
-<pre>
-  template &lt;class PredecessorMap&gt;
-  record_predecessors&lt;PredecessorMap&gt;
-  make_predecessor_recorder(PredecessorMap p) {
-    return record_predecessors&lt;PredecessorMap&gt;(p);
-  }
-</pre>
-<p>We are now ready to use the <tt>record_predecessors</tt> in
-Dijkstra's algorithm. Luckily, BGL's Dijkstra's algorithm is already
-equipped to handle visitors, so we just pass in our new visitor. In
-this example we only need to use one visitor, but the BGL is also
-equipped to handle the use of multiple visitors in the same algorithm
-(see Section <a href="visitor_concepts.html">Visitor Concepts</a>).
-<p>&nbsp;
-<pre>
-  using std::vector;
-  using std::cout;
-  using std::endl;
-  vector&lt;Vertex&gt; p(num_vertices(G)); //the predecessor array
-  dijkstra_shortest_paths(G, s, distance_map(&amp;d[0]).
-                          visitor(make_predecessor_recorder(&amp;p[0])));
-

- cout << "parents in the tree of shortest paths:"<< endl;

-  for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
-    cout &lt;&lt; &quot;parent(&quot; &lt;&lt; *vi;
-    if (p[*vi] == Vertex())
-      cout &lt;&lt; &quot;) = no parent&quot; &lt;&lt; endl;
-    else
-      cout &lt;&lt; &quot;) = &quot; &lt;&lt; p[*vi] &lt;&lt; endl;
-  }
-</pre>
-The output is:
-<pre>
-  parents in the tree of shortest paths:
-  parent(0) = no parent
-  parent(1) = 4
-  parent(2) = 0
-  parent(3) = 2
-  parent(4) = 3
-</pre>

-<br>

-<h3>Notes</h3>

-<a name="1">[1]</a> The new version of Dijkstra's algorithm now includes
-a named parameter for recording predecessors, so a predecessor visitor
-is no long necessary, though this still makes for a good example.

-<br>
-<hr>
-<table>
-  <tr valign="top">
-    <td nowrap>Copyright   2000</td>

- <td><a href="http://www.boost.org/people/jeremy_siek.htm";>JeremySiek</a>,- Indiana University (<ahref="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)</td>

-  </tr>
-</table>

-</body>

-</html>
+
+
+
+
+
+

+在接下去的部分中，我们将会用BGL来构建这个例子，并且用多种方法去操作它。这个例子的全部代码在 <ahref="../example/quick_tour.cpp"><tt>examples/quick_tour.cpp</tt></a>文件中。接下去的每部分将会讨论该例子文件中的程序片段。程序的输出内容我们也会列出来。 

+</p>
+
+
+
+
+
+<h2>构造一个图</h2>
+
+
+
+
+
+

+在该例中我们将使用BGL的 <ahref="adjacency_list.html"><tt>adjacency_list</tt></a>

+类来示范一下BGL接口的主要思想。adjacency_list
+类给传统的"邻接列表"数据结构提供了一个泛型版本。adjacency_list

+是一个带有六个参数的模板类，在该例中我们只使用前三个参数，其余三个参数都用默认值。前两个模板参数（vecS，vecS）分别表示每个顶点出边集合的数据+结构和图中顶点集合的数据结构（关于不同数据结构间的折中方案，请参考：<ahref="using_adjacency_list.html#sec:choosing-graph-type">边列表和顶点列表的选择</a>一节）。第三个参数：bidirectionalS，它表示一个既有出边也有入边的有向图。第三个参数的另一个可选值是：directedS，它表示选择一个仅有出边的有向图；undirectedS 则表示一个无向图。

+</p>
+
+
+
+
+

+一旦我们确定了图的类型，我们就能够创建 <ahref="#fig:quick-start">图2</a> 表示的图了，首先声明一个图对象，然后用<ahref="MutableGraph.html">MutableGraph</a>接口（它是adjacency_list实现的）中的<a href="MutableGraph.html#sec:add-edge"><tt>add_edge()</tt></a>+函数来添加图中的边。在这个例子中，我们使用一对 edge_array 数组仅仅是为了能够简单直接地创建边。 

+</p>
+
+
+
+
+

+<pre> #include <iostream> // for std::cout #include <utility> // for std::pair #include<algorithm> // for std::for_each #include<boost/graph/graph_traits.hpp> #include<boost/graph/adjacency_list.hpp> #include<boost/graph/dijkstra_shortest_paths.hpp> using namespaceboost; int main(int,char*[]) { // typedef图类型 typedef adjacency_list<vecS, vecS, bidirectionalS>Graph; // 便于标记各顶点 enum { A, B, C, D, E, N}; const int num_vertices = N; const char* name= "ABCDE"; // 表示图中的边 typedef std::pair<int,int> Edge; Edge edge_array[] = { Edge(A,B), Edge(A,D),Edge(C,A), Edge(D,C), Edge(C,E), Edge(B,D), Edge(D,E) }; const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]); // 声明一个图对象 Graph g(num_vertices); // 给图对象增加边 for (int i = 0; i < num_edges; ++i) add_edge(edge_array[i].first, edge_array[i].second, g); ... return 0; } </pre>

+
+
+
+
+
+

+我们可以使用 <ahref="adjacency_list.html#sec:iterator-constructor">edge iterator+constructor 边迭代器构造函数</a> 来替代 add_edge() 函数，该函数比add_edge()函数更有效率。指向 edge_array 的指针可以被看作是迭代器，所以我们可以用该数组中的头元素和尾元素来创建一个迭代器。

+</p>
+
+
+
+
+

+<pre> Graph g(edge_array, edge_array + sizeof(edge_array) /sizeof(Edge), num_vertices); </pre>

+
+
+
+
+
+

+除了在创建图的时候就指定固定顶点个数的方法以外，也可以用以 add_vertex()函数和 remove_vertex() 函数来增加、删除顶点的方法来代替，这两个函数都是 <a href="MutableGraph.html">MutableGraph</a> 接口中的。

+</p>
+
+
+
+
+
+<h2>存取顶点集</h2>
+
+
+
+
+
+

+现在我们已经建立了一个图，我们可是通过相关的图接口使用各种方法来访问图中的数据。首先，我们可以使用 <ahref="VertexListGraph.html">VertexListGraph</a>接口中的<ahref="VertexListGraph.html#sec:vertices"><tt>vertices()</tt></a>函

+数来访问图中各顶点。该函数返回一个顶点迭代器对(std::pair of vertex

+iterators)(第一个iterator指向顶点的开始元素，第二个迭代器指向最后元素的下一位置)，通过一个顶点迭代器来间接引用一个顶点对象。+顶点迭代器的类型在graph_traits类中给出。注意：不同的图类跟不同的顶点迭代器相关联，这就是需要graph_traits类的原因。给定正+确的图类型，<a href="graph_traits.html"><tt>graph_traits</tt></a>类就能给出正确的vertex_iterator类型。

+
+
+
+
+
+
+

+下面的例子打印出图中每个顶点的序号。所有顶点和边的属性，包括序号在内，全都通过属性映射（<a href="property_map.html"><tt>property_map</tt></a>）对象来访问。property_map类被用于得到具体的属性（比如：vertex_index_t，它是BGL预定义的一个属性）或者通过调用具体函数得到实际的属性映射对象。 

+</p>
+
+
+
+
+

+<pre> // ... int main(int,char*[]) { // ... // 得到顶点索引的属性映射 typedef property_map<Graph,vertex_index_t>::type IndexMap; IndexMap index =get(vertex_index, g); std::cout << "vertices(g)= "; typedef graph_traits<Graph>::vertex_iteratorvertex_iter; std::pair<vertex_iter, vertex_iter> vp; for (vp = vertices(g); vp.first != vp.second; ++vp.first) std::cout << index[*vp.first] << " "; std::cout<< std::endl; // ... return 0; } </pre>

+
+
+
+
+
+
+输出是：
+<pre>  vertices(g) = 0 1 2 3 4<br></pre>
+
+
+
+
+
+
+<p>&nbsp;
+</p>
+
+
+
+
+
+<h2>访问边集合<br>
+
+</h2>
+
+
+
+
+
+
+
+
+
+
+
+

+图中的边集合能够通过EdgeListGraph接口的<ahref="EdgeListGraph.html#sec:edges"><tt>edges()</tt></a>函数访问。与vertices()函数类似，该函数也返回一个迭代器对，不过这次返回的是边迭代器(edgeiterators)，通过边迭代器对象能够访问到边对象。source()函数和target()函数返回链接一条边的首、尾顶点。这次我们用<ahref="../../tuple/doc/tuple_users_guide.html#tiers"><tt>tie()</tt></a>辅助函数来替换std::pair迭代器对，这个函数把std::pair中的两部分拆分到了两个变量当中去，本例中是ei和ei_end。这种方法比创建std::pair更简单，所以在BGL中我们经常使用这种方法。 

+</p>
+
+
+
+
+

+<pre> // ... int main(int,char*[]) { // ... std::cout << "edges(g) = "; graph_traits<Graph>::edge_iterator ei, ei_end; for (tie(ei,ei_end) = edges(g); ei != ei_end; ++ei) std::cout << "("<< index[source(*ei, g)] << "," <<index[target(*ei, g)] << ") "; std::cout <<std::endl; // ... return 0; } </pre>

+
+
+
+
+
+
+输出是：

+<pre> edges(g) = (0,1) (0,2) (0,3) (0,4) (2,0) (2,4) (3,0) (3,1)(3,4) (4,0) (4,1) </pre>

+
+
+
+
+
+
+<p>&nbsp;
+</p>
+
+
+
+
+
+<h2>邻接结构<br>
+
+</h2>
+

+在接下去的几个例子中，我们将从特定顶点的视角来探究图的邻接结构。我们将着眼于研究顶点的入边、出边和他的邻接顶点。我们将封装一个"exercise+vertex"函数以得到上面这些数据结构，该函数接受图中顶点作为参数。为了示范BGL和STL的互操作性，我们使用STL中的

+for_each() 函数对顶点进行迭代并调用"exercise vertex"函数。&nbsp;
+
+
+
+
+
+

+<pre> //... int main(int,char*[]) { //... std::for_each(vertices(g).first, vertices(g).second, exercise_vertex<Graph>(g)); return 0; } </pre>

+我们使用仿函数－－exercise_vertex来替代一般的函数，因+为我们存取顶点信息的时候需要图对象，使用仿函数能够让我们在执行std::for_each()期间一直保持一个对图对象的引用。并且，我们将这个仿函数按图类型进行模板化，这+样就能够对不同的图类复用代码。下面是exercise_vertex仿函数的开始部分： 

+
+
+
+

+<pre> template <class Graph> struct exercise_vertex { exercise_vertex(Graph& g_) : g(g_) {} //... Graph&g; }; </pre>

+
+
+
+
+
+
+<p>&nbsp;
+</p>
+
+
+
+
+
+<h3>顶点描述符<br>
+
+</h3>
+
+<span style="font-family: monospace;">为了写仿函数的"operator()"函数，

+我们首先需要知道图中顶点的类型。顶点类型将作为"operator()"的参数。为了准确性，我们不去处理实际的顶点对象，而是

+处理顶点描述符(vertex

+descriptors)。一些图的表示法（比如：邻接列表）并不保存实际的图对象，而有些则会保存（比如：链接指针图）。这些区别被隐藏在顶点描述符对+象的"黑盒"之下。顶点描述符是由各个图类型提供的，它被用于通过一些函数来访问相关图的信息，比如通过图的out_edges()函数、

+in_edges()函数、

+adjacent_vertices()函数以及属性映射函数，后面的章节会有详细描述。顶点描述符类型是通过graph_traits类来得到的。关键

+字－－"

+typename"是必须的，因为域操作符左边的类型是依赖于模板参数（图类型）的。下面定义我们的仿函数的应用方法： 

+
+
+
+
+
+

+<pre> template <class Graph> struct exercise_vertex { //... typedef typenamegraph_traits<Graph> ::vertex_descriptor Vertex; void operator()(const Vertex& v) const { //... } //... }; </pre>

+
+
+
+
+
+
+<p>&nbsp;
+</p>
+
+
+
+
+
+<h3>出边、入边和边描述符<br>
+</h3>
+
+
+
+
+
+
+
+
+
+
+
+

+通过<a href="IncidenceGraph.html">IncidenceGraph</a>接口的out_edges()函数能够访问一个顶点的出边。<ahref="IncidenceGraph.html#sec:out-edges"><tt>out_edges()</tt></a>函+数有2个参数：第一个参数是该出边所对应的顶点，第二个参数是边所在的图对象。这个函数提供一个迭代器对，这个迭代器对可用于访问该顶点的所有出边(与

+vertices()函数返回一个迭代器对相类似)。这个迭代器叫做"出边迭代器"(out-edge
+iterators)，解引用一个迭代器可以得到对应的边描述符(edge

+descriptor)对象。一个边描述符起到的作用和顶点描述符相类似，它是一个由图提供的"黑盒"。以下代码片断对 vertex <tt>v</tt> 的每条出边打印"源-目标"对。

+&nbsp;
+</p>
+
+
+
+
+

+<pre> template <class Graph> struct exercise_vertex { //... void operator()(const Vertex& v) const { typedef graph_traits<Graph> GraphTraits; typenameproperty_map<Graph, vertex_index_t>::type index =get(vertex_index, g); std::cout<< "out-edges: "; typename GraphTraits::out_edge_iteratorout_i, out_end; typename GraphTraits::edge_descriptor e; for (tie(out_i, out_end) = out_edges(v, g); out_i !=out_end; ++out_i) { e = *out_i; Vertex src =source(e, g), targ = target(e, g); std::cout << "("<< index[src] << "," << index[targ]<< ") "; } std::cout << std::endl; //... } //... }; </pre>对于顶点0，输出为:

+<pre>  out-edges: (0,1) (0,2) (0,3) (0,4)<br></pre>
+
+
+
+
+
+
+

+<a href="BidirectionalGraph.html">BidirectionalGraph</a>接口的<ahref="BidirectionalGraph.html#sec:in-edges"><tt>in_edges()</tt></a>函数通过入边迭代器访问一个顶点所有的入边。in_edges()函数仅当bidirectionalS作为adjacency_list的<tt>Directed</tt>模板参数的时候才有效。相对于单向图，双向图占用更多的空间。 

+</p>
+
+
+
+
+

+<pre> template <class Graph> struct exercise_vertex { //... void operator()(const Vertex& v) const { //... std::cout << "in-edges: "; typedef typenamegraph_traits<Graph> GraphTraits; typenameGraphTraits::in_edge_iterator in_i, in_end; for (tie(in_i, in_end)= in_edges(v,g); in_i != in_end; ++in_i) { e =*in_i; Vertex src = source(e, g), targ = target(e,g); std::cout << "(" << index[src] << ","<< index[targ] << ") "; } std::cout <<std::endl; //... } //... }; </pre>

+
+
+
+
+
+
+顶点0的输出:
+<pre>  in-edges: (2,0) (3,0) (4,0)<br></pre>
+
+
+
+
+
+
+<p>&nbsp;
+</p>
+
+
+
+
+
+<h3>相邻顶点</h3>
+
+
+
+
+
+

+给定一个顶点的出边，该边的目标顶点就是源顶点的相邻顶点。有时候，一个算法不关心图中的边而是仅需关心图中顶点。因此，图接口中提供了<ahref="AdjacencyGraph.html">AdjacencyGraph</a>接口，该接口中的 <ahref="AdjacencyGraph.html#sec:adjacent-vertices"><tt>adjacent_vertices()</tt></a>函数能够直接访问顶点的相邻顶点。这个函数返回一个邻接迭代器对，通过间接引用邻接迭代器能够得到邻接顶点的顶点描述符。 

+</p>
+
+
+
+
+

+<pre> template <class Graph> struct exercise_vertex { //... void operator()(Vertex v) const { //... std::cout << "adjacent vertices: "; typenamegraph_traits<Graph>::adjacency_iterator ai; typenamegraph_traits<Graph>::adjacency_iterator ai_end; for (tie(ai,ai_end) = adjacent_vertices(v, g); ai != ai_end;++ai) std::cout << index[*ai] << " "; std::cout << std::endl; } //... }; </pre>

+顶点4的输出是:
+<pre>  adjacent vertices: 0 1<br></pre>
+
+
+
+
+
+
+<p>&nbsp;
+</p>
+
+
+
+
+
+<h2>给你的图增添一些色彩<br>
+</h2>
+
+
+
+
+
+

+BBGL试图尽可能灵活地提供图的相关附属属性。一个属性，比如边的权重，可能需要贯穿图对象的整个生命周期，因此图对象就需要管理该属性的存储。+另一方面，顶点颜色属性有可能仅在一个单独的算法中被用到，那么最好是把该属性和图对象分开存储。前一种属性被称作内部存储属性，而第二种属性被称作外部+存储属性。BGL提供统一的机制来访问这两种属性，该机制叫作：属性映射(propertymap)，内部的算法实现是property+map接口，该接口在<a href="property_map.html">Property Map Concepts属性映射概念</a>一章中介绍。此外，<a href="PropertyGraph.html">PropertyGraph</a>概念定义了一个接口，该接口用于对一个内部存储属性获得属性映射对象。+BGL的adjacency_list类允许用户通过图类的模板参数指定内部存储属性。具体的实现在<ahref="using_adjacency_list.html#sec:adjacency-list-properties">Internal

+Properties内部属性</a>一

+节中讲解。有多种方法能够创建外部存储属性，但是这些方法最终都是传递给图算法一个模板参数而已。一个直观的存储属性的办法是，根据点或边的索引创建一个索+引数组。在<tt>VertexList</tt>模板参数指定为vecS的adjacency_list类中，顶点被自动赋予索引值，顶点索引能够通过属性映射得到vertex_index_t+值。边不会自动赋予索引值。然而属性机制可以被用来把索引绑定到需要把索引作为外部存储属性的边上。+在以下例子中，我们使用<ahref="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths()</tt></a>函数建立一个图。这个例子的完整的源代码在<ahref="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>文件中。Dijkstra算法计算从一点到图中每个其它顶点的最短路径。+Dijkstra算法需要给边添加一个权重属性，并且给顶点添加一个距离属性。这里，我们把权重作为内部属性，把距离作为外部属性。我们使用属性类来表示+权重属性，并且规定权重的类型为整型(int)，使用edge_weight_t作为属性标记(它是BGL预定义的一个属性标记)。然后，权重属性作为

+adjacency_list的模版参数使用。<br>
+
+
+
+
+
+

+TlistS和vecS是adjacency_list内部数据结构的类型(参考：<ahref="using_adjacency_list.html#sec:choosing-graph-type">Choosing+the <tt>Edgelist</tt> and <tt>VertexList 选择边列表和顶点列表</tt></a>)。directedS类型规定了该图必须是一个有向图(与无向图相对)。下面的代码详细说明了图类型以及它的初始化部分。边和权重以迭代器(一个被当作<ahref="http://www.sgi.com/tech/stl/RandomAccessIterator.html";>RandomAccessIterator</a>的指针)的形式传入图的构造函数。 

+</p>
+
+
+
+
+

+<pre> typedef adjacency_list<listS, vecS, directedS, no_property, property<edge_weight_t,int> > Graph; typedefgraph_traits<Graph>::vertex_descriptor Vertex; typedefstd::pair<int,int> E; const int num_nodes = 5; Eedges[] = { E(0,2), E(1,1), E(1,3),E(1,4), E(2,1), E(2,3), E(3,4), E(4,0), E(4,1) }; int weights[] = { 1, 2,1, 2, 7, 3, 1, 1, 1}; Graph G(edges + sizeof(edges) / sizeof(E),weights, num_nodes); </pre>+我们使用std::vector来存储距离这个外部属性。BGL处理随机迭代器像处理属性映射一样，所以我们仅需传递distance+vector的开始迭代器到Dijkstra算法既可。继续我们上面的例子，下面的代码展示的是创建一个distance+vector，以及调用Dijkstra算法(隐式地使用了内部属性－－权重)，然后输出结果。 +<pre> // vector为了给distance属性排序 std::vector<int>d(num_vertices(G)); // 得到第一个顶点 Vertex s =*(vertices(G).first); // 调用Dijkstra算法 dijkstra_shortest_paths(G, s, distance_map(&d[0])); std::cout<< "distances from start vertex:" << std::endl; graph_traits<Graph>::vertex_iterator vi; for(vi =vertices(G).first; vi != vertices(G).second; ++vi) std::cout<< "distance(" << index(*vi) << ") = " << d[*vi] << std::endl; std::cout <<std::endl; </pre>

+输出是:

+<pre> distances from start vertex: distance(0) = 0 distance(1)= 6 distance(2) = 1 distance(3) = 4 distance(4) = 5 </pre>

+
+
+
+
+
+
+<p>&nbsp;
+</p>
+
+
+
+
+
+<h2>用遍历器扩展图算法<br>
+</h2>

+多数情况下，一个库提供的算法能够满足你的大多数应用，但不是全部。例如，上一节我们使用Dijkstra算法计算到每个顶点的最短路径，但是我们也许想记下最短路径的树。一种方法是记录下最短路径数中每一个节点的前驱(父节点)。+最好是不要重写Dijkstra算法，仅仅增加记录前驱节点的代码即可<ahref="quick_tour.html#1">[1]</a>。在STL中，这种扩展能力通过仿函数来提供，它是一个每个算法的可选参数。在BGL中扮演相同角色的是遍历器(Visitor)。

+</p>
+
+
+
+
+

+遍历器类似于仿函数，但是不同于仿函数只有一个"应用"方法，遍历器有多个"应用"方法。它的每个方法都会在算法内部预先定义好的点被调用。遍历器中的方法在<ahref="visitor_concepts.html">Visitor Concepts遍历器概念</a>一+节中详细讲解。BGL为一般任务提供了一系列遍历器，其中包括记录前驱节点的遍历器。希望用户能够使用遍历器来扩展BGL。在这+里，我们将会快速的看一遍历器r的实现方法，以及记录前驱节点的遍历器的使用。因为我们使用 <ahref="dijkstra_shortest_paths.html">dijkstra_shortest_paths()</a>算法，所以我们必须创建一个<a href="DijkstraVisitor.html">Dijkstra遍历器</a>。+record_predecessors 遍历器的功能被分为两个部分。我们使用<ahref="../../property_map/property_map.html">property map</a>来存储和访问前驱节点属性。然后，predecessor 遍历器仅负责记录前驱节点。为了实现这些，我们创建模板类record_predecessors。以后就可以调用该遍历器的方法了，因为我们继承自<a href="dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a>类，所以这个类没有提供其它方法。predecessor_recorder的构造函数将接受一个属性映射对象并且把它保存到数据成员。 

+</p>
+
+
+
+
+

+<pre> template <class PredecessorMap> classrecord_predecessors : public dijkstra_visitor<> { public: record_predecessors(PredecessorMap p) :m_predecessor(p) { } template <class Edge, classGraph> void edge_relaxed(Edge e, Graph& g) { // 把源顶点设置成目标顶点的父节点 put(m_predecessor, target(e, g),source(e, g)); } protected: PredecessorMapm_predecessor; }; </pre>+记录前驱节点非常简单。当Dijkstra算法走到一条边(意味着把它放入最短路径树中)的时候，我们把源点作为目标顶点的前驱节点记录下来。然后如果这+条边再被访问，那么前驱属性将会被新的前驱节点改写。我们使用put()函数把属性影射关联到记录的前驱节点。visitor的edge_filter告+诉算法何时调用explore()方法。我们仅仅想通知在最短路径树中的边，所以规定使用tree_edge_tag标记。 

+<br>

+作为最后一点，我们创建一个辅助函数来使创建predecessor visitors更简单一些。所有的BGL visitor都有一个与之类似的辅助函数。

+
+
+
+
+
+

+<pre> template <class PredecessorMap> record_predecessors<PredecessorMap> make_predecessor_recorder(PredecessorMap p) { returnrecord_predecessors<PredecessorMap>(p); } </pre>

+
+
+
+
+
+

+我们准备在Dijkstra算法中使用record_predecessors了。幸运的是，BGL中的Dijkstra算法已经配备了一个+visitor句柄，所以我们只需要传入新的visitor即可。在这个例子中我们只需要使用一个visitor，但是BGL中一个算法经常配备多个+visitor句柄(参考<a href="visitor_concepts.html">Visitor Concepts</a>一节)。 

+</p>
+
+
+
+
+

+<pre> using std::vector; using std::cout; using std::endl; vector<Vertex> p(num_vertices(G)); //the predecessor array dijkstra_shortest_paths(G, s, distance_map(&d[0]). visitor(make_predecessor_recorder(&p[0]))); cout<< "parents in the tree of shortest paths:" << endl; for(vi = vertices(G).first; vi != vertices(G).second; ++vi) { cout<< "parent(" << *vi; if (p[*vi] == Vertex()) cout << ") = no parent" << endl; else cout<< ") = " << p[*vi] << endl; } </pre>输出为：+<pre> parents in the tree of shortest paths: parent(0) = noparent parent(1) = 4 parent(2) = 0 parent(3) = 2 parent(4) = 3 </pre>

+
+
+
+
+
+
+
+<br>
+
+
+
+
+
+
+
+<h3>注意：</h3>
+
+
+
+
+
+
+

+<a name="1">[1]</a> 虽然predecessor visitor提供了一个好例子，但是predeceddor遍历器已经不需要了，因为新版的Dijkstra算法为记录前驱节点包含了一个命名参数。 

+
+
+
+
+
+
+<hr>
+<table>
+
+
+
+
+
+
+  <tbody>
+
+
+
+
+
+    <tr valign="top">
+
+
+
+
+
+
+    <td nowrap="nowrap">Copyright (c) 2000</td>
+
+
+
+
+
+
+    <td><a href="../../../people/jeremy_siek.htm">Jeremy Siek</a>,

+ Indiana University (<ahref="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)</td>

+
+
+
+
+
+
+  </tr>
+
+
+
+
+
+
+
+
+
+
+
+  </tbody>
+</table>
+
+
+
+
+
+
+

<!-- LocalWords: STL BGL cpp vecS bidirectionalS directedS undirectedShpp vp

-->

<!-- LocalWords: iostream namespace int const num sizeof map ID's giftypedef

@@ -622,3 +754,4 @@
  -->
 <!--  LocalWords:  DijkstraVisitor PredecessorMap siek htm Univ Notre
  -->
+</body></html>
\ No newline at end of file

Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html (original)
+++ trunk/libs/graph/doc/table_of_contents.html Fri Jun 26 00:01:13 2009
@@ -1,304 +1,401 @@
-<HTML>
-<!--
-     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>Table of Contents: 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>Table of Contents: the Boost Graph Library
-<a href="http://www.awprofessional.com/title/0201729148";>
-<img src="bgl-cover.jpg" ALT="BGL Book" ALIGN="RIGHT"></a>
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>

+<meta content="text/html;charset=UTF-8" http-equiv="Content-Type">

+<title>Table of Contents: Boost Graph Library</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"> <brclear="">+<h1>目录:Boost图库<ahref="http://www.awprofessional.com/title/0201729148";><imgsrc="bgl-cover.jpg" alt="BGL Book" align="right"></a>

 </h1>
-
-      <OL>
-        <LI><A Href="./index.html">Introduction to the BGL</A>
-        <LI><A Href="./history.html">History</A>
-        <LI><A Href="./users.html">List of BGL Users</A>
-        <LI><A Href="./publications.html">Publications</A>
-        <LI><A Href="./acknowledgements.html">Acknowledgements</A>

- <LI><A href="./quick_tour.html">A Quick Tour of the Boost GraphLibrary.</a>- <LI><A Href="graph_theory_review.html">Review of Elementary GraphTheory</A>

-        <LI>Boost Graph Library Tutorial
-           <OL>
-            <LI><a
-            href="./using_property_maps.html">Property Maps</a>
-            <LI><a

- href="./using_adjacency_list.html">The <tt>adjacency_list</tt>class</a>

-           </OL>
-        <LI>Examples
-           <OL>
-            <LI><a href="./file_dependency_example.html">File
-            Dependency Example</a>
-            <LI><a href="./kevin_bacon.html">Six Degrees of Kevin Bacon</a>
-            <LI><a href="./graph_coloring.html">Graph Coloring</a>
-            <LI><a href="./sparse_matrix_ordering.html">Sparse Matrix
-            Ordering</a>
-           </OL>
-        <LI>Extending the Boost Graph Library
-         <OL>

- <LI><a href="./constructing_algorithms.html">Constructing graphalgorithms with BGL</a>- <LI><a href="./leda_conversion.html">Converting Existing Graphsto BGL</a>

-         </OL>
-        <LI><A href="./graph_concepts.html">The Boost Graph Interface</A>
-         <OL>
-           <LI><A href="./Graph.html">Graph</A>
-           <LI><A href="./IncidenceGraph.html">Incidence Graph</A>
-           <LI><A href="./BidirectionalGraph.html">Bidirectional Graph</A>
-           <LI><A href="./AdjacencyGraph.html">Adjacency Graph</A>
-           <LI><A href="./VertexListGraph.html">Vertex List Graph</A>
-           <LI><A href="./EdgeListGraph.html">Edge List Graph</A>

- <LI><A href="./VertexAndEdgeListGraph.html">Vertex and EdgeList Graph</A>

-           <LI><A href="./MutableGraph.html">Mutable Graph</A>
-           <LI><A href="./PropertyGraph.html">Property Graph</A>

- <LI><A href="./MutablePropertyGraph.html">Mutable PropertyGraph</A>

-         </OL>

- <li><a href="../../property_map/property_map.html">The PropertyMap Library</a> (technically not part of the graph library, but used a lothere)- <li><img src="figs/python_ico.gif" alt="(Python)"/><ahref="python.html">Python bindings</a></li>

-        <li><a href="./visitor_concepts.html">Visitor Concepts</a>
-          <OL>
-            <LI><a href="./BFSVisitor.html">BFS Visitor</a>
-            <LI><a href="./DFSVisitor.html">DFS Visitor</a>

- <LI><a href="./DFSVisitor.html"><ahref="./DijkstraVisitor.html">Dijkstra Visitor</a>- <LI><a href="./BellmanFordVisitor.html">Bellman FordVisitor</a>

-            <LI><a href="AStarVisitor.html">A* Visitor</a></LI>
-            <LI><a href="./EventVisitor.html">Event Visitor</a>
-            <LI><a href="./PlanarFaceVisitor.html">Planar Face Visitor</a>
-            <li><a href="TSPTourVisitor.html">TSP Tour Visitor</a></li>
-          </OL>
-        <li>EventVisitorList Adaptors
-          <OL>
-            <LI><a href="EventVisitorList.html">Event Visitor List</a>
-            <LI><a href="bfs_visitor.html"><tt>bfs_visitor</tt></a>
-            <LI><a href="dfs_visitor.html"><tt>dfs_visitor</tt></a>

- <LI><ahref="dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a>

-            <LI><a href="bellman_visitor.html"><tt>bellman_visitor</tt></a>

- <li><ahref="astar_visitor.html"><tt>astar_visitor</tt></a></li>

-          </OL>
-        <li>Event Visitors
-          <OL>

- <LI><ahref="predecessor_recorder.html"><tt>predecessor_recorder</tt></a>- <LI><ahref="distance_recorder.html"><tt>distance_recorder</tt></a>

-            <LI><a href="time_stamper.html"><tt>time_stamper</tt></a>
-            <LI><a href="property_writer.html"><tt>property_writer</tt></a>

- <li><ahref="tsp_tour_visitor.html"><tt>tsp_tour_visitor</tt></a></li>- <li><ahref="tsp_tour_len_visitor.html"><tt>tsp_tour_len_visitor</tt></a></li>

-          </OL>
-        <LI>Graph classes
-          <OL>

- <LI><Ahref="./adjacency_list.html"><tt>adjacency_list</tt></a></li>- <LI><Ahref="./adjacency_matrix.html"><tt>adjacency_matrix</tt></a></li>- <li><ahref="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a></li>

-          </OL></li>
-        <LI>Graph Adaptors
-          <OL>
-            <LI><A href="./subgraph.html"><tt>subgraph</tt></A>
-            <LI><A href="./edge_list.html"><tt>edge_list</tt></A>
-            <LI><A href="./reverse_graph.html"><tt>reverse_graph</tt></A>
-            <LI><A href="./filtered_graph.html"><tt>filtered_graph</tt></A>

- <LI><A href="../../../boost/graph/vector_as_graph.hpp">Vectoras Graph </A><a href="#*">*</a>- <LI><A href="../../../boost/graph/matrix_as_graph.hpp">Matrixas Graph</A><a href="#*">*</a>- <LI><A href="../../../boost/graph/leda_graph.hpp">Leda Graph</A><a href="#*">*</a>

-            <LI><A href="./stanford_graph.html">Stanford GraphBase</A>
-           </OL>
-        <LI>Iterator Adaptors
-          <OL>
-            <LI><a

-href="./adjacency_iterator.html"><tt>adjacency_iterator</tt></a>

-            <LI><a

-href="./inv_adjacency_iterator.html"><tt>inv_adjacency_iterator</tt></a>

-          </OL>
-        <LI>Traits classes
-          <OL>
-            <LI><a href="./graph_traits.html"><tt>graph_traits</tt></a>

- <LI><ahref="./adjacency_list_traits.html"><tt>adjacency_list_traits</tt></a>

-            <LI><a href="./property_map.html"><tt>property_map</tt></a>
-          </OL>
-        <LI>Algorithms
-          <OL>

- <LI><ahref="./bgl_named_params.html"><tt>bgl_named_params</tt></a>

-            <LI>Core Algorithm Patterns
-              <OL>

- <LI><Ahref="./breadth_first_search.html"><tt>breadth_first_search</tt></A>- <LI><A href="./breadth_first_search.html"><Ahref="./breadth_first_visit.html"><tt>breadth_first_visit</tt></A>

-                <LI><A

-href="./depth_first_search.html"><tt>depth_first_search</tt></A>- <LI><Ahref="./depth_first_visit.html"><tt>depth_first_visit</tt></A>

-                <LI><A
-                href="./undirected_dfs.html"><tt>undirected_dfs</tt></A>
-              </OL>
-            <LI>Graph Algorithms
-              <OL>
-                <LI>Shortest Paths Algorithms
-                  <OL>

- <LI><Ahref="./dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths</tt></A>- <LI><Ahref="./bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths</tt></A>- <LI><Ahref="./dag_shortest_paths.html"><tt>dag_shortest_paths</tt></A>

-                    <LI><A

-href="./johnson_all_pairs_shortest.html"><tt>johnson_all_pairs_shortest_paths</tt></A>- <li><ahref="floyd_warshall_shortest.html"><tt>floyd_warshall_all_pairs_shortest_paths</tt></a></li>- <li><ahref="r_c_shortest_paths.html"><tt>r_c_shortest_paths</tt> -resource-constrained shortest paths</a></li>

-                  </OL>
-                <LI>Minimum Spanning Tree Algorithms
-                  <OL>
-                    <LI><A

-href="./kruskal_min_spanning_tree.html"><tt>kruskal_minimum_spanning_tree</tt></A>

-                    <LI><A

-href="./prim_minimum_spanning_tree.html"><tt>prim_minimum_spanning_tree</tt></A>

-                  </OL>
-        <LI>Connected Components Algorithms
-        <OL>

- <LI><Ahref="./connected_components.html"><tt>connected_components</tt></A>- <LI><Ahref="./strong_components.html"><tt>strong_components</tt></A>

- <LI><ahref="biconnected_components.html"><tt>biconnected_components</tt></a>- <LI><ahref="biconnected_components.html#sec:articulation_points"><tt>articulation_points</tt></a>- <LI><a href="./incremental_components.html">IncrementalConnected Components</a>

-            <OL>

- <LI><Ahref="./incremental_components.html#sec:initialize-incremental-components"><tt>initialize_incremental_components</tt></A>- <LI><Ahref="./incremental_components.html#sec:incremental-components"><tt>incremental_components</tt></A>

-            <LI><A

-href="./incremental_components.html#sec:same-component"><tt>same_component</tt></A>- <LI><Ahref="./incremental_components.html#sec:component-index"><tt>component_index</tt></A>

-            </OL>
-        </OL></LI>
-                <LI>Maximum Flow and Matching Algorithms
-                  <OL>

- <LI><Ahref="edmonds_karp_max_flow.html"><tt>edmonds_karp_max_flow</tt></A>- <LI><Ahref="push_relabel_max_flow.html"><tt>push_relabel_max_flow</tt></A>- <li><ahref="kolmogorov_max_flow.html"><tt>kolmogorov_max_flow</tt></a></li>- <LI><Ahref="maximum_matching.html"><tt>edmonds_maximum_cardinality_matching</tt></A>

-                  </OL>
-
-                <li>Sparse Matrix Ordering Algorithms
-                  <ol>
-                    <LI><A

-href="./cuthill_mckee_ordering.html"><tt>cuthill_mckee_ordering</tt></a>- <li><ahref="king_ordering.html"><tt>king_ordering</tt></a></li>- <LI><ahref="./minimum_degree_ordering.html"><tt>minimum_degree_ordering</tt></a>

-                  </ol>
-                </li>

- <LI><Ahref="topological_sort.html"><tt>topological_sort</tt></A>- <li><ahref="transitive_closure.html"><tt>transitive_closure</tt></a>

-                <LI><A href="copy_graph.html"><tt>copy_graph</tt></A>

- <LI><Ahref="transpose_graph.html"><tt>transpose_graph</tt></A>

-                <LI><A href="isomorphism.html"><tt>isomorphism</tt></A>
-
-                <li>Path and Tour Algorithms
-                    <ol>

- <li><ahref="metric_tsp_approx.html"><tt>metric_tsp_approx</tt></a></li>

-                    </ol>
-                </li>
-

- <LI><Ahref="sequential_vertex_coloring.html"><tt>sequential_vertex_coloring</tt></A>- <li><ahref="sloan_ordering.htm"><tt>sloan_ordering</tt></a></li>- <li><ahref="sloan_start_end_vertices.htm"><tt>sloan_start_end_vertices</tt></a></li>

- <LI><A href="./wavefront.htm"><tt>ith_wavefront</tt>,<tt>max_wavefront</tt>, <tt>aver_wavefront</tt>, and<tt>rms_wavefront</tt></A></LI>- <LI><Ahref="betweenness_centrality.html"><tt>brandes_betweenness_centrality</tt></A></LI>

-                <li>Layout algorithms
-                  <ol>

- <li><ahref="random_layout.html"><tt>random_graph_layout</tt></a></li>- <li><ahref="circle_layout.html"><tt>circle_layout</tt></a></li>- <li><ahref="kamada_kawai_spring_layout.html"><tt>kamada_kawai_spring_layout</tt></a></li>- <li><ahref="fruchterman_reingold.html"><tt>fruchterman_reingold_force_directed_layout</tt></a></li>- <li><ahref="gursoy_atun_layout.html"><tt>gursoy_atun_layout</tt></a></li>

-                    </ol>
-                    </li>
-                <li>Clustering algorithms
-                    <ol>

- <li><ahref="bc_clustering.html"><tt>betweenness_centrality_clustering</tt></a></li>

-                    </ol>
-                </li>
-        <li><a href="astar_search.html"><tt>astar_search</tt></a></li>

- <li><ahref="lengauer_tarjan_dominator.htm"><tt>lengauer_tarjan_dominator_tree</tt></a></li>- <li><ahref="howard_cycle_ratio.html"><tt>minimum_cycle_ratio</tt> and<tt>maximum_cycle_ratio</tt></a></li>

-               <li><a href="planar_graphs.html">Planar Graph Algorithms</a>
-               <ol>
-               <li><a href="boyer_myrvold.html">
-               <tt>boyer_myrvold_planarity_test</tt></a>
-               <li><a href="planar_face_traversal.html">
-               <tt>planar_face_traversal</tt></a>
-               <li><a href="planar_canonical_ordering.html">
-               <tt>planar_canonical_ordering</tt></a>
-               <li><a href="straight_line_drawing.html">
-               <tt>chrobak_payne_straight_line_drawing</tt></a>
-               <li><a href="is_straight_line_drawing.html">
-               <tt>is_straight_line_drawing</tt></a>
-               <li><a href="is_kuratowski_subgraph.html">
-               <tt>is_kuratowski_subgraph</tt></a>
-               <li><a href="make_connected.html">
-               <tt>make_connected</tt></a>
-               <li><a href="make_biconnected_planar.html">
-               <tt>make_biconnected_planar</tt></a>
-               <li><a href="make_maximal_planar.html">
-               <tt>make_maximal_planar</tt></a>
-               </ol>

- <li><ahref="lengauer_tarjan_dominator.htm"><tt>lengauer_tarjan_dominator_tree</tt></a></li>

-            </OL>
-         </OL>
-
-         <li>Graph Input/Output
-           <ol>

- <li>AT&T Graphviz: <ahref="read_graphviz.html">read_graphviz</a>, <ahref="./write-graphviz.html">write_graphviz</a></li>- <li>DIMACS Max-flow: <ahref="read_dimacs.html">read_dimacs_max_flow</a>, <ahref="write_dimacs.html">write_dimacs_max_flow</a></li>- <li>GraphML: <a href="read_graphml.html">read_graphml</a> and<a href="write_graphml.html">write_graphml</a></li>

-           </ol></li>
-
-      <LI>Auxiliary Concepts, Classes, and Functions
-        <OL>
-          <LI><a href="./property.html"><tt>property</tt></a>
-          <LI><a href="./ColorValue.html">ColorValue</a>
-          <LI><a href="./Buffer.html">Buffer</a>
-          <LI><a href="./BasicMatrix.html">BasicMatrix</a>
-          <LI><a href="./incident.html"><tt>incident</tt></a>
-          <LI><a href="./opposite.html"><tt>opposite</tt></a>

- <LI><ahref="./bandwidth.html#sec:bandwidth"><tt>bandwidth</tt></a>- <LI><ahref="./bandwidth.html#sec:ith-bandwidth"><tt>ith_bandwidth</tt></a>

-          <LI><a href="./random.html">Tools for random graphs</a>
-          <OL>
-          <LI><a href="./random.html#random_vertex">random_vertex</a>
-          <LI><a href="./random.html#random_edge">random_edge</a>

- <LI><ahref="./random.html#generate_random_graph">generate_random_graph</a>- <LI><ahref="./random.html#randomize_property">randomize_property</a>- <li><ahref="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></li>- <li><ahref="sorted_erdos_renyi_gen.html"><tt>sorted_erdos_renyi_iterator</tt></li>

-          <li><a href="plod_generator.html"><tt>plod_iterator</tt></li>

- <li><ahref="small_world_generator.html"><tt>small_world_iterator</tt></li>

-          </OL>
-        </OL>
-      <LI><a href="./challenge.html">Challenge and To-Do List</a>
-      <LI><a href="./trouble_shooting.html">Trouble Shooting</a>
-      <LI><a href="./known_problems.html">Known Problems</a>
-      <LI><a href="./faq.html">FAQ</a>
-      <LI><a href="http://siek.info/bgl.html";>BGL Book Errata</a>
-      </OL>
+<ol>
+<li><a href="./index.html">Introduction to the
+BGL图库简介</a> </li>
+<li><a href="./history.html">History 历史</a> </li>
+<li><a href="./users.html">List of BGL Users
+Boost图库用户列表</a> </li>
+<li><a href="./publications.html">Publications 出版</a>
+</li>
+<li><a href="./acknowledgements.html">Acknowledgements
+感谢</a> </li>
+<li><a href="./quick_tour.html">A Quick Tour of
+the Boost Graph Library. Boost图库快速指南</a> </li>
+<li><a href="graph_theory_review.html">Review of
+Elementary Graph Theory 图论基础回顾</a> </li>
+<li>Boost Graph Library Tutorial BGL指南
+<ol>
+<li><a href="./using_property_maps.html">Property
+Maps 属性映射</a> </li>
+<li><a href="./using_adjacency_list.html">The <tt>adjacency_list</tt>

+class </a><ahref="using_adjacency_list.html"><tt>adjacency_list</tt></a><ahref="./using_adjacency_list.html">类</a> </li>

+</ol>
+</li>
+<li>Examples 范例
+<ol>
+<li><a href="./file_dependency_example.html">File
+Dependency Example 文件关联范例</a> </li>
+<li><a href="./kevin_bacon.html">Six Degrees
+of Kevin Bacon 六度分离理论 </a> </li>
+<li><a href="./graph_coloring.html">Graph
+Coloring 图染色</a> </li>
+<li><a href="./sparse_matrix_ordering.html">Sparse
+Matrix Ordering 稀疏矩阵排序</a> </li>
+</ol>
+</li>
+<li>Extending the Boost Graph Library 图库扩展
+<ol>
+<li><a href="./constructing_algorithms.html">Constructing
+graph algorithms with BGL 用Boost图库构建图相关算法</a> </li>
+<li><a href="./leda_conversion.html">Converting
+Existing Graphs to BGL 非BGL图转换到BGL</a> </li>
+</ol>
+</li>
+<li><a href="./graph_concepts.html">The Boost
+Graph Interface Boost图库接口</a>
+<ol>
+<li><a href="./Graph.html">Graph 图</a> </li>
+<li><a href="./IncidenceGraph.html">Incidence
+Graph 关联图</a> </li>
+<li><a href="./BidirectionalGraph.html">Bidirectional
+Graph 双向图</a> </li>
+<li><a href="./AdjacencyGraph.html">Adjacency
+Graph 邻接图</a> </li>
+<li><a href="./VertexListGraph.html">Vertex
+List Graph&nbsp;点表图</a> </li>
+<li><a href="./EdgeListGraph.html">Edge List
+Graph 边表图</a> </li>
+<li><a href="./VertexAndEdgeListGraph.html">Vertex
+and Edge List Graph 点边列表图</a> </li>
+<li><a href="./MutableGraph.html">Mutable
+Graph 可变图</a> </li>
+<li><a href="./PropertyGraph.html">Property
+Graph 属性图</a> </li>
+<li><a href="./MutablePropertyGraph.html">Mutable
+Property Graph 可变特性图</a> </li>
+</ol>
+</li>
+<li><a href="../../property_map/property_map.html">The
+Property Map Library 特性映射库</a> (technically not part of the graph
+library, but used a lot here) </li>

+<li><img src="figs/python_ico.gif" alt="(Python)"><ahref="python.html">Python bindings</a></li>

+<li><a href="./visitor_concepts.html">Visitor
+Concepts 遍历器概念</a>
+<ol>
+<li><a href="./BFSVisitor.html">BFS Visitor
+广度优先遍历器</a> </li>
+<li><a href="./DFSVisitor.html">DFS Visitor
+深度优先遍历器</a> </li>
+<li><a href="./DijkstraVisitor.html">Dijkstra
+Visitor&nbsp;</a><a href="DijkstraVisitor.html">Dijkstra
+遍历器</a> </li>
+<li><a href="./BellmanFordVisitor.html">Bellman
+Ford Visitor&nbsp;</a><a href="BellmanFordVisitor.html">Bellman
+Ford遍历器</a> </li>
+<li><a href="AStarVisitor.html">A* Visitor
+A*遍历器</a></li>
+<li><a href="./EventVisitor.html">Event
+Visitor 事件遍历器</a></li>
+<li><a href="./PlanarFaceVisitor.html">Planar

+Face Visitor 平面遍历器</a></li><li><a href="TSPTourVisitor.html">TSP TourVisitor  TSP巡游遍历器</a></li>

+</ol>
+</li>
+<li>EventVisitorList Adaptors 事件遍历器列表适配器
+<ol>
+<li><a href="./EventVisitorList.html">Event
+Visitor List 事件遍历器列表</a> </li>
+<li><tt><a href="bfs_visitor.html"><tt>bfs_visitor</tt></a></tt>
+</li>
+<li><tt><a href="dfs_visitor.html"><tt>dfs_visitor</tt></a></tt>
+</li>
+<li><tt><a href="dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a></tt>
+</li>
+<li><a href="./bellman_visitor.html"><tt>bellman_visitor</tt></a>
+</li>
+<li><a href="astar_visitor.html"><tt>astar_visitor</tt></a></li>
+</ol>
+</li>
+<li>Event Visitors 事件遍历器
+<ol>
+<li><a href="./predecessor_recorder.html"><tt>predecessor_recorder</tt></a>
+</li>
+<li><a href="./distance_recorder.html"><tt>distance_recorder</tt></a>
+</li>
+<li><a href="./time_stamper.html"><tt>time_stamper</tt></a>
+</li>

+<li><ahref="./property_writer.html"><tt>property_writer</tt></a></li><li><ahref="tsp_tour_visitor.html"><tt>tsp_tour_visitor</tt></a>+</li><li><ahref="tsp_tour_len_visitor.html"><tt>tsp_tour_len_visitor</tt></a> </li>

+</ol>
+</li>
+<li>Graph classes 图相关类
+<ol>
+<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a></li>
+<li><a href="./adjacency_matrix.html"><tt>adjacency_matrix</tt></a></li>

+<li><ahref="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a></li>

+</ol>
+</li>
+<li>Graph Adaptors 图相关适配器
+<ol>
+<li><a href="./subgraph.html"><tt>subgraph</tt></a>
+</li>
+<li><a href="./edge_list.html"><tt>edge_list</tt></a>
+</li>
+<li><a href="./reverse_graph.html"><tt>reverse_graph</tt></a>
+</li>
+<li><a href="./filtered_graph.html"><tt>filtered_graph</tt></a>
+</li>
+<li><a href="../../../boost/graph/vector_as_graph.hpp">Vector
+as Graph </a><a href="#*">*</a> </li>
+<li><a href="../../../boost/graph/matrix_as_graph.hpp">Matrix
+as Graph</a><a href="#*">*</a> </li>
+<li><a href="../../../boost/graph/leda_graph.hpp">Leda
+Graph </a><a href="#*">*</a> </li>
+<li><a href="./stanford_graph.html">Stanford
+GraphBase</a> </li>
+</ol>
+</li>
+<li>Iterator Adaptors 迭代器适配器
+<ol>
+<li><a href="./adjacency_iterator.html"><tt>adjacency_iterator</tt></a>
+</li>

+<li><ahref="./inv_adjacency_iterator.html"><tt>inv_adjacency_iterator</tt></a>

+</li>
+</ol>
+</li>
+<li>Traits classes 特性类
+<ol>
+<li><a href="./graph_traits.html"><tt>graph_traits</tt></a>
+</li>

+<li><ahref="./adjacency_list_traits.html"><tt>adjacency_list_traits</tt></a>

+</li>
+<li><a href="./property_map.html"><tt>property_map</tt></a>
+</li>
+</ol>
+</li>
+<li>Algorithms 算法
+<ol>
+<li><a href="./bgl_named_params.html"><tt>bgl_named_params</tt></a>
+</li>
+<li>Core Algorithm Patterns 核心算法模式
+<ol>
+<li><a href="./breadth_first_search.html"><tt>breadth_first_search</tt></a>
+</li>
+<li><a href="./breadth_first_visit.html"><tt>breadth_first_visit</tt></a>
+</li>
+<li><a href="./depth_first_search.html"><tt>depth_first_search</tt></a>
+</li>
+<li><a href="./depth_first_visit.html"><tt>depth_first_visit</tt></a>
+</li>
+<li><a href="./undirected_dfs.html"><tt>undirected_dfs</tt></a>
+</li>
+</ol>
+</li>
+<li>Graph Algorithms 图算法
+<ol>
+<li>Shortest Paths Algorithms 最短路径算法
+<ol>

+<li><ahref="./dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths</tt></a>

+</li>

+<li><ahref="./bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths</tt></a>

+</li>
+<li><a href="./dag_shortest_paths.html"><tt>dag_shortest_paths</tt></a>
+</li>

+<li><ahref="./johnson_all_pairs_shortest.html"><tt>johnson_all_pairs_shortest_paths</tt></a>

+</li>

+<li><ahref="floyd_warshall_shortest.html"><tt>floyd_warshall_all_pairs_shortest_paths</tt></a></li><li><ahref="http://alai04.kmip.net/boost_doc/libs/graph/doc/r_c_shortest_paths.html";><tt>r_c_shortest_paths</tt>- resource-constrained shortest paths</a></li>

+</ol>
+</li>
+<li>Minimum Spanning Tree Algorithms 最小生成树算法
+<ol>

+<li><ahref="./kruskal_min_spanning_tree.html"><tt>kruskal_minimum_spanning_tree</tt></a>

+</li>

+<li><ahref="./prim_minimum_spanning_tree.html"><tt>prim_minimum_spanning_tree</tt></a>

+</li>
+</ol>
+</li>
+<li>Connected Components Algorithms 连通分支算法
+<ol>
+<li><a href="./connected_components.html"><tt>connected_components</tt></a>
+</li>
+<li><a href="./strong_components.html"><tt>strong_components</tt></a>
+</li>

+<li><ahref="biconnected_components.html"><tt>biconnected_components</tt></a>

+</li>

+<li><ahref="biconnected_components.html#sec:articulation_points"><tt>articulation_points</tt></a>

+</li>
+<li><a href="./incremental_components.html">Incremental
+Connected Components 增量连通分支</a>
+<ol>

+<li><ahref="./incremental_components.html#sec:initialize-incremental-components"><tt>initialize_incremental_components</tt></a>

+</li>

+<li><ahref="./incremental_components.html#sec:incremental-components"><tt>incremental_components</tt></a>

+</li>

+<li><ahref="./incremental_components.html#sec:same-component"><tt>same_component</tt></a>

+</li>

+<li><ahref="./incremental_components.html#sec:component-index"><tt>component_index</tt></a>

+</li>
+</ol>
+</li>
+</ol>
+</li>
+<li>Maximum Flow and Matching Algorithms 最大流和最大匹配算法
+<ol>

+<li><ahref="./edmunds_karp_max_flow.html"><tt>edmunds_karp_max_flow</tt></a>

+</li>

+<li><ahref="./push_relabel_max_flow.html"><tt>push_relabel_max_flow</tt></a></li>+<li><ahref="kolmogorov_max_flow.html"><tt>kolmogorov_max_flow</tt></a></li>+<li><ahref="./maximum_matching.html"><tt>edmonds_maximum_cardinality_matching</tt></a>

+</li>
+</ol>
+</li>
+<li>Sparse Matrix Ordering Algorithms 稀疏矩阵排序算法
+<ol>

+<li><ahref="./cuthill_mckee_ordering.html"><tt>cuthill_mckee_ordering</tt></a>

+</li>
+<li><a href="king_ordering.html"><tt>king_ordering</tt></a></li>

+<li><ahref="./minimum_degree_ordering.html"><tt>minimum_degree_ordering</tt></a>

+</li>
+</ol>
+</li>
+<li><a href="./topological_sort.html"><tt>topological_sort</tt></a>
+</li>
+<li><a href="./transitive_closure.html"><tt>transitive_closure</tt></a>
+</li>
+<li><a href="./copy_graph.html"><tt>copy_graph</tt></a>
+</li>
+<li><a href="./transpose_graph.html"><tt>transpose_graph</tt></a>
+</li>

+<li><a href="./isomorphism.html"><tt>isomorphism</tt></a></li><li>Path andTour Algorithms 路径和巡游算法

+<ol><li><a href="metric_tsp_approx.html"><tt>metric_tsp_approx</tt></a>
+</li></ol></li>

+<li><ahref="sequential_vertex_coloring.html"><tt>sequential_vertex_coloring</tt></a>

+</li>
+<li><a href="./sloan_ordering.htm"><tt>sloan_ordering</tt></a></li>

+<li><ahref="sloan_start_end_vertices.htm"><tt>sloan_start_end_vertices</tt></a></li>

+<li><a href="./wavefront.htm"><tt>ith_wavefront</tt>,
+<tt>max_wavefront</tt>, <tt>aver_wavefront</tt>,
+and <tt>rms_wavefront</tt></a></li>

+<li><ahref="betweenness_centrality.html"><tt>brandes_betweenness_centrality</tt></a></li>

+<li>Layout algorithms 排样算法
+<ol>
+<li><a href="random_layout.html"><tt>random_graph_layout</tt></a></li>
+<li><a href="circle_layout.html"><tt>circle_layout</tt></a></li>

+<li><ahref="kamada_kawai_spring_layout.html"><tt>kamada_kawai_spring_layout</tt></a></li>+<li><ahref="fruchterman_reingold.html"><tt>fruchterman_reingold_force_directed_layout</tt></a></li>

+<li><a href="gursoy_atun_layout.html"><tt>gursoy_atun_layout</tt></a></li>
+</ol>
+</li>
+<li>Clustering algorithms 聚类算法
+<ol>

+<li><ahref="bc_clustering.html"><tt>betweenness_centrality_clustering</tt></a></li>

+</ol>
+</li>
+<li><a href="astar_search.html"><tt>astar_search</tt></a></li>

+<li><ahref="lengauer_tarjan_dominator.htm"><tt>lengauer_tarjan_dominator_tree</tt></a></li>

+<li><a href="howard_cycle_ratio.html"><tt>minimum_cycle_ratio</tt>
+and <tt>maximum_cycle_ratio</tt></a></li>
+<li><a href="planar_graphs.html">Planar
+Graph Algorithms 平面图算法</a>
+<ol>
+<li><a href="boyer_myrvold.html">
+<tt>boyer_myrvold_planarity_test</tt></a>
+</li>
+<li><a href="planar_face_traversal.html"><tt>planar_face_traversal</tt></a>
+</li>

+<li><ahref="planar_canonical_ordering.html"><tt>planar_canonical_ordering</tt></a>

+</li>

+<li><ahref="straight_line_drawing.html"><tt>chrobak_payne_straight_line_drawing</tt></a>

+</li>

+<li><ahref="is_straight_line_drawing.html"><tt>is_straight_line_drawing</tt></a>

+</li>

+<li><ahref="is_kuratowski_subgraph.html"><tt>is_kuratowski_subgraph</tt></a>

+</li>
+<li><a href="make_connected.html"><tt>make_connected</tt></a>
+</li>

+<li><ahref="make_biconnected_planar.html"><tt>make_biconnected_planar</tt></a>

+</li>
+<li><a href="make_maximal_planar.html"><tt>make_maximal_planar</tt></a>
+</li>
+</ol>
+</li>

+<li><ahref="lengauer_tarjan_dominator.htm"><tt>lengauer_tarjan_dominator_tree</tt></a></li>

+</ol>
+</li>
+</ol>
+</li>
+<li>Graph Input/Output 图的输入/输出
+<ol>
+<li>AT&amp;T Graphviz: <a href="read_graphviz.html">read_graphviz</a>,
+<a href="./write-graphviz.html">write_graphviz</a></li>
+<li>DIMACS Max-flow: <a href="read_dimacs.html">read_dimacs_max_flow</a>,
+<a href="write_dimacs.html">write_dimacs_max_flow</a></li>
+<li>GraphML: <a href="read_graphml.html">read_graphml</a>
+and <a href="write_graphml.html">write_graphml</a></li>
+</ol>
+</li>
+<li>Auxiliary Concepts, Classes, and Functions 相关类和函数的一些补充
+<ol>
+<li><a href="./property.html"><tt>property</tt></a>
+</li>
+<li><a href="./ColorValue.html">ColorValue</a>
+</li>
+<li><a href="./Buffer.html">Buffer</a> </li>
+<li><a href="./BasicMatrix.html">BasicMatrix</a>
+</li>
+<li><a href="./incident.html"><tt>incident</tt></a>
+</li>
+<li><a href="./opposite.html"><tt>opposite</tt></a>
+</li>
+<li><a href="./bandwidth.html#sec:bandwidth"><tt>bandwidth</tt></a>
+</li>
+<li><a href="./bandwidth.html#sec:ith-bandwidth"><tt>ith_bandwidth</tt></a>
+</li>
+<li><a href="./random.html">Tools for random
+graphs</a>
+<ol>
+<li><a href="./random.html#random_vertex">random_vertex</a>
+</li>
+<li><a href="./random.html#random_edge">random_edge</a>
+</li>
+<li><a href="./random.html#generate_random_graph">generate_random_graph</a>
+</li>
+<li><a href="./random.html#randomize_property">randomize_property</a>
+</li>

+<li><ahref="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a></li>+<li><ahref="sorted_erdos_renyi_gen.html"><tt>sorted_erdos_renyi_iterator</tt></a></li>

+<li><a href="plod_generator.html"><tt>plod_iterator</tt></a></li>

+<li><ahref="small_world_generator.html"><tt>small_world_iterator</tt></a></li>

+</ol>
+<a href="small_world_generator.html"> </a></li>
+</ol>
+<a href="small_world_generator.html"> </a></li>
+<li><a href="./challenge.html">Challenge and To-Do
+List 难题和未做列表</a> </li>
+<li><a href="./trouble_shooting.html">Trouble
+Shooting 疑难解答</a> </li>
+<li><a href="./known_problems.html">Known Problems
+已知问题</a> </li>
+<li><a href="./faq.html">FAQ</a> </li>
+<li><a href="http://siek.info/bgl.html";>BGL Book
+Errata BGL书籍刊误表</a> </li>
+</ol>
 <p>
-
-<a name="*">*</a> Items marked have not yet been documented.
-
-<br>
-<HR>
-<TABLE>
-<TR valign=top>
-<TD nowrap>Copyright &copy 2000-2001</TD><TD>
-<A HREF="http://www.boost.org/people/jeremy_siek.htm";>Jeremy Siek</A>,
-Indiana University (<A
-HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>

-<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>,Indiana University (<AHREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>) 

-<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
-Indiana University (<A
-HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
-</TD></TR></TABLE>
-
-</BODY>
-</HTML>
+<a name="*">*</a> Items marked have not yet been
+documented.
+*表示还没有相关文档<br>
+</p>
+<hr>
+<table>
+<tbody>
+<tr valign="top">
+<td nowrap="nowrap">Copyright (c) 2000-2001</td>
+<td> <a href="../../../people/jeremy_siek.htm">Jeremy
+Siek</a>,

+Indiana University (<ahref="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>) 

+<a href="../../../people/liequan_lee.htm">Lie-Quan

+Lee</a>, Indiana University (<ahref="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</a>) 

+<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>
\ No newline at end of file

Modified: trunk/libs/graph/doc/users.html
==============================================================================
--- trunk/libs/graph/doc/users.html     (original)
+++ trunk/libs/graph/doc/users.html     Fri Jun 26 00:01:13 2009
@@ -1,45 +1,40 @@
-<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) 2002 Trustees of Indiana University
   --
   -- Distributed under the Boost Software License, Version 1.0.
   -- (See accompanying file LICENSE_1_0.txt or copy at
   -- http://www.boost.org/LICENSE_1_0.txt)
-  -->
-<title>Boost Graph Library Users</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>Boost Graph Library Users</h1>
-
-<p>This is a list of people, projects, courses, companies, and other
-languages that are using the Boost Graph Library in some way, shape,
-or form.</p>
+  --><title>Boost Graph Library Users</title></head>

-<p>If you are using the BGL and want to be listed here, please send
-  mail to the Boost Users mailing list!</p>
+

+<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>Boost Graph Library Users &nbsp;Boost图库的用户</h1>
+

+以下列出以各种方法、方式或形式使用BGL的人、项目、课程、公司和其它语言。

+
+<p>如果你正在使用BGL且想被列入，请发邮件给Boost用户邮件列表！</p>

 <ul>

- <li><a href="http://www.cs.rpi.edu/~musser/gsd/";>Generic Software DesignCourse at RPI</a></li>

+  <li><a href="http://www.cs.rpi.edu/%7Emusser/g

==============================================================================
Diff truncated at 200k characters

[boost-doc-zh commit] r276 - graph 库文档第1-7章，由felurkinda翻译，alai04校验。

Other related posts: