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