102 lines
2.6 KiB
OpenEdge ABL
102 lines
2.6 KiB
OpenEdge ABL
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
|
|
|
|
|