]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | |
25 | href="http://citeseer.ist.psu.edu/eppstein99dynamic.html">Dynamic Graph | |
26 | Algorithms</a> and <a | |
27 | href="http://citeseer.ist.psu.edu/alberts98software.html">A Software | |
28 | Library of Dynamic Graph Algorithms</a>. | |
29 | ||
30 | <li>Polish up code/docs for pending items and champion the formal | |
31 | review. 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> </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 | |
47 | traversals. Note that edge traversals need to resolve to particular ends | |
48 | and 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. | |
50 | Again, edges are viewed as having left and right sides.</li> | |
51 | <li> Given a line segment, find intersecting vertices, edges, or bounded | |
52 | polygons.</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 | |
62 | high difficulty challenge). Or, for a more manageable challenge, | |
63 | write an interface for Qhull with the BGL. <a | |
64 | href="http://www.geom.umn.edu/locate/qhull">Qhull</a> computes the | |
65 | convex hull, Delaunay triangulation, Voronoi diagram, and halfspace | |
66 | intersection about a point. Qhull runs in 2-d, 3-d, 4-d, and higher | |
67 | dimensions. Qhull is used for collision detection, animation, plate | |
68 | tectonics, 3-d modeling, robot motion planning, and other <a | |
69 | href="http://www.geom.umn.edu/~bradb/qhull-news.html#use">applications</a>. | |
70 | It 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> |