Tranzitív lezárt

Hatékony algoritmus implementálása egy gráf tranzitív lezártjának előállítására.

Háttér

Egy G=(V,E) irányított gráf tranzitív lezártja az a G' =(V,E' ) gráf, amelyben u-ból v-be pontosan akkor vezet él, ha u-ból vezet irányított út v-be az eredeti G gráfban.

Egy gráf tranzitív lezártja könnyen kiszámítható pl. a Floyd-Warshall-algoritmussal O(n³) időben, illetve n szélességi kereséssel O(n(n+m)) időben. Ugyanakkor vannak lényegesen hatékonyabb módszerek is, amelyek a gyakorlatban majdnem lineáris időben futnak.

Egy ilyen módszer az erősen összefüggő komponensek meghatározásán, valamint a komponensek gráfjának topologikus rendezésén alapul, de összetett adatszerkezeteket is alkalmaz. További információ: ​http://www.cs.hut.fi/~enu/thesis.html

Feladat

A feladat minél hatékonyabb algoritmusok implementálása, valamint a különböző módszerek összehasonlítása.

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.

Kapcsolódó ticketek: #378.

Előfeltételek

• C++ programozási nyelv ismerete
• gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
• angol nyelvismeret