Exercícios a resolver na 3ªaula prática

 - Tratamento de Excepções

Implemente a classe Grafo de acordo com a especificação das alíneas seguintes.

A classe Grafo permite representar um grafo orientado composto por nós interligados por arestas. Cada um destes itens pode estar associado a tipos de dados diferentes. A classe Grafo é uma classe genérica com dois argumentos, os nós e as arestas. Pressupõe-se que nós e arestas podem ser sujeitas a um teste de igualdade, mas não necessariamente a testes de comparação. Todos os nós de um grafo são diferentes.

Cada instância da classe Grafo contém um vector de nós (o que permite associar internamente cada nó a uma posição do vector). Para cada nó, existe um vector de arestas (ordenadas segundo o nó de destino). Para um grafo de n nós, podem existir até n² arestas. A figura seguinte mostra a estrutura de dados para um exemplo.

A declaração da classe Grafo é a seguinte:

template <class N, class A>

class Grafo {

    struct Aresta { A val; bool usada; };

    struct No { N val; Aresta *arestas; };

    No *v_nos;   // vector de nós

    int tamanho;

    int nn;     // nº de nós

    int na;     // nº de arestas

  public:

    Grafo (const int n = 10);

    ~Grafo();

    Grafo & inserir_no(const N &dados);

    Grafo & inserir_aresta(const N &inicio, const N &fim, const A &dados);

    Grafo & eliminar_aresta(const N &inicio, const N &fim);

    A & valor_aresta(const N &inicio, const N &fim);

    int n_arestas(void) const;

    int n_nos(void) const;

    int capacidade (void) const;

    void imprimir(std::ostream &os) const;

};

template <class N, class A>

std::ostream & operator<<(std::ostream &out, const Grafo<N, A> &g);

Os membros função da classe devem lançar excepções sempre que conveniente.

1. Implemente o construtor e o destrutor.

2. Implemente os métodos n_nos (que retorna o número de nós), capacidade (que retorna o número máximo de nós que o grafo pode ter) e n_arestas (que retorna o número de arestas existentes).

3. Implemente o membro-função inserir_no, que insere um novo nó no grafo e retorna o grafo alterado (this). Esta função deve lançar excepções apropriadas caso não exista espaço para um novo nó, ou esse nó já exista (ver programa de teste).

4. Implemente o membro-função inserir_aresta, que insere uma nova aresta no grafo e retorna o grafo alterado (this). Esta função deve lançar uma excepção apropriada caso a aresta já exista.

5. Implemente o membro-função valor_aresta, que retorna uma referência para os dados da aresta especificada. Esta função deve lançar uma excepção apropriada caso a aresta não exista no grafo (ver programa de teste).

6. Implemente o membro-função eliminar_aresta, que elimina uma aresta do grafo e retorna o grafo alterado (this). Esta função deve lançar uma excepção apropriada caso a aresta não exista no grafo (ver programa de teste).

7. Implemente o membro-função imprimir, que escreve o grafo para um stream de saída. Para o exemplo indicado anteriormente, a função deve produzir:

   ( A [B 5] [C 8] ) ( B [D 9] ) ( C [D 3] [E 4] ) ( D [B 11] [E 2] ) ( E )

8. Utilize a função anterior para implementar o operador de saída <<.

9. Execute, e analise, o seguinte programa de teste: TesteGrafo.cpp