Lista zależności Javascript

Question

Mam listę elementów, w których muszę określić zależność.

mam:

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

a zależy od b i d i d na c i e. Czy istnieje sposób na zbudowanie zależności w taki sprytny sposób? Wyjście powinno (mogą) być:

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

/Kristian

Answer 1

Zakładając chciałeś listę rekurencyjnych zależności od elementu, w tym samym elemencie, w dowolnej kolejności:

„dla każdego uzależnienia , dodaj jego zależności do listy zależności "jest wystarczająco sprytny?

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; 
} 

Jeśli chcesz element sama na końcu, a nie na początku, można ustalić, że z output.push(output.shift())

---

Jeśli chcesz, aby zależności w takiej kolejności, że każdy element poprzedza elementy, które zależą od niego, wtedy będziesz musiał zdefiniować sposób obsługi zależności cyklicznych. Jednym ze sposobów radzenia sobie z tym jest wykrycie zależności cyklicznej i niepowodzenie.

Jeśli każdy zależność potrzebna jest co najwyżej jeden element, a następnie można użyć poprzedniego algorytmu: po prostu czytać wyjście do tyłu (lub do tyłu tablicy lub skorzystać unshift zamiast push (uwaga: spadek wydajności))

---

Zależności tworzą wykres, a Ty szukasz jego topologicznego sortowania. Jednym (nieskutecznym) sposobem byłoby uporządkowanie węzłów w pierwszej kolejności i ponowne ich umieszczenie, jeśli zostaną ponownie wprowadzone. Możesz użyć stosu Open, aby wykryć błędy - jeśli dziecko zostanie przywrócone z rodzica, masz zależność cykliczną.

Lepszym rozwiązaniem byłoby użyć standardowego algorytmu sortowania topologiczną: Chociaż istnieje nieposortowane węzły, wybrać jeden, który nie ma nierozwiązanych zależności:

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; 
} 

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