Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Identificação de ciclos em grafos: diferenças entre revisões
[edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição |
Sem resumo de edição |
||
Linha 144:
list<list<vid_t>*> *inMsgs = vertex.inedge(i)->get_data();
if(inMsgs && inMsgs->size()>0){
for(int j=0; j < vertex.num_outedges(); j++) {
list<list<vid_t>*>::iterator msgList;
for(msgList = inMsgs->begin(); msgList!=inMsgs->end(); msgList++){
list<vid_t> *value = copyVertexList((*msgList));
if(value->front()==vertex.vertexid){
Linha 159 ⟶ 160:
}else delete value;
}
deleteMessages(inMsgs);▼
}
}
}
Linha 216:
bool CycleDetection::hasInMessages(graphchi_vertex<VertexDataType, EdgeDataType> &vertex) {
for(int i=0; i < vertex.num_inedges(); i++) {
list<list<vid_t>*> *inMsgs = vertex.inedge(i)->get_data();
if(inMsgs->size()>0)
▲ break;
}
return
}
Linha 236 ⟶ 232:
bool CycleDetection::vertexListContains(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, list<vid_t> *value) {
list<vid_t>::iterator it = value->begin();
while(it!=value->end()){
if( (*it)==vertex.vertexid )
it++;
}
return
}
Linha 284 ⟶ 276:
Para esse grafo de 13485277 vértices, basicamente representando o intervalo de números naturais [0, 13485277], foram encontrados 71 grupos sociáveis de ordem maior ou igual a dois.
=== Experimento #3 ===
O segundo experimento foi executado para um grafo de 16875505 vértices. O tempo total para a execução de todas as iterações foi de 367,872 segundos (6,13 minutos), realizando um total de 87 iterações, com tempo médio de 4.18037 segundos para processar cada vértice a cada iteração.
Para esse grafo de 13485277 vértices, basicamente representando o intervalo de números naturais [0, 16875505], foram encontrados 76 grupos sociáveis de ordem maior ou igual a dois.
=== Experimento #4 ===
O segundo experimento foi executado para um grafo de 18109729 vértices. O tempo total para a execução de todas as iterações foi de 433,687 segundos (7,23 minutos), realizando um total de 87 iterações, com tempo médio de 4,92826 segundos para processar cada vértice a cada iteração.
Para esse grafo de 18109729 vértices, basicamente representando o intervalo de números naturais [0, 18109729], foram encontrados 78 grupos sociáveis de ordem maior ou igual a dois.
|