VERSION 1.0 CLASS
BEGIN
  MultiUse = -1  'True
  Persistable = 0  'NotPersistable
  DataBindingBehavior = 0  'vbNone
  DataSourceBehavior  = 0  'vbNone
  MTSTransactionMode  = 0  'NotAnMTSObject
END
Attribute VB_Name = "clsCPWeight"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = True
Attribute VB_PredeclaredId = False
Attribute VB_Exposed = False
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