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