Create adjacency list with linked nodes using immutable lists

Question

I'm trying to create a adjacency list with linked nodes that is currently defined like this:

type Node =
    {
        Name: string
        Neighbors: Node list
    }

type AdjacencyList(nodes: Node list) =

    interface IHasNodes with
        /// Gets the number of nodes in the adjacency list.
        member this.NodeCount = nodes.Length

        /// Gets a list of all nodes in the adjacency list.
        member this.Nodes = nodes

The input from which i want to create the list is a sequence of strings in the format

node_name neighbor_name_1 ... neighbor_name_n

So, basically this should be a simple task, but i can't think of a way to update nodes without running into an cycle when one node, e.g. A, has an edge to B and B has an edge to A. In this case i have to update the neighbors of B when creating its node object and in turn update the neighbor reference in node A to node B, which in turn leaves me with updating node B again and so on.

module List =

    /// <summary>
    /// Replaces the first item in a list that matches the given predicate.
    /// </summary>
    /// <param name="predicate">The predicate for the item to replace.</param>
    /// <param name="item">The replacement item.</param>
    /// <param name="list">The list in which to replace the item.</param>
    /// <returns>A new list with the first item that matches <paramref name="predicate"/> replaced by <paramref name="item"/>.</returns>
    let replace predicate item list =
        let rec replaceItem remainingItems resultList =
            match remainingItems with
            | []         ->  resultList |> List.rev
            | head::tail ->
                match predicate(head) with
                | false -> replaceItem tail (head::resultList)
                | true  -> (item::resultList |> List.rev) @ tail

        replaceItem list []

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module AdjacencyList =

    let create (rows: seq<string>) =
        let mutable preBuiltNodes: Node list = []
        let rowsToEnumerate = rows |> Seq.where (fun str -> not (System.String.IsNullOrWhiteSpace(str)) || not (str.StartsWith("//")))
        let neighborsForNodes = Dictionary<string, string array>()

        // Build the base nodes and get the neighbors of each node.
        for row in rowsToEnumerate do
            let rowData = row.Split(' ')

            neighborsForNodes.Add(rowData.[0], rowData |> Array.skip 1)
            preBuiltNodes <- { Name = rowData.[0]; Neighbors = [] } :: preBuiltNodes

        // Build the final nodes from the pre-built nodes.
        let rec buildAdjacencyList remainingNodes (builtNodes: Node list) =
            match remainingNodes with
            | []         -> builtNodes
            | head::tail ->
                let neighbors = preBuiltNodes |> List.where (fun node -> neighborsForNodes.[head.Name] |> Array.exists (fun name -> name = node.Name))
                let newNode = { head with Neighbors = neighbors };

                // Update nodes referencing an old version of the new node.
                let mutable newBuiltNodes: Node list = []

                for i = 0 to (builtNodes.Length - 1) do
                    if builtNodes.[i].Neighbors |> List.exists (fun node -> node.Name = head.Name) then
                        let updatedNode = { builtNodes.[i] with Neighbors = builtNodes.[i].Neighbors |> List.replace (fun n -> n.Name = newNode.Name) newNode }
                        newBuiltNodes <- updatedNode :: newBuiltNodes

                        // Cycle here when updating newNode
                        // if it has an edge to the node at builtNodes.[i]

                    else
                        newBuiltNodes <- builtNodes.[i] :: newBuiltNodes

                preBuiltNodes <- preBuiltNodes |> List.replace (fun n -> n.Name = newNode.Name) newNode
                buildAdjacencyList tail (newNode::newBuiltNodes)

        buildAdjacencyList preBuiltNodes [] |> AdjacencyList

I've implemented that algorithm in C# before (using mutable lists) so i might be missing a point here. Of course i could use mutable lists as well, but i wanted to try to use immutable ones.

Answer 1

The problem with your approach is the Node type. I propose a different approach like this:

type Node = Node of string

type Graph = Graph of Map<Node, Set<Node>>

let emptyGraph = Graph Map.empty

let addEdge nodeA nodeB g =
    let update mainNode adjNode map =
        let updatedAdjs =
            match map |> Map.tryFind mainNode with
            | Some adjs ->
                adjs |> Set.add adjNode
            | None ->
                Set.singleton adjNode
        map
        |> Map.add mainNode updatedAdjs

    let (Graph map) = g
    map
    |> update nodeA nodeB
    |> update nodeB nodeA
    |> Graph

let addIsolatedNode node g =
    let (Graph map) = g
    match map |> Map.tryFind node with
    | Some _ ->
        g
    | None ->
        map
        |> Map.add node Set.empty
        |> Graph

let getAdjs node g =
    let (Graph map) = g
    map
    |> Map.tryFind node

// TEST
let myGraph =
    emptyGraph
    |> addEdge (Node "A") (Node "B")
    |> addEdge (Node "A") (Node "C")
    |> addEdge (Node "A") (Node "D")
    |> addEdge (Node "B") (Node "C")
    |> addEdge (Node "C") (Node "D")
    |> addIsolatedNode (Node "E")
myGraph |> getAdjs (Node "A") // result: Some (set [Node "B"; Node "C"; Node "D"])
myGraph |> getAdjs (Node "E") // result: Some (set [])
myGraph |> getAdjs (Node "F") // result: None

Answer 2

In C# you would include a reference to the neighbor Nodes. But with your definition you have a Neighbor node instead, that makes it an impossible task. Apart from the solution by @kvb there are other options:

Option 1: use a string list

To me it would make much more sense to make the list reference the Node name and not the node itself:

type Node =
    {
        Name     : string
        Neighbors: string list
    }

First some helper functions:

let addRelation relations (node1, node2)  = 
    relations 
    |> Set.add (node1, node2)
    |> Set.add (node2, node1)

let allRelations nodes =
    nodes |> List.fold addRelation Set.empty

This would be the way to create it:

let getNodes nodes = 
    let rels = allRelations nodes
    rels
    |> Seq.groupBy fst
    |> Seq.map (fun (name, neighbors) -> 
        { Name      = name
          Neighbors = neighbors |> Seq.map snd |> Seq.toList 
        } 
    )
    |> Seq.toList

and basically you feed it a list with the pair of names:

["1", "2" 
 "3", "4"
 "1", "3"
 "4", "5" ]
|> getNodes 
|> Seq.iter (printfn "%A")

produces:

{Name = "1";
 Neighbors = ["2"; "3"];}
{Name = "2";
 Neighbors = ["1"];}
{Name = "3";
 Neighbors = ["1"; "4"];}
{Name = "4";
 Neighbors = ["3"; "5"];}
{Name = "5";
 Neighbors = ["4"];}

---

Option 2: ref to Node list

You could have a reference to a list of neighbor nodes:

type Node =
    {
        Name     : string
        Neighbors: Node list ref
    }

This way you can first create the nodes and then add them to the lists:

let getNodes nodePairs = 
    let rels        = allRelations nodePairs
    let nodes       = rels |> Seq.map (fun (name, _) -> name, { Name = name ; Neighbors = ref [] }) |> Map
    let getNode  nm = nodes |> Map.find nm
    rels
    |> Seq.groupBy fst
    |> Seq.iter (fun (name, neighbors) ->
        (getNode name).Neighbors := neighbors |> Seq.map (snd >> getNode) |> Seq.toList
    )
    nodes |> Map.toList |> List.map snd

Test it like this:

["1", "2" 
 "3", "4"
 "1", "3"
 "4", "5" ]
|> getNodes 
|> Seq.iter (printfn "%A")

output:

{Name = "1";
 Neighbors =
  {contents =
    [{Name = "2";
      Neighbors = {contents = [...];};};
     {Name = "3";
      Neighbors =
       {contents =
         [...;
          {Name = "4";
           Neighbors = {contents = [...; {Name = "5";
                                          Neighbors = {contents = [...];};}];};}];};}];};}
{Name = "2";
 Neighbors =
  {contents =
    [{Name = "1";
      Neighbors =
       {contents =
         [...;
          {Name = "3";
           Neighbors =
            {contents =
              [...;
               {Name = "4";
                Neighbors =
                 {contents = [...; {Name = "5";
                                    Neighbors = {contents = [...];};}];};}];};}];};}];};}
{Name = "3";
 Neighbors =
  {contents =
    [{Name = "1";
      Neighbors = {contents = [{Name = "2";
                                Neighbors = {contents = [...];};}; ...];};};
     {Name = "4";
      Neighbors = {contents = [...; {Name = "5";
                                     Neighbors = {contents = [...];};}];};}];};}
{Name = "4";
 Neighbors =
  {contents =
    [{Name = "3";
      Neighbors =
       {contents =
         [{Name = "1";
           Neighbors = {contents = [{Name = "2";
                                     Neighbors = {contents = [...];};}; ...];};};
          ...];};}; {Name = "5";
                     Neighbors = {contents = [...];};}];};}
{Name = "5";
 Neighbors =
  {contents =
    [{Name = "4";
      Neighbors =
       {contents =
         [{Name = "3";
           Neighbors =
            {contents =
              [{Name = "1";
                Neighbors =
                 {contents = [{Name = "2";
                               Neighbors = {contents = [...];};}; ...];};}; ...];};};
          ...];};}];};}

Answer 3

I don't think there's any way to do what you want with your exact representation. One simple alternative is to make the set of neighbors lazy:

type node<'a> = {
    id : 'a
    neighbors : Lazy<node<'a> list>
}

let convert (m:Map<'a, 'a list>) =
    let rec nodes = [
        for KeyValue(k,vs) in m -> 
            { id = k; 
              neighbors = lazy 
                            vs 
                            |> List.map (fun id -> 
                                            nodes 
                                            |> List.find (fun n -> n.id = id))}]
    nodes

convert (Map [1,[2;3]; 2,[3]; 3,[1]])

The key is that by making the neighbor list lazy, we can first create the set of all nodes that we care about before populating the set of neighbors (the neighbor computation is specified at the same time as the node is created, but not run until later).