Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

--- inf05504:trabalhos [2010/08/24 16:25]
marcus
+++ inf05504:trabalhos [2010/12/03 17:08] (Actual)
marcus
@@ Linha 128: / Linha 128: @@
 }
 </code>
 ==== Trabalho 2 (rp-heaps) ====
@@ Linha 141: / Linha 140: @@
 === 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>
@@ Linha 148: / Linha 258: @@
 </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

Diferenças

Ferramentas de Página