有没有人有PowerShell的依赖图和拓扑排序代码片段？ [英] Does anyone have a Dependency graph and topological sorting code snippet for PowerShell?

问题描述

我们正在尝试使用依赖图和拓扑排序并行化构建。

我们的所有构建逻辑都是用Msbuild编写的，我们正在使用powershell来调用它。 / p>

有没有使用powershell实现依赖图和拓扑排序？

我知道在unix中有一个实用程序称为tsort可用。有没有类似的东西可以在PowerShell中使用？

这篇文章给了很好的主意，但是在C＃ http://msdn.microsoft.com/en-us/magazine/dd569760.aspx

解决方案

我快速翻译了维基百科的拓扑排序算法a>：

  function Get-TopologicalSort {
 param（
 [Parameter（Mandatory = $ true，位置= 0）] 
 [hashtable] $ edgeList 
）
 
＃确保我们可以使用HashSet 
添加类型-AssemblyName System.Core 
 
＃克隆它，以便不更改原始
 $ currentEdgeList = [hashtable]（Get-ClonedObject $ edgeList）
 
＃algorithm from http://en.wikipedia.org / wiki / Topological_sorting＃Algorithms 
 $ topologicalSortedElements = New-Object System.Collections.ArrayList 
 $ setOfAllNodesWithNoIncomingEdges = New-Object System.Collections.Queue 
 
 $ fasterEdgeList = @ {} 
 
＃跟踪所有节点，以防它们放在边缘目的地但不是源
 $ allNodes = New-Object -TypeName System.Collections.Generic.HashSet [object] -ArgumentList（，[object []] $ currentEdgeList.Keys）
 
 foreach（$ currentNode in $ currentEdgeList.Keys）{
 $ currentDestinationNodes = [array] $ currentEdgeList [$ currentNode] 
 if（$ currentDestinationNodes.Length -eq 0）{
 $ setOfAllNodesWithNoIncomingEdges.Enqueue （$ currentNode）
} 
 
 foreach（$ currentDestinationNodes中的$ currentDestinationNode）{
 if（！$ allNodes.Contains（$ currentDestinationNode））{
 [void] $ allNodes.Add（$ currentDestinationNode）
} 
} 
 
＃花费这个时间将它们转换为HashSet以实现更快的操作
 $ currentDestinationNodes = New-Object -TypeName System.Collections.Generic.HashSet [object] -ArgumentList（，[object []] $ currentDestinationNodes）
 [void] $ fasterEdgeList.Add（$ currentNode，$ currentDestinationNodes）
} 
 
＃现在让我们通过为源节点添加空的依赖关系来调和，他们没有告诉我们关于
 foreach（$ allNode中的$ currentNode）{
 if（！$ currentEdgeList.ContainsKey（$ currentNode ）$ {
 [void] $ currentEdgeList.Add（$ currentNode，（New-Object -TypeName System.Collections.Generic.HashSet [object]））
 $ setOfAllNodesWithNoIncomingEdges.Enqueue（$ currentNode）
 $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。 dequeue（）
 [void] $ currentEdgeList.Remove（$ currentNode）
 [void] $ topologicalSortedElements.Add（$ currentNode）
 
 foreach（$ currentEdgeSourceNode in $ currentEdgeList.Keys）{
 $ currentNodeDestinations = $ currentEdgeList [$ currentEdgeSourceNode] 
 if（$ currentNodeDestinations.Contains（$ currentNode））{
 [void] $ currentNodeDestinations.Remove（$ currentNode） 
 
 if（$ currentNodeDestinations.Count -eq 0）{
 [void] $ setOfAllNodesWithNoIncomingEdges.Enqueue（$ currentEdgeSourceNode）
} 
} 
} 
} 
 
 if（$ currentEdgeList.Count -gt 0）{
 throw图表至少有一个循环！ 
} 
 
 return $ topologicalSortedElements 
} 
  

这取决于

 ＃来自http://stackoverflow.com/questions/7468707/deep-copy-a-dictionary- hashtable-in-powershell 
函数Get-ClonedObject {
 param（$ DeepCopyObject）
 $ memStream = new-object IO.MemoryStream 
 $ formatter = new-object Runtime.Serialization。 Formatters.Binary.BinaryFormatter 
 $ formatter.Serialize（$ memStream，$ DeepCopyObject）
 $ memStream.Position = 0 
 $ formatter.Deserialize（$ memStream）
} 
  

而且你这样使用

 ＃对维基百科的例子进行排序：
 Get-TopologicalSort @ {11 = @（7,5）; 8 = @（7,3）; 2 = @（11）; 9 = 11,8）; 10 = @（11,3）} 
  

哪个产生：

  7 
 5 
 3 
 11 
 8 
 10 
 2 
 9 
  

We were trying to parallelize our build with dependency graph and topological sorting.

All our build logic is written in Msbuild and we are using powershell to call it.

Has any one implemented dependency graph and topological sorting using powershell?

I know that in unix there is a utility called tsort available. Is there any thing similar available in powershell?

This article gives good idea but it is done in C# "http://msdn.microsoft.com/en-us/magazine/dd569760.aspx"

解决方案

I did a quick translation of Wikipedia's Topological Sort Algorithm:

function Get-TopologicalSort {
  param(
      [Parameter(Mandatory = $true, Position = 0)]
      [hashtable] $edgeList
  )

  # Make sure we can use HashSet
  Add-Type -AssemblyName System.Core

  # Clone it so as to not alter original
  $currentEdgeList = [hashtable] (Get-ClonedObject $edgeList)

  # algorithm from http://en.wikipedia.org/wiki/Topological_sorting#Algorithms
  $topologicallySortedElements = New-Object System.Collections.ArrayList
  $setOfAllNodesWithNoIncomingEdges = New-Object System.Collections.Queue

  $fasterEdgeList = @{}

  # Keep track of all nodes in case they put it in as an edge destination but not source
  $allNodes = New-Object -TypeName System.Collections.Generic.HashSet[object] -ArgumentList (,[object[]] $currentEdgeList.Keys)

  foreach($currentNode in $currentEdgeList.Keys) {
      $currentDestinationNodes = [array] $currentEdgeList[$currentNode]
      if($currentDestinationNodes.Length -eq 0) {
          $setOfAllNodesWithNoIncomingEdges.Enqueue($currentNode)
      }

      foreach($currentDestinationNode in $currentDestinationNodes) {
          if(!$allNodes.Contains($currentDestinationNode)) {
              [void] $allNodes.Add($currentDestinationNode)
          }
      }

      # Take this time to convert them to a HashSet for faster operation
      $currentDestinationNodes = New-Object -TypeName System.Collections.Generic.HashSet[object] -ArgumentList (,[object[]] $currentDestinationNodes )
      [void] $fasterEdgeList.Add($currentNode, $currentDestinationNodes)        
  }

  # Now let's reconcile by adding empty dependencies for source nodes they didn't tell us about
  foreach($currentNode in $allNodes) {
      if(!$currentEdgeList.ContainsKey($currentNode)) {
          [void] $currentEdgeList.Add($currentNode, (New-Object -TypeName System.Collections.Generic.HashSet[object]))
          $setOfAllNodesWithNoIncomingEdges.Enqueue($currentNode)
      }
  }

  $currentEdgeList = $fasterEdgeList

  while($setOfAllNodesWithNoIncomingEdges.Count -gt 0) {        
      $currentNode = $setOfAllNodesWithNoIncomingEdges.Dequeue()
      [void] $currentEdgeList.Remove($currentNode)
      [void] $topologicallySortedElements.Add($currentNode)

      foreach($currentEdgeSourceNode in $currentEdgeList.Keys) {
          $currentNodeDestinations = $currentEdgeList[$currentEdgeSourceNode]
          if($currentNodeDestinations.Contains($currentNode)) {
              [void] $currentNodeDestinations.Remove($currentNode)

              if($currentNodeDestinations.Count -eq 0) {
                  [void] $setOfAllNodesWithNoIncomingEdges.Enqueue($currentEdgeSourceNode)
              }                
          }
      }
  }

  if($currentEdgeList.Count -gt 0) {
      throw "Graph has at least one cycle!"
  }

  return $topologicallySortedElements
}

This depends on

# Idea from http://stackoverflow.com/questions/7468707/deep-copy-a-dictionary-hashtable-in-powershell 
function Get-ClonedObject {
    param($DeepCopyObject)
    $memStream = new-object IO.MemoryStream
    $formatter = new-object Runtime.Serialization.Formatters.Binary.BinaryFormatter
    $formatter.Serialize($memStream,$DeepCopyObject)
    $memStream.Position=0
    $formatter.Deserialize($memStream)
}

And you use it like this

# Sort the Wikipedia example:
Get-TopologicalSort @{11=@(7,5);8=@(7,3);2=@(11);9=@(11,8);10=@(11,3)}

Which yields:

7
5
3
11
8
10
2
9

这篇关于有没有人有PowerShell的依赖图和拓扑排序代码片段？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！