A számítástudományban egy irányított gráf topológiai rendezése a csúcsainak lineáris sorrendje, úgy, hogy minden irányított uv élnél, az u csúcstól a v csúcsig, u előtt v van a sorrendben. Például a gráf csúcsait reprezentálhatják a végrehajtandó feladatokat, és az élek képviselik azokat a korlátozásokat, amelyek szerint az egyik feladatot a másik előtt kell végrehajtani; ebben az alkalmazásban a topológiai rendezés csak egy érvényes sorrend a feladatokhoz. A topológiai rendezés akkor és csak akkor lehetséges, ha a gráfnak nincs köre, azaz ha ez egy irányított körmentes gráf (DAG).

Legyen D = (V, A) irányított gráf. A gráf csúcsainak akkor és csak akkor van olyan sorrendje, amiben minden él előrefelé vezet, ha aciklikus (irányított körmentes gráf). Az ilyen sorrendet topologikus sorrendnek nevezik.

Algoritmus a topologikus sorrend meghatározására

Az algoritmus egy adott s pontból indul. Erről vagy előre ismert, hogy minden pont elérhető belőle, vagy az algoritmus adja hozzá. A gráfba még beteszi az összes sv élet, ahol v eleme V. Minden pontra két címkét tart számon. Az egyik címke azt mutatja, hogy a pont elért-e, és ha igen, akkor melyik csúcsból. A másik címke pedig azt, hogy a csúcs átvizsgált-e, vagy sem. Kezdetben s elért, nem átvizsgált.

Amíg van elért, de nem átvizsgált pont, addig ismétli a következőket:

Kiválasztja a legkésőbb elért, nem átvizsgált u pontot. Eldönti, hogy van-e egy uv él a gráfban, aminek v végpontja nem elért. Ha talál ilyet, akkor átállítja v címkéjét: v elért az u pontból. Ha nem talál, akkor átállítja u címkéjét: u átvizsgált, és feljegyzi a címkébe, hogy éppen hányadik lépésnél tart.

Az átvizsgálási sorrend topologikus sorrendet ad. Ha az s pont nem volt az eredeti gráfban, akkor törli.

Megfelelő adatstruktúrával mindez az élszámmal arányos időt vesz igénybe.

A bal oldalon látható gráfnak több topologikus rendezése is létezik, köztük: 7,5,3,11,8,2,10,9 7,5,11,2,3,10,8,9 3,7,8,5,11,10,9,2 3,5,7,11,10,2,8,9

További algoritmusok

A topológiai rendezés szokásos algoritmusainak futási ideje lineáris a csúcsok számában, plusz az élek száma aszimptotikus módon, ${\displaystyle O(\left|{V}\right|+\left|{E}\right|)}$.

Kahn algoritmusa

Ezen algoritmusok egyike, amelyet először Kahn (1962) írt le, úgy működik, hogy a csúcsokat ugyanolyan sorrendben választja, mint a lehetséges topológiai rendezést. Először megkeresi a "kezdő csúcsok" listáját, amelyeknek nincs bejövő éle, és beilleszti őket egy S halmazba; legalább egy ilyen csúcsnak léteznie kell egy nem üres aciklikus gráfban. Akkor:

L ← Üres lista, amely tartalmazni fogja a rendezett elemeket
S ← Az összes csúcs halmaza bejövő él nélkül

amíg az S nem üres
  távolítson el egy n csúcsot S-ből
  szúrja be n-t az L végére
  ciklus m csúcs egy e éllel n-től m-ig
    távolítsa el az e élet a gráfból
    ha m-nek nincs más bejövő éle, akkor
      illessze be m-t az S-be

ha a gráfnak vannak élei, akkor
  visszatér hiba (a gráfnak legalább egy köre van)
különben
  visszatér L (topológiailag rendezett sorrend)

Ha a gráf egy Irányított körmentes gráf, egy megoldás szerepelni fog az L listában. Ellenkező esetben a gráfnak legalább egy körének kell lennie, ezért a topológiai rendezés lehetetlen.

A kapott rendezés nem egyediségét tükrözve az S struktúra egyszerűen halmaz vagy sor vagy halom lehet. Az n csúcsok eltávolításának sorrendjétől függően az S halmazból eltérő megoldás jön létre. Kahn algoritmusának van olyan variációja, amely lexikográfiailag köti a kapcsolatokat, a Coffman – Graham algoritmus kulcsfontosságú elemét képezi a párhuzamos ütemezés és a hierarchikus gráfrajzolásnak.

Mélységi keresés

A topológiai rendezés alternatív algoritmusa a mélységi keresésen alapszik. Az algoritmus végigmegy a gráf minden egyes csúcsán tetszőleges sorrendben, és elindítja a mélységi keresést, amely akkor fejeződik be, amikor elér egy olyan csúcshoz, amelyet egyszer már meglátogatott a topológiai rendezés kezdete óta, vagy a csúcsnak nincs kimenő éle.

L ← Üres lista, amely tartalmazni fogja a rendezett csúcsokat
amíg létező csúcsok állandó jelölés nélkül
  válasszon egy n jelöletlen csúcsot
  látogat (n)

funkció látogat (csúcs n)
  ha n-nek állandó jelölése van, akkor
    visszatér
  ha n-nek van ideiglenes jelölése, akkor
    stop (nem DAG)

  n jelölése ideiglenes jelöléssel

  ciklus m csúcs egy él n-től m-ig
    látogat (m)

  távolítsa el az ideiglenes jelölést az n-ről
  n jelölés állandó jelöléssel
  illessze be n-t az L elejébe

Minden egyes n csúcs hozzá lesz fűzve az L kimeneti listához miután figyelembe lett véve az összes csúcs, ami függ az n-től. Pontosabban, ha az algoritmus hozzáadja az n csúcsot, akkor garantált, hogy az összes n-től függő csúcs szerepel az L kimeneti listában. Mivel minden él és csúcs egyszer meg lesz látogatva, az algoritmus lineáris futásidejű. Ez a mélységi keresés alapú algoritmus az, amelyet Cormen et al. (2001) írt le; először nyomtatott formában pedig Tarjan (1976).

Párhuzamos algoritmusok

Egy párhuzamos véletlen hozzáférésű gépen, topológiás rendezés készíthető O (log² n) futásidőben, polinomszámú processzor felhasználásával, a problémát az NC² bonyolultsági osztályba sorolva (Cook 1985). Ennek egyik módja az adott gráf szomszédsági mátrixának többszöri négyzete, logaritmikusan sokszor, a min-plus mátrix szorzásának felhasználásával, a minimalizálás helyett maximalizálással. A kapott mátrix a leghosszabb úttávolságokat írja le a gráfban. A csúcsok osztályozása a leghosszabb bejövő út hossza alapján topológiai sorrendet eredményez (Dekel, Nassimi & Sahni 1981).

Az elosztott memóriájú gépeken a párhuzamos topológiai rendezés algoritmusa párhuzamosítja Khan algoritmusát egy DAG-hoz G = (V, E)^[1] Magas szinten Khan algoritmusa többször eltávolítja a 0-ig pontatlan csúcsokat és hozzáadja őket a topológiai rendezéshez azok eltávolításának sorrendjében. Mivel az eltávolított csúcsok kimenő élei is eltávolításra kerülnek, új csúcsok lesznek, amelyek független 0 pontokat mutatnak, ahol az eljárást addig ismételjük, amíg nem maradnak csúcsok. Ez az algoritmus D + 1 iterációt végez, ahol D a leghosszabb út G -ben. Minden iterációt párhuzamosítani lehet, ami a következő algoritmus ötlete.

Az alábbiakban feltételezzük, hogy a gráf partíció a p feldolgozóelemeken (PE) van tárolva, amelyek ${\displaystyle 0,\dots ,p-1}$ -ként vannak feltüntetve. Minden PE i inicializálja a helyi csúcsok halmazát ${\displaystyle Q_{i}^{1}}$ a 0 -fokkal, ahol a felső index jelenti az aktuális iterációt. Mivel az összes csúcs a helyi ${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$halmazokban található 0 -fokkal, azaz nem szomszédosak, tehát tetszőleges sorrendben adhatók meg érvényes topológiai rendezéshez. Hogy hozzárendeljen egy globális indexet minden csúcshoz, egy előtag összeget számol ${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$ méreteiben. Tehát minden lépésben ${\displaystyle \sum _{i=0}^{p-1}|Q_{i}|}$ csúcsok lesznek hozzáadva, a topológiai rendezéshez.

Az első lépésben a PE j hozzárendeli az indexeket ${\displaystyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$-hez a helyi csúcsokra ${\displaystyle Q_{j}^{1}}$-ban . Ezek a csúcsok ${\displaystyle Q_{j}^{1}}$-ban eltávolítja, a hozzájuk tartozó kimenő élekkel együtt. Minden kimenő ${\displaystyle (u,v)}$ élhez v végponttal egy másik PE ${\displaystyle l,j\neq l}$-ben, az ${\displaystyle (u,v)}$üzenet lesz a PE l . Miután az összes csúcs el lett távolítva ${\displaystyle Q_{j}^{1}}$-ből, az üzeneteket elküldik a megfelelő PE-hez. Ezután elindul a következő iteráció.

A k lépésben a PE j jelöli az ${\displaystyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ indexeket , ahol ${\displaystyle a_{k-1}}$ a feldolgozott csúcsok teljes mennyisége a ${\displaystyle k-1}$ lépés után. Ez az eljárás addig ismétlődik, amíg már nem marad több csúcs feldolgozásra, ennélfogva ${\displaystyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$ . Az alábbiakban egy magas szintű, egyetlen program, több adat álnévkód áttekintése található az algoritmusról.

Vegye figyelembe, hogy a helyi eltolások előtag összege ${\displaystyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ hatékonyan kiszámítható párhuzamosan.

p feldolgozó elemek azonosítóval 0-tól p-1-ig
Bemenet: ${\displaystyle G=(V,E)}$ DAG, elosztva a PE-k számára, PE-index ${\displaystyle j\in \{0,\dots ,p-1\}}$
Kimenet: G topológiai rendezése

függvény traverseDAGDistributed
  δ helyi csúcsok bejövő V foka
  Q = { v ∈ V | δ  = 0} // Minden csúcs 0-val független
  feldolgozottCsucsokSzama= 0
  csinál
     globális összeépítési előtag összege a Q méretnél nagyobb // meghatározza az eltolások és a csúcsok teljes számát ebben a lépésben
     eltolt = feldolgozottCsucsokSzama+ ${\displaystyle \sum _{i=0}^{j-1}|Q_{i}|}$ // j a processzor indexe
     ciklus u ∈ Q
       helyiRend = index ++;
       ciklus (u, v) ∈ E utáni üzenet (u, v) a PE birtokló v csúcs
     feldolgozottCsucsokSzama+= ${\displaystyle \sum _{i=0}^{p-1}|Q_{i}|}$
     minden üzenetet továbbít a csúcsok szomszédainak Q-ban
     üzenetek fogadása a helyi V csúcsokra
     eltávolít minden csúcsot Q-ban
     ciklus üzenet (u, v) kapott:
       ha --δ  = 0
         hozzáadja V-t Q-hoz
  amíg Q globális mérete> 0
  visszatérés helyiRend

A kommunikációs költség nagyban függ az adott gráf felosztásától. Ami a futási időt illeti, egy CRCW-PRAM modellnél, amely állandó időben lehetővé teszi a letöltést és csökkentést, ez az algoritmus ${\displaystyle }$Információ forrás: https://hu.wikipedia.org/wiki/Topologikus_sorrend
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.