QuickGraph - есть ли алгоритм для нахождения всех родителей (вплоть до корневой вершины) из набора вершин - PullRequest
Новая
       18

QuickGraph - есть ли алгоритм для нахождения всех родителей (вплоть до корневой вершины) из набора вершин

3 голосов
/ 27 апреля 2010

В QuickGraph - есть ли алгоритм для поиска всех родителей (вплоть до корневой вершины) из набора вершин. Другими словами, все вершины, которые находятся где-то под ними (на пути к конечным узлам), вводят одну или несколько вершин. Поэтому, если вершины были узлами, а ребра зависели от отношений, найдите все узлы, на которые будет влиять данный набор узлов.

Если нет, то насколько сложно написать собственные алгоритмы?

Ответы [ 3 ]

1 голос
/ 20 июля 2012

Я воспользовался ответом Дага и обнаружил, что если для вершины более одного родителя, его решение предоставляет только один из родителей. Я не уверен почему.

Итак, я создал свою собственную версию, которая выглядит следующим образом: 

    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;
    }
1 голос
/ 12 августа 2016

Вам либо нужно поддерживать перевернутый граф, либо создать обертку над графом, которая переворачивает каждое ребро. QuickGraph имеет класс ReversedBidirectionalGraph, который является оберткой, предназначенной именно для этого, но, похоже, не работает с классами алгоритма из-за несовместимости универсального типа. Я должен был создать свой собственный класс оболочки: 

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
}

Затем запустите DFS или BFS для этой оболочки: 

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

Ответ Дуга неправильный, потому что DFS будет посещать только нижний подграф. Предшественник-наблюдатель не помогает.

1 голос
/ 03 мая 2010

Вот что я использовал для поиска предшественника по заданной вершине: 

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

Обратите внимание, что если вы заранее знаете свой корень, вы можете указать его в методе dfs.Compute() (т.е. dfs.Compute(0)).

-Doug

...