Élgráf adatstruktúra

Egy irányítatlan gráf élgráfját megvalósító dinamikus adatstruktúra implementálása.

Háttér

Egy G irányítatlan gráf L(G) élgráfja a G gráf éleinek kapcsolatát reprezentálja. L(G) egy egyszerű irányítatlan gráf, amelynek csúcsai a G élei, és két csúcsot pontosan akkor köt össze él, ha az eredeti gráfban a két él szomszédos (van közös végpontjuk).

Ez a struktúra fontos fontos szerepet tölt be a gráfelméletben és gyakorlati alkalmazásai is vannak. További információ: ​http://en.wikipedia.org/wiki/Line_graph.

Feladat

A LEMON könyvár nagy erőssége, hogy lehetővé teszi algoritmusok futtatását "implicit gráfokon", vagyis olyan strukturákon, amelyek nincsenek fizikailag eltárolva a memóriában.

A jelentkező feladata egy olyan LEMON gráf adatstruktúra implementálása, amely dinamikus módon előállítja egy gráf élgráfját és lehetővé teszi algoritmusok futtatását a kapott gráfon. A "dinamikus" működés azt jelenti, hogy az alapgráf megváltoztatásakor automatikusan megváltozik az élgráf is.

Cél, hogy erre a feladatra hatékony megoldás szülessen és a letisztázott implementáció bekerüljön a LEMON programkönyvtárba.

A feladat elsősorban BSc szakdolgozat alapjául szolgálhat. A célként kitűzött adatstruktúra implementálása kiváló lehetőséget biztosít a LEMON programkönyvtár koncepciójának és felépítésének alapos megismerésére; ez a tudás késöbbiekben alapja lehet egy értékes TDK-, ill. diplomamunkának is.

Kapcsolódó ticket: #237.

Megjegyzés: A téma összevonható egy másik hasonló feladattal: Gráfok direkt szorzata.

Előfeltételek

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