330 lines
9.0 KiB
VB.net
330 lines
9.0 KiB
VB.net
' Adapted from:
|
|
' http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html
|
|
' added/changed:
|
|
' - conversion to VB.Net (.Net 2 framework)
|
|
' - added Rosetta Code dependency format parsing
|
|
' - check & removal of self-dependencies before sorting
|
|
Module Program
|
|
Sub Main()
|
|
Dim Fields As New List(Of Field)()
|
|
' You can also add Dependson using code like:
|
|
' .DependsOn = New String() {"ieee", "dw01", "dware"} _
|
|
|
|
fields.Add(New Field() With { _
|
|
.Name = "des_system_lib", _
|
|
.DependsOn = Split("std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "dw01", _
|
|
.DependsOn = Split("ieee dw01 dware gtech", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "dw02", _
|
|
.DependsOn = Split("ieee dw02 dware", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "dw03", _
|
|
.DependsOn = Split("std synopsys dware dw03 dw02 dw01 ieee gtech", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "dw04", _
|
|
.DependsOn = Split("dw04 ieee dw01 dware gtech", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "dw05", _
|
|
.DependsOn = Split("dw05 ieee dware", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "dw06", _
|
|
.DependsOn = Split("dw06 ieee dware", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "dw07", _
|
|
.DependsOn = Split("ieee dware", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "dware", _
|
|
.DependsOn = Split("ieee dware", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "gtech", _
|
|
.DependsOn = Split("ieee gtech", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "ramlib", _
|
|
.DependsOn = Split("std ieee", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "std_cell_lib", _
|
|
.DependsOn = Split("ieee std_cell_lib", " ") _
|
|
})
|
|
fields.Add(New Field() With { _
|
|
.Name = "synopsys" _
|
|
})
|
|
Console.WriteLine("Input:")
|
|
For Each ThisField As field In fields
|
|
Console.WriteLine(ThisField.Name)
|
|
If ThisField.DependsOn IsNot Nothing Then
|
|
For Each item As String In ThisField.DependsOn
|
|
Console.WriteLine(" -{0}", item)
|
|
Next
|
|
End If
|
|
Next
|
|
|
|
Console.WriteLine(vbLf & "...Sorting..." & vbLf)
|
|
|
|
Dim sortOrder As Integer() = getTopologicalSortOrder(fields)
|
|
|
|
For i As Integer = 0 To sortOrder.Length - 1
|
|
Dim field = fields(sortOrder(i))
|
|
Console.WriteLine(field.Name)
|
|
' Write up dependencies, too:
|
|
'If field.DependsOn IsNot Nothing Then
|
|
' For Each item As String In field.DependsOn
|
|
' Console.WriteLine(" -{0}", item)
|
|
' Next
|
|
'End If
|
|
Next
|
|
Console.Write("Press any key to continue . . . ")
|
|
Console.ReadKey(True)
|
|
End Sub
|
|
|
|
Private Sub CheckDependencies (ByRef Fields As List(Of Field))
|
|
' Make sure all objects we depend on are part of the field list
|
|
' themselves, as there may be dependencies that are not specified as fields themselves.
|
|
' Remove dependencies on fields themselves.Y
|
|
Dim AField As Field, ADependency As String
|
|
|
|
For i As Integer = Fields.Count - 1 To 0 Step -1
|
|
AField=fields(i)
|
|
If AField.DependsOn IsNot Nothing then
|
|
For j As Integer = 0 To Ubound(AField.DependsOn)
|
|
ADependency = Afield.DependsOn(j)
|
|
' We ignore fields that depends on themselves:
|
|
If AField.Name <> ADependency then
|
|
If ListContainsVertex(fields, ADependency) = False Then
|
|
' Add the dependent object to the field list, as it
|
|
' needs to be there, without any dependencies
|
|
Fields.Add(New Field() With { _
|
|
.Name = ADependency _
|
|
})
|
|
End If
|
|
End If
|
|
Next j
|
|
End If
|
|
Next i
|
|
End Sub
|
|
|
|
Private Sub RemoveSelfDependencies (ByRef Fields As List(Of Field))
|
|
' Make sure our fields don't depend on themselves.
|
|
' If they do, remove the dependency.
|
|
Dim InitialUbound as Integer
|
|
For Each AField As Field In Fields
|
|
If AField.DependsOn IsNot Nothing Then
|
|
InitialUbound = Ubound(AField.DependsOn)
|
|
For i As Integer = InitialUbound to 0 Step - 1
|
|
If Afield.DependsOn(i) = Afield.Name Then
|
|
' This field depends on itself, so remove
|
|
For j as Integer = i To UBound(AField.DependsOn)-1
|
|
Afield.DependsOn(j)=Afield.DependsOn(j+1)
|
|
Next
|
|
ReDim Preserve Afield.DependsOn(UBound(Afield.DependsOn)-1)
|
|
End If
|
|
Next
|
|
End If
|
|
Next
|
|
End Sub
|
|
|
|
Private Function ListContainsVertex(Fields As List(Of Field), VertexName As String) As Boolean
|
|
' Check to see if the list of Fields already contains a vertext called VertexName
|
|
Dim Found As Boolean = False
|
|
For i As Integer = 0 To fields.Count - 1
|
|
If Fields(i).Name = VertexName Then
|
|
Found = True
|
|
Exit For
|
|
End If
|
|
Next
|
|
Return Found
|
|
End Function
|
|
|
|
Private Function getTopologicalSortOrder(ByRef Fields As List(Of Field)) As Integer()
|
|
' Gets sort order. Will also add required dependencies to
|
|
' Fields.
|
|
|
|
' Make sure we don't have dependencies on ourselves.
|
|
' We'll just get rid of them.
|
|
RemoveSelfDependencies(Fields)
|
|
|
|
'First check depencies, add them to Fields if required:
|
|
CheckDependencies(Fields)
|
|
' Now we have the correct Fields list, so we can proceed:
|
|
Dim g As New TopologicalSorter(fields.Count)
|
|
Dim _indexes As New Dictionary(Of String, Integer)(fields.count)
|
|
|
|
'add vertex names to our lookup dictionaey
|
|
For i As Integer = 0 To fields.Count - 1
|
|
_indexes(fields(i).Name.ToLower()) = g.AddVertex(i)
|
|
Next
|
|
|
|
'add edges
|
|
For i As Integer = 0 To fields.Count - 1
|
|
If fields(i).DependsOn IsNot Nothing Then
|
|
For j As Integer = 0 To fields(i).DependsOn.Length - 1
|
|
g.AddEdge(i, _indexes(fields(i).DependsOn(j).ToLower()))
|
|
Next
|
|
End If
|
|
Next
|
|
|
|
Dim result As Integer() = g.Sort()
|
|
Return result
|
|
End Function
|
|
|
|
Private Class Field
|
|
Public Property Name() As String
|
|
Get
|
|
Return m_Name
|
|
End Get
|
|
Set
|
|
m_Name = Value
|
|
End Set
|
|
End Property
|
|
Private m_Name As String
|
|
Public Property DependsOn() As String()
|
|
Get
|
|
Return m_DependsOn
|
|
End Get
|
|
Set
|
|
m_DependsOn = Value
|
|
End Set
|
|
End Property
|
|
Private m_DependsOn As String()
|
|
End Class
|
|
End Module
|
|
Class TopologicalSorter
|
|
''source adapted from:
|
|
''http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html
|
|
''which was adapted from:
|
|
''http://www.java2s.com/Code/Java/Collections-Data-Structure/Topologicalsorting.htm
|
|
#Region "- Private Members -"
|
|
|
|
Private ReadOnly _vertices As Integer()
|
|
' list of vertices
|
|
Private ReadOnly _matrix As Integer(,)
|
|
' adjacency matrix
|
|
Private _numVerts As Integer
|
|
' current number of vertices
|
|
Private ReadOnly _sortedArray As Integer()
|
|
' Sorted vertex labels
|
|
|
|
#End Region
|
|
|
|
#Region "- CTors -"
|
|
|
|
Public Sub New(size As Integer)
|
|
_vertices = New Integer(size - 1) {}
|
|
_matrix = New Integer(size - 1, size - 1) {}
|
|
_numVerts = 0
|
|
For i As Integer = 0 To size - 1
|
|
For j As Integer = 0 To size - 1
|
|
_matrix(i, j) = 0
|
|
Next
|
|
Next
|
|
' sorted vert labels
|
|
_sortedArray = New Integer(size - 1) {}
|
|
End Sub
|
|
|
|
#End Region
|
|
|
|
#Region "- Public Methods -"
|
|
|
|
Public Function AddVertex(vertex As Integer) As Integer
|
|
_vertices(System.Threading.Interlocked.Increment(_numVerts)-1) = vertex
|
|
Return _numVerts - 1
|
|
End Function
|
|
|
|
Public Sub AddEdge(start As Integer, [end] As Integer)
|
|
_matrix(start, [end]) = 1
|
|
End Sub
|
|
|
|
Public Function Sort() As Integer()
|
|
' Topological sort
|
|
While _numVerts > 0
|
|
' while vertices remain,
|
|
' get a vertex with no successors, or -1
|
|
Dim currentVertex As Integer = noSuccessors()
|
|
If currentVertex = -1 Then
|
|
' must be a cycle
|
|
Throw New Exception("Graph has cycles")
|
|
End If
|
|
|
|
' insert vertex label in sorted array (start at end)
|
|
_sortedArray(_numVerts - 1) = _vertices(currentVertex)
|
|
|
|
' delete vertex
|
|
deleteVertex(currentVertex)
|
|
End While
|
|
|
|
' vertices all gone; return sortedArray
|
|
Return _sortedArray
|
|
End Function
|
|
|
|
#End Region
|
|
|
|
#Region "- Private Helper Methods -"
|
|
|
|
' returns vert with no successors (or -1 if no such verts)
|
|
Private Function noSuccessors() As Integer
|
|
For row As Integer = 0 To _numVerts - 1
|
|
Dim isEdge As Boolean = False
|
|
' edge from row to column in adjMat
|
|
For col As Integer = 0 To _numVerts - 1
|
|
If _matrix(row, col) > 0 Then
|
|
' if edge to another,
|
|
isEdge = True
|
|
' this vertex has a successor try another
|
|
Exit For
|
|
End If
|
|
Next
|
|
If Not isEdge Then
|
|
' if no edges, has no successors
|
|
Return row
|
|
End If
|
|
Next
|
|
Return -1
|
|
' no
|
|
End Function
|
|
|
|
Private Sub deleteVertex(delVert As Integer)
|
|
' if not last vertex, delete from vertexList
|
|
If delVert <> _numVerts - 1 Then
|
|
For j As Integer = delVert To _numVerts - 2
|
|
_vertices(j) = _vertices(j + 1)
|
|
Next
|
|
|
|
For row As Integer = delVert To _numVerts - 2
|
|
moveRowUp(row, _numVerts)
|
|
Next
|
|
|
|
For col As Integer = delVert To _numVerts - 2
|
|
moveColLeft(col, _numVerts - 1)
|
|
Next
|
|
End If
|
|
_numVerts -= 1
|
|
' one less vertex
|
|
End Sub
|
|
|
|
Private Sub moveRowUp(row As Integer, length As Integer)
|
|
For col As Integer = 0 To length - 1
|
|
_matrix(row, col) = _matrix(row + 1, col)
|
|
Next
|
|
End Sub
|
|
|
|
Private Sub moveColLeft(col As Integer, length As Integer)
|
|
For row As Integer = 0 To length - 1
|
|
_matrix(row, col) = _matrix(row, col + 1)
|
|
Next
|
|
End Sub
|
|
|
|
#End Region
|
|
End Class
|