Какую структуру представлять направленный ациклический граф в .NET? - PullRequest
Новая
       18

Какую структуру представлять направленный ациклический граф в .NET?

0 голосов
/ 31 марта 2011

Я рассматриваю представление DAG как Dictionary(Of Integer, List(Of Integer)), где ключом будет идентификатор вершины, а список будет содержать все целевые вершины вдоль ребер.

Я буду использовать эту структуру позже, чтобы:

получить списки возможных восходящих и нисходящих путей получить списки возможных следующих путей и возможных исходных путей получить список конечных узлов проверить предложенные ребра между вершинами Топологически сортировать вершины

Есть ли проблемы с моим подходом?Как ты это сделал в прошлом?Спасибо

РЕДАКТИРОВАТЬ
Одна из проблем, связанных с моим подходом, заключается в том, что поиск исходных путей к вершинам является дорогостоящей операцией, поскольку она требует итерации по всему словарю.Возможно, в моих интересах сделать объект DAGVertex, выставляющий Targets и Sources

Ответы [ 2 ]

1 голос
/ 31 марта 2011

Вы можете представить график в виде двух словарей - один для входящих ребер и один для исходящих.Это удвоит время на изменение графика и потребление памяти, но уменьшит временную сложность получения списка ребер, приходящих к определенной вершине, с O(V + E) до O(1).

Получение списка конечных узловможно сделать аналогично - просто иметь список текущих конечных узлов (или Dictionary(Of Integer, Boolean)).Добавляйте к нему узел всякий раз, когда он становится конечным узлом, и удаляйте его, если он перестает быть единым целым.

0 голосов
/ 31 марта 2011

Я считаю, что я бы создал сущности для своих узлов и затем использовал бы ООП на моем подходе.

Если ваши требования никогда не изменятся, и вы абсолютно уверены в этом, возможно, ваш подход в порядке, но если выможет иметь изменения требований, как, например, назначить «веса» для каждого пути между узлом и другим, я думаю, это может быть трудно сделать это.(разрешил бы это, сделав что-то вроде: 

Dictionary<Int32, List<Int32, Dictionary<Int32, Int32>>

???)

Я думаю, что мой класс будет выглядеть примерно так; 

public class GraphNode
{
    private Int32 value;
    public Int32 Value
    {
        get { return this.value; }
    }

    private List<GraphNode> siblings;
    public ReadOnlyCollection<GraphNode> Siblings
    {
        get { return new ReadOnlyCollection<GraphNode>(siblings); }
    }

    public void AddSibling(GraphNode node)
    {
        if (this == node)
            throw new Exception("Can't assing a node to itself as a sibling");

        if (this.siblings.Contains(node))
            throw new Exception("This node is already contained in the siblings list");

        this.siblings.Add(node);
    }

    public GraphNode(Int32 value)
    {
        this.value = value;
        this.siblings = new List<GraphNode>();
    }
}
...