Changes between Version 10 and Version 11 of soc2009

Timestamp:

Mar 20, 2009, 6:23:59 PM (14 years ago)

Author:

Jeremiah Willcock

Comment:

Added wording about Boost Graph Library projects

soc2009

@@ -316 +316 @@
 -Thorsten
 
+== Boost Graph Library ==
+
+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.
+
+=== Hierarchical graph 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/]).  
+
+=== 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. 
+
+=== 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.
+
+=== Graph partitioning ===
+
+This project would involve implementing graph partitioning algorithms, such as those used in METIS ([http://www.cs.umn.edu/~metis]), using BGL. Integrating this support into the Parallel BGL would also be useful.
+
+=== 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. 
+
+=== Network Workbench integration ===            
+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. 
 
 = Earlier Boost SOC Project Proposals =