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
adăugat editat
Vizualizări: 66
sursa
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 





sursa















î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 





sursa







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 





sursa







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