本文章是由機器翻譯。

測試回合

圖表結構和最大團

詹姆斯 McCaffrey

下載程式碼範例

在本月的專欄中,我會提出的設計,C# 語言實作和測試技術可用來解決最大的 clique 問題的圖形資料結構。圖形程式碼可以也用於許多其他的問題,我將說明。

因此,到底是什麼是最大的 clique 問題,以及為什麼它可能與您相關?Clique 是圖形的子集合,其中每個節點連接到每個其他的節點。請看一下中的圖形表示法圖 1。節點 2、 4 和 5 形成三個大小的 clique。最大的 clique 問題是在圖表中尋找最大的大小 clique。在圖形的最大的 clique 圖 1 是節點集 {0、1、 3、 4},其中有四個的大小。


圖 1] 圖形的最大值 Clique 問題

最大的 clique 問題發生在應用程式,包括共享的網路通訊分析、 電腦網路分析、 電腦願景和許多其他的大範圍。即使中等大小的圖形,結果的最大的 clique 問題是在電腦科學領域中最具挑戰性,有趣的問題之一。用來解決最大的 clique 問題的技術,包括 tabu 搜尋、 窮盡搜尋、 高原搜尋、 即時的參數適應以及動態解決方案歷程記錄,可用於許多其他問題狀況。簡單來說,最大的 clique 問題已解決的程式碼可以直接用來,與演算法中使用的進階的技巧很有幫助解決其他困難的程式設計問題。

最大的 clique 問題的完整解決方案是太長,無法顯示,並說明一個發行項,因此我將透過幾篇文章提供解決方案。如需解決最大的 clique 問題的第一個步驟是設計、 實作和測試可以有效率地儲存在記憶體中的圖形,在 [分析] 下的資料結構。在主控台應用程式圖 2 我向在本篇文章將告訴您。


圖 2 圖形載入和驗證

有一些 WriteLine 陳述式移除,產生執行所示的程式碼圖 2 是:

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? "
+
  graph.AreAdjacent(5,8));
Console.WriteLine("Number neighbors of node 4 = " +
  graph.NumberNeighbors(4));

資料圖 1 圖表儲存在外部的文字檔,名為 DimacsClique.clq,會使用稱為 DIMACS 的標準格式。我將稍後說明的 DIMACS 檔案格式。我的範例程式開始驗證原始程式檔,然後使用資料檔的圖形資料結構會具現化。圖形具現化之後,我會驗證的內部表示,並顯示人類友善映像中。如您所見,有效的內部表示是圖形的最大的 clique 問題很重要的。藉由呼叫方法,判斷兩個節點是相鄰的示範程式完成,5 到 8,在此情況下,並藉由呼叫方法,傳回的其他例項數目的節點的節點有,節點 4 在此情況下。

我將引導您產生的程式碼完成圖 2 輸出琵式。範例程式的完整原始程式碼位於 code.msdn.microsoft.com/mag201110TestRun。在 C# 中,撰寫程式碼,但您應該能夠了解我,如果您有任何現代的高階語言的中間層級的程式設計技能。此處所提供的圖形程式碼解決最大的 clique 問題在未來的發行項中的基礎並應該是程式開發人員、 軟體測試人員和軟體專案管理] 工具套件外加很有用。

位元矩陣

有許多常見的方式來表示 unweighted (圖形邊緣尚未指派的一些排序優先順序),undirected (邊緣不需要從一個節點到另一個方向) 在記憶體中的圖形。最大的 clique 問題,表示圖形使用位元矩陣提供空間與效能的效率的絕佳的組合。圖 3 顯示對應到範例圖表的位元矩陣。雖然我們正在處理 undirected 的圖形,它會呼叫到節點從節點的垂直索引] 及 [水平索引。值為 1 表示有是邊緣之間的對應的節點。 0 表示,介於節點之間沒有邊緣。請注意,矩陣是對等的我們假設節點不是鄰接到本身。


圖 3 遭到元矩陣圖形表示**

位元矩陣替代的設計上的主要優點是它可快速相鄰查詢作業、 經常支配,包括最大的 clique 問題的許多圖形演算法的執行階段。如果實作 crudely,位元矩陣的主要缺點是記憶體使用量。例如,如果 9 x 9 矩陣中的圖 3 用來實作以 4 個位元組整數或布林值的二維陣列,矩陣會需要 9 * 9 * 4 = 324 位元組。但是因為 0 或 1,可能只會在位元矩陣中的每個值,我們可以使用的位元的整數來儲存每個整數的最多 32 個值。在這個範例中,如果我們想像的低序位位元是在右邊的第一列可以儲存成單一 32 位元整數 00000000-00000000-00000000-10110000,其中有 128 + 32 + 16 = 176 的十進位值。因此如果矩陣的每個資料列儲存為單一整數的整數的位元用於表示邊緣節點間存在,9 x 9 矩陣需要只 36 個位元組。

在較舊的程式語言,您必須實作重新使用低階位元運算子,例如左移位的位元的位元矩陣-或等等。但是 Microsoft。NET Framework System.Collections 命名空間有 BitArray 型別會實作簡單的程式定義 BitMatrix 類型。BitMatrix 類別定義中所示圖 4

圖 4 BitMatrix 類別

private class BitMatrix
{
  private BitArray[] data;
  public readonly int Dim;
 
  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 可能如下:

 

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

第一行會建立一開始設定所有 9 x 9 BitMatrix 物件 false (或零) 表示的 unweighted、 undirected 圖,有九個節點。 第二個程式碼行設定資料列 5,則為 true/1,表示沒有邊緣節點 5 與 8 節點之間的資料行 8。 第三行,將第 8 欄 5 列設定為 true (1),以便一致的圖形邊緣的表示。 第四行擷取資料列 2,資料行值,指出在節點 2 到 6,為 false (0) 之間沒有邊緣 6 的值。 請注意判斷是連在一起的兩個節點快速陣列查閱。

圖形類別

在手中的 BitMatrix 類別,很容易 
define 適用於最大的 clique 問題及許多其他圖形相關的問題是有效的圖形類別。 圖形類別的結構以圖 5。 圖形類別會對系統、 System.IO 及 System.Collections 的命名空間中的相依性。 範例程式,我放置圖形類別直接在主控台應用程式,但您可能想要將程式碼放在類別庫]。

圖 48-cpu 圖形類別定義

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")
      LoadDimacsFormatGraph(graphFile);
    else
      throw new Exception("Format " + fileFormat + " not supported");
  }
   
  private void LoadDimacsFormatGraph(string graphFile)
  {
    // 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;
...

我命名為 MyGraph 的類別。 它有點 tempting,嘗試定義的所有目的的圖形類別,但有很多不同的版本的圖形它是個不錯定義不同的圖形類別,針對不同種類的問題。 我在這裡所定義的圖形類別旨在解決最大的 clique 和相關的問題,因此我無法已命名的類別項目喜歡 MaxCliqueGraph。 類別有四個資料欄位。 第一個是 BitMatrix 物件,如前一節所述。 [NumberNodes] 和 [numberEdges] 欄位保留節點 (在範例中的九個) 的數目和 undirected 的邊緣 (在範例中的 [13]),在圖形中的數目。

當解決許多圖形,它的需要知道多少 neighbors 節點有 — 也就是幾個節點連接到指定的節點。 在 [範例] 圖形的圖 1,5 的節點有三個周圍鄰居。 節點有其他例項的數目也稱為節點的程度。 針對指定的節點,這個值可以被計算出來時所需的計算中節點的資料列則為 true (1) 值的數目。 更快的方法是計算和儲存的數字 neighbors 一次在圖表的建構函式然後再將每個節點時所需的陣列查閱。 因此如具現化後的 [範例] 圖表中,陣列 numberNeighbors 會有九個儲存格的值 [3,3,2,3,6,3,1,3,2],指出節點 0 有三個周圍鄰居 1 的節點有三個周圍鄰居、 節點 2,以此類推有兩個其他例項。

圖形類別建構函式是:

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

建構函式接受文字檔案保留圖表的資料和字串,表示特定的資料檔案格式。 在此,我立即控制權轉移到 LoadDimacsFormatGraph 的 helper 方法。 此設計可讓您輕易擴充,以容納多個資料檔案格式的圖形類別。 如果您不喜歡利用列舉型別時,可以使用列舉型別實作的檔案格式參數。

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

所示的範例程式圖 2 使用一個名為 DimacsGraph.clq,它列示在檔案 Figure6。 以 c 開頭的行是註解行。 沒有 p 具有字串 「 邊緣,"後面的節點,後面接著邊緣數目的數字開始的單行。 以 e 為開頭的程式碼行會定義邊緣。 請注意,DIMACS 檔案格式是空白空間分隔,並以 1 起始,和每一個邊緣會儲存一次。

圖 6 DIMACS 格式資料檔案

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

Load 方法開始:

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

當讀取文字檔,我比較喜歡使用 FileStream] 和 [StreamReader] 類別中,但您可能想要使用其中一個多。NET 的替代方案。 下一步:

 

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

我執行 priming 讀取,然後移至 [資料檔案中的 [p] 行。 因為文字檔可以經過一段時間,輕鬆地取得假性的空白字元,我會使用修剪方法,要避免發生問題。 在繼續進行:

 

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

我可以使用 String.Split 方法來分析 p 列。 此時,語彙基元 [0] 保留的字串常值"p"、 語彙基元 [1] 擁有 「 邊緣 」,"9"和語彙基元,會保留語彙基元 [2] [3] 保留"13 」。 我使用 int。剖析的方法 (我無法使用 Convert.ToInt32),將節點和邊緣的數字轉換成 int 值,我將儲存在本機變數 numNodes 和 numEdges。 我無法儲存這些值成類別欄位這。 numberNodes,這。 在這個階段的 numberEdges。 既然我已決定的節點數目和邊緣數目,我會關閉資料檔案,並具現化的 BitMatrix 資料欄位。

現在我準備好要從資料檔讀取邊緣資料:

ifs = new FileStream(graphFile, FileMode.Open);
sr = new StreamReader(ifs);
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();
...

我重新開啟檔案,並從頭開始讀取。 技術上來說,因為 p 行任何電子行之前的目前狀態的 — 不需要使用兩次讀取的 DIMACS 格式檔案。 不過,對於不明確地儲存的數字,邊緣的其他檔案格式,您可以執行像此處所用的雙精度浮點數掃描。 當程式碼遇到"e 3 6"e 一行時,我會分析電子列,轉換為 int 型別和減去 1,若要從 1 開始的的表示法變更為 0 為基礎的兩個節點。 我可以使用 setvalue 巨集的方法來建立對稱的項目中的 BitMatrix。 請注意由於 BitMatrix 是對稱的我無法儲存剛才的上方或下方三角形的部分,以減少記憶體。

接下來,我負責的 numberNeighbors 陣列:

 

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;
}
...

針對每個節點中,我會逐步帶在其對應的資料列和 true (1) 值的數字,以提供節點邊緣數目,因此其他例項的數目的計數。 LoadDimacsFormatGraph 方法結束:

 

...
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; }
}

我喜歡使用明確的屬性語法,但如果您正在使用,您可以使用自動實作屬性語法。NET 3.0 或更大。 我公開 (expose) 透過方法節點具有的其他例項的數目:

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

使用圖形時,很難知道何時執行標準錯誤檢查,略過檢查的時機。 在此,我並沒有檢查節點參數在範圍 0.. 這。 numberNodes-1,讓我開啟陣列索引超出範圍例外狀況。 我通常會在開發期間,加入錯誤檢查],然後開發我移除後我覺得這些檢查可以安全地省略以增進效能。 因為我的資料結構的設計與 BitMatrix 類別,撰寫某個方法,以判斷兩個節點是否相鄰很簡單:

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

您應該還記得 BitMatrix 是對稱的因此我可以檢查 GetValue nodeA (nodeB) 或 GetValue nodeB (nodeA)。 如先前所述,檢查節點相鄰勝於許多圖形演算法的執行階段。 使用位元矩陣,檢查節點相鄰關係時快速因為檢查是只要陣列查閱加上由 BitArray 類別負荷處理一些位元操作。

我的程式碼的 MyGraph 類別的簡單 ToString 方法:

 

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;
}

在 [最大 clique 案例而定,效能不大發出,因此 ToString 方法,我使用簡單的字串串連,而不是更有效率的 StringBuilder 類別。 在此,我使用 i 到 BitMatrix 的資料列和 j 至資料行的索引的索引。 我會終止使用 Environment.NewLine 而非"\n"使 MyGraph 類別的可移植性的字串。

驗證圖表

如果您參考回圖 2,您會注意到我會執行兩個重要的類型的圖形驗證: graph 物件具現化之前,驗證圖表資料檔案,並驗證之後執行個體化的內部的圖形表示。

圖表的驗證和測試的完整討論需要一整篇文章,因此我只是將提供概觀。 您可以取得並檢視完整的驗證程式碼,從 code.msdn.microsoft.com/mag201110TestRun。

我執行資料檔案驗證所示,使用靜態方法 ValidateGraphFile 圖 5。 如同 MyGraph 建構函式,ValidateGraphFile 立即呼叫 helper 方法執行的實際工時的 ValidateDimacsGraphFile。 檔案驗證程式碼會逐一查看每行是否為有效的 DIMACS 格式檔案:

 

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

這個方法也會嘗試剖析檢查非註解行的格式。 例如,對於單一 p] 行中:

 

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);
}

該方法會使用相同的邏輯測試電子行。 此模式會驗證圖表資料檔時通常保留: 檢查有效的行,並嘗試剖析資料行。

一旦執行個體化,我會驗證使用 ValidateGraph 方法的內部的圖形表示。 結果圖形的資料結構的完整檢查是相當複雜,因此實際上是常見的只是最有可能發生的錯誤檢查。 圖表資料檔案的常見錯誤是遺失的資料行建立非對稱的 BitMatrix 資料存放區。 它可以使用如下的程式碼檢查:

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);
  }
}

若要檢查有其他錯誤包括 true/1 的位元矩陣主對角線上,包含所有 false/0] 或 [真/1] 和 [在 numberNeighbors 陣列欄位不等於位元矩陣中的則為 true (1) 值的總數值的總和的位元矩陣的存在。

密切注意如需詳細資訊

本文提供可解決許多與圖形相關問題包括最大的 clique 問題的圖形資料結構類型。圖表的資料結構的重要功能是程式定義的位元矩陣是有效的記憶體使用量,並允許快速的相鄰節點的對應使用。使用實作圖表的資料結構的位元矩陣欄位。NET BitArray 類別,就會自己料理所有低階位元處理作業。在下一個測試回合欄中,我將說明更多詳細資料的最大的 clique 問題,並顯示您在這裡使用圖形結構描述的窮盡演算法方案。

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

感謝到下列的技術專家來檢閱這份文件:Paul Koch, Dan Liebling, Ann Loomis ThompsonShane Williams