ceph/src/boost/libs/graph/doc/challenge.html

   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> &quot;Walk around the block&quot; 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 &copy; 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>