COIN-OR::LEMON - Graph Library

Changes between Version 7 and Version 8 of GSoC2010Ideas

03/14/10 07:54:29 (14 years ago)
Peter Kovacs



  • GSoC2010Ideas

    v7 v8  
    29 == Multi thread support & thread safe graph maps ==
     29== Multi-thread support & thread safe graph maps ==
    3030mentor: Péter Kovács
    7373 - knowledge of C++ language
    74  - basic knowledge in graph theory
     74 - basic knowledge of graph theory
    7575 - English language knowledge
    108108By taking part in this project, you will get familiar with the LEMON library and the basic principles 2D rendering and perhaps with GUI design.
     112== Binary graph format ==
     113mentor: Alpár Jüttner
     115=== Background ===
     117LEMON has its own text file format, [ LGF (LEMON Graph Format)] for storing graphs and related data (typically node and arc maps). This format makes it possible to handle graphs in a convenient and flexible way and it can be easily read and written both by hand and by a program. However, combinatorial optimization tasks usually require working with very large graphs, i.e. graphs containing millions of nodes and arcs. Storing such a huge graph in a text format takes a large amount of space (e.g. several GBs), however compact the format is (not to mention complicated structured formats, such as XML).
     119Therefore, it would be quite useful to have a binary graph format that could provide (almost) the same functionalities as LGF but require much less space. In addition, the reading and writing operations could also be made much faster using such a compact binary format.
     121=== The task ===
     123 - Design an appropriate binary graph format. It could be called e.g. LBF (LEMON Binary Format).
     124 - Develop convenient functions for reading and writing data in this format (with similar interfaces to the LGF tools).
     125 - Develop LGF->LBF and LBF->LGF converter tools.
     127Related tickets: #225, #297.
     129=== Application conditions ===
     131 - knowledge of C++ language
     132 - English language knowledge
     134=== Benefits of participating ===
     136By taking part in this project, you can get familiar with the LEMON library, especially with the LGF related tools.