# 窮盡演算法與最大團

### 詹姆斯 McCaffrey

[圖 2 窮盡的最大值 Clique 示範執行

## 整個程式結構

[圖 3 整體程式結構

``````using System;
using System.Collections.Generic;
using System.IO;
using System.Collections;

namespace GreedyMaxClique
{
class GreedyMaxCliqueProgram
{
static Random random = null;

static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin greedy maximum clique demo\n");

string graphFile = "..
\\..
\\DimacsGraph.clq";
MyGraph graph = new MyGraph(graphFile, "DIMACS");

int maxTime = 20;
int targetCliqueSize = graph.NumberNodes;

List<int> maxClique = FindMaxClique(graph, maxTime,
targetCliqueSize);
Console.WriteLine("\nMaximum time reached");
Console.WriteLine("\nSize of best clique found = " +
maxClique.Count);

Console.WriteLine("\nBest clique found:");
Console.WriteLine(ListAsString(maxClique));

Console.WriteLine("\nEnd greedy maximum clique demo\n");
}
catch (Exception ex)
{
Console.WriteLine("Fatal: " + ex.Message);
}
} // Main

static List<int> FindMaxClique(MyGraph graph, int maxTime,
int targetCliqueSize)
{
// ...
}

static List<int> MakePossibleAdd(MyGraph graph, List<int> clique)
{
// ...
}

static bool FormsALargerClique(MyGraph graph, List<int> clique,
int node)
{
// ...
}

{
// ...
}

static int GetNodeToDrop(MyGraph graph, List<int> clique,
List<int> oneMissing)
{
// ...
}

static List<int> MakeOneMissing(MyGraph graph, List<int> clique)
{
// ...
}

static string ListAsString(List<int> list)
{
// ...
}
} // class Program

public class MyGraph
{
// ...
}
} // ns
``````

## FindMaxClique 方法

``````initialize clique with a single node
get list of candidate nodes to add
loop until stop condition met
if there are nodes that can be added
else
find best node to drop and drop from clique

if lack of progress
restart algorithm

update list of candidate nodes
end loop
return largest clique found
``````

FindMaxClique 方法定義開頭：

``````static List<int> FindMaxClique(MyGraph graph, int maxTime,
int targetCliqueSize)
{
List<int> clique = new List<int>();
random = new Random(1);
int time = 0;
int timeBestClique = 0;
int timeRestart = 0;
int nodeToDrop = -1;
...
``````

``````int randomNode = random.Next(0, graph.NumberNodes);
...
``````

``````List<int> bestClique = new List<int>();
int bestSize = bestClique.Count;
timeBestClique = time;
...
``````

[BestClique] 清單用來追蹤此演算法的搜尋期間找到的最大 clique 的複本。 我可以使用方便的 AddRange 方法來將項目複製到 bestClique 中目前的 clique。 BestSize 變數是用來以方便使用。 TimeBestClique 用來決定是否的演算法會重新啟動電腦：

``````List<int> possibleAdd = MakePossibleAdd(graph, clique);
List<int> oneMissing = MakeOneMissing(graph, clique);
...
``````

MakePossibleAdd 的 helper 方法會檢查目前的 clique，並建構可以逐一加入至 clique 的單位來放大 clique 的所有節點的清單。 這份清單是最佳的節點將新增至 clique 的對象的來源。 MakeOneMissing 的 helper 方法有一點技巧。 方法會建構一份所有已連線至目前的 clique 中的某個節點的節點。 如您所見，此 oneMissing 清單用來決定最佳的節點從 clique 中卸除。 現在，我開始主要處理迴圈：

``````while (time < maxTime && bestSize < targetCliqueSize)
{
++time;
bool cliqueChanged = false;
...
``````

``````if (possibleAdd.Count > 0) {
clique.Sort();
cliqueChanged = true;
if (clique.Count > bestSize) {
bestSize = clique.Count;
bestClique.Clear();
}
...
``````

``````if (cliqueChanged == false) {
if (clique.Count > 0) {
nodeToDrop = GetNodeToDrop(graph, clique, oneMissing);
Console.WriteLine("Dropping node " + nodeToDrop);
clique.Remove(nodeToDrop);
clique.Sort();
cliqueChanged = true;
}
} // drop
...
``````

``````int restart = 2 * bestSize;
if (time - timeBestCliqueFound > restart &&
time - timeLastRestart > restart) {
Console.WriteLine("\nRestarting\n");
timeLastRestart = time;
int seedNode = random.Next(0, graph.NumberNodes);
clique.Clear();
} // restart
...
``````

``````...
oneMissing = MakeOneMissing(graph, clique);
} // loop
return bestClique;
}
``````

FindMaxClique 方法會重新計算根據新的 clique 的 possibleAdd 和 oneMissing 清單。 當主要處理迴圈結束時，這個方法會傳回找到的最佳 clique。

## 加入最佳的節點

``````static List<int> MakePossibleAdd(MyGraph graph, List<int> clique)
{
List<int> result = new List<int>();
for (int i = 0; i < graph.NumberNodes; ++i) {
if (FormsALargerClique(graph, clique, i) == true)
}
return result;
}
``````

``````static bool FormsALargerClique(MyGraph graph, List<int> clique, int node)
{
for (int i = 0; i < clique.Count; ++i) {
return false;
}
return true;
}
``````

FormsALargerClique 方法會比較依據目前的 clique 中的所有節點的一個節點。 如果候選節點不相鄰，即使只有其中的 clique 中的節點，候選節點無法加入至目前的 clique。 請注意當一個節點會比對本身，則 AreAdjacent 會傳回 false，因為在目前的 clique 節點將不會加入至 possibleAdd 節點的清單。

``````static int GetNodeToAdd(MyGraph graph, List<int> possibleAdd)
{
...
``````

``````int maxDegree = 0;
for (int i = 0; i < possibleAdd.Count; ++i) {
int degreeOfCurrentNode = 0;
for (int j = 0; j < possibleAdd.Count; ++j) {
++degreeOfCurrentNode;
}
if (degreeOfCurrentNode > maxDegree)
maxDegree = degreeOfCurrentNode;
}
...
``````

``````List<int> candidates = new List<int>();
for (int i = 0; i < possibleAdd.Count; ++i) {
int degreeOfCurrentNode = 0;
for (int j = 0; j < possibleAdd.Count; ++j) {
++degreeOfCurrentNode;
}
if (degreeOfCurrentNode == maxDegree)
}
...
``````

``````...
return candidates[random.Next(0, candidates.Count)];
}
``````

## 正在卸除最佳的節點

MakeOneMissing 方法所示圖 4。 透過圖表] 中的每個節點，掃描的方法。 其概念是，若要計算 clique 中的幾個節點連接到目前正在檢查的節點。 如果總和計算的連接節點正好一個小於目前的 clique，大小，那麼正在檢查節點就是 oneMissing 的節點。 此方法 short-circuits，如果目前的節點，正在檢查有少於必要數目的其他例項。 此方法必須篩選出已在 clique 因為他們連線到他們自己的 clique (也就是本身) 中的某個節點的節點。 二進位搜尋因為目前的 clique 排序 (每個新增或卸除) 之後，可以用來代替較慢的線性搜尋 (請參閱圖 4)。

[圖 4 將清單中的 oneMissing 節點

``````static List<int> MakeOneMissing(MyGraph graph, List<int> clique)
{
int count;
List<int> result = new List<int>();
for (int i = 0; i < graph.NumberNodes; ++i) {
count = 0;
if (graph.NumberNeighbors(i) < clique.Count - 1) continue;
if (clique.BinarySearch(i) >= 0) continue;
for (int j = 0; j < clique.Count; ++j) {
++count;
}
if (count == clique.Count - 1)
}
return result;
}
``````

GetNodeToDrop 方法會開始：

``````static int GetNodeToDrop(MyGraph graph, List<int> clique,
List<int> oneMissing)
{
if (clique.Count == 1)
return clique[0];
...
``````

``````int maxCount = 0;
for (int i = 0; i < clique.Count; ++i) {
int currCliqueNode = clique[i];
for (int j = 0; j < oneMissing.Count; ++j) {
int currOneMissingNode = oneMissing[j];
}
}
...
``````

``````List<int> candidates = new List<int>();
for (int i = 0; i < clique.Count; ++i) {
int currCliqueNode = clique[i];
for (int j = 0; j < oneMissing.Count; ++j) {
int currOneMissingNode = oneMissing[j];
}
}
...
``````

``````...
return candidates[random.Next(0, candidates.Count)];
} // GetNodeToDrop
``````

## 結論

Dr。 詹姆斯 McCaffrey *適用於 Volt 資訊科學 Inc.，他用來管理使用 Microsoft 里德蒙，Wash.，在校園的軟體工程師技術的訓練。 他已投入許多 Microsoft 產品，包括網際網路檔案總管] 及 [MSN 搜尋。 Dr。 McCaffrey 是作者 」。NET 測試自動化的食譜 」 (Apress 2006)，並且可以連線到 jammc@microsoft.com。*