# 圖表結構和最大團

### 詹姆斯 McCaffrey

``````string graphFile = "..
\\..
\\DimacsGraph.clq";
MyGraph.ValidateGraphFile(graphFile, "DIMACS");

MyGraph graph = new MyGraph(graphFile, "DIMACS");

graph.ValidateGraph();
Console.WriteLine(graph.ToString());

Console.WriteLine("\nAre nodes 5 and 8 adjacent? "
+
Console.WriteLine("Number neighbors of node 4 = " +
graph.NumberNeighbors(4));
``````

## 位元矩陣

``````private class BitMatrix
{
private BitArray[] data;

public BitMatrix(int n)
{
this.data = new BitArray[n];
for (int i = 0; i < data.Length; ++i) {
this.data[i] = new BitArray(n);
}
this.Dim = n;
}
public bool GetValue(int row, int col)
{
return data[row][col];
}
public void SetValue(int row, int col, bool value)
{
data[row][col] = value;
}
public override string ToString()
{
string s = "";
for (int i = 0; i < data.Length; ++i) {
for (int j = 0; j < data[i].Length; ++j) {
if (data[i][j] == true)
s += "1 ";
else
s += "0 ";
}
s += Environment.NewLine;
}
return s;
}
}
``````

BitMatrix 類別代表方形矩陣，基本上 BitArray 陣列物件的陣列。 因為我想要將它內嵌圖表的類別定義中，而不是將它當做獨立類別，我會宣告具有私用範圍的 BitMatrix 類別。 BitMatrix 建構函式接受參數 n 是維度的 nxn矩陣配置資料行大小的 n 的 BitArray 陣列物件，然後再具現化每一個 BitArray 使用大小 n。 因為沒有任何位元型別。NET Framework 中，BitArray 中的值，因此 BitMatrix 類別中 — 集合都會公開成 bool 型別，如 [setvalue 巨集的方法。 請注意為了我簡短的程式碼，我已移除一般的錯誤檢查。

``````BitMatrix matrix = new BitMatrix(9);
matrix.SetValue(5, 8, true);
matrix.SetValue(8, 5, true);
bool connected = matrix.GetValue(2, 6);
``````

## 圖形類別

``````public class MyGraph
{
private BitMatrix data;
private int numberNodes;
private int numberEdges;
private int[] numberNeighbors;

public MyGraph(string graphFile, string fileFormat)
{
if (fileFormat.ToUpper() == "DIMACS")
else
throw new Exception("Format " + fileFormat + " not supported");
}

{
// Code here
}

public int NumberNodes
{
get { return this.
numberNodes; }
}

public int NumberEdges
{
get { return this.
numberEdges; }
}

public int NumberNeighbors(int node)
{
return this.
numberNeighbors[node];
}

public bool AreAdjacent(int nodeA, int nodeB)
{
if (this.data.GetValue(nodeA, nodeB) == true)
return true;
else
return false;
}

public override string ToString()
{
// Code here
}

public static void ValidateGraphFile(string graphFile, string fileFormat)
{
if (fileFormat.ToUpper() == "DIMACS")
ValidateDimacsGraphFile(graphFile);
else
throw new Exception("Format " + fileFormat + " not supported");
}

public static void ValidateDimacsGraphFile(string graphFile)
{
// Code here
}

public void ValidateGraph()
{
// Code here
}

// -------------------------------------------------------------------
private class BitMatrix
{
// Code here
}
// -------------------------------------------------------------------

} // Class MyGraph
``````

``````public class MyGraph
{
private BitMatrix data;
private int numberNodes;
private int numberEdges;
private int[] numberNeighbors;
...
``````

``````public MyGraph(string graphFile, string fileFormat)
{
if (fileFormat.ToUpper() == "DIMACS")
else
throw new Exception("Format " + fileFormat + " not supported");
}
``````

MyGraph 類別的核心是 LoadDimacsFormatGraph 方法，讀取來源資料檔案並儲存的圖形表示。 有許多的更多或較少標準的圖形檔案格式。 我在這裡使用一個稱為 DIMACS 格式。 這個縮寫字 DIMACS 代表獨立的數學和理論電腦科學領域。 DIMACS 是由 Rutgers 大學向共同作業關聯。

``````c DimacsGraph.clq
c number nodes, edges: 9, 13
p edge 9 13
e 1 2
e 1 4
e 1 5
e 2 4
e 2 5
e 3 5
e 3 6
e 4 5
e 5 6
e 5 8
e 6 9
e 7 8
e 8 9
``````

``````private void LoadDimacsFormatGraph(string graphFile)
{
FileStream ifs = new FileStream(graphFile, FileMode.Open);
string line = "";
string[] tokens = null;
...
``````

``````line = sr.ReadLine();
line = line.Trim();
while (line != null && line.StartsWith("p") == false) {
line = line.Trim();
}
...
``````

``````tokens = line.Split(' ');
int numNodes = int.Parse(tokens[2]);
int numEdges = int.Parse(tokens[3]);
sr.Close(); ifs.Close();
this.data = new BitMatrix(numNodes);
...
``````

``````ifs = new FileStream(graphFile, FileMode.Open);
while ((line = sr.ReadLine()) != null) {
line = line.Trim();
if (line.StartsWith("e") == true) {
tokens = line.Split(' ');
int nodeA = int.Parse(tokens[1]) - 1;
int nodeB = int.Parse(tokens[2]) - 1;
data.SetValue(nodeA, nodeB, true);
data.SetValue(nodeB, nodeA, true);
}
}
sr.Close(); ifs.Close();
...
``````

``````this.
numberNeighbors = new int[numNodes];
for (int row = 0; row < numNodes; ++row) {
int count = 0;
for (int col = 0; col < numNodes; ++col) {
if (data.GetValue(row, col) == true) ++count;
}
numberNeighbors[row] = count;
}
...
``````

``````...
this.
numberNodes = numNodes;
this.
numberEdges = numEdges;
return;
}
``````

MyGraph 類別的其餘部分很簡單。 我公開 (expose) 私用的 numberNodes 和 numberEdges 是類別欄位做為使用 C# 類別屬性機制的唯讀屬性值：

``````public int NumberNodes  {
get { return this.
numberNodes; }
}

public int NumberEdges  {
get { return this.
numberEdges; }
}
``````

``````public int NumberNeighbors(int node) {
return this.
numberNeighbors[node];
}
``````

``````public bool AreAdjacent(int nodeA, int nodeB)
{
if (this.data.GetValue(nodeA, nodeB) == true)
return true;
else
return false;
}
``````

``````public override string ToString()
{
string s = "";
for (int i = 0; i < this.data.Dim; ++i) {
s += i + ": ";
for (int j = 0; j < this.data.Dim; ++j) {
if (this.data.GetValue(i, j) == true)
s += j + " ";
}
s += Environment.NewLine;
}
return s;
}
``````

## 驗證圖表

``````if (line.StartsWith("c") == false &&
line.StartsWith("p") == false &&
line.StartsWith("e") == false)
throw new Exception("Unknown line type: " + line);
``````

``````try {
if (line.StartsWith("p")) {
tokens = line.Split(' ');
int numNodes = int.Parse(tokens[2]);
int numEdges = int.Parse(tokens[3]);
}
catch {
throw new Exception("Error parsing line = " + line);
}
``````

``````for (int i = 0; i < this.data.Dim; ++i) {
for (int j = 0; j < this.data.Dim; ++j) {
if (this.data.GetValue(i, j) != this.data.GetValue(j, i))
throw new Exception("Not symmetric at " + i + " and " + j);
}
}
``````

## 密切注意如需詳細資訊

Dr。James McCaffrey 適用於 Volt 資訊科學 Inc.，他用來管理技術訓練軟體工程師使用 Microsoft 里德蒙，Wash.，在校園。他已投入許多 Microsoft 產品，包括 Internet Explorer 和 MSN 搜尋。 Dr。 McCaffrey 是作者 」。NET 測試自動化食譜 」 (Apress，2006年，) 且能夠存取在 mjammc@microsoft.com