Wikilivros

Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Identificação de ciclos em grafos: diferenças entre revisões

Explorar interativamente o histórico
(Ver alterações pendentes à versão publicada)
[edição não verificada][edição não verificada]
← Edição anteriorEdição posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
Sem resumo de edição
Sem resumo de edição
Linha 81:
 
<source lang=cpp>
typedef vid_t VertexDataType;
void update(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, graphchi_context &gcontext) {
typedef list<list<vid_t>*>* EdgeDataType;
 
class CycleDetection : public GraphChiProgram<VertexDataType, EdgeDataType> {
public:
void update(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, graphchi_context &gcontext);
void before_iteration(int iteration, graphchi_context &gcontext);
void after_iteration(int iteration, graphchi_context &gcontext);
void before_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &gcontext);
void after_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &gcontext);
private:
void sendInitialMessageToNeighbours(graphchi_vertex<VertexDataType, EdgeDataType> &vertex);
void sendMessageToNeighbour(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, int neighbourId, list<vid_t> *value);
void deleteMessages(list<list<vid_t>*> *msgs);
 
bool hasInMessages(graphchi_vertex<VertexDataType, EdgeDataType> &vertex);
 
vid_t getMinVertexId(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, list<vid_t> *value);
bool vertexListContains(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, list<vid_t> *value);
list<vid_t> *copyVertexList(list<vid_t> *vList);
void outputCycle(list<vid_t> *value);
};
</source>
 
<source lang=cpp>
void CycleDetection::update(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, graphchi_context &gcontext) {
if (countIteration == 0) {
sendInitialMessageToNeighbours(vertex);
Linha 92 ⟶ 117:
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 *outvalue = vertex.outedge(j)->get_data()msgList;
for(list<list<vid_t>*>::iterator msgList = inMsgs->begin(); msgList!=inMsgs->end(); msgList++){
list<vid_t> *value = copyVertexList(*msgList);
 
Linha 104 ⟶ 129:
delete value;
}else if(!vertexListContains(vertex, value)){
value->push_backsendMessageToNeighbour(vertex.vertexid, j, value);
outvalue->push_back(value);
}else delete value;
}
Linha 114 ⟶ 138:
}
}
}
</source>
 
<source lang=cpp>
graphchi_engine<VertexDataType, EdgeDataType> *enginePtr;
int countIteration;
size_t finishedVertices;
 
#define activateVertex() finishedVertices--
#define initIteration() finishedVertices = gcontext.nvertices
#define closeIteration() if(finishedVertices==gcontext.nvertices) enginePtr->set_outside_closing(true)
 
void CycleDetection::before_iteration(int iteration, graphchi_context &gcontext) {
initIteration();
}
void CycleDetection::after_iteration(int iteration, graphchi_context &gcontext) {
if(countIteration>0)
closeIteration();
countIteration++;
}
 
void CycleDetection::before_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &gcontext) {}
 
void CycleDetection::after_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &gcontext) {}
 
</source>
 
<source lang=cpp>
void CycleDetection::sendInitialMessageToNeighbours(graphchi_vertex<VertexDataType, EdgeDataType> &vertex) {
vertex.set_data(vertex.vertexid);
for(int i=0; i < vertex.num_outedges(); i++) {
list<list<vid_t>*> *edge_value = new list<list<vid_t>*>;
list<vid_t> *msg = new list<vid_t>;
msg->push_back(vertex.vertexid);
edge_value->push_back(msg);
vertex.outedge(i)->set_data(edge_value);
}
}
 
void CycleDetection::sendMessageToNeighbour(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, int neighbourId, list<vid_t> *value) {
list<list<vid_t>*> *outvalue = vertex.outedge(neighbourId)->get_data();
value->push_back(vertex.vertexid);
outvalue->push_back(value);
}
 
void CycleDetection::deleteMessages(list<list<vid_t>*> *msgs) {
for(list<list<vid_t>*>::iterator it = msgs->begin(); it!=msgs->end(); it++){
delete (*it);
}
msgs->clear();
}
 
bool CycleDetection::hasInMessages(graphchi_vertex<VertexDataType, EdgeDataType> &vertex) {
bool finished = true;
for(int i=0; i < vertex.num_inedges(); i++) {
list<list<vid_t>*> *inMsgs = vertex.inedge(i)->get_data();
if(inMsgs->size()>0){
finished = false;
break;
}
}
return(!finished);
}
 
vid_t CycleDetection::getMinVertexId(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, list<vid_t> *value) {
vid_t minId = vertex.vertexid;
for(list<vid_t>::iterator it = value->begin(); it!=value->end(); it++){
if( (*it)<minId ) minId = (*it);
}
return minId;
}
 
bool CycleDetection::vertexListContains(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, list<vid_t> *value) {
bool found = false;
list<vid_t>::iterator it = value->begin();
it++;
while(it!=value->end()){
if( (*it)==vertex.vertexid ){
found = true;
break;
}
it++;
}
return found;
}
 
list<vid_t> *CycleDetection::copyVertexList(list<vid_t> *vList) {
list<vid_t> *value = new list<vid_t>;
for(list<vid_t>::iterator it = vList->begin(); it!=vList->end(); it++){
value->push_back(*it);
}
return value;
}
 
void CycleDetection::outputCycle(list<vid_t> *value) {
cout << "CYCLE: [ ";
for(list<vid_t>::iterator it = value->begin(); it!=value->end(); it++){
cout << (*it) << " ";
}
cout << "]" << endl;
}
</source>
Obtido em "https://pt.wikibooks.org/wiki/Processamento_de_Dados_Massivos/Projeto_e_implementação_de_aplicações_Big_Data/Identificação_de_ciclos_em_grafos"