[boost] Boost.Graph for GSoC

Subject: [boost] Boost.Graph for GSoC
From: Daniel Mitchell (dlm.bulk.messages_at_[hidden])
Date: 2013-04-08 12:32:18

Hi all, I'm a researcher and graduate student at the University of Texas at Austin and I'm interested in doing a Boost.Graph project for GSoC. I was thinking of doing one or more planar graph algorithms, in particular the multiple source shortest paths algorithm for planar graphs described at

http://courses.csail.mit.edu/6.889/fall11/lectures/L11.html

The algorithm assumes that the sources are located on a single face. It proceeds by calculating the shortest paths tree from one source and then minimally modifying the tree to efficiently get the shortest paths from the other sources. The algorithm uses a dynamic tree data structure, so developing that data structure would be part of the project too.

I've made prior contributions to BGL. I worked with Doug Gregor to implement color maps for the breadth first and Dijkstra's algorithms. One of my current areas of research is movement ecology, where planar graphs can be used to study movement.

Let me know what you think.

Daniel Mitchell