在给定目的地的（DAG）有向无环图中查找路径
Finding paths in (DAG) directed acyclic graph given destination
假设我有这个数组：
let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|]
元组中的第一个 int 向第二个 int 报告。
我可以用
轻松映射
let orgMap = Map.ofArray reporting
从那里，我可以很容易地得到一个向 2 报告的所有整数的列表
orgMap
|> Map.filter (fun _ key -> key = 2)
哪个returns
map [(3, 2); (4, 2)]
然而，我真正想看到的是整个结构，从 2 一直向下。例如，我想找到一种可以给我样本输出的方法
map [(3, 2); (4, 2); (5, 3); (6, 4); (7, 3)]
如果我要找人 2 或
map [(5, 3); (7, 3)]
如果我对第 3 个人感兴趣。
我可以这样做吗？如果是这样，如何？除了 map 之外，还有其他结构可以更好地实现这一目标吗？
在此先感谢您的帮助。
我假设你想获得一对整数列表 "numbers" 直接或间接报告给某些 "root"。
这是一个简单但效率低下的解决方案：
let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|]
let reportStructureSet =
reportStructure |> Set.ofArray
let reportingDirectlyTo root raportsToSet =
raportsToSet
|> Set.filter(fun (_, key) -> key = root)
let addNextGeneration previousIteration raportsToSet =
let numbersLowerInHierarchy = previousIteration |> Set.map fst
raportsToSet |> Set.filter(
// select only those elements from raportsToSet...
fun (num, supervisor) ->
// ...which either are already in previousIteration
(Set.contains (num, supervisor) previousIteration) ||
// ...or are "below" someone from previousIteration
(Set.contains supervisor numbersLowerInHierarchy))
let reportingDirectlyOrIndirectlyTo root raportsToSet =
// applies addNextGeneration until is "stabilizes" on some value
let rec fixPointHelper previousIteration =
let nextIteration = addNextGeneration previousIteration raportsToSet
if nextIteration = previousIteration
then nextIteration
else fixPointHelper nextIteration
// set of numbers directly reporting to root
let reportsDirectly = reportingDirectlyTo root raportsToSet
// start "iteration" using numbers directly reporting to root
fixPointHelper reportsDirectly
let reportingDirectlyOrIndirectlyToList root raportsToSet =
reportingDirectlyOrIndirectlyTo root raportsToSet
|> Set.toList
如果您想实施有效的解决方案，您应该将 reportStructureSet 解释为以下方式的图表：
ints是顶点- 一对
int是有向边
然后使用 DFS.
简单地检查从 "root" 可以到达哪些边
由于 OCaml 接近于 F#，并且试图在 F# 中找到拓扑排序没有找到任何有用的东西，所以我寻找了 OCaml 代码。
我发现 An Introduction to Objective Caml 使用深度优先搜索解决了您的问题，并将其用作此答案的基础。另外，由于您是 F# 的新手，您可以查看文档并查看代码是如何派生的。奇怪的是，我在发布后查看了文档的其余部分，他在文档的后面有一个更高级的 DFS 版本。
你的输入是一个数组 [| |] 但你的答案是一个列表 [] 所以我做了大部分工作作为列表。
答案的顺序与您的顺序不同，但格式相同。
let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|]
//
// 6 -> 4 -> 2
// 5 -> 3 -> 2 -> 1
// 7 -> 3
// val revStructure : tl:('a * 'b) list -> ('b * 'a) list
let revStructure tl = List.map (fun (a,b) -> (b,a)) tl
// val mem : item:'a -> list:'a list -> bool when 'a : equality
let mem item list = List.exists (fun x -> x = item) list
// val successors : n:'a -> edges:('a * 'b) list -> 'b list when 'a : equality
let successors n edges =
let matching (s,_) = s = n
List.map snd (List.filter matching edges)
// val dist : pred:'a -> succs:'b list -> ('a * 'b) list
let dist pred succs = List.map (fun y -> (pred,y)) succs
// val dfsPairs : edges:('a * 'a) list -> start:'a -> ('a * 'a) list when 'a : equality
let dfsPairs edges start =
let rec dfsPairsInner edges visited start result =
match start with
| [] -> List.rev (revStructure result)
| n::nodes ->
if mem n visited then
dfsPairsInner edges visited nodes result
else
let predecessors = dist n (successors n edges)
let result =
match predecessors with
| [] -> result
| _ -> predecessors @ result
dfsPairsInner edges (n::visited) ((successors n edges) @ nodes) result
dfsPairsInner edges [] [start] []
let revEdges = revStructure (List.ofArray reportStructure)
let result = dfsPairs revEdges 2
// val result : (int * int) list = [(4, 2); (3, 2); (7, 3); (5, 3); (6, 4)]
let result = dfsPairs revEdges 3
// val result : (int * int) list = [(7, 3); (5, 3)]
我喜欢 f# 拼图，所以我试了一下这个。我希望你喜欢。
let orgList = [(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)]
let orgMap =
orgList
|> List.fold (fun acc item ->
let key = snd item
match Map.tryFind key acc with
| Some(value) ->
let map' = Map.remove key acc
Map.add(key) (item::value) map'
| None ->
Map.add(key) (item::[]) acc
) Map.empty<int, (int*int) list>
let findReports supervisor =
let rec findReports' acc collection =
match collection with
| head::tail ->
(findReports' (head::acc) tail)
@ match Map.tryFind (fst head) orgMap with
| Some(value) -> (findReports' [] value)
| None -> []
| [] -> acc
findReports' [] (Map.find supervisor orgMap)
findReports 2
|> List.map fst
|> List.distinct
returns
val it : int list = [3; 4; 5; 7; 6]
findReports 2returns
val it : (int * int) list = [(3, 2); (4, 2); (5, 3); (7, 3); (6, 4)]
我会分解它来澄清。
let orgList = [ (1, 2); (1, 3); (1, 4); (2, 5); (3, 6); (4, 5); (5, 6); (5, 7) ]
我们获取您的元组列表并创建老板到（（报告，老板）列表）的功能映射。这可能被称为邻接表，用于遍历图。
let orgMap =
orgList
|> List.fold (fun acc item ->
let key = snd item
match Map.tryFind key acc with
如果老板手下有报告列表，请添加到该列表中。
| Some(reports) ->
let map' = Map.remove key acc
Map.add(key) (item::reports) map'
否则，添加到一个空列表并插入到字典中。
| None ->
Map.add(key) (item::[]) acc
从一张空地图作为累加器开始。
) Map.empty<int, (int*int) list>
通过项目递归查找所有报告。
let findReports supervisor =
let rec findReports' acc collection =
match collection with
如果有项，将其追加到累加器中。这就是 BFS。如果在连接运算符 (@) 前后切换表达式，它将变成 DFS。
| head::tail ->
(findReports' (head::acc) tail)
将当前列表连接到报表的递归列表。
@ match Map.tryFind (fst head) orgMap with
| Some(value) -> (findReports' [] value)
| None -> []
如果在列表末尾，return 列表。
| [] -> acc
运行递归函数。
findReports' [] (Map.find supervisor orgMap)
运行 函数。
findReports 7
Return 仅报告
|> List.map fst
请勿二次举报。
|> List.distinct
假设我有这个数组：
let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|]
元组中的第一个 int 向第二个 int 报告。
我可以用
轻松映射let orgMap = Map.ofArray reporting
从那里，我可以很容易地得到一个向 2 报告的所有整数的列表
orgMap
|> Map.filter (fun _ key -> key = 2)
哪个returns
map [(3, 2); (4, 2)]
然而，我真正想看到的是整个结构，从 2 一直向下。例如，我想找到一种可以给我样本输出的方法
map [(3, 2); (4, 2); (5, 3); (6, 4); (7, 3)]
如果我要找人 2 或
map [(5, 3); (7, 3)]
如果我对第 3 个人感兴趣。
我可以这样做吗？如果是这样，如何？除了 map 之外，还有其他结构可以更好地实现这一目标吗？
在此先感谢您的帮助。
我假设你想获得一对整数列表 "numbers" 直接或间接报告给某些 "root"。 这是一个简单但效率低下的解决方案：
let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|]
let reportStructureSet =
reportStructure |> Set.ofArray
let reportingDirectlyTo root raportsToSet =
raportsToSet
|> Set.filter(fun (_, key) -> key = root)
let addNextGeneration previousIteration raportsToSet =
let numbersLowerInHierarchy = previousIteration |> Set.map fst
raportsToSet |> Set.filter(
// select only those elements from raportsToSet...
fun (num, supervisor) ->
// ...which either are already in previousIteration
(Set.contains (num, supervisor) previousIteration) ||
// ...or are "below" someone from previousIteration
(Set.contains supervisor numbersLowerInHierarchy))
let reportingDirectlyOrIndirectlyTo root raportsToSet =
// applies addNextGeneration until is "stabilizes" on some value
let rec fixPointHelper previousIteration =
let nextIteration = addNextGeneration previousIteration raportsToSet
if nextIteration = previousIteration
then nextIteration
else fixPointHelper nextIteration
// set of numbers directly reporting to root
let reportsDirectly = reportingDirectlyTo root raportsToSet
// start "iteration" using numbers directly reporting to root
fixPointHelper reportsDirectly
let reportingDirectlyOrIndirectlyToList root raportsToSet =
reportingDirectlyOrIndirectlyTo root raportsToSet
|> Set.toList
如果您想实施有效的解决方案，您应该将 reportStructureSet 解释为以下方式的图表：
ints是顶点- 一对
int是有向边
然后使用 DFS.
简单地检查从 "root" 可以到达哪些边由于 OCaml 接近于 F#，并且试图在 F# 中找到拓扑排序没有找到任何有用的东西，所以我寻找了 OCaml 代码。
我发现 An Introduction to Objective Caml 使用深度优先搜索解决了您的问题，并将其用作此答案的基础。另外，由于您是 F# 的新手，您可以查看文档并查看代码是如何派生的。奇怪的是，我在发布后查看了文档的其余部分，他在文档的后面有一个更高级的 DFS 版本。
你的输入是一个数组 [| |] 但你的答案是一个列表 [] 所以我做了大部分工作作为列表。
答案的顺序与您的顺序不同，但格式相同。
let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|]
//
// 6 -> 4 -> 2
// 5 -> 3 -> 2 -> 1
// 7 -> 3
// val revStructure : tl:('a * 'b) list -> ('b * 'a) list
let revStructure tl = List.map (fun (a,b) -> (b,a)) tl
// val mem : item:'a -> list:'a list -> bool when 'a : equality
let mem item list = List.exists (fun x -> x = item) list
// val successors : n:'a -> edges:('a * 'b) list -> 'b list when 'a : equality
let successors n edges =
let matching (s,_) = s = n
List.map snd (List.filter matching edges)
// val dist : pred:'a -> succs:'b list -> ('a * 'b) list
let dist pred succs = List.map (fun y -> (pred,y)) succs
// val dfsPairs : edges:('a * 'a) list -> start:'a -> ('a * 'a) list when 'a : equality
let dfsPairs edges start =
let rec dfsPairsInner edges visited start result =
match start with
| [] -> List.rev (revStructure result)
| n::nodes ->
if mem n visited then
dfsPairsInner edges visited nodes result
else
let predecessors = dist n (successors n edges)
let result =
match predecessors with
| [] -> result
| _ -> predecessors @ result
dfsPairsInner edges (n::visited) ((successors n edges) @ nodes) result
dfsPairsInner edges [] [start] []
let revEdges = revStructure (List.ofArray reportStructure)
let result = dfsPairs revEdges 2
// val result : (int * int) list = [(4, 2); (3, 2); (7, 3); (5, 3); (6, 4)]
let result = dfsPairs revEdges 3
// val result : (int * int) list = [(7, 3); (5, 3)]
我喜欢 f# 拼图，所以我试了一下这个。我希望你喜欢。
let orgList = [(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)]
let orgMap =
orgList
|> List.fold (fun acc item ->
let key = snd item
match Map.tryFind key acc with
| Some(value) ->
let map' = Map.remove key acc
Map.add(key) (item::value) map'
| None ->
Map.add(key) (item::[]) acc
) Map.empty<int, (int*int) list>
let findReports supervisor =
let rec findReports' acc collection =
match collection with
| head::tail ->
(findReports' (head::acc) tail)
@ match Map.tryFind (fst head) orgMap with
| Some(value) -> (findReports' [] value)
| None -> []
| [] -> acc
findReports' [] (Map.find supervisor orgMap)
findReports 2
|> List.map fst
|> List.distinct
returns
val it : int list = [3; 4; 5; 7; 6]
findReports 2returns
val it : (int * int) list = [(3, 2); (4, 2); (5, 3); (7, 3); (6, 4)]
我会分解它来澄清。
let orgList = [ (1, 2); (1, 3); (1, 4); (2, 5); (3, 6); (4, 5); (5, 6); (5, 7) ]
我们获取您的元组列表并创建老板到（（报告，老板）列表）的功能映射。这可能被称为邻接表，用于遍历图。
let orgMap =
orgList
|> List.fold (fun acc item ->
let key = snd item
match Map.tryFind key acc with
如果老板手下有报告列表，请添加到该列表中。
| Some(reports) ->
let map' = Map.remove key acc
Map.add(key) (item::reports) map'
否则，添加到一个空列表并插入到字典中。
| None ->
Map.add(key) (item::[]) acc
从一张空地图作为累加器开始。
) Map.empty<int, (int*int) list>
通过项目递归查找所有报告。
let findReports supervisor =
let rec findReports' acc collection =
match collection with
如果有项，将其追加到累加器中。这就是 BFS。如果在连接运算符 (@) 前后切换表达式，它将变成 DFS。
| head::tail ->
(findReports' (head::acc) tail)
将当前列表连接到报表的递归列表。
@ match Map.tryFind (fst head) orgMap with
| Some(value) -> (findReports' [] value)
| None -> []
如果在列表末尾，return 列表。
| [] -> acc
运行递归函数。
findReports' [] (Map.find supervisor orgMap)
运行 函数。
findReports 7
Return 仅报告
|> List.map fst
请勿二次举报。
|> List.distinct