MAC0328 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.
• O que é cweb. O objetivo é conhecer um sistema de programação conhecido como "Literate Programming" (programas com pretensões de serem um trabalho literário).
• Exemplos de documentos cweb.
• Utilização de cweb com GraphBase.
• O sistema cweb consiste de 2 programas: cweave e ctangle.
• LaTeX - conjunto de macros que facilitam o uso de TeX.
• Estrutura de um documento LaTeX.
• Estrutura de um documento CWEB.
• Tarefas iniciais:
  • instalar cweb  e  LaTeX em seu computador (que a força esteja com você);
  • brincar com os exemplos de documentos cweb visto em sala de aula.
  • inscrever-se na lista de discussão da disciplina.
  • Fazer o exercicio-programa 1.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Receita para criar os arquivos .dvi e bin a partir do documento em CWEB.
• O utilitário Make: regras de dependências; targets; comandos. Um makefile simples consiste de uma seqüência de `regras' com o seguinte formato:

    <target> :  <dependências>
    <TAB>       <comando1>
    <TAB>       <comando2>
             [...]
  

• Um exemplo de makefile.
• Grafos.
• Grafos na natureza.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Grafos no computador: matrizes de adjacência e listas de adjacências.
• Grafos no SGB: os tipos Graph, Vertex e Arc.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Um pouquinho de C: atribuição composta; o cgomando for; vetores; estruturas (struct); Strings; uniões (union); strings; definições de tipos (typedef); alocação dinâmica de memoria (malloc e free).
• Campos util_types da estrutura Graph do SGB.
• Descrição do Stanford GraphBase.
• 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.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• 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.
• 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.
• Grafos, passeios, caminhos, ciclos e ciclos.
• O território X(r) de um vértice r é o conjunto de vértices acessível a partir de r, ou seja, X(r) é o conjunto de todos os vértices v para os quais existe um caminho de r a v.

• PROBLEMA:  Dado um vértice r de um grafo, encontrar o território de r.

• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
  EXERCíCIO :  Quantos grafos com n vértices e m arcos existem?

• PROBLEMA:  Dado um vértice r de um grafo, encontrar o território de r.

• Algoritmo TERRITÓRIO (Grafo g, Vértice r) que recebe um grafo g e um vértice r e devolve o território de r. Veja a implementação da função usando o GraphBase aqui.

• PROBLEMA:  Dado um vértice r de um grafo, encontrar um caminho de r a v para cada vértice v no território de r.

• Predecessor: representação compacta de caminhos.
• A solução é uma pequena variante do Algoritmo TERRITORIO.
• 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/grafos/sgb/exemplos/.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Distâncias em um grafo.
• Algoritmo DISTANCIA(Grafo g, Vértice r) que recebe um grafo g e um vértice r e devolve a distância de r a v, para cada v no território de r.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Note que para comprovar que não existe um passeio de um vértice r a um vértice v, basta aplicar o algoritmo TERRITORIO(g,r) é verificar que não existe arco com ponta inicial VISITADO e ponta final NAOVISTO, ou seja,

              
              for (u = g-> vertices; u < g->vertices + g->n; u++)
                {
                  for (a = u->arcs; a; a = a->next)
                    {
                      if (v->estado == VISITADO && a->tip->estado == NAOVISTO)
                        {
                          fprintf(stderr,"Hmmmm. Há erro na função território");
                        }
                }
               
            

• Sejam g um grafo e X e Y conjuntos de vértices de g. Denotamos por A(X,Y) o conjunto dos arcos com ponta inicial em X e ponta final em Y. Um corte é um conjunto da forma A(X, V-X), onde V é o conjunto de vértices de g.

  Para comprovar que um vértice v é acessível a partir de um vértice r, basta exibir um passeio de r a v.

  Para comprovar que um vértice v não é acessível a partir de um vértice r, basta exibir um conjunto S de vértices tal que: (1) r está em S; (2) v está em V-S; e (3) A(S,V-S) é o conjunto vazio.

• Busca em grafos: busca em largura (breadth first search).
  EXERCíCIO (CLR 23.2.4):  Mostre como o valor v->dist atribuindo a cada vértice v pela busca em largura é independente da ordem dos arcos na lista de adjacência de cada vértice do grafo.
  EXERCíCIO (CLR 23.2.5):  Apresente um grafo e uma árvore com raiz em um vértice r do grafo tal que para cada vértice v do grafo o único caminho de r a v tem comprimento mínimo (aqui, o comprimento de um caminho é o número de arcos no caminho) entretanto essa árvore não pode ser obtida através de uma busca em largura a partir de r, não importanto a ordem dos arcos nas listas de adjacências.
  EXERCíCIO (CLR 23.2.7 e Sedgewick 18.56):  O diâmetro de uma árvore simétrica é o maior comprimento de um caminho na árvore. Escreva uma função

  int diametro (Graph *g){...}

  que recebe uma árvore simétrica g e devolve o diâmetro de g. Qual o consumo de tempo da sua função?
  EXERCíCIO (CLR 23.2.8):  Escreva uma função

  void euler (Graph *g){...}

  que recebe um grafo simétrico e devolve, se existir, um passeio que atravessa cada arco exatamente uma vez. O consumo de tempo da sua função deve ser linear, ou seja, O(n+m).
  Note que aqui ainda temos algumas questões de implemetação, por exemplo, "como representar o passeio?", "como devolver o passeio". Um tal caminho pode não existir?
  EXERCíCIO (Sedgewick 18.54):  O que pode-se dizer sobre a distância de entre dois vértices de uma árvore de busca em largura se nenhum deles é a raiz?
• Busca em grafos: Busca em profundidade (depth first search).
  EXERCíCIO (CLR 23.3.2):  Simule o algoritmo de busca em profundidade para algum grafo. Apresente a numeração pré-ordem e pós-ordem dos vértices do grafo obtida durante a busca.
  EXERCíCIO (CLR 23.3.6):  O professor MacSperto afirmou que se em um grafo existe um caminho de u a v, então u->pré_ordem < v->pré-ordem, onde o campo pré_ordem indica a númeração pré-ordem de um vértice em uma busca em profundidade no grafo. O professor tem razão?
  EXERCíCIO (CLR 23.3.7):  Escreva uma função

  void dfs_classifica (Graph *g) {...}

  que recebe um grafo g e faz busca em profundidade em g imprimindo cada arco junto com o seu tipo: arco da árvore; arco de retorno; arco para frente; ou arco de cruzamento.
  EXERCíCIO (CLR 23.3.8):  Explique como um vértice u de um grafo ser uma árvore em uma floresta de busca em profundidade, mesmo u sendo ponta inicial e ponta final de arcos.

• PROBLEMA (versão café-com-leite):  Dado um grafo, decidir se ele tem ou não tem um ciclo.

  Que objeto um programa pode devolver para comprovar que o grafo tem um ciclo?

  Que objeto um programa pode devolver para comprovar que o grafo não tem um ciclo?

• Trailer dos próximos episódios.

• Melhores momentos da aula passada.

• PROBLEMA (versão elaborada):  Dado um grafo, encontrar um ciclo ou determinar uma númeração topológica dos seus vértices.

• Ciclos e grafos acíclicos.
• Numeração topológica
  EXERCíCIO (CLR 23.4.3):  Escreva uma função

  int tem_ciclo_simetrico (Graph *g) {...}

  que recebe um grafo simétrico g e devolve 1 se g tem um circuito com pelo menos 3 arcos, em caso contrário a função devolve 0. O consumo ad sua função deve ser O(n) (Sim, é isso mesmo, o consumo de tempo deve ser independente de m.)
  EXERCíCIO (CLR 23.4.4):  Prove ou dê um contra-exemplo para a seguinte afirmação:

  Se um grafo não tem ciclos então a númeração topológica produz uma ordenação que minimiza o número de arcos que estão na `contra-mão'.

  EXERCíCIO (CLR 23.4.5):  Uma maneira alternativa de se obter uma númeração topológica de um grafo acíclico é iterar o seguinte:

  "Numere um vértice de grau de entrada zero e depois remova do
  grafo esse vértice e todos os arcos que têm ponta inicial nele."

  Escreva uma função

  void numeracao_topologica (Graph *g) {...}

  que implementa essa idéia para obter um numeração topológica do grafo acíclico g dado. O consumo de tempo da sua função deve ser O(n+m). O que acontece se por engano fornecermos a função um grafo que tem algum ciclo?
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Numeração topológica (continuação).
• Grafos simétricos biparticionáveis e bipartidos.

• PROBLEMA (versão café-com-leite):  Dado um grafo simétrico, decidir se ele é biparticionável.

• Função Boolean bipartido (Graph *g){...} que recebe um grafo simétrico g e devolve TRUE se o g é bipartido e devolve FALSE em caso contrário.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Grafos simétricos biparticionáveis e bipartidos (continuação).

• PROBLEMA (versão elaborada):  Dado um grafo, determinar uma bipartição dos seus vértices ou encontrar um ciclo ímpar.

• Conexidade em grafos simétricos: componentes conexos, arestas de corte e pontes.

• PROBLEMA (versão café-com-leite):  Dado um grafo simétrico, decidir se ele é conexo.

• PROBLEMA (versão elaborada):  Dado um grafo simétrico, determinar os seus componentes conexos.

• PROBLEMA:  Dado um grafo simétrico, determinar suas arestas de corte.

• Função void pontes (Graph *g){...} que recebe um grafo simétrico g e determina as suas arestas de corte.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Conexidade em grafos simétricos (continuação)
  EXERCíCIO :  Considere a seguinte declaração:

  #define no_comp z.I

  Escreva uma função

  void componentes (Graph *g){...}

  que recebe um grafo simétrico grafo g e numera os campos comp de cada vértice de tal forma que

  u->no_comp == v->no_comp

  se e somente se u e v pertencem a um mesmo componente conexo de g. O consumo de tempo da sua função deve ser linear.
  

• PROBLEMA:  Dado um grafo simétrico, determinar as suas arestas de corte.

  EXERCíCIO :  Escreva uma função

  void vertices_de_corte (Graph *g){...}

  que recebe um grafo simétrico grafo g e devolve os vértices de corte de g. O consumo de tempo da sua função deve ser linear.
  
• Conexidade forte.

• PROBLEMA (versão café-com-leite):  Dado um grafo, decidir se ele é fortemente conexo.

• PROBLEMA (versão elaborada):  Dado um grafo determinar os seus componentes fortemente conexos.

• Módulo ROGET_COMPONENTS do SGB encontra componentes fortemente conexos de um grafo.
  
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Passeios e caminhos mínimos.

  Teorema. Sejam r e v vértices de um grafo com comprimentos nos arcos. Suponha que v é acessível a partir de r. Vale uma, e apenas uma, das seguintes afirmação:

  1. existe um passeio mínimo de r a v; ou
  2. existe um passeio de r a v que percorre um ciclo (de comprimento) negativo.

• Árvore de caminhos mínimo.
  

  Teorema. Uma árvore com raiz r é de caminhos mínimos se e somente se
  
  

  u->dist == infinito   ou   u->dist + a->len <= v->dist   para cada arco a=uv de g,

  onde w->dist denota o comprimento do caminho de r a w na árvore.

• PROBLEMA (source-sink shortest path problem): 
  Dado um grafo com comprimento nos arcos e vértices r e s, determinar um passeio mínimo de r a s.

• PROBLEMA (single-source shortest path problem): 
  Dado um grafo com comprimento nos arcos e um vértice r, determinar um passeio mínimo de r a v para cada vértice v do grafo.

• PROBLEMA (all-pairs shortest path problem): 
  Dado um grafo com comprimento nos arcos, determinar um passeio mínimo de r a s, para cada par (r,s) de vértice do grafo.

• Módulo GB_DIJK do SGB resolve o segundo PROBLEMA para grafos com arcos de comprimentos não-negativos.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.

• PROBLEMA : 
  Dado um grafo com comprimentos não-negativos nos arcos e um vértice r, determinar um passeio mínimo de r a v para cada vértice v do grafo.

• Problema do caminho mínimo [Escrito por Shigueo Isotani].
• Algoritmo de Dijkstra [Escrito por Shigueo Isotani].
  EXERCíCIO (CLR 25.2.3):  O professor MacSperto propôs que no algoritmo de Dijkstra inicializemos a fila com prioridades com todos os vértices do grafo (o vértice r com prioridade 0 e os demais com prioridade infinito) e que depois disso poderiamos trocar a condição

                  while (fila_vazia() == FALSE)
                    {
                      Vertex *u = del_min();
                      [...]
                     } 
          

  por

                  while ("a fila tem pelo menos 2 elementos")
                    {
                      Vertex *u = del_min();
                      [...]
                     }
            

  Ele afirma que com esta modificação o algoritmo está correto e executa n-1 iterações em vez de n. O professor tem razão?
  EXERCíCIO (CLR 25.2.4):  Considere um grafo que representa uma rede de comunicações. Nesse grafo cada arco representa um canal de comunicação e o `comprimento' a->len de cara arco a representa a sua confiabilidade (reliability); quanto maior o comprimento, maior é a confiabilidade. A confiabilidade de um caminho é o menor comprimento de um arco no caminho. Um caminho de um vértice u a um vértice v nesse grafo é dito confiável se a sua confiabilidade é máxima entre todos os caminhos de u a v. Escreva uma função

                  void comunica (Graph *g, Vertex *r) {...}
            

  que recebe um grafo g representando uma rede de comunicação e um vértice r e devolve um caminho de confiável de r a v, para cada vértice v do grafo. O consumo de tempo de sua função deve ser o mesmo do algoritmo de Dijkstra (isto é uma dica!).
  EXERCíCIO (CLR 25.2.5):  Escreva um função void dijkstra (Graph *g, Vertex *r) {...} que recebe um grafo g com cada arco tendo como comprimento um número inteiro no intervalo [0..L-1] e um vértice r e devolve um caminho de comprimento mínimo de r a v, para cada vértice v do grafo. O consumo de tempo da sua função deve ser O(nL + m).
  
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Consumo de tempo e correção do algoritmo de Dijkstra
• Implementações de filas com prioridades [Escrito por Shigueo Isotani].
• Estudo experimental do algoritmo de Dijkstra [Escrito por Shigueo Isotani].
  EXERCíCIO :  Encontre um grafo com comprimentos nos arcos (possivelmente negativos) e sem circuitos negativos em que o algoritmo de Dijkstra falha na sua tarefa de encontrar caminhos mínimos a partir de um dado vértice.
  EXERCíCIO :  Encontre um grafo g com comprimentos não-negativos e um vértice r de g em que a função

  void dijkstra(Graph *g, Vertex *r){...}

  realiza cerca de m-n operações enqueue.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.

• PROBLEMA (caminhos mínimos em grafos acíclicos) : 
  Dado um grafo acíclico com comprimentos nos arcos (possivelmente negativos) e um vértice r, determinar um caminho mínimo de r a v para cada vértice v do grafo.

• Solução para o problema dos caminhos mínimos em grafos acíclicos que consome tempo O(n+m). A solução examina os vértices em ordem de númeração topológica (reversa).
  EXERCíCIO (caminhos máximos em grafos acíclicos) :  Dado um grafo acíclico com comprimentos nos arcos (possivelmente negativos) e um vértice r, determinar um caminho máximo de r a v, para cada vértice v do grafo.
• (Escalonamento de tarefas com precedências) Encontrar caminhos máximos em grafos acíclicos tem aplicações em escalonamente de tarefas com precedência. Os arcos do grafo representam tarefas a serem executadas. Os comprimentos dor arcos indicam a duração das tarefas. Se uv e vw tarefas então a tarefa uv deve ser executada antes da tarefa vw. Um caminho de comprimento máximo no grafo, também chamado de caminho crítico, corresponde a quantidade mínima de tempo necessária para realizar todas as tarefas em um número não limitado de máquinas paralelas.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Algoritmo de Bellman-Ford-Moore.
  EXERCíCIO (Lema da dualidade): Demonstre que se uma atribuição de um número val a cada vértice v satisfaz

  u->val + a->len <= v->val   para cada arco a=uv,

  então a distância de um vértice r a um vértice t é pelo menos t->val - r->val.
  EXERCíCIO: Seja g um grafo com comprimentos arbitrários nos arcos. Considere uma atribuição de um número dist a cada vértice v de g. Seja h o grafo formado pelos vértices de g e pelos arcos a=uv de g que satisfazem

                v->dist == u->dist + a->len.
  

  Demonstre que todo caminho de r a v no grafo h tem comprimento v->dist - r->dist. Suponha agora que v->dist é a distância em g de um certo vértice r a v para cada vértice v. O que pode-se concluir disso?
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.

• PROBLEMA (all-pairs shortest path problem): 
  Dado um grafo com comprimento nos arcos, determinar um passeio mínimo de r a s, para cada par (r,s) de vértice do grafo.

• Algoritmos que resolvem o problema em tempo O(n²m), O(m+n⁴) e O(m+n³log(n))
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Algoritmo de Floyd-Warshall: resolve o problema "all-pairs shortest path problem" em tempo O(m+n³)
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Árvores e florestas em grafos simétricos. Árvores geradoras. Árvores geradoras mínimas. Cortes.

• PROBLEMA (da árvore geradora mínima): 
  Dado um grafo com comprimento nos arcos, encontrar uma árvore geradora mínima.

• Algoritmo guloso para o problema da árvore geradora mínima.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Três algoritmos clássicos para o problema da árvore geradora mínima: algoritmo de Boruvka, algoritmo de Kruskal e algoritmo de Prim.
• Módulo MILES_SPAN do SGB tem a implementação de três algoritmos para o problem da árvore geradora mínima.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Implementação do algoritmo de Prim.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.

• PROBLEMA (do par disjunto de caminhos problem): 
  Dado um grafo e dois vértices r e s, encontrar um par disjunto de caminhos de r a s.

• Par disjunto de caminhos: separadores, fluxos, seqüências de aumento.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Implementação de uma solução para o problema do par disjunto de caminhos.
• Fluxos.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Fluxos
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Método dos caminhos de aumento.
• Emparelhamentos
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Trailer dos próximos episódios.

• Melhores momentos da aula passada.
• Trailer dos próximos episódios.