121 lines
4.4 KiB
HTML
121 lines
4.4 KiB
HTML
<HTML>
|
|
<!--
|
|
Copyright (c) Jeremy Siek 2000
|
|
|
|
Distributed under the Boost Software License, Version 1.0.
|
|
(See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt)
|
|
-->
|
|
<Head>
|
|
<Title>Challenge</Title>
|
|
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
|
|
ALINK="#ff0000">
|
|
<IMG SRC="../../../boost.png"
|
|
ALT="C++ Boost" width="277" height="86">
|
|
|
|
<BR Clear>
|
|
|
|
|
|
<h2>Boost Graph Library Challenge and To-Do Items</h2>
|
|
|
|
|
|
<ul>
|
|
|
|
<li>Dynamic graph algorithms such as described in <a
|
|
href="http://citeseer.ist.psu.edu/eppstein99dynamic.html">Dynamic Graph
|
|
Algorithms</a> and <a
|
|
href="http://citeseer.ist.psu.edu/alberts98software.html">A Software
|
|
Library of Dynamic Graph Algorithms</a>.
|
|
|
|
<li>Polish up code/docs for pending items and champion the formal
|
|
review. The pending items are:</li>
|
|
<ul>
|
|
<li><tt>container_traits.hpp</tt> (this should also include
|
|
the work Matt Austern is doing on this topic)</li>
|
|
|
|
<li>The queues and heaps: <tt>queue.hpp</tt>,
|
|
<tt>mutable_queue.hpp</tt>, <tt>fibonacci_heap.hpp</tt>.
|
|
Somehow merge implementation with Dietmer's heaps and queues.</li>
|
|
|
|
<li><tt>disjoint_sets</tt> </li>
|
|
</ul>
|
|
|
|
<li>Construct a set of planar graph algorithms.</li>
|
|
<ul>
|
|
<li> Is the graph planar?</li>
|
|
<li> "Walk around the block" and similar open and closed neighborhood
|
|
traversals. Note that edge traversals need to resolve to particular ends
|
|
and sides (see below), not just to the edge as a whole.</li>
|
|
<li> Given a point, find the nearest vertex, edge, or bounded polygon.
|
|
Again, edges are viewed as having left and right sides.</li>
|
|
<li> Given a line segment, find intersecting vertices, edges, or bounded
|
|
polygons.</li>
|
|
<li> Given a polygon, find intersecting whatever...</li>
|
|
<li> Various minimum bounding rectangle and clipping problems.</li>
|
|
<li> Construct a planar embedding of a planar graph.</li>
|
|
<li> Find a balanced separator of a graph.</li>
|
|
<li> Modify adjacency_list so that the out-edges can be ordered
|
|
according to a user defined comparison object.</li>
|
|
</ul>
|
|
|
|
<li>Rewrite the Qhull algorithm using the Boost Graph Library (this is
|
|
high difficulty challenge). Or, for a more manageable challenge,
|
|
write an interface for Qhull with the BGL. <a
|
|
href="http://www.qhull.org/">Qhull</a> computes the
|
|
convex hull, Delaunay triangulation, Voronoi diagram, and halfspace
|
|
intersection about a point. Qhull runs in 2-d, 3-d, 4-d, and higher
|
|
dimensions. Qhull is used for collision detection, animation, plate
|
|
tectonics, 3-d modeling, robot motion planning, and other <a
|
|
href="http://www.qhull.org/news/qhull-news.html#users">applications</a>.
|
|
It is currently difficult to use from a C++ program.
|
|
|
|
</li>
|
|
|
|
|
|
<li>Explore the use of Algorithm Objects as an alternative to
|
|
the current approach with visitors.</li>
|
|
|
|
<li>Analyze the algorithms that do not yet have visitors, and
|
|
come up with visitor interfaces for them.</li>
|
|
|
|
<li>Add a check in the adjacency_list class to make sure
|
|
all the vertex property template arguments have kind=vertex_property_tag
|
|
and all edge property template arguments have kind=edge_property_tag.</li>
|
|
|
|
<li>Clean up the output functions in graph_utility.hpp to
|
|
use streams, and document all the utility functions. Replace
|
|
the random number stuff with calls to the boost random number generator.</li>
|
|
|
|
<li>Modularize the tests in test/graph.cpp to apply to particular
|
|
concepts. Make sure there are run-time tests for every BGL concept.</li>
|
|
|
|
<li>Write tests for the BGL algorithms. There are a few, but
|
|
more are needed. The example provide a sanity check but do not
|
|
provide full coverage.</li>
|
|
|
|
<li>Write up the examples from Knuth's <i>Stanford GraphBase</i> using
|
|
the BGL. The file <a
|
|
href="../example/miles_span.cpp"><tt>examples/miles_span.cpp</tt></a>
|
|
is a start.</li>
|
|
|
|
<li>Further testing of the <tt>subgraph</tt> class and add more
|
|
features.</li>
|
|
|
|
<li>Implement a minimum-cost maximum-flow algorithm.</li>
|
|
|
|
<li>Make the <tt>type</tt> of all (internal) property maps convertible to the <tt>const_type</tt> of the property maps.<li>
|
|
|
|
<li>Add static functions to <tt>adjacency_list</tt> to return the per-vertex, per-edge, and per-graph overhead.</li>
|
|
</ul>
|
|
|
|
<br>
|
|
<HR>
|
|
<TABLE>
|
|
<TR valign=top>
|
|
<TD nowrap>Copyright © 2000-2001</TD><TD>
|
|
<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>)
|
|
</TD></TR></TABLE>
|
|
|
|
</BODY>
|
|
</HTML>
|