COIN-OR::LEMON - Graph Library

Changes between Version 7 and Version 8 of GSoC2010Ideas


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

--

Legend:

Unmodified
Added
Removed
Modified
  • GSoC2010Ideas

    v7 v8  
    2727----
    2828
    29 == Multi thread support & thread safe graph maps ==
     29== Multi-thread support & thread safe graph maps ==
    3030mentor: Péter Kovács
    3131
     
    7272
    7373 - knowledge of C++ language
    74  - basic knowledge in graph theory
     74 - basic knowledge of graph theory
    7575 - English language knowledge
    7676
     
    107107
    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.
     109
     110----
     111
     112== Binary graph format ==
     113mentor: Alpár Jüttner
     114
     115=== Background ===
     116
     117LEMON has its own text file format, [http://lemon.cs.elte.hu/pub/doc/1.1.2/lgf-format.html 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).
     118
     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.
     120
     121=== The task ===
     122
     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.
     126
     127Related tickets: #225, #297.
     128
     129=== Application conditions ===
     130
     131 - knowledge of C++ language
     132 - English language knowledge
     133
     134=== Benefits of participating ===
     135
     136By taking part in this project, you can get familiar with the LEMON library, especially with the LGF related tools.