Changes between Version 17 and Version 18 of SoC2010

Timestamp:

Mar 11, 2010, 9:07:20 PM (13 years ago)

Author:

Andrew Sutton

Comment:

--

SoC2010

@@ -60 +60 @@
 For projects on the Boost.Graph library, students should have a working knowledge of graph theory and graph data structures. An sound understanding of techniques for [http://www.boost.org/community/generic_programming.html generic programming] are also required.
 
+In addition to the graph library that is currently in Boost, Indiana University has also created parallel extensions to BGL (the Parallel Boost Graph Library) for distributed-memory computers.  Several of the projects below would also be worthwhile to integrate into the parallel framework.
+
  * Topology Generators - One useful set of algorithms not included in the BGL is the ability to easily generate graphs of specific topologies (e.g., [http://mathworld.wolfram.com/PathGraph.html path], [http://mathworld.wolfram.com/CycleGraph.html cycle], [http://mathworld.wolfram.com/StarGraph.html star], etc.). In addition to creating graphs of these topologies, it would be useful to induce these topologies on an existing set of vertices, and query a set of vertices to determine if the topology is admitted by a set of vertices.
  
  * Graph Connectives - The Boost.Graph library is missing [http://mathworld.wolfram.com/Connective.html connectives].  Develop a set of generic algorithms for computing the [http://mathworld.wolfram.com/GraphUnion.html union], [http://mathworld.wolfram.com/GraphJoin.html join], [http://mathworld.wolfram.com/GraphIntersection.html intersection], and [http://mathworld.wolfram.com/GraphDifference.html difference] of graphs. Additional algorithms might be constructed for unary operations (e.g., line graph). Other operations may include a family of [http://mathworld.wolfram.com/GraphProduct.html graph products].
+
+ * Hierarchical Layout Algorithms - The Boost Graph Library (BGL) currently only implements a small number of graph layout algorithms, primarily spring-based layout algorithms. This project would involve implementing other layout algorithms, especially hierarchical algorithms such as that used in the dot program of Graphviz ([http://www.graphviz.org/]).  
+
+ * Semantic Graphs - A semantic graph is a graph that can have multiple distinct types of vertices and edges, with restrictions on connections between vertices and edges based on their types.  There may also be more efficient representations of the graph based on storing different vertex and edge types separately.  This project would be to define appropriate concepts, algorithms, and data structures for semantic graphs in BGL.
+
+ * Computer Vision Algorithms - This project would be to implement computer vision algorithms based on max-flow problems on graphs using BGL.  Implementing a specialized graph type for grids would also be needed in order to avoid storing the graph topology explicitly. 
+
+ * Closures and Reductions - Implement a suite of generic graph algorithms that computer closures and reductions on graphs. The BGL already contains a `transitive_closure` algorithm, but not (yet) a `transitive_reduction`. Other kinds of computable closures and reductions include reflexive, symmetric, and congruence. This project can also include predicates to test whether or not a graph exhibits these properties (e.g., is_symmetric).
+
+ * Bindings to Python (or Other Languages) - BGL has some bindings to Python and R, but they do not exist for all algorithms.  This project would be to either extend the Python or R bindings, or write a set of BGL bindings to another language. 
+
+ * Network Workbench - The Network Workbench ([http://nwb.slis.indiana.edu/]) is a GUI-based framework for analysis of large-scale networks.  This project would involve implementing components for NWB based on BGL and/or Parallel BGL. 
 
 == Heaps & Queues ==