Option Explicit

' Ostergard, P.R.J.: A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, Vol. 120. (2002) 197-207

' (without compressing graphs etc)

Private level_nodes() As Long, nStart() As Long, NodesNum() As Long

Private t As Long, mnMaxClique As Long

Private nMaxCliques() As Long

'

Public Function Start() As Long

Dim i As Long, t_minus_1 As Long, nn As Long

ReDim level_nodes(1 To Nodes, 1 To Nodes)

ReDim NodesNum(1 To Nodes)

ReDim nStart(1 To Nodes)

ReDim nMaxCliques(1 To Nodes)

' ReDim degree_arr(1 To nodes) As Long

mnMaxClique = 0

'''''' each level has its own set of nodes

For i = 1 To Nodes

level_nodes(1, i) = i

Next

NodesNum(1) = Nodes

'''''''''''''''''''''''''''''''''''

DefineClasses

For nn = Nodes To 1 Step -1

t = 2

NodesNum(t) = 0

For i = nn + 1 To Nodes

If arr(level_nodes(1, nn), level_nodes(1, i)) Then

NodesNum(t) = NodesNum(t) + 1

level_nodes(t, NodesNum(t)) = level_nodes(1, i)

End If

Next

If NodesNum(t) = 0 Then

t = t - 1

If t > mnMaxClique Then mnMaxClique = t

Else

nStart(t) = 0

End If

While t >= 2

nStart(t) = nStart(t) + 1

''' Degree control

If (t + NodesNum(t) - nStart(t)) > mnMaxClique And _

(t + nMaxCliques(level_nodes(t, nStart(t)))) > mnMaxClique Then

t_minus_1 = t

t = t + 1

nStart(t) = 0

NodesNum(t) = 0

''' define nodes for the next level

For i = nStart(t_minus_1) + 1 To NodesNum(t_minus_1)

If arr(level_nodes(t_minus_1, nStart(t_minus_1)), level_nodes(t_minus_1, i)) Then

NodesNum(t) = NodesNum(t) + 1

level_nodes(t, NodesNum(t)) = level_nodes(t_minus_1, i)

End If

Next

If NodesNum(t) = 0 Then

t = t - 1

If t > mnMaxClique Then

mnMaxClique = t

t = 1

End If

End If

Else

t = t - 1

End If

Wend

nMaxCliques(level_nodes(1, nn)) = mnMaxClique

Next

Start = mnMaxClique

End Function

Private Sub DefineClasses()

Dim class_init() As Boolean '' show if node exist

Dim i As Long, k As Long

Dim mnRemainNodes As Long, bFirstNode As Boolean, nkNode As Long, nNodeNum As Long

ReDim class_init(1 To Nodes)

'''''

mnRemainNodes = Nodes

While True

''' build up new class

bFirstNode = True

''' position of first node

i = mnRemainNodes

While i > 0

''' swap nodes

nNodeNum = level_nodes(1, i)

If i <> mnRemainNodes Then

''' swap rows

level_nodes(1, i) = level_nodes(1, mnRemainNodes)

level_nodes(1, mnRemainNodes) = nNodeNum

End If

'''

mnRemainNodes = mnRemainNodes - 1

If mnRemainNodes = 0 Then Exit Sub

If bFirstNode Then

For k = 1 To mnRemainNodes

nkNode = level_nodes(1, k)

class_init(nkNode) = arr(nNodeNum, nkNode)

Next

bFirstNode = False

Else

For k = 1 To mnRemainNodes

nkNode = level_nodes(1, k)

class_init(nkNode) = arr(nNodeNum, nkNode) Or class_init(nkNode)

Next

End If

For i = mnRemainNodes To 1 Step -1

If Not class_init(level_nodes(1, i)) Then Exit For

Next

Wend

Wend

End Sub