Private/Get-TopologicalSort.ps1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# From https://stackoverflow.com/a/13350764
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
}