Just submitted GSoC Project Proposals : OGDF

I have submitted four proposals for project ideas given by OGDF.

1. Computation of Treewidth
2. Basic Linear Algebra Support
3. Generators for Different Random Graph Models
4. Search Trees and Priority Queues

Computation of Treewidth

Short description: The treewidth measures how similar a given graph is to a tree. Tree width is widely used in various areas in Graph theory. However, already computing the treewidth of a graph is NP-complete. There exist, however, practically good heuristics which construct a tree decomposition close to the optimum.

Find the complete proposal here.

Basic Linear Algebra Support

Short description: Basic data structures for vectors and matrices are used in many graph layout algorithms that apply some kind of numerical optimization. But OGDF does not provide vector/matrix classes out-of-the-box. So the goal of this project is to provide powerful and efficient vector and matrix classes, that provide the obvious basic functionality as well as more complex operations and different storage models.

Find the complete proposal here.

Generators for Different Random Graph Models

Short description: Every good graph framework should have a standard set of random graph generators with known properties. There are many different random graph models that are used throughout theory. The task is to rework and extend the set of efficient random graph generators in the OGDF. Our target of this project is to build different random graph generators and documentation about them. Every generator should come with a documentation including a brief summary of the properties of the graph model.

Find the complete proposal here.

Search Trees and Priority Queues

Short description: The goal of this project is clearly separate abstract data types from implementing data structures, and identifying and providing various implementing data structures. An important design goal is to focus on efficiency. Implementation of data types PriorityQueue and Dictionary which can use different implementing data structures; implementation of data structures that can be used as implementing data structures for priority queues and dictionaries.

Find the complete proposal here.

Hope I will get the chance to spend summer with OGDF and make good contribution to the open source world.