SHARE
TWEET

Untitled

a guest Jun 16th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void* graphSCCGraphRec(void* gra)
  2. {
  3.     GraphObject* graph = (GraphObject*)gra;
  4.  
  5.     //creo lo stack
  6.     StackType* stkType = ConstructStackVecType();
  7.     StackObject* stack = stkConstruct(stkType);
  8.     StackObject* stackRet = stkConstruct(stkType);
  9.  
  10.     DataType* intDataType = ConstructIntDataType();
  11.     DataObject* bstData = adtConstruct(intDataType);
  12.  
  13.     BSTType* bstType = ConstructBSTRecursive();
  14.     BSTObject* tree = bstConstruct(bstType);
  15.     BSTObject* treeGreys = bstConstruct(bstType);
  16.  
  17.     ITRObject* vertItr = graphVertices(graph);
  18.  
  19.     while(vertItr != NULL && !itrTerminated(vertItr)){
  20.         DataObject* name = itrElement(vertItr);
  21.         int id = adtGetVertexId(name->value);
  22.         adtSetValue(bstData, &id);
  23.         if(!bstExists(tree, bstData)){
  24.             stack = TopologicalRec(graph, id, tree, treeGreys, stack);
  25.             //stack =  SCCUtilityRec(graph, id, tree, stack);
  26.         }
  27.         itrSuccessor(vertItr);
  28.     }
  29.     //costruisco il trasposto
  30.     GraphObject* transpose = graphTranspose(graph);
  31.  
  32.     ITRObject* transpVertItr = graphVertices(transpose);
  33.  
  34.     //pulisco l'albero dei colori
  35.     bstClear(tree);
  36.  
  37.     printf("\n*** procedo a stampare lo stack ***\n");
  38.     stkMap(stack, &stampaMap, NULL);
  39.  
  40.     while(!stkEmpty(stack)){
  41.         uint stackElem = *((int*)adtGetValue(stkTopNPop(stack)));
  42.         adtSetValue(bstData, &stackElem);
  43.         if(!bstExists(tree, bstData)) {
  44.             stkPush(stackRet, bstData);
  45.             DFSVisitSCC(transpose, stackElem, tree);
  46.         }
  47.     }
  48.     printf("\n*** procedo a stampare lo stackRet ***\n");
  49.     stkMap(stackRet, &stampaMap, NULL);
  50. }
  51.  
  52. void* SCCUtilityRec(GraphObject* graph, uint name, BSTObject* tree, StackObject* stack)
  53. {
  54.     DataType* intDataType = ConstructIntDataType();
  55.     DataObject* intDo = adtConstruct(intDataType);
  56.  
  57.     ITRObject* edgItr = graphVertexEdges(graph,name);
  58.  
  59.     adtSetValue(intDo, &name);
  60.     bstInsert(tree ,intDo);
  61.  
  62.     if(!stkExists(stack,intDo)) {
  63.         stkPush(stack, intDo);
  64.     }
  65.  
  66.     while(edgItr != NULL && !itrTerminated(edgItr)){
  67.         uint curr = *((int*)itrElement(edgItr));
  68.         adtSetValue(intDo, &curr);
  69.         if(!bstExists(tree, intDo)){
  70.             stack = SCCUtilityRec(graph , curr, tree, stack);
  71.         }
  72.         itrSuccessor(edgItr);
  73.     }
  74.  
  75.     return stack;
  76. }
  77.  
  78. void DFSVisitSCC(GraphObject* transpose, int stackElem, BSTObject* tree)
  79. {
  80.     DataType* intDataType = ConstructIntDataType();
  81.     DataObject* intDo = adtConstruct(intDataType);
  82.  
  83.     ITRObject* edgItr = graphVertexEdges(transpose,stackElem);
  84.  
  85.     adtSetValue(intDo, &stackElem);
  86.     bstInsert(tree ,intDo);
  87.  
  88.  
  89.     while(edgItr != NULL && !itrTerminated(edgItr)){
  90.         uint curr = *((int*)itrElement(edgItr));
  91.         adtSetValue(intDo, &curr);
  92.         if(!bstExists(tree, intDo)){
  93.             DFSVisitSCC(transpose,curr, tree);
  94.         }
  95.         itrSuccessor(edgItr);
  96.     }
  97. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top