visualizations

Programmatic visualizations
git clone git://git.laack.co/visualizations.git
Log | Files | Refs | README

prim.cpp (1492B)

      1 #include "../headers/graph.hpp"
      2 #include "../headers/prim.hpp"
      3 #include <cstdlib>
      4 #include <unistd.h>
      5 #include <raylib.h>
      6 #include <queue>
      7 #include <unordered_set>
      8 
      9 
     10 void explore(
     11         std::size_t cIdx, 
     12         std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
     13         Edge& current,
     14         Graph& g,
     15         std::unordered_set<std::size_t>& visitedIndices
     16     ) {
     17 
     18     visitedIndices.insert(cIdx);
     19     g.traverseVertexIdx(cIdx);
     20 
     21     g.setEdgeTraversed(current);
     22 
     23     std::vector<Edge> edges = g.getEdgesOfVertexIdx(cIdx);
     24     for(auto edge: edges) {
     25         toVisit.push(edge);
     26     }
     27 }
     28 
     29 void oneStepPrim(
     30         std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
     31         std::unordered_set<std::size_t>& visitedIndices,
     32         Graph& g
     33         ) {
     34     bool found = false;
     35     if(toVisit.size() == 0) {
     36         return;
     37     }
     38     while(found == false) {
     39         if(toVisit.size() == 0) {
     40             return;
     41         }
     42 
     43         found = true;
     44         auto current = toVisit.top();
     45         toVisit.pop();
     46 
     47         if(visitedIndices.find(current.v2Index) == visitedIndices.end()) {
     48             auto cIdx = current.v2Index;
     49             explore(cIdx, toVisit, current, g, visitedIndices);
     50 
     51         } else if(visitedIndices.find(current.v1Index) == visitedIndices.end()) {
     52             auto cIdx = current.v1Index;
     53             explore(cIdx, toVisit, current, g, visitedIndices);
     54         } else {
     55             found = false;
     56         }
     57 
     58     }
     59 }
     60 
     61