1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek 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>Challenge</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 19<h2>Boost Graph Library Challenge and To-Do Items</h2> 20 21 22<ul> 23 24<li>Dynamic graph algorithms such as described in <a 25href="http://citeseer.ist.psu.edu/eppstein99dynamic.html">Dynamic Graph 26Algorithms</a> and <a 27href="http://citeseer.ist.psu.edu/alberts98software.html">A Software 28Library of Dynamic Graph Algorithms</a>. 29 30<li>Polish up code/docs for pending items and champion the formal 31review. The pending items are:</li> 32 <ul> 33 <li><tt>container_traits.hpp</tt> (this should also include 34 the work Matt Austern is doing on this topic)</li> 35 36 <li>The queues and heaps: <tt>queue.hpp</tt>, 37 <tt>mutable_queue.hpp</tt>, <tt>fibonacci_heap.hpp</tt>. 38 Somehow merge implementation with Dietmer's heaps and queues.</li> 39 40 <li><tt>disjoint_sets</tt> (see <a href="disjoint_sets.html">)</li> 41 </ul> 42 43<li>Construct a set of planar graph algorithms.</li> 44 <ul> 45 <li> Is the graph planar?</li> 46 <li> "Walk around the block" and similar open and closed neighborhood 47traversals. Note that edge traversals need to resolve to particular ends 48and sides (see below), not just to the edge as a whole.</li> 49 <li> Given a point, find the nearest vertex, edge, or bounded polygon. 50Again, edges are viewed as having left and right sides.</li> 51 <li> Given a line segment, find intersecting vertices, edges, or bounded 52polygons.</li> 53 <li> Given a polygon, find intersecting whatever...</li> 54 <li> Various minimum bounding rectangle and clipping problems.</li> 55 <li> Construct a planar embedding of a planar graph.</li> 56 <li> Find a balanced separator of a graph.</li> 57 <li> Modify adjacency_list so that the out-edges can be ordered 58 according to a user defined comparison object.</li> 59 </ul> 60 61<li>Rewrite the Qhull algorithm using the Boost Graph Library (this is 62high difficulty challenge). Or, for a more manageable challenge, 63write an interface for Qhull with the BGL. <a 64href="http://www.qhull.org/">Qhull</a> computes the 65convex hull, Delaunay triangulation, Voronoi diagram, and halfspace 66intersection about a point. Qhull runs in 2-d, 3-d, 4-d, and higher 67dimensions. Qhull is used for collision detection, animation, plate 68tectonics, 3-d modeling, robot motion planning, and other <a 69href="http://www.qhull.org/news/qhull-news.html#users">applications</a>. 70It is currently difficult to use from a C++ program. 71 72</li> 73 74 75<li>Explore the use of Algorithm Objects as an alternative to 76 the current approach with visitors.</li> 77 78<li>Analyze the algorithms that do not yet have visitors, and 79 come up with visitor interfaces for them.</li> 80 81<li>Add a check in the adjacency_list class to make sure 82 all the vertex property template arguments have kind=vertex_property_tag 83 and all edge property template arguments have kind=edge_property_tag.</li> 84 85<li>Clean up the output functions in graph_utility.hpp to 86 use streams, and document all the utility functions. Replace 87 the random number stuff with calls to the boost random number generator.</li> 88 89<li>Modularize the tests in test/graph.cpp to apply to particular 90 concepts. Make sure there are run-time tests for every BGL concept.</li> 91 92<li>Write tests for the BGL algorithms. There are a few, but 93 more are needed. The example provide a sanity check but do not 94 provide full coverage.</li> 95 96<li>Write up the examples from Knuth's <i>Stanford GraphBase</i> using 97 the BGL. The file <a 98 href="../example/miles_span.cpp"><tt>examples/miles_span.cpp</tt></a> 99 is a start.</li> 100 101<li>Further testing of the <tt>subgraph</tt> class and add more 102 features.</li> 103 104<li>Implement a minimum-cost maximum-flow algorithm.</li> 105 106<li>Make the <tt>type</tt> of all (internal) property maps convertible to the <tt>const_type</tt> of the property maps.<li> 107 108<li>Add static functions to <tt>adjacency_list</tt> to return the per-vertex, per-edge, and per-graph overhead.</li> 109</ul> 110 111<br> 112<HR> 113<TABLE> 114<TR valign=top> 115<TD nowrap>Copyright © 2000-2001</TD><TD> 116<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>) 117</TD></TR></TABLE> 118 119</BODY> 120</HTML> 121
