PowerShell에 대한 종속성 그래프 및 토폴로지 정렬 코드 스 닙트가 있습니까?

Question

우리는 의존성 그래프와 토폴로지 정렬을 사용하여 빌드를 병렬화하려고했습니다.

우리의 모든 빌드 논리는 Msbuild로 작성되었으며 powershell을 사용하여 호출합니다.

powershell을 사용하여 구현 된 의존성 그래프 및 토폴로지 정렬 중 하나가 있습니까?

유닉스에는 tsort라는 유틸리티가 있습니다. powershell에서 비슷한 것을 사용할 수 있습니까?

이 문서에서는 좋은 아이디어를 제공합니다 있지만 내가 Wikipedia's Topological Sort Algorithm의 빠른 번역 한 C#을 "http://msdn.microsoft.com/en-us/magazine/dd569760.aspx"

Answer 1

로 수행됩니다

# 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) 
} 

에

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 
} 

이 의존을 그리고 당신이 그것을 사용 like

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

산출

:

7 
5 
3 
11 
8 
10 
2 
9