Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Avaliação do algoritmo PageRank: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Linha 188:
A implementação foi feita em linguagem C++, com o objetivo de ser mais genérica possível, podendo executar em qualquer tipo de grafo.
<syntaxhighlight lang="cpp">
#include <string>
#include <fstream>
#include <graphlab.hpp>
#define DAMPING_FACTOR 0.85
#define MAX_ERROR 1e-6
// Estruturas de Dados
typedef double Vertice;
typedef graphlab::empty Aresta;
typedef graphlab::distributed_graph<Vertice, Aresta> Grafo;
// Algoritmo
class PageRank :
public graphlab::ivertex_program<Grafo, double>,
public graphlab::IS_POD_TYPE
{
private:
double error;
public:
edge_dir_type gather_edges(icontext_type &context, const vertex_type &vertex) const {
return graphlab::IN_EDGES;
}
gather_type gather(icontext_type &context, const vertex_type &vertex, edge_type &edge) const {
return edge.source().data() / edge.source().num_out_edges();
}
void apply(icontext_type &context, vertex_type &vertex, const gather_type &total) {
double valor_novo = (1 - DAMPING_FACTOR) + DAMPING_FACTOR*total;
error = std::fabs(vertex.data() - valor_novo);
vertex.data() = valor_novo;
}
edge_dir_type scatter_edges(icontext_type &context, const vertex_type &vertex) const {
if (error > MAX_ERROR) {
return graphlab::OUT_EDGES;
}
else {
return graphlab::NO_EDGES;
}
}
void scatter(icontext_type &context, const vertex_type &vertex, edge_type &edge) const {
context.signal(edge.target());
}
};
void pagerank_valor_inicial(Grafo::vertex_type& vertice) {
vertice.data() = 1.0;
}
// Saida
class pagerank_writer {
public:
std::string save_vertex(Grafo::vertex_type v) {
std::stringstream saida_linha;
saida_linha << v.id() << " " << v.data() << std::endl;
return saida_linha.str();
}
std::string save_edge(Grafo::edge_type e) {
return "";
}
};
// Main
int main(int argc, char** argv) {
// Inicializa GraphLab
graphlab::mpi_tools::init(argc, argv);
graphlab::distributed_control dc;
// Parametros de Entrada
graphlab::command_line_options clopts("Algoritmo PageRank.");
std::string arquivo_entrada_grafo = "/shared/data/grafo.adj";
std::string arquivo_saida = "/shared/results/temp";
std::string formato_grafo = "adj";
std::string tipo_execucao = "synchronous";
clopts.attach_option("entrada", arquivo_entrada_grafo, "Arquivo de entrada do grafo");
clopts.attach_option("formato", formato_grafo, "Formato do arquivo do grafo: 'tsv' ou 'adj'");
clopts.attach_option("exec", tipo_execucao, "Tipo de execucao: 'synchronous' ou 'asynchronous'");
clopts.attach_option("saida", arquivo_saida, "Arquivo de saida com os valores de PageRank calculados para cada vertice");
if(!clopts.parse(argc, argv)) {
dc.cout() << "ERRO: Argumentos de linha de comando invalidos." << std::endl;
return EXIT_FAILURE;
}
// Carrega o grafo
Grafo grafo(dc);
grafo.load_format(arquivo_entrada_grafo, formato_grafo);
grafo.finalize();
// Executa algoritmo
grafo.transform_vertices(pagerank_valor_inicial);
graphlab::omni_engine<PageRank> engine(dc, grafo, tipo_execucao);
engine.signal_all();
engine.start();
const float runtime = engine.elapsed_seconds();
dc.cout() << "Terminou de executar em " << runtime << " segundos." << std::endl;
// Saida
grafo.save(arquivo_saida, pagerank_writer(), false, true, false);
// Finaliza GraphLab
graphlab::mpi_tools::finalize();
return EXIT_SUCCESS;
}
</syntaxhighlight>
== Avaliação ==
| |||