Marcus Ritt

Esta página é apenas de leitura. Pode ver a fonte, mas não alterá-la. Informe-se com o administrador deste Wiki se achar que isto não está correcto.
  * Ver também a página com [[dicas]] gerais.
  * D. S. Johnson: {{http://www.research.att.com/~dsj/papers/experguide.pdf|A Theoretician's Guide to the Experimental Analysis of Algorithms}}
==== Trabalho 1 (Heaps binários) ====

Entrega: 23/08/2010

=== Objetivos ===

  * Implementar um heap binário
  * Implementar o algoritmo de Prim usando esse heap
  * Verificar as complexidades experimentalmente

=== Convenções ===

  * As implementações do algoritmo Prim devem aceitar uma árvore no formato Steinlib na entrada padrão (stdin) e imprimir o peso total de uma árvore geradora mínima na saída padrão (stdout).

=== Casos de teste ===

  * Os casos de teste são parte do [[http://steinlib.zib.de//steinlib.php|Steinlib]].
  * Todos possuem somente uma componente conectada.

^ Nome          ^ MST ^ Nome ^ MST ^ Nome ^ MST ^
| b01 |   238 | c01 |  2426 |   msm0580 |   2141 |
| b02 |   238 | c02 |  2333 |   msm0654 |   7333 |
| b03 |   217 | c03 |  2313 |   msm0709 |   8837 |
| b04 |   196 | c04 |  2391 |   msm0920 |   4195 |
| b05 |   167 | c05 |  2372 |   msm1008 |   2381 |
| b06 |   168 | c06 |  1705 |   msm1234 |   5252 |
| b07 |   341 | c07 |  1734 |   msm1477 |   7110 |
| b08 |   343 | c08 |  1665 |   msm1707 |   1713 |
| b09 |   331 | c09 |  1616 |   msm1844 |    517 |
| b10 |   282 | c10 |  1669 |   msm1931 |   5218 |
| b11 |   236 | c11 |   862 |   msm2000 |   5333 |
| b12 |   253 | c12 |   895 |   msm2152 |  12279 |
| b13 |   480 | c13 |   884 |   msm2326 |   2525 |
| b14 |   463 | c14 |   855 |   msm2492 |  23844 |
| b15 |   462 | c15 |   882 |   msm2525 |  17518 |
| b16 |   319 | c16 |   503 |   msm2601 |  17024 |
| b17 |   296 | c17 |   499 |   msm2705 |   7646 |
| b18 |   337 | c18 |   503 |   msm2802 |   9540 |
|     |       | c19 |   504 |   msm2846 |  18494 |
|     |       | c20 |   509 |   msm3277 |   9579 |
|     |	      |	    |       |   msm3676 |   5948 |
|     |	      |	    |       |   msm3727 |  25659 |
|     |	      |	    |       |   msm3829 |  24972 |
|     |	      |	    |       |   msm4038 |   1436 |
|     |	      |	    |       |   msm4114 |   2333 |
|     |	      |	    |       |   msm4190 |   2270 |
|     |	      |	    |       |   msm4224 |   1094 |
|     |	      |	    |       |   msm4312 |  30628 |
|     |	      |	    |       |   msm4414 |   1996 |
|     |	      |	    |       |   msm4515 |   4488 |

=== Gerador de casos de teste ===

  * Gera um grafo com n vértices e probabilidade de um arco p, e imprime o peso total de uma árvore geradora mínima
  * Existe uma chance que o grafo não é conexo. Nesse caso o algoritmo falha.
  * Para compilar: Usar C++ e [[http://www.boost.org|Boost]].

<code c++>
#include <iostream>
#include <cassert>
using namespace std;

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/graph/kruskal_min_spanning_tree.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, undirectedS,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=i+1; j<n; j++)
      if (drand48() < p) {
        Edge e = add_edge(i,j,g).first;
	g[e].weight = lrand48()%maxweight;
      }

  // (2) verify number of connected components
  unsigned cc = connected_components(g, get(&VertexInformation::component,g));
  cout << cc << " connected components." << endl;
  if (cc>1)
    return 1;

  // (2.1) MST
  vector <Edge> mst;
  kruskal_minimum_spanning_tree(g, back_inserter(mst), weight_map(get(&EdgeInformation::weight,g)));
  unsigned cost = 0;
  for(vector<Edge>::iterator i=mst.begin(); i!=mst.end(); i++)
    cost += g[*i].weight;
  cout << "The weight of a MST is " << cost << "." << endl;
  
  // (3) print out in STP format
  cout << "SECTION Graph" << endl;
  cout << "Nodes " << num_vertices(g) << endl;
  cout << "Edges " << 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 << " " << g[*eb].weight << endl;
}
</code>
==== Trabalho 2 (rp-heaps) ====

Entrega: 06/09/2010

=== Objetivos ===
  * Implementar um rp-heap e verificar a complexidade das operações experimentalmente.
  * Verificar a complexidade do algoritmo de Prim usando um rp-heap experimentalmente.
  * Comparar as complexidades experimentais dos heaps binários e dos rp-heaps.
  * Comparar as complexidades experimentais do algoritmo de Prim com os dois heaps.

=== Casos de teste ===
  * Podem ser usados os mesmo casos de teste do primeiro trabalho.

=== Materias ===
  * {{:inf05504:rank-pairing_heaps_easier_.pdf|Artigo}}

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

Entrega: 27/09/2010

=== Objetivos ===
  * Implementar o algoritmo de Edmonds-Karp para achar um caminho 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}}.
  * 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 uam 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 determina 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: <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/edmunds_karp_max_flow.hpp>

using namespace boost;

// a directed graph with reverse edges
struct VertexInformation {};
struct EdgeInformation;

typedef adjacency_list<vecS,vecS,directedS,VertexInformation,EdgeInformation> DiGraph;
typedef graph_traits<DiGraph>::edge_descriptor Edge;
typedef graph_traits<DiGraph>::vertex_descriptor DiNode;

typedef unsigned Capacity;
struct EdgeInformation {
  Capacity edge_capacity;
  Capacity edge_residual_capacity;
  Edge reverse_edge;
};

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 << edmunds_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;
}
</code>


<html>
<br><br>
<a href="http://www2.clustrmaps.com/counter/maps.php?url=http://www.inf.ufrgs.br/~mrpritt" id="clustrMapsLink"><img width=1 src="http://www2.clustrmaps.com/counter/index2.php?url=http://www.inf.ufrgs.br/~mrpritt" style="border:1px solid;" alt="Locations of visitors to this page" title="Locations of visitors to this page" id="clustrMapsImg" onError="this.onError=null; this.src='http://clustrmaps.com/images/clustrmaps-back-soon.jpg'; document.getElementById('clustrMapsLink').href='http://clustrmaps.com'" />
</a>
</html>
==== Trabalho 4 (Emparelhamentos) ====

Entrega: 18/10/2009

=== 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)m).

=== 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;                                                                                               
                                                                                                                     
// information stored in vertices                                                                                    
struct VertexInformation;                                                                                            
                                                                                                                     
// information stored in edges                                                                                       
struct EdgeInformation {};                                                                                           
                                                                                                                     
// graph is an adjacency list represented by vectors                                                                 
typedef adjacency_list<vecS, vecS, undirectedS,VertexInformation,EdgeInformation> Graph;                             
typedef graph_traits<Graph>::vertex_descriptor Node;                                                                 
typedef graph_traits <Graph>::edge_descriptor Edge;                                                                  

struct VertexInformation {
  Node mate; // partner or graph_traits<Graph>::null_vertex()
};                                                           
                                                             
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;
  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 (Emparelhamentos) ====

Entrega: 08/11/2009

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

=== Casos de teste ===
  * Gerar grafos bi-partidos completos com pesos aleatórios escolhidos uniformemente no intervalo [0,n^2].
  * {{http://www.inf.ufrgs.br/~mrpritt/data1.tgz|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 ainda o valor peso total da solução correta. 

=== Convenções ===
  * 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 é
<code>
n
p11 p12 p13 ... p1n
p21 p22 p23 ... p2n
...
pn1 pn2 pn3 ... pnn
</code>
com pij o peso entre vértice i do primeiro parte do grafo e vértice j do segundo parte.



==== Trabalho 6 (Aproximação para o PCV métrico) ====

Entrega: 22/11/2009

=== Objetivos ===
  * Implementar o algoritmo de Cristofides para aproximar o PCV.
  * Documentar a implementação, em particular as estruturas de dados para a representação do problema.
  * Conduzir testes para avaliar o tempo de execução e a qualidade da solução obtida. Em particular, comparar com os melhores resultados conhecidos das instâncias do {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/|TSPLIB}}.

=== Casos de teste ===
  * Instâncias métricas do {{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/|TSPLIB}}, entre eles gr96, gr202, gr229, gr431, ali535, gr666, dsj1000, pla7397, pla33810, pla85900.

=== Convenções ===
  * As implementações do algoritmo devem aceitar uma instância de PCV no formato da TSPLIB na entrada padrão (stdin) e imprimir o valor da rota na saída padrão (stdout).

=== Observações ===
  * Para conseguir resultados para as maiores instâncias uma representação do grafo por uma matriz de adjacência não é adequado. Faz parte do objetivo de trabalho conseguir resultados para instâncias desse tamanho. Como o grafo é completo, não é necessário representa-lo explicitamente. Nas instâncias acima, as distâncias também são dadas implicitamente e não precisam ser representadas.
  * Não é o objetivo implementar um algoritmo de emparelhamento de peso máximo: usam {{http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/software.html|Blossom V}}. Observem que o Blossom V tem apoio para grafos geometricos no formato do TSPLIB, então não é necessário nem aconsehável criar o grafo explicitamente.
Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Ferramentas de Página
