GSoC 2010 Project Ideas

PyLemon Module

mentor: Alpár Jüttner

Background

LEMON was written in C++, because this is the only widely used programming language that makes is possible to optimize the running time and memory usage of complex data-structures and algorithms to the extreme. However C++ is a rather complex language, which require deep knowledge of programming, and it's usage is many times complicated. Experimenting with and idea and prototyping solution can be much simpler in modern interpreted and dynamically linked languages. Python is a prominent member of these languages, being easy-to-learn, versatile and extremely productive. Python is also a highly extensible language, which allows programmers to create their own modules in C or C++.

The Task

The goal is to create a Python interface module to LEMON's data structures and algorithms (written in C++), thus combine the high efficiency of LEMON with the flexibility of Python.

You can find the pre-alpha version of this project in our repository: ​http://lime.cs.elte.hu/~alpar/hg/pylemon/

Application conditions

• knowledge of C++ language
• knowledge of Python language or have a tendency to learn it
• basic knowledge of graph theory
• English language knowledge

Benefits of participating

By taking part in this project, you can highly improve both your C++ and Python skills. In addition, understanding LEMON is a good opportunity to learn more about network modeling, graph algorithms and combinatorial optimization.

Multi thread support & thread safe graph maps

mentor: Péter Kovács

Background

Most LEMON data structures provides thread safety in the usual sense (i.e. they can be safely created in parallel and the read operation is also safe until no one tries to write it in the same time). There is however a very important exception - the default graph maps. The reason is that these data structures must register themselves at the underlying graph in order to be notified about the changes. For thread safety, a locking mechanism is necessary here to prevent race condition.

The Task

• Develop a basic API for the most usual threading building blocks (such as mutex semaphore etc). It must be easy-to-use and should be usable on different platforms and with different threading library. Consider using existing open source library, but any external dependence must be optional
• Implement a locking mechanism into the graph event notifiers.

Application conditions

• knowledge of C++ language
• English language knowledge

Benefits of participating

By taking part in this project, you can get familiar with the LEMON library, and principles of concurrent programming - a soon to be fundamental paradigm in practical operations research and optimization.

Cairo based graph visualization

mentor: Alpár Jüttner

Background

​Cairo is a 2D graphics library with support for multiple output devices, including PostScript?, PDF, and SVG file output and also direct display rendering under various operating systems.

GraphToEps, LEMON's current graph visualizing tool creates an Encapsulated Postscript file by hand. Implementing a similar tool based on ​Cairo would provide various output formats and easy integration to graphical user interfaces.

The Task

Develop a tool that provide similar functionality to GraphToEps but uses the ​Cairo library for drawing. In order to achieve further flexibility the following changes should be made compared to GraphToEps.

• The extensive use of named template parameters should be replaces by a mechanism using virtual function calls. (In fact, this will make the code much easier).
• The necessary preprocessing of the graph should be separated to the actual drawing, in order to speed up this latter process.

Application conditions

• knowledge of C++ language
• basic knowledge of graph theory
• English language knowledge

Benefits of participating

By taking part in this project, you will get familiar with the LEMON library, the basic principles 2D rendering and perhaps with GUI design.