Il presente articolo è stato tradotto automaticamente.

Esecuzione di test

Strutture grafiche e clique massima

James McCaffrey

Scaricare il codice di esempio

Nell'articolo di mese questo presenterò la progettazione, un'implementazione del linguaggio C# e tecniche per una struttura di dati del grafico che può essere utilizzato per risolvere il problema clique massimo di test. Il codice grafico utilizzabile anche per molti altri problemi, come spiegherò.

In questo modo, cos'è il problema clique massima e perché siano pertinente per l'utente? Un clique è un sottoinsieme di un grafico in cui ogni nodo è connesso a tutti i nodi. Si osservi la rappresentazione in forma di grafico in nella figura 1. I nodi 2, 4 e 5 formano un clique delle tre dimensioni. Il problema clique massima consiste nel trovare clique con la dimensione massima in un grafico. La clique massima per il grafico in nella figura 1 è l'insieme di nodi {0, 1, 3, 4}, che dispone di quattro dimensioni.

Figura 1 associazione grafico per il problema Clique massimo

Si è verificato il problema clique massimo in una vasta gamma di applicazioni, incluse l'analisi di comunicazione di rete sociale, analisi di rete del computer, degli obiettivi di computer e molti altri. Per i grafici di dimensioni anche moderato, si scopre che il problema clique massimo è uno dei problemi più complessi e interessanti in informatica. Le tecniche utilizzate per risolvere il problema clique massimo — tra cui ricerca tabu, ricerca generico, ricerca piatta, adattamento del parametro in tempo reale e cronologia soluzione dinamica, ovvero può essere utilizzato in molti altri scenari di problema. In altre parole, il codice che è stato risolto il problema clique massima può essere utile direttamente all'utente e le tecniche avanzate impiegate nell'algoritmo possono essere utile per la risoluzione di altri problemi di programmazione complessa.

Una soluzione completa per il problema clique massima è troppo lunga per presentare e spiegare in un articolo, in modo che descriverò la soluzione su diversi articoli. Il primo passo per risolvere il problema clique massima consiste nel progettare, implementare e testare una struttura di dati che è possibile memorizzare in modo efficiente il grafico di analisi in memoria. L'applicazione console in nella figura 2 viene illustrato dove potrò in questa colonna.

La convalida e il caricamento del grafico nella figura 2

Con alcuni WriteLine istruzioni rimosso, il codice che ha elaborato la sequenza illustrata nella nella figura 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));

I dati per la nella figura 1 grafico viene memorizzato in un file esterno denominato DimacsClique.clq, che utilizza un formato standard denominato DIMACS. Spiegherò al più presto il formato del file DIMACS. Il programma demo inizia con la convalida del file di origine, quindi crea un'istanza di una struttura di dati del grafico utilizzando il file di dati. Dopo che il grafico è stata creata un'istanza, ho la rappresentazione interna di convalidare e visualizzarlo in un'immagine di uomo-friendly. Come si vedrà una rappresentazione interna efficiente di un grafico è particolarmente importante per il problema clique massima. Al termine dell'applicazione demo chiamando un metodo che determina se due nodi sono adiacenti, nodi 5 e 8 in questo caso e chiamando un metodo che restituisce il numero di elementi adiacenti di un nodo dispone, per il nodo 4 nella fattispecie.

Prenderanno in considerazione è il codice che ha generato la nella figura 2 riga per riga di output. Il codice sorgente completo per il programma demo è disponibile all'indirizzo code.msdn.microsoft.com/mag201110TestRun. Il codice è scritto in C#, ma deve essere in grado di seguire me se si dispone di competenze di programmazione di livello intermedio in qualsiasi linguaggio di alto livello moderno. Il codice grafico che mi accingo getta le basi per risolvere il problema clique massimo nei prossimi articoli e deve essere un'utile integrazione per il Toolkit di gestione progetto software, tester e sviluppatori.

Una matrice di Bit

Esistono numerosi metodi per rappresentare un non pesati (i bordi del grafico non sono assegnati le priorità di qualche tipo), undirected (spigoli non dispongono di una direzione da un nodo a altro) il grafico in memoria. Per il problema di massimo clique, che rappresenta un grafico utilizzando una matrice di bit offre un'eccellente efficienza spazio e le prestazioni. Figura 3 viene mostrata una matrice di bit che corrisponde al grafico di esempio. Anche se ci stiamo si lavora con un grafico undirected, viene generalmente chiamato gli indici verticali da nodi e gli indici orizzontali di nodi. Un valore pari a 1 significa che vi è uno spigolo tra i nodi corrispondenti; il valore 0 non indica nessun bordo tra i nodi. Si noti che la matrice è simmetrica e che si suppone che i nodi non sono adiacenti a se stessi.

Figura 3 Bit Matrix grafico rappresentazione

Il vantaggio principale di una matrice di bit su progetti alternativi è che consente le ricerche di adiacenza fast spesso dominano il tempo di esecuzione di molti algoritmi di graph, tra cui il problema clique massima. Se implementato in breve, lo svantaggio principale di una matrice di bit è l'utilizzo della memoria. Ad esempio, se la matrice 9 x 9 in nella figura 3 è stato implementato come una matrice bidimensionale di valori integer a 4 byte o valori booleani, la matrice richiederebbe 9 * 9 * 4 = 324 byte. Tuttavia, poiché ogni valore in una matrice di bit può essere solo 0 o 1, possiamo utilizzare i bit del valore integer per memorizzare i valori fino a 32 per intero. In questo esempio, se ci si supponga che il bit meno significativi sia a destra, la prima riga può essere archiviata come un integer a 32 bit singoli 00000000-00000000-00000000-10110000, che ha il valore decimale di 128 + 32 + 16 = 176. Pertanto, ogni riga della matrice viene memorizzato come un numero intero in cui i bit del valore integer vengono utilizzati per rappresentare la presenza o assenza di uno spigolo tra i nodi, la matrice 9 x 9 richiederebbe solo 36 byte.

Nei linguaggi di programmazione precedente, sarebbe necessario implementare una matrice di bit da zero utilizzando gli operatori bit di basso livello, ad esempio spostamento a sinistra bit per bit- o e così via. Mentre in Microsoft.Spazio dei nomi System. Collections di NET Framework ha un tipo di BitArray che semplifica l'implementazione di un programma tipo definito dal BitMatrix semplice. Una classe di BitMatrix può essere definita come indicato nella nella figura 4.

Figura 4 BitMatrix classe

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

La classe BitMatrix rappresenta una matrice quadrata ed è essenzialmente una matrice di oggetti di matrice BitArray. Il sottoscritto dichiara la classe BitMatrix con ambito privato perché sarò in grado di incorporarlo nella definizione della classe graph invece di utilizzarlo come classe autonomo. Il costruttore BitMatrix accetta un parametro n che è la dimensione di un nxnmatrix, alloca una colonna di dimensioni n di BitArray array di oggetti e quindi crea un'istanza di ogni BitArray utilizzando dimensioni n. Perché non contiene alcun tipo di bit di.NET Framework, i valori di BitArray — e, di conseguenza nella classe BitMatrix, ovvero sono esposti come tipo bool, come si può vedere nel metodo SetValue. Si noti che per mantenere il mio codice breve, ho rimosso normale degli errori.

Come potrebbe apparire con il BitMatrix:

 

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

La prima riga viene creato un oggetto di BitMatrix 9 x 9 inizialmente impostato a tutte le false (o zero) per rappresentare un grafico a undirected non pesato con nove nodi. La seconda riga imposta la riga 5, la colonna 8 su true/1 per indicare che non vi è uno spigolo tra nodo 5 e 8. La terza riga imposta la riga 8, colonna 5 su true/1, in modo che la rappresentazione di bordo del grafico è coerenza. La quarta riga viene recuperato il valore in corrispondenza della riga 2, colonna 6, un valore che indica se non vi è uno spigolo tra i nodi 2 e 6, che dovrebbe essere false/0. Si noti che determinare due nodi sono adiacenti o meno è semplicemente una ricerca rapida di matrice.

Classe di una grafico

Con una classe di BitMatrix in mano, è facile 
define una classe graph efficiente adatta per il problema clique massima e molti altri problemi di grafico. La struttura di una classe di grafico è presentata in nella figura 5. La classe graph presenta dipendenze sugli spazi dei nomi System, System. IO e System. Collections. Per il programma di esempio, ho inserito la classe graph direttamente all'interno dell'applicazione console, ma è possibile che si desidera inserire il codice in una libreria di classi.

Definizione della classe Graph figura 5

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

La definizione della classe graph inizia con:

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

Nome di classe MyGraph. È un po' spinge a tentare di definire una classe graph multiuso, ma esistono numerose varianti di grafici che è un'idea più precisa definizione delle classi di grafici diversi per diversi tipi di problemi. Qui è possibile definire la classe di grafico è volto a risolvere la massima clique e i problemi correlati, in modo avrei chiamato la classe qualcosa come MaxCliqueGraph. La classe dispone di quattro campi di dati. Il primo è un oggetto BitMatrix, come descritto nella sezione precedente. I campi numberNodes e numberEdges tenere il numero di nodi (nove nell'esempio) e il numero di spigoli undirected (13 nell'esempio) nel grafico.

Durante la risoluzione di molti problemi di graph, è necessario sapere quanti neighbors un nodo ha, vale a dire quanti nodi sono collegati a un nodo. Per il grafico di esempio in nella figura 1, nodo 5 contiene tre elementi adiacenti. Il numero di elementi adiacenti di che un nodo possiede è l'acronimo di livello del nodo. Per un determinato nodo, tale valore può essere calcolato al volo quando necessario, contando il numero di valori true/1 nella riga di dati del nodo. Un approccio molto più veloce è il conteggio e memorizzare il numero di neighbors per ciascun nodo una sola volta nel costruttore del grafico e quindi effettuare una ricerca della matrice quando è necessario. Pertanto, per il grafico di esempio dopo la creazione dell'istanza, matrice numberNeighbors avrebbe nove celle con valori [3,3,2,3,6,3,1,3,2], che indica il nodo 0 ha tre elementi adiacenti, nodo 1 dispone di tre elementi adiacenti, nodo 2 dispone di due router adiacenti e così via.

È il costruttore della classe graph:

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

Il costruttore accetta un file di testo che contiene i dati del grafico e una stringa che indica il formato del file di dati specifico. In questo caso, trasferire immediatamente il controllo a un metodo di supporto LoadDimacsFormatGraph. Questa struttura consente alla classe graph per essere facilmente estesa per supportare diversi formati di file di dati. Se sei un appassionato di tipi di enumerazione, il parametro di formato di file può essere implementato utilizzando un'enumerazione.

Il nucleo della classe MyGraph è il metodo LoadDimacsFormatGraph, che legge un file di dati di origine e memorizza la rappresentazione in forma di grafico. Esistono numerosi formati grafici standard file più o meno. Quello di che utilizzare in questo caso viene chiamato il formato DIMACS. Il DIMACS acronimo discreti matematica e scienza informatica teorica. DIMACS è un'associazione di collaborazione diretta dalla Rutgers University.

Il programma di esempio mostrato nella nella figura 2 utilizza un file denominato DimacsGraph.clq, che è elencato in Figure6. Le righe che iniziano con c sono le righe di commento. Non vi è una singola riga che inizia con p è la stringa "edge," seguita dal numero di nodi, seguita dal numero degli spigoli. Le righe che iniziano con e definiscono gli spigoli. Si noti che DIMACS il formato di file è vuoto-spazio delimitato e basati su 1 e che ciascun bordo viene memorizzato una sola volta.

Figura 6 DIMACS i dati in formato File

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

Il metodo load inizia:

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

Durante la lettura dei file di testo, è preferibile utilizzare le classi FileStream e StreamReader, ma è possibile utilizzare una delle numerose.NET alternative. Argomento successivo:

 

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

Posso eseguire un'operazione di lettura innescante e quindi passare alla riga del file di dati p. Poiché i file di testo facilmente possono acquisire spazi spurie nel tempo, viene utilizzato il metodo Trim per evitare problemi. Continuare:

 

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

Utilizzare il metodo String. Split per analizzare la riga di p. A questo punto, i token [0] contiene la stringa letterale "p", i token [1] contiene "bordo", i token [2] contiene i token e "9" [3] contiene "13". Utilizzare il valore int.Analizzare il metodo (avrei già utilizzato Convert. ToInt32) per convertire il numero di nodi e bordi in valori int che memorizzare in numEdges e numNodes variabili locali. Avrei conservato questi valori nei campi della classe ciò. numberNodes e this. numberEdges in questo momento. Ora che ho ho stabilito il numero di nodi e il numero di impulsi, chiudere il file di dati e creare un'istanza del campo di dati BitMatrix.

A questo punto si procede alla lettura dei dati di bordo dal file di dati:

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

Riapre il file e avviare la lettura dall'inizio. Tecnicamente, ovvero a causa della presenza della riga prima di tutte le righe e p, ovvero non è necessario utilizzare due letture di un file in formato DIMACS. Tuttavia, per altri formati di file in modo esplicito non memorizzano il numero di impulsi, si desideri eseguire una scansione della doppia simile a quella utilizzata in questo esempio. Quando il codice incontra una riga e quali "e 3 6", analizzare la riga e, convertire i due nodi di tipo int e sottrarre 1 per modificare la rappresentazione da 1-based a base zero. Utilizzare il metodo SetValue per creare voci simmetriche nella BitMatrix. Nota che poiché il BitMatrix è simmetrica, avrei conservato appena superiore o inferiore parte triangolare per ridurre la memoria.

A questo punto, occuparsi della matrice 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;
}
...

Per ogni nodo, esaminate attraverso la riga corrispondente e il conteggio è il numero di valori true/1 che fornisce il numero di spigoli e di conseguenza il numero di router adiacenti del nodo. Il metodo LoadDimacsFormatGraph finisce con:

 

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

Dopo il trasferimento del numero di nodi e il numero di impulsi dalle variabili locali per le variabili di campo classe, viene utilizzato un ritorno esplicito per migliorare la leggibilità per uscire dal metodo.

Il resto della classe MyGraph è semplice. Espongono i privati numberNodes e numberEdges i campi della classe come valori di sola lettura utilizzando la classe C# meccanismo delle proprietà:

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

Preferisce utilizzare la sintassi della proprietà esplicita, ma è possibile utilizzare la sintassi della proprietà implementata automaticamente se si sta utilizzando.NET 3.0 o versione successiva. Posso far conoscere il numero di elementi adiacenti di che un nodo possiede tramite un metodo:

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

Quando si lavora con i grafici, è difficile sapere quando eseguire il controllo degli errori standard e quando omettere il controllo. In questo caso, è necessario non controllare se il parametro node è compreso nell'intervallo 0.. In questo. numberNodes-1, lasciando me per aprire un indice della matrice di eccezioni dell'intervallo. In genere si aggiungono controlli di errore durante lo sviluppo, quindi dopo lo sviluppo che è possibile rimuovere i controlli che mi sento in modo sicuro possono essere omesso per migliorare le prestazioni. A causa della mia struttura dati struttura con una classe BitMatrix, scrivere un metodo per determinare se due nodi sono adiacenti è semplice:

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

È importante ricordare che il BitMatrix è simmetrica, in modo posso controllare GetValue (nodeA, NodoB) o GetValue (NodoB, NodoA). Come accennato in precedenza, controllo adiacenza nodo domina il runtime di molti algoritmi di grafico. Quando si utilizza una matrice di bit, controllo adiacenza nodo risulta più rapida poiché il controllo è una piccola modifica bit overhead gestita dalla classe BitArray oltre a una ricerca di matrice.

Codice di un semplice metodo ToString per la classe MyGraph:

 

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

Nello scenario di massimo clique, le prestazioni non sono un grande problema, in modo che per il metodo ToString, utilizzo concatenazione di stringhe semplici anziché la classe StringBuilder più efficiente. In questo caso, utilizzare i indice nelle righe di BitMatrix e j per indice nelle colonne. Terminato la stringa con un Environment. NewLine anziché "\n" per la classe MyGraph più facilmente.

Convalida del grafico

Se si fa riferimento nuovamente nella figura 2, si noterà che è possibile eseguire due importanti tipi di convalida del grafico: convalida del file di dati del grafico prima viene creata un'istanza dell'oggetto grafico e la rappresentazione in forma di grafico interno dopo la creazione di istanze di convalida.

Una trattazione completa di test e validazione graph richiederebbe un intero articolo, in modo che mi limiterò a riportare una panoramica. È possibile ottenere e visualizzare il codice di convalida completa da code.msdn.microsoft.com/mag201110TestRun.

È possibile eseguire la convalida dei dati file mediante un metodo statico ValidateGraphFile come illustrato nella nella figura 5. Come accade con il costruttore MyGraph, ValidateGraphFile immediatamente chiama un metodo di supporto ValidateDimacsGraphFile per eseguire il lavoro effettivo. Il codice di convalida del file eseguito lo scorrimento del file per verificare se tutte le righe nel modulo DIMACS valido:

 

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

Il metodo controlla anche il formato delle righe di commento non dal tentativo di analisi. Ad esempio, per la riga singola 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);
}

Il metodo utilizza una logica analoga per righe e di prova. Questo modello contiene in genere durante la convalida dei file di dati del grafico: verificare la presenza di righe valide e tenta di analizzare le righe di dati.

Una volta creata, convalidare la rappresentazione interna del grafico utilizzando il metodo ValidateGraph. Ho scoperto che un controllo completo della struttura di dati del grafico è estremamente complesso, in modo che in pratica è comune per controllare solo gli errori sono maggiori probabili di verificarsi. Un errore comune nei file di dati del grafico è una riga di dati mancanti che consente di creare un archivio di dati BitMatrix asimmetrico. Può essere confrontato con il seguente codice:

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

Verificare la presenza di altri errori includono la presenza di un vero/1 sulla bit matrice diagonale principale, una matrice di bit costituita da tutte le false/0 o true/1 e la somma dei valori nel campo di matrice numberNeighbors non uguale a numero totale di valori true/1 della matrice di bit.

Restate sintonizzati per ulteriori dettagli

In questo articolo viene presentato un tipo di struttura dati grafico che può essere utilizzato per la risoluzione di molti problemi relativi al grafico tra cui il problema clique massima. La caratteristica essenziale della struttura di dati grafico consiste nell'utilizzo di una matrice di bit definito dal programma che è efficace in termini di utilizzo della memoria e che consente le ricerche di adiacenza di nodo singolo. Il campo di matrice di bit della struttura di dati del grafico viene implementato utilizzando il.Classe BitArray NET, che si occupa di tutte le operazioni di manipolazione dei bit di basso livello. Nella colonna prossima esecuzione dei Test verrà descrivono il problema massimo clique in modo più dettagliato e mostra una soluzione di algoritmo generico che utilizza la struttura del grafico descritta di seguito.

Dr. James McCaffrey lavora per Volt Information Sciences Inc., dove gestisce la formazione tecnica degli ingegneri software Microsoft Redmond, WA, campus. Si è occupato di numerosi prodotti Microsoft, tra cui Internet Explorer e MSN Search. Dr. McCaffrey è l'autore di ".NET Test Automation Recipes"(Apress, 2006) e può essere contattato al mjammc@microsoft.com.

Grazie ai seguenti esperti tecnici per la revisione di questo articolo:Paul Koch, Dan Liebling, Ann Loomis Thompson eShane Williams