Topológiai rendezés - Topological sorting

A számítástechnika , a topológiai rendezés vagy topológiai rendelés egy irányított gráf egy lineáris rendezés annak csúcsait olyan, hogy minden irányított él uv csúcsból induló u a vertex v , u előtt jön v a rendelés. Például a gráf csúcsai az elvégzendő feladatokat jelenthetik, az élek pedig azokat a korlátozásokat, amelyeket az egyik feladatnak a másik előtt kell végrehajtania; ebben az alkalmazásban a topológiai rendezés csak érvényes sorrend a feladatokhoz. Pontosan a topológiai rendezés egy gráfbejárás, amelyben minden v csomópont csak az összes függőségének megtekintése után látogatható meg . A topológiai rendezés akkor és csak akkor lehetséges, ha a gráfnak nincs irányított ciklusa , azaz ha irányított aciklikus gráf (DAG). Bármely DAG rendelkezik legalább egy topológiai sorrenddel, és ismert algoritmusok bármely DAG topológiai rendezésének lineáris időbeli létrehozására . A topológiai rendezésnek számos alkalmazása van, különösen a rangsorolási problémákban, például a visszacsatolásos ívkészletben . A topológiai rendezés akkor is lehetséges, ha a DAG leválasztotta az alkatrészeket .

Példák

A topológiai rendezés kanonikus alkalmazása a feladatok vagy feladatok sorozatának ütemezése függőségeik alapján . A feladatokat csúcsok jelölik, és x -től y -ig terjedő él van , ha az x feladatot el kell végezni, mielőtt az y feladatot el lehet kezdeni (például ruhák mosásakor a mosógépnek be kell fejeznie, mielőtt a ruhákat a szárítóba helyezzük) . Ezután egy topológiai rendezés parancsot ad a feladatok elvégzésére. A topológiai rendezési algoritmusok szorosan kapcsolódó alkalmazását először az 1960 -as évek elején tanulmányozták a projektmenedzsment ütemezésére szolgáló PERT technika keretében . Ebben az alkalmazásban a gráf csúcsai a projekt mérföldköveit, az élek pedig az egyik és a másik mérföldkő között végrehajtandó feladatokat jelentik. A topológiai rendezés lineáris idejű algoritmusok alapját képezi a projekt kritikus útvonalának megtalálásához , mérföldkövek és feladatok sorozata, amely szabályozza a teljes projekt ütemtervét.

Számítástechnika, alkalmazás ilyen típusú felmerülő használati ütemezését , rendelés képletű sejt értékeléssel újra kiszámításának képlet értékeket táblázatok , logikai szintézis , meghatározó nagyságrendű összeállítása feladataik vannak makefiles adatok sorszámozás , és megoldása szimbólum függőségek kapcsolókat . Arról is döntenek, hogy milyen sorrendben kell betölteni a táblákat idegen kulcsokkal az adatbázisokban.

A bal oldalon látható grafikon számos érvényes topológiai típust tartalmaz, többek között:

5, 7, 3, 11, 8, 2, 9, 10 (vizuálisan fentről lefelé, balról jobbra)
3, 5, 7, 8, 11, 2, 9, 10 (először a legkisebb számú elérhető csúcs)
5, 7, 3, 8, 11, 10, 9, 2 (először a legkevesebb él)
7, 5, 11, 3, 10, 8, 9, 2 (először a legnagyobb számú elérhető csúcs)
5, 7, 11, 2, 3, 8, 9, 10 (felülről lefelé, balról jobbra próbálkozás)
3, 7, 8, 5, 11, 10, 2, 9 (tetszőleges)

Algoritmusok

A topológiai rendezéshez használt szokásos algoritmusok lineáris futási időt mutatnak a csomópontok számában és az élek számában, aszimptotikusan, ${\ displaystyle O (\ bal | {V} \ jobb |+\ bal | {E} \ jobb |).}$

Kahn algoritmusa

Az egyik ilyen algoritmus, amelyet először Kahn (1962) írt le, úgy működik, hogy a csúcsokat ugyanabban a sorrendben választja ki, mint az esetleges topológiai rendezést. Először keressen egy listát a "kezdő csomópontokról", amelyeknek nincs bejövő éle, és illessze be őket egy S halmazba; legalább egy ilyen csomópontnak léteznie kell egy nem üres aciklikus gráfban. Azután:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else 
    return L   (a topologically sorted order)

Ha a grafikon DAG , akkor egy megoldás szerepel az L listában (a megoldás nem feltétlenül egyedi). Ellenkező esetben a gráfnak legalább egy ciklusnak kell lennie, ezért a topológiai rendezés lehetetlen.

A kapott rendezés nem egyediségét tükröző S szerkezet egyszerűen lehet egy halmaz, egy sor vagy egy halom. Attól függően, hogy milyen sorrendben távolítják el az n csomópontokat az S halmazból, más megoldás jön létre. Kahn algoritmusának egy változata, amely lexikográfiailag megszakítja a kapcsolatokat , a Coffman – Graham algoritmus kulcsfontosságú összetevője a párhuzamos ütemezéshez és a réteges gráfrajzhoz .

Mélység-első keresés

A topológiai rendezés alternatív algoritmusa a mélység-első keresésen alapul . Az algoritmus tetszőleges sorrendben végigmegy a gráf minden csomópontján, és mélység-első keresést kezdeményez, amely akkor fejeződik be, amikor a topológiai rendezés kezdete óta már meglátogatott bármely csomópontot eléri, vagy ha a csomópontnak nincs kimenő éle (pl. levél csomópont):

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

Minden egyes csomópont n gets fűzve a kimeneti lista L csak figyelembe véve az összes többi csomópont, amely attól függ, N (összes leszármazottai n a gráfban). Pontosabban, ha az algoritmus hozzáadja az n csomópontot , garantáljuk, hogy az összes n -től függő csomópont már szerepel az L kimeneti listában: az L -hez hozzáadásra került vagy a rekurzív call to visit () hívással, amely az n -es látogatás előtt fejeződött be , vagy látogató hívással (), amely még a n . Mivel minden él és csomópont egyszer meglátogatásra kerül, az algoritmus lineáris időben fut. Ezt a mélység-első keresésen alapuló algoritmust írja le Cormen és mtsai. (2001) ; úgy tűnik, először Tarjan írta le nyomtatásban 1976 -ban.

Párhuzamos algoritmusok

Egy párhuzamos véletlen hozzáférésű gépen O (log ² n ) időben topológiai sorrendet lehet konstruálni polinomszámú processzor segítségével, a problémát az NC ² komplexitási osztályba helyezve . Ennek egyik módja az, hogy az adott gráf szomszédsági mátrixát többször logaritmikusan négyzetre kell helyezni, min-plus mátrixszorzást használva, a minimalizálás helyett maximalizálással. A kapott mátrix leírja a gráf leghosszabb útvonalait . A csúcsok rendezése a leghosszabb bejövő útvonalak hossza szerint topológiai rendezést eredményez.

Az elosztott memóriagépeken végzett párhuzamos topológiai rendezés algoritmusa párhuzamosítja Kahn algoritmusát a DAG számára . Magas szinten Kahn algoritmusa többször eltávolítja a 0 fokú 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ő szélei is eltávolításra kerülnek, új 0 -as csúcshalmaz lesz, ahol az eljárást addig ismételjük, amíg nem maradnak csúcsok. Ez az algoritmus iterációkat hajt végre , ahol $D$ a $G$ leghosszabb útja . Minden iteráció párhuzamosítható, ami a következő algoritmus ötlete. ${\ displaystyle G = (V, E)}$ ${\ displaystyle D+1}$

A következőkben azt feltételezzük, hogy a gráfpartíciót $p$ feldolgozó elemeken (PE) tárolják, amelyek meg vannak jelölve . Mindegyik PE $i$ inicializálja egy sor helyi csúcsok a -foka 0, ahol a felső index jelenti az aktuális iterációban. Mivel a helyi halmazok minden csúcsa 0 -val rendelkezik, azaz nem szomszédosak, tetszőleges sorrendben megadhatók az érvényes topológiai rendezéshez. Ahhoz, hogy minden csúcshoz globális indexet rendeljen, az előtag összege kiszámításra kerül a . Tehát minden lépésben vannak csúcsok a topológiai rendezéshez. ${\ displaystyle 0, \ dots, p-1}$ ${\ displaystyle Q_ {i}^{1}}$ ${\ displaystyle Q_ {0}^{1}, \ pöttyök, Q_ {p-1}^{1}}$ ${\ displaystyle Q_ {0}^{1}, \ pöttyök, Q_ {p-1}^{1}}$ ${\ texttyle \ sum _ {i = 0}^{p-1} | Q_ {i} |}$

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

Az első lépésben a PE $j$ hozzárendeli az indexeket a helyi csúcsokhoz . Ezeket a csúcsokat eltávolítjuk a hozzájuk tartozó kimenő élekkel együtt. Minden kimenő élhez, amelynek $v$ végpontja van egy másik PE -ben , az üzenet a PE $l -be kerül$ . Miután eltávolította az összes csúcsot , a közzétett üzeneteket elküldi a megfelelő PE -nek. Minden fogadott üzenet frissíti a $v$ . Ha az indegree nullára csökken, akkor a $v$ hozzáadódik . Ezután kezdődik a következő iteráció. ${\ texttyle \ sum _ {i = 0}^{j-1} | Q_ {i}^{1} |, \ pöttyök, \ bal (\ sum _ {i = 0}^{j} | Q_ {i }^{1} | \ jobb) -1}$ ${\ displaystyle Q_ {j}^{1}}$ ${\ displaystyle Q_ {j}^{1}}$ ${\ displaystyle (u, v)}$ ${\ displaystyle l, j \ neq l}$ ${\ displaystyle (u, v)}$ ${\ displaystyle Q_ {j}^{1}}$ ${\ displaystyle (u, v)}$ ${\ displaystyle Q_ {j}^{2}}$

A $k$ lépésben a PE $j$ hozzárendeli az indexeket , ahol a lépés után a feldolgozott csúcsok teljes mennyisége . Ez az eljárás addig ismétlődik, amíg nincsenek feldolgozandó csúcsok . Az alábbiakban ennek az algoritmusnak a magas szintű, egyetlen program, több adat pszeudo kód áttekintése található. ${\ texttyle a_ {k-1}+\ sum _ {i = 0}^{j-1} | Q_ {i}^{k} |, \ pontok, a_ {k-1}+\ bal (\ összeg _ {i = 0}^{j} | Q_ {i}^{k} | \ right) -1}$ ${\ displaystyle a_ {k-1}}$ ${\ displaystyle k-1}$ ${\ texttyle \ sum _ {i = 0}^{p-1} | Q_ {i}^{D+1} | = 0}$

Megjegyezzük, hogy a prefix összeget a helyi eltolások hatékonyan lehet kiszámítani párhuzamosan. ${\ texttyle a_ {k-1}+\ sum _ {i = 0}^{j-1} | Q_ {i}^{k} |, \ pontok, a_ {k-1}+\ bal (\ összeg _ {i = 0}^{j} | Q_ {i}^{k} | \ right) -1}$

p processing elements with IDs from 0 to p-1
Input: G = (V, E) DAG, distributed to PEs, PE index j = 0, ..., p - 1
Output: topological sorting of G

function traverseDAGDistributed
    δ incoming degree of local vertices V
     $Q = {v \in V | δ[v] = 0}$                      // All vertices with indegree 0
    nrOfVerticesProcessed = 0

    do                 
        global build prefix sum over size of Q     // get offsets and total amount of vertices in this step
        offset = nrOfVerticesProcessed + sum(Q_i, i = 0 to j - 1)          // j is the processor index
        foreach u in Q                                       
            localOrder[u] = index++;
            foreach (u,v) in E do post message (u, v) to PE owning vertex v
        nrOfVerticesProcessed += sum(|Q_i|, i = 0 to p - 1)
        deliver all messages to neighbors of vertices in Q  
        receive messages for local vertices V
        remove all vertices in Q
        foreach message (u, v) received:
            if --δ[v] = 0
                add v to Q
    while global size of Q > 0

    return localOrder

A kommunikációs költség nagymértékben függ az adott gráfpartíciótól. Ami a futásidőt illeti, egy CRCW-PRAM modellnél, amely lehetővé teszi a lekérést és csökkentést állandó időben, ez az algoritmus fut be , ahol $D$ ismét a leghosszabb út $G-ben$ és $Δ$ a maximális fok. ${\ texttyle {\ mathcal {O}} \ left ({\ frac {m+n} {p}}+D (\ Delta+\ log n) \ right)}$

Alkalmazás a legrövidebb útkereséshez

A topológiai rendezés arra is használható, hogy gyorsan kiszámítsuk a legrövidebb utakat 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. Ezután a következő algoritmus kiszámítja a legrövidebb utat az egyes $s$ forráscsúcsoktól az összes többi csúcsig :

Legyen $d$ $V -vel$ azonos hosszúságú tömb ; ez tartja a legrövidebb útvonalakat $s-től$ . Állítsa be a $d [s] = 0$ , az összes többi $d [u] = \infty beállítást$ .
Legyen $p$ egy $V -vel$ azonos hosszúságú tömb , minden elem nullára inicializálva . Mindegyik $p [u]$ az $u$ elődjét fogja tartani az $s$ és $u közötti$ legrövidebb úton .
Hurkolja át az u csúcsokat V -ben rendelt módon , az s -től kezdve :
- Minden u pontot követő $v$ csúcsra (azaz van egy él u -tól v
  -ig ):
  - Legyen $w$ az él súlya $u$ -tól $v$ -ig .
  - Lazítsa el az élét: ha d [ v ]> d [ u ] + w , állítsa be
    - $d [v] \leftarrow d [u] + w$ ,
    - $p [v] \leftarrow u$ .

Egyenértékűen:

Legyen $d$ $V -vel$ azonos hosszúságú tömb ; ez tartja a legrövidebb útvonalakat $s-től$ . Állítsa be a $d [s] = 0$ , az összes többi $d [u] = \infty beállítást$ .
Legyen $p$ egy $V -vel$ azonos hosszúságú tömb , minden elem nullára inicializálva . Mindegyik $p [u]$ az $u$ elődjét fogja tartani az $s$ és $u közötti$ legrövidebb úton .
Hurkolja át az u csúcsokat V -ben rendelt módon , az s -től kezdve :
- Minden v csúcsra u -ba (azaz van egy él v -től u -ig ):
  - Legyen $w$ az él súlya $v$ -től $u$ -ig .
  - Lazítsa el az élét: ha d [ u ]> d [ v ] + w , állítsa be
    - $d [u] \leftarrow d [v] + w$ ,
    - $p [u] \leftarrow v$ .

Egy $n$ csúcsból és $m$ élből álló gráfon ez az algoritmus $Θ (n + m)$ , azaz lineáris időt vesz igénybe .

Egyediség

Ha egy topológiai rendezésnek megvan az a tulajdonsága, hogy a rendezett sorrendben minden egymást követő csúcspár élekkel van összekötve, 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; más sorrend nem tartja tiszteletben az út széleit. Ezzel szemben, ha egy topológiai rendezés nem képez Hamilton -útvonalat, a DAG -nak két vagy több érvényes topológiai sorrendje lesz, mivel ebben az esetben mindig lehetséges egy második érvényes sorrend kialakítása két egymást követő csúcs felcserélésével, amelyeket nem köt össze éle egymáshoz. Ezért lineáris idő alatt tesztelhető, hogy létezik-e egyedi rendezés, és létezik-e Hamilton-útvonal, annak ellenére, hogy általánosabb irányú gráfok esetében (azaz ciklikusan irányított gráfok) a Hamilton-út problémájának NP-keménysége van.

Részleges megrendelésekhez való viszony

Topológiai megrendeléseknek is szorosan kapcsolódik a fogalom a lineáris kiterjesztése egy parciális rendezés a matematikában. A részben rendezett halmaz csak objektumok halmaza az "≤" egyenlőtlenségi reláció definíciójával együtt, kielégítve a reflexivitás ( x ≤ x ), az antiszimmetria (ha x ≤ y és y ≤ x, akkor x = y ) és a tranzitivitás axiómáját (ha x ≤ y és y ≤ z , akkor x ≤ z ). A teljes sorrend részleges sorrend, amelyben a halmaz minden x és y objektuma esetén x ≤ y vagy y ≤ x . Az összes rendelés ismerős az informatikában, mivel az összehasonlító operátorok szükségesek az összehasonlító rendezési algoritmusok végrehajtásához. Véges halmazok esetén a teljes sorrend azonosítható az objektumok lineáris sorozatával, ahol a "≤" reláció igaz, amikor az első objektum megelőzi a sorrendben lévő második objektumot; összehasonlító rendezési algoritmus használható a teljes sorrend ilyen módon történő szekvenciává alakítására. A részleges sorrend lineáris kiterjesztése a teljes sorrend, amely kompatibilis vele, abban az értelemben, hogy ha x ≤ y a részleges sorrendben, akkor x ≤ y a teljes sorrendben is.

Egy definiálhat részleges rendelési bármely DAG engedi, hogy a sor tárgyak lehetnek a csúcsai a DAG, és meghatározza x ≤ y , hogy igaz, bármely két csúcs x és y , ha létezik egy irányított út a x az y ; azaz amikor Y jelentése elérhető a x . Ezekkel a definíciókkal a DAG topológiai rendezése ugyanaz, mint ennek a részrendnek a lineáris kiterjesztése. Ezzel szemben minden részleges sorrend meghatározható elérhetőségi relációként egy DAG -ban. Ennek egyik módja az, hogy definiálunk egy DAG -t, amelynek van egy csúcsa a részlegesen rendezett halmaz minden objektumához, és egy xy éle minden olyan objektumpárhoz, amelynél x ≤ y . Ennek alternatív módja a részleges rendezés tranzitív redukciójának használata ; általában ez kevesebb szegéllyel rendelkező DAG -kat eredményez, de az elérhetőségi reláció ezekben a DAG -kban továbbra is ugyanaz a részleges sorrend. Ezen konstrukciók használatával topológiai sorrendi algoritmusok segítségével találhatjuk meg a részleges sorrendek lineáris kiterjesztéseit.

Lásd még

tsort , Unix program a topológiai rendezéshez
Visszajelző ívkészlet , élek halmaza, amelyek eltávolítása lehetővé teszi a fennmaradó részgráf topológiai rendezését
Tarjan erősen összekapcsolt komponenseinek algoritmusa , egy algoritmus, amely a grafikonon erősen összekapcsolt komponensek topológiailag rendezett listáját adja meg
Pre-topológiai sorrend

Hivatkozások

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 sorrend topológiai rendezéséhez és rövid előzményeket tartalmaz.

Languages

In other projects