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.