Atualizado: 13/01/2012

R = recebido P = avaliado e publicado

Entrega: 19/09/2012

• Implementar um heap binário e verificar a complexidade das operações experimentalmente.
• Implementar o algoritmo de Dijkstra usando o heap implementado.
• Comparar a complexidade teórica pessimista com a complexidade real. Em particular verificar que a complexidade real respeita o limite teórico.

• O caso de teste é o rede de trânsito de New York, que pode ser baixado na página do DIMACS challenge.
• Para testar: Gerar um número suficiente (>100) de pares aleatórias de vértices origem e destino e medir o tempo de execução e o número de operações “insert”, “deletemin” e “decreasekey”.

• Como o grafo possui 264346 vértices é necessário usar uma representação esparsa. Uma matriz de adjacência, em particular, não serve.

• As implementações do algoritmo de Dijkstra devem aceitar um grafo no formato da DIMACS challenge na entrada padrão (stdin), os índices de dois vértices origem e destino na linha de comando e imprimir o valor do caminho mais curto na saída padrão (stdout). Caso não existo caminho entre os dois vértices imprimir “inf”. Exemplo (em UNIX)

> ./dijkstra 1 2 < NY.gr
803

/**
 * \file gen.cpp
 *   \author Marcus Ritt <mrpritt@inf.ufrgs.br> 
 *   \version $Id: emacs 2872 2009-01-31 01:46:50Z ritt $
 *   \date Time-stamp: <2011-08-24 15:17:49 ritt>
 */
 
#include <iostream>
#include <cassert>
using namespace std;
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace boost;
 
// information stored in vertices
struct VertexInformation {
  unsigned component;
};
 
// information stored in edges
struct EdgeInformation {
  unsigned weight;
};
 
const unsigned maxweight = 1000;
 
// graph is an adjacency list represented by vectors
typedef adjacency_list<vecS, vecS, directedS,VertexInformation,EdgeInformation> Graph;
typedef graph_traits<Graph>::vertex_descriptor Node;
typedef graph_traits <Graph>::edge_descriptor Edge;
 
int main(int argc, char *argv[]) {
  assert(argc == 3);
  unsigned n = atoi(argv[1]);
  double p = atof(argv[2]);
 
  srand48(time(0));
 
  // (1) generate random graph
  Graph g;
 
  for(unsigned i=0; i<n; i++)
    add_vertex(g);
 
  for(unsigned i=0; i<n; i++)
    for(unsigned j=0; j<n; j++)
      if (i != j && drand48() < p) {
        Edge e = add_edge(i,j,g).first;
	g[e].weight = lrand48()%maxweight;
      }
 
 
  // (2) print example path
  unsigned src = lrand48()%num_vertices(g);
  unsigned dst = lrand48()%num_vertices(g);
 
  vector<unsigned> dist(n);
  vector<unsigned> pred(n);
  dijkstra_shortest_paths(g,src,weight_map(get(&EdgeInformation::weight,g)).distance_map(&dist[0]).predecessor_map(&pred[0]));
  cerr << "Distance between " << src+1 << " and " << dst+1 << " is " << dist[dst] << endl;
 
  // (3) print out in DIMACS challenge format
  cout << "p sp " << num_vertices(g) << " " << num_edges(g) << endl;
  graph_traits<Graph>::edge_iterator eb, ee;
  for ( tie(eb, ee)=edges(g); eb != ee; eb++)
    cout << "a " << source(*eb,g)+1 << " " << target(*eb, g)+1 << " " << g[*eb].weight << endl;
}

Entrega: 10/10/2012

• Implementar uma árvore de van Emde Boas e verificar a complexidade das operações experimentalmente.
• Implementar o algoritmo de Dijkstra usando o heap implementado.
• Comparar a complexidade teórica pessimista com a complexidade real. Em particular verificar que a complexidade real respeita o limite teórico.
• Comparar a complexidade com a versão do trabalho 1 usando árvores binárias.

• Redes de trânsito da DIMACS challenge.
• Para testar: Gerar um número suficiente (>100) de pares aleatórias de vértices origem e destino e medir o tempo de execução e o número de operações “insert”, “deletemin” e “decreasekey”.

• Para poder utilizar a árvore de van Emde Boas em grafos com distâncias grandes (que são as prioridades), vocês tem que implementar a versão “esparsa” descrito no livro do Cormen, no exercício 20.1, que substitui o vetor “cluster” (chamado “bottom” nas notas de aula) por uma tabela hash e precisa memoria proporcional ao número de elementos inseridos. (Em C++ vocês podem usar um unordered_map para e tabela hash.)

• Igual ao trabalho 1.

• Igual ao trabalho 1.

Entrega: 02/11/2012

• Implementar o algoritmo de Ford-Fulkerson com a estratégia do “caminho mais gordo” (fattest path) s-t.
• Verificar a complexidade do algoritmo experimentalmente.

• Um gerador de casos de teste em formato DIMACS em C é disponível aqui.
• Documentação:

             To use:  cc washington.c -o gengraph
                      gengraph function arg1 arg2 arg3

             Command line arguments have the following meanings:

                      function:           index of desired graph type
                      arg1, arg2, arg3:   meanings depend on graph type
                                          (briefly listed below: see code
                                           comments for more info)

                 Mesh Graph:          1 rows  cols  maxcapacity
                 Random Level Graph:  2 rows  cols  maxcapacity
                 Random 2-Level Graph:3 rows  cols  maxcapacity
                 Matching Graph:      4 vertices  degree
                 Square Mesh:         5 side  degree  maxcapacity
                 Basic Line:          6 rows  cols  degree
                 Exponential Line:    7 rows  cols  degree
                 Double Exponential   8 rows  cols  degree
                 DinicBadCase:        9 vertices
                      (causes n augmentation phases)
                 GoldBadCase         10 vertices
                 Cheryian            11 dim1 dim2  range
                      (last 2 are bad for goldberg's algorithm)

• As implementações do algoritmo devem aceitar uma instância no formato DIMACS na entrada padrão (stdin) e imprimir o valor do fluxo máximo na saída padrão (stdout).

• O seguinte código determina o fluxo máximo. Para compilar: Usar C++ e Boost.

/**
 * \file maxflow.cpp
 *   \author Marcus Ritt <mrpritt@inf.ufrgs.br> 
 *   \version $Id: emacs 2872 2009-01-31 01:46:50Z ritt $
 *   \date Time-stamp: <2012-12-06 17:10:05 ritt>
 *
 * Read a maximum flow problem in DIMACS format and output the maximum flow.
 *
 */
#include <iostream>
#include <cstring>
using namespace std;
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
using namespace boost;
 
// graph element descriptors
typedef adjacency_list_traits<vecS,vecS,directedS>::vertex_descriptor DiNode;
typedef adjacency_list_traits<vecS,vecS,directedS>::edge_descriptor Edge;
 
// a directed graph with reverse edges
struct VertexInformation {};
typedef unsigned Capacity;
struct EdgeInformation {
  Capacity edge_capacity;
  Capacity edge_residual_capacity;
  Edge reverse_edge;
};
 
typedef adjacency_list<vecS,vecS,directedS,VertexInformation,EdgeInformation> DiGraph;
 
int main(int argc, char *argv[]) {
  // (0) read graph
 
  DiGraph g;
  DiNode s,t;
 
  read_dimacs_max_flow(g,
                       get(&EdgeInformation::edge_capacity,g),
                       get(&EdgeInformation::reverse_edge,g),
                       s, t);
 
  // (1) determine maximum flow
  cout << push_relabel_max_flow(g, s, t,
                                capacity_map(get(&EdgeInformation::edge_capacity,g)).
                                residual_capacity_map(get(&EdgeInformation::edge_residual_capacity,g)).
                                reverse_edge_map(get(&EdgeInformation::reverse_edge,g))) << endl;
}

Entrega: 16/11/2009

• Implementar o algoritmo de Hopcroft/Karp que resolve o problema do emparelhamento máximo em grafos bi-partidos.
• Documentar a implementação, em particular as estruturas de dados para a representação do problema.
• Conduzir testes, que demonstram que a complexidade do algoritmo é O(sqrt(n)m).

• Gerar grafos bi-partidos randômicas com probabilidade de uma aresta 0 ⇐ p ⇐ 1.

• As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado no formato DIMACS na entrada padrão (stdin) e imprimir a cardinalidade de um emparelhamento máximo na saída padrão (stdout).

• Gerador de casos de teste no formato DIMACS + verificação.
• Para compilar: Usar C++ e Boost.

#include <iostream>
#include <cassert>
using namespace std;
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/max_cardinality_matching.hpp>
using namespace boost;
 
// graph element descriptors
typedef adjacency_list_traits<vecS,vecS,undirectedS>::vertex_descriptor Node;
typedef adjacency_list_traits<vecS,vecS,undirectedS>::edge_descriptor Edge;
 
// information stored in vertices
struct VertexInformation {
  Node mate; // partner or graph_traits<Graph>::null_vertex()
};
// information stored in edges
struct EdgeInformation {};
 
// graph is an adjacency list represented by vectors
typedef adjacency_list<vecS,vecS,undirectedS,VertexInformation,EdgeInformation> Graph;
 
int main(int argc, char *argv[]) {
  assert(argc == 3);
  unsigned n = atoi(argv[1]);
  double p = atof(argv[2]);
 
  srand48(time(0));
 
  // (1) generate random bi-partite graph
  Graph g;
 
  for(unsigned i=0; i<2*n; i++)
    add_vertex(g);
 
  for(unsigned i=0; i<n; i++)
    for(unsigned j=n; j<2*n; j++)
      if (drand48() < p) {
        Edge e = add_edge(i,j,g).first;
      }
 
  // (2) get maximum matching
  edmonds_maximum_cardinality_matching(g, get(&VertexInformation::mate,g));
  unsigned card = 0;
  graph_traits<Graph>::vertex_iterator vb, ve;
  for ( tie(vb, ve)=vertices(g); vb != ve; vb++)
    if (g[*vb].mate != graph_traits<Graph>::null_vertex())
      card++;
  //cout << "The cardinality of a maximum matching is " << card/2 << "." << endl;
 
  // (3) print out in DIMACS format
  cout << "c Bi-partite graph" << endl << endl;
  cout << "p edge " << num_vertices(g) << " " << num_edges(g) << endl;
  graph_traits<Graph>::edge_iterator eb, ee;
  for ( tie(eb, ee)=edges(g); eb != ee; eb++)
    cout << "e " << source(*eb,g)+1 << " " << target(*eb, g)+1 << endl;
}

Entrega: 12/12/2012

• Implementar tabelas hash com resolução de colisões com encadeamento, com endereçamento aberto e com cuco hashing.
• Escolher funções hash adequadas.
• Conduzir testes, que determinam a complexidade média (amortizada) das operações insert e lookup para diferentes fatores de ocupação.

• Conjuntos de chaves aleatórias.

• As implementações do algoritmo devem aceitar um arquivo na entrada padrão (stdin) que informa na primeira linha

n m

o número de inserções n e o número de consultas m, seguido por n linhas que contém um número inteiro que representa uma chave a inserir e m linhas que contém um número inteiro que representa uma consulta. O algoritmo deve imprimir na saida padrão (stdout) m linhas que contém o resultado dos m lookups: 0 para uma chave que não pertence a tabela hash, e 1 caso contrário.