Option Explicit

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

' converted to the weighted case

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

Private t As Long, mnMaxClique As Long

Private nLevelWAcc() As Long

'

Public Function Start() As Long

Dim i As Long, t_minus_1 As Long, wt As Long

ReDim level_nodes(1 To Nodes, 1 To Nodes)

ReDim NodesNum(1 To Nodes)

ReDim nStart(1 To Nodes)

ReDim nLevelWAcc(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

If NodesNum(t) < nStart(t) Then

t = t - 1

Else

wt = 0

For i = nStart(t) To NodesNum(t)

wt = wt + w(level_nodes(t, i))

Next

''' Degree control

If (nLevelWAcc(t) + wt) > mnMaxClique Then

t_minus_1 = t

t = t + 1

nStart(t) = 0

NodesNum(t) = 0

nLevelWAcc(t) = nLevelWAcc(t_minus_1) + w(level_nodes(t_minus_1, nStart(t_minus_1)))

''' 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 nLevelWAcc(t + 1) > mnMaxClique Then

mnMaxClique = nLevelWAcc(t + 1)

End If

End If

Else

t = t - 1

End If

End If

Wend

Start = mnMaxClique

End Function