Bináris formátum gráfok tárolására

Egy általános bináris fájlformátum kidolgozása gráfok tárolásához, valamint megfelelő kezelőfüggvények implementálása.

Megjegyzés: A témakörön már dolgozik szakdolgozó, ezért a részletekről érdemes érdeklődni.

Háttér

Az LGF (LEMON Graph Format) gráfok és hozzájuk tartozó adatok (tipikusan node és arc map-ek) kényelmes és rugalmas tárolását, kezelését teszi lehetővé. Ez egy egyszerű, szöveges formátum, így könnyen szerkeszthető akár programmal, akár "kézzel". Ha azonban rendkívül nagy gráfokat akarunk tárolni (pl. több millió csúcs és/vagy él van), akkor ez a formátum (tömörsége ellenére is) nagy méretű fájlokat eredményez.

Ezért hasznos lenne egy olyan bináris formátum is (pl. LBF - LEMON Binary Format), amely funkcionalitását tekintve lényegében ekvivalens az LGF-fel, de jóval kisebb fájlméretet eredményez.

Feladat

A jelentkezők feladata egy alkalmas bináris fájlformátum kidolgozása, valamint az LGF formátumot kezelő osztályokhoz/függvényekhez hasonló eszközök implementálása. Hasznos lenne továbbá automatikus LGF->LBF és LBF->LGF konvertáló programok készítése is. Cél, hogy ezen feladatokra hatékony megoldások szülessenek és a letisztázott implementációk bekerüljenek a LEMON programkönyvtárba.

A feladatkör BSc/MSc szakdolgozat alapjául is szolgálhat.

Kapcsolódó ticketek: #225, #297.

Előfeltételek

• C++ programozási nyelv ismerete
• alap gráfelméleti ismeretek
• angol nyelvismeret