Calcul des trajectoires dans un graphe

Question

Je dois faire une méthode pour faire une liste avec tous les chemins dans un graphe. Mon graphe a seulement un noeud de début et un noeud de finition. Chaque noeud a une liste avec ses enfants et une autre liste avec ses parents. Je dois faire une autre liste contenant tous les chemins (chacun d'entre eux dans une autre liste)

Une suggestion?

Answer 1

Vous pouvez générer toutes les combinaisons possibles de sommets (en utilisant la combinatoire) et filtrer les chemins qui n'existent pas (où les sommets ne sont pas joints par un bord ou le bord n'a pas la bonne direction).

Vous pouvez améliorer cette idée de base en demandant au code qui génère les combinaisons de vérifier les sommets restants disponibles à partir du sommet en cours. Ceci est supposé que vous avez des graphes acycliques et souhaitez visiter chaque sommet exactement une fois.

Answer 2

Cela dépend de si elle est acyclique ou non. De toute évidence, un cycle se traduira par des chemins infinis (une fois autour de la boucle, deux fois ronde, 3 fois ronde ... etc etc). Si le graphique est acyclique, vous devriez être en mesure de faire une recherche en profondeur (DFS) (http://en.wikipedia.org/wiki/Depth-first_search) et simplement compter le nombre de fois que vous rencontrez le nœud de destination.

Answer 3

Familiarisez-vous d'abord avec les algorithmes graphiques de base (essayez un manuel, ou google). Déterminez lequel correspond le mieux au problème que vous résolvez et appliquez-le. Vous devrez peut-être adapter un peu l'algorithme, mais en général il existe des algorithmes largement connus pour tous les problèmes de base des graphes.

Answer 4

Si vous avez une classe GraphNode qui ressemble à ceci:

public class GraphNode 
{ 
    public IEnumerable<GraphNode> Children { get; set; } 
    // ... 
} 

Alors ce Sould faire le travail:

public static class GraphPathFinder 
{ 
    public static IEnumerable<IEnumerable<GraphNode>> FindAllPathsTo(this GraphNode startNode, GraphNode endNode) 
    { 
     List<IEnumerable<GraphNode>> results = new List<IEnumerable<GraphNode>>(); 
     Stack<GraphNode> currentPath = new Stack<GraphNode>(); 
     currentPath.Push(startNode); 

     FindAllPathsRecursive(endNode, currentPath, results); 

     return results; 
    } 

    private static void FindAllPathsRecursive(GraphNode endNode, Stack<GraphNode> currentPath, List<IEnumerable<GraphNode>> results) 
    { 
     if (currentPath.Peek() == endNode) results.Add(currentPath.ToList()); 
     else 
     { 
      foreach (GraphNode node in currentPath.Peek().Children.Where(p => !currentPath.Contains(p))) 
      { 
       currentPath.Push(node); 
       FindAllPathsRecursive(endNode, currentPath, new List<IEnumerable<GraphNode>>()); 
       currentPath.Pop(); 
      } 
     } 
    } 
} 

Il est une implémentation simple de l'algorithme DFS. Aucune vérification d'erreur, optimisations, thread-sécurité, etc ...

Aussi si vous êtes sûr que votre graphique ne fonctionne pas, vous pouvez supprimer la clause where dans l'instruction foreach dans la dernière méthode.

J'espère que cela a aidé.