J'ai ces données:

const main = 'test1';
const data = [
  {
    from: 'test1',
    to: 'test2'
  },
  {
    from: 'test2',
    to: 'test3'
  },
  {
    from: 'test3',
    to: 'test4'
  },
  {
    from: 'test4',
    to: 'test2'
  },
  {
    from: 'test1',
    to: 'test4'
  }
];

Je veux obtenir le nombre de liens vers le nœud principal (dans ce cas test1). Par exemple, si nous regardons le nœud test3, il faut 2 liens pour accéder à test1 :

test3 → test2 → test1

Même chose avec le nœud test2, il faut 1 lien pour accéder à test1.

Quelle est la meilleure façon de calculer cela? Au final, je veux le plus long nombre de liens vers test1. Dans l'exemple, c'est 3:

test3 → test2 → test4 → test1

3
Case09 18 mars 2019 à 15:25

2 réponses

Meilleure réponse

Vous auriez besoin de visiter chaque chemin possible. Cependant, si un cycle est rencontré et que le nœud cible est accessible, la distance la plus longue devient l'infini, car on peut parcourir ce cycle un nombre quelconque de fois.

Pour visiter tous les chemins, vous pouvez utiliser une fonction récursive.

En voici un:

function find(data, sourceName, targetName) {
    // Create hash data structure keying nodes by their name
    const map = new Map(data.map(({from}) => [from, []]));
    data.forEach(({from,to}) => map.get(from).push(map.get(to)));
    // If links are supposed to be undirected, allowing traversal in both directions
    //   then uncomment this:
    // data.forEach(({from,to}) => map.get(to).push(map.get(from)));
    const target = map.get(targetName);
    // Recursive function
    function recur(node) {
        if (node === target) return 0; // Found target
        if (node.visited) { // Cycle; mark node for detection during backtracking 
            node.onCycle = true;
            return -Infinity;
        }
        node.visited = true;
        let dist = 1 + Math.max(...node.map(recur)); // Maximise path length
        node.visited = false;
        // Leave out next line if longest path should not include cycles
        if (node.onCycle && dist > 0) return Infinity; // Solution path can have cycles
        return dist;
    }
    const dist = recur(map.get(sourceName)); // Start!
    return dist < 0 ? null : dist; // Return null when target cannot be reached
}

const data = [{from: 'test1', to: 'test2'},{from: 'test2', to: 'test3'},{from: 'test3',to: 'test4'},{from: 'test4',to: 'test2'},{from: 'test1',to:'test4'}];
const longestDist = find(data, 'test1', 'test3');
console.log(longestDist);

Notez que cette solution ne poursuivra pas une recherche en passant par le nœud cible puis en essayant de le retrouver à partir de là (par un cycle). En d'autres termes, il suppose qu'un chemin ne peut contenir la cible que comme dernier nœud, et non plusieurs fois.

Si vous souhaitez exclure les chemins comportant des cycles, supprimez la ligne qui renvoie Infinity comme distance.

Le code suppose que les liens sont dirigés. Dans le cas où les liens doivent être compris comme bidirectionnels (alias non dirigé), ce qui signifie que si une direction est spécifiée, la direction opposée est également possible sans l'inclure explicitement en tant que lien en miroir, alors décommentez le deuxième ligne forEach dans le code ci-dessus.

2
trincot 18 mars 2019 à 14:04

Votre question peut être redéfinie en termes de théorie des graphes : "test1", "test2",... sont des sommets, le tableau de données contient des arêtes (paires "de-à") - nous avons donc un graphique - trouver le chemin le plus long le problème NP-difficile - wiki. Vous devez donc vérifier tous les chemins possibles pour trouver le plus long

1
Kamil Kiełczewski 18 mars 2019 à 12:40