Entrega: 17/08/2015

• Implementar um heap n-ário.
• Implementar o algoritmo de Dijkstra usando o heap implementado.
• Determinar o valor de n tal que o algoritmo de Dijkstra com um heap n-ário tem o melhor desempenho.
• Comparar a complexidade teórica pessimista com a complexidade real. Em particular verificar que a complexidade real respeita o limite teórico.
• Avaliar o escalonamento do algoritmo Dijkstra.

• Verificação da complexidade do Dijkstra: usar o gerador de casos de testes abaixo.
• Verificação do escalonamento: o caso de teste é o rede de trânsito de New York e dos EUA (distance), que pode ser baixado na página do DIMACS challenge.
• Para testar em geral: Gerar um número suficiente (>30) 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;
}

void read_dimacs(std::istream& in, unsigned& n, unsigned& m, MyGraph& a) {
  std::string line="", dummy;
  while (line.substr(0,4) != "p sp")
    getline(in,line);
 
  // (1) get nodes and edges
  std::stringstream linestr;
  linestr.str(line);
  linestr >> dummy >> dummy >> n >> m;
  a.resize(n);
  unsigned i=0;
  while (i<m) {
    getline(in,line);
    if (line.substr(0,2) == "a ") {
      std::stringstream arc(line);
      unsigned u,v,w;
      char ac;
      arc >> ac >> u >> v >> w;
      // processar arco (u,v) com peso w
      i++;
    }
  }
}

Entrega: 31/08/2015

• Implementar a estrutura de dados “union-find” com balanceamento (UF1) e com balanceamento e compressão de caminhos (UF2).
• Determinar a complexidade real (em comprimento de caminho) de uma sequência de operações e apresentar um histograma e a complexidade amortizada.
• Conduzir um experimento com grafos randômicos usando UF para análise
  • Modificar o UF para poder determinar em O(1) o número de componentes conexos, e o tamanho de cada componente; caso tem k componentes deve ser possível determinar a tamanho de cada uma em tempo total O(k)
  • Conduzir experimentos como segue: criar um grafo vazio com n vertices, e inserir n/2 arestas aleatórias, e depois determinar o tamanho da componente maior
  • Repetir este experimento 30 vezes para cada n, e para n=2^i, i=1,…,20.
  • Apresentar um boxplot com o tamanho da maior componente em função de n, e uma regressão polinomial do tamanho da maior componente em função de n. Conclusão?

• Para o primeiro parte: gerar sequências randômicas de operações.
• Para o segundo parte: usar um gerador de casos de testes abaixo.

• Fornecer uma implementação do UF que recebe na entrada padrão (stdin) uma lista de operações “make-set n”; “union n1 n2” e “find n” e imprime na saída padrão (stdout) os resultados das operações find.

Entrega: 21/09/2015

• Implementar o algoritmo de Ford-Fulkerson (estratégia “caminho arbitrário” s-t) e Edmonds-Karp (estratégia do “caminho mais curto” s-t).
• Verificar a complexidade dos dois algoritmos experimentalmente e comparar com a complexidade teorica O(mn(m+n))=O(m^2n).
• Qual variante é mais eficiente na prática em termos de número iterações globais (caminhos buscados) e complexidade total (vértices expandidos)?

• 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: <2009-03-23 17:52:25 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>
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;
 
typedef unsigned Capacity;
struct VertexInformation {};
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 << edmonds_karp_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: 12/10/2015

• Aplicar o algoritmo de fluxo máximo desenvolvido no trabalho 3 para resolver o problema de “open pit mining”
• Uma descrição do problema está disponível aqui.
• Apresentar as soluções das 6 instâncias de teste abaixo no relatório (como figuras).

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

  Gerar uma instância aleatória:                ./opm --w 10 --h 10 --ins test.ins; display opm.pbm
  Visualizar uma solução:                       ./opm --ins test.ins --sol test.sol --pbm vis.pbm; display vis.pbm
  Converter PBM para PNG (Linux/ImageMagick):    convert vis.pbm vis.png

• Casos de teste: I1, I2, I3, I4, I5, I6

• As implementações do algoritmo devem aceitar uma instância na entrada padrão (stdin), imprimir a solução na saída padrão (stdout), e imprimir o lucro total na saíde de erro (stderr).
• Formato da instância: uma largura w, uma altura h, e lucros pij, com -128 < pij < 128, e pij != 0:

  w h
  p11 p12 ... p1w
  p21 p22 ... p2w
      ...
  ph1 ph2 ... phw

• Formato da solução: uma largura w, uma altura h, e booleanos sij que indicam se a celula ij é extraída ou não

  w h
  s11 s12 ... s1w
  s21 s22 ... s2w
      ...
  sh1 sh2 ... shw

Entrega: 16/11/2015

• Implementar o algoritmo Húngaro que resolve o problema do emparelhamento de maior peso em grafos bi-partidos ponderados.
• 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(mn^2), usando Bellman-Ford para busca de caminhos aumentantes.

• Gerar grafos bi-partidos completos com pesos aleatórios escolhidos uniformemente no intervalo [0,n^2].
• Casos de teste com soluções para a emparelhamento ponderado perfeito mínimo (para comparar com emparelhamento perfeito máximo: multiplicar os valores por -1). O formato corresponde com o que está descrito nas convenções abaixo com a última linha informando o peso total da solução correta.

• As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado completo na entrada padrão (stdin) e imprimir o maior peso de um emparelhamento na saída padrão (stdout). O formato é

n
p11 p12 p13 ... p1n
p21 p22 p23 ... p2n
...
pn1 pn2 pn3 ... pnn

com pij o peso entre vértice i do primeiro parte do grafo e vértice j do segundo parte.

Entrega: 10/12/2015 (Observação: esta data não será prorrogada)

• Implementar o algoritmo de Cristofides
• Testar duas variantes: a) usando um emparelhamento perfeito máximo, b) usando um emparelhamento perfeito obtido por um algoritmo guloso que seleciona cada vez a aresta livre de maior peso.
• Conduzir testes que avaliam o desempenho do algoritmo em termos de qualidade e tempo.

• Disponíveis na TSPLIB. Aplicar pelo menos nas instâncias gr96, gr202, gr229, gr431, ali535, gr666, dsj1000, pla7397, pla33810, pla85900.
• Para avaliar a qualidade: relatar o desvio relativo percentual (v-b)/b de uma solução com valor v e melhor valor conhecido b.
• Informar o tempo de execução em segundos.

• A implementação deve aceitar uma instância na entrada padrão (stdin) e imprimir o valor da rota obtida pelo algoritmo de Cristofides na saída padrão (stdout).
• O formato das instâncias é o mesmo formato usado na TSPLIB: uma documentação está aqui

• Para calcular o matching, usar o software Blossom V. (O algoritmo Húngaro da questão 5 não serve, porque é necessário determinar um matching no grafo não-bipartido.)
• Para facilitar a leitura de instâncias da TSPLIB, tspParse.H e tspParse.C mostram um exemplo em C++, que pode ser adaptado.