如何在PowerShell中进行拓扑排序

Question

对于我的项目，我需要根据其依赖关系对 PSCustomObject 的数组进行排序。类似的问题How to sort array of dependency?有一个有用的提示，但它不包含任何代码。问题 Topological Sorting using LINQ 确实包含代码，但仅基于 C#。

因此，我决定创建简单的数据集，以便能够在将其放入我的完整项目之前使用最小的、可重现的示例（andwer）来检查我的想法：

$Array = ConvertFrom-Json @'
[
  { "Name": "Function1", "Dependency": ["Function3"] },
  { "Name": "Function2", "Dependency": ["Function3", "Function4", "Function5"] },
  { "Name": "Function3", "Dependency": [] },
  { "Name": "Function4", "Dependency": ["Function1", "Function5"] },
  { "Name": "Function5", "Dependency": ["Function1"] }
]
'@

任务是对对象进行排序，以便首先加载其他对象所需的任何对象，这意味着预期结果顺序应如下所示：

Name      Dependency
----      ----------
Function3 {}
Function1 {Function3}
Function5 {Function1}
Function4 {Function1, Function5}
Function2 {Function3, Function4, Function5}

Answer 1

我认为这是一个非常常见的用例（例如创建模块构建器），我决定在这里分享我的一般方法，因为我知道您可能无法使用标准可用的

Sort-Object

cmdlet 来实现这一点计算属性，因为它需要 .Net IComparer 接口。

Using Namespace System.Collections.Generic

class DependencyComparer : IComparer[PSCustomObject] {
    [int] Compare ([PSCustomObject]$1, [PSCustomObject]$2) {
        if ($1.Name -in $1.Dependency) {
            Throw "Object named '$($1.Name)' has a cyclic dependency with itself."
        }
        $1in2 = $1.Name -in $2.Dependency
        $2in1 = $2.Name -in $1.Dependency
        # write-host $1.Name  $2.Name $1in2 $2in1
        if ($1in2 -and $2in1) {
            Throw "Object named '$($1.Name)' has a cyclic dependency with the object named '$($2.Name)'."
        }
        if ($1in2) { return -1 }
        if ($2in1) { return 1 }
        return 0
    }
}

知道无法在

PowerShell

数组上使用 .Sort() 方法，因此需要先将其转换为

[List[PSCustomObject]]

：

$List = [List[PSCustomObject]]$Array
$List.Sort([DependencyComparer]::new())
$List

Name      Dependency
----      ----------
Function3 {}
Function1 {Function3}
Function5 {Function1}
Function4 {Function1, Function5}
Function2 {Function3, Function4, Function5}

请注意，在循环对象依赖的情况下：

• 如果循环对象依赖于自身以及两个对象之间，您将收到错误消息：

  cyclic object dependencies with itself and between two objects

  
  比较中提到的错误可以在：

  $Error[0].Exception.InnerException.InnerException.ErrorRecord

  下找到，例如：
  

  Object named 'Function5' has a cycled dependency with the object named 'Function2'.

• 比较不会检查3个或更多对象的循环依赖关系，例如：

$Array = ConvertFrom-Json @'
[
  { "Name": "Function1", "Dependency": ["Function2"] },
  { "Name": "Function2", "Dependency": ["Function3"] },
  { "Name": "Function3", "Dependency": ["Function1"] }
]
'@

相关：

• #24560

  将 -Comparer 参数添加到 Sort-Object

• #23959

  基类规范中“不支持指定的方法”