Serializzazione del grafico

Question

Sto cercando un semplice algoritmo per "serializzare" un grafico diretto.In particolare ho una serie di file con interdipendenze sul loro ordine di esecuzione e voglio trovare l'ordine corretto in fase di compilazione.So che deve essere una cosa abbastanza comune da fare - i compilatori lo fanno continuamente - ma il mio google-fu è stato debole oggi.Qual è l'algoritmo "go-to" per questo?

Answer 1

Ordinamento topologico (Da Wikipedia):

Nella teoria dei grafici, un tipo topologico o un ordinamento topologico di un grafico aciclico diretto (DAG) è un ordinamento lineare dei suoi nodi in cui ogni nodo viene prima di tutti i nodi a cui ha bordi in uscita.Ogni DAG ha uno o più tipi topologici.

Pseudocodice:

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)

Answer 2

Mi aspetterei che gli strumenti che ne hanno bisogno semplicemente camminino lungo l'albero in profondità e quando colpiscono una foglia, la elaborino semplicemente (ad es.compilare) e rimuoverlo dal grafico (o contrassegnarlo come elaborato e trattare i nodi con tutte le foglie elaborate come foglie).

Finché si tratta di un DAG, questa semplice passeggiata basata sullo stack dovrebbe essere banale.

Answer 3

Se il grafico contiene cicli, come possono esistere ordini di esecuzione consentiti per i tuoi file?Mi sembra che se il grafico contiene cicli, allora non hai una soluzione, e questo è riportato correttamente dall'algoritmo sopra.

Answer 4

Ho escogitato un algoritmo ricorsivo abbastanza ingenuo (pseudocodice):

Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> 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);

Il problema più grande è che non ha la capacità di rilevare le dipendenze cicliche: può andare in ricorsione infinita (cioè stack overflow ;-p).L'unico modo per aggirare ciò che posso vedere sarebbe trasformare l'algoritmo ricorsivo in uno interattivo con uno stack manuale e controllare manualmente lo stack per elementi ripetuti.

Qualcuno ha qualcosa di meglio?