MAC 328 Algoritmos em Grafos

Este projeto foi elaborado pelo professor Francisco Reverbel

Segundo Exercício-Programa. Make: Episode I

A long time ago in a galaxy far,
far away ...

Avisos

1. O programa pode ser feito em grupos de uma ou duas pessoas.
2. O valor deste EP � 20 pontos.

Objetivos

1. Manipulação da representação de um grafo através de listas de adjacências.
2. Treino no uso de algumas funções básicas do Stanford GraphBase.
3. Familiarização com o processo de compilação usando a biblioteca libgb.
   (Veja o Makefile em http://www.ime.usp.br/~coelho/grafos/sgb/exemplos/.)

Descrição

Introdução

Neste exercício-programa você fará um documento em CWEB que deverá charmar-se Make.w. Este documento utilizará a biblioteca do SGB para a criação e recuperação de um `grafo de dependências', como descreveremos a seguir.

O seu programa deverá chamar-se Make. O `M' maiúsculo em Make é para diferenciarmos o se programa do make do UNIX. Da mesma maneira que o utilitário make, o seu programa, ao ser chamado na linha de comando sem opção alguma, lerá um arquivo de nome MakeFile contendo informações de dependências e comandos para reconstrução (rebuilding commands). O `F' maiúsculo em MakeFile é para não confundirmos a entrada do Make com o arquivo Makefile que você muito provavelmente estará utilizado.

Formato de um MakeFile

  target ... :  dependências ...
         comando1
         comando2
         ...

Um target é usualmente o nome de um arquivo que é gerado por um programa; exemplos de targets são arquivos executáveis (bin ou .o). Um target também pode ser o nome de uma ação, tal como `clean'.

Uma dependência é um arquivo que é usado para criar o target. Um target pode depender de vários arquivos.

Um comando é uma ação que Make pode mandar que seja executada. Um regra pode ter mais que um comando, cada um em uma linha. Nota: deve existir um caractere TAB ('\t') no início de cada linha.

Exemplo de um MakeFile

A seguir está um exemplo típico de um arquivo MakeFile que seu programa Make deverá ser capaz de tratar (os números das linhas foram colocada apenas para efeito de referência, eles não farão parte do MakeFile):

1   meuprog: meuprog.o  fila.o  etc.o
2         gcc meuprog.o fila.o etc.o -o meuprog 
3
4   meuprog.o:  meuprog.c  minhasdefs.h  fila.h   etc.h
5         gcc -c meuprog.c
6
7   fila.o:  fila.c minhasdefs.h  fila.h
8         gcc -c fila.c
9
10  etc.o: etc.c  minhasdefs.h  etc.h
11        gcc -c etc.c
12
13  clean:
14        rm -f meuprog.o fila.o etc.o

• Linhas 1, 4, 7, 10 e 13 fornecem informações de dependência. Em uma linha de dependência o nome de um target aparece primeiro, seguido por dois pontos (`:'). Depois dos dois pontos segue-se uma lista (possivelmente vazia) de arquivos dos quais o target depende. A Linha 7, por exemplo, diz que o target file fila.o depende dos arquivos fila.c, minhasdefs.h e fila.h.
• Uma linha de dependência é seguida por uma ou mais linhas com comandos (rebuild commands) que criam ou atualizam o target especificado na linha de dependência. O primeiro caractere de um linha contendo um comando deve ser um TAB (`\t'); uma, aparentemente identica, seq��ncia de caracteres não por ser usada ao invés do TAB. Linhas 2, 5, 8, 11 e 14 cotém comandos. A Linha 8, por exemplo, diz que o comando
  

  gcc -c fila.c

  deverá ser executado para reconstruir o target fila.o a partir dos arquivos fila.c, minhasdefs.h e fila.h. Neste particular MakeFile, cada linha de dependência é seguida por apenas uma linha de comando. Seu programa, entretanto, deverá ser capaz de tratar o caso em que várias linhas de comando seguem uma linha de dependência.
• As linhas em branco (linhas 3, 6, 9 e 12) são ignoradas. Estas linhas podem estar presente apenas para facilitar a legibilidade do MakeFile, mas elas não são necessária. Um Makefile similar sem linhas em branco também devem ser aceitas pelo seu programa Make.

Grafo de dependências

As linhas de dependências em um MakeFile (ou Makefile) definem um grafo de dependências, um grafo dirigido cujos vértices correspondem a targets e arquivos de dependência, e cujos arcos representam a dependência entre estes targets e arquivos. Sempre que um target f₁ depende de um arquivo f₂ o correspondente grafo de dependências deve conter um arco do vértice de nome f₁ até o vértice de nome f₂. A Linha 7 do nosso exemplo de MakeFile acima diz que respectivo grafo de dependências contém arcos do vértice de nome fila.o até o vértice de nome fila.c, até o vértice de nome minhasdefs.h, e até o vértice de nome fila.h .

Um ciclo em um grafo é caminho fechado. Mais precisamente, um ciclo é uma seqüência de vértices (v₁,v₂,...,v_k) tal que

existe um arco de v_i até v_i+1 (i=1,...,k-1) e um arco de v_k até v₁.

Um grafo de depêndencias não deve conter um ciclos. Isto, entretanto, não é obstáculo para que um grafo de dependência correspondente a um arquivo MakeFile tenha circuitos. Isto apenas significa que o Make deverá ser capaz de verificar a presença ou não de circlos no grafo de dependências. A existência de ciclos deverá ser considerada pelo Make como um erro na especificação do MakeFile. Detecção de ciclos será o objeto de estudo do Exercício-Programa 3. (Por enquanto não se preocupe com isto.)

O que Make deverá fazer

• Make. Chamado desta maneira Make dever� procurar no diret�rio corrente um arquivo de nome MakeFile e processa-lo da seguinte maneira:
  1. (Contrói o grafo de dependências) Make lê o arquivo MakeFile, que tem o formato descrito acima, e contrói o correspondente grafo de dependências usando o módulo GB_GRAPH do SGB.
  2. (Salva o grafo) Após a criação do grafo de dependências na representação interna do SGB, Make converte este grafo para a representação simbólica (texto) do SGB e salva está representação no diretório corrente em um arquivo de nome MakeFile.gb. Tudo isto corresponde a uma simples chamada da rotina gb_save do módulo GB_SAVE do SGB.
• Make -g. Chamado desta maneira Make deverá procura no diretório corrente um arquivo de no MakeFile.gb e processa-lo da seguinte maneira:
  1. (Restaura o grafo de dependências) Make lê o arquivo Makefile.gb, que contém um grafo de dependências no formato simbólico (texto) do SGB, e converte este grafo para a representação interna do SGB. Tudo isto corresponde a uma simples chamada da rotina restore_graph do módulo GB_SAVE do SGB.
  2. (Recria o MakeFile). Make percorre o grafo de dependências e produz e envia para a saída padrão (stdout) o MakeFile que gerou este grafo de dependências. Ou seja, ao percorrer o grafo de dependências Make envia para a saída padrão algo parecido com o exemplo de MakeFile acima, possivelmente sem as linhas em branco ou trocando alguma das regras de lugar (isto depende de como Make gerou o grafo.

Representação interna de um grafo de dependências

http://www.ime.usp.br/~coelho/grafos/sgb/exemplos/

Um vértice v (registro ou estrutura do tipo Vertex) deverá conter:

• v->name será um apontador para um string de caracteres que contém o nome do vértice. Exemplos de nomes de vértices do grafo de dependências correspondente ao Makefile do exemplo são "meuprog.c", "fila.h" e "clean".
• v->arcs é um apontador para um registro do tipo Arc. Este é o apontador para o início da lista ligada de arcos que saem do vértice v (um arco para cada arquivo do qual v->name depende).
• v->commands é um apontador para um string de caracteres. Este string deverá conter todos os comandos associados ao target de nome v->name, uma após o outro, separados por um '\n'.

  O nome commands não é um nome padrão de um dos campos de um registro do tipo Vertex. Use a seguinte macro do C:

  #define commands y.S

  Assim, v->commands é um nome mnemônico para v->y.S.

Fazendo a busca por um vértice

• void hash_in (Vetex *v) coloca o nome do vértice v (v->name) em uma tabela de hash do "grafo corrente";
• Vertex *hash_out(char *s) encontra o vértice de nome s, se este estiver presente na tabela de hash do "grafo corrente". Se o vértice não for encontrado a função devolve NULL;
• void hash_setup(Graph *g) prepara uma tabela de hash para todos os vértices do grafo g;
• Vertex *hash_out(char *s, Graph *g) procura um vértice de nome s na tabela de hash do grafo g.

Important: Utility fields u and v of each vertex are reserved for use by the search routine when hashing is active. You can crash the system if you try to fool around with these values yourself, or if you use any subroutines that change those fields. The first two characters in the current graph's util_types field should be VV if the hash table information is to be saved by GB_SAVE.

Warning: Users of this hash scheme must preserve the number of vertices g->n in the current graph g. If g->n is changed, the hash table will be worthless, unless hash_setup is used to rehash everything.

Caution: This hash coding scheme is system-dependent, because it uses the system's character codes. If you create a graph on a machine with ASCII code and save it with GB_SAVE, and if you subsequently ship the resulting text file to some friend whose machine does not use ASCII code, your friend will have to rebuild the hash structure with hash_setup before being able to use hash_lookup successfully.

Entrega e Prazos

1. Como sempre, somente entregue seu programa se o mesmo não apresentar erros de compilação. O processo de compilação aqui deve ser entendido como todo o processo cweave, latex, ctangle e cc.
2. A entrega do programa consiste da entrega eletrônica do programa E da entrega de uma impressão do arquivo dvi correspondente (huuummm, vocês têm onde imprimir isto?).
   • Entrega eletrônica: o seu programa.w deve ser entregue por e-mail até dia 14/9/99, inclusive. Sobre a entrega eletrônica veja http://panda.ime.usp.br/eet/.
   • Entrega da impressão: a saída produzida pelo arquivo dvi deverá ser entregue na aula do dia 16/9.