VERSION 1.0 CLASS
BEGIN
  MultiUse = -1  'True
  Persistable = 0  'NotPersistable
  DataBindingBehavior = 0  'vbNone
  DataSourceBehavior  = 0  'vbNone
  MTSTransactionMode  = 0  'NotAnMTSObject
END
Attribute VB_Name = "clsCP"
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
' (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