Entrega: 23/08/2010

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

• 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).

• Os casos de teste são parte do Steinlib.
• Todos possuem somente uma componente conectada.

• 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 Boost.

#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;
}

Entrega: 06/09/2010

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

• Podem ser usados os mesmo casos de teste do primeiro trabalho.

• Artigo

Entrega: 27/09/2010

• Implementar o algoritmo de Edmonds-Karp para achar um caminho 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 uam 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/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;
}

Entrega: 18/10/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;                                                                                               
 
// 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;
}

Entrega: 08/11/2009

• 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 ainda o valor 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: 22/11/2009

• 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 TSPLIB.

• Instâncias métricas do TSPLIB, entre eles gr96, gr202, gr229, gr431, ali535, gr666, dsj1000, pla7397, pla33810, pla85900.

• 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).

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