DAA 2021/2022 (CC2001) - DCC/FCUP

Aula Prática #12 - Fluxos Máximos
(semana de 06/06 a 10/06)

Exercícios para submissão

Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre, os exercícios a submeter desta aula são:

• [DAA 041] Corridas no parque (peso 50%) (exercício do guião principal)
• [DAA 042] Clube de livros (peso 50%) (exercício do guião principal)

Prazo de submissão: 12 de Junho (submeter no Mooshak de DAA)

Não se esqueçam que qualquer ajuda que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem.
Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota. Relebre que cada aula vale 10% da nota desta componente.
Para um problema contar tem acertar todos os testes. Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.

Conteúdos das teóricas

Nesta aula iremos abordar conceitos de Fluxos Máximos em grafos. Será por isso conveniente ver o que foi falado nas teóricas:

• Slides (capítulo "10 - Grafos: Fluxos Máximos")
• Vídeos: (vídeo #23)

Exercício 1) Introdução ao algoritmo de Edmonds-Karp

Comece por fazer download do código exemplo do algoritmo de Edmonds-Karp (que funciona em tempo \(\mathcal{O}(|V| \times |E|^2)\) [ver slides 5 a 21]:

• C++: edmondskarp.cpp (versão original feita em C++)
• C: edmondskarp_c.cpp (adaptação para C/C++ "quase como em C, sem usar classes)
• Java: edmondskarp.java (adaptação para Java)

Se costuma usar C, a sugestão é que use a última versão, que é essencialmente C com excepção do vector e queue, que já estão implementadas em C++ usando STL. A ideia é que progressivamente possa ir começando a usar as estruturas de dados úteis que o C++ tem e o C não, continuando no essencial a programar em C "normal" e usando C++ apenas para essas estruturas de dados.

1. Compile e execute o código usando como input o ficheiro edmondskarp.txt, que corresponde ao grafo da figura seguinte (o mesmo que é usado na explicação de fluxo máximo nos slides):
   
    
   
2. Procure compreender todos as linhas do código dado e procure também seguir a execução, verificando se percebe os caminhos de aumento que vão sendo imprimidos, que no final dão origem a um fluxo total de 23 (12+4+7)
    
   
    
   

Exercício 2) Resolvendo um problema usando fluxo máximo (edge disjoint paths)

Usando como base o código dado no exercício anterior, implemente e submeta uma solução para o problema [DAA 041] Corridas no parque.

Dicas:

• Para encontrar o máximo número de caminhos entre dois pontos tal que uma mesma aresta não possa aparecer em dois caminhos diferentes (edge disjoint paths) basta pensar no grafo do parque com uma rede de fluxo onde todas as arestas têm capacidade 1. Desse modo o fluxo máximo dá-nos o número máximo de caminhos que não usam as mesmas arestas (pois a sua capacidade apenas "deixa passar" um caminho) [ver slide 24].
• Tendo em conta os limites baixos no número de nós e de arestas, pode usar (quase) qualquer algoritmo, mas aqui sugerimos o Edmonds-Karp (com BFS), para o qual já tem uma implementação base. Tenha cuidado com o facto do grafo neste problema ser não dirigido (ao passo que a implementação base assume um grafo dirigido - o que tem de mudar?).

Exercício 2) Resolvendo um problema usando fluxo máximo (maximum bipartite matching

Implemente e submeta uma solução para o problema [DAA 042] Clube de livros.

Dicas:

• Podemos representar as declarações de interesse por um grafo bipartido onde de um lado estão os membros do clube e do outro lado estão os livros.
• Criamos uma super-origem e um super-destino [ver slides 25 a 27]fluxo máximo.
• Se o fluxo máximo for igual ao número de membros, então temos um emparelhamento perfeito e a resposta é YES. Caso contrário a resposta é NO.
• Sugerimos usar como base a implementação dada, sendo que o problema passa quase a ser unicamente criar o grafo que representa o problema:
   
  
   
  

Material complementar

Vamos ficar pelos 42 problemas para submissão no Mooshak :) [e por isso nesta aula não existem problemas complementares]

Se quiser complementar o seu conhecimento sobre fluxos máximos com material que não foi falado na teórica (nem será alvo de avaliação no teste) pode espreitar por exemplo:

• O algoritmo de Dinic, que corre em \(\mathcal{O}(|E| \times |V|^2)\), o que é melhor que \(\mathcal{O}(|V| \times |E|^2)\) do Edmonds-Karp (ver exemplo implementação.
• O algoritmo de Hopcraft-Karp que funciona para o caso muito específico da maximum bipartite matching, onde os pesos são 1, e por isso corre em \(\mathcal{O}(|E|\sqrt{|V|})\).
• A relação entre um corte mínimo (partição do grafo em duas partições disconexas usando arestas de peso mínimo) e o fluxo máximo: max-flow min-cut theorem

Isto serve também para relembrar que apesar de termos coberto muito material nesta unidade curricular, ainda há muitas coisas para aprenderem!

Exercício de Desafio

O exercício de desafio desta semana é um pouco diferente e com um espírito mais natalício (originalmente esta UC era dada no 1º semestre). O objectivo é imprimir uma árvore de natal usando o menor programa possível!. A sua pontuação é igual ao tamanho do seu programa (quantidade de bytes): quanto menor melhor!

O prémio para as 5 melhores soluções no final do dia 31 de Julho 11 de Setembro de 2022 é um lanche no Alicantina pago por mim, Pedro Ribeiro (mais companhia para pequena conversa sobre algoritmos), a fazer no início do 1º semestre de 22/23.

Como prémio (e desafio) adicional, o primeiro aluno a conseguir melhorar a minha solução lá submetida (212 bytes) recebe um almoço pago por mim (uma francesinha no Capa Negra II).

Este desafio está disponível para submissão no Mooshak (têm de usar C, C++ ou Java):