Topologikus sorrend forrásának megtekintése

A [[számítástudomány]]ban egy irányított gráf '''topológiai rendezése''' a [[Csúcs (gráfelmélet)|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ör (gráfelmélet)|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 sorrend'''nek 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áf]]ba 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úra|adatstruktúrával]] mindez az élszámmal arányos időt vesz igénybe.

{|
| [[Fájl:Directed_acyclic_graph_2.svg|balra|180x180px]]
| 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, <math>O(\left|{V}\right| + \left|{E}\right|)</math>.

=== 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és]]en 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<sup>2</sup> ''n'') futásidőben, polinomszámú processzor felhasználásával, a problémát az NC<sup>2</sup> bonyolultsági osztályba sorolva {{Harvard citation|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 {{Harvard citation|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 [[Irányított körmentes gráf|DAG-hoz]] ''G'' = (''V'', ''E'')<ref name=":0">{{Hivatkozás/Könyv |last=Sanders |first=Peter |title=Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox |url=https://www.springer.com/gp/book/9783030252083 |date=2019 |publisher=Springer International Publishing |language=en |isbn=978-3-030-25208-3}}</ref> 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 {{Mvar|D}} a leghosszabb út {{Mvar|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 {{Mvar|p}} feldolgozóelemeken (PE) van tárolva, amelyek <math>0, \dots, p-1</math> -ként vannak feltüntetve. Minden PE {{Mvar|i}} inicializálja a helyi csúcsok halmazát <math>Q_i^1</math> a 0 -fokkal, ahol a felső index jelenti az aktuális iterációt. Mivel az összes csúcs a helyi <math>Q_0^1, \dots, Q_{p-1}^1</math>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 <math>Q_0^1, \dots, Q_{p-1}^1</math> méreteiben. Tehát minden lépésben <math>\sum_{i=0}^{p-1} |Q_i|</math> csúcsok lesznek hozzáadva, a topológiai rendezéshez.

[[Fájl:Parallel_Topological_Sorting.gif|bélyegkép|jobbra|300x300px|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 {{Mvar|j}} hozzárendeli az indexeket <math>\sum_{i=0}^{j-1} |Q_i^1|, \dots, \left(\sum_{i=0}^{j} |Q_i^1|\right) - 1</math>-hez a helyi csúcsokra <math>Q_j^1</math>-ban . Ezek a csúcsok <math>Q_j^1</math>-ban eltávolítja, a hozzájuk tartozó kimenő élekkel együtt. Minden kimenő <math>(u, v)</math> élhez {{Mvar|v}} végponttal egy másik PE <math>l, j \neq l</math>-ben, az <math>(u, v)</math>üzenet lesz a PE {{Mvar|l}} . Miután az összes csúcs el lett távolítva <math>Q_j^1</math>-ből, az üzeneteket elküldik a megfelelő PE-hez. Ezután elindul a következő iteráció.

A {{Mvar|k}} lépésben a PE {{Mvar|j}} jelöli az <math>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</math> indexeket , ahol <math>a_{k-1}</math> a feldolgozott csúcsok teljes mennyisége a <math>k-1</math> 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 <math>\sum_{i=0}^{p-1} |Q_i^{D+1}| = 0</math> . 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 <math>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</math> hatékonyan kiszámítható párhuzamosan.

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

 '''függvény''' traverseDAGDistributed
   δ helyi csúcsok bejövő V foka
   <span class="texhtml">''Q'' = { ''v'' ∈ ''V'' | δ [ ''v'' ] = 0}</span> <u>// Minden csúcs 0-val független</u>
   feldolgozottCsucsokSzama= 0
   '''csinál'''
      '''globális''' összeépítési előtag összege a ''Q'' méretnél nagyobb <u>// meghatározza az eltolások és a csúcsok teljes számát ebben a lépésben</u>
      eltolt = feldolgozottCsucsokSzama+ <math>\sum_{i=0}^{j - 1} |Q_i|</math> <u>// ''j'' a processzor indexe</u>
      '''ciklus''' {{Math|''u'' ∈ ''Q''}}
        helyiRend[u] = index ++;
        '''ciklus''' {{Math|(''u, v'') ∈ ''E''}} utáni üzenet ''(u, v)'' a PE birtokló ''v'' csúcs
      {{Nowrap|1=feldolgozottCsucsokSzama+= <math>\sum_{i=0}^{p - 1} |Q_i|</math>}}
      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 <math>\mathcal{O} \left(\frac{m + n}{p} + D (\Delta + \log n)\right)</math> időben fut le, ahol {{Mvar|D}} ismét a leghosszabb út {{Mvar|G}}-ben és {{Mvar|&Delta;}} a legnagyobb fok.<ref name=":0"/>

== Alkalmazás a legrövidebb útkereséshez ==
A topológiai rendezés arra is felhasználható, hogy gyorsan kiszámítsuk a [[Legrövidebb út probléma|legrövidebb útvonalakat]] egy [[Gráfelméleti fogalomtár|súlyozott]] irányított aciklikus gráfon keresztül. Legyen {{Mvar|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:<ref name="clrs">{{Hivatkozás/Könyv|title=Introduction to Algorithms|3|pages=655–657}}</ref>

<div style="margin-left: 35px; width: 600px">
{{Színkeret|blue}}
* Legyen {{Mvar|d}} egy tömb, ami ugyanolyan hosszúságú mint {{Mvar|V}}; ez megtartja a legrövidebb távolságokat az {{Mvar|s}}-től. Legyen {{Math|''d''[''s''] {{=}} 0}}, az összes többi {{Math|''d''[''u''] {{=}} ∞}}.
* Legyen {{Mvar|p}} egy tömb, ami ugyanolyan hosszúságú mint {{Mvar|V}}, minden eleme inicializálva {{Mono|nil}}-ra. Minden {{Math|''p''[''u'']}} fogja tartani az {{Math|''u''}}-t a legrövidebb úton {{Mvar|s}}-től {{Mvar|u}}-ig.
* Végig megy az {{Mvar|u}} csúcsokon a {{Mvar|V}} szerinti sorrendben,kezdve az {{Mvar|s}}-el:
** Minden {{Mvar|v}} csúcs közvetlenül követi {{Mvar|u}}-t (azaz ha létezik él {{Mvar|u}}-tól {{Mvar|v}}-ig):
*** Legyen {{Mvar|w}} az élek súlya {{Mvar|u}}-tól {{Mvar|v}}-ig.
*** Pihenjen az él: ha {{Math|''d''[''v''] > ''d''[''u''] + ''w''}}, legyen
**** {{Math|''d''[''v''] ← ''d''[''u''] + ''w''}},
**** {{Math|''p''[''v''] ← ''u''}}.
{{Színkeret vége}}
</div>

Egy n csúcsú, m élű gráfon ez az algoritmus {{Math|Θ(''n'' + ''m'')}} futásidejű, azaz lineáris időt vesz igénybe. {{R|clrs}}

== 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-út|Hamilton-utat]] képeznek a [[Irányított körmentes gráf|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{{Harvard citation|Vernet|Markenzon|1997}}.

== Kapcsolat részleges rendezésekhez ==
A topológiai rendezések szorosan kapcsolódnak a [[Részbenrendezett halmaz|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.<ref>{{Hivatkozás/Könyv |last=Spivak |first=David I. |title=Category Theory for the Sciences |date=2014 |publisher=MIT Press}}</ref>

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 [[Tranzitív reláció|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 [[Útgráf|irányított út]] az ''x'' és ''y között'' ; vagyis amikor ''y'' [[Elérhetőségi reláció|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-algoritmus|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 ==
{{Reflist}}

* 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 ==
* [[Donald Knuth|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 ==
* [https://xlinux.nist.gov/dads/HTML/topologicalSort.html NIST Dictionary of Algorithms and Data Structures: topological sort]
* {{MathWorld|urlname=TopologicalSort|title=TopologicalSort}}

[[Kategória:Irányított gráfok]]
[[Kategória:Rendezési algoritmusok]]
[[Kategória:Gráfalgoritmusok]]