Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/history.html @ 12

Last change on this file since 12 was 12, checked in by landauf, 18 years ago

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