Dieser Artikel wurde maschinell übersetzt.

Test Run

Diagrammstrukturen Und maximale Clique

James McCaffrey

Herunterladen des Codebeispiels

James McCaffreyIm Artikel Dieses Monats Präsentiere Ich Das Design Eine Sprachimplementierung C# Und Testverfahren Für Eine Graph-Datenstruktur, die Zur Lösung des Probleme Maximale Clique Verwendet Werden Kann. Der Graph-Code Kann Auch Für Viele Andere Probleme Verwendet Werden, Wie Ich Erläutern Werde.

Außerdem war Genau ist Das Problem der Clique Und Warum es Möglicherweise Für Sie relevanten maximalen? Eine Clique ist Eine Teilmenge Eines Diagramms, in Dem Jeder Knoten Auf Alle Anderen Knoten verknüpft. Schauen Sie Sich Die Grafische Repräsentation in Abbildung 1. Knoten 2, 4 Und 5 Bilden Eine Clique von Drei Größe. Das Maximale Clique Problem ist Die Clique Mit der Größten Größe in Einem Diagramm Zu Finden. Die Maximale Clique Für Das Diagramm in der Abbildung 1 ist Die Knotengruppe {0, 1, 3, 4} the Four Größe Hat.

A Graph for the Maximum Clique Problem
Abbildung 1 Ein Diagramm Für Das Maximale Clique Problem

Das Maximale Clique Problem ist in Einer Vielzahl von Anwendungen, Einschließlich Analyse der Sozialen Netzwerk-Kommunikation, Computer-Netzwerk-Analyse, anlagenbausoftware Und Vielen Anderen Aufgetreten. Für Graphen von Sogar Mittlerer Größe Stellt Sich Heraus, Dass Das Maximale Clique Problem Eines der Schwierigsten Und Interessante Probleme in Computer Science ist. Die Techniken Zur Lösung des Probleme Maximale Clique — Die Tabu-Suche, Gierige Suche, Suche Plateau, Echtzeit-Parameter Anpassung Und Dynamische Lösungsverlauf Enthalten – in Vielen Anderen Problemszenarios Verwendet Werden Können. Kurz Gesagt, Kann Code, der Das Maximale Clique Problem 08.10.2001 Direkt Für Sie Nützlich Sein, Und Die Erweiterten Techniken, die Beschäftigung in der Algorithmus kann Für Andere difficult Programmierung Probleme nützlich Sein.

Eine Umfassende Lösung Für Das Problem der maximalen Clique ist Zu Lang, Zu Präsentieren Und Erläutern Sie in Einem Artikel, so Dass Ich die Lösung Über Mehrere Artikel Vorstellen Werde. Der Erste Schritt Zur Lösung des Probleme Maximale Clique ist Zum Entwerfen, Implementieren Und Testen Eine Datenstruktur, die Effizient Das Diagramm in der Analyse Im Arbeitsspeicher Gespeichert Werden Kann. Die Konsolenanwendung in Abbildung 2 Zeigt Ihnen, Worauf Ich Hinaus wird in Dieser Spalte.

Graph Loading and Validation
Abbildung 2 Diagramm beladen Und Punkt

Mit a few WriteLine Anweisungen Entfernt, den Code, der Erzeugt Die Ausführung Angezeigt, Abbildung 2 ist:

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

Die Daten Für Die Abbildung 1 Graph Befindet Sich in Einer Externen Textdatei Namens DimacsClique.clq, die Ein Standardformat Namens DIMACS Verwendet. Das Dateiformat der DIMACS Werde Ich in Kürze Eingehen. Mein Demoprogramm Durch Überprüfen der Quelldatei wird Dann Instanziiert Eine Graph Datenstruktur Mithilfe der Datendatei. Nach Dem eine der Graph Ich Überprüfen die Interne Darstellung Und in Einer Menschen-Freundliche Bild Angezeigt Wird. Wie Sie Sehen Werden, ist Eine Effiziente Interne Darstellung Eines Diagramms Entscheidend Für Die Maximale Clique Problem. Die Demo-Programm Beendet Wird Durch Aufrufen Einer Methode, Die Bestimmt, Ob Zwei Knoten Nebeneinander Zu Sehen Sind Knoten 5 Und 8 in Diesem Herbst, Und Durch Aufrufen Einer Methode, Die der Anzahl der Nachbarn ein Knoten Zurückgibt provides Für Den Knoten 4 in Diesem Fall.

Ich Werde Sie Den Generierten Code Die Abbildung 2 Ausgabe Zeilenweise. Der Vollständigen under Für Die Demo-Programm Steht Unter code.msdn.microsoft.com/mag201110TestRun. Ist der Code in C# Geschrieben should, Aber Sie in der Lage, Mir Zu Folgen, Wenn Sie in Jedem modernen Hochsprache Intermediate-Level-Programmierkenntnisse Verfügen. Der Hier Dargestellte Code Graph Bildet Die Grundlage Für Die Lösung des Probleme Maximale Clique Im Nächsten Artikel Und Sollte Eine Useful Ergänzung Zu Ihrem Entwickler, Tester Und Software-Projekt-Management-Toolkits.

Eine Bit-Matrix

Es Gibt Mehrere Möglichkeiten, um Eine Ungewichtete Darstellen (Graph Kanten Sind Nicht Irgendeine Prioritäten Zugewiesen), Ohne wird (Kanten Haben Keine Richtung von Einem Knoten Zu Einem Anderen) Graph Im Arbeitsspeicher. Für Die Maximale Clique Problem Enthält, Ein Diagramm Mit Einer Bit-Matrix repräsentiert Eine Hervorragende Kombination aus Speicherplatz Und Leistung-Effizienz. Abbildung 3 Zeigt Eine Bit-Matrix, die Im Diagramm Beispiel Entspricht. Obwohl Wir Ein Diagramm Ohne wird Geht, ist es Üblich, Rufen Sie die Vertikale Grundlinie aus Knoten Und Die Horizontale Grundlinie Zu-Knoten. Der Wert 1 Bedeutet, es ist Eine Kante Zwischen Den Entsprechenden Knoten. der Wert 0 Zeigt Keinen Rand Zwischen Den Knoten. Beachten Sie, Dass die Matrix Symmetrisch ist Und Wir Davon Ausgehen, Dass Knoten Neben Selbst Sind Nicht.

A Bit Matrix Graph Representation
Abbildung 3 Bit Graph Matrixdarstellung

Der Hauptvorteil Einer Bit-Matrix Über alternative Designs ist, Dass Dadurch Schnelle Adjacency-Lookups, Die Die Common Language Runtime Viele Graph-Algorithmen, EINSCHLIESSLICH des maximalen Clique Probleme oft Dominieren. Wenn Groben Implementiert, ist der Primäre Nachteil Einer Matrix Bit Speichernutzung. Z. B. Wenn die 9 x 9 Matrix in Abbildung 3 Wurde als Ein Zweidimensionales Array von 4-Byte-Ganzzahlen Oder Boolesche Werte,, die Guarantee the Matrix 9 * 9 * 4 = 324 Bytes Erfordern Würde. Aber da Jeder Wert in Einer Bit-Matrix Nur 0 Oder 1 Sein Kann, Können Wir Die Bits Einer Ganzzahl Zum Speichern von Bis Zu 32 Werte pro Integer Verwenden. In Diesem Beispiel Wenn Wir Uns Vorstellen, Dass Das Niederwertige Bit Auf der Rechten Seite ist Abrechnungscode Die Erste Zeile als Eine Individual 32-Bit-Ganzzahl-00000000-00000000-00000000-10110000 be Werden sterben Hat Den Dezimalwert 128 + 32 + 16 = 176. Wenn Jede Zeile der Matrix als Eine Einzelne Ganzzahl Gespeichert ist, wo die Bits der Ganzzahl Mit Vorzeichen Zum Darstellen der Anwesenheit Oder Abwesenheit Einer Kante Zwischen Knoten Verwendet Werden, Müsste die 9 x 9 Matrix so Nur 36 Bytes.

In Älteren Programmiersprachen, Müssten Sie Implementieren Eine Bit-Matrix von Grund Auf Mit Low-Level-Bit-Operatoren, Wie Z. B. UMSCHALT links, Bitweise OR Und so Weiter. Aber Die Microsoft.NET Framework System.Collections-Namespace ist Ein BitArray ist ein Programm-BitMatrix Typ Einfach Implementieren. Eine BitMatrix-Klasse Kann Definiert Werden, Wie in Gezeigt Abbildung 4.

Abbildung 4 Eine BitMatrix-Klasse

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

Die BitMatrix-Klasse Stellt Eine Quadratische Matrix Dar Und ist Im Grunde Ein Objektarray BitArray-Array. Ich Erkläre Mit Privaten Bereich Die BitMatrix-Klasse, da Ich als Standalone-Klasse Verwenden, Anstatt es Innerhalb Einer Klassendefinition Diagramm Einbetten Möchten. Der BitMatrix-Konstruktor Akzeptiert Einen Parameter n , Das ist Die Dimension der Ein nxnMatrix, Weist der Größe Eine Spalte n von BitArray Array-Objekte Und Instanziiert Dann Jedes BitArray Mit Größe n. Da Gibt es Keinen Typ Bit in der.NET Framework, die Werte in Einem BitArray – Und deshalb in der Klasse BitMatrix – are Ausgesetzt als Typ Bool, See Die SetValue-Methode. Beachten Sie, Dass um Mein Code Kurz Zu Halten, Ich Normale Fehlerüberprüfung Entfernt Haben.

Verwenden Die BitMatrix Könnte so Aussehen:

 

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

Die Erste Zeile Erstellt Ein 9 x 9-BitMatrix-Objekt, Legen Sie Zunächst Auf Alle False (Oder Nullen) Ein Ungewichtete, Ungerichteten Graphen Mit Neun Knoten darstellt. Der Zweiten Zeile Wird die Zeile 5, 8-Spalte Auf True/1, um Anzugeben, Dass es Eine Kante Zwischen 5 Und 8 Knoten. In der Dritte Zeile Wird Die Zeile 8, Spalte 5 True/1, so Dass die Edge Graph-Darstellung Konsistent ist. Die Vierte Zeile Holt Den Wert in Zeile 2, Spalte 6, Einen Wert, der Angibt, Ob Zwischen Knoten 2 Und 6, die False/0 Wäre Eine Kante Vorliegt. Beachten Sie, Dass ermitteln, Ob Zwei Knoten Nebeneinander Zu Sehen Sind Oder Nicht Gerade Ein Array quick Lookup.

Ein Graph-Klasse

Mit Einer BitMatrix-Klasse in der Hand ist es Leicht Zu 
define Eine Effiziente Graph-Klasse Für Die Maximale Clique Problem Und Viele Andere Graph-Bezogene Probleme Geeignet. Die Struktur Einer Graph-Klasse Dargestellt Wird, in Abbildung 5. Die Graph-Klasse Hat Antworthistorie Für System, System.IO Und System.Collections-Namespaces. Für Das Beispielprogramm für das sowohl Ich die Graph-Klasse Direkt in der Konsole app, Aber Sie Können Den Code in Einer Klassenbibliothek Zu Platzieren.

Abbildung 5 Ein Graph-Klassendefinition

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

Die Graph-Klassendefinition Beginnt Mit:

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

Ich Nennen Sie Die Klasse MyGraph. Es ist ein wenig verlockend um zu versuchen, eine universell einsetzbares Graph-Klasse definieren, aber es gibt so viele Variationen von Graphen, dass es eine bessere Idee, anderes Diagramm Klassen für unterschiedliche Arten von Problemen zu definieren. Die Graph-Klasse, die ich hier definieren richtet sich an die maximale Clique zu lösen, und verwandte Probleme, so dass ich die Klasse etwas auffällt konnte wie MaxCliqueGraph. Die Klasse verfügt über vier Datenfelder. Der erste ist ein BitMatrix-Objekt, wie im vorherigen Abschnitt beschrieben. Die Felder NumberNodes und NumberEdges halten Sie die Anzahl der Knoten (im Beispiel neun) und die Anzahl der ohne Ausrichtung Kanten (im Beispiel 13) im Diagramm.

Wenn viele Graph-Probleme zu lösen, es ist notwendig zu wissen, wie viele Knoten Nachbarn hat – d. h. wie viele Knoten mit einem bestimmten Knoten verbunden sind. Für das Beispiel-Diagramm in der Abbildung 1, 5 Knoten drei Nachbarn hat. Den Grad des Knotens ist die Abkürzung für der Anzahl der Nachbarn ein Knoten hat. Für einen gegebenen Knoten kann dieser Wert on the Fly bei Bedarf durch zählen der Anzahl von True/1-Werte in den Knoten Datenzeile berechnet werden. Eine viel schnellere Methode ist Nachbarn zu zählen, und speichern die Anzahl der für jeden Knoten einmal im Graph-Konstruktor und dann bei Bedarf eine Array-Suche. Also, für das Diagramm Beispiel nach der Instanziierung Array NumberNeighbors neun Zellen mit Werten [3,3,2,3,6,3,1,3,2] würden, drei Nachbarn hat, der angibt, Knoten 0 Knoten 1 drei Nachbarn hat, Knoten 2 besitzt die beiden Nachbarn und so weiter.

Der Graph-Klassenkonstruktor ist:

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

Der Konstruktor akzeptiert eine Textdatei, die Diagrammdaten enthält und eine Zeichenfolge, die das Format der Datendatei angibt. Hier überträgt ich sofort die Kontrolle an eine Hilfsmethode LoadDimacsFormatGraph. Dieser Entwurf ermöglicht die Graph-Klasse, um problemlos erweitert werden, um mehrere Datendateiformate gerecht zu werden. Wenn Sie ein von Enumerationstypen Fan kann der File Format-Parameter mit einer Enumeration implementiert werden.

Das Herz der MyGraph-Klasse ist die LoadDimacsFormatGraph-Methode, die eine Quelldatei für die Daten liest und speichert die grafische Repräsentation. Es gibt viele mehr oder weniger standard Graph-Dateiformate. Die hier verwendeten Format DIMACS heißt. Das Akronym steht DIMACS für diskrete Mathematik und theoretische Informatik. DIMACS ist eine kollaborative Association unter der Leitung von Rutgers University.

Das Programm wird in Abbildung 2 verwendet eine Datei namens DimacsGraph.clq, aufgeführt in bild6. Beginnend mit c Zeilen sind Kommentarzeilen. Es gibt eine einzelne Zeile beginnt mit p, die den Zeichenfolge "Rand" gefolgt von der Anzahl der Knoten, gefolgt von der Anzahl der Kanten hat. Mit e Zeilen definieren die Kanten. Beachten Sie, dass die DIMACS-Dateiformat ist leer-Space mit Trennzeichen und 1-basierte und jede Kante nur einmal gespeichert wird.

Abbildung 6 DIMACS-Format-Datendatei

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

Die Load-Methode beginnt:

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

Beim Lesen von Textdateien, ich bevorzuge die FileStream- und StreamReader-Klassen verwenden, aber Sie eines der vielen verwenden möchten.NET-alternativen. Weiter:

 

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

Führen eine Grundieren Lese-, und klicken Sie dann auf die p-Zeile in der Datendatei voraus. Da Textdateien leicht vermeidbare Whitespace-Zeichen mit der Zeit erwerben können, verwende ich die Trim-Methode, um Probleme zu vermeiden. Fortfahren:

 

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

Ich verwende die String.Split-Methode zum Analysieren der p-Reihe. Zu diesem Zeitpunkt Token [0] enthält die Zeichenfolge literal "p", Token [1] enthält "Rand", Token [2] enthält Token und "9" [3] "13" enthält. Ich verwende die int.Parse-Methode (ich könnte Convert. ToInt32 verwendet haben), um die Anzahl der Knoten und Kanten in Int-Werte zu konvertieren, die ich in der lokalen Variablen NumNodes und NumEdges speichern. Ich konnte diese Werte in die Klassenfelder der diese gespeichert haben. NumberNodes und das. NumberEdges zu diesem Zeitpunkt. Nun, da ich die Anzahl der Knoten und die Anzahl der Kanten festgelegt haben, kann ich schließen Sie die Datendatei und instanziieren das Datenfeld BitMatrix.

Jetzt bin ich bereit, Edge-Daten aus der Datendatei zu lesen:

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();
...

Öffnen Sie die Datei, und Lesen am Anfang beginnen. Technisch – wegen des Vorhandenseins der Linie vor alle Zeilen e p – es gibt keine Notwendigkeit, zwei Lesevorgänge in eine Datei im Format DIMACS verwenden. Für andere Dateiformate, die explizit die Anzahl der Kanten nicht speichern, möchten Sie jedoch einen double Scan wie die hier verwendete ausführen. Stößt der Code eine e-Line, wie z. B. "e 3 6", ich die Analysezeile e, konvertieren die beiden Knoten Typ Int und subtrahieren 1 ein, um die Darstellung von 1 auf 0-basierte zu ändern. Ich verwende die SetValue-Methode symmetrischen Einträge in der BitMatrix erstellt. Beachten Sie, dass da die BitMatrix symmetrisch ist, ich nur die oberen gespeichert haben könnte oder unteren dreieckige Teil, um Speicher zu reduzieren.

Als Nächstes kümmern ich das NumberNeighbors-Array:

 

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

Für jeden Knoten fu ich über die entsprechende Zeile und Count die Anzahl der Werte True/1, die die Anzahl der Kanten und somit die Anzahl der Nachbarn den Knoten gibt hat. Die LoadDimacsFormatGraph-Methode endet mit:

 

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

Nachdem Sie die Anzahl der Knoten und die Anzahl der Kanten von lokalen Variablen auf Klassenvariablen Feld übertragen, verwende ich eine explizite Rückkehr zur besseren Lesbarkeit um die Methode zu beenden.

Der Rest der MyGraph-Klasse ist einfach. Ich Aussetzen der privaten NumberNodes und NumberEdges Felder als schreibgeschützte Werte mithilfe der C#-Klasse Eigenschaftenmechanismus Klasse:

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

Ich Bevorzuge die Explizite Eigenschaftensyntax Verwenden, Aber Können Sie Automatisch Implementierte Eigenschaftensyntax Verwenden, Wenn Sie Verwenden.NET 3.0 Oder Höher. Ich Offen Legen Die Anzahl der Nachbarn, die Einen Knoten Verfügt Über Eine Methode:

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

Beim Arbeiten Mit 3D-Diagrammen, ist es Schwierig Zu Wissen, Wann Fehlerüberprüfung Standard Time and to Auslassen. Ich Überprüfen Nicht Hier, Ob der Node-Parameter Im Bereich von 0 ist... Stirbt. NumberNodes-1, Verlassen mich Öffnen, um Ein Arrayindex Außerhalb des Bereichs-Ausnahme. Ich Fehler-Kontrollkästchen in der Regel Während der Entwicklung Hinzufügen Und anschliessend Nach der Entwicklung, die Ich Entfernen, kann Dieser Kontrollen, die Ich Fühle mich Sicher Zur Leistungssteigerung Ausgelassen Werden. Aufgrund der Meine Datenstruktur ist Design Mit Einer BitMatrix-Klasse, Schreiben Eine Methode, um Festzustellen, Ob Zwei Knoten Nebeneinander Zu Sehen Sind Einfach:

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

Denken Sie Daran, Dass Die BitMatrix Symmetrisch, so Dass Ich GetValue (KnotenA, KnotenB) Oder der GetValue (KnotenB, NodeA) Überprüfen Können. Wie Bereits Inhalt Dominiert Adjacency Knoten Überprüft Die Common Language Runtime Viele Graph-Algorithmen. Bei Verwendung einer Bit-Matrix is my Knoten Adjacency quickly Die Prüfung ist Eine Array-Suche plus Ein Wenig-Bitmanipulation Overhead Durch Die BitArray-Klasse Behandelt.

Ich Code Eine easily ToString-Methode Für Die MyGraph-Klasse:

 

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

Im Szenario Clique Maximale Leistung ist Kein großes Ausgeben, so Dass Für Die ToString-Methode Ich easily Zeichenfolgenverkettung Anstelle der Effizienter StringBuilder-Klasse Verwenden. Ich Benutze Hier i Index in Die Zeilen BitMatrix Und j der Index in Die Spalten. Ich Beenden Die Zeichenfolge Mit Einem Environment.NewLine tend als "\n" Auf Die MyGraph-Klasse Besser Übertragbar Zu Machen.

Überprüfen Das Diagramm

If you Zurück Zu Verweisen Abbildung 2, Sie Werden Bemerken, Dass Ich Zwei Wichtige Arten von Graph Punkt Durchführen: die Datendatei Graph Bevor Das Graph-Objekt Instanziiert Wird Validieren Und Die Interne Grafische Repräsentation Nach der Instanziierung.

Eine Vollständige Erläuterung der Graph-Punkt Und Prüfung Würde Einen Ganzen Artikel Erfordern, so Dass Ich Nur Einen Überblick Geben Werde. Sie Können auch Abrufen Und Anzeigen Den Vollständigen Validierungscode aus code.msdn.microsoft.com/mag201110TestRun.

Ich Punkt Daten-Datei Mithilfe Einer Statischen Methode ValidateGraphFile, Wie in Gezeigt Abbildung 5. Wie Bei der MyGraph-Konstruktor Ruft ValidateGraphFile Sofort Eine Hilfsmethode ValidateDimacsGraphFile Die Eigentliche Arbeit Zu Tun. Der Datei Validierungscode werden die Datei, um Festzustellen, Ob Jede Zeile in Form von Gültigen DIMACS ist:

 

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

Die Methode Überprüft Das Format der Kommentarlosen Zeilen Auch Durch Den Versuch, Zu Analysieren. Z. B. Für die Einzelnen p-Linie:

 

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

Die Methode Verwendet verwendet Logik e Linien Zu Testen. Dieses Muster Enthält Im Allgemeinen Beim Überprüfen von Datendateien Graph: You Die Gültigen Positionen Und Datenleitungen Analysieren.

Nach der Instanziierung Validieren Ich Die Interne Graph Darstellung Mithilfe Einer ValidateGraph-Methode. Es Stellt Sich Heraus, Dass Eine Vollständige to der Graph Datenstruktur Überraschend Komplexe, auch in der Praxis es Üblich ist, Nur Die Fehler Überprüfen, die am Wahrscheinlichsten Auftreten. Ein Häufiger Fehler in Graph-Datendateien ist Eine Fehlende Daten, die Einen Asymmetrischen BitMatrix Datenspeicher Erstellt. You can Mit Code Wie Folgt Überprüft Werden:

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

Andere Fehler Zu Prüfen, this Information Das Vorhandensein von True/1 Auf der Hauptdiagonale in Bit-Matrix, machte aus either Alle/0, False Oder True/1, Und Die Summe der Werte Im Feld Array NumberNeighbors Nicht Gleich der Gesamtzahl der True/1-Werte in der Matrix Bit Bit Matrix.

Bleiben Sie Dran Für Weitere Details

In Diesem Artikel Vorgestellt Graph-Struktur Ein, Die Verwendet Werden Kann, maximalen Für Viele Probleme Im Zusammenhang Mit Dem Diagramm einschliesslich des Clique Probleme Zu Lösen. Das Grundlegende Merkmal der Graph Datenstruktur ist die Zeilenstruktur Einer Matrix-Programm Definierten Bit Effizienz Hinsichtlich der Speicherauslastung Und Die Schnelle Knoten Adjacency Lookups wird. Das Bitfeld Matrix der Graph Datenstruktur Wird, die Guarantee Mit DemokratischeNET BitArray-Klasse Alle Low-Level Bit Manipulation Operationen Kümmert. In der Nächsten Testlauf Spalte Ich Das Maximale Clique Problem Genauer Beschreiben Und Zeigen Sie Eine greedy-Algorithmus-Lösung die Hier Beschriebene Graph-Struktur Verwendet.

Dr. James McCaffrey Arbeitet Für Volt Information Sciences Inc., wo er Technische Schulungen Für Softwareentwickler Auf Dem Microsoft in Redmond, Washington, Campus. Er ist in Mehreren Microsoft-Produkten, Einschließlich Internet Explorer Und MSN Search Gearbeitet. Dr. McCaffrey ist Autor von ".NET Test Automation Recipes "(Apress, 2006), Und Erreichen Sie Unter mjammc@microsoft.com.

Dank der Folgenden Technischen Experten Für die Überprüfung Dieses Artikels:Paul Koch, Dan Liebling, Ann Loomis Thompson andShane Williams