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.
==== Trabalho 1 (Heaps binários e algoritmo de Dijkstra) ====

Entrega: 27/03/2020

=== Objetivos ===

  * Implementar um heap k-ário.
  * Implementar o algoritmo de Dijkstra usando o heap implementado.
  * Determinar o valor de k tal que o algoritmo de Dijkstra com um heap k-á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:testplan20201.pdf|plano de teste}}.

=== Observações ===

  * Como o grafo possui 23,947,347 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>
Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Ferramentas de Página
