Este exercício-programa consite na implementação do algoritmo de Kruskal que recebe um grafo (simétrico) g com comprimentos nos arcos e devolve uma árvore geradora mínima do grafo.
O seu programa C (documento CWEB) deve chamar-se kruskal.c (kruskal.w, respectivamente). O programa deve utilizar a biblioteca do SGB para representação e recuperação um grafo, como descrito a abaixo.
Imagine que cada aresta e=uv de um grafo simétrico tem um comprimento len(uv) (ou len(e)). O comprimento de cada aresta pode ser positivo, negativo ou nulo. Como nosso grafo é simétrico, temos a função comprimento len também é simétrica, ou seja len(uv)=len(vu) para cada aresta uv. Se
e0,e2,e3,...,en-1são as arestas de uma árvore geradora T de g, então seu comprimento len(T) é
len(e1) + len(e2) + ... + len(en-1).Assim, o comprimento de um árvore é a soma dos comprimentos das arestas na árvore. Uma árvore geradora T é dita (de comprimento) mínimo se len(T) <= len(T') para toda árvore geradora T' do grafo.
PROBLEMA (da árvore geradora mínima): Dado um grafo simétrico com comprimentos nas arestas, encontrar uma árvore geradora mínima.
O problema tem solução se e somente e o grafo é conexo.
Eis um algoritmo guloso que resolve o problema da árvore geradora mínima. No início de cada iteração temos um conjunto de arestas azuis que formam uma floresta e um conjunto de arestas que foram pintadas de vermelho. As arestas azuis foram escolhidas para fazer parte da árvore geradora mínima e as vermelhas foram rejeitadas. Cada iteração examina a aresta mais leve dentre as que ainda não foram pintadas e determina se ela deve ser pintada de azul ou de vermelho.
O algoritmo devolve um lista contendo todas as arestas em T.
1
2
3
4
5
6
7
8
9
10
KRUSKAL-VERSÃO-I (Grafo g)
Ordene as arestas de g em ordem não-decrescente de comprimento.
Sejam e1, e2,..., em as arestas de g em ordem de comprimento.
T = vazio;
para i := 1 até m faça
se T+ei não tem circuito então
pinte ei de azul;
T = T+ei;
senão pinte ei de vermelho;
devolva T.
É claro que o algoritmo KRUSKAL-VERSÃO-I produz uma árvore geradora do grafo dado (supondo que o grafo seja conexo). Resta saber se nossa estratégia gulosa garante que a árvore tem comprimento mínimo.
Vamos dar nomes às coisas. No início de cada iteração, T é o conjunto das arestas azuis. O conjunto T é a parte pronta da árvore que o algoritmo está construindo. É preciso mostrar que, no início de cada iteração,
T faz parte de uma árvore geradora mínima.
Eis um esboço da demonstração. Suponha que, no início de uma iteração, T faz parte de uma árvore geradora A de peso mínimo. Durante esta iteração, a aresta uv será acrescentada a T. Se esta nova aresta já está em A não é preciso se preocupar com nada. Mas suponha que esta nova aresta não está em A; que fazer? É preciso mostrar que existe uma aresta xy em A-T tal que
A - xy + uv
é uma árvore geradora de mesmo peso que A. Como encontrar a aresta xy? Resposta: xy é uma aresta que pertence ao único caminho em A que liga u a v. Como xy não foi examinada ainda pelo algoritmo temos que
len(uv) <= len(xy)
porque esse foi o critério de escolha de uv. Logo, A - xy + uv é uma árvore tão mínima quanto T.
Nossa segunda versão do Algoritmo de Kruskal usa uma fila de prioridades de arestas, digamos H, organizada com base no peso w. Cada aresta é representada como um par ordenado de vértices. Os detalhes de implementação da fila ficam por conta da imaginação do leitor, mas tudo se passa como se as arestas estivessem na fila sempre em ordem crescente de w.
1
2
3
4
5
6
7
8
9
10
KRUSKAL-VERSÃO-II (Grafo g)
Monte um heap H com as arestas de g. A chave a ser considerada
é o comprimento da aresta e a aresta mais leve deve ficar na primeira posição.
T = vazio;
n_azuis = 0;
enquanto (n_azuis < n-1 e (e = RETIRE-MÍNIMO(H) |= NULL)) faça
se T+e não tem circuito então
n_azuais = n_azuais+1;
T = T+e;
se (n_azuis < n -1) então
g não é conexo;
senão devolva T.
No início de cada iteração, H contém todas as arestas ainda não examinadas (arestas que não foram pintadas).
O sub-algoritmo RETIRE-MÍNIMO retira de H uma aresta uv tal que len(uv) é mínimo. O sub-algoritmo INSIRA-NA-FILA simplesmente insere uma nova aresta na fila.
Se o teste "T+e não tem circuito" for bem implementado o consumo de tempo dessa versão será O(m log(m)), onde m é o número de arestas do grafo.
Talvez você queira dar uma olhada na implementação do algoritmo de Kruskal feita pelo Knuth. Ela está no arquivo miles_span.w e a função se chama krusk. Tome cuidado, porém, pois a função krusk não deve funcionar no nosso caso. A função assume que o grafo de entrada tem uma característica que não vale no nosso caso. Alguém sabe me informar o qual é essa característica?
Acho que não dá para fazer o heap sem alocar memória para um vetor de apontadores para as arestas. Faça essa alocação de forma dinâmica para não impor restrições desnecessárias ao número de arestas do grafo.
O heap deve ser construído em tempo linear (O(m)), através do mesmo procedimento que cria o heap do Heapsort. Ou seja, o heap não deve ser criado através de seqüências de inserções! (Seqüência de inserções gastaria tempo O(m log(m)).)
Conforme a árvore T vai sendo montada, conjuntos de vértices formam uma floresta de árvores azuis (cada árvore azul é um subgrafo conexo maximal de T).
A cada momento, vamos representar cada árvores azul pelo conjunto de vértices da árvores. Quando uma nova aresta é inserida em T (é pintada de azul), devemos fazer a união dos conjuntos de vértices contendo os extremos das arestas. Caso a aresta examinada tem as duas pontas num mesmo conjunto, ela cria circuito e deve ser descartada (pintada de vermelho).
Uma estrutura de dados apropriada para representarmos conjuntos disjuntos é a estrutura Union-Find, que muitos podem ter visto em MAC0323 Estruturas de Dados ou neste semestre em MAC0338 Análise de Algoritmos. Inicialmente cada vértice é um conjunto diferente
make_set(x)
x->pai = x ;
x->rank = 0;
Quando as arestas são inseridas, os conjuntos são reorganizados e os ranks alterados.
Para se encontrar o representante (ou nome) de um conjunto, usamos o find_set
find_set(x)
se (x != x->pai)
então x->pai = find_set(x->pai)
devolva (x->pai);
Para fazermos a união dos conjuntos, usamos a função union que faz a união "balanceada". A função union supõe que x e y são representantes de conjuntos distintos.
union(x,y)
se (x->rank > y->rank)
então y->pai = x
senão
x->pai = y;
se (x->rank == y->rank)
então y->rank = y->rank + 1;
Você deve usar a estrutura de dados Union-Find. Por via das dúvidas, deixarei na Pasta ?? do xerox, cópia de umas páginas que descrevem a estrutura (que está praticamente descrita acima).
A implementação do Union-Find deve ser feita utilizando algum dos campos utilitários dos vértices. Para isto sugiro (estou apenas sugerindo...) que cada vértices tenha os seguintes campos.
#define pai u.V /* ou ... o campo você achar mais conveniente */
v->pai é um apontador para o vértice pai de v na árvore que representa o conjunto (vértices da árvore azul) contendo v.
#define rank v.I /* ou ... o campo você achar conveniente */
v->rank é o `rank' do vértice v.
Para representar a árvore crie uma lista ligada das arestas. A única memória extra necessária é um apontador para o início da lista. Para os outros apontadores, podemos usar um dos campos util das arestas, por exemplo:
#define prox a.A
Assim, se a é um arco (aresta) na árvore T, então a->prox é o próximo arco (aresta) na lista de arestas de T.
Finalmente, eis a versão mais eficiente e sofisticada do Algoritmo de Kruskal. Ela usa um heap para armazenar a fila com prioridades e a estrutura Union-Find para manter os conjuntos de vértices das árvores azuis.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
KRUSKAL-VERSÃO-III (Grafo g)
Monte um heap H com as arestas de G. A chave a ser considerada
é o peso da aresta e a aresta mais leve deve ficar na primeira posição.
T = vazio;
n_azuis = 0;
Para cada vértice v faça make_set(v);
enquanto (n_azuis < n-1 e (e = RETIRE-MÍNIMO(H) |= NULL)) faça
Sejam u e v os estremos de e;
x = find_set(u);
y = find_set(v);
se (x != y) /* T+e não tem circuito então */
n_azuais = n_azuais+1;
T = T + e;
union(x,y);
se (n_azuis < n -1) então
G não é conexo;
senão devolva T.
Neste exercício-programa você implementará a versão III do Algoritmo de Kruskal que encontra um árvore geradora mínima de um grafo simétrico conexo com comprimentos nas arestas.
O programa deve receber como entrada, na linha de comando, o nome de um arquivo .gb contendo a representação de um grafo simétrico com comprimentos nas suas arestas:
Se o usuário usar a opção -v, o programa deve listar todas as arestas que fazem parte da árvore gerado mínima encontrada. Exemplo:
O seu programa deve prever pelo menos os seguintes casos, informando o fato ao usuário com uma mensagem conveniente:
Não deixe de incluir algumas funções de auto-teste em seu programa: Se o usuário digitar a opção "-teste", essas funções farão testes em vários pontos do programa. Por exemplo, verificarão se uma suposta arvore é de fato uma árvore, se uma suposta árvore mínima é de fato uma árvore mínima, etc Se a opção "-teste" estiver ativa, é uma boa idéia exibir a seqüência de vértices sendo examinados.
Sugestões são bem-vindas!
A saída do seu programa deve ser enviada para a saída padrão (stdout).
Copiado do arquivo miles_span.w:
Minimum spanning trees.
A classic paper by R. L. Graham and Pavol Hell about the history of algorithms to find the minimum-length spanning tree of a graph [Annals of the History of Computing 7 (1985), 43--57] describes three main approaches to that problem. Algorithm 1, ``two nearest fragments,'' repeatedly adds a shortest edge that joins two hitherto unconnected fragments of the graph; this algorithm was first published by J.~B. Kruskal in 1956. Algorithm~2, ``nearest neighbor,'' repeatedly adds a shortest edge that joins a particular fragment to a vertex not in that fragment; this algorithm was first published by V. Jarník in 1930. Algorithm~3, ``all nearest fragments,'' repeatedly adds to each existing fragment the shortest edge that joins it to another fragment; this method, seemingly the most sophisticated in concept, also turns out to be the oldest, being first published by Otakar Boruvka in 1926.
[...]
Os dados de distâncias rodoviárias foram obtidos, com pequenas alterações, do Guia 4-Rodas Brasil de 1998. Os demais dados foram obtidos do IBGE.
#define latitude u.I #define longitude v.I #define altitude w.I #define população x.I #define homens y.I #define outro_nome z.S
O outro nome é um apelido que porventura a cidade tenha.
Essas informações podem ser ignoradas, e os campos serem usados
para outras finalidades.
Copiado do arquivo gb_miles.w:
The subroutine call
The constructed graph will be ``complete''---that is, it will have edges between every pair of vertices---unless special values are given to the parameters max_distance or max_degree. If max_distance!=0, edges with more than max_distance miles will not appear; if max_degree!=0, each vertex will be limited to at most max_degree of its shortest edges.
Um exemplo de uso da função miles pode ser encontrado no módulo MILES_SPAN (miles_span.w), como mostrado abaixo.
#include "gb_miles.h" /* the |miles| routine */
[...]
main(argc,argv)
int argc; /* the number of command-line arguments */
char *argv[]; /* an array of strings containing those arguments */
{@+unsigned long n=100; /* the desired number of vertices */
unsigned long n_weight=0; /* the |north_weight| parameter */
unsigned long w_weight=0; /* the |west_weight| parameter */
unsigned long p_weight=0; /* the |pop_weight| parameter */
unsigned long d=10; /* the |max_degree| parameter */
long s=0; /* the random number seed */
unsigned long r=1; /* the number of repetitions */
char *file_name=NULL; /* external graph to be restored */
@;
while (r--) {
if (file_name) g=restore_graph(file_name);
else g=miles(n,n_weight,w_weight,p_weight,0L,d,s);
if (g==NULL || g->n<=1) {
fprintf(stderr,"Sorry, can't create the graph! (error code %ld)\n",
panic_code); /* panic_code is set nonzero if graph
* generator panics.
* panic_code indica o problema que ocorreu,
* veja gb_graph.w
*/
return -1; /* error code 0 means the graph is too small */
}
Copiado do arquivo módulo GB_RAND (gb_rand.w):
This GraphBase module provides two external subroutines called random_graph and random_bigraph, which generate graphs in which the arcs or edges have been selected ``at random.'' A third subroutine, random_lengths, randomizes the lengths of the arcs of a given graph. The performance of algorithms on such graphs can fruitfully be compared to their performance on the nonrandom graphs generated by other GraphBase routines.[...]
The procedure
If dist_from or dist_to are NULL, the probability distribution is uniform over vertices; otherwise the dist parameter points to an array of n nonnegative integers that sum to 230, specifying the respective probabilities (times 230) that each given vertex will appear as the source or destination of the random arcs.
[...]
Um comentário sobre comentários: ``Antes de cada função [e bloco] diga o que a função [e bloco] faz. Procure responder as perguntas que um usuário faria: que dados essa função recebe? que suposições faz sobre esses dados? que resultados devolve? Não perca tempo tentando dizer como a função faz o que ela faz.''(Paulo Feofiloff) Se o tamanho de seus blocos é razoavelmente pequeno, como deve ser, o conselho é extremamente útil.
Mudando de assunto, gostaria de destacar que o uso do WEB, segundo o seu criador D. Knuth, tem as seguintes finalidades de
Observação. Cópiei o comentário acima da página de grafos do prof. José Augusto
cweave, latex,
ctangle (se você fez em CWEB) e gcc.
meu_prompt> make kruskal.texgere o documento kruskal.tex correspondente ao seu EP5,
meu_prompt> make kruskal.dviproduza o Make.dvi correspondente ao seu EP5,
meu_prompt> make kruskal.ccrie o arquivo kruskal.c correspondente ao seu EP5, e
meu_prompt> make kruskalproduza o executável de nome kruskal correspondente ao seu EP5.
meu_prompt>tar -xvf ep5.tarcrie um diretório que tenha o seu login na rede Linux como nome. Neste diretório devem estar todos os arquivos do seu EP5, inclusive o Makefile que você usou. Se você achar necessários coloque junto um arquivo 00-leia-me, onde você descreve algo que achar necessário: como limitações e bugs no seu programa.