Elenco Dipendenze Javascript

Question

Ho una lista di elementi in cui ho bisogno di capire la dipendenza.

ho:

[{ 
    "a": ["b", "d"] 
}, { 
    "d": ["c", "e"] 
}] 

a dipende b e d, e d su c e e. C'è un modo per costruire le dipendenze in modo intelligente per questo? L'output dovrebbe (potrebbe) essere:

["b", "c", "e", "d", "a"] 

/Kristian

Answer 1

Supponendo che si voleva la lista delle dipendenze ricorsive di un elemento, tra cui l'elemento stesso, in qualsiasi ordine:

"per ogni dipendenza , aggiungi le sue dipendenze alla lista delle dipendenze "è abbastanza intelligente?

function recursiveDependencies (dependencies, element){ 
    var output = [element]; 
    for(i=0; i<output.length(); i++){ 
    dependencies[output[i]].forEach(function(x){ 
     if(output.indexOf(x)<0){ //prevent duplicates 
     output.push(x) 
     } 
    }) 
    } 
    return output; 
} 

Se si desidera che l'elemento stesso alla fine piuttosto che all'inizio, è possibile rimediare con output.push(output.shift())

---

Se volete che il vostro dipendenze in tale ordine che ogni elemento precede gli elementi che dipende da questo, quindi dovrai definire come gestire le dipendenze circolari. Un modo per gestire questo è rilevare una dipendenza circolare e fallire.

Se ogni dipendenza è necessaria al massimo da un elemento, è possibile utilizzare l'algoritmo precedente: è sufficiente leggere l'output indietro (o invertire la matrice o utilizzare unshift al posto di push (attenzione: calo di prestazioni))

---

Le dipendenze formano un grafico e si sta cercando il suo ordinamento topologico. Un modo (inefficiente) sarebbe quello di ordinare i nodi in profondità - primo ordine e reinserirli se sono rientrati. È possibile utilizzare lo stack Apri per rilevare errori: se un figlio viene reinserito da un genitore, si ha una dipendenza circolare.

Una soluzione migliore sarebbe quella di utilizzare l'algoritmo di ordinamento topologico di serie: Mentre ci sono nodi non ordinati, sceglierne uno che non ha dipendenze non risolte:

function recursiveDependencies (dependencies, root){ 
    var nodes={}; 
    var nodeCount=0; 
    var ready=[]; 
    var output=[]; 

    // build the graph 
    function add(element){ 
    nodeCount++; 
    nodes[element]={needs:[], neededBy:[], name: element}; 
    if(dependencies[element]){ 
     dependencies[element].forEach(function(dependency){ 
     if(!nodes[dependency]) add(dependency); 
     nodes[element].needs.push(nodes[dependency]); 
     nodes[dependency].neededBy.push(nodes[element]); 
     }); 
    } 
    if(!nodes[element].needs.length) ready.push(nodes[element]); 
    } 

    if(root){ 
    add(root) 
    } else { 
    for (element in dependencies){ 
     if(!nodes[element]) add(element); 
    } 
    } 


    //sort the graph 
    while(ready.length){ 
    var dependency = ready.pop(); 
    output.push(dependency.name); 
    dependency.neededBy.forEach(function(element){ 
     element.needs = element.needs.filter(function(x){return x!=dependency}) 
     if(!element.needs.length) ready.push(element) 
    }) 
    } 

    //error-check 
    if(output.length != nodeCount){ 
    throw "circular dependency detected" 
    } 

    return output; 
} 

violino: http://jsfiddle.net/Xq5dz/4/