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