Scrierea seriilor

Caut un algoritm simplu de a "serializa" un grafic direcționat. În special, am un set de fișiere cu interdependență în ordinea execuției lor și vreau să găsesc ordinea corectă la momentul compilării. Știu că trebuie să fie un lucru destul de obișnuit de făcut - compilatorii o fac tot timpul - dar google-fu meu a fost slab astăzi. Care este algoritmul "go-to" pentru asta?

0
fr hi bn

3 răspunsuri

Am venit cu un algoritm recursiv destul de naiv (pseudocod):

Map> source; // map of each object to its dependency list
List dest; // destination list

function resolve(a):
    if (dest.contains(a)) return;
    foreach (b in source[a]):
        resolve(b);
    dest.add(a);

foreach (a in source):
    resolve(a);

Cea mai mare problemă în acest sens este că nu are capacitatea de a detecta dependențele ciclice - poate trece în recursivitate infinită (adică suprapopularea stivei ;-p). Singura modalitate pe care o văd ar fi să întoarcă algoritmul recursiv într-un algoritm interactiv cu un teanc manual și să verifice manual stiva pentru elemente repetate.

Oricine are ceva mai bun?

0
adăugat
în loc să utilizați o vreme o foreach, păstrați două pointeri traversând datele a, una care conduce cu pași dubli și una care traversează acei pași simpli. Indicatorul de vârf se ocupă de rezoluțiile acutale și dacă atinge indicatorul final, există un ciclu.
adăugat autor Tenderdude, sursa

Topological Sort (From Wikipedia):

În teoria graficelor, un tip topologic sau   ordonarea topologică a unui regizor   Graficul grafic (DAG) este liniar   ordonarea nodurilor sale în care fiecare   nodul se află înaintea tuturor nodurilor la care se află   are margini de ieșire. Fiecare DAG are   unul sau mai multe tipuri topologice.

Pseudo cod:

L ? Empty list where we put the sorted elements
Q ? Set of all nodes with no incoming edges
while Q is non-empty do
    remove a node n from Q
    insert n into 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 Q
if graph has edges then
    output error message (graph has a cycle)
else 
    output message (proposed topologically sorted order: L)
0
adăugat
da, vă rugăm să menționați sursele
adăugat autor Jason S, sursa
Eh ... copiat direct de pe wikipedia?
adăugat autor Benjol, sursa
Mulțumiri. M-am ajutat să mapăm faptul că arborele de dependență poate fi sortat folosind această metodă. :-)
adăugat autor Shamasis Bhattacharya, sursa

M-aș aștepta la unelte care au nevoie de acest lucru, pur și simplu să se plimbe pe copac într-o primă manieră și atunci când lovesc o frunză, procesează-o (de exemplu, compilați) și scoate-o din grafic (sau marchează-o ca procesată și tratați nodurile cu toate frunzele prelucrate ca frunze).

Atâta timp cât este un DAG, această plimbare simplă bazată pe stiva ar trebui să fie banală.

0
adăugat
Da, asa faceti voi. Se numește o căutare în profunzime (DFS). Și dacă nu sunteți sigur că aveți un DAG, trebuie să verificați marginile din spate, altfel un ciclu vă va trimite într-o buclă infinită.
adăugat autor sleske, sursa