I've been asked to create some code to help automate the loading of data into a system based on employee data in a spreadsheet. However, the data isn't clean, so some people may have no manager, some may be their own manager, some have managers who already exist in the system, so aren't included in the export, and others managers are somewhere in the export. Ideally we'd create managers before creating their subordinates, to set both values in one pass (rather than creating all accounts, then updating the managers).
The below sort algorithm is to allow a sort of such dirty data, to ensure that where a dependency chain can be resolved it is and the items are returned in the appropriate order; but if the data's bad, we'll still be able to do as much good as possible.
Sharing it here as there may be a more efficient solution. I've seem similar solutions which build a tree then traverse it; but all those I've seen require clean data to function correct, and I can't think of a way to amend them whilst keeping their efficiency.
Function Sort-ParentChild {
[CmdletBinding()]
Param (
[Parameter(Mandatory, ValueFromPipeline)]
[PSCustomObject[]]$ListItems
,
[Parameter(Mandatory)]
[string]$ParentPropertyName
,
[Parameter(Mandatory)]
[string]$CurrentPropertyName
)
Begin {
[System.Collections.Generic.List[PSCustomObject]]$Pending = [System.Collections.Generic.List[PSCustomObject]]::new()
}
Process {
foreach ($item in $ListItems) {
# first return items which have no parent, or which are their own parent (since circular dependencies would otherwise never be resolved
if (($null -eq $item."$ParentPropertyName") -or (($item."$CurrentPropertyName" -eq $item."$ParentPropertyName"))) {
$item
} else {
$Pending.Add($item)
}
}
}
End {
while ($Pending.Count) {
$circularLoop = $true
# return any items whose parents are not in the pending list (i.e. they already existed so weren't in the todo list, or we've returned them earlier in the process)
for ($i = ($Pending.Count-1); $i -ge 0; $i--) { # work down, so that removing an item won't have any odd impacts
if ($Pending[$i]."$ParentPropertyName" -notin @($Pending | Select-Object -ExpandProperty $CurrentPropertyName)) {
$Pending[$i]
$Pending.RemoveAt($i)
$circularLoop = $false # if we've found something to return, we're not in a loop yet
}
}
if ($circularLoop) {
# in case there are any circular dependencies, to avoid getting stuck, return a single item, then try to unravel in dependency order from there
Write-Warning "Circular dependency found; breaking loop by returning $($Pending[0]."$CurrentPropertyName")"
$Pending[0]
$Pending.RemoveAt(0)
}
}
}
}
Example Usage
$users = @(
@{Id = 'Subordinate17'; ManagerId = 'MiddleManager1'}
@{Id = 'Subordinate15'; ManagerId = 'MiddleManager1'}
@{Id = 'Subordinate14'; ManagerId = 'MiddleManager3'}
@{Id = 'Subordinate13'; ManagerId = 'MiddleManager1'}
@{Id = 'TopDog'; ManagerId = $null} # this person's the top dog; they don't have a manager
@{Id = 'MiddleManager1'; ManagerId = 'BigBoss1'}
@{Id = 'BigBoss1'; ManagerId = 'BigBoss1'} # Big Boss is their own boss
@{Id = 'AmbassadorX'; ManagerId = 'PilotX'}
@{Id = 'MiddleManager2'; ManagerId = 'BigBoss1'}
@{Id = 'PilotX'; ManagerId = 'InstructorX'}
@{Id = 'Subordinate17'; ManagerId = 'MiddleManager1'}
@{Id = 'MiddleManager3'; ManagerId = 'TopDog'}
@{Id = 'Subordinate16'; ManagerId = 'MiddleManager3'}
@{Id = 'Mya'; ManagerId = 'PilotX'}
@{Id = 'Subordinate12'; ManagerId = 'MiddleManager2'}
@{Id = 'Subordinate11'; ManagerId = 'MiddleManager1'}
@{Id = 'InstructorX'; ManagerId = 'AmbassadorX'}
@{Id = 'Subordinate10'; ManagerId = 'MiddleManager2'}
@{Id = 'Subordinate09'; ManagerId = 'MiddleManager2'}
@{Id = 'Subordinate08'; ManagerId = 'MiddleManager2'}
@{Id = 'Subordinate07'; ManagerId = 'MiddleManager2'}
@{Id = 'Subordinate06'; ManagerId = 'MiddleManager2'}
@{Id = 'Subordinate05'; ManagerId = 'TopDog'}
@{Id = 'Subordinate04'; ManagerId = 'BigBoss1'}
@{Id = 'Subordinate03'; ManagerId = 'MiddleManager3'}
@{Id = 'Shark'; ManagerId = $null} # alone shark :S
@{Id = 'Subordinate02'; ManagerId = 'MiddleManager3'}
@{Id = 'Subordinate01'; ManagerId = 'MiddleManager3'}
) | %{[pscustomobject]$_} #| Sort -Property @{E={[Guid]::NewGuid()}} # optional chaos sort, to avoid any chance of my data being in some helpful order before testing
$users | Sort-ParentChild -ParentPropertyName 'ManagerId' -CurrentPropertyName 'Id'
Example Output
WARNING: Circular dependency found; breaking loop by returning AmbassadorX
Id ManagerId
-- ---------
TopDog
BigBoss1 BigBoss1
Shark
Subordinate04 BigBoss1
Subordinate05 TopDog
MiddleManager3 TopDog
MiddleManager2 BigBoss1
MiddleManager1 BigBoss1
Subordinate13 MiddleManager1
Subordinate14 MiddleManager3
Subordinate15 MiddleManager1
Subordinate17 MiddleManager1
Subordinate01 MiddleManager3
Subordinate02 MiddleManager3
Subordinate03 MiddleManager3
Subordinate06 MiddleManager2
Subordinate07 MiddleManager2
Subordinate08 MiddleManager2
Subordinate09 MiddleManager2
Subordinate10 MiddleManager2
Subordinate11 MiddleManager1
Subordinate12 MiddleManager2
Subordinate16 MiddleManager3
Subordinate17 MiddleManager1
AmbassadorX PilotX
InstructorX AmbassadorX
PilotX InstructorX
Mya PilotX
