Elementos de Programação
Amílcar Sernadas, Cristina Sernadas e Jaime Ramos

Tipos de dados abstractos: implementação

Grafos

Um grafo dirigido é um par (V,A), onde V é um conjunto (de vértices) e A é um conjunto (de arestas) de pares de elementos de V.  Quando o par (v1,v2) é um aresta, dizemos que v1 e v2 estão ligados ou que há um caminho de v1 para v2.  O facto de o grafo ser dirigido significa que a existência de um caminho de v1 para v2 é independente da existência de um caminho de v2 para v1.

Desenvolva o diagrama ADJ e especifique o tipo de dados graphs com as operações newgraph, addedge, deledge, graphQ e emptyQ definidas como se segue.
 - newgraph[N] representa o grafo vazio com vértices {1,...,N}.
 - addedge[g,x,y] representa o grafo que se obtém acrescentando uma aresta de x para y ao grafo g.
 - deledge[g,x,y] representa o grafo que se obtém retirando a aresta de x para y ao grafo g, caso esta exista (devolvendo g caso contrário).
 - dim[g] devolve o número de vértices de g.
 - graphQ[e] devolve True se e representar um grafo.
 - emptyQ[g] devolve True se g for o grafo vazio.
 - edge[g,x,y] devolve True se houver uma aresta de x para y no grafo g.

Crie pacotes graphs1, graphs2 e graphs3 que implementem este tipo de dados e informação sobre as operações disponíveis sobre as seguintes estruturas.
 - graphs1: pares <N,w> em que N é o número de vértices e w é a lista das arestas do grafo.
 - graphs2: listas de listas {w1,...,wN} em que os elementos de wi são os sucessores directos do vértice i no grafo.
 - graphs3: matrizes quadradas de dimensão N em que m[[i,j]]=1 sse existe uma aresta do vértice i para o vértice j (matrizes de adjacência)

Enriqueça o tipo de dados graphs com as operações a seguir descritas, cuja definição deve ser independente da implementação concreta dos grafos.
 - pathQ: recebe um grafo g e uma sequência de vértices w e verifica se w constitui um caminho (sequência de arestas) em g.
 - addpath: recebe um grafo g e um caminho e acrescenta esse caminho a g (aresta a aresta).
 - sucs: recebe um grafo g e um vértice v e devolve a lista dos sucessores de v (num passo).
  - acessiveis: recebe um grafo g e um vértice v e devolve a lista dos vértices acessíveis a partir de v (em qualquer número de passos).
 - fecho: recebe um grafo g e devolve o grafo cujas arestas são os caminhos de g.
 - custo: recebe um grafo, um caminho e uma função (de custo) sobre pares de naturais e devolve o custo do caminho.
 - completo: recebe um natural n e devolve o grafo completo com vértices 0,...,n.
 - simetrico: recebe um grafo g e devolve o grafo simétrico de g.
 - fechosim: recebe um grafo g e devolve o grafo simétrico que se obtém de g acrescentando a aresta de v2 para v1 sempre que haja uma aresta de v1 para v2 em g.