abg

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

prim.cpp (2010B)


      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 double 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 0;
     41     }
     42     while (found == false) {
     43         if (toVisit.size() == 0) {
     44             return 0;
     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             return current.length2;
     55 
     56         } else if (visitedIndices.find(current.v1Index) ==
     57                    visitedIndices.end()) {
     58             auto cIdx = current.v1Index;
     59             explore(cIdx, toVisit, current, g, visitedIndices, minVertWeight);
     60             return current.length2;
     61         } else {
     62             found = false;
     63         }
     64     }
     65     return 0;
     66 }