Granted it took me a while to come up with an optimized solution for you. Here goes:
Solution (Graphs!)
Ok, why don't you approach this the same way you would in an OOP language:
# Use a hashtable for O(1) lookup for a node by name
$Script:NodeTracker = @{}
class TaskNode {
#==PROPS==================================================|
[System.Collections.ArrayList]$then = @()
[String] $Val
[Bool]$Visited = $false
[Collections.ArrayList]$Parent = @()
#==CONSTRUCTORS===========================================|
TaskNode([String]$Val) {$this.constructor($Val, $null)}
TaskNode([String]$Val, [TaskNode]$Parent) {$this.constructor($Val, $Parent)}
hidden constructor([String]$Val, [TaskNode]$Parent) {
$This.Val = $Val
if ($Parent) {$This.Parents.Add($Parent)}
$Script:NodeTracker.$Val = $This
}
#==METHODS================================================|
[TaskNode] To([String]$Val) {
$Node = $Script:NodeTracker.$Val
# If node doesn't exist, create and track
if (!$Node) {$Node = New-Object TaskNode $Val}
$This.then.Add($Node)
$Node.Parent.Add($This)
return $Node
}
[String] ToString() {return "$($this.val)-$(if($this.Visited){'✓'}else{'✘'})"}
static [String] ReverseModdedBFS([Collections.Queue]$Queue) {
$Output = ""
[Collections.Queue]$NextQueue = @()
do {
while ($Queue.Count) {
$Root = $Queue.Dequeue()
# Write-Host "Root: $Root | Queue: [$Queue] | Next-Queue [$NextQueue] | Non-Visited [$($Root.then | {!$_.Visited})]"
if ($Root.Visited) {continue}
if ($Root.Then.Count -gt 1 -and ($Root.then | {!$_.Visited})) {$NextQueue.Enqueue($Root);continue}
$Root.Visited = $true
$Output += ','+$Root.Val
$Root.Parent | % {
# Write-Host " Enqueuing $_"
$Queue.Enqueue($_)
}
}
If ($Queue.Count -eq 1 -and !$Queue.Peek().Parent.count) {break}
$Queue = $NextQueue
$NextQueue = @()
} while($Queue.Count)
$Out = $Output.Substring(1).split(',')
[Array]::Reverse($Out)
return $Out -join ','
}
#==STATICS=================================================|
static [TaskNode] Fetch([String]$Val) {
$Node = $Script:NodeTracker.$Val
# If node doesn't exist, create and track
if (!$Node) {return (New-Object TaskNode $Val)}
return $Node
}
static [TaskNode[]] GetAll() {
return @($Script:NodeTracker.Values)
}
static [TaskNode] GetStart() {
$Nodes = [TaskNode]::GetAll() | {$_.Parent.count -eq 0}
if ($Nodes.Count -gt 1) {throw 'There is more than one starting node!'}
if (!$Nodes.Count) {throw 'There is no starting node!'}
return @($Nodes)[0]
}
static [TaskNode[]] GetEnds() {
$Nodes = [TaskNode]::GetAll() | {$_.Then.count -eq 0}
if (!$Nodes.Count) {throw 'There is no ending node!'}
return @($Nodes)
}
}
function Parse-Edge($From, $To) {
# Use the safe static accessor so that it will fetch the singleton instance of the node, or create and return one!
[TaskNode]::Fetch($From).To($To)
}
function XML-Main([xml]$XML) {
@($XML.Flow.Task) | % {Parse-Edge $_.From $_.To}
[TaskNode]::ReverseModdedBFS([TaskNode]::GetEnds())
}
Test for proof!
I tested it like the following:
#Create or Find root node 'O'
$Root = [TaskNode]::Fetch('O')
# Set up Chains! Please draw to test
$root.To('A').To('B').To('C').To('H').To('Z').To('M')
$Root.To('D').To('E').To('C').To('H').To('I').To('M')
$Root.To('F').To('G').To('C').To('H').To('J').To('M')
[TaskNode]::Fetch('C').To('K').To('L').To('M')
# Run BFS!
[TaskNode]::ReverseModdedBFS([TaskNode]::GetEnds())
Output of Test
Root: M-✘ | Queue: [] | Next-Queue [] | Non-Visited []
Enqueuing Z-✘
Enqueuing I-✘
Enqueuing J-✘
Enqueuing L-✘
Root: Z-✘ | Queue: [I-✘ J-✘ L-✘] | Next-Queue [] | Non-Visited []
Enqueuing H-✘
Root: I-✘ | Queue: [J-✘ L-✘ H-✘] | Next-Queue [] | Non-Visited []
Enqueuing H-✘
Root: J-✘ | Queue: [L-✘ H-✘ H-✘] | Next-Queue [] | Non-Visited []
Enqueuing H-✘
Root: L-✘ | Queue: [H-✘ H-✘ H-✘] | Next-Queue [] | Non-Visited []
Enqueuing K-✘
Root: H-✘ | Queue: [H-✘ H-✘ K-✘] | Next-Queue [] | Non-Visited []
Enqueuing C-✘
Enqueuing C-✘
Enqueuing C-✘
Root: H-✓ | Queue: [H-✓ K-✘ C-✘ C-✘ C-✘] | Next-Queue [] | Non-Visited []
Root: H-✓ | Queue: [K-✘ C-✘ C-✘ C-✘] | Next-Queue [] | Non-Visited []
Root: K-✘ | Queue: [C-✘ C-✘ C-✘] | Next-Queue [] | Non-Visited []
Enqueuing C-✘
Root: C-✘ | Queue: [C-✘ C-✘ C-✘] | Next-Queue [] | Non-Visited []
Enqueuing B-✘
Enqueuing E-✘
Enqueuing G-✘
Root: C-✓ | Queue: [C-✓ C-✓ B-✘ E-✘ G-✘] | Next-Queue [] | Non-Visited []
Root: C-✓ | Queue: [C-✓ B-✘ E-✘ G-✘] | Next-Queue [] | Non-Visited []
Root: C-✓ | Queue: [B-✘ E-✘ G-✘] | Next-Queue [] | Non-Visited []
Root: B-✘ | Queue: [E-✘ G-✘] | Next-Queue [] | Non-Visited []
Enqueuing A-✘
Root: E-✘ | Queue: [G-✘ A-✘] | Next-Queue [] | Non-Visited []
Enqueuing D-✘
Root: G-✘ | Queue: [A-✘ D-✘] | Next-Queue [] | Non-Visited []
Enqueuing F-✘
Root: A-✘ | Queue: [D-✘ F-✘] | Next-Queue [] | Non-Visited []
Enqueuing O-✘
Root: D-✘ | Queue: [F-✘ O-✘] | Next-Queue [] | Non-Visited []
Enqueuing O-✘
Root: F-✘ | Queue: [O-✘ O-✘] | Next-Queue [] | Non-Visited []
Enqueuing O-✘
Root: O-✘ | Queue: [O-✘ O-✘] | Next-Queue [] | Non-Visited []
Root: O-✓ | Queue: [O-✓] | Next-Queue [] | Non-Visited []
Root: O-✓ | Queue: [] | Next-Queue [] | Non-Visited []
O,F,D,A,G,E,B,C,K,H,L,J,I,Z,M
Explanation, and Algo
We use a graph to plot all edges to each other using some nifty OOP tricks. Then we traverse the graph in reverse from all sink nodes (ie. nodes that have no children). We keep doing BFS till we hit a node that:
- Has more than 1 child
- AND, has more than 0 non-visited descendants
- If so, add that for the next round of BFS!
Repeat this till your current and future queues are empty, in which case, your output is now complete. Now:
- Split by comma
- Reverse array (since we did a reverse traversal)
- Print output!
