Каков идеальный тип коллекции для списка смежности графа, реализованного в .NET?

#.net #algorithm #collections #f#

#.net #алгоритм #Коллекции #f#

Вопрос:

Согласно книге алгоритмов Седжвика, он использует коллекцию пакетов из Java для реализации списков смежности графов. И это имеет смысл, поскольку для поиска в O (1) и разрешения дублирования ребер из вершины в другую. Можно использовать список, но они медленны в поиске, как в O (n), поэтому я бы этого избегал.

К сожалению, в .NET его нет. Существуют такие реализации, как Wintellect, но они не переносимы (или совместимы со стандартом .NET). Что я должен использовать вместо этого?

1. Будет Dictionary<T, List<T>> ли достаточно?

2. @Enigmativity, не могли бы вы уточнить? Похоже ли это на то, что я помещаю первый экземпляр Vertex в Dictionary в качестве ключа, а также добавляю этот и последующие в список?

3. Если у вас есть набор вершин (типа T ), которые составляют граф, то ключом является одна вершина, а List<T> все вершины, с которыми соединяется ключевая вершина. Тогда Dictionary<T, List<T>> это ориентированный циклический граф.

4. Нет, это было бы неэффективно. Вы только что использовали List<T> в качестве списка смежности. В вашем случае поиск, если две вершины являются соседними, займет O (n) времени, где n — количество соседей. С помощью пакета вы можете ответить на тот же вопрос лучше, чем с постоянным временем.

5. В этом случае я не знаю, существует ли структура, которая может выполнять все операции O (1) . Но я думаю, вам следует явно указать, какие операции вы хотите использовать O (1), чтобы упростить ответ на ваш вопрос. (т.Е. Добавить ребро, удалить ребро, проверить смежность узлов, подсчитать ребра между двумя соседними узлами и т.д.. все, что имеет значение для вашего случая).

Ответ №1:

Ну, после некоторых размышлений я реализовал свой собственный пакет в виде Dictionary<‘T,int> Это похоже на мультимножество или пакет. Вот моя реализация в F#:

 type Bag<'T when 'T : equality>() =
    let dict = Dictionary<'T,int>()
    let mutable count = 0

    member x.Add = (x:>ICollection<'T>).Add

    member x.Remove = (x:>ICollection<'T>).Remove

    member x.Count = (x:>ICollection<'T>).Count

    member x.Clear = (x:>ICollection<'T>).Clear

    member x.ItemCount item =
        match dict.TryGetValue item with
            | true, itemCount -> itemCount
            | _ -> 0

    interface ICollection<'T> with

        member x.Add item =
            count <- count   1
            let itemCount =
                match dict.TryGetValue item with
               | true, itemCount -> itemCount
               | _ -> 0
            dict.[item] <- itemCount   1

        member x.Clear() = dict.Clear()

        member x.Contains item = dict.ContainsKey item

        member x.CopyTo(array, arrayIndex) =
            x
            |> Seq.take(array.Length - arrayIndex)
            |> Seq.iteri (fun i item ->  array.[i   arrayIndex] <- item)

        member x.Count = count

        member x.GetEnumerator()  =
            (x :> ICollection<'T>).GetEnumerator() :> Collections.IEnumerator

        member x.GetEnumerator() =
            let seq =
                let innerSeq (kvp : KeyValuePair<'T,int>) =
                     Seq.init kvp.Value (fun _ -> kvp.Key)
                dict |> Seq.map innerSeq |> Seq.collect id
            seq.GetEnumerator()

        member x.IsReadOnly = false

        member x.Remove item =
            match dict.TryGetValue item with
            | true, 1 ->
                count <- count - 1
                dict.Remove item
            | true, itemCount ->
                count <- count - 1 
                dict.[item] <- itemCount - 1
                true
            | _ -> false

1. Мне непонятно, почему вы используете a List<T> вместо просто an int в качестве значений словаря — все, что вам нужно поддерживать, это количество, вам не нужно добавлять несколько копий элемента.