QuickGraph - Existe-t-il un algorithme pour trouver tous les parents (jusqu'aux sommets racine) d'un ensemble de sommets ?

Question

Dans QuickGraph, existe-t-il un algorithme permettant de trouver tous les parents (jusqu'aux sommets racine) d'un ensemble de sommets ? En d'autres termes, tous les sommets qui ont quelque part en dessous d'eux (sur le chemin des nœuds feuilles) un ou plusieurs sommets d'entrée. Ainsi, si les sommets sont des nœuds et que les arêtes sont une relation de dépendance, il faut trouver tous les nœuds qui seraient affectés par un ensemble donné de nœuds.

Si ce n'est pas le cas, à quel point est-il difficile d'écrire ses propres algorithmes ?

Answer 1

Voici ce que j'ai utilisé pour effectuer une recherche de 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 à l'avance, vous pouvez la spécifier dans le champ dfs.Compute() (c'est-à-dire dfs.Compute(0) ).

-Doug

Answer 2

J'ai utilisé la réponse de Doug et j'ai découvert que s'il y a plus d'un parent pour un sommet, sa solution ne fournit qu'un seul des parents. Je ne sais pas exactement pourquoi.

J'ai donc 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 maintenir un graphe inversé, soit créer une enveloppe sur le graphe qui inverse chaque arête. QuickGraph possède la classe ReversedBidirectionalGraph qui est un wrapper prévu à cet effet, mais elle ne semble pas fonctionner avec les classes d'algorithmes à cause d'une incompatibilité de type générique. J'ai donc dû créer ma propre classe :

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
}

Exécutez ensuite DFS ou BFS sur ce wrapper :

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

La réponse de Doug n'est pas correcte, car DFS ne visitera que le sous-graphe en aval. L'observateur du prédécesseur n'est d'aucune utilité.