Hello again, As I was asked to be more specific than I was in my proposal I am sending you this addition, which is also posted as a comment at my proposal page. Regards, Balsa I'll be glad to give more details. Like stated in my proposal, my idea would be to discuss all the algorithms with all interested parties before implementing them, so these would be just some of my ideas. In many current graph partitioning packages the multilevel partitioning is included. For me, this is where I would start, since from studies I've seen, high quality partitions with moderate computational complexity are produced with this approach. Multilevel partitioning has 3 phases: coarsening, partitioning and uncoarsening. To coarsen a graph for me the best solution would be the edge collapsing. METIS reduces the size of the graph by collapsing vertices and edges using a heavy-edge matching scheme. Some other heuristics for coarsening the graph iteratively, could also be implemented (random matching or gain vertex matching). The partitioning algorithm would probably be some sort of a recursive bisection algorithm. I know also METIS uses greedy graph growing algorithm. For uncoarsening and refinement phase, my choice would be Kernighan - Lin heuristic. It seems to me that multilevel algorithms that adopt K-L during the uncoarsening and refinement phase are proven to be superior. Like I said, multilevel algorithms would be primary, but expanding The BGL with some geometric or spectral partitioning algorithms could be very useful for some users. Since the main purpose of partitioning is the prospect of implementing the application code on parallel machines, the logical next step would be to include parallel partitioning similar to ParMETIS. Also, like stated in my proposal, if the hypergraph data structure gets developed by then, I would like to implement some partitioning algorithms on hypergraphs. I am aware that implementing, testing, optimizing and documenting all this would be too much for a duration of GSoC,so I would put my priorities in multilevel partitioning on existing graph data structures in The BGL, and if time allows or afterwards get to other ideas. Thank you very much for taking interest and I'll be glad to answer any further questions regarding this proposal. Regards, Balsa On Tue, Mar 31, 2009 at 10:46 AM, Balša Raičević <balsa.raicevic@gmail.com>wrote:
Hello,
I'm a Computer Science student from Faculty of Mathematics, University of Belgrade. I am interested in working on The BGL. I have a lot of experience with C++ and code refactoring also, since I've done a lot of tutoring and encountered a lot of strange students' code :)
I have taken a deep look at BGL ( which is why I'm writing my proposal so late :) ) and to some extend its extension - The Parallel Boost Graph Library.
I am mostly interested in graph partitioning, as I find them very useful for parallel computing. I understood the importance of it when I had to do some major calculations for numerical approximations and wanted to use all the CPU power available :)
In the project idea list ( https://svn.boost.org/trac/boost/wiki/soc2009#Graphpartitioning) it's said that it would be good to implement algorithms similar to those in METIS ( http://www.cs.umn.edu/~metis <http://www.cs.umn.edu/%7Emetis>). I've read some of George Karypis' "Publications Related to Graph Partitioning", so I was wondering if I could discuss with someone which algorithms would be good to implement, and of course, how. I found little, if any, discussion about that in mailing list archive.
Other thing I would really like to see is hypergraph partitioning. I see that implementing hypergraphs in the BGL is one of GSoC projects, so I would like to know would it be possible, if that project is not awarded to anyone for this summer, to do basic implementation of a hypergraph, or (since I see there is already a discussion about that) if somebody else would do that project, to collaborate on hypergraph partitioning algorithms.
Last, but not least, an important question: I would like to use this work as part of my Master's Thesis. I looked at GSoC FAQ ( http://socghop.appspot.com/document/show/program/google/gsoc2009/faqs#course...), so I guess it is OK with the program, but I would still like to discuss it with potential mentor.
Thanks ahead, Balsa