[boost-doc-zh commit] r254 - 转换至1.39.0,第7批,完成以下库:filesystem, flyweight, format, function_type...

  • From: codesite-noreply@xxxxxxxxxx
  • To: boost-doc-zh-notify@xxxxxxxxxxxxx
  • Date: Tue, 02 Jun 2009 04:30:11 +0000

Author: alai04
Date: Mon Jun  1 21:27:33 2009
New Revision: 254

Added:
   trunk/libs/functional/test/
   trunk/libs/functional/test/CMakeLists.txt
   trunk/libs/functional/test/Jamfile.v2
   trunk/libs/functional/test/function_test.cpp
Removed:
   trunk/libs/functional/function_test.cpp
Modified:
   trunk/libs/flyweight/doc/acknowledgements.html
   trunk/libs/flyweight/doc/release_notes.html
   trunk/libs/functional/index.html
   trunk/libs/graph/doc/BFSVisitor.html
   trunk/libs/graph/doc/BellmanFordVisitor.html
   trunk/libs/graph/doc/ColorValue.html
   trunk/libs/graph/doc/DFSVisitor.html
   trunk/libs/graph/doc/DijkstraVisitor.html
   trunk/libs/graph/doc/EventVisitor.html
   trunk/libs/graph/doc/EventVisitorList.html
   trunk/libs/graph/doc/IncidenceGraph.html
   trunk/libs/graph/doc/IteratorConstructibleGraph.html
   trunk/libs/graph/doc/Monoid.html
   trunk/libs/graph/doc/acknowledgements.html
   trunk/libs/graph/doc/adjacency_list.html
   trunk/libs/graph/doc/adjacency_list_traits.html
   trunk/libs/graph/doc/bellman_visitor.html
   trunk/libs/graph/doc/betweenness_centrality.html
   trunk/libs/graph/doc/bfs_visitor.html
   trunk/libs/graph/doc/bgl_named_params.html
   trunk/libs/graph/doc/circle_layout.html
   trunk/libs/graph/doc/compressed_sparse_row.html
   trunk/libs/graph/doc/constructing_algorithms.html
   trunk/libs/graph/doc/default.css
   trunk/libs/graph/doc/depth_first_search.html
   trunk/libs/graph/doc/dfs_visitor.html
   trunk/libs/graph/doc/dijkstra_visitor.html
   trunk/libs/graph/doc/distance_recorder.html
   trunk/libs/graph/doc/edge_list.html
   trunk/libs/graph/doc/erdos_renyi_generator.html
   trunk/libs/graph/doc/filtered_graph.html
   trunk/libs/graph/doc/graph_coloring.html
   trunk/libs/graph/doc/graph_theory_review.html
   trunk/libs/graph/doc/graph_traits.html
   trunk/libs/graph/doc/gursoy_atun_layout.html
   trunk/libs/graph/doc/history.html
   trunk/libs/graph/doc/incident.html
   trunk/libs/graph/doc/incremental_components.html
   trunk/libs/graph/doc/index.html
   trunk/libs/graph/doc/known_problems.html
   trunk/libs/graph/doc/leda_conversion.html
   trunk/libs/graph/doc/null_visitor.html
   trunk/libs/graph/doc/opposite.html
   trunk/libs/graph/doc/plod_generator.html
   trunk/libs/graph/doc/predecessor_recorder.html
   trunk/libs/graph/doc/property_map.html
   trunk/libs/graph/doc/property_writer.html
   trunk/libs/graph/doc/publications.html
   trunk/libs/graph/doc/python.html
   trunk/libs/graph/doc/quick_tour.html
   trunk/libs/graph/doc/sequential_vertex_coloring.html
   trunk/libs/graph/doc/small_world_generator.html
   trunk/libs/graph/doc/sorted_erdos_renyi_gen.html
   trunk/libs/graph/doc/stanford_graph.html
   trunk/libs/graph/doc/table_of_contents.html
   trunk/libs/graph/doc/time_stamper.html
   trunk/libs/graph/doc/trouble_shooting.html
   trunk/libs/graph/doc/undirected_dfs.html
   trunk/libs/graph/doc/visitor_concepts.html

Log:
转换至1.39.0,第7批,完成以下库:filesystem, flyweight, format, function_types, functional, fusion, gil, graph, in_place_factory&typed_in_place_factory, integer, interval, io_state_savers, iostreams, iterators

Modified: trunk/libs/flyweight/doc/acknowledgements.html
==============================================================================
--- trunk/libs/flyweight/doc/acknowledgements.html      (original)
+++ trunk/libs/flyweight/doc/acknowledgements.html      Mon Jun  1 21:27:33 2009
@@ -59,6 +59,16 @@
 dire straits gentler oceans will lie.
 </p>

+<h2><a name="boost_1_39">Boost 1.39 release</a></h2>
+
+<p>
+Many thanks to Tim Blechmann for helping identify and solve a serious
+<a href="release_notes.html#refcounted_bug">tread safety problem</a>
+and to Peter Dimov for kindly extending the interface of his
+<code>boost::detail::atomic_count</code> utility to allow for the
+implementation of the fix.
+</p>
+
 <hr>

<div class="prev_link"><a href="release_notes.html"><img src="prev.gif" alt="release notes" border="0"><br>
@@ -72,9 +82,9 @@

 <br>

-<p>Revised December 10th 2008</p>
+<p>Revised April 18th 2009</p>

-<p>© Copyright 2006-2008 Joaquín M López Muñoz.
+<p>© Copyright 2006-2009 Joaquín M López Muñoz.
 Distributed under the Boost Software
License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt"> LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt";>

Modified: trunk/libs/flyweight/doc/release_notes.html
==============================================================================
--- trunk/libs/flyweight/doc/release_notes.html (original)
+++ trunk/libs/flyweight/doc/release_notes.html Mon Jun  1 21:27:33 2009
@@ -1,103 +1,63 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
-<html>
-<head>
-
-  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
-
-
-  <title>Boost.Flyweight Documentation - Release notes</title>
-  <link rel="stylesheet" href="style.css" type="text/css">
-
-  <link rel="start" href="index.html">
-
-  <link rel="prev" href="future_work.html">
-
-  <link rel="up" href="index.html">
-
-  <link rel="next" href="acknowledgements.html">
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
+<html><head>
+<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Boost.Flyweight Documentation - Release notes</title>
+
+<link rel="stylesheet" href="style.css" type="text/css">
+<link rel="start" href="index.html">
+<link rel="prev" href="future_work.html">
+<link rel="up" href="index.html">
+<link rel="next" href="acknowledgements.html">
 </head>

 <body>
-
-<h1><img src="../../../boost.png" alt="Boost logo" align="middle" height="86" width="277">Boost.Flyweight Release notes</h1>
-
-
+<h1><img src="../../../boost.png" alt="Boost logo" align="middle" height="86" width="277">Boost.Flyweight
+Release notes</h1>
<div class="prev_link"><a href="future_work.html"><img src="prev.gif" alt="future work" border="0"><br>
-
 Future work
 </a></div>
-
<div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
-
 Index
 </a></div>
-
<div class="next_link"><a href="acknowledgements.html"><img src="next.gif" alt="acknowledgements" border="0"><br>
-
 Acknowledgements
 </a></div>
 <br style="" clear="all">
-
 <br style="" clear="all">
-
-
 <hr>
-
 <h2>Contents &nbsp;目录</h2>
-
-
 <ul>
-
-  <li><a href="#boost_1_38">Boost 1.38 release</a></li>
-
+<li><a href="#boost_1_39">Boost 1.39 release</a></li>
+<li><a href="#boost_1_38">Boost 1.38 release</a></li>
 </ul>
-
-
-<h2><a name="boost_1_38">Boost 1.38 release Boost 1.38 发布</a></h2>
-
-
-<p>
-</p>
+<h2><a name="boost_1_38">Boost 1.39
+release&nbsp;Boost 1.39 发布</a></h2>
 <ul>
-
-  <li>Initial release of Boost.Flyweight.</li>
-
+<li><a name="refcounted_bug">The </a><a href="tutorial/configuration.html#refcounted"><code>refcounted</code></a>
+component was not thread-safe due to an incorrect implementation and
+could deadlock under heavy usage conditions. This problem has been
+corrected.<br>由于一个不正确的实现,组件 <a href="tutorial/configuration.html#refcounted"><code>refcounted</code></a>
+不是线程安全的,在重度使用的条件下有可能会死锁。该问题已被修正。</li>
 </ul>
-<div style="margin-left: 40px;">Boost.Flyweight首次发布</div>
-<hr>
-
-<div class="prev_link"><a href="future_work.html"><img src="prev.gif" alt="future work" border="0"><br>
-
+<h2><a name="boost_1_38">Boost 1.38 release</a></h2>
+<ul><li>Initial release of Boost.Flyweight.<br>Boost.Flyweight 的首次发布。 </li></ul><hr> +<div class="prev_link"><b><a href="future_work.html"><img src="prev.gif" alt="future work" border="0"><br>
 Future work
-</a></div>
-
-<div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
-
+</a></b></div>
+<div class="up_link"><b><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
 Index
-</a></div>
-
-<div class="next_link"><a href="acknowledgements.html"><img src="next.gif" alt="acknowledgements" border="0"><br>
-
+</a></b></div>
+<div class="next_link"><b><a href="acknowledgements.html"><img src="next.gif" alt="acknowledgements" border="0"><br>
 Acknowledgements
-</a></div>
+</a></b></div>
+<b><br style="" clear="all">
 <br style="" clear="all">
-
-<br style="" clear="all">
-
-
 <br>
-
-
-<p>Revised August 27th 2008</p>
-
-
-<p>&copy; Copyright 2006-2008 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
-Distributed under the Boost Software
-License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">
+</b>
+<p><b>Revised August 27th 2008</b></p>
+<p><b>© Copyright 2006-2008 Joaquín M López Muñoz.
+Distributed under the Boost Software License, Version 1.0. (See
+accompanying file <a href="../../../LICENSE_1_0.txt">
LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt";>
 http://www.boost.org/LICENSE_1_0.txt</a>)
-</p>
-
-
-</body>
-</html>
+</b></p>
+</body></html>
\ No newline at end of file

Modified: trunk/libs/functional/index.html
==============================================================================
--- trunk/libs/functional/index.html    (original)
+++ trunk/libs/functional/index.html    Mon Jun  1 21:27:33 2009
@@ -3,9 +3,7 @@
 <meta http-equiv="Content-Language" content="en-us">
 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
 <meta name="GENERATOR" content="Microsoft FrontPage 6.0">
-<meta name="ProgId" content="FrontPage.Editor.Document"><title>Boost Function Object Adapter Library</title>
-
-</head>
+<meta name="ProgId" content="FrontPage.Editor.Document"><title>Boost Function Object Adapter Library</title></head>
 <body style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255);">
 <table summary="" bgcolor="#007f7f" border="1" cellpadding="2">
 <tbody>
@@ -141,9 +139,9 @@
 接受的是一个引用参数。对此的解释请参见 <a href="binders.html#refref">binder
 文档</a> 中的注解。</p>
 <h3>Compiler Compatibility 编译器兼容性</h3>
-<p>The header and <a href="function_test.cpp">test
+<p>The header and <a href="test/function_test.cpp">test
 program</a> have been compiled with the following compilers:</p>
-<p>相关头文件和 <a href="function_test.cpp">测试程序</a>
+<p>相关头文件和 <a href="test/function_test.cpp">测试程序</a>
 已经在以下编译器通过编译:</p>
 <table summary="" border="1" cellpadding="5">
 <tbody>

Added: trunk/libs/functional/test/CMakeLists.txt
==============================================================================
--- (empty file)
+++ trunk/libs/functional/test/CMakeLists.txt   Mon Jun  1 21:27:33 2009
@@ -0,0 +1 @@
+boost_test_run(function_test function_test.cpp)

Added: trunk/libs/functional/test/Jamfile.v2
==============================================================================
--- (empty file)
+++ trunk/libs/functional/test/Jamfile.v2       Mon Jun  1 21:27:33 2009
@@ -0,0 +1,9 @@
+#~ Copyright Rene Rivera 2008
+#~ Distributed under the Boost Software License, Version 1.0.
+#~ (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+import testing ;
+
+test-suite functional :
+    [ run function_test.cpp ]
+    ;

Added: trunk/libs/functional/test/function_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/functional/test/function_test.cpp        Mon Jun  1 21:27:33 2009
@@ -0,0 +1,334 @@
+// ------------------------------------------------------------------------------
+// Copyright (c) 2000 Cadenza New Zealand Ltd
+// Distributed under the Boost Software License, Version 1.0. (See accompany- +// ing file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// ------------------------------------------------------------------------------
+// Tests for the Boost functional.hpp header file
+//
+// Note that functional.hpp relies on partial specialisation to be
+// effective.  If your compiler lacks this feature, very few of the
+// tests would compile, and so have been excluded from the test.
+// ------------------------------------------------------------------------------
+// $Id: function_test.cpp 50456 2009-01-04 05:17:02Z bgubenko $
+// ------------------------------------------------------------------------------
+// $Log$
+// Revision 1.3  2006/12/02 13:57:32  andreas_huber69
+// Fixed license & copyright issues.
+//
+// From Mark Rodgers Fri Dec 1 12:59:14 2006
+// X-Apparently-To: ahd6974-boostorg -at- yahoo.com via 68.142.206.160; Fri, 01 Dec 2006 12:59:41 -0800
+// X-Originating-IP: [195.112.4.54]
+// Return-Path: <mark.rodgers -at- cadenza.co.nz>
+// Authentication-Results: mta550.mail.mud.yahoo.com from=cadenza.co.nz; domainkeys=neutral (no sig) +// Received: from 195.112.4.54 (EHLO smtp.nildram.co.uk) (195.112.4.54) by mta550.mail.mud.yahoo.com with SMTP; Fri, 01 Dec 2006 12:59:40 -0800 +// Received: from snagglepuss.cadenza.co.nz (81-6-246-87.dyn.gotadsl.co.uk [81.6.246.87]) by smtp.nildram.co.uk (Postfix) with ESMTP id D32EA2B6D8C for <ahd6974-boostorg -at- yahoo.com>; Fri, 1 Dec 2006 20:59:35 +0000 (GMT) +// Received: from penfold.cadenza.co.nz ([192.168.55.56]) by snagglepuss.cadenza.co.nz with esmtp (Exim 4.63) (envelope-from <mark.rodgers -at- cadenza.co.nz>) id J9M4Y9-0009TO-9K for ahd6974-boostorg -at- yahoo.com; Fri, 01 Dec 2006 20:58:57 +0000
+// Message-ID: <457097A2.1090305@xxxxxxxxxxxxx>
+// Date: Fri, 01 Dec 2006 20:59:14 +0000
+// From: "Mark Rodgers" <mark.rodgers -at- cadenza.co.nz>
+// User-Agent: Thunderbird 1.5.0.8 (Macintosh/20061025)
+// MIME-Version: 1.0
+// To: ahd6974-boostorg -at- yahoo.com [Edit - Delete]
+// Subject: Re: [boost] Reminder: Need your permission to correct license & copyright issues
+// References: <379990.36007.qm@xxxxxxxxxxxxxxxxxxxxxxxxxxx>
+// In-Reply-To: <379990.36007.qm@xxxxxxxxxxxxxxxxxxxxxxxxxxx>
+// Content-Type: text/plain; charset=ISO-8859-1; format=flowed
+// Content-Transfer-Encoding: 7bit
+// Content-Length: 812
+// Gidday Andreas
+//
+// Sure that's fine.  I'm happy for you to do 1, 2 and 3.
+//
+// Regards
+// Mark
+//
+// Andreas Huber wrote:
+// > Hello Mark
+// >
+// > Quite a while ago it was decided that every file that goes into the
+// > 1.34 release of the Boost distribution (www.boost.org) needs uniform
+// > license and copyright information. For more information please see:
+// >
+// > <http://www.boost.org/more/license_info.html>
+// >
+// > You are receiving this email because several files you contributed
+// > lack such information or have an old license:
+// >
+// > boost/functional/functional.hpp
+// > boost/libs/functional/binders.html
+// > boost/libs/functional/function_test.cpp
+// > boost/libs/functional/function_traits.html
+// > boost/libs/functional/index.html
+// > boost/libs/functional/mem_fun.html
+// > boost/libs/functional/negators.html
+// > boost/libs/functional/ptr_fun.html
+// > boost/people/mark_rodgers.htm
+// >
+// > I therefore kindly ask you to grant the permission to do the
+// > following:
+// >
+// > 1. For the files above that already have a license text (all except
+// > mark_rodgers.htm), replace the license text with:
+// >
+// > "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)"
+// >
+// > 2. For the file that does not yet have a license and copyright
+// > (mark_rodgers.htm) add the same license text as under 1. and add the
+// > following copyright:
+// >
+// > "(c) Copyright Mark Rodgers 2000"
+// >
+// > 3. (Optional) I would also want to convert all HTML files to conform
+// > the HTML 4.01 Standard by running them through HTML Tidy, see
+// > <http://tidy.sf.net>
+// >
+// > It would be great if you could grant me permission to do 1 & 2 and
+// > optionally also 3.
+// >
+// > Thank you!
+// >
+// > Regards,
+// >
+// > Andreas Huber
+// >
+//
+// Revision 1.2  2001/09/22 11:52:24  johnmaddock
+// Intel C++ fixes: no void return types supported.
+//
+// Revision 1.1.1.1  2000/07/07 16:04:18  beman
+// 1.16.1 initial CVS checkin
+//
+// Revision 1.3  2000/06/26 09:44:01  mark
+// Updated following feedback from Jens Maurer.
+//
+// Revision 1.2  2000/05/17 08:31:45  mark
+// Added extra tests now that function traits work correctly.
+// For compilers with no support for partial specialisation,
+// excluded tests that won't work.
+//
+// Revision 1.1  2000/05/07 09:14:41  mark
+// Initial revision
+// ------------------------------------------------------------------------------
+
+// To demonstrate what the boosted function object adapters do for
+// you, try compiling with USE_STD defined.  This will endeavour to
+// use the standard function object adapters, but is likely to result
+// in numerous errors due to the fact that you cannot have references
+// to references.
+#ifdef USE_STD
+#include <functional>
+#define boost std
+#else
+#include <boost/functional.hpp>
+#endif
+
+#include <algorithm>
+#include <iostream>
+#include <iterator>
+#include <string>
+#include <vector>
+
+class Person
+{
+  public:
+    Person() {}
+    Person(const char *n) : name(n) {}
+
+    const std::string &get_name() const { return name; }
+    void print(std::ostream &os) const { os << name << " "; }
+ void set_name(const std::string &n) { name = n; std::cout << name << " "; } + std::string clear_name() { std::string ret = name; name = ""; return ret; }
+    void do_something(int) const {}
+
+    bool is_fred() const { return name == "Fred"; }
+
+  private:
+    std::string name;
+};
+
+namespace
+{
+    bool is_equal(const std::string &s1, const std::string &s2)
+    {
+        return s1 == s2;
+    }
+
+    bool is_betty(const std::string &s)
+    {
+        return s == "Betty";
+    }
+
+    void do_set_name(Person *p, const std::string &name)
+    {
+        p->set_name(name);
+    }
+
+    void do_set_name_ref(Person &p, const std::string &name)
+    {
+        p.set_name(name);
+    }
+}
+
+int main()
+{
+    std::vector<Person> v1;
+    v1.push_back("Fred");
+    v1.push_back("Wilma");
+    v1.push_back("Barney");
+    v1.push_back("Betty");
+
+    const std::vector<Person> cv1(v1.begin(), v1.end());
+
+    std::vector<std::string> v2;
+    v2.push_back("Fred");
+    v2.push_back("Wilma");
+    v2.push_back("Barney");
+    v2.push_back("Betty");
+
+    Person person;
+    Person &r = person;
+
+    Person fred("Fred");
+    Person wilma("Wilma");
+    Person barney("Barney");
+    Person betty("Betty");
+    std::vector<Person*> v3;
+    v3.push_back(&fred);
+    v3.push_back(&wilma);
+    v3.push_back(&barney);
+    v3.push_back(&betty);
+
+    const std::vector<Person*> cv3(v3.begin(), v3.end());
+    std::vector<const Person*> v3c(v3.begin(), v3.end());
+
+    std::ostream &os = std::cout;
+
+#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(__ICL)
+    // unary_traits, unary_negate
+    std::transform(v2.begin(), v2.end(),
+                   std::ostream_iterator<bool>(std::cout, " "),
+                   boost::not1(is_betty));
+
+    std::cout << '\n';
+    std::transform(v1.begin(), v1.end(),
+                   std::ostream_iterator<bool>(std::cout, " "),
+                   boost::not1(boost::mem_fun_ref(&Person::is_fred)));
+
+    // binary_traits, binary_negate
+    std::cout << '\n';
+    std::transform(v2.begin(), v2.end(),
+                   std::ostream_iterator<bool>(std::cout, " "),
+                   boost::bind1st(boost::not2(is_equal), "Betty"));
+
+    std::cout << '\n';
+    std::transform(v2.begin(), v2.end(),
+                   std::ostream_iterator<bool>(std::cout, " "),
+                   boost::bind2nd(boost::not2(is_equal), "Betty"));
+
+    // pointer_to_unary_function
+    std::cout << '\n';
+    std::transform(v2.begin(), v2.end(),
+                   std::ostream_iterator<bool>(std::cout, " "),
+                   boost::not1(boost::ptr_fun(is_betty)));
+
+    // binary_traits, bind1st, bind2nd
+    std::cout << '\n';
+    std::transform(v2.begin(), v2.end(),
+                   std::ostream_iterator<bool>(std::cout, " "),
+                   boost::bind1st(is_equal, "Betty"));
+
+    std::cout << '\n';
+    std::transform(v2.begin(), v2.end(),
+                   std::ostream_iterator<bool>(std::cout, " "),
+                   boost::bind2nd(is_equal, "Betty"));
+
+    // pointer_to_binary_function, bind1st
+    std::cout << '\n';
+ std::for_each(v2.begin(), v2.end(), boost::bind1st(boost::ptr_fun(do_set_name), &person));
+
+    std::cout << '\n';
+ std::for_each(v2.begin(), v2.end(), boost::bind1st(boost::ptr_fun(do_set_name_ref), person));
+
+    std::cout << '\n';
+ std::for_each(v2.begin(), v2.end(), boost::bind1st(boost::ptr_fun(do_set_name_ref), r));
+
+    // binary_traits
+    std::cout << '\n';
+ std::for_each(v2.begin(), v2.end(), boost::bind1st(do_set_name, &person));
+
+    std::cout << '\n';
+ std::for_each(v2.begin(), v2.end(), boost::bind1st(do_set_name_ref, person));
+
+    std::cout << '\n';
+ std::for_each(v2.begin(), v2.end(), boost::bind1st(do_set_name_ref, r));
+#endif
+
+    // const_mem_fun_t
+    std::cout << '\n';
+    std::transform(v3.begin(), v3.end(),
+                   std::ostream_iterator<std::string>(std::cout, " "),
+                   boost::mem_fun(&Person::get_name));
+
+    std::cout << '\n';
+    std::transform(cv3.begin(), cv3.end(),
+                   std::ostream_iterator<std::string>(std::cout, " "),
+                   boost::mem_fun(&Person::get_name));
+
+    std::cout << '\n';
+    std::transform(v3c.begin(), v3c.end(),
+                   std::ostream_iterator<std::string>(std::cout, " "),
+                   boost::mem_fun(&Person::get_name));
+
+    // const_mem_fun_ref_t
+    std::cout << '\n';
+    std::transform(v1.begin(), v1.end(),
+                   std::ostream_iterator<std::string>(std::cout, " "),
+                   boost::mem_fun_ref(&Person::get_name));
+
+    std::cout << '\n';
+    std::transform(cv1.begin(), cv1.end(),
+                   std::ostream_iterator<std::string>(std::cout, " "),
+                   boost::mem_fun_ref(&Person::get_name));
+
+#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+    // const_mem_fun1_t, bind2nd
+    std::cout << '\n';
+ std::for_each(v3.begin(), v3.end(), boost::bind2nd(boost::mem_fun(&Person::print), std::cout));
+
+    std::cout << '\n';
+ std::for_each(v3.begin(), v3.end(), boost::bind2nd(boost::mem_fun(&Person::print), os));
+
+    // const_mem_fun1_ref_t, bind2nd
+    std::cout << '\n';
+ std::for_each(v1.begin(), v1.end(), boost::bind2nd(boost::mem_fun_ref(&Person::print), std::cout));
+
+    std::cout << '\n';
+ std::for_each(v1.begin(), v1.end(), boost::bind2nd(boost::mem_fun_ref(&Person::print), os));
+
+    // mem_fun1_t, bind1st
+    std::cout << '\n';
+ std::for_each(v2.begin(), v2.end(), boost::bind1st(boost::mem_fun(&Person::set_name), &person));
+
+    // mem_fun1_ref_t, bind1st
+    std::cout << '\n';
+ std::for_each(v2.begin(), v2.end(), boost::bind1st(boost::mem_fun_ref(&Person::set_name), person));
+
+    std::cout << '\n';
+ std::for_each(v2.begin(), v2.end(), boost::bind1st(boost::mem_fun_ref(&Person::set_name), r));
+#endif
+
+    // mem_fun_t
+    std::cout << '\n';
+ std::transform(v3.begin(), v3.end(), std::ostream_iterator<std::string>(std::cout, " "),
+                   boost::mem_fun(&Person::clear_name));
+
+    // mem_fun_ref_t
+    std::cout << '\n';
+ std::transform(v1.begin(), v1.end(), std::ostream_iterator<std::string>(std::cout, " "),
+                   boost::mem_fun_ref(&Person::clear_name));
+
+    std::cout << '\n';
+    return 0;
+}

Modified: trunk/libs/graph/doc/BFSVisitor.html
==============================================================================
--- trunk/libs/graph/doc/BFSVisitor.html        (original)
+++ trunk/libs/graph/doc/BFSVisitor.html        Mon Jun  1 21:27:33 2009
@@ -211,7 +211,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/BellmanFordVisitor.html
==============================================================================
--- trunk/libs/graph/doc/BellmanFordVisitor.html        (original)
+++ trunk/libs/graph/doc/BellmanFordVisitor.html        Mon Jun  1 21:27:33 2009
@@ -175,7 +175,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/ColorValue.html
==============================================================================
--- trunk/libs/graph/doc/ColorValue.html        (original)
+++ trunk/libs/graph/doc/ColorValue.html        Mon Jun  1 21:27:33 2009
@@ -99,7 +99,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/DFSVisitor.html
==============================================================================
--- trunk/libs/graph/doc/DFSVisitor.html        (original)
+++ trunk/libs/graph/doc/DFSVisitor.html        Mon Jun  1 21:27:33 2009
@@ -203,7 +203,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/DijkstraVisitor.html
==============================================================================
--- trunk/libs/graph/doc/DijkstraVisitor.html   (original)
+++ trunk/libs/graph/doc/DijkstraVisitor.html   Mon Jun  1 21:27:33 2009
@@ -213,7 +213,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/EventVisitor.html
==============================================================================
--- trunk/libs/graph/doc/EventVisitor.html      (original)
+++ trunk/libs/graph/doc/EventVisitor.html      Mon Jun  1 21:27:33 2009
@@ -152,7 +152,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/EventVisitorList.html
==============================================================================
--- trunk/libs/graph/doc/EventVisitorList.html  (original)
+++ trunk/libs/graph/doc/EventVisitorList.html  Mon Jun  1 21:27:33 2009
@@ -118,7 +118,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/IncidenceGraph.html
==============================================================================
--- trunk/libs/graph/doc/IncidenceGraph.html    (original)
+++ trunk/libs/graph/doc/IncidenceGraph.html    Mon Jun  1 21:27:33 2009
@@ -193,7 +193,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/IteratorConstructibleGraph.html
==============================================================================
--- trunk/libs/graph/doc/IteratorConstructibleGraph.html        (original)
+++ trunk/libs/graph/doc/IteratorConstructibleGraph.html Mon Jun 1 21:27:33 2009
@@ -152,7 +152,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/Monoid.html
==============================================================================
--- trunk/libs/graph/doc/Monoid.html    (original)
+++ trunk/libs/graph/doc/Monoid.html    Mon Jun  1 21:27:33 2009
@@ -113,7 +113,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/acknowledgements.html
==============================================================================
--- trunk/libs/graph/doc/acknowledgements.html  (original)
+++ trunk/libs/graph/doc/acknowledgements.html  Mon Jun  1 21:27:33 2009
@@ -67,7 +67,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/adjacency_list.html
==============================================================================
--- trunk/libs/graph/doc/adjacency_list.html    (original)
+++ trunk/libs/graph/doc/adjacency_list.html    Mon Jun  1 21:27:33 2009
@@ -1125,7 +1125,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/adjacency_list_traits.html
==============================================================================
--- trunk/libs/graph/doc/adjacency_list_traits.html     (original)
+++ trunk/libs/graph/doc/adjacency_list_traits.html     Mon Jun  1 21:27:33 2009
@@ -149,7 +149,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/bellman_visitor.html
==============================================================================
--- trunk/libs/graph/doc/bellman_visitor.html   (original)
+++ trunk/libs/graph/doc/bellman_visitor.html   Mon Jun  1 21:27:33 2009
@@ -102,7 +102,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/betweenness_centrality.html
==============================================================================
--- trunk/libs/graph/doc/betweenness_centrality.html    (original)
+++ trunk/libs/graph/doc/betweenness_centrality.html Mon Jun 1 21:27:33 2009
@@ -297,7 +297,7 @@
 <TR valign=top>
 <TD nowrap>Copyright &copy 2004</TD><TD>
<A HREF="http://www.boost.org/people/doug_gregor.html";>Douglas Gregor</A>, Indiana University (dgregor@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</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>

Modified: trunk/libs/graph/doc/bfs_visitor.html
==============================================================================
--- trunk/libs/graph/doc/bfs_visitor.html       (original)
+++ trunk/libs/graph/doc/bfs_visitor.html       Mon Jun  1 21:27:33 2009
@@ -119,7 +119,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/bgl_named_params.html
==============================================================================
--- trunk/libs/graph/doc/bgl_named_params.html  (original)
+++ trunk/libs/graph/doc/bgl_named_params.html  Mon Jun  1 21:27:33 2009
@@ -87,7 +87,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/circle_layout.html
==============================================================================
--- trunk/libs/graph/doc/circle_layout.html     (original)
+++ trunk/libs/graph/doc/circle_layout.html     Mon Jun  1 21:27:33 2009
@@ -45,7 +45,7 @@
 <TR valign=top>
 <TD nowrap>Copyright &copy 2004</TD><TD>
<A HREF="http://www.boost.org/people/doug_gregor.html";>Douglas Gregor</A>, Indiana University (dgregor -at- cs.indiana.edu</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (lums -at- osl.iu.edu)
 </TD></TR></TABLE>
                            </body></html>

Modified: trunk/libs/graph/doc/compressed_sparse_row.html
==============================================================================
--- trunk/libs/graph/doc/compressed_sparse_row.html     (original)
+++ trunk/libs/graph/doc/compressed_sparse_row.html     Mon Jun  1 21:27:33 2009
@@ -204,13 +204,13 @@

<i>// <a href="#incremental-construction-functions">Incremental construction functions</a></i>
 template&lt;typename Graph&gt;
-vertex_descriptor <a href=#add_vertex">add_vertex</a>(compressed_sparse_row_graph&amp; g); +vertex_descriptor <a href="#add_vertex">add_vertex</a>(compressed_sparse_row_graph&amp; g);

 template&lt;typename Graph&gt;
-vertex_descriptor <a href=#add_vertices">add_vertices</a>(vertices_size_type count, compressed_sparse_row_graph&amp; g); +vertex_descriptor <a href="#add_vertices">add_vertices</a>(vertices_size_type count, compressed_sparse_row_graph&amp; g);

 template&lt;typename Graph&gt;
-edge_descriptor <a href=#add_edge">add_vertices</a>(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph&amp; g); +edge_descriptor <a href="#add_edge">add_vertices</a>(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph&amp; g);

 } <i>// end namespace boost</i>
    </pre>
@@ -713,7 +713,7 @@
 <TD nowrap>Copyright &copy; 2005</TD><TD>
<A HREF="http://www.boost.org/people/doug_gregor.html";>Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br> Jeremiah Willcock, Indiana University (<script language="Javascript">address("osl.iu.edu", "jewillco")</script>)<br>
-  <A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+  <A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
 </TD></TR></TABLE>
   </body>

Modified: trunk/libs/graph/doc/constructing_algorithms.html
==============================================================================
--- trunk/libs/graph/doc/constructing_algorithms.html   (original)
+++ trunk/libs/graph/doc/constructing_algorithms.html Mon Jun 1 21:27:33 2009
@@ -174,7 +174,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/default.css
==============================================================================
--- trunk/libs/graph/doc/default.css    (original)
+++ trunk/libs/graph/doc/default.css    Mon Jun  1 21:27:33 2009
@@ -1,7 +1,7 @@
 /*
 :Author: David Goodger
 :Contact: goodger@xxxxxxxxxxxxxxxxxxxxx
-:date: $Date: 2006-11-03 13:55:11 -0500 (Fri, 03 Nov 2006) $
+:date: $Date: 2006-11-03 14:55:11 -0400 (Fri, 03 Nov 2006) $
 :version: $Revision: 35824 $
 :copyright: This stylesheet has been placed in the public domain.


Modified: trunk/libs/graph/doc/depth_first_search.html
==============================================================================
--- trunk/libs/graph/doc/depth_first_search.html        (original)
+++ trunk/libs/graph/doc/depth_first_search.html        Mon Jun  1 21:27:33 2009
@@ -305,7 +305,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/dfs_visitor.html
==============================================================================
--- trunk/libs/graph/doc/dfs_visitor.html       (original)
+++ trunk/libs/graph/doc/dfs_visitor.html       Mon Jun  1 21:27:33 2009
@@ -102,7 +102,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/dijkstra_visitor.html
==============================================================================
--- trunk/libs/graph/doc/dijkstra_visitor.html  (original)
+++ trunk/libs/graph/doc/dijkstra_visitor.html  Mon Jun  1 21:27:33 2009
@@ -116,7 +116,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/distance_recorder.html
==============================================================================
--- trunk/libs/graph/doc/distance_recorder.html (original)
+++ trunk/libs/graph/doc/distance_recorder.html Mon Jun  1 21:27:33 2009
@@ -167,7 +167,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/edge_list.html
==============================================================================
--- trunk/libs/graph/doc/edge_list.html (original)
+++ trunk/libs/graph/doc/edge_list.html Mon Jun  1 21:27:33 2009
@@ -212,7 +212,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/erdos_renyi_generator.html
==============================================================================
--- trunk/libs/graph/doc/erdos_renyi_generator.html     (original)
+++ trunk/libs/graph/doc/erdos_renyi_generator.html     Mon Jun  1 21:27:33 2009
@@ -144,7 +144,7 @@
 <TR valign=top>
 <TD nowrap>Copyright &copy 2005</TD><TD>
<A HREF="http://www.boost.org/people/doug_gregor.html";>Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
-  <A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+  <A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
 </TD></TR></TABLE>


Modified: trunk/libs/graph/doc/filtered_graph.html
==============================================================================
--- trunk/libs/graph/doc/filtered_graph.html    (original)
+++ trunk/libs/graph/doc/filtered_graph.html    Mon Jun  1 21:27:33 2009
@@ -526,7 +526,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/graph_coloring.html
==============================================================================
--- trunk/libs/graph/doc/graph_coloring.html    (original)
+++ trunk/libs/graph/doc/graph_coloring.html    Mon Jun  1 21:27:33 2009
@@ -182,7 +182,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

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       Mon Jun  1 21:27:33 2009
@@ -1,460 +1,451 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html><head><meta content="text/html; charset=UTF-8" http-equiv="content-type"><!--
+<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>

-
-  <title>Boost Graph Library: Graph Theory Review</title></head>
+<H1>Review of Elementary Graph Theory</H1>

-<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b">
-
-
-<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
-
-<br clear="">
-
-
-
-<h1>图论基础复习<br>
-</h1>
-
-
-
-<p>
-
-</p>
-
-<p>本章将复习一下图论的基本理论。如果读者以前接触过图算法,那么可以便可以马 上开始本章的学习;如果读者以前没有相关图算法背景知识,我们建议最好还是对其有 一个了解,可以去看Cormen, Leiserson, 和Rivest写的<a href="http://toc.lcs.mit.edu/%7Eclr/";>Introduction to Algorithms</a>(《算法 导论》)。
+<P>

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

-</p>
+<H1>The Graph Abstraction</H1>

-<h1>图简介<br>
-</h1>
-图是用来解决各种实际问题的数学抽象。从根本上说,一个图是由一组顶点集合和一 组边集合组成的,其中,一条边连接图中两个顶点。更准确的描述是,一个组是 -一个(V,E)对,V是一个有限集,e是表示V的二元关系。V被称作顶点集,其中的元素 统称为vertices。E是边的集合,一条边是一个(u,v) -对,u,v分别是顶点集V中的元素。在一个有向图中,边是一个连接源点和目标点的有 序对。在一个无向图中,边是一个无序对,仅仅连接两个顶点,因此五项途
-中(u,v)和(v,u)含义相同。<br>
-<br>
-<br>
-以上对于图的定义在某些方面有点含糊不清,例如,没有说清顶点和边到底表示什 么。他们可能是城市和连接城市的公路;亦或是网页和链接网页的超链接。这些细 -节不被考虑到定义中是有原因的,它们不属于图抽象的部分。通过省略这些细节,我 们能够建立一个可复用的原理,它能够帮我们解决各种不同的问题。<br>
-<br>
-<br>
-切回到我们的定义:图是一组顶点和边的集合。演示一下,我们来建立一个图,该图 顶点已经用字母标好,因此边可以简单的写成一个字母对。现在我们可以写出一个有向 图,如下:<br>
-<div align="center">
-<table>
+<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.

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

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

-      <td><tt>
+<P>
+<BR>
+<DIV ALIGN="center">
+<table><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>
-
-
-  </tbody>
-</table>
-
-
-</div>
-
-
-<br clear="all">
-
-<p></p>
-
-
-
-
-<p>
-<a href="#fig:directed-graph">图一</a> 是该图的图示版。边(x,x)叫做闭包。 边(b,y)和另一条(b,y)边是平行边,平行变仅仅出现在多重图中(一般有向图和 无向图是不允许出现的)。
-
-</p>
-
-<p>
-
-</p>
-
-<p></p>
-
-
-<div align="center"><a name="fig:directed-graph"></a><a name="1509"></a>
-<table>
-
-
-  <caption align="bottom"><strong>图 1:</strong>
-一个有向图的例子</caption>
-  <tbody>
-
-    <tr>
+</tt></td></tr></table>
+</DIV>
+<BR CLEAR="ALL"><P></P>

-      <td><img src="./figs/digraph.gif" height="163" width="124"></td>

-    </tr>
-
-
-
-  </tbody>
-</table>
-
-
-</div>
+<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>
-下面我们将演示一个与图一相似的图,不过这次是无向的。<a href="graph_theory_review.html#fig:undirected-graph">图二</a>是该图的图示。 闭包是不允许出现在无向图中的。该图是边(b,y)的无向版本,相同的顶点和去除方 向的边。相同的边被删除,有些边被合并,比如(a,z)和(z,a)。无向图的有向版 本是把其中每条边换成两条,每一条指向一个方向。<br>
-<div align="center">
-<table>
+<P>

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

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

-      <td><tt>
+<P>
+<BR>
+<DIV ALIGN="CENTER">
+<table><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>
-
-
-  </tbody>
-</table>
-
-
-</div>
-
-
-<a name="def:directed-version"><br clear="all">
-
-</a>
-<p></p>
-
-
-
-<p>
-
-</p>
-
-<p></p>
-
-
-<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>
-现在开始讲讲图的专业术语吧。如果边(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的入边。在 &nbsp;<a href="graph_theory_review.html#fig:undirected-graph">图二 </a>中,y是b的临界点,反之亦然。边(y,b)是与y和b关联的。<br>
-<br>
-</p>
-在有向图中,一个顶点出边的数量叫做该点的出度,入边的数量叫做该点的入度。无 向图中,点关联的边的数量叫做该点的度。在<a href="graph_theory_review.html#fig:directed-graph">图一</a>中,顶点的出度是 3,入度是0。在<a href="graph_theory_review.html#fig:undirected-graph">图二 </a>中,顶点b仅仅是度为2。<br>
-<br>
-<br>
-路径是图中边的序列,该序列中,每条边的目标顶点是下一条边的源顶点。如果一条 路径起始于顶点u终止于顶点v,那么我们便说v是从u可到达的。如果一条路 -径中没有重复顶点,我们便称该路径是简单的。路径&lt;(b,x),(x,v)&gt;是简单 的,但是&lt;(a,z),(z,a)&gt;不是。路 -径&lt;(a,z),(z,a)&gt;叫做环,因为路径中起点和终点是同一个点。一个没有环的图 被称作无环的。<br>
-<br>
-<br>
-可平面图是一个图能够被画到一个平面上,并且其中没有边相互交叉。能够用上面方 法画出的图叫做平面图。一个平面图的面是被边环绕的平面的连通区域。可平面 -图的一个重要性质是:面、边和顶点的数量关系遵循欧拉公式:|F|-|E|+|V|=2。这意 味着简单的可平面图最多有O(|V|)条边。<br>
-<p>
-
-</p>
-
-<h1>图相关数据结构<br>
-</h1>
-在图中,考虑使用什么数据结构时,最重要的一个属性是稀疏性,稀疏性指边的数量 相对于点的数量。一个图中,边的数量接近于顶点平方,该图是稠密图,反之, -一个图中E=α×V,并且α比V小得多的时候称该图为稀疏图。表示稠密图,邻接矩阵表示 法是最佳选择;邻接列表表示 -法是稀疏图的最佳选择。某些情况下,对于稀疏图,边-表表示法在空间效率选择上更 加合适。<br>
-<h2>邻接矩阵表示法<br>
-</h2>
-
-
-
-<p>图的邻接矩阵表示的就是一个V×V的2维数组。数组中的每一个元素auv存储一个布 尔值,该值表示边(u,v)是否出现在图中。<a href="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)。&nbsp;<a href="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>
-
-<p></p>
-
-
-
-<p>
-
-</p>
-
-<h2><a name="sec:adjacency-list-representation"></a>&nbsp;邻接表表示法
-</h2>
-
-
-
-<p>图的邻接列表表示的是每个顶点的出边序列。对于一个稀疏图来讲,该表示法节省 了空间,因为仅需了O(V + -E)大小的内存。而且,访问顶点出边更加有效率。边得插入操作复杂度是O(1),但是 访问制定边的效率是O(α),α表示矩阵的 -稀疏因子(稀疏因子等于最大的顶点出度)。<a href="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> 类是邻接列表表示 法的一个实现。<br>
-<br>
-</p>
-<p></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>
-
-<p></p>
-
-
-
-<p>
-
-</p>
-
-<h2>边列表表示法<br>
-</h2>
-
-
-
-<p>图的边列表表示就是一个边的序列,其中每条边使用一个顶点ID对来表示的。该表 示法仅需要O(E)大小的内存。边插入复杂度是O(1),但是访问一个指定边的复杂度是 O(E)(效率低下)。<a href="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>
-
-<p></p>
-
-
-
-
-<p>
-
-</p>
-
-<h1>图相关算法<br>
-</h1>
-
+</tt></td></tr></table>
+</DIV>
+<BR CLEAR="ALL"><P></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>
+<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>.

-<h2>图搜索算法<br>
-</h2>
+<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 href="visitor_concepts.html"> visitor </a>的explore -()方法)(u,v)时,点v首先被遍历到,那么边(u,v)就是一条树边。在搜索树 中,后向边连接顶点到他们的祖先。所以边(u,v)中,点v一定是点 -u的祖先。闭包被认为是反向边。前向边是非树边,搜索树中(u,v)连接点u到它的 子孙节点v。交叉边是不属于前面三种定义的边。<br>
-<i></i></p>
-<br>
-<h2><a name="sec:bfs-algorithm"></a> 广度优先搜索</h2>
+<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>

-<p>广度优先搜索(BFS)是指从某点开始遍历整张图,遍历顺序是首先遍历该点的邻 居结点会,然后是它邻居节点的邻居节点优先遍历到,直至遍历完整张 -图。可以把深度优先遍历想像成石子落入水中时激起的涟漪,在相同波浪的顶点和源 点的距离是相同的。发现点是该算法浏览时首先遇到的点,结束点是遍历完它所 -有邻居的最后一个点。下面有一个例子将帮助你理解。<a href="graph_theory_review.html#fig:bfs-example">图六</a>中展示了一幅图,并且 在图下面列出了BFS(深度优先算法)的算法中顶点的发现和结束顺序。</p>
-<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.

-<div align="center"><a name="fig:bfs-example"></a><a name="1826"></a>
-<table>
+<P>

+<H2>Adjacency Matrix Representation</H2>

- <caption align="bottom"><strong>图 6:</strong> 图遍历的广度优先搜索 </caption>
-  <tbody>
+<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.

-    <tr>

-      <td><img src="./figs/bfs_example.gif" height="143" width="242"></td>
+<P>

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

-
-  </tbody>
-</table>
+<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.

-</div>
+<P>

-<p></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>
-</p>
+<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.

-<pre> order of discovery: s r w v t x u y <br> order of finish: 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。 -<p>为了能够知道我们在图中的位置以及知道将要访问的下一个点,BFS算法需要对顶 点进行染色(color)(请参考 <a href="using_property_maps.html">Property Maps</a>一节来了解更多关于图属性的细节)。颜色值既可以放在图结构内,也可以作 为算法的参数传进去。<br>
-</p>
-<br>
-<h2><a name="sec:dfs-algorithm"></a> 深度优先搜索
-</h2>
-<br>
-深度优先搜索(DFS)访问图中所有顶点的方法是,我们依据边来进行遍历,该算法会 始终选择图中较深一层的边来遍历。也就是说,DFS会首先访问它未被访 -问的邻接顶点,然后邻接顶点访问该邻接顶点的邻接顶点,直到一点没有邻接顶点 时,再回溯到前面顶点继续沿着未被访问的边来遍历顶点。DFS算法从一点遍历 -完所有能够到达的顶点后,它将选择仍未被发现的顶点来进行搜索。搜索的过程建立 了一组深度优先树(depth-first
-trees),这些树合起来就成了深度优先森林(depth-first
-forest)。DFS把图中的边分为三类:树边,反向边和正向边(或称交叉边)。根据一 些典型的深度优先森林,边还有一些其它的分类方法。<br> -<p>DFS一个比较有意思的特性是按点的发现和结束顺序插入到括号中,方法是:把发 现一点放到左括号,把结束一点放到右括号,最后形成了一个嵌套的括号集合。<a href="graph_theory_review.html#fig:dfs-example">图七</a>展示了DFS对于一个无 向图的应用,该图边上已经标好了遍历的顺序。下面我们列出了发现和结束的顺序,以 及嵌套的括号集合。DFS是其他一些算法的核心,比如托普排序和连通分量算法。DFS算 法还能检测是图中是否存在环(参考文件依赖例子中的<a href="file_dependency_example.html#sec:cycles">Cylic Dependencies</a>(循环 依赖)一节)。<br>
-</p>
+<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>

-<div align="center"><a name="fig:dfs-example"></a><a name="1841"></a>
-<table>

+<P>

-  <caption align="bottom"><strong>图 7:</strong>
-无向图的深度优先搜索</caption>
-  <tbody>
+<H1>Graph Algorithms</H1>

-    <tr>
+<P>

-      <td><img src="./figs/dfs.gif" height="204" width="141"></td>
+<H2>Graph Search Algorithms</H2>

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

-
-  </tbody>
-</table>
+<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.

-</div>
+<P>

-<p></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>
-</p>
+<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.

-<pre> order of discovery: a b e d c f g h i<br> order of finish: d f c e b a<br> parenthesis: (a (b (e (d d) (c (f f) c) e) b) a) (g (h (i i) h) g)<br></pre>
+<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>
+<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 parenthesis structure. 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>

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

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

-<br clear="all">
+<H2><a name="sec:minimum-spanning-tree">Minimum Spanning Tree Problem</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>.

-这样的T称为最小生成树。&nbsp;<!--
+<!--
 <P>
 Kruskal's algorithm&nbsp;[<A
  HREF="bibliography.html#kruskal56">18</A>]
@@ -471,143 +462,129 @@
  with the appropriate choice of comparison and combine functors.
 -->

-<p>
-
-</p>
-
-<h2><a name="sec:shortest-paths-algorithms">最短路径算法</a></h2>
-图论中的一个经典问题是找出两点之间的最短路径。在图G中,一条路径是一个顶点序 列&lt;v0,v1,....,Vk&gt;,使得序列中的每个顶点都 -和下一个顶点相连(边(vi,vi+1)i=0,1,....k属于边集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>
+<P>

+<H2><a name="sec:shortest-paths-algorithms">Shortest-Paths Algorithms</a></H2>

-<br clear="all">
+<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 <i>&lt;v<sub>0</sub>,v<sub>1</sub>,...,v<sub>k</sub>&gt;</i>
+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>

 <p></p>
-顶点u到v的最短路径的权值是:<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 --&gt; v }</i> if there is a path from
+<DIV ALIGN="left">
+<i>delta (u,v) = min { w(p) : u --> v }</i> if there is a path from
 <i>u</i> to <i>v</i> <br>
-
-
 <i>delta (u,v) = infinity</i> otherwise.
-</div>
+</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>.

-<br clear="all">
-
-<p></p>
-最短路径可以是权值等于最短路径权值的任何一条路径。<br>
-<br>
-<br>
-还有一些最短路径的衍生问题。上面我们定义了single-pair问题,但是还有一个 single-source问题,该问题等效于单目标single --destination问题和all-pairs问题。没有解决single-pair问题比解决 single-source问题还快的算法。<br>
-<br>
-<br>
-在图G=(V,E)中,以某点为根的最短路径树是该图的一个有向子图G'=(V',E'),其中 V'是V的子集,E'是E的子集,而且V'还是该点能够到 -到达顶点的集合。G'是一颗以顶点为根的有根树,因而,从V'中一点v到G'中一点u的 唯一简单路径就是从v到u的最短路径。single-source
-算法的结果就是一颗最短路径树。<br>
-<h2><a name="sec:network-flow-algorithms">网络流算法</a></h2>
-
+<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>
-<a name="sec:network-flow-algorithms">一个网络流是一个以顶点s为源点,以顶点 t为接受点的有向图G=(V,E)。每条边e均具有一个非负容量(capacity )c(e)而且每个 顶点对还有一个流f(e)。流一定要满足下面三个条件:
+<P>

-</a></p>
+<H2><a name="sec:network-flow-algorithms">Network Flow Algorithms</H2>

 <p>
-<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):f(u,v) = 0<br>
-</i>
-
-</a></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:

 <p>
-<a name="sec:network-flow-algorithms">网络流是指流向接收点t的流(等效于流出 源点s的流)。</a></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>
+<i>sum<sub>v in V</sub> f(u,v) = 0 for all u in V - {s,t}</i> (Flow conservation)

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

-<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>
+<i>|f| = sum<sub>u in V</sub> f(u,t) = sum<sub>v in V</sub> f(s,v)</i>

 <p>
-<a name="sec:network-flow-algorithms">一条边的剩余容量为:r(u,v) = c(u,v) - f(u,v)。如果r(u,v)&gt;0则该边是有余量的,包含该边的图为有余量图。如果 r(u,v)=0,则该边为饱和的。
-
-</a></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>.

 <p>
-<a name="sec:network-flow-algorithms">最大流问题是指确定|f|的最大值和图中每 个顶点对相应的流是多少。
-
-</a></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.

 <p>
-<a name="sec:network-flow-algorithms"> </a><a href="graph_theory_review.html#fig:max-flow">图八</a><a name="sec:network-flow-algorithms">表示一个流网络,顶点A为源点,顶点H为终 点。</a>
-
-</p>
-
-<p></p>
-
-
-<div align="center"><a name="fig:max-flow"></a><a name="1509"></a>
-<table>
-
-
- <caption align="bottom"><strong>Figure 8:</strong>&nbsp;一个最大流网络 <br>
-边已经被标上流和容量值</caption>
-  <tbody>
-
-    <tr>
-
-      <td><img src="./figs/max-flow.gif" height="240" width="578"></td>
-
-    </tr>
-
-
-
-  </tbody>
-</table>
+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>

-</div>
-
-<p></p>
-<p>解决最大流问题算法已经有很长历史了,首先提出解决该问题的算法是&nbsp; <a href="bibliography.html#ford56:_maxim">Ford 和 Fulkerson</a>.对于数据最通用 的算法是<a href="bibliography.html#goldberg85:_new_max_flow_algor">Goldberg</a>提出的 push-relabel算法,该算法基于<a href="bibliography.html#karzanov74:_deter">Karzanov</a>提出的前向(preflow)概 念。</p>
-
-
-
-
-<hr>
-<table>
-
-
-  <tbody>
-
-    <tr valign="top">
-
-
-      <td nowrap="nowrap">Copyright © 2000-2001</td>
-
-      <td>
- <a href="../../../people/jeremy_siek.htm">Jeremy Siek</a>, Indiana University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)
-      </td>
-
-    </tr>
-
-
-  </tbody>
-</table>
+<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>
\ No newline at end of file
+</BODY>
+</HTML>

Modified: trunk/libs/graph/doc/graph_traits.html
==============================================================================
--- trunk/libs/graph/doc/graph_traits.html      (original)
+++ trunk/libs/graph/doc/graph_traits.html      Mon Jun  1 21:27:33 2009
@@ -243,7 +243,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/gursoy_atun_layout.html
==============================================================================
--- trunk/libs/graph/doc/gursoy_atun_layout.html        (original)
+++ trunk/libs/graph/doc/gursoy_atun_layout.html        Mon Jun  1 21:27:33 2009
@@ -454,7 +454,7 @@
 <TD nowrap>Copyright &copy; 2004</TD><TD>
Jeremiah Willcock, Indiana University (<script language="Javascript">address("osl.iu.edu", "jewillco")</script>)<br> <A HREF="http://www.boost.org/people/doug_gregor.html";>Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
-  <A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+  <A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
 </TD></TR></TABLE>


Modified: trunk/libs/graph/doc/history.html
==============================================================================
--- trunk/libs/graph/doc/history.html   (original)
+++ trunk/libs/graph/doc/history.html   Mon Jun  1 21:27:33 2009
@@ -1,223 +1,208 @@
-<!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) --><title>Boost Graph Library: History</title>
-
-</head>
-
-<body style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255);" alink="#ff0000" link="#0000ee" vlink="#551a8b"> -<img src="../../../boost.png" alt="C++ Boost" height="86" width="277"> <br clear="">
-<h1>Boost图库的历史</h1>
-Boost图库最开始是作为通用图组件库(GGCL)出现的,它是Notre Dame大学&nbsp;<a href="http://www.lsc.nd.edu";>科学计算实验室 (LSC)</a> 由 <a href="http://www.osl.iu.edu/%7Elums";>Andrew Lumsdaine</a> -教授带领的一个项目。该实验室的研究方向还包括:数值线性代数,并行计算,以及 软件工程(包括范型编程)。 -<p>标准模版库出现后不久,LSC实验室就开始采用范型编程来进行科学计算。<a href="http://www.lsc.nd.edu/research/mtl";>矩阵模版库(Matrix
-Template Library</a>&nbsp;(Jeremy
-Siek的硕士学位论文)就是最早采用范型编程的项目之一。同时,构建MTL过程中的一 些经验被引入到GGCL的设计和实现当中。
-</p>
-<p>由于图算法在稀疏矩阵计算当中起着非常重要的作用,所以LSC需要一个优秀的图 库。然而,没有一个图库(LEDA, GTL,
-Stanford
-GraphBase)是用STL的范型编程风格去写的,并且已有库也不能很好的适应LSC对于灵 活和高性能方面的需求。另外也有一些人非常需要用C++实
-现的范型库。在一次会议期间Bjarne
-Stroustrup被介绍给了一些需要这些库的人。其实在范型图算法方面已经做了一些前 期工作,比如Alexander
-Stepanov写的一些代码,以及Dietmar Kühl的硕士论文。
-</p>
-<p>在这种思想的驱动下,同时为了完成算法课的作业,Jeremy于1998年春开始一套实 现接口原型和一些图相关类了。随后,Lie-
-Quan Lee开发了GGCL的第一个版本,并且该项目作为他的硕士论文项目。
-</p>
-<p>接下去的一年,Jeremy和Alexander Stepanov 以及Matt
-Austern一起到了SGI工作。其间Alex的基于连通分支的不相交集合算法被加入到 GGCL中,并且Jeremy开始给GGCL的概念文档了,该文
-档类似于Matt给STL写的文档。
-</p>
-<p>在SGI工作期间,Jeremy听说了Boost并且找到了一群对创造一套高质量C++库感兴 趣的人。Boost成员中,有很多人对泛
-型图算法都很
-感兴趣,最有名的是Dietmar
-Kühl。关于图结构的范型接口的一些论述被加入到了GGCL中,它们已经很像现在的 Boost图库接口了。
-</p>
-<p>在2000年9月4日,GGCL通过了Boost的正式评审并且成为了Boost图库(BGL)。 BGL的第一个发行版是2000年9
-月27日发行的。
-</p>
-<h2>版本变更</h2>
+<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>
 <a name="by-version">
-</a>
-<ul>
-<a name="1.35.0"></a><li>Version 1.35.0<br><b>New algorithms and components</b>
-<ul>
-<li><a href="kolmogorov_max_flow.html"><tt>kolmogorov_max_flow</tt></a>, from Stephan Diederich as part of the <a href="http://code.google.com/soc/";>2006 Google Summer of Code</a>.</li> -<li><a href="read_dimacs.html">read_dimacs_max_flow</a> and <a href="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 <a href="write_graphml.html">write_graphml</a> for <a href="http://graphml.graphdrawing.org/";>GraphML</a> input/output, from Tiago 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 Andrey Parfenov.</li> -<li><a href="boyer_myrvold.html"><tt>boyer_myrvold_planarity_test</tt></a>, along with a suite of <a href="planar_graphs.html">algorithms for planar graphs</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="by-version"> </a><a name="1.34.1"></a><li>1.34.1
-版<br>
-<b>BUG修复</b><br>
-<ul>
-<li><a href="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><a href="maximum_matching.html"><tt>edmonds_maximum_cardinality_matching</tt></a>,&nbsp;
-Aaron Windsor 提供</li>
-<li><a href="lengauer_tarjan_dominator.htm"><tt>lengauer_tarjan_dominator_tree</tt></a>,&nbsp;JongSoo
-Park&nbsp;提供</li>
-<li><a href="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a>,
-印第安纳大学的Jeremiah Willcock 和 Douglas Gregor提供</li>
-<li><a href="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><a href="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>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&lt; </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 x86
-Linux.</li>
-<li>Bundled properties now work with adjacency list I/O.</li>
-<li><a href="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><a href="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><a href="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 <a href="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><a href="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><a href="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><a href="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a></li>
-<li><a href="plod_generator.html"><tt>plod_iterator</tt></a></li>
-<li><a href="small_world_generator.html"><tt>small_world_iterator</tt></a></li>
-</ul>
-<br>
-<b>Enhancements</b><br>
-<ul>
-<li><a href="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><a href="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths</tt></a> -now uses a relaxed heap&nbsp;[<a href="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><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><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><a href="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 singular iterators.</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><a href="sequential_vertex_coloring.html"><tt>sequential_vertex_coloring</tt></a>
-has been updated, tested, and documented.</li>
-</ul>
-</li>
+ <a name="1.35.0"></a><li>Version 1.35.0<br><b>New algorithms and components</b>
+    <ul>
+ <li><a href="kolmogorov_max_flow.html"><tt>kolmogorov_max_flow</tt></a>, from Stephan Diederich as part of the <a href="http://code.google.com/soc/";>2006 Google Summer of Code</a>.</li> + <li><a href="read_dimacs.html">read_dimacs_max_flow</a> and <a href="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 <a href="write_graphml.html">write_graphml</a> for <a href="http://graphml.graphdrawing.org/";>GraphML</a> input/output, from Tiago 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 Andrey Parfenov.</li> + <li><a href="boyer_myrvold.html"><tt>boyer_myrvold_planarity_test</tt></a>, along with a suite of <a href="planar_graphs.html">algorithms for planar graphs</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&uuml;ller.</li>
+    </ul>
+  </li><br>
+
+  <a name="1.34.1"></a><li>Version 1.34.1</br><b>Bug Fixes</b><br>
+  <ul>
+ <li><a href="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<br><b>New algorithms and components</b>
+    <ul>
+ <li><a href="maximum_matching.html"><tt>edmonds_maximum_cardinality_matching</tt></a>, from Aaron Windsor.</li> + <li><a href="lengauer_tarjan_dominator.htm"><tt>lengauer_tarjan_dominator_tree</tt></a>, from JongSoo Park.</li> + <li><a href="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a>, from Jeremiah Willcock and Douglas Gregor of Indiana University.</li> + <li><a href="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 is now called <code>boost_graph</code> rather than <code>bgl-viz</code>.</li> + <li><a href="biconnected_components.html"><tt>biconnected_components</tt></a> now has a visitor parameter and supports named parameters, from Janusz Piwowarski.</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><a href="adjacency_list.html"><tt>adjacency_list</tt></a> is now <a href="../../serialization/doc/index.html">Serializable</a>, from Jeremy Siek 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 x86 Linux.</li>
+      <li>Bundled properties now work with adjacency list I/O.</li>
+ <li><a href="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><a href="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.
+    </ul>
+    <br>
+  </li>
+
+  <li>Version 1.33.1<br><b>Bug Fixes</b>
+    <ul>
+ <li><a href="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 <a
+ href="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><A href="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><A href="fruchterman_reingold.html"><TT>fruchterman_reingold_force_directed_layout</TT></A>, from Doug Gregor and Indiana University.</a></LI> + <LI><A href="biconnected_components.html"><tt>biconnected_components</tt> and <tt>articulation_points</tt></a>, from Indiana University.</a></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><a href="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a></li>
+      <li><a href="plod_generator.html"><tt>plod_iterator</tt></a></li>
+ <li><a href="small_world_generator.html"><tt>small_world_iterator</tt></a></li>
+    </ul><br><b>Enhancements</b><br>
+    <ul>
+ <li><a href="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><a href="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths</tt></a> now uses a relaxed heap&nbsp;[<A + HREF="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><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><a href="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 singular iterators.</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><a href="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 © 2000-2001</td>
-<td> <a href="../../../people/jeremy_siek.htm">Jeremy
-Siek</a>,
-Indiana University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)<br>
-<a href="../../../people/liequan_lee.htm">Lie-Quan
-Lee</a>, Indiana University (<a href="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</a>)<br>
-<a href="http://www.osl.iu.edu/%7Elums";>Andrew
-Lumsdaine</a>,
-Indiana University (<a href="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</a>)
-</td>
-</tr>
-</tbody>
-</table>
-<!-- LocalWords: gif ALT GGCL LSC Lumsdaine Siek's MTL LEDA GTL GraphBase STL --> -<!-- LocalWords: Bjarne Stroustrup hl's Quan SGI Stepanov Austern Alex's hl --><!-- LocalWords: Dietmar BGL siek htm Univ -->
-</body></html>
\ No newline at end of file
+<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 (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
+Indiana University (<A
+HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
+<!-- LocalWords: gif ALT GGCL LSC Lumsdaine Siek's MTL LEDA GTL GraphBase STL
+ -->
+<!-- LocalWords: Bjarne Stroustrup hl's Quan SGI Stepanov Austern Alex's hl
+ -->
+<!--  LocalWords:  Dietmar BGL siek htm Univ
+ -->

Modified: trunk/libs/graph/doc/incident.html
==============================================================================
--- trunk/libs/graph/doc/incident.html  (original)
+++ trunk/libs/graph/doc/incident.html  Mon Jun  1 21:27:33 2009
@@ -70,7 +70,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/incremental_components.html
==============================================================================
--- trunk/libs/graph/doc/incremental_components.html    (original)
+++ trunk/libs/graph/doc/incremental_components.html Mon Jun 1 21:27:33 2009
@@ -412,7 +412,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/index.html
==============================================================================
--- trunk/libs/graph/doc/index.html     (original)
+++ trunk/libs/graph/doc/index.html     Mon Jun  1 21:27:33 2009
@@ -1,403 +1,302 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html><head><meta content="text/html; charset=UTF-8" http-equiv="content-type"><!--
+<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>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">

-
-
-
-
-  <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="">
-
-
-
+<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 <a href="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&lt;T&gt;</TT>. This hardly scratches
+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 introduces the
+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.
+
+<p>
+
+<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 List Graph</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 (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
+Indiana University (<A
+HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
+</TD></TR></TABLE>

-
-
-<p>在计算机科学中,图是一些用来解决各种问题的数学抽象概念。所以,这些抽象的 概念一定可以用计算机程序表示。一个标准化的用来遍历图的通用接口,对 -于图的算法和数据结构来说是相当重要的。Boost图库中专门有一些用来访问图数据结 构的通用接口,它们隐藏了繁杂的内部实现。这是一套开放的接口,一些 -用其它图库实现的接口也能够使用BGL中的通用算法,而且这套接口也能使用BGL中其 它算法。BGL提供了一些遵照这套接口的通用类,但是不要以为这是唯 -一的图形类;BGL中当然还有一些能够更好解决特定问题的类。我们相信BGL最大的贡 献就是规范话了这套接口。
-</p>
-
-
-<p>与STL[<a href="bibliography.html#austern99:_gener_progr_stl">2</a>]相类 似,BGL中的接口和组件也是范型的。接下来的几节,我们将回顾一下范型编程在STL中 扮演的角色,以及比较一下我们如何把范型编程应用到图的环境中。&nbsp;
-
-</p>
-
-
-<p>
-当然如果你已经对范型编程很熟悉了那么请跳到<a href="table_of_contents.html">目录</a>继续阅读下面章节。
-
-</p>
-
-
-<p>
-BGL的源代码是随着Boost一起发布的,到这<a href="http://sourceforge.net/project/showfiles.php?group_id=7586";>下载</a>。
-
-</p>
-
-
-<h2>如何编译BGL<br>
-
-
-</h2>
-
-
-
-<p><span style="font-weight: bold;">不能!</span>Boost图库仅仅是一些头文 件,所以不需要编译。唯一的例外是: <a href="read_graphviz.html">GraphViz input parser</a>。</p>
-
-
-当编译的时候,<span style="font-weight: bold;">别忘了开启编译优化选项 </span>。比如,在Ms Visual C++中选择“Release”模式;在GCC中使用-o2或者-o3标 志。
-<h2>STL中的范型<br>
-
-
-</h2>
-
-
-
-
-<p>STL中用三中方法来实现范型化
-</p>
-
-
-<p>
-
-</p>
-
-
-<h3>算法/数据结构互通性<br>
-
-
-</h3>
-
-
-
-
-<p>首先,每一个算法都是用数据结构无关的方法写出的,允许一个单独的函数模版处 理多种不同容器类。迭代器的概念是实现算法和数据结构解藕的关键因素。 -这个方法最明显的效果就是缩小的STL的代码尺寸,使其从O(M*N)变成了O(M+N),其中 M是算法个数,N是容器个数。试想,如果有20个算法、5 -个数据结构,采用范型编程与不采用的区别是:由写100个函数编程写25个函数!随着 算法和数据结构数量的增加这个差距会越来越大。</p>
-
-
-<p>
-
-</p>
-
-
-<h3>通过函数对象扩展<br>
-
-
-</h3>
-
-
-STL范型化的第二种方法是算法和容器可扩展。用户能够通过函数对象改写和定制 STL。这样的灵活性使STL成为解决现实问题的有利工具。每一个编程问题对应它自己的 一组实体和被规范化的接口。函数对象提供了一种机制,它能够对STL扩充以处理特定 领域问题的。
-<h3>元素类型参数化<br>
-
-
-</h3>
-
-
-STL范型化的第三种方法使参数化元素类型。相对于其它两种方法,STL中使用这种方 法的次数比较少。范型编程中经常简写参数化列表,例如:std::list&lt;T&gt;。以上 仅仅是范型编程的冰山一角。
-<h2>Boost图库中的范型
-</h2>
-
-
-
-
-<p>与STL一样,BGL中也有3种范型方法
-</p>
-
-
-<p>
-
-</p>
-
-
-<h3>算法/数据结构互通性<br>
-</h3>
-
-
-
-
-<p>第一种,BGL中的图算法被写成了一种把具体数据结构细节抽象出来的接口。与 STL相同,BGL也是用迭代器(iterator)来定义遍历相关数 -据结构的接口。有3种完全不同的遍历模式:遍历图中所有的点,遍历图中所有的 边,以及沿相邻结构进行遍历(从一丁点到它的每一相邻顶点)。每一种遍历方式
-需要一种迭代器。<br>
-</p>
-
-
-<p>这种范型接口能够使模版函数(例如:&nbsp;<a href="./breadth_first_search.html"><tt>breadth_first_search()</tt></a> -函数)接受各种图数据结构,从链表表示的图到数组表示的图都可以。在图领域这种 灵活性是相当重要的。图数据结构经常为了某些特殊需求而定制。传统上,如果 -程序员想要复用一个算法,他们一定要把自己的数据结构进行转换(或拷贝)成图库 的规定数据结构才行。比如LEDA,GTL,Stanford -GraphBase就是这种情况;特别是用Fortan写成的图算法更需要这种转换。这种转换严 格的限制了图算法的复用性。
-</p>
-
-
-
-
-<p>与之相反,定制的图数据结构能够被BGL中的范型算法统一对待,BGL使用一种叫做 外部适配(external adaptation)(参考<span style="text-decoration: underline;"> </span><a href="./leda_conversion.html">如何把非BGL图转换到 BGL中</a>一 -节)的方法来实现该技术。外部适配封装了一个新的接口,使数据结构不用进行拷 贝,也不用替换内部适配对象。BGL相关接口使这种转换变得很容易。举个来
-说,在BGL中,我们已经用各种图数据结构(比如:LEDA图,Stanford
-GraphBase图,甚是还有Fortan风格的数组)建立了一套接口。
-</p>
-<p>
-
-</p>
-
-
-<h3>用遍历器(vistitor)进行扩展</h3>
-
-
-
-
-<p>第二种,BGL中的图算法是可扩展的。BGL引入了遍历器(visitor)的概念,遍历 器就是一个有多个方法的功能实体。在图算法中,经常会有几 -个关键的“事件点”使用户插入一些操作。在每个“事件点”,遍历器对象会有不同的方 法被调用。 -“事件点”以及对应的遍历器方法都依赖于相应的算法。遍历器经常包括的方法 有:<br> -start_vertex(), discover_vertex(), examine_edge(), tree_edge(), 以及 finish_vertex().
-
-</p>
-
-
-<p>
-
-</p>
-
-
-<h3>点、边属性多重参数化</h3>
-
-
-
-
-<p>BGL中的第三种范型方法与STL容器中的元素类型参数化相似,虽然这点对于图来说 有些复杂。我们需要给图的边、点赋予相关含义(属性)。另外,有
-时候需要给各个点、边赋予多重属性;这意味这需要多重参数化。STL的
-std::list&lt;T&gt;类有一个参数T作为它的元素类型。类似,BGL中的图类也有模版 参数作为边、点的属性。一个属性详细说明了该属性的 -参数类型,并且分配了标识该属性的标签。标签用来区分边或点的多重属性。与特性 点或边相对应的属性能够通过属性映射(property
-map)获得。每一个属性有一个单独的属性映射。
-
-</p>
-
-
-<p>传统的图库和图数据结构在图属性参数化方面做的不是很好。这也是图数据结构一 定要为应用定制的主要原因。BGL中的属性参数化能够使BGL中的图类很好的复用。
-
-</p>
-
-
-<p>
-
-</p>
-
-
-<h2>算法</h2>
-
-
-
-
-<p>BGL中的算法由一组核心算法模型(用范型算法实现)和一组较大的图算法组成。 核心算法模型是:
-
-</p>
-
-
-<p>
-
-</p>
-
-
-<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>
-
-
-
-
-<p>
-
-</p>
-
-
-<h2>数据结构</h2>
-
-
-
-
-<p>BGL当前提供2种图类和一个边列表适配器:
-</p>
-
-
-<p>
-
-</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>adjacency_list类好比图类中的“瑞士军刀”。它高度参数化,以致于能够为各种情 况优化,例如:有向图还是无向图,允许还是不允许平行边,仅外边能有效访问还是内 外边都可以,是否以空间为代价进行快速顶点插入或移出,等等。
-
-</p>
-
-
-<p>adjacency_matrix类把边存储在一个|V|x|V|的矩阵中(其中,|V|表示顶点个数 )。矩阵元素表示图中的边。邻接矩阵尤其适合表示稠密图(dense graphs),比 如,有<i>|V|<sup>2</sup></i>条边的图。
-
-</p>
-
-
-<p><br>
-edge_list类是一个能接受任何边迭代器的适配器,实现了一个<a href="./EdgeListGraph.html">边列表图(Edge List Graph</a>)。<br>
-
-
-
-</p>
-
-
-<hr>
-<table>
-
-
-
-  <tbody>
-
-
-    <tr valign="top">
-
-
-
-      <td nowrap="nowrap">Copyright © 2000-2001</td>
-
-
-      <td>
-      <a href="../../../people/jeremy_siek.htm">Jeremy Siek</a>,
-Indiana University (<a href="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</a>)<br>
-
-
-
- <a href="../../../people/liequan_lee.htm">Lie-Quan Lee</a>, Indiana University (<a href="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</a>)<br>
-
-
-
-      <a href="http://www.osl.iu.edu/%7Elums";>Andrew Lumsdaine</a>,
-Indiana University (<a href="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</a>)
-      </td>
-
-
-    </tr>
-
-
-
-
-  </tbody>
-</table>
-
-
-
-
-</body></html>
\ No newline at end of file
+</BODY>
+</HTML>

Modified: trunk/libs/graph/doc/known_problems.html
==============================================================================
--- trunk/libs/graph/doc/known_problems.html    (original)
+++ trunk/libs/graph/doc/known_problems.html    Mon Jun  1 21:27:33 2009
@@ -61,7 +61,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/leda_conversion.html
==============================================================================
--- trunk/libs/graph/doc/leda_conversion.html   (original)
+++ trunk/libs/graph/doc/leda_conversion.html   Mon Jun  1 21:27:33 2009
@@ -254,7 +254,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/null_visitor.html
==============================================================================
--- trunk/libs/graph/doc/null_visitor.html      (original)
+++ trunk/libs/graph/doc/null_visitor.html      Mon Jun  1 21:27:33 2009
@@ -85,7 +85,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/opposite.html
==============================================================================
--- trunk/libs/graph/doc/opposite.html  (original)
+++ trunk/libs/graph/doc/opposite.html  Mon Jun  1 21:27:33 2009
@@ -70,7 +70,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/plod_generator.html
==============================================================================
--- trunk/libs/graph/doc/plod_generator.html    (original)
+++ trunk/libs/graph/doc/plod_generator.html    Mon Jun  1 21:27:33 2009
@@ -131,7 +131,7 @@
 <TR valign=top>
 <TD nowrap>Copyright &copy 2005</TD><TD>
<A HREF="http://www.boost.org/people/doug_gregor.html";>Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
-  <A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+  <A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
 </TD></TR></TABLE>


Modified: trunk/libs/graph/doc/predecessor_recorder.html
==============================================================================
--- trunk/libs/graph/doc/predecessor_recorder.html      (original)
+++ trunk/libs/graph/doc/predecessor_recorder.html      Mon Jun  1 21:27:33 2009
@@ -177,7 +177,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/property_map.html
==============================================================================
--- trunk/libs/graph/doc/property_map.html      (original)
+++ trunk/libs/graph/doc/property_map.html      Mon Jun  1 21:27:33 2009
@@ -77,7 +77,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/property_writer.html
==============================================================================
--- trunk/libs/graph/doc/property_writer.html   (original)
+++ trunk/libs/graph/doc/property_writer.html   Mon Jun  1 21:27:33 2009
@@ -188,7 +188,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/publications.html
==============================================================================
--- trunk/libs/graph/doc/publications.html      (original)
+++ trunk/libs/graph/doc/publications.html      Mon Jun  1 21:27:33 2009
@@ -37,7 +37,7 @@
 Indiana University (<A
 HREF="mailto:jsiek@xxxxxxxxxx";>jsiek@xxxxxxxxxx</A>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm";>Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@xxxxxxxxxxxxxx";>llee@xxxxxxxxxxxxxx</A>)<br>
-<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+<A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@xxxxxxxxxx";>lums@xxxxxxxxxx</A>)
 </TD></TR></TABLE>

Modified: trunk/libs/graph/doc/python.html
==============================================================================
--- trunk/libs/graph/doc/python.html    (original)
+++ trunk/libs/graph/doc/python.html    Mon Jun  1 21:27:33 2009
@@ -44,7 +44,7 @@
       <TR valign=top>
         <TD nowrap>Copyright &copy; 2005</TD><TD>
<A HREF="http://www.boost.org/people/doug_gregor.html";>Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
-          <A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
+          <A HREF="http://www.osl.iu.edu/~lums";>Andrew Lumsdaine</A>,
Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
     </TD></TR></TABLE>
   </body>

Modified: trunk/libs/graph/doc/quick_tour.html
==============================================================================
--- trunk/libs/graph/doc/quick_tour.html        (original)
+++ trunk/libs/graph/doc/quick_tour.html        Mon Jun  1 21:27:33 2009
@@ -1,8 +1,6 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html><head>
+<html>

-
-  <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.
@@ -10,748 +8,600 @@
   -- http://www.boost.org/LICENSE_1_0.txt)
   -->

-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- <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"><br clear="">
-
-
-
-
-
-
-<h1>Boost图库快速指南<br>
-
-
-
-
-
-</h1>
-
-
-
-
-
-
-
-
-<p>图数据结构和算法在某些方面比它们的容器更加复杂。STL中使用的抽象迭代器不 能完全适用于图算法中的各种遍历方法。因此,我们专门有一个抽象接口给图使用,该 接口就像基本容器中的迭代器(迭代器仍然占有很重要的角色)。为此,<a href="#fig:analogy">图1</a>对BGL和STL做了比较。<br>
-
-
-
-&nbsp;</p>
-
-
-
-
-
-
-<div align="center">
+<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"><br clear>
+<h1>A Quick Tour of the Boost Graph Library</h1>
+<p>The domain of graph data structures and algorithms is in some respects more +complicated than that of containers. The abstract iterator interface used by STL +is not sufficiently rich to encompass the numerous ways that graph algorithms +may traverse a graph. Instead, we formulate an abstract interface that serves
+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">
   <a name="fig:analogy"></a><a name="752"></a>
-
-<table>
-
-
-
-
-
-
-    <caption valign="bottom"><strong>图1:BGL和STL比较</strong></caption>
-    <tbody>
-
-
-
-
-
+  <table>
+ <caption valign="bottom"><strong>Figure 1:</strong> The analogy between the
+      STL and the BGL.</caption>
     <tr>
-
-
-
-
-
-
-      <td><img src="figs/analogy.gif" height="335" width="518"></td>
-
-
-
-
-
-
+      <td><img src="figs/analogy.gif" width="518" height="335"></td>
     </tr>
-
-
-
-
-
-
-
-
-
-
-
-
-  </tbody>
-</table>
-
-
-
-
-
-
+  </table>
 </div>
-
-
-
-
-
-
 <p>&nbsp;</p>
-
-
-图的抽象表示是由一组顶点(或称:节点)和一组链接顶点的边(或称:弧)组成 的。&nbsp;<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的入边。 +The graph abstraction consists of a set of vertices (or nodes), and a set of +edges (or arcs) that connect the vertices. <a href="#fig:quick-start">Figure 2</a> +depicts a directed graph with five vertices (labeled 0 through 4) and 11 edges. +The edges leaving a vertex are called the <i>out-edges</i> 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 <i>in-edges</i> of the vertex. The edges <tt>{(0,4),(2,4),(3,4)}</tt>
+are all in-edges of vertex 4.
 <p>&nbsp;</p>
-
-
-
-
-
-
-<div align="center">
+<div align="CENTER">
   <a name="fig:quick-start"></a>
-
-<table>
-
-
-
-
-
-
-    <caption valign="bottom"><strong>图2:一个有向图例子</strong></caption>
-    <tbody>
-
-
-
-
-
+  <table>
+ <caption valign="bottom"><strong>Figure 2:</strong> An example of a directed
+      graph.</caption>
     <tr>
-
-
-
-
-
-
-      <td><img src="figs/quick_start.gif" height="124" width="103"></td>
-
-
-
-
-
-
+      <td><img src="figs/quick_start.gif" width="103" height="124"></td>
     </tr>
-
-
-
-
-
-
-
-
-
-
-
-
-  </tbody>
-</table>
-
-
-
-
-
-
+  </table>
 </div>
-
-
-
-
-
-
 <p>&nbsp;</p>
+<p>In the following sections we will use the BGL to construct this example graph +and manipulate it in various ways. The complete source code for this example can +be found in <a href="../example/quick_tour.cpp"><tt>examples/quick_tour.cpp</tt></a>. +Each of the following sections discusses a &quot;slice&quot; of this example
+file. Excerpts from the output of the example program will also be listed.
+<p>&nbsp;
+<h2>Constructing a Graph</h2>
+<p>In this example we will use the BGL <a href="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 &quot;adjacency list&quot;
+data structure. The <tt>adjacency_list</tt> is a template class with six
+template parameters, though here we only fill in the first three parameters 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-edges for each +vertex in the graph and the data structure used to represent the graph's vertex +set (see section <a href="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 selects an
+undirected graph.
+<p>Once we have the graph type selected, we can create the graph in <a href="#fig:quick-start">Figure +2</a> by declaring a graph object and filling in edges using the <a href="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>
+<p>Instead of calling the <tt>add_edge()</tt> function for each edge, we could +use the <a href="adjacency_list.html#sec:iterator-constructor">edge iterator +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 can call +the iterator constructor by passing pointers to the beginning and end of the
+array.
+<pre>
+ Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge), num_vertices);
+</pre>
+<p>Instead of creating a graph with a certain number of vertices to begin with, +it is also possible to add and remove vertices with the <a href="MutableGraph.html#sec:add-vertex"><tt>add_vertex()</tt></a> +and <a href="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>
+<p>Now that we have created a graph, we can use the graph interface to access +the graph data in different ways. First we can access all of the vertices in the +graph using the <a href="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 <i>vertex iterators</i> (the <tt>first</tt> +iterator points to the &quot;beginning&quot; of the vertices and the <tt>second</tt> +iterator points &quot;past the end&quot;). Dereferencing a vertex iterator gives +a vertex object. The type of the vertex iterator is given by the <a href="graph_traits.html"><tt>graph_traits</tt></a> +class. Note that different graph classes can have different associated vertex +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.
+<p>The following example prints out the index for each of the vertices in the
+graph. All vertex and edge properties, including index, are accessed via
+property map objects. The <a href="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) and function
+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>
+<p>The set of edges for a graph can be accessed with the <a href="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 of iterators, +but in this case the iterators are <i>edge iterators</i>. Dereferencing an edge
+iterator gives an edge object. The <tt>source()</tt> and <tt>target()</tt>
+functions return the two vertices that are connected by the edge. Instead of +explicitly creating a <tt>std::pair</tt> for the iterators, this time we will +use the <a href="../../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>. This is +usually more convenient than creating a <tt>std::pair</tt> and is our method 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)]
+ &lt;&lt; &quot;,&quot; &lt;&lt; index[target(*ei, g)] &lt;&lt; &quot;) &quot;;
+    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>
+<p>In the next few examples we will explore the adjacency structure of the graph +from the point of view of a particular vertex. We will look at the vertices' +in-edges, out-edges, and its adjacent vertices. We will encapsulate this in an +&quot;exercise vertex&quot; function, and apply it to each vertex in the graph. +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 about each +vertex; using a functor gives us a place to keep a reference to the graph object
+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 graph classes.
+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>
+<p>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 with <i>vertex +descriptors</i>. Many graph representations (such as adjacency lists) do not +store actual vertex objects, while others do (e.g., pointer-linked graphs). This
+difference is hidden underneath the &quot;black-box&quot; of the vertex
+descriptor object. The vertex descriptor is something provided by each graph +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 map functions +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 of the
+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>
+<p>The out-edges of a vertex are accessed with the <a href="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 the second is +the graph object. The function returns a pair of iterators which provide access
+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 called <i>out-edge
+iterators</i> and dereferencing one of these iterators gives an <i>edge
+descriptor</i> object. An edge descriptor plays the same kind of role as the +vertex descriptor object, it is a &quot;black box&quot; provided by the graph
+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 &lt;&lt; &quot;(&quot; &lt;&lt; index[src] &lt;&lt; &quot;,&quot;
+                  &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>
+<p>The <a href="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 through <i>in-edge +iterators</i>. 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 &lt;&lt; &quot;(&quot; &lt;&lt; index[src] &lt;&lt; &quot;,&quot; &lt;&lt; index[targ] &lt;&lt; &quot;) &quot;;
+      }
+      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>
+<p>Given the out-edges of a vertex, the target vertices of these edges are <i>adjacent</i> +to the source vertex. Sometimes an algorithm does not need to look at the edges +of the graph and only cares about the vertices. Therefore the graph interface +also includes the <a href="AdjacencyGraph.html#sec:adjacent-vertices"><tt>adjacent_vertices()</tt></a> +function of the <a href="AdjacencyGraph.html">AdjacencyGraph</a> interface which +provides direct access to the adjacent vertices. This function returns a pair of +<i>adjacency iterators</i>. Dereferencing an adjacency iterator gives a vertex
+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 edge weight +may need to be used throughout a graph object's lifespan and therefore it would +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 the duration 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 an <i>internally
+stored property</i> while the second kind is called an <i>externally stored
+property</i>. BGL uses a uniform mechanism to access both kinds of properties +inside its graph algorithms called the <i>property map</i> interface, described +in Section <a href="property_map.html">Property Map Concepts</a>. In addition, +the <a href="PropertyGraph.html">PropertyGraph</a> concept defines the interface
+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 <a href="using_adjacency_list.html#sec:adjacency-list-properties">Internal +Properties</a>. Externally stored properties can be created in many different +ways, although they are ultimately passed as separate arguments to the graph +algorithms. One straightforward way to store properties is to create an array +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 map for
+the <tt>vertex_index_t</tt>. Edges are not automatically assigned indices.
+However the property mechanism can be used to attach indices to the edges which
+can be used to index into other externally stored properties.
+<p>In the following example, we construct a graph and apply <a href="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths()</tt></a>. +The complete source code for the example is in <a href="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>. +Dijkstra's algorithm computes the shortest distance from the starting vertex to
+every other vertex in the graph.
+<p>Dijkstra's algorithm requires that a weight property is associated with each +edge and a distance property with each vertex. Here we use an internal property
+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> as the type +used to represent weight values and <tt>edge_weight_t</tt> for the property tag +(which is one of the BGL predefined property tags). The weight property is then
+used as a template argument for <tt>adjacency_list</tt>.
+<p>The <tt>listS</tt> and <tt>vecS</tt> types are selectors that determine the +data structure used inside the <tt>adjacency_list</tt> (see Section <a href="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). The following +code shows the specification of the graph type and then the initialization of +the graph. The edges and weights are passed to the graph constructor in the form +of iterators (a pointer qualifies as a <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html";>RandomAccessIterator</a>).
+<p>&nbsp;
+<pre>
+  typedef adjacency_list&lt;listS, vecS, directedS,
+ no_property, property&lt;edge_weight_t, int&gt; &gt; 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>
+<p>For the external distance property we will use a <tt>std::vector</tt> for +storage. BGL algorithms treat random access iterators as property maps, so we
+can just pass the beginning iterator of the distance vector to Dijkstra's
+algorithm. Continuing the above example, the following code shows the creation +of the distance vector, the call to Dijkstra's algorithm (implicitly using the
+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 &lt;&lt; &quot;distances from start vertex:&quot; &lt;&lt; std::endl;
+  graph_traits&lt;Graph&gt;::vertex_iterator vi;
+  for(vi = vertices(G).first; vi != vertices(G).second; ++vi)
+ std::cout &lt;&lt; &quot;distance(&quot; &lt;&lt; index(*vi) &lt;&lt; &quot;) = &quot;
+              &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>
+<p>Often times an algorithm in a library <i>almost</i> does what you need, but +not quite. For example, in the previous section we used Dijkstra's algorithm to +calculate the shortest distances to each vertex, but perhaps we also wanted 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.
+<p>It would be nice if we could avoid rewriting Dijkstra's algorithm, and just +add that little bit extra needed to record the predecessors <a href="#1">[1]</a>. In the STL, this +kind of extensibility is provided by functors, which are optional parameters to
+each algorithm. In the BGL this role is fulfilled by <i>visitors</i>.
+<p>A visitor is like a functor, but instead of having just one &quot;apply&quot;
+method, it has several. Each of these methods get invoked at certain
+well-defined points within the algorithm. The visitor methods are explained 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 visitors as a +way of extending the BGL. Here we will take a quick look at the implementation +and use of the predecessor recorder. Since we will be using the <a href="dijkstra_shortest_paths.html">dijkstra_shortest_paths()</a> +algorithm, the visitor we create must be a <a href="DijkstraVisitor.html">Dijkstra Visitor</a>. +<p>The functionality of the <tt>record_predecessors</tt> visitor is separated +into two parts. For the storage and access of the predecessor property, we will
+use a <a href="../../property_map/property_map.html">property map</a>. The
+predecessor visitor will then only be responsible for what parent to record. To +implement this, we create a <tt>record_predecessors</tt> class and template it +on the predecessor property map <tt>PredecessorMap</tt>. Since this visitor will +only be filling in one of the visitor methods, we will inherit from <a href="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-paths tree) 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 the new
+predecessor. Here we use the <tt>put()</tt> function associated with the
+property map to record the predecessor. The <tt>edge_filter</tt> of the visitor +tells the algorithm when to invoke the <tt>explore()</tt> method. In this case +we only want to be notified about edges in the shortest-paths tree so we specify
+<tt>tree_edge_tag</tt>.
+<p>As a finishing touch, we create a helper function to make it more convenient +to create predecessor visitors. All BGL visitors have a helper function like
+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 &lt;&lt; &quot;parents in the tree of shortest paths:&quot; &lt;&lt; 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.

-
-
-<p>在接下去的部分中,我们将会用BGL来构建这个例子,并且用多种方法去操作它。 这个例子的全部代码在&nbsp;<a href="../example/quick_tour.cpp"><tt>examples/quick_tour.cpp</tt></a>文件 中。接下去的每部分将会讨论该例子文件中的程序片段。程序的输出内容我们也会列出 来。
-</p>
-
-
-
-
-
-<p>&nbsp;
-</p>
-
-
-
-
-
-<h2>构建一个图</h2>
-
-
-
-
-
-
-<p>在该例中我们将使用BGL的&nbsp;<a href="adjacency_list.html"><tt>adjacency_list</tt></a>
-类来示范一下BGL接口的主要思想。adjacency_list
-类给传统的“邻接列表”数据结构提供了一个范型版本。adjacency_list
-是一个有六个参数的模版类,在该例中我们只使用前三个参数,其余三个参数都用默 认值。前两个模版参数(vecS,vecS)分别表示每个顶点出边集合的数据 -结构和图中顶点集合的数据结构(参考:<a href="using_adjacency_list.html#sec:choosing-graph-type">边列表和顶点列表的 选择</a> :不同数据结构的折中方案)。第三个参数:bidirectionalS,它表示一个 既有出边也有入边的有向图。第三个参数另外的选项是:directedS,它表示选择一个 仅有出边的有向图;undirectedS 表示一个无向图。
-</p>
-
-
-
-
-
-<p>一旦我们确定了图的类型,我们就能够创建&nbsp;<a href="#fig:quick-start">图2</a> 表示的图了,首先声明一个图对象,然后用<a href="MutableGraph.html">MutableGraph</a>接口(它是adjacency_list实现的)中 的<a href="MutableGraph.html#sec:add-edge"><tt>add_edge()</tt></a> -函数来添加图中的边。在这个例子中,我们使用一对edge_array 数组仅仅是为了能够 简单直接的创建边。&nbsp;
-</p>
-
-
-
-
-
-<pre> #include &lt;iostream&gt; // for std::cout<br> #include &lt;utility&gt; // for std::pair<br> #include &lt;algorithm&gt; // forstd::for_each<br> #include &lt;boost/graph/graph_traits.hpp&gt;<br> #include &lt;boost/graph/adjacency_list.hpp&gt;<br> #include &lt;boost/graph/dijkstra_shortest_paths.hpp&gt;<br><br> using namespace boost;<br> <br> int main(int,char*[])<br> {<br> // typedef图类型 <br> typedef adjacency_list&lt;vecS, vecS, bidirectionalS&gt; Graph;<br><br> // 便于标记各顶点<br> enum { A, B, C, D, E, N };<br> const int num_vertices = N;<br> const char* name = "ABCDE";<br><br> // 表示图中的边<br> typedef std::pair&lt;int, int&gt; Edge;<br> Edge edge_array[] = <br> { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),<br> Edge(C,E), Edge(B,D), Edge(D,E) };<br> const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);<br><br> // 声明一个图对象<br> Graph g(num_vertices);<br><br> // 给图对象增加边 <br> for (int i = 0; i &lt; num_edges; ++i)<br> add_edge(edge_array[i].first, edge_array[i].second, g);<br> ...<br> return 0;<br> }<br></pre>
-
-
-
-
-
-
-<p>我们可以使用&nbsp;<a href="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);<br></pre>
-
-
-
-
-
-
-<p>可以用add_vertex() 函数和remove_vertex() 函数来增加、删除顶点的方法来替 换创建图的时候就带固定顶点个数的方法,那两个函数也是&nbsp;<a href="MutableGraph.html">MutableGraph</a>接口中的。
-</p>
-
-
-
-
-
-<h2>存取顶点集</h2>
-
-
-
-
-
-
-<p>现在我们已经建立了一个图,我们可是通过相关图接口使用各种方法来访问图中数 据。首先,我们可以使用 <a href="VertexListGraph.html">VertexListGraph</a>接 口中的<a href="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类型。</p>
-
-
-
-
-
-<p>下面的例子打印出图中每个顶点的序号。所有顶点和边的属性,包括序号在内,全 都通过属性映射(<a href="property_map.html"><tt>property_map</tt></a>)对象 访问。property_map类被用来得到具体的属性(比如:vertex_index_t,它是BGL预定 义的一个属性)或者通过调用具体函数得到相关的属性映射对象。</p>
-
-<p>&nbsp;
-</p>
-
-
-
-
-
-<pre> // ...<br> int main(int,char*[])<br> {<br> // ...<br><br> // <span style="text-decoration: underline;">得到顶点索引的属性映射 </span><br> typedef property_map&lt;Graph, vertex_index_t&gt;::type IndexMap;<br> IndexMap index = get(vertex_index, g);<br><br> std::cout &lt;&lt; "vertices(g) = ";<br> typedef graph_traits&lt;Graph&gt;::vertex_iterator vertex_iter;<br> std::pair&lt;vertex_iter, vertex_iter&gt; vp;<br> for (vp = vertices(g); vp.first != vp.second; ++vp.first)<br> std::cout &lt;&lt; index[*vp.first] &lt;&lt; " ";<br> std::cout &lt;&lt; std::endl;<br> // ...<br> return 0;<br> }<br></pre>
-
-
-
-
-
-
-输出是:
-<pre>  vertices(g) = 0 1 2 3 4<br></pre>
-
-
-
-
-
-
-<p>&nbsp;
-</p>
-
-
-
-
-
-<h2>访问边集合<br>
-
-</h2>
-
-
-
-
-
-
-
-
-
-
-<p>图中边集合能够通过EdgeListGraph接口的<a href="EdgeListGraph.html#sec:edges"><tt>edges()</tt></a>函数访问。与 vertices()函数类似,该函数也返回一个迭代器对,不过这次返回的是边迭代器(edge iterators),通过边迭代器对象能够访问到边对象。source()函数和target()函数返回 链接一条边的首、尾顶点。这次我们用<a href="../../tuple/doc/tuple_users_guide.html#tiers"><tt>tie()</tt></a>辅助函 数来替换std::pair迭代器对,这个函数把std::pair中的两部分拆分到了两个变量当中 去,本例中是ei和ei_end。这种方法比创建std::pair更简单,所以在BGL中我们经常使 用这种方法。</p>
-
-<p>&nbsp;
-</p>
-
-
-
-
-
-<pre> // ...<br> int main(int,char*[])<br> {<br> // ...<br> std::cout &lt;&lt; "edges(g) = ";<br> graph_traits&lt;Graph&gt;::edge_iterator ei, ei_end;<br> for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)<br> std::cout &lt;&lt; "(" &lt;&lt; index[source(*ei, g)] <br> &lt;&lt; "," &lt;&lt; index[target(*ei, g)] &lt;&lt; ") ";<br> std::cout &lt;&lt; std::endl;<br> // ...<br> return 0;<br> }<br></pre>
-
-
-
-
-
-
-输出是:
-<pre> edges(g) = (0,1) (0,2) (0,3) (0,4) (2,0) (2,4) (3,0)<br> (3,1) (3,4) (4,0) (4,1)<br></pre>
-
-
-
-
-
-
-<p>&nbsp;
-</p>
-
-
-
-
-
-<h2>邻接结构<br>
-
-</h2>
-
-在接下去的几个例子中,我们将研究图中邻接结构。我们将着眼于研究顶点的入边、 出边和他的邻接顶点。我们将封装一个“exercise -vertex”函数以得到上面这些数据结构,该函数接受图中顶点作为参数。为了示范 BGL和STL的互用性,我们使用STL中的
-for_each()函数进行迭代顶点并且调用“exercise vertex”函数。
-<p>&nbsp;
-</p>
-
-
-
-
-
-<pre> //...<br> int main(int,char*[])<br> {<br> //...<br> std::for_each(vertices(g).first, vertices(g).second,<br> exercise_vertex&lt;Graph&gt;(g));<br> return 0;<br> }<br></pre>
-
-<span style="font-family: monospace;">我们使用仿函数--exercise_vertex来替 代一般的函数,因 -为我们存取顶点信息的时候需要图对象,使用仿函数能够在执行std::for_each()期间 一直引用图对象。并且,我们使用模版函数来定义图类型,这 -样能够在不同图类的情况下复用代码。下面是exercise_vertex仿函数的开始部 分:<br>
-
-<br>
-
-</span>&nbsp;
-
-
-
-
-<pre> template &lt;class Graph&gt; struct exercise_vertex {<br> exercise_vertex(Graph&amp; g_) : g(g_) {}<br> //...<br> Graph&amp; g;<br> };<br></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”是必须的,因为域操作符左边的类型是依赖于模版参数(图类型)的。下面 是我们定义的仿函数调用方法:<br>
-
-</span>
-<p>&nbsp;
-</p>
-
-
-
-
-
-<pre> template &lt;class Graph&gt; struct exercise_vertex {<br> //...<br> typedef typename graph_traits&lt;Graph&gt;<br> ::vertex_descriptor Vertex;<br><br> void operator()(const Vertex&amp; v) const<br> {<br> //...<br> }<br> //...<br> };<br></pre>
-
-
-
-
-
-
-<p>&nbsp;
-</p>
-
-
-
-
-
-<h3>出边、入边和边描述符<br>
-</h3>
-
-
-
-
-
-
-
-
-
-
-
-<p>通过<a href="IncidenceGraph.html">IncidenceGraph</a>接口的out_edges()函 数能够访问一个顶点的出边。<a href="IncidenceGraph.html#sec:out-edges"><tt>out_edges()</tt></a>函 -数有2个参数:第一个参数是该出边所对应的顶点,第二个参数是边所在的图对象。这 个函数提供一个迭代器对,这个迭代器对允许访问该顶点的所有出边(与
-vertices()函数返回一个迭代器对相类似)。这个迭代器叫做“出边迭代器”(out-edge
-iterators),能够通过某个迭代器得到对应的边描述符(edge
-descriptor)对象。一个边描述符起到的作用和顶点描述符相类似,它是一个由图提供 的黑盒。</p>
-<p>&nbsp;
-</p>
-
-
-
-
-
-<pre> template &lt;class Graph&gt; struct exercise_vertex {<br> //...<br> void operator()(const Vertex&amp; v) const<br> {<br> typedef graph_traits&lt;Graph&gt; GraphTraits;<br> typename property_map&lt;Graph, vertex_index_t&gt;::type <br> index = get(vertex_index, g);<br><br> std::cout &lt;&lt; "out-edges: ";<br> typename GraphTraits::out_edge_iterator out_i, out_end;<br> typename GraphTraits::edge_descriptor e;<br> for (tie(out_i, out_end) = out_edges(v, g); <br> out_i != out_end; ++out_i) {<br> e = *out_i;<br> Vertex src = source(e, g), targ = target(e, g);<br> std::cout &lt;&lt; "(" &lt;&lt; index[src] &lt;&lt; "," <br> &lt;&lt; index[targ] &lt;&lt; ") ";<br> }<br> std::cout &lt;&lt; std::endl;<br> //...<br> }<br> //...<br> };<br></pre>
-顶点0的输出:
-<pre>  out-edges: (0,1) (0,2) (0,3) (0,4)<br></pre>
-
-
-
-
-
-
-<p><a href="BidirectionalGraph.html">BidirectionalGraph</a>接口的<a href="BidirectionalGraph.html#sec:in-edges"><tt>in_edges()</tt></a>函数通过 入边迭代器访问一个顶点所有的入边。in_edges()函数仅当bidirectionalS作为 adjacency_list的模版参数的时候才有效。相对于单向图,双向图占用更多的空间。 </p>
-<p>&nbsp;
-</p>
-
-
-
-
-
-<pre> template &lt;class Graph&gt; struct exercise_vertex {<br> //...<br> void operator()(const Vertex&amp; v) const<br> {<br> //...<br> std::cout &lt;&lt; "in-edges: ";<br> typedef typename graph_traits&lt;Graph&gt; GraphTraits;<br> typename GraphTraits::in_edge_iterator in_i, in_end;<br> for (tie(in_i, in_end) = in_edges(v,g); <br> in_i != in_end; ++in_i) {<br> e = *in_i;<br> Vertex src = source(e, g), targ = target(e, g);<br> std::cout &lt;&lt; "(" &lt;&lt; index[src] &lt;&lt; "," &lt;&lt; index[targ] &lt;&lt; ") ";<br> }<br> std::cout &lt;&lt; std::endl;<br> //...<br> }<br> //...<br> };<br></pre>
-
-
-
-
-
-
-顶点0的输出:
-<pre>  in-edges: (2,0) (3,0) (4,0)<br></pre>
-
-
-
-
-
-
-<p>&nbsp;
-</p>
-
-
-
-
-
-<h3>相邻顶点</h3>
-
-
-
-
-
-
-<p>给定一个顶点的出边,该边的目标顶点就是源顶点的相邻顶点。有时候,一个算法 不关心图中的边而是仅需关心图中顶点。因此,图接口中提供了<a href="AdjacencyGraph.html">AdjacencyGraph</a>接口,该接口中的 <a href="AdjacencyGraph.html#sec:adjacent-vertices"><tt>adjacent_vertices()</tt></a>函 数能够直接访问顶点的相邻顶点。这个函数返回一个邻接迭代器对,通过间接引用邻接 迭代器能够得到邻接顶点的顶点描述符。<br>
 <br>
-&nbsp;
-</p>
-
-
-
-
-
-<pre> template &lt;class Graph&gt; struct exercise_vertex {<br> //...<br> void operator()(Vertex v) const<br> {<br> //...<br> std::cout &lt;&lt; "adjacent vertices: ";<br> typename graph_traits&lt;Graph&gt;::adjacency_iterator ai;<br> typename graph_traits&lt;Graph&gt;::adjacency_iterator ai_end;<br> for (tie(ai, ai_end) = adjacent_vertices(v, g);<br> ai != ai_end; ++ai)<br> std::cout &lt;&lt; index[*ai] &lt;&lt; " ";<br> std::cout &lt;&lt; std::endl;<br> }<br> //...<br> };<br></pre>
-顶点4的输出是:
-<pre>  adjacent vertices: 0 1<br></pre>
-
-
-
-
-
-
-<p>&nbsp;
-</p>
-
-
-
-
-
-<h2>给你的图增添一些色彩<br>
-</h2>
-
-
-
-
-
-
-<p>BBGL试图尽可能灵活的提供图的相关附属属性。一个属性,比如边的权重,可能需 要贯穿图对象的整个生命周期,因此图对象就需要管理该属性的存储。 -另一方面,顶点颜色属性有可能仅在一个单独的算法中被用到,那么最好是把该属性 和图对象分开存储。前一种属性被称作内部存储属性,而第二种属性被称作外部 -存储属性。BGL提供统一的机制来访问这两种属性,该机制叫作:属性影射(property map),内部算法实现是property -map接口,该接口在<a href="property_map.html">Property Map Concepts</a>一章 中被介绍<a href="PropertyGraph.html">PropertyGraph</a>概念定义了一个接口,该 接口用来访问所得图映射对象的内部存储属性。</p> -<p>BGL的adjacency_list类允许用户通过图类的模版参数规定内部存储属性。具体的 实现在<a href="using_adjacency_list.html#sec:adjacency-list-properties">Internal
-Properties</a>一
-节中讲解。有多种方法能够创建外部存储属性,但是这些方法最终都是传递给图算法 一个模版参数而已。一个直观的存储属性的办法是根据点或边的索引创建一个索 -引数组。在adjacency_list类中vecS模版参数,顶点自动给它赋值对应序号,顶点序 号能够通过属性映射得到vertex_index_t -值。边不进行自动赋值索引值。然而属性机制能够被用来把索引绑定到需要把索引作 为外部存储属性的边上。</p> -<p>下面的例子中,我们使用<a href="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths()</tt></a>函 数建立一个图。这个例子的完整的源代码在<a href="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>文 件中。Dijkstra算法计算从一点到图中其它顶点的最短路径。</p> -Dijkstra算法需要给边添加一个权重属性,并且给顶点添加一个距离属性。这里,我 们把权重作为内部属性,把距离作为外部属性。我们使用属性类来表示 -权重属性,并且规定权重的类型为整型(int),使用edge_weight_t作为属性标记(它是 BGL预定义的一个属性标记)。然后,权重属性作为
-adjacency_list的模版参数使用。<br>
-<p>TlistS和vecS是adjacency_list内部数据结构的类型(参考:<a href="using_adjacency_list.html#sec:choosing-graph-type">Choosing -the <tt>Edgelist</tt> and <tt>VertexList 选择边列表和顶点列表</tt></a>)。 directedS类型规定了该图必须是一个有向图(与无向图相对)。下面的代码详细说明了 图类型以及它的初始化部分。边和权重以迭代器的被传入图的构造函数(一个<a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html";>RandomAccessIterator</a>)。
-</p>
-
-
-
-
-
-<p>&nbsp;
-</p>
-
-
-
-
-
-<pre> typedef adjacency_list&lt;listS, vecS, directedS, <br> no_property, property&lt;edge_weight_t, int&gt; &gt; Graph;<br> typedef graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;<br> typedef std::pair&lt;int,int&gt; E;<br><br> const int num_nodes = 5;<br> E edges[] = { E(0,2), <br> E(1,1), E(1,3), E(1,4),<br> E(2,1), E(2,3), <br> E(3,4),<br> E(4,0), E(4,1) };<br> int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1};<br><br> Graph G(edges + sizeof(edges) / sizeof(E), weights, num_nodes);<br></pre> -我们使用std::vector来存储距离这个外部属性。BGL处理随机迭代器像处理属性映射 一样,所以我们仅需传的distance -vector的开始迭代器到Dijkstra算法既可。继续我们上面的例子,下面的代码展示的 是创建一个distance -vector,以及调用Dijkstra算法(隐式的使用了内部属性--权重),然后输出结果。 <br>
-<br>
-<br>
-<pre> // vector为了给distance属性排序 <br> std::vector&lt;int&gt; d(num_vertices(G));<br><br> // 得到第一个顶点<br> Vertex s = *(vertices(G).first);<br> // 调用Dijkstra算法<br> dijkstra_shortest_paths(G, s, distance_map(&amp;d[0]));<br><br> std::cout &lt;&lt; "distances from start vertex:" &lt;&lt; std::endl;<br> graph_traits&lt;Graph&gt;::vertex_iterator vi;<br> for(vi = vertices(G).first; vi != vertices(G).second; ++vi)<br> std::cout &lt;&lt; "distance(" &lt;&lt; index(*vi) &lt;&lt; ") = " <br> &lt;&lt; d[*vi] &lt;&lt; std::endl;<br> std::cout &lt;&lt; std::endl;<br></pre>
-输出是:
-<pre> distances from start vertex:<br> distance(0) = 0<br> distance(1) = 6<br> distance(2) = 1<br> distance(3) = 4<br> distance(4) = 5<br></pre>
-
-
-
-
-
-
-<p>&nbsp;
-</p>
-
-
-
-
-
-<h2>用遍历器扩展图算法<br>
-</h2>
-多数情况下,一个库提供的算法能够满足你的大多数应用,但不是全部。例如,上一 节我们使用Dijkstra算法计算到每个顶点的最短路径,但是我们也许想记录一下前三个 最短路径。一种方法是记录下最短路径数中每一个节点的前驱(父节点)。 -<p>最好是不重写Dijkstra算法,仅仅增加记录前驱节点的代码即可<a href="quick_tour.html#1">[1]</a>。在STL中,这种扩展能力被仿函数提供,它是一 个每个算法的可选参数。在BGL中扮演相同角色的是Visitor。
-</p>
-
-
-
-
-
-<p>Visitor类似于仿函数,但是与仿函数仅有一个可用方法不同,visitor有多个方法 可用。它的每个方法都能够被算法内部预先定义好的指针调用。visitor的方法在<a href="visitor_concepts.html">Visitor Concepts</a>一 -节中详细讲解。BGL为一般任务提供了一系列visitor,其中包括记录前驱节点的 visitor。希望用户能够使用visitor为BGL扩展。在这 -里,我们将会快速的看一看visitor的实现方法,以及记录前驱节点的visitor的使 用。因为我们使用&nbsp;<a href="dijkstra_shortest_paths.html">dijkstra_shortest_paths()</a>算法,所以 我们必须创建一个<a href="DijkstraVisitor.html">Dijkstra Visitor</a>。</p> -<p>record_predecessors visitor的泛函性被分为两个部分。我们使用<a href="../../property_map/property_map.html">property map</a>来存储和访问前驱 节点属性。然后,predecessor visitor将仅负责记录前驱节点。为了实现这些,我们 创建模版类record_predecessors。以后就可以调用该visitor的方法了,因为我们继承 子<a href="dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a>类,所以这个 类没有提供其它方法。predecessor_recorder的构造函数将接受一个属性影射对象并且 把它保存到数据成员。<br>
-<br>
-&nbsp;
-</p>
-
-
-
-
-
-<pre> template &lt;class PredecessorMap&gt;<br> class record_predecessors : public dijkstra_visitor&lt;&gt;<br> {<br> public:<br> record_predecessors(PredecessorMap p)<br> : m_predecessor(p) { }<br><br> template &lt;class Edge, class Graph&gt;<br> void edge_relaxed(Edge e, Graph&amp; g) {<br> // 把源 顶点设置成目标顶点的父节点 <br> put(m_predecessor, target(e, g), source(e, g));<br> }<br> protected:<br> PredecessorMap m_predecessor;<br> };<br></pre> -记录前驱节点非常简单。当Dijkstra算法走到一条边(意味着把它放入最短路径树中 )的时候,我们把源点作为目标顶点的前驱节点记录下来。然后如果这 -条边再被访问,那么前驱属性将会被新的前驱节点改写。我们使用put()函数把属性影 射关联到记录的前驱节点。visitor的edge_filter告 -诉算法何时调用explore()方法。我们仅仅想通知在最短路径树中的边,所以规定使用 tree_edge_tag标记。<br>
-<br>
-作为最后一点,我们创建一个辅助函数来使创建predecessor visitors更简单一些。 所有的BGL visitor都有一个与之类似的辅助函数。
-<p>&nbsp;
-</p>
-
-
-
-
-
-<pre> template &lt;class PredecessorMap&gt;<br> record_predecessors&lt;PredecessorMap&gt;<br> make_predecessor_recorder(PredecessorMap p) {<br> return record_predecessors&lt;PredecessorMap&gt;(p);<br> }<br></pre>
-
-
-
-
-
-
-<p>我们准备在Dijkstra算法中使用record_predecessors了。幸运的是,BGL中的 Dijkstra算法已经配备了一个 -visitor句柄,所以我们只需要传入新的visitor即可。在这个例子中我们只需要使用 一个visitor,但是BGL中一个算法经常配备多个 -visitor句柄(参考<a href="visitor_concepts.html">Visitor Concepts</a>一节)。 <br>
-<br>
-&nbsp;
-</p>
-
-
-
-
-
-<pre> using std::vector;<br> using std::cout;<br> using std::endl;<br> vector&lt;Vertex&gt; p(num_vertices(G)); //the predecessor array<br> dijkstra_shortest_paths(G, s, distance_map(&amp;d[0]). <br> visitor(make_predecessor_recorder(&amp;p[0])));<br><br> cout &lt;&lt; "parents in the tree of shortest paths:" &lt;&lt; endl;<br> for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {<br> cout &lt;&lt; "parent(" &lt;&lt; *vi;<br> if (p[*vi] == Vertex())<br> cout &lt;&lt; ") = no parent" &lt;&lt; endl; <br> else <br> cout &lt;&lt; ") = " &lt;&lt; p[*vi] &lt;&lt; endl;<br> }<br></pre>输出为: -<pre> parents in the tree of shortest paths:<br> parent(0) = no parent<br> parent(1) = 4<br> parent(2) = 0<br> parent(3) = 2<br> parent(4) = 3<br></pre>
-
-


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

Other related posts:

  • » [boost-doc-zh commit] r254 - 转换至1.39.0,第7批,完成以下库:filesystem, flyweight, format, function_type... - codesite-noreply