Boost圖庫的歷史

標準模版庫出現後不久，LSC實驗室就開始採用范型編程來進行科學計算。矩陣模版庫(Matrix Template Library （Jeremy Siek的碩士學位論文）就是最早採用范型編程的項目之一。同時，構建MTL過程中的一些經驗被引入到GGCL的設計和實現當中。

由於圖算法在稀疏矩陣計算當中起著非常重要的作用，所以LSC需要一個優秀的圖庫。然而，沒有一個圖庫(LEDA, GTL, Stanford GraphBase)是用STL的范型編程風格去寫的，並且已有庫也不能很好的適應LSC對於靈活和高性能方面的需求。另外也有一些人非常需要用C++實 現的范型庫。在一次會議期間Bjarne Stroustrup被介紹給了一些需要這些庫的人。其實在范型圖算法方面已經做了一些前期工作，比如Alexander Stepanov寫的一些代碼，以及Dietmar Kuhl的碩士論文。

在這種思想的驅動下，同時為了完成算法課的作業，Jeremy於1998年春開始一套實現接口原型和一些圖相關類了。隨後，Lie- Quan Lee開發了GGCL的第一個版本，並且該項目作為他的碩士論文項目。

接下去的一年，Jeremy和Alexander Stepanov 以及Matt Austern一起到了SGI工作。其間Alex的基於連通分支的不相交集合算法被加入到GGCL中，並且Jeremy開始給GGCL的概念文檔了，該文 檔類似於Matt給STL寫的文檔。

在SGI工作期間，Jeremy聽說了Boost並且找到了一群對創造一套高質量C++庫感興趣的人。Boost成員中，有很多人對泛 型圖算法都很 感興趣，最有名的是Dietmar Kuhl。關於圖結構的范型接口的一些論述被加入到了GGCL中，它們已經很像現在的Boost圖庫接口了。

在2000年9月4日，GGCL通過了Boost的正式評審並且成為了Boost圖庫（BGL）。BGL的第一個發行版是2000年9 月27日發行的。

版本變更

• Version 1.35.0
  New algorithms and components
  • kolmogorov_max_flow, from Stephan Diederich as part of the 2006 Google Summer of Code.
  • read_dimacs_max_flow and write_dimacs_max_flow for max-flow problems, from Stephan Diederich.
  • read_graphml and write_graphml for GraphML input/output, from Tiago de Paula Peixoto.
  • minimum_cycle_ratio and maximum_cycle_ratio, from Dmitry Bufistov and Andrey Parfenov.
  • boyer_myrvold_planarity_test, along with a suite of algorithms for planar graphs, from Aaron Windsor.
  
  Enhancements
  
  • LEDA Adaptor improvements, from Jens Muller.


• 1.34.1 版
  BUG修復
  
  • bellman_ford_shortest_paths: 修復了某些負回路不能被正確識別的BUG。
• 1.34.0版
  新算法和新組件
  • edmonds_maximum_cardinality_matching,  Aaron Windsor 提供
  • lengauer_tarjan_dominator_tree, JongSoo Park 提供
  • compressed_sparse_row_graph, 印第安納大學的Jeremiah Willcock 和 Douglas Gregor提供
  • sorted_erdos_renyi_iterator, 印第安納大學的Jeremiah Willcock提供
  
  改善
  
  • 注意：GraphViz編譯出來的名字現在叫boost_graph了，比起bgl-viz來更好讀；
  • biconnected_components 現在有了一個遍歷器（visitor）參數並且支持命名參數了，Janusz Piwowarski提供；
  • adjacency_matrix 現在宿模 Bidirectional Graph 概念.
  • adjacency_list 現在可序列化 Serializable, Rice大學的Jeremy Siek提供；
  • Added edges_size_type and vertices_size_type to adjacency_list_traits, from Jeremy Siek of Rice University.
  • Added operator< , etc. to the edge descriptor of adjacency_list, from Jeremy Siek of Rice University.
  
  Bug Fixes
  
  • Fixed a bug that causes the relaxed heap to fail on x86 Linux.
  • Bundled properties now work with adjacency list I/O.
  • floyd_warshall_all_pairs_shortest_paths now properly uses its compare, inf, and zero parameters.
  • johnson_all_pairs_shortest_paths now supports compare, combine, inf, and zero.
  • 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.
  
  
• Version 1.33.1
  Bug Fixes
  • fruchterman_reingold_force_directed_layout: Fixed enumeration of grid-force pairs, which caused some odd graph formations along grid lines.
  • king_ordering and cuthill_mckee_ordering: Fixed bug that caused failures with the multi-component version of these algorithms.
• Version 1.33.0
  New algorithms and components
  • Experimental Python bindings, from Doug Gregor and Indiana University.
  • floyd_warshall_all_pairs_shortest_paths, from Lauren Foutz and Scott Hill.
  • astar_search, from Kristopher Beevers and Jufeng Peng.
  • fruchterman_reingold_force_directed_layout, from Doug Gregor and Indiana University.
  • biconnected_components and articulation_points, from Indiana University.
  • gursoy_atun_layout, from Jeremiah Willcock and Doug Gregor of Indiana University.
  • king_ordering, from D. Kevin McGrath of Indiana University.
  • erdos_renyi_iterator
  • plod_iterator
  • small_world_iterator
  
  Enhancements
  
  • bellman_ford_shortest_paths now permits one to specify the starting vertex, so that it will perform its own initialization.
  • undirected_dfs is now data-recursive, resulting in improved performance in some cases, from Synge Todo.
  • dijkstra_shortest_paths now uses a relaxed heap [61] as its priority queue, improving its complexity to O(V log V) and improving real-world performance for larger graphs.
  • read_graphviz 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.
  • write_graphviz now supports output of dynamic properties (as read in through the new read_graphviz).
  • cuthill_mckee_ordering has been recast as an invocation of breadth_first_search and now supports graphs with multiple components.
  • subgraph now supports bundled properties. get_property now refers to the subgraph property, not the root graph's property.
  • filtered_graph now supports bundled properties.
  • reverse_graph now supports bundled properties, set_property, and get_property.
  
  Bug fixes
  
  • bellman_ford_shortest_paths now deals with unreachable vertices better.
  • adjacency_list: parallel edge removal with OutEdgeListS = listS has been fixed. Copying and swapping has been fixed.
  • Incremental connected components: fixed a bug in the incremental_components routine that may have caused incorrect results.
  • The remove_out_edge_if function for an undirected adjacency_list has been rewritten and should no longer dereference singular iterators.
  • write_graphviz now accepts a vertex_id parameter that is used to name the nodes.
  • read_graphviz now accepts empty attribute lists.
  • sequential_vertex_coloring has been updated, tested, and documented.