MAC 328 Algoritmos em Grafos

"The philosophy behind CWEB is that programmers who want to provide
the best possible documentation for their programs need two things simultaneously:
a language like TEX for formatting, and a language like C for programming."

D.E. Knuth and S. Levy
"The CWEB System of Structured Documentation".

• Descrição da disciplina.
• Tarefas iniciais:
  • Conhecer CWEB.
  • Utilização de CWEB com GraphBase.
  O objetivo é conhecer um sistema de programação conhecido como "Literate Programming" (programas com pretensões de serem um trabalho literário).
• O sistema CWEB consiste de 2 programas: CWEAVE e CTANGLE.
• L^ATEX - conjunto de macros que facilitam o uso de TEX.
• Estrutura de um documento L^ATEX.
• Estrutura de um documento CWEB.
• Trailer dos próximos episódios.

• Resumo da aula anterior.
• Receita para criar os arquivos .dvi e bin a partir do documento em CWEB.
• O utilitário Make: regras de dependências; targets; comandos.
• Grafos não-dirigidos ou grafos simétricos (sem flechas) e grafos dirigidos (com flechas). Exemplos de grafos.
• Trailer dos próximos episódios.

• Resumo da aula anterior.
• Exemplos de grafos simétricos e dirigidos.
• Representação de grafos: matriz de adjacência; lista de adjacência e matriz de incidência.
• Representação de grafos no SGB: os tipos Graph, Vertex e Arc.
• Trailer dos próximos episódios.

• Resumo da aula anterior.
• Um pouquinho de C: atribuição composta; o comando for; vetores; estruturas (struct); Strings; uniões (union); strings; definições de tipos (typedef); alocação dinâmica de memoria (malloc e free).
• O campo util_types da estrutura Graph do SGB.
• Trailer dos próximos episódios.

• Resumo da aula anterior.
• Uso dos campos util das estruturas Vertex e Arc. Os campos util> usualmente recebem nomes significativos através de macros, por exemplo
  #define source a.V.
• Descrição do Stanford GraphBase.
• O módulo GB_GRAPH do SGB.
  #include < gb_graph.h >
  Este módulo inclui rotinas para alocar e armazenar novos grafos, novos arcos, novas strings e novas struturas de dados de todos os tipos:
  • Graph *gb_new_graph(long n).
    Um novo grafo é criado chamando-se gb_new_graph(n), que retorna um pointer para um registro do tipo Graph com n vértices e nenhum arco.
  • void gb_new_arc(Vertex *u, Vertex *v, long len).
    Cria um novo arco de comprimento len de u até v. O arco passa a ser parte do grafo "corrente". O novo arco será apontado por u->arcs.
  • void gb_new_edge(Vertex *u, Vertex *v, long len).
    Similar a gb_new_arc. Registros para dois arcos são criados, um de u a v e outro de v a u. Os dois arcos aparecem em posições consecutivas na memória: v->arcs é u->arcs + 1 quando u < v .
  • char *gb_save_string (char *s).
    Faz uma cópia de s para ser usada no grafo "corrente".
  • void gb_recycle (Graph *g).
    Remove o grafo apontado por g da memória.
• O módulo GB_SAVE do SGB.
  #include < gb_save.h >
  Este módulo contém código para converter grafos da sua representação interna para uma representação simbólica e vice-versa:
  • long save_graph (Graph *g, char *filename).
    Converte o grafo apontado por g para formato texto e salva o grafo no arquivo de nome filename.
  • Graph *restore_graph (char *filename).
    Converte um grafo guardado no arquivo filename do formato texto para a representação interna dp SGB.
• Trailer dos próximos episódios.

• Resumo da aula anterior.
• A página Grafos, preparada pelo Prof. Paulo Feofiloff para a disciplina MAC 338, contém conceitos de grafos, caminhos etc.
• Exemplo de documento CWEB usando o SGB, preparado pelo Prof. José Augusto para a disciplina MAC 328, para criar, salvar e recuperar um pequeno grafo. Uma cópia do exemplo se encontra em
  http://www.ime.usp.br/~coelho/mac328/sgb/exemplos/.
• O território X(s) de um vértice s é o conjunto de vértices acessível a partir de s, ou seja, X(s) é o conjunto de todos os vértices v para os quais existe um caminho de s até v.
• Algoritmo TERRITÓRIO(Grafo D, Vértice s) que: dados um grafo D e um vértice s de D; devolve: o território de s.
• Trailer dos próximos episódios.

• Resumo da aula anterior.
• Distâncias em um grafo.
• Algoritmo DISTÂNCIA(Grafo D, Vértice s) que: dados um grafo D e um vértice s de D; devolve: a distância de s a todos os vértices de D.
• Trailer dos próximos episódios.