f# - 在给定目的地的(DAG)有向无环图中寻找路径

Question

假设我有这个数组:

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)

返回

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 之外还有其他结构吗？这将是实现这一目标的更好方法？

在此先感谢您的帮助。

Answer 1

我假设你想得到一个带有“数字”的整数对列表，这些数字直接或间接地报告给某个“根”。
这是一个简单但效率低下的解决方案:

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以下列方式作为图表:

int s 是顶点

一对 int s 是有向边

然后使用 DFS 简单地检查哪些边可以从“根”访问。 .