Status das entregas (25 de julho 2017):

^ Cartão ^ T1 ^ T2 ^ T3 ^ T4 ^ T5 ^
| 120921 | s  | s  | s  | s  | s  |
| 161896 | s  | s  | s  | s  | s  |
| 205691 | s  | s  | s  | s  | s  |
| 205798 |    |    |    |    |    |
| 213917 |    |    |    |    |    |
| 218319 | s  |    |    |    |    |
| 218326 | s  | s  | s  | s  | s  |
| 219436 |    |    |    |    |    |
| 220505 | s  | s  | s  | s  | s  |
| 228401 | s  |    |    |    |    |
| 228483 | s  | s  | s  | s  | s  |
| 228527 | s  | s  | s  | s  | s  |
| 242239 | s  |    |    |    |    |
| 242249 | s  |    |    |    |    |
| 242274 | s  | s  | s  | s  | s  |
| 259094 | s  | s  | s  | s  | s  |
| 262528 | s  |    |    |    |    |
| 264311 | s  |    |    |    |    |
| 273103 | s  | s  |    |    |    |
| 282838 | s  |    |    |    |    |
| 286120 | s  | s  | s  | s  | s  |
| 286134 | s  | s  | s  | s  | s  |
| 286244 | s  |    | s  | s  | s  |
| 291000 | s  | s  | s  | s  | s  |

==== Trabalho 1 (Heaps binários e algoritmo de Dijkstra) ====

Entrega: 18/04/2017

=== Objetivos ===

  * 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.

=== Casos de teste ===

  * 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 [[http://www.dis.uniroma1.it/~challenge9/download.shtml|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".
  * Exemplo de um {{:inf05016:testplan20171.pdf|plano de teste}}.

=== Observações ===

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

=== Convenções ===
    * 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

=== Gerador de casos de teste ===
<code c++>
/**
 * \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;
}
</code>

=== Leitura (Exemplo) ===
<code c++>
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++;
    }
  }
}
</code>

==== Trabalho 2 (Heaps com nós vazios, hollow heaps) ====

Entrega: 02/05/2017

=== Objetivos ===
  * Implementar um heap com nós vazios e verificar a complexidade das operações experimentalmente.
  * Verificar a complexidade do algoritmo de Dijkstra usando um heap com nós vazios experimentalmente.
  * Comparar as complexidade empírica do heap binário com a do heap com nós vazios.
  * Comparar as complexidades empíricas do algoritmo de Dijkstra com os dois heaps.

=== Casos de teste ===
  * Podem ser usados os mesmos casos de teste do primeiro trabalho e o mesmo tipo de avaliação.

=== Material sobre "hollow heaps" ===

  * [[https://arxiv.org/abs/1510.06535|Artigo de Hansen et al.]]
  * {{hollow-heap-main.pdf|Notas de aula}}

=== Convenções ===
    * As implementações do algoritmo de Dijsktra 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".

==== Trabalho 3 (Fluxo s-t máximo) ====

Entrega: 23/05/2017

=== Objetivos ===
  * Implementar o algoritmo de Ford-Fulkerson com a estratégia do "caminho mais gordo" (fattest path) s-t.
  * Verificar a complexidade do algoritmo experimentalmente.

=== Casos de teste ===
  * Um gerador de casos de teste em formato DIMACS em C é disponível {{http://www.inf.ufrgs.br/~mrpritt/washington.c|aqui}}.
  * Novo: Uma versão melhor do {{http://www.inf.ufrgs.br/~mrpritt/aa/new_washington_test_dir.tar.gz|gerador}}.
  * Documentação:
<code>
             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)
</code>

^ No. ^ Nome ^ Parâmetros ^ Descrição ^ n ^ m ^
|   1 | Mesh | r,c | Grade, 3 viz. 1 direita | rc+2 | 3r(c-1) |
|   2 | Random level | r,c | Grade, 3 viz. rand. 1 direita | rc+2 | 3r(c-1) |
|   3 | Random 2-level | r,c | Grade, 3 viz. rand. 2 direita | rc+2 | 3r(c-1) |
|   4 | Matching | n,d | Bipart. n-n, d viz. rand. | 2n+2 | n(d+2) |
|   5 | Square Mesh | d,D | Quadr. mesh dxd, grau D | d*d+2 | (d-1)dD+2d |
|   6 | BasicLine | n,m,D | Linha, grau D| nm+2 | nmD+2m |
|   7 | ExpLine | n,m,D | Linha, grau D | nm+2 | nmD+2m |
|   8 | DExpLine | n,m,D | Linha, grau D | nm+2 | nmD+2m |
|   9 | DinicBad | n | Linha | n | 2n-3|
|  10 | GoldBad | n | | 3n+3 | 4n+1 |

=== Convenções ===
  * As implementações do algoritmo devem aceitar uma instância no formato {{http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm|DIMACS}} na entrada padrão (stdin) e imprimir o valor do fluxo máximo na saída padrão (stdout).

=== Verificação  ===
  * O seguinte código calcula o fluxo máximo. Para compilar: Usar C++ e {{http://www.boost.org|Boost}}.
<code c++>
/**
 * \file maxflow.cpp
 *   \author Marcus Ritt <mrpritt@inf.ufrgs.br> 
 *   \version $Id: emacs 2872 2009-01-31 01:46:50Z ritt $
 *   \date Time-stamp: <2015-09-22 21:17:31 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/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,
                                get(&EdgeInformation::edge_capacity,g),
                                get(&EdgeInformation::edge_residual_capacity,g),
                                get(&EdgeInformation::reverse_edge,g),
                                get(boost::vertex_index, g));    
}
</code>

==== Trabalho 4 (Emparelhamentos) ====

Entrega: 13/6/2017

=== Objetivos ===
  * 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)(n+m)). Em particular: complexidades O(sqrt(n)) para o número de fases e O(n+m) para a extração de um conjunto maximál de caminhos aumentantes.
  * Decidir experimentalmente: a abordagem por redução para um problema de fluxo é mais eficiente?

=== Casos de teste ===
  * Gerar grafos bi-partidos randômicas com probabilidade de uma aresta 0 <= p <= 1.

=== Convenções ===
  * As implementações do algoritmo devem aceitar um grafo bi-partido não-direcionado no formato [[http://prolland.free.fr/works/research/dsat/dimacs.html|DIMACS]] na entrada padrão (stdin) e imprimir a cardinalidade de um emparelhamento máximo na saída padrão (stdout).

=== Códigos disponíveis ===
  * Gerador de casos de teste no formato DIMACS + verificação.
  * Para compilar: Usar C++ e Boost.
<code c++>
#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;
}
</code>

==== Trabalho 5 (O algoritmo de Cristofides) ====

Entrega: 7/7/2017

=== Objetivos ===

  * 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.

=== Casos de teste ===
  * Disponíveis na {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95|TSPLIB}}. Aplicar pelo menos nas instâncias berlin52, vm1748, pr2392, pcb3038, fnl4461, rl5934, rl5915, usa13509, brd14051, d18512.
  * 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.

=== Convenções ===

  * 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 {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95|TSPLIB}}: uma documentação está {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/DOC.PS|aqui}}

=== Materiais ===

  * Para calcular o matching, usar o software {{http://pub.ist.ac.at/~vnk/software/blossom5-v2.05.src.tar.gz|Blossom V}}.
  * Para facilitar a leitura de instâncias da TSPLIB, {{http://www.inf.ufrgs.br/~mrpritt/aa/tspParse.H}} e {{http://www.inf.ufrgs.br/~mrpritt /aa/tspParse.C}} mostram um exemplo em C++, que pode ser adaptado.
  * {{http://www.inf.ufrgs.br/~mrpritt/aa/blossom.patch-2|Um patch}} contra blossom5 para trabalhar com coordenadas reais (e um bugfix).