Uso de memória da matriz e lista

showMemoryUse()

O método exibe a quantidade de memória usada pela matriz de adjacência e pela lista de adjacência.
O cálculo do uso de memória é o seguinte:

• Para a matriz
  
  
  
  • É pego a quantidade de nós da matriz e elevado ao quadrado. O resultado é multiplicado por 4 (tamanho de inteiros, em bytes)
    
  • qtdnos*qtdnos*4
    
  
  
• Para a lista
  
  
  
  • Primeiro se é multiplicado a quantidade de nós por 4. Isso é para calcular o tamanho do vetor que armazenará as listas encadeadas.
    
  • O resultado da multiplicação da quantidade de nós por 4 é somado com a quantidade de arestas multiplicada por 12. Isso por que cada elemento da lista (que é, na verdade, uma aresta) armazena um peso e o indice do nó para onde se tem a ligação, ambos inteiros (tamanho 4 bytes) e um ponteiro para o próximo elemento, sendo que o ponteiro utiliza também 4 bytes.
    
  • (qtdnos*4) + (qtdarestas * 12);
    
  
  
  

Realizando alguns testes, observamos que a lista de adjacência só é eficiente caso seja usada para representar uma matriz esparsa. Matrizes não-esparsas ainda são eficientes, na questão de uso de memoria, na forma de matrizes de adjacência.

Exemplo

Levando em consideração um grafo de 100 nós, o uso da matriz de adjacência é de 40000 bytes. A lista de adjacência, por sua vez, usa apenas 400 bytes se não houver arestas. Se preenchermos o grafo com 10000 arestas, fazendo todos os nós se conectarem, o uso de memória da matriz permanece inalterado enquanto o uso de memória da lista sobe para 120400 bytes.

  void Grafo::showMemoryUse()
  {
      int mem_matr;
      int mem_list;
      mem_matr = qtdnos*qtdnos*4;
      mem_list = (qtdnos*4) + (qtdarestas * 12);
      cout << "Memória usada pela matriz: " << mem_matr << endl;
      cout << "Memória usada pela lista: " << mem_list << endl;
  }

Gerar o grafo a partir de um arquivo de texto

Aqui está o método para preencher o grafo a partir de um arquivo de texto.
O arquivo deve seguir o seguinte padrão para que seja interpretado corretamente:

  N
  p0
  p1
  p2
  ...
  pN-1
  A
  X Y P D
  X Y P D
  X Y P D
  X Y P D
  X Y P D

• N - número de nós que o grafo irá conter
  
• p0 ~ pn-1 - o peso de cada nó a ser inserido
  
• A - número de arestas a serem inseridos no grafo
  
• X, Y - coordenadas do da aresta a ser inserida
  
• P - Peso da aresta
  
• D - Diz se a aresta é direcional(1) ou não (0)
  

Um exemplo de arquivo válido:

  2
  1
  2
  4
  0 0 2 1
  0 1 1 1
  1 0 5 1
  1 1 6 1

O seguinte formato de arquivo também é válido, mas não é bom usar pois é difícil identificar os itens do arquivo

  2 1 2 4 0 0 2 1 0 1 1 1 1 0 5 1 1 1 6 1

O método para ler arquivos:

  void Grafo::readFile(string filename){
   ifstream arquivo (filename.c_str());
   if( arquivo.is_open()){
    int contador, temp, x, y, p;
    arquivo >> qtdnos;
    dimensionar(qtdnos);
    for( int i = 0; i < qtdnos; i++)
     arquivo >> pesos[i];
    arquivo >> contador;
    for(int i = 0; i < contador; i++){
     arquivo >> x >> y >> p >> temp;
     setAresta(x,y,p);
     if(temp == 0)
      setAresta(y,x,p);
    }
   } else {
    cout << "erro: arquivo inexistente/inválido" << endl;
   }
  }

O método recebe o nome do arquivo como parametro (uma string) e tenta abri-lo. Caso consiga, ou seja, caso o arquivo exista, é iniciada a interpretação do arquivo na seguinte lógica:

• É lida a primeira linha, que contém o numero de nós do grafo. Com isso ele é redimensionado pelo método dimensionar(int tamanho)
  
• Na próximas N linhas (N sendo a quantidade de nós lido) são lidos e armazenados os pesos de cada nó.
  
• Assim que a última linha de pesos for lida, é lido a quantidade de arestas a serem inseridas na matriz de adjacência do grafo
  
• Cada linha que contém as informações da aresta é lida a aresta adicionada conforme o peso. Caso a aresta não seja direcional(0), uma nova aresta com o mesmo peso é inserido nas coordenadas inversas (se as coordenadas era 1,2 e a aresta não é direcional, uma nova aresta é colocada em 2,1)
  

Usando exemplo de arquivo de entrada dado aqui, o grafo é preenchido desta maneira:

  Matriz
    0 1 
  0|2 1 
  1|5 6 
  Pesos
  0|1|
  1|2|

A saída acima foi gerada usando o método showAll(). Para ficar mais legível, alteramos um pouco o método os métodos showPesos() e showMatriz(), além de adicionar um teste em showAll() para verificar se o grafo está vazio ou não

  void Grafo::showMatriz(){
   cout << "  ";
   for(int i = 0; i < qtdnos; i++)
    cout << i << " ";
   cout << endl;
   for(int i = 0; i < qtdnos; i++){
    cout << i << "|";
    for (int j = 0; j < qtdnos; j++){
     cout << matriz[i][j] << " ";
    }
    cout << endl;
   }
  }
  
  void Grafo::showPesos(){
   for(int i = 0; i < qtdnos; i++)
    cout << i << "|";
   cout << endl;
    
   for(int i = 0; i < qtdnos; i++)
    cout << pesos[i] << "|";
   cout << endl;
  }
  
  void Grafo::showAll(){
   if(qtdnos != 0){
   cout << "Matriz" << endl;
   showMatriz();
   cout << "Pesos" << endl;
   showPesos();
   } else {
    cout << "Grafo vazio"<< endl;
   }
  }

O código fonte da classe grafo com todas as alterações até agora pode ser baixado aqui.

Correções na classe grafo

Pois é. Haviam alguns erros na classe grafo que postamos. Nenhum deles foi sério (apenas esquemos de colocar a declaração de alguns métodso dentro da classe, e coisas assim). No entanto, o método dimensionar(int tamanho) pode ser problemático dependendo do compilador usado. O problema está no final do post (assim como uma possível solução).

Classe

    class Grafo{
    private:
     int qtdnos;
     int **matriz;
     int *pesos;
    public:
     Grafo();
     Grafo(int tamanho);
     void dimensionar(int tamanho);
     void setAresta(int linha, int coluna);
     void setAresta(int linha, int coluna, int peso);
     void setPeso(int no, int peso);
     int getPeso(int no);
     int getAresta(int linha, int coluna);
     int size();
     void showMatriz();
     void showPesos();
     void showAll();
    };

---

Construtores

    Grafo::Grafo(){
     dimensionar(0);
    }
    Grafo::Grafo(int tamanho){
     dimensionar(tamanho);
    }

---

dimensionar(int tamanho)

Este método funcionou sem problemas usando o compilador g++. No entanto, quando o compilamos usando o Builder, os ponteiros para inteiro alocados no vetor de pesos e na matriz de adjacência não foram setados para NULL por padrão, o que faz o grafo ser gerado com lixo.
Criamos um workaround para resolver o problema, mas é apresentado dois warnings ao compilar com o g++ (não sei se com o Builder estes warnings aparecem):

  grafo.cpp:18: warning: converting to non-pointer type ‘int’ from NULL
  grafo.cpp:20: warning: converting to non-pointer type ‘int’ from NULL
  
  linha 18: pesos[i] = NULL;
  linha 20: matriz[i][j] = NULL;

Então se alguém pensar em uma solução melhor, por favor, avise :)

  void Grafo::dimensionar(int tamanho) {
   if (tamanho > 0) {
    qtdnos = tamanho;
    pesos = new int[qtdnos];
    matriz = new int*[qtdnos];
    for(int i = 0; i < qtdnos; i++){
     matriz[i] = new int[qtdnos];
     pesos[i] = NULL;
     for(int j = 0; j < qtdnos; j++)
      matriz[i][j] = NULL;
    }
   } else {
    qtdnos = 0;
    pesos = NULL;
    matriz = NULL;
   }
  }

Classe para Grafos

Segue abaixo a classe de Grafos.
É usada uma matriz de adjacência para marcar onde há arestas e o peso delas.
Um vetor separado é usado para armazenar o peso de cada nó do grafo.

  class Grafo{
  private:
   int qtdnos;
   int **matriz;
   int *pesos;
  public:
   Grafo();
   Grafo(int tamanho);
   void dimensionar(int tamanho);
   void setAresta(int linha, int coluna);
   void setAresta(int linha, int coluna, int peso);
   void setPeso(int no, int peso);
   int getPeso(int no);
   int getAresta(int linha, int coluna);
   int size();
   void showMatriz();
   void showPesos();
   void showAll();
  };

---

Construtores

Possui dois contrutores. Ambos tem o procedimento interno tratado pelo método dimensionar(int tamanho)

  Grafo::Grafo(){
   dimensionar(0);
  }
  Grafo::Grafo(int tamanho){
   dimensionar(tamanho);
  }

---

dimensionar

O método dimensionar é responsavél pela criação das dimensões da matriz de adjacência, vetor de peso e a quantidade de nós.

Seu funcionamento é o seguinte:

• Se receber um valor maior que zero:
  
  
  
  • A quantidade de nós será definada como esse valor
    
  • O vetor de pesos será criado dinâmicamente.
    
  • A matriz de adjacência é criada, utilizando um vetor de ponteiros para inteiros e, em cada posição, um vetor de inteiros
    
  
  
  
• Se o valor recebido foir igual ou menor a zero
  
  
  
  • A quantidade de nós será definica como zero
    
  • Tanto o vetor de pesos quanto a matriz de adjacência apontarão para NULL
    
  
  

  void Grafo::dimensionar(int tamanho) {
   if (tamanho > 0) {
    qtdnos = tamanho;
    pesos = new int[qtdnos];
    matriz = new int*[qtdnos];
    for(int i = 0; i < qtdnos; i++)
     matriz[i] = new int[qtdnos];
   } else {
    qtdnos = 0;
    pesos = NULL;
    matriz = NULL;
   }
  }

.:Uma dificuldade encontrada pelo grupo foi na alocação da matriz.

Inicialmente usamos o seguinte código para tentar aloca-la:

  *matriz = new int[qtdnos];
  for(int i = 0; i < qtdnos; i++)
   matriz[i] = new int[qtdnos];

O erro estava logo na primeira alocação da matriz. Ali está para atribuir um vetor de inteiros ao ponteiro. No entanto, o objetivo é fazer com que seja atribuido um vetor de ponteiros para inteiros e depois, para cada posição do vetor, atribuir um vetor de inteiros.

---

setAresta e getAresta

Existem dois métodos com o nome de setAresta. O primeiro, que recebe apenas coordenadas X,Y (neste caso, representados por i e j), chama o segundo método setAresta, desta vez passando o valor 1 como parametro adicional. O segundo método setAresta, que recebe coordenadas X,Y e um peso, faz com que o peso recebido seja inserido na matriz, na posição especificada por i e j.

O método getAresta recebe apenas uma coordenada X,Y e retorna o valor armazenado na matriz naquela posição.

  void Grafo::setAresta(int i, int j){
   setAresta(i, j, 1);
  }
  
  void Grafo::setAresta(int i, int j, int peso){
   matriz[i][j] = peso;
  }
  
  int Grafo::getAresta(int i, int j){
   return matriz[i][j];
  }

---

setPeso e getPeso

O método setPeso recebe apenas dois valores como parametro: o primeiro é o nó que terá seu peso alterado; o segundo é o valor a ser atribuido ao nó especificado.

O método getPeso recebe como parametro apenas o nó a ser retornado.

  void Grafo::setPeso(int i, int peso){
   pesos[i] = peso;
  }
  
  int Grafo::getPeso(int i){
   return pesos[i];
  }

---

size

Este método apenas retorna a quantidade de nós existentes no grafo

  int Grafo::size(){
   return qtdnos;
  }

---

showMatriz, showPesos e showAll

Métodos para exibir o conteúdo do gráfo. Nada mais.

  void Grafo::showMatriz(){
   for(int i = 0; i < qtdnos; i++){
    for (int j = 0; j < qtdnos; j++){
     cout << matriz[i][j] << " ";
    }
    cout << endl;
   }
  }
  
  void Grafo::showPesos(){
   for(int i = 0; i < qtdnos; i++)
    cout << i << " ";
   cout << endl;
    
   for(int i = 0; i < qtdnos; i++)
    cout << pesos[i] << " ";
   cout << endl;
  }
  
  void Grafo::showAll(){
   cout << "Matriz" << endl;
   showMatriz();
   cout << "Pesos" << endl;
   showPesos();
  }