Topologikus sorrend

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, $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 $0,\dots ,p-1$ -ként vannak feltüntetve. Minden PE $i$ inicializálja a helyi csúcsok halmazát $Q_{i}^{1}$ a 0 -fokkal, ahol a felső index jelenti az aktuális iterációt. Mivel az összes csúcs a helyi $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 $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ méreteiben. Tehát minden lépésben $\sum _{i=0}^{p-1}|Q_{i}|$ csúcsok lesznek hozzáadva, a topológiai rendezéshez.

A párhuzamos topológiai rendezési algoritmus végrehajtása egy DAG-on, két feldolgozó elemmel.

Az első lépésben a PE $j$ hozzárendeli az indexeket $\sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1$ -hez a helyi csúcsokra $Q_{j}^{1}$ -ban . Ezek a csúcsok $Q_{j}^{1}$ -ban eltávolítja, a hozzájuk tartozó kimenő élekkel együtt. Minden kimenő $(u,v)$ élhez $v$ végponttal egy másik PE $l,j\neq l$ -ben, az $(u,v)$ üzenet lesz a PE $l$ . Miután az összes csúcs el lett távolítva $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 $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 $a_{k-1}$ a feldolgozott csúcsok teljes mennyisége a $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 $\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 $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:  $G=(V,E)$  DAG, elosztva a PE-k számára, PE-index  $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 \in 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+  $\sum _{i=0}^{j-1}|Q_{i}|$  // j a processzor indexe
     ciklus  $u \in Q$ 
       helyiRend[u] = index ++;
       ciklus  $(u, v) \in E$  utáni üzenet (u, v) a PE birtokló v csúcs
     feldolgozottCsucsokSzama+=  $\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 --δ [v] = 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 ${\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)$ időben fut le, ahol $D$ ismét a leghosszabb út $G$ -ben és $Δ$ a legnagyobb fok.^[1]

Alkalmazás a legrövidebb útkereséshez

A topológiai rendezés arra is felhasználható, hogy gyorsan kiszámítsuk a legrövidebb útvonalakat egy súlyozott irányított aciklikus gráfon keresztül. Legyen $V$ a csúcsok listája egy ilyen gráfban, topológiai sorrendben. Aztán a következő algoritmus kiszámítja a legrövidebb utat néhány s forrás csúcstól az összes többi csúcsig:^[2]

Legyen $d$ egy tömb, ami ugyanolyan hosszúságú mint $V$ ; ez megtartja a legrövidebb távolságokat az $s$ -től. Legyen $d [s] = 0$ , az összes többi $d [u] = \infty$ .
Legyen $p$ egy tömb, ami ugyanolyan hosszúságú mint $V$ , minden eleme inicializálva nil-ra. Minden $p [u]$ fogja tartani az $u$ -t a legrövidebb úton $s$ -től $u$ -ig.
Végig megy az u csúcsokon a V szerinti sorrendben,kezdve az s-el:
- Minden v csúcs közvetlenül követi u-t (azaz ha létezik él u-tól v-ig):
  - Legyen $w$ az élek súlya $u$ -tól $v$ -ig.
  - Pihenjen az él: ha d[v] > d[u] + w, legyen
    - $d [v] \leftarrow d [u] + w$ ,
    - $p [v] \leftarrow u$ .

Egy n csúcsú, m élű gráfon ez az algoritmus $Θ(n + m)$ futásidejű, azaz lineáris időt vesz igénybe. ^[2]

Egyediség

Ha egy topológiai rendezésnek az a tulajdonsága, hogy az egymást követő csúcsok összes párját rendezett sorrendben élek kötik össze, akkor ezek az élek irányított Hamilton-utat képeznek a DAG-ban. Ha létezik Hamilton-út, akkor a topológiai rendezési sorrend egyedi; egyetlen más rend sem tartja tiszteletben az élek szélét. Ezzel szemben, ha egy topológiai rendezés nem alkot Hamilton-utat a DAG-nak két vagy több érvényes topológiai sorrendje lesz, mert ebben az esetben mindig lehetséges egy második érvényes sorrend kialakítása két egymást követő csúcs cseréjével, amelyek nem kapcsolódnak egy éllel egymáshoz. Ezért lineáris időben meg lehet vizsgálni, hogy létezik-e egyedi sorrend, és létezik-e Hamilton-út, annak ellenére hogy NP-nehézsége a Hamilton-út problémának az általános irányítású gráfok esetében(Vernet & Markenzon 1997).

Kapcsolat részleges rendezésekhez

A topológiai rendezések szorosan kapcsolódnak a részben rendezett halmazok lineáris kiterjesztéséhez a matematikában. Magas szintű különbség van az irányított gráfok és a részleges sorrend között.^[3]

A részlegesen rendezett halmaz csak egy objektumkészlet, a "≤" egyenlőtlenségi reláció meghatározásával együtt, amely kielégíti a reflexivitás axiómáit (x ≤ x), antiszimmetriáit (ha x ≤ y és y ≤ x, majd x = y) és tranzitivitását (ha x ≤ y és y ≤ z, majd x ≤ z). A teljes megrendelés egy részleges sorrend, amelyben minden két objektum x és y a beállított, vagy X ≤ y vagy y ≤ x . Az összes megrendelés ismeretes a számítástechnikában, mivel az összehasonlító operátoroknak szükségük volt az összehasonlító rendezési algoritmusok végrehajtására. A véges halmazok esetén az összes sorrend objektumok lineáris sorozatával azonosítható, ahol a "≤" kapcsolat igaz, amikor az első objektum megelőzi a második objektumot a sorrendben; egy összehasonlító rendezési algoritmust lehet használni a teljes rendelés szekvenciává konvertálására. A részleges sorrend lineáris kiterjesztése egy olyan teljes sorrend, amely kompatibilis azzal, abban az értelemben, hogy ha x ≤ y részleges sorrendben, majd x ≤ y is teljes sorrendben.

Bármely DAG-ból meg lehet határozni a részleges rendezést úgy, hogy az objektumkészlet a DAG csúcsa lesz, és a meghatározott x ≤ y-nak igaznak kell lennie bármelyik két x és y csúcs esetében, ha létezik egy irányított út az x és y között ; vagyis amikor y elérhető x-től . Ezekkel a meghatározásokkal a DAG topológiai rendezése ugyanaz, mint ennek a részleges sorrendnek a lineáris kiterjesztése. Ezzel szemben a véges készlet bármely részleges rendezése meghatározható a DAG-ban elérhető elérhetőségi viszonyként. Ennek egyik módja egy olyan DAG meghatározása, amelynek csúcsa van minden objektumhoz a részlegesen elrendezett halmazban, és van xy éle minden olyan objektumpárnak, amelyre x ≤ y igaz. Ennek alternatív módja a részleges rendezés tranzitív redukciójának használata; általánosságban ez kevesebb élű DAG-okat eredményez, de ezekben a DAG-okban az elérhetőségi viszony továbbra is ugyanaz a részleges sorrend. Ezen konstrukciók felhasználásával topológiai rendezési algoritmusok használhatók a részleges sorrend lineáris kiterjesztéseinek megtalálására.

További információk

tsort, egy Unix program a topológiai rendezésre
Visszacsatoló élhalmaz : élek sorozata, amelynek eltávolítása lehetővé teszi a fennmaradó algráf topológiás rendezését
Tarjan szorosan összekapcsolt összetevőinek algoritmusa, egy olyan algoritmus, amely grafikonon mutatja az erősen összekapcsolt összetevők topológiailag rendezett listáját
Pre-topológiai sorrend

Források

↑ ^a ^b Sanders, Peter. Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox (angol nyelven). Springer International Publishing (2019. november 2.). ISBN 978-3-030-25208-3
↑ ^a ^b Introduction to Algorithms, 655–657. o.
↑ Spivak, David I.. Category Theory for the Sciences. MIT Press (2014. november 2.)

Cook, Stephen A. (1985), "A Taxonomy of Problems with Fast Parallel Algorithms", Information and Control, 64 (1–3): 2–22, doi:10.1016/S0019-9958(85)80041-3.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Section 22.4: Topological sort", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 549–552, ISBN 0-262-03293-7.
Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981), "Parallel matrix and graph algorithms", SIAM Journal on Computing, 10 (4): 657–675, doi:10.1137/0210049, MR 0635424.
Jarnagin, M. P. (1960), Automatic machine methods of testing PERT networks for consistency, Technical Memorandum No. K-24/60, Dahlgren, Virginia: U. S. Naval Weapons Laboratory.
Kahn, Arthur B. (1962), "Topological sorting of large networks", Communications of the ACM, 5 (11): 558–562, doi:10.1145/368996.369025.
Tarjan, Robert E. (1976), "Edge-disjoint spanning trees and depth-first search", Acta Informatica, 6 (2): 171–185, doi:10.1007/BF00268499.
Vernet, Oswaldo; Markenzon, Lilian (1997), "Hamiltonian problems for reducible flowgraphs", Proc. 17th International Conference of the Chilean Computer Science Society (SCCC '97) (PDF), pp. 264–267, doi:10.1109/SCCC.1997.637099.
http://www.cs.elte.hu/~frank/jegyzet/opkut/ulin.2008.pdf

További irodalom

DE Knuth, A számítógépes programozás művészete, 1. kötet, 2.2.3. szakasz, amely algoritmust ad a részleges topológiai rendezésekhez és egy rövid történetet tartalmaz.

Külső linkek

NIST Dictionary of Algorithms and Data Structures: topological sort
Weisstein, Eric W.: TopologicalSort (angol nyelven). Wolfram MathWorld

[:0-1] Sanders, Peter. Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox (angol nyelven). Springer International Publishing (2019. november 2.). ISBN 978-3-030-25208-3

[clrs-2] Introduction to Algorithms, 655–657. o.

[3] Spivak, David I.. Category Theory for the Sciences. MIT Press (2014. november 2.)

[1]

[2]

[3]