Este artículo proviene de un motor de traducción automática.

Ejecución de pruebas

Estructuras de grafos y el clique máximo

James McCaffrey

Descargar el ejemplo de código

En la columna de este mes, presento el diseño, una implementación del lenguaje C# y pruebas técnicas para una estructura de datos de gráfico que se puede utilizar para resolver el problema de la clique máxima. El código de gráfico puede utilizarse también para muchos otros problemas, como explicaré más adelante.

Por lo tanto, ¿qué es el problema de la clique máxima y por qué podría ser relevante? Un clique es un subconjunto de un gráfico donde cada nodo está conectado a todos los otros nodos. Eche un vistazo la representación gráfica en figura 1. Nodos de 2, 4 y 5 forman a una clique de tamaño tres. El problema de la clique máxima es encontrar a la camarilla con el tamaño más grande en un gráfico. La camarilla máxima de la gráfica en figura 1 es el conjunto de nodo {0, 1, 3, 4}, que tiene cuatro.

Gráfico de la figura 1 para el problema de la Clique máxima

El problema de la clique máxima se encuentra en una amplia gama de aplicaciones, incluyendo análisis de la comunicación de red social, análisis de red del equipo, visión de equipo y muchos otros. Para gráficas de tamaño incluso moderado, pero resulta que el problema de la clique máxima es uno de los problemas más interesantes y desafiantes en informática. Las técnicas utilizadas para resolver el problema de la clique máxima, que incluyen la búsqueda tabú, búsqueda avaricioso, búsqueda de meseta, adaptación de parámetro en tiempo real y historia de la solución dinámica, se puede utilizar en muchos otros escenarios de problema. En resumen, código que resuelve el problema de la clique máxima puede ser útil directamente a usted y las técnicas avanzadas por cuenta ajena en el algoritmo pueden ser útiles para solucionar otros problemas de programación difíciles.

Una solución completa para el problema de la clique máxima es demasiado larga para presentar y explicar en un artículo, por lo que presentaré la solución a través de varios artículos. El primer paso para resolver el problema de la clique máxima es diseñar, implementar y probar una estructura de datos que puede almacenar eficientemente el gráfico de análisis en memoria. La aplicación de consola en figura 2 muestra mi objetivo en esta columna.

Validación y la carga de gráfico de la figura 2

Con algunos WriteLine extractos suprimidos, el código que genera la ejecución se muestra en la figura 2 es:

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

Los datos de la figura 1 gráfico se almacena en un archivo de texto externo denominado DimacsClique.clq, que utiliza un formato estándar denominado DIMACS. Explicaré en breve el formato de archivo DIMACS. Mi programa de demostración comienza por validar el archivo de origen, a continuación, se crea una instancia de una estructura de datos de gráfico utilizando el archivo de datos. Después de que se ha duplicado el gráfico, valide la representación interna y mostrar en una imagen de fácil de usar. Como verá, una representación interna eficiente de un gráfico es extremamente importante para el problema de la clique máxima. Los acabados de programa de demostración mediante una llamada a un método que determina si dos nodos son adyacentes, nodos 5 y 8 en este caso y mediante una llamada a un método que devuelve el número de vecinos de un nodo tiene, para el nodo 4 en este caso.

Examinaré el código que genera la figura 2 línea por línea de salida. El código fuente completo para el programa de demostración está disponible en code.msdn.microsoft.com/mag201110TestRun. El código está escrito en C#, pero podrá seguirme si tiene conocimientos de programación de nivel intermedio en cualquier lenguaje de alto nivel moderno. El código de gráfico presentado aquí sienta las bases para resolver el problema de la clique máxima en los próximos artículos y debe ser una adición útil a los kits de herramientas administración de proyecto developer, tester y software.

Una matriz de Bit

Existen varios modos para representar una ponderada (bordes del gráfico no están asignados las prioridades de algún tipo), grafo (bordes no tienen una dirección de un nodo a otro) gráfico en la memoria. Para el problema de la clique máxima, que representa un gráfico utilizando una matriz de bits proporciona una excelente combinación de espacio y el mayor rendimiento. Figura 3 muestra una matriz de bit que se corresponde con el gráfico de ejemplo. A pesar de que estamos tratando con un grafo, es común llamar e índices horizontales de los índices verticales de los nodos de los nodos a. Un valor de 1 significa que es un borde entre los nodos correspondientes; el valor 0 no indica borde entre los nodos. Observe que la matriz es simétrica y que suponemos que los nodos no son adyacentes a sí mismos.

Representación de gráfico de matriz de bits de figura 3 una

La principal ventaja de una matriz de bits a través de diseños alternativos es que permite búsquedas de adyacencia rápido, que a menudo dominan el tiempo de ejecución de muchos algoritmos de gráfico, incluido el problema de la clique máxima. Si implementa sencillos, el inconveniente principal de una matriz de bits es el uso de memoria. Por ejemplo, si la matriz de 9 x 9 en figura 3 se implementó como una matriz bidimensional de enteros de 4 bytes o valores booleanos, la matriz requeriría 9 * 9 * 4 = 324 bytes. Pero dado que cada valor en una matriz de bit sólo puede ser 0 o 1, podemos utilizar los bits de un entero para almacenar valores de hasta 32 por entero. En este ejemplo, si nos imaginamos que es el bit de orden inferior de la derecha, la primera fila puede almacenarse como un único entero de 32 bits 00000000-00000000-00000000-10110000, que tiene el valor decimal de 176 = 128 + 32 + 16. Si cada fila de la matriz se almacena como un número entero donde los bits del entero se utilizan para representar la presencia o ausencia de un borde entre los nodos, la matriz de 9 x 9 requeriría sólo 36 bytes.

En lenguajes de programación anteriores, tendría que implementar una matriz de bits desde cero utilizando los operadores de bits de bajo nivel como Izq, bit a bit- o y así sucesivamente. Pero Microsoft.Espacio de nombres System.Collections de NET Framework tiene un tipo de BitArray que hace que la implementación de un tipo de BitMatrix definido por el programa fácil. Una clase de BitMatrix puede definirse como se muestra en figura 4.

Figura 4 BitMatrix clase

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 clase BitMatrix representa una matriz cuadrada y es esencialmente una matriz de objetos de la matriz de BitArray. Declara la clase BitMatrix con ámbito privado porque tengo intención de incrustar dentro de una definición de clase de gráfico en lugar de utilizar como una clase independiente. El constructor BitMatrix acepta un parámetro n que es la dimensión de un nxnmatrix, asigna una columna de tamaño n de BitArray matriz de objetos y, a continuación, crea una instancia de cada BitArray con tamaño n. Porque no hay ningún tipo de bit el.NET Framework, los valores de una BitArray — y, por tanto, en la clase BitMatrix — se exponen como un tipo bool, como puede ver en el método SetValue. Observe que para mantener mi código corto, he quitado comprobación de errores normal.

Utilizando la BitMatrix podría ser similar:

 

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

La primera línea crea un objeto de BitMatrix de 9 x 9 inicialmente establecido a todos false (o ceros) para representar un gráfico grafo, ponderado con nueve nodos. La segunda línea establece la fila 5, columna 8 a 1/true para indicar que hay un borde entre el nodo 5 y 8. La tercera línea establece fila 8, columna 5 en 1 o true para que la representación de borde del gráfico es coherente. La cuarta línea recupera el valor de la fila 2, columna 6, un valor que indica si existe o no un borde entre los nodos 2 y 6, que sería false/0. Observe que determinar si dos nodos son adyacentes es sólo una búsqueda rápida de matriz.

Una clase de gráfico

Con una clase de BitMatrix en mano, es fácil de 
define una clase de gráfico eficaz adecuada para el problema de la clique máxima y muchos otros problemas relacionados con el gráfico. La estructura de una clase de gráfico se presenta en figura 5. La clase de gráfico tiene dependencias en los espacios de nombres System, System.IO y System.Collections. El programa de ejemplo, se ha colocado la clase graph directamente dentro de la aplicación de consola, pero desea colocar el código en una biblioteca de clases.

Figura 5 definición de clase de gráfico

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 definición de clase de gráfico comienza con:

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

Nombre de la clase MyGraph. Es algo tentador intentar definir una clase de gráfico de uso múltiple, pero hay muchas variaciones de gráficos que es mejor definir clases de gráfico diferente para distintos tipos de problemas. La clase de gráfico que se define aquí está dirigida a resolver a la camarilla máxima y problemas relacionados, por lo que pude ha denominado la clase algo como MaxCliqueGraph. La clase tiene cuatro campos de datos. El primero es un objeto de BitMatrix como se describe en la sección anterior. Los campos numberNodes y numberEdges mantienen el número de nodos (nueve en el ejemplo) y el número de aristas grafo (13 en el ejemplo) en el gráfico.

Al resolver muchos problemas de gráfico, es necesario saber cuántos vecinos un nodo tiene — es decir, cuántos nodos están conectados a un nodo determinado. Para el gráfico de ejemplo en figura 1, nodo 5 tiene tres elementos contiguos. El número de vecinos de que un nodo tiene también se denomina grado del nodo. Para un determinado nodo, este valor puede calcularse sobre la marcha cuando sea necesario contando el número de valores true/1 en la fila de datos del nodo. Un enfoque mucho más rápido es contar y almacenar el número de vecinos para cada nodo de una vez en el constructor de gráfico y a continuación, realice una búsqueda en el arreglo de discos cuando sea necesario. Por lo que, para el gráfico de ejemplo después de la creación de instancias, matriz numberNeighbors tendrían nueve celdas con valores [3,3,2,3,6,3,1,3,2], que indica el nodo 0 tiene tres elementos contiguos, el nodo 1 tiene tres elementos contiguos, nodo 2 tiene dos vecinos y así sucesivamente.

El constructor de clase de gráfico es:

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

El constructor acepta un archivo de texto que contiene datos de gráfica y una cadena que indica el formato del archivo de datos específico. Aquí, inmediatamente transferir control a un método auxiliar LoadDimacsFormatGraph. Este diseño permite la clase de gráfico para ampliarse fácilmente para adaptarse a diversos formatos de archivo de datos. Si eres un fanático de tipos de enumeración, el parámetro de formato de archivo puede implementarse mediante una enumeración.

El corazón de la clase MyGraph es el método LoadDimacsFormatGraph, que lee un archivo de datos de origen y almacena la representación gráfica. Existen muchos formatos de archivo de gráfico estándar de más o menos. El que uso aquí se llama el formato DIMACS. El acrónimo DIMACS significa matemática discreta y informática teórica. DIMACS es una asociación de colaboración encabezada por la Universidad de Rutgers.

El programa de ejemplo se muestra en la figura 2 utiliza un archivo denominado DimacsGraph.clq, que aparece en 6. Las líneas que comienzan con c son las líneas de comentario. Hay un sola línea que comience con p que tiene la cadena "edge," seguido del número de nodos, seguido del número de aristas. Las líneas que comienzan con e definen bordes. Observe que el formato de archivo de las DIMACS es en blanco-espacio delimitado y basado en 1 y que cada borde se almacena sólo una vez.

Archivo de datos en formato DIMACS de la figura 6

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

El método load comienza:

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

Al leer archivos de texto, prefiero mediante las clases FileStream y StreamReader, pero desea utilizar uno de los muchos.NETAS alternativas. Siguiente:

 

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

Realizar una lectura de cebado y, a continuación, avance hasta la línea de p en el archivo de datos. Porque los archivos de texto pueden adquirir fácilmente caracteres falsos espacios en blanco con el tiempo, uso el método Trim para evitar problemas. Continuar:

 

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

Uso el método String.Split para analizar la línea de p. En este momento, tokens [0] contiene la cadena literal "p", tokens [1] contiene "borde", tokens [2] contiene "9" y tokens [3] contiene "13". Utilizar el int.Analizar el método (podía ha utilizado Convert.ToInt32) para convertir al número de nodos y bordes en valores int que almacenan en numEdges y numNodes de variables locales. Pude ha almacenado estos valores en los campos de la clase esto. numberNodes y esto. numberEdges en este momento. Ahora que he determinado el número de nodos y el número de aristas, cierre el archivo de datos y crear una instancia del campo de datos de BitMatrix.

Ahora estoy listo para leer datos de borde del archivo de datos:

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

Vuelve a abrir el archivo y comenzar a leer desde el principio. Técnicamente, debido a la presencia de la línea de p antes de las líneas e, no hay ninguna necesidad de utilizar dos lecturas de un archivo de formato DIMACS. Sin embargo, para otros formatos de archivo que explícitamente no almacenan el número de aristas, puede desear realizar un doble análisis como el que se utiliza aquí. Cuando el código encuentra una línea de e como, por ejemplo, "e 3 6", analizar la línea e, convertir los dos nodos de tipo int y reste 1 para cambiar la representación de base 1 a basado en 0. Uso el método SetValue para crear entradas simétricas en el BitMatrix. Nota que porque el BitMatrix es simétrica, pude ha almacenado sólo la parte superior o una parte triangular inferior para reducir la memoria.

A continuación, tenga cuidado de la matriz de numberNeighbors del sistema:

 

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

Para cada nodo, lo guíe a través de su fila correspondiente y el recuento del número de valores true o 1 que da el número de aristas y por lo tanto, el número de vecinos del nodo ha. El método LoadDimacsFormatGraph finaliza con:

 

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

Después de transferir el número de nodos y el número de aristas de las variables locales a las variables de campo de clase, uso un retorno explícito para mejorar la legibilidad para salir del método.

El resto de la clase MyGraph es fácil. Exponen la privada numberNodes y numberEdges clase campos como valores de sólo lectura mediante la clase C# mecanismo de propiedad:

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

Prefiero utilizando la sintaxis de propiedad explícita, pero puede utilizar sintaxis de la propiedad implementada automáticamente si está utilizando.NET 3.0 o posterior. El número de vecinos de que un nodo tiene expone a través de un método:

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

Cuando se trabaja con gráficos, es difícil saber cuándo realizar la comprobación de errores estándar y cuándo se debe omitir la comprobación. Aquí, no comprobar para ver si el parámetro node está en el intervalo de 0.. Esto. me numberNodes-1, dejando abierta a un índice de matriz fuera de la excepción de intervalo. Personalmente suelo agregar comprobaciones de errores durante el desarrollo, a continuación, después de quitar el desarrollo las comprobaciones que me siento segura pueden omitirse para mejorar el rendimiento. Debido a mi estructura de datos del diseño con una clase de BitMatrix, escribir un método para determinar si dos nodos adyacentes es fácil:

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

Recuerde que el BitMatrix es simétrico, por lo que puedo comprobar GetValue (NodoA, NodoB) o GetValue (NodoB, NodoA). Como he mencionado anteriormente, la comprobación de adyacencia de nodo domina el tiempo de ejecución de muchos algoritmos de gráfico. Cuando se utiliza una matriz de bit, comprobación adyacencia de nodo es rápido porque la comprobación es simplemente una búsqueda en el arreglo de discos más un poco de manipulación de bits overhead controlado por la clase BitArray.

Código de un simple método ToString de la clase 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;
}

En el escenario de la clique máxima, rendimiento no es un gran problema, por lo que el método ToString, utilizar concatenación de cadena simple en lugar de la clase StringBuilder más eficiente. Aquí, uso i índice en las filas de BitMatrix y j para indizar las columnas. Terminar la cadena con un Environment.NewLine en lugar de "\n" para que la clase MyGraph más portátil.

Validando el gráfico

Si hacen referencia a figura 2, observará que realizar dos importantes tipos de validación de gráfico: validar el archivo de datos de gráfico antes de que se crea una instancia del objeto gráfico y validación de la representación interna de gráfico después de la creación de instancias.

Una explicación completa de pruebas y validación de gráfico requeriría un artículo completo, por lo que únicamente presentaré una visión general. Puede obtener y ver el código de validación completa de code.msdn.microsoft.com/mag201110TestRun.

Realizar validación de archivos de datos mediante un método estático ValidateGraphFile como se muestra en figura 5. Al igual que con el constructor de MyGraph, ValidateGraphFile inmediatamente llama a un método auxiliar ValidateDimacsGraphFile para realizar el trabajo real. El código de validación de archivo recorre el archivo para ver si cada línea es en forma DIMACS válido:

 

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

El método también comprueba el formato de las líneas de comentario no al intentar analizar. Por ejemplo, para la línea p único:

 

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

El método utiliza una lógica similar para comprobar las líneas de e. Este patrón se mantiene en general al validar los archivos de datos de gráfico: comprobar las líneas válidas e intentará analizar las líneas de datos.

Una vez creada, valida la representación interna del gráfico mediante el método ValidateGraph. Parece que una comprobación completa de la estructura de datos del gráfico es sorprendentemente compleja, por lo que en la práctica es común para comprobar sólo aquellos errores que tengan más probabilidades de ocurrir. Un error común en los archivos de datos de gráfico es una línea de datos que faltan que crea un almacén de datos de BitMatrix asimétrico. Puede comprobarse con código como éste:

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

Otros errores para comprobar si hay incluyen la presencia de un 1 o true de la diagonal principal matriz bits, una matriz de bits formada por todos false/0 o 1/true y la suma de los valores en el campo de la matriz de numberNeighbors no es igual al número total de los valores true/1 en la matriz de bit.

Esté atento para obtener más detalles

Este artículo presenta un tipo de estructura de datos de gráfico que se puede utilizar para resolver muchos problemas relacionados con el gráfico incluido el problema de la clique máxima. La característica esencial de la estructura de datos del gráfico es el uso de una matriz de bits definido por el programa que es eficaz en términos de uso de memoria y permite realizar búsquedas de adyacencia-nodo rápido. El campo de la matriz de bits de la estructura de datos del gráfico se implementa mediante el.Clase BitArray NET, que se encarga de todas las operaciones de manipulación de bits de bajo nivel. En la siguiente columna ejecución de prueba, describiremos el problema de la clique máxima con más detalle y mostrar una solución de algoritmo voraz que utiliza la estructura de gráfico que se describe aquí.

Dr.James McCaffrey  trabaja en Volt Information Sciences Inc., donde encarga de formación técnica, los ingenieros de software en el Microsoft Redmond, Washington, campus. Trabajó en varios productos de Microsoft, incluyendo Internet Explorer y MSN Search. Recuperación ante desastres. McCaffrey es el autor de ".NET Test Automation Recipes"(Apress, 2006) y puede ponerse en mjammc@microsoft.com.

Gracias a los siguientes expertos técnicos para la revisión de este artículo:Paul Koch, Dan Liebling, Ann Loomis Thompson yShane Williams