CODEWITHSUNDEEP
.netalgorithmcollectionsf#
Onur Gumus
Onur Gumus

Reputation: 1439

What is the ideal collection type for an adjecency list of a Graph implemented in .NET?

According to Sedgewick's algorithm book he uses a Bag collection from Java to implement adjacency lists of Graphs. And it makes perfect sense since for searching in O(1) and allowing duplicate edges from a Vertex to another. List can be used but they are slow in search as in O(n), so I would avoid it.

Unfortunately .NET doesn't have it. There are implementations like Wintellect but they are not Portable (or .NET standard compatible). What should I use instead ?

Upvotes: 3

Views: 119

Answers (1)

Onur Gumus
Onur Gumus

Reputation: 1439

Well after some thinking I implemented my own Bag as a Dictionary<'T,int> This is like a multiset or a bag. Here's my implementation in 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

Upvotes: 2

Related Questions