PrimsAlgorithm.cpp

//============================================================================
// Name        : PrimsAlgorithm.cpp
// Author      : Dean Sands
// Version     : 0.0.1a
// Copyright   : I will set your flamingos on fire.
// Description : Prim's Minimum Spanning Tree Maze Creator
//============================================================================


#include <SFML/Graphics.hpp>
#include <unordered_map>
#include <vector>
#include <deque>
#include <iostream>
#include <cstdlib>
#include <climits>
#include <chrono>
#include <random>
#include <algorithm>
#include <set>
#pragma comment(lib,"glew.lib")
#pragma comment(lib,"sfml-system-d.lib")
#pragma comment(lib,"sfml-window-d.lib")
#pragma comment(lib,"sfml-graphics-d.lib")

#define WIDTH 40
#define HEIGHT 30
#define TOTAL (WIDTH*HEIGHT)

using namespace std;


struct node{
    float x;
    float y;
    node(float newX, float newY):x(newX),y(newY){}
};


struct edge{
    node *a;
    node *b;
    uint64_t weight;
    edge(node *newNodeA, node *newNodeB, uint64_t newWeight=0):a(newNodeA),b(newNodeB), weight(newWeight){}
    bool operator() (edge *i, edge *j) { return (i->weight<j->weight);}
    bool operator() (edge i, edge j) { return (i.weight<j.weight);}
};



set<node*> knownNodes;
set<node*> unknownNodes;
unordered_map<uint64_t, edge*> edgemap;
deque<edge*> edgeQueue;
vector<edge*> usedEdges;
vector<node*> nodelist;
std::mt19937_64 *generator;

node *addNode(float x, float y){
    node *newNode=new node(x,y);
    nodelist.push_back(newNode);
    unknownNodes.insert(newNode);
    return newNode;
}

void connectNodes(uint64_t a,uint64_t b){
    uint64_t weight;
    edge *newEdge = new edge(nodelist[a],nodelist[b]);
    do{
        weight=(*generator)();
    }while(edgemap.find(weight)!=edgemap.end());
    newEdge->weight=weight;
    edgemap[weight]=newEdge;
    edgeQueue.push_back(newEdge);
}

void createNodes(){
    int x=0, y=0;
    for(y=0;y<HEIGHT;y++)for(x=0;x<WIDTH;x++)addNode(x*20,y*20);
}

void createEdges(){
    int x=0, y=0;
    //Top row
    for(x=1;x<WIDTH;x++){
        uint64_t myNodeIndex=y*WIDTH+x;
        connectNodes(myNodeIndex-1,myNodeIndex);
    }
    for(y=1;y<HEIGHT;y++){
        for(x=1;x<WIDTH;x++){
            uint64_t myNodeIndex=y*WIDTH+x;
            connectNodes(myNodeIndex-1,myNodeIndex);
            connectNodes(myNodeIndex-WIDTH,myNodeIndex);
        }
    }
}
void primsAlgorithm(){
    bool addA,addB;
    edge *currentEdge;
    node *nodeA, *nodeB;
    int i=0;
    while(!unknownNodes.empty()){
        auto currentEdgeIter = edgeQueue.begin();
        if (currentEdgeIter == edgeQueue.end()){ cout << "End of queue reached." << endl; break; }
        currentEdge = *currentEdgeIter;
        nodeA = currentEdge->a;
        nodeB=currentEdge->b;
        addA = (unknownNodes.find(nodeA) != unknownNodes.end());
        addB=(unknownNodes.find(nodeB)!=unknownNodes.end());
        if (!(addA || addB)) {
            edgeQueue.pop_front();
            continue;
        }
        usedEdges.push_back(currentEdge);
        if(addA){unknownNodes.erase(nodeA);}
        if(addB){unknownNodes.erase(nodeB);}
        edgeQueue.pop_front();
        i++;
        std::cout<<i<<endl;
    }

    while (!unknownNodes.empty()){
        auto nodeIter = unknownNodes.begin();
        auto nodeC = *nodeIter;
        cout << "Unknown Node:" << nodeC->x << "," << nodeC->y << endl;
        unknownNodes.erase(nodeIter);
    }
}
void display(){
    sf::RenderWindow window(sf::VideoMode(800, 600), "My window");

    // run the program as long as the window is open
    while (window.isOpen())
    {
        // check all the window's events that were triggered since the last iteration of the loop
        sf::Event event;
        while (window.pollEvent(event))
        {
            // "close requested" event: we close the window
            if (event.type == sf::Event::Closed)
                window.close();
            // "close requested" event: we close the window
            if (event.type == sf::Event::KeyPressed)
                if (event.key.code == sf::Keyboard::Escape)
                window.close();
        }

        // clear the window with black color
        window.clear(sf::Color::Black);

        for(auto thisEdge:usedEdges){
            sf::Vertex line[] =
            {
                sf::Vertex(sf::Vector2f(thisEdge->a->x, thisEdge->a->y)),
                sf::Vertex(sf::Vector2f(thisEdge->b->x, thisEdge->b->y))
            };

            window.draw(line, 2, sf::Lines);
        }

        for(auto c:nodelist){
            // define a circle with radius = 5
            sf::CircleShape *circle=new sf::CircleShape(5);
            circle->setOrigin(c->x,c->y);

            // change the number of sides (points) to 8
            circle->setPointCount(8);
            circle->setFillColor(sf::Color(250, 100, 50));
            window.draw(*circle);
            delete circle;
        }

        // end the current frame
        window.display();
    }
}
void cleanup(){
    // ******** //
        for(auto nodeX:nodelist){
            delete nodeX;
        }
        for(auto edgeX:edgemap){
            delete edgeX.second;
        }
}

int main(void) {
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    generator = new std::mt19937_64(seed);
    createNodes();
    cout<<"nodes created."<<endl;
    createEdges();
    cout<<"edges created"<<endl;
    sort(edgeQueue.begin(),edgeQueue.end());
    cout<<"edges sorted"<<endl;
    primsAlgorithm();
    cout<<"edges primmed"<<endl;
    display();
    cout<<"edges displayed"<<endl;
    cleanup();
    cout<<"nodes and edges cleaned"<<endl;
    return EXIT_SUCCESS;
}