Option Explicit

' Carraghan, R., Pardalos, P. M.: An exact algorithm for the maximum clique problem. Op. Research Letters 9. (1990) 375-382

' (without compresing graphs etc)

Private level_nodes() As Long

Private nStart() As Long

Private NodesNum() As Long ' number of vertrices on a level

Private t As Long ' current level

Private mnMaxClique As Long ' current best clique

'

Public Function Start() As Long

Dim i As Long, t_minus_1 As Long

ReDim level_nodes(1 To Nodes, 1 To Nodes)

ReDim NodesNum(1 To Nodes)

ReDim nStart(1 To Nodes)

mnMaxClique = 0

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

For i = 1 To Nodes

level_nodes(1, i) = i

Next

NodesNum(1) = Nodes

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

t = 1

nStart(t) = 0

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

While t >= 1

nStart(t) = nStart(t) + 1

''' Degree control

If (t + NodesNum(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

End If

End If

Else

t = t - 1

End If

Wend

''' return size of the maximum clique

Start = mnMaxClique

End Function