COIN-OR::LEMON - Graph Library

Changes between Version 6 and Version 7 of GSoC2010Ideas


Ignore:
Timestamp:
03/14/10 07:10:29 (10 years ago)
Author:
Peter Kovacs
Comment:

A new topic + improve former ones

Legend:

Unmodified
Added
Removed
Modified
  • GSoC2010Ideas

    v6 v7  
    88LEMON 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++.
    99
    10 === The Task ===
     10=== The task ===
    1111
    1212The 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.
     
    3434Most 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.
    3535
    36 === The Task ===
     36=== The task ===
    3737
    3838 - 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
     
    4646=== Benefits of participating ===
    4747
    48 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.
     48By 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.
     49
     50----
     51
     52== Bipartite graph structures & bipartite matching algorithms ==
     53mentor: Balázs Dezső
     54
     55=== Background ===
     56
     57LEMON contains various data structures for storing undirected and directed graphs and there are matured concepts for them. However, bipartite graphs form a special class of (typically undirected) graphs that needs additional functionalities. These specialities are based on the dividing of the node set into two subsets A and B, for which there is no edge with end points belonging to the same subset. This partition can be calculated by a simple graph search algorithm (BFS) on an undirected graph that is actually bipartite, but the bipartite graph algorithms usually require the partition, so it is worth to store it explicitly. Therefore, we need a special graph concept for the bipartite graphs, that is an extension of the undirected graph concept and we need some bipartite graph implementations. Bipartite matching algorithms are also important to have in the library.
     58
     59The older LEMON versions (0.x releases, up to 0.7) contain implementations of bipartite graphs and bipartite matching algorithms, however, these tools have to be thoroughly revised, reworked and improved to be able to include in the stable 1.x releases. In fact, this task is of high importance for the upcomming release LEMON 1.3.
     60
     61=== The task ===
     62
     63 - Revise the old implementations:
     64    - bipartite graph concept,
     65    - bipartite graph implementations,
     66    - bipartite matching algorithms.
     67 - Rework these implementations or reimplement them from scratch, if it is necessary.
     68
     69Related tickets: #69, #168.
     70
     71=== Application conditions ===
     72
     73 - knowledge of C++ language
     74 - basic knowledge in graph theory
     75 - English language knowledge
     76
     77=== Benefits of participating ===
     78
     79By taking part in this project, you can get familiar with the LEMON library and you can gain a deep insight into the sophisticated implementations of graph concepts and graph structures in LEMON.
    4980
    5081----
     
    5586=== Background ===
    5687
    57 [http://cairographics.org/ 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.
     88[http://cairographics.org/ 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.
    5889
    59 [http://lemon.cs.elte.hu/pub/doc/1.1.2/a00134.html GraphToEps], LEMON's current graph visualizing tool creates an Encapsulated Postscript file by hand. Implementing a similar tool based on [http://cairographics.org/ Cairo] would provide various output formats and easy integration to graphical user interfaces.
     90[http://lemon.cs.elte.hu/pub/doc/1.1.2/a00134.html GraphToEps], LEMON's current graph visualizing tool creates an Encapsulated !PostScript file by hand. Implementing a similar tool based on [http://cairographics.org/ Cairo] would provide various output formats and easy integration to graphical user interfaces.
    6091
    61 === The Task ===
     92=== The task ===
    6293
    6394Develop a tool that provide similar functionality to [http://lemon.cs.elte.hu/pub/doc/1.1.2/a00134.html GraphToEps] but uses the [http://cairographics.org/ Cairo] library for drawing. In order to achieve further flexibility the following changes should be made compared to [http://lemon.cs.elte.hu/pub/doc/1.1.2/a00134.html GraphToEps].
    64  - 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).
    65  - The necessary preprocessing of the graph should be separated to the actual drawing, in order to speed up this latter process.
     95 - The extensive use of named template parameters should be replaced by a mechanism using virtual function calls. (In fact, this will make the code much easier).
     96 - The necessary preprocessing of the graph should be separated from the actual drawing, in order to speed up this latter process.
     97
     98Related tickets: #344, #86, #76, #284.
    6699
    67100=== Application conditions ===
     
    73106=== Benefits of participating ===
    74107
    75 By taking part in this project, you will get familiar with the LEMON library, the basic principles 2D rendering and perhaps with GUI design.
     108By taking part in this project, you will get familiar with the LEMON library and the basic principles 2D rendering and perhaps with GUI design.