abg

Animated background for X11
git clone git://git.laack.co/abg.git
Log | Files | Refs | README | LICENSE

prim.cpp (1918B)

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