QuickGraph - est-il un algorithme pour trouver tous les parents (jusqu'à la racine vertex) d'un ensemble de vertex

Question

Dans QuickGraph - est-il un algorithme pour trouver tous les parents (jusqu'au sommet racine) d'un ensemble de vertex. En d'autres termes, tous les sommets qui ont quelque part en dessous (sur le chemin des nœuds feuilles) un ou plusieurs sommets entrés. Donc, si les vertex étaient des nœuds, et que les bords étaient dépendants, trouvez tous les nœuds qui seraient affectés par un ensemble donné de nœuds.

Si ce n'est pas difficile d'écrire ses propres algorithmes?

Answer 1

Voici ce que je l'ai utilisé pour accomplir une recherche prédécesseur sur un sommet donné:

IBidirectionalGraph<int, IEdge<int>> CreateGraph(int vertexCount) 
{ 
    BidirectionalGraph<int, IEdge<int>> graph = new BidirectionalGraph<int, IEdge<int>>(true); 
    for (int i = 0; i < vertexCount; i++) 
     graph.AddVertex(i); 

    for (int i = 1; i < vertexCount; i++) 
     graph.AddEdge(new Edge<int>(i - 1, i)); 

    return graph; 
} 

static public void Main() 
{ 
    IBidirectionalGraph<int, IEdge<int>> graph = CreateGraph(5); 

    var dfs = new DepthFirstSearchAlgorithm<int, IEdge<int>>(graph);    
    var observer = new VertexPredecessorRecorderObserver<int, IEdge<int>>(); 

    using (observer.Attach(dfs)) // attach, detach to dfs events 
     dfs.Compute(); 

    int vertexToFind = 3; 
    IEnumerable<IEdge<int>> edges; 
    if (observer.TryGetPath(vertexToFind, out edges)) 
    { 
     Console.WriteLine("To get to vertex '" + vertexToFind + "', take the following edges:"); 
     foreach (IEdge<int> edge in edges) 
      Console.WriteLine(edge.Source + " -> " + edge.Target); 
    } 
} 

Notez que si vous connaissez votre racine au préalable, vous pouvez le spécifier dans la méthode dfs.Compute() (à savoir dfs.Compute(0)).

-Doug

Answer 2

J'utilise la réponse de Doug et a découvert que s'il y a plus d'un parent pour un sommet, sa solution ne fournit que l'un des parents. Je ne suis pas sûr pourquoi.

Alors, j'ai créé ma propre version qui est la suivante:

public IEnumerable<T> GetParents(T vertexToFind) 
    { 
     IEnumerable<T> parents = null; 

     if (this.graph.Edges != null) 
     { 
      parents = this.graph 
       .Edges 
       .Where(x => x.Target.Equals(vertexToFind)) 
       .Select(x => x.Source); 
     } 

     return parents; 
    } 

Answer 3

Vous devez soit de maintenir un graphique inversé, ou créer une enveloppe sur le graphique qui renverse toutes les arêtes. QuickGraph a la classe ReversedBidirectionalGraph qui est un wrapper destiné uniquement à cela, mais elle ne semble pas fonctionner avec les classes d'algorithme en raison de l'incompatibilité de type générique. J'ai dû créer ma propre classe d'emballage:

class ReversedBidirectionalGraphWrapper<TVertex, TEdge> : IVertexListGraph<TVertex, TEdge> where TEdge : IEdge<TVertex> 
{ 
    private BidirectionalGraph<TVertex, TEdge> _originalGraph; 
    public IEnumerable<TEdge> OutEdges(TVertex v) 
    { 
     foreach (var e in _graph.InEdges(v)) 
     { 
      yield return (TEdge)Convert.ChangeType(new Edge<TVertex>(e.Target, e.Source), typeof(TEdge)); 
     } 
    } //...implement the rest of the interface members using the same trick 
} 

Lancez ensuite DFS ou BFS sur cette enveloppe:

var w = new ReversedBidirectionalGraphWrapper<int, Edge<int>>(graph);  
var result = new List<int>();  
var alg = new DepthFirstSearchAlgorithm<int, Edge<int>>(w); 
alg.TreeEdge += e => result.Add(e.Target);  
alg.Compute(node); 

réponse de Doug est incorrect, car DFS ne visiter le sous-graphe en aval. L'observateur prédécesseur n'aide pas.