使用不可变列表创建具有链接节点的邻接列表
Create adjacency list with linked nodes using immutable lists
我正在尝试创建一个包含当前定义如下的链接节点的邻接列表：
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
我要创建列表的输入是格式为
的字符串序列
node_name neighbor_name_1 ... neighbor_name_n
所以，基本上这应该是一个简单的任务，但我想不出一种方法来更新没有 运行 的节点进入一个循环，当一个节点，例如A，有一条到 B 的边，B 有一条到 A 的边。在这种情况下，我必须在创建其节点对象时更新 B 的邻居，然后将节点 A 中的邻居引用更新为节点 B，这又让我离开再次更新节点 B 等等。
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
我之前已经在 C# 中实现了该算法（使用可变列表），所以我在这里可能遗漏了一点。当然我也可以使用可变列表，但我想尝试使用不可变列表。
我认为没有任何方法可以用您的确切表示来做您想做的事。一个简单的替代方法是使邻居集合变得惰性：
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]])
关键是通过使邻居列表惰性化，我们可以首先创建我们关心的所有节点的集合然后填充邻居集合（邻居computation是在创建节点的同时指定的，但不是运行直到后来）。
在 C# 中，您将包含对相邻节点的引用。但是根据您的定义，您有一个 Neighbor 节点，这使它成为一项不可能完成的任务。
除了@kvb 的解决方案外，还有其他选择：
选项 1： 使用 string list
对我来说，让列表引用节点名称而不是节点本身更有意义：
type Node =
{
Name : string
Neighbors: string list
}
首先是一些辅助函数：
let addRelation relations (node1, node2) =
relations
|> Set.add (node1, node2)
|> Set.add (node2, node1)
let allRelations nodes =
nodes |> List.fold addRelation Set.empty
这将是创建它的方式：
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
基本上你给它一个包含一对名字的列表：
["1", "2"
"3", "4"
"1", "3"
"4", "5" ]
|> getNodes
|> Seq.iter (printfn "%A")
产生：
{Name = "1";
Neighbors = ["2"; "3"];}
{Name = "2";
Neighbors = ["1"];}
{Name = "3";
Neighbors = ["1"; "4"];}
{Name = "4";
Neighbors = ["3"; "5"];}
{Name = "5";
Neighbors = ["4"];}
选项 2： ref 到 Node list
您可以参考邻居节点列表：
type Node =
{
Name : string
Neighbors: Node list ref
}
这样您可以先创建节点，然后将它们添加到列表中：
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
这样测试：
["1", "2"
"3", "4"
"1", "3"
"4", "5" ]
|> getNodes
|> Seq.iter (printfn "%A")
输出：
{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 = [...];};}; ...];};}; ...];};};
...];};}];};}
您的方法的问题是 Node 类型。我提出了这样一种不同的方法：
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
我正在尝试创建一个包含当前定义如下的链接节点的邻接列表：
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
我要创建列表的输入是格式为
的字符串序列node_name neighbor_name_1 ... neighbor_name_n
所以，基本上这应该是一个简单的任务，但我想不出一种方法来更新没有 运行 的节点进入一个循环，当一个节点，例如A，有一条到 B 的边，B 有一条到 A 的边。在这种情况下，我必须在创建其节点对象时更新 B 的邻居，然后将节点 A 中的邻居引用更新为节点 B，这又让我离开再次更新节点 B 等等。
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
我之前已经在 C# 中实现了该算法（使用可变列表），所以我在这里可能遗漏了一点。当然我也可以使用可变列表，但我想尝试使用不可变列表。
我认为没有任何方法可以用您的确切表示来做您想做的事。一个简单的替代方法是使邻居集合变得惰性：
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]])
关键是通过使邻居列表惰性化，我们可以首先创建我们关心的所有节点的集合然后填充邻居集合（邻居computation是在创建节点的同时指定的，但不是运行直到后来）。
在 C# 中，您将包含对相邻节点的引用。但是根据您的定义，您有一个 Neighbor 节点，这使它成为一项不可能完成的任务。 除了@kvb 的解决方案外，还有其他选择：
选项 1： 使用 string list
对我来说，让列表引用节点名称而不是节点本身更有意义：
type Node =
{
Name : string
Neighbors: string list
}
首先是一些辅助函数：
let addRelation relations (node1, node2) =
relations
|> Set.add (node1, node2)
|> Set.add (node2, node1)
let allRelations nodes =
nodes |> List.fold addRelation Set.empty
这将是创建它的方式：
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
基本上你给它一个包含一对名字的列表：
["1", "2"
"3", "4"
"1", "3"
"4", "5" ]
|> getNodes
|> Seq.iter (printfn "%A")
产生：
{Name = "1";
Neighbors = ["2"; "3"];}
{Name = "2";
Neighbors = ["1"];}
{Name = "3";
Neighbors = ["1"; "4"];}
{Name = "4";
Neighbors = ["3"; "5"];}
{Name = "5";
Neighbors = ["4"];}
选项 2： ref 到 Node list
您可以参考邻居节点列表：
type Node =
{
Name : string
Neighbors: Node list ref
}
这样您可以先创建节点，然后将它们添加到列表中：
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
这样测试：
["1", "2"
"3", "4"
"1", "3"
"4", "5" ]
|> getNodes
|> Seq.iter (printfn "%A")
输出：
{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 = [...];};}; ...];};}; ...];};};
...];};}];};}
您的方法的问题是 Node 类型。我提出了这样一种不同的方法：
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