VERSION 1.0 CLASS
BEGIN
  MultiUse = -1  'True
END
Attribute VB_Name = "API_StrongComponents"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = False
Attribute VB_PredeclaredId = False
Attribute VB_Exposed = False
' ===== Graph strongly linked components ====
' Shared module version: 20220408
' Tested in: TestCommons
' Depends on: CDS_Graph
' Required reference:
Option Explicit

Private graph_ As CDS_Graph
Private components_ As Collection
Private current_ As Scripting.Dictionary

Private visited_ As Scripting.Dictionary
Private reversedOrder_ As Scripting.Dictionary

Public Function GetComponents(iGraph As CDS_Graph) As Collection
  Set graph_ = iGraph
  Set components_ = New Collection
 
  Call CalculateOrder
  Call ScanComponents
  
  Set GetComponents = components_
End Function

' =============
Private Function CalculateOrder()
  Set visited_ = New Scripting.Dictionary
  Set reversedOrder_ = New Scripting.Dictionary
  
  Dim vNode As Variant
  For Each vNode In graph_.Nodes
    If Not visited_.Exists(vNode) Then
      Call VisitInversed(vNode)
    End If
  Next vNode
End Function

Private Function ScanComponents()
  Set visited_ = New Scripting.Dictionary
  Dim nItem&
  Dim vItems As Variant: vItems = reversedOrder_.Keys()
  For nItem = UBound(vItems, 1) To LBound(vItems, 1) Step -1
    Dim nodeID As Variant: nodeID = vItems(nItem)
    If visited_.Exists(nodeID) Then _
      GoTo NEXT_NODE
      
    Set current_ = New Scripting.Dictionary
    Call VisitNode(nodeID)
    If current_.Count = 1 Then
      If Not graph_.HasEdge(nodeID, nodeID) Then _
        GoTo NEXT_NODE
    End If
    Call components_.Add(current_)
NEXT_NODE:
  Next nItem
End Function

Private Function VisitInversed(nodeID As Variant)
  Call visited_.Add(nodeID, 0)
  Call VisitChildrenInversed(nodeID)
  Call reversedOrder_.Add(nodeID, 0)
End Function

Private Function VisitChildrenInversed(nodeID As Variant)
  If graph_.nodes_(nodeID).inputs_.Count = 0 Then _
    Exit Function
  
  Dim parentID As Variant
  For Each parentID In graph_.nodes_(nodeID).inputs_
    If Not visited_.Exists(parentID) Then _
      Call VisitInversed(parentID)
  Next parentID
End Function

Private Function VisitNode(nodeID As Variant)
  Call visited_.Add(nodeID, 0)
  Call current_.Add(nodeID, 0)
  Call VisitChildren(nodeID)
End Function

Private Function VisitChildren(nodeID As Variant)
  If graph_.nodes_(nodeID).outputs_.Count = 0 Then _
    Exit Function
    
  Dim childID As Variant
  For Each childID In graph_.nodes_(nodeID).outputs_
    If Not visited_.Exists(childID) Then _
      Call VisitNode(childID)
  Next childID
End Function