Este artigo foi traduzido por máquina.

Execução de teste

Estruturas de gráfico e o número máximo de grupos

James McCaffrey

Baixar o código de exemplo

Na coluna deste mês, apresento o design, uma implementação de linguagem C# e técnicas para uma estrutura de dados do gráfico que pode ser usado para solucionar o problema de clique máximo de teste. O código de gráfico também pode ser usado para muitos outros problemas, conforme explicarei.

Assim, o que é o problema de clique máximo e por que ele seja relevante para você? Um clique é um subconjunto de um gráfico em que cada nó é conectado a todos os outros nós. Dê uma olhada na representação da graph a Figura 1. Nós de 2, 4 e 5 formam um clique do tamanho de três. O problema de clique máximo é encontrar o clique com o maior tamanho em um gráfico. O clique máximo para o gráfico na a Figura 1 é o conjunto de nós {0, 1, 3, 4}, cujo tamanho quatro.

Figura 1 uma gráfico para o problema de Clique máximo

O problema de clique máximo é encontrado em uma grande variedade de aplicativos, incluindo análise de comunicação de rede social, análise de rede do computador, a visão do computador e muitos outros. Para gráficos de tamanho até mesmo moderado, acontece que o problema de clique máximo é um dos problemas mais difíceis e interessantes em ciências da computação. As técnicas usadas para resolver o problema de clique máximo — que incluem pesquisa tabu, pesquisa greedy, pesquisa de estabilidade, adaptação de parâmetro em tempo real e histórico de solução dinâmico — pode ser usado em muitos outros cenários de problema. Em suma, código que resolve o problema de clique máximo pode ser útil diretamente para você e as técnicas avançadas empregadas no algoritmo podem ser útil para solucionar outros problemas de programação difícil.

Uma solução completa para o problema de clique máximo é muito longa para apresentar e explicar um artigo, portanto, apresentarei a solução ao longo de vários artigos. A primeira etapa para solucionar o problema de clique máximo é projetar, implementar e testar uma estrutura de dados que pode armazenar de forma eficiente o gráfico em análise na memória. O aplicativo de console em a Figura 2 mostra aonde quero chegar nesta coluna.

Validação e carregamento de gráfico da Figura 2

Com alguns WriteLine instruções removidas, o código que produziu a execução mostrada na a 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));

Os dados para o a Figura 1 gráfico é armazenado em um arquivo de texto externo denominado DimacsClique.clq, que usa um formato padrão, chamado DIMACS. Explicarei o formato de arquivo DIMACS em breve. Meu programa de demonstração começa Validando o arquivo de origem, em seguida, cria uma estrutura de dados do gráfico usando o arquivo de dados. Depois que o gráfico foi instanciado tem, eu validar a representação interna e exibi-la em uma imagem amigável a humanos. Como você verá, uma eficiente representação interna de um gráfico é extremamente importante para o problema de clique máximo. A conclusão do programa de demonstração, chamando um método que determina se os dois nós são adjacentes, nós 5 e 8, neste caso e chamando um método que retorna o número de vizinhos um nó possui, para nó 4 nesse caso.

Vou lhe apresentar através do código que gerou o a Figura 2 linha por linha de saída. O código-fonte completo para o programa de demonstração está disponível em code.msdn.microsoft.com/mag201110TestRun. O código é escrito em C#, mas você deve ser capaz de acompanhar-me se você tiver as habilidades de programação de nível intermediário em qualquer idioma moderno de alto nível. O código de gráfico apresentado aqui estabelece as bases para resolver um problema clique máximo em artigos futuros e deve ser uma adição útil para seu toolkits desenvolvedor, testador e software de gerenciamento de projeto.

Uma matriz de bits

Há várias maneiras comuns para representar uma média não ponderada (as bordas do gráfico não são prioridades atribuídas de algum tipo), dirigido (bordas não têm uma direção de um nó para outro) gráfico na memória. O problema, clique em máximo que representa um gráfico usando uma matriz de bits oferece uma combinação excelente de eficiências de espaço e o desempenho. Figura 3 mostra uma matriz de bits que corresponde ao gráfico de exemplo. Mesmo que estamos lidando com um gráfico dirigido, é comum para chamar os índices verticais os partir-nós e os índices horizontais nós-a. Um valor 1 significa que há é uma borda entre os nós correspondentes; um valor 0 não indica que nenhuma borda entre os nós. Observe que a matriz é simétrica e que Supomos que nós não são adjacentes entre si.

Figura 3 uma Bit Matrix Graph representação

A principal vantagem de uma matriz de bits sobre designs alternativos é que ele permite pesquisas de adjacência rápida, que geralmente dominam o tempo de execução de vários algoritmos de gráfico, incluindo o problema clique máximo. Se implementada bruta, a principal desvantagem de uma matriz de bits é o uso de memória. Por exemplo, se a matriz de 9x9 na a Figura 3 foi implementado como uma matriz bidimensional de inteiros de 4 bytes ou booleanos, a matriz exigiria 9 * 9 * 4 = 324 bytes. Mas porque cada valor em uma matriz de bits só pode ser 0 ou 1, podemos usar os bits de um inteiro para armazenar até 32 valores por inteiro. Neste exemplo, se podemos imaginar que o bit de ordem inferior é à direita, a primeira linha pode ser armazenada como um único inteiro de 32 bits 00000000-00000000-00000000-10110000, que tem o valor decimal de 128 + 32 + 16 = 176. Portanto, se cada linha da matriz é armazenada como um único inteiro onde os bits do inteiro são usados para representar a presença ou ausência de uma borda entre os nós, a matriz de 9x9 exigiria apenas 36 bytes.

Em linguagens de programação mais antigas, você terá que implementar uma matriz de bits a partir do zero usando operadores de bit de baixo nível, como shift esquerda, bit a bit- ou e assim por diante. Mas o Microsoft.NET Framework System. Collections namespace tem um tipo de BitArray que torna a implementação de um tipo de BitMatrix definido pelo programa fácil. Uma classe de BitMatrix pode ser definida como mostrado na a Figura 4.

Figura 4 um 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;
  }
}

A classe BitMatrix representa uma matriz quadrada e é essencialmente uma matriz de objetos de matriz BitArray. Eu declaro a classe BitMatrix com escopo particular porque pretendo incorporá-lo dentro de uma definição de classe do gráfico, em vez de usá-lo como uma classe de autônomo. O construtor BitMatrix aceita um parâmetro n que é a dimensão de um nxnmatrix, aloca uma coluna de tamanho n de BitArray array objetos e então instancia cada BitArray usando tamanho n. Porque não há nenhum tipo de bit.NET Framework, os valores em um BitArray — e, portanto, na classe BitMatrix — são expostos como tipo bool, como você pode ver no método SetValue. Observe que para manter meu código curto, removi a verificação de erros normal.

Usar o BitMatrix pode parecer com:

 

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

A primeira linha cria um objeto de BitMatrix de 9x9 inicialmente definido para todos os falso (ou zeros) para representar um gráfico de média não ponderado, dirigido com nove nós. A segunda linha define a linha 5, 8 de coluna para true/1 para indicar que há uma borda entre o nó 5 e 8. A terceira linha define linha 8, coluna 5 1/verdadeiro para que a representação de borda do gráfico é consistente. A quarta linha busca o valor na linha 2, 6, um valor que indica se há ou não uma borda entre os nós 2 e 6, o que seria FALSO/0 coluna. Observe que determinar se dois nós são adjacentes ou não é apenas uma pesquisa rápida de matriz.

Uma classe de gráfico

Com uma classe de BitMatrix em mãos, é fácil 
define uma classe de gráfico eficiente adequada para o problema de clique máximo e muitos outros problemas relacionados ao gráfico. A estrutura de uma classe de gráfico é apresentada em a Figura 5. A classe de gráfico possui dependências em namespaces System, System. IO e System. Collections. Para o programa de exemplo, coloquei a classe gráfico diretamente dentro do aplicativo de console, mas talvez você queira colocar o código em uma biblioteca de classe.

Figura 5 uma definição de classe 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

A definição de classe do gráfico começa com:

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

Chamei a classe MyGraph. É um pouco tentador para tentar definir uma classe de gráfico com várias finalidades, mas existem tantas variações de gráficos que é uma idéia melhor definir classes de gráfico diferente para diferentes tipos de problemas. A classe graph que aqui, eu defino visa Resolvendo o clique máximo e problemas relacionados, portanto, foi chamado a classe algo como MaxCliqueGraph. A classe possui quatro campos de dados. A primeira é um objeto BitMatrix, conforme descrito na seção anterior. Os campos numberNodes e numberEdges mantém o número de nós (nove no exemplo) e o número de arestas dirigidos (13 no exemplo) no gráfico.

Ao solucionar muitos problemas de gráfico, é necessário saber quantos neighbors um nó possui — ou seja, quantos nós são conectados a um determinado nó. Para o gráfico de exemplo na a Figura 1, nó 5 tem três vizinhos. O número de vizinhos que tem um nó também é chamado o grau do nó. Para um determinado nó, esse valor poderia ser calculado dinamicamente quando necessário, contando o número de valores true/1 na linha de dados do nó. Uma abordagem muito mais rápida é contar e armazenar o número de neighbors para cada nó de uma vez no construtor do gráfico e em seguida, executar uma pesquisa de matriz, quando necessário. Portanto, para o gráfico de exemplo após instanciação, array numberNeighbors teria nove células com valores [3,3,2,3,6,3,1,3,2], indicando que o nó 0 tem três vizinhos, o nó 1 tem três vizinhos, nó 2 tem dois vizinhos e assim por diante.

O construtor de classe de gráfico é:

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

O construtor aceita um arquivo de texto que contém os dados do gráfico e uma seqüência de caracteres que indica o formato específico do arquivo de dados. Aqui, eu imediatamente transfere o controle para um método auxiliar LoadDimacsFormatGraph. Esse design permite que a classe de gráfico pode ser facilmente estendido para acomodar vários formatos de arquivo de dados. Se você é fã de tipos de enumeração, o parâmetro do formato de arquivo pode ser implementado usando uma enumeração.

O coração da classe MyGraph é o método de LoadDimacsFormatGraph, que lê um arquivo de dados de origem e armazena a representação de gráfico. Há muitos formatos de arquivo de gráfico padrão de mais ou menos. O que uso aqui será chamado o formato DIMACS. O acrônimo DIMACS significa discretas de matemática e ciência da computação teórica. DIMACS é uma associação de colaboração pontas pela Universidade de Rutgers.

O programa de exemplo mostrado na a Figura 2 usa um arquivo chamado DimacsGraph.clq, que é listado em Figura 6. Linhas que começam com c são linhas de comentário. Há uma única linha que começa com p que tem a string "edge," seguido do número de nós, seguido pelo número de bordas. Linhas que começam com e definem as bordas. Observe que o DIMACS formato de arquivo é o espaço em branco delimitado e baseado em 1 e que cada borda é armazenada apenas uma vez.

Figura 6 arquivo de dados em formato 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

O método load começa:

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

Ao ler arquivos de texto, eu prefiro usar as classes de FileStream e StreamReader, mas convém usar uma das várias.NET alternativas. Próximo:

 

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

Posso executar uma leitura a desobstrução e, em seguida, Avançar para a linha p no arquivo de dados. Porque os arquivos de texto facilmente podem adquirir os caracteres de espaço em branco artificiais ao longo do tempo, uso o método de aparo para ajudar a 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);
...

Eu uso o método String. Split para analisar a linha de p. Neste ponto, tokens [0] contém a seqüência de caracteres literal "p", [1] tokens mantém "edge", tokens [2] tem "9" e tokens [3] tem "13". Posso usar o int.Analisa método (poderia ter usado Convert. ToInt32) para converter o número de nós e bordas em int valores que posso armazenar em numEdges e numNodes variáveis locais. Eu poderia armazenou esses valores em campos de classe isso. numberNodes e isso. numberEdges neste momento. Agora que eu tenha determinado o número de nós e o número de arestas, fechar o arquivo de dados e instanciar o campo de dados BitMatrix.

Agora estou pronto para ler dados de borda do arquivo de dados:

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

Posso reabrir o arquivo e iniciar a leitura do início. Tecnicamente — por causa da presença da linha antes de quaisquer linhas e p — não é necessário usar duas leituras de um arquivo de formato DIMACS. No entanto, para outros formatos de arquivo que não explicitamente armazenam o número de arestas, convém executar uma verificação dupla como aquele usado aqui. Quando o código encontra uma linha e, como "e 3 6", posso analisar a linha e, converta os dois nós digitar int e subtraia 1 para alterar a representação de base 1 para baseado em 0. Uso o método SetValue para criar entradas simétricas o BitMatrix. Observe que como o BitMatrix é simétrico, eu poderia armazenou apenas a parte superior ou inferior parte triangular para reduzir a memória.

Em seguida, tome cuidado da matriz 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;
}
...

Para cada nó, eu caminhar pela sua linha correspondente e contar o número de valores true/1 que fornece o número de arestas e, portanto, o número de vizinhos do nó tem. O método LoadDimacsFormatGraph termina com:

 

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

Depois de transferir o número de nós e o número de arestas das variáveis locais para variáveis de campo da classe, eu uso um retorno explícito para legibilidade para sair do método.

O restante da classe MyGraph é fácil. Divulgar o private numberNodes e numberEdges os campos de classe como somente leitura valores usando a classe C# mecanismo de propriedade:

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

Eu prefiro usar a sintaxe da propriedade explícita, mas você pode usar a sintaxe da propriedade implementada automaticamente se você estiver usando.NET 3.0 ou superior. Divulgar o número de vizinhos que tem um nó por meio de um método:

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

Ao trabalhar com gráficos, é difícil saber quando realizar a verificação de erro padrão ou omitir a verificação. Aqui, não verifico se o parâmetro de nó está no intervalo de 0.. isso. numberNodes-1, me deixando aberta para um índice de matriz de exceção do intervalo. Geralmente adiciono verificações de erro durante o desenvolvimento e, em seguida, após o desenvolvimento de que remover as verificações que sinto-me com segurança podem ser omitidas para melhorar o desempenho. Devido a minha estrutura de dados de design com uma classe BitMatrix, escrever um método para determinar se os dois nós são adjacentes é fácil:

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

Lembre-se de que o BitMatrix é simétrico, assim verificar GetValue (nodeA, nodeB) ou GetValue (nodeB, nodeA). Como mencionei anteriormente, a verificação de adjacência do nó domina o tempo de execução de vários algoritmos de gráfico. Ao usar uma matriz de bits, verificação adjacência de nó é rápida porque a verificação é apenas uma pesquisa de array mais um pouco-manipulação de bits sobrecarga é manipulado pela classe BitArray.

Eu de código: um método ToString simples para a 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;
}

No cenário, clique em máximo desempenho não é um grande problema, portanto, para o método ToString, posso usar a concatenação de cadeia de caracteres simples em vez de usar a classe StringBuilder mais eficiente. Aqui, eu uso i para indexar em linhas de BitMatrix e j para indexar em colunas. Vou encerrar a seqüência de caracteres com um Environment.NewLine em vez de "\n" para tornar a classe MyGraph mais portátil.

Validando o gráfico

Se você consultar novamente a a Figura 2, você observará que eu executar dois tipos importantes de validação de gráfico: Validando o arquivo de dados do gráfico antes do objeto gráfico é instanciado e validando a representação interna do gráfico após a instanciação.

Uma discussão completa sobre teste e validação de gráfico exigiria um artigo inteiro, portanto, apenas apresentarei uma visão geral. Você pode obter e exibir o código de validação completa da code.msdn.microsoft.com/mag201110TestRun.

Posso executar a validação do arquivo de dados usando um método estático ValidateGraphFile, conforme mostrado na a Figura 5. Como ocorre com o construtor de MyGraph, ValidateGraphFile imediatamente chama um método auxiliar ValidateDimacsGraphFile para fazer o trabalho real. O código de validação do arquivo itera por meio do arquivo para ver se cada linha no formulário válido do DIMACS:

 

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

O método também verifica o formato de linhas sem comentário, tentar analisar. Por exemplo, para a linha única 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);
}

O método usa uma lógica similar para linhas e de teste. Esse padrão mantém em geral ao validar os arquivos de dados do gráfico: Verificar linhas válidas e tentar analisar as linhas de dados.

Depois de instanciado, posso validar a representação de gráfico interno usando um método ValidateGraph. Acontece que uma verificação completa da estrutura de dados do gráfico é surpreendentemente complexa, portanto, na prática é comum para verificar apenas os erros que são mais chances de ocorrer. Um erro comum em arquivos de dados do gráfico é uma linha de dados ausentes que cria um armazenamento de dados de BitMatrix assimétrico. Ele pode ser verificado com código como este:

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

Outros erros para verificar se há incluem a presença de um verdadeiro/1 no bit matrix principal diagonal, uma matriz de bits que consiste em todos os falsos/0 ou verdadeiro/1 e a soma dos valores no campo de matriz de numberNeighbors o número total de valores true/1 na matriz de bits igual a não.

Fique atento para obter mais detalhes

Este artigo apresentou um tipo de estrutura de dados do gráfico que pode ser usado para solucionar muitos problemas relacionados ao gráfico incluindo o problema clique máximo.O recurso essencial da estrutura de dados do gráfico é o uso de uma matriz de bits definido pelo programa que é eficiente em termos de uso de memória e que permite pesquisas rápidas de nó-adjacência.O campo de matriz de bits da estrutura de dados do gráfico é implementado usando o.Classe de BitArray NET, que cuida de todas as operações de manipulação de bits de nível inferior.Na próxima coluna execução de teste, vou descrever o problema máximo clique em mais detalhes e mostrar a você uma solução de algoritmo greedy que usa a estrutura do gráfico descrita aqui.

Recuperação de desastres James McCaffrey trabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico para engenheiros de software trabalhando com a Microsoft Redmond, Wash campus. Ele é trabalhou em vários produtos da Microsoft, incluindo o Internet Explorer e o MSN Busca. Recuperação de desastres. McCaffrey é autor de ".NET Test Automation Recipes"(Apress, 2006) e pode ser contatado pelo mjammc@microsoft.com.

Graças aos seguintes especialistas técnicos para revisão deste artigo: Paul Koch, Dan Liebling, Ana Loomis Thompson eShane Williams