Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/history.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 11.3 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
4  --
5  -- Distributed under the Boost Software License, Version 1.0.
6  -- (See accompanying file LICENSE_1_0.txt or copy at
7  -- http://www.boost.org/LICENSE_1_0.txt)
8  -->
9<Head>
10<Title>Boost Graph Library: History</Title>
11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
12        ALINK="#ff0000"> 
13<IMG SRC="../../../boost.png" 
14     ALT="C++ Boost" width="277" height="86"> 
15
16<BR Clear>
17
18<h1>History of the Boost Graph Library</h1>
19
20The Boost Graph Library began its life as the Generic Graph Component
21Library (GGCL), a software project at the <a
22href="http://www.lsc.nd.edu">Lab for Scientific Computing (LSC)</a> at
23the University of Notre Dame, under the direction of Professor <a
24href="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</a>. The Lab's
25research directions include numerical linear algebra, parallel
26computing, and software engineering (including generic programming).
27
28<p>
29Soon after the Standard Template Library was released, work began at
30the LSC to apply generic programming to scientific computing.  The <a
31href="http://www.lsc.nd.edu/research/mtl">Matrix Template Library</a>
32(Jeremy Siek's masters thesis) was one of the first projects. Many of
33the lessons learned during construction of the MTL were applied to the
34design and implementation of the GGCL.
35
36<p>
37Graph algorithms play an important role in sparse matrix computations,
38so the LSC had a need for a good graph library. However, none of the
39available graph libraries (LEDA, GTL, Stanford GraphBase) were
40written using the generic programming style of the STL, and hence did
41not fulfill the flexibility and high-performance requirements of the
42LSC. Others were also expressing interest in a generic C++ graph
43library. During a meeting with Bjarne Stroustrup we were introduced to
44several people at AT\&T who needed such a library. There had also been
45earlier work in the area of generic graph algorithms, including some
46codes written by Alexander Stepanov, and Dietmar K&uuml;hl's masters
47thesis.
48
49<p>
50With this in mind, and motivated by homework assignments in his
51algorithms class, Jeremy began prototyping an interface and some graph
52classes in the spring on 1998. Lie-Quan Lee then developed the first
53version of GGCL, which became his masters thesis project.
54
55<p>
56The following year, Jeremy went to work for SGI with Alexander
57Stepanov and Matt Austern. During this time Alex's disjoint-sets based
58connected components algorithm was added to GGCL, and Jeremy began
59working on the concept documentation for GGCL similar to Matt's STL
60documentation.
61
62<p>
63While working at SGI, Jeremy heard about Boost and was excited to find
64a group of people interested in creating high-quality C++
65libraries. At boost there were several people interested in generic
66graph algorithms, most notably Dietmar K&uuml;hl.  Some discussions
67about generic interfaces for graph structures resulted in the a
68revision of GGCL which closely resembles the current Boost Graph
69Library interface.
70
71<p>
72On September 4, 2000 GGCL passed the Boost formal review and became
73the Boost Graph Library (BGL). The first release of BGL was
74September 27, 2000.
75
76<h2>Changes by version</h2>
77<a name="by-version">
78<ul>
79  <a name="1.34.1"></a><li>Version 1.34.1</br><b>Bug Fixes</b><br>
80  <ul>
81     <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>
82  </ul>
83  <a name="1.34.0"></a><li>Version 1.34.0<br><b>New algorithms and components</b>
84    <ul>
85      <li><a href="maximum_matching.html"><tt>edmonds_maximum_cardinality_matching</tt></a>, from Aaron Windsor.</li>
86      <li><a href="lengauer_tarjan_dominator.htm"><tt>lengauer_tarjan_dominator_tree</tt></a>, from JongSoo Park.</li>
87      <li><a href="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a>, from Jeremiah Willcock and Douglas Gregor of Indiana University.</li>
88      <li><a href="sorted_erdos_renyi_gen.html"><tt>sorted_erdos_renyi_iterator</tt></a>, from Jeremiah Willcock of Indiana University.</li>
89    </ul><br><b>Enhancements</b><br>
90    <ul>
91       <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>
92      <li><a href="biconnected_components.html"><tt>biconnected_components</tt></a> now has a visitor parameter and supports named parameters, from Janusz Piwowarski.</li>
93      <li><a href="adjacency_matrix.html"><tt>adjacency_matrix</tt></a> now models the <a href="BidirectionalGraph.html">Bidirectional Graph</a> concept.</li>
94                             <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>
95       <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>
96       <li>Added <tt>operator< </tt>, etc. to the edge descriptor of <tt>adjacency_list</tt>,
97             from Jeremy Siek of Rice University.</li>
98    </ul>
99    <br><b>Bug Fixes</b><br>
100    <ul>
101      <li>Fixed a bug that causes the relaxed heap to fail on x86 Linux.</li>
102      <li>Bundled properties now work with adjacency list I/O.</li>
103      <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>
104      <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>
105      <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.
106    </ul>
107    <br>
108  </li>
109
110  <li>Version 1.33.1<br><b>Bug Fixes</b>
111    <ul>
112      <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>
113      <li><a href="king_ordering.html"><tt>king_ordering</tt></a> and <a
114      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>
115    </ul></li>
116
117  <li>Version 1.33.0<br><b>New algorithms and components</b>
118    <ul>
119      <li><a href="python.html">Experimental Python bindings</a>, from Doug Gregor and Indiana University.</li>
120      <LI><A href="floyd_warshall_shortest.html"><TT>floyd_warshall_all_pairs_shortest_paths</TT></A>, from Lauren Foutz and Scott Hill.</LI>
121      <LI><A href="astar_search.html"><TT>astar_search</TT></A>, from Kristopher Beevers and Jufeng Peng.</LI>
122      <LI><A href="fruchterman_reingold.html"><TT>fruchterman_reingold_force_directed_layout</TT></A>, from Doug Gregor and Indiana University.</a></LI>
123      <LI><A href="biconnected_components.html"><tt>biconnected_components</tt> and <tt>articulation_points</tt></a>, from Indiana University.</a></li>
124      <li><a href="gursoy_atun_layout.html"><tt>gursoy_atun_layout</tt></a>, from Jeremiah Willcock and Doug Gregor of Indiana University.</li>
125      <li><a href="king_ordering.html"><tt>king_ordering</tt></a>, from
126      D. Kevin McGrath of Indiana University.</li>
127      <li><a href="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a></li>
128      <li><a href="plod_generator.html"><tt>plod_iterator</tt></a></li>
129      <li><a href="small_world_generator.html"><tt>small_world_iterator</tt></a></li>
130    </ul><br><b>Enhancements</b><br>
131    <ul>
132      <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>
133      <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>
134      <li><a href="dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths</tt></a> now uses a relaxed heap&nbsp;[<A
135  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>
136      <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>
137     
138      <li><a
139      href="write-graphviz.html"><code>write_graphviz</code></a> now
140      supports output of dynamic properties (as read in through the
141      new <code>read_graphviz</code>).</li>
142
143      <li><a
144      href="cuthill_mckee_ordering.html"><tt>cuthill_mckee_ordering</tt></a>
145      has been recast as an invocation of
146      <tt>breadth_first_search</tt> and now supports graphs with
147      multiple components.</li>
148 
149      <li><a href="subgraph.html"><tt>subgraph</tt></a> now supports
150      <a href="bundles.html">bundled
151      properties</a>. <code>get_property</code> now refers to the
152      subgraph property, not the root graph's property.</li></li>
153
154      <li><a href="filtered_graph.html"><tt>filtered_graph</tt></a> now
155      supports <a href="bundles.html">bundled properties</a>.</li>
156
157      <li><a href="reverse_graph.html"><tt>reverse_graph</tt></a> now
158      supports <a href="bundles.html">bundled properties</a>,
159      <tt>set_property</tt>, and <tt>get_property</tt>.</li>
160
161    </ul><br><b>Bug fixes</b><br>
162    <ul>
163      <li><a href="bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths</tt></a> now deals with unreachable vertices better.</li>
164      <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>
165      <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>
166      <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>
167      <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>
168      <li><a href="read_graphviz.html"><tt>read_graphviz</tt></a> now accepts empty attribute lists.</li>
169      <li><a href="sequential_vertex_coloring.html"><tt>sequential_vertex_coloring</tt></a> has been updated, tested, and documented.</li>
170    </ul>
171  </li>
172</ul>
173
174<br>
175<HR>
176<TABLE>
177<TR valign=top>
178<TD nowrap>Copyright &copy 2000-2001</TD><TD>
179<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
180Indiana University (<A
181HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
182<A HREF="../../../people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
183<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
184Indiana University (<A
185HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
186</TD></TR></TABLE>
187
188</BODY>
189</HTML> 
190<!--  LocalWords:  gif ALT GGCL LSC Lumsdaine Siek's MTL LEDA GTL GraphBase STL
191 -->
192<!--  LocalWords:  Bjarne Stroustrup hl's Quan SGI Stepanov Austern Alex's hl
193 -->
194<!--  LocalWords:  Dietmar BGL siek htm Univ
195 -->
Note: See TracBrowser for help on using the repository browser.