visualizations

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

main.cpp (3566B)

      1 #include <algorithm>
      2 #include <thread>
      3 #include <chrono>
      4 #include <ctime>
      5 #include <time.h>
      6 #include <iostream>
      7 #include <cstdint>
      8 #include <raylib.h>
      9 #include <stdlib.h>
     10 #include <time.h>
     11 #include <unordered_map>
     12 #include <unordered_set>
     13 #include <vector>
     14 #include "draw.h"
     15 
     16 #define VERTICES 100
     17 #define EDGES 1000
     18 
     19 std::unordered_map<std::uintptr_t, std::vector<Edge*>> getMap(Vertex* verts, Edge* edges, int edgeCount, int vertCount) {
     20 
     21     std::unordered_map<std::uintptr_t, std::vector<Edge*>> res {};
     22 
     23     for(int i = 0; i < vertCount; ++i) {
     24         Vertex* vert = &verts[i];
     25         res[std::uintptr_t(vert)] = std::vector<Edge*>{};
     26     }
     27 
     28 
     29     for (int i = 0; i < edgeCount; ++i) {
     30         Edge& e = edges[i];
     31         res[std::uintptr_t(e.v1)].push_back(&e);
     32         res[std::uintptr_t(e.v2)].push_back(&e);
     33     }
     34 
     35     return res;
     36 }
     37 
     38 void visit_vertex(
     39     Vertex* v,
     40     const std::vector<Edge*>& edges,
     41     std::vector<Edge*>& visitHeap,
     42     std::unordered_set<std::uintptr_t>& visited
     43 ) {
     44 
     45     v->visited = true;
     46 
     47     visited.insert(uintptr_t(v));
     48     for(Edge* edge: edges) {
     49         visitHeap.push_back(edge);
     50 
     51         auto cmp = [](Edge* a, Edge* b) {
     52             // this makes it a min heap bc <
     53             return a->weight < b->weight;
     54         };
     55 
     56         std::push_heap(visitHeap.begin(), visitHeap.end(), cmp);
     57     }
     58     return;
     59 }
     60 
     61 // create vertices
     62 // create weighted edge list
     63 // associated edges with both vertices
     64     // undirected graph
     65 // start with arbitrary element
     66     // push edges into an array
     67     // search array for smallest element
     68     // explore
     69 int main(void)
     70 {
     71 
     72     srand(time(0));
     73     InitWindow(5120, 1440, "Raylib background animation window");
     74 
     75     while (!WindowShouldClose())
     76     {
     77         Vertex* vertices = gen_vertices(VERTICES);
     78         Edge* edges = gen_edges(vertices, VERTICES, EDGES);
     79         auto mp = getMap(vertices,edges,EDGES,VERTICES);
     80 
     81         std::unordered_set<std::uintptr_t> visited {};
     82         std::vector<Edge*> visitHeap;
     83 
     84         visit_vertex(&vertices[0], mp[uintptr_t(&vertices[0])], visitHeap, visited);
     85         bool done = false;
     86 
     87         while(!done) {
     88 
     89             BeginDrawing();
     90             ClearBackground(BLACK);
     91             draw_edges(edges,EDGES);
     92             draw_vertices(vertices,VERTICES);
     93             EndDrawing();
     94             std::this_thread::sleep_for(std::chrono::seconds(1));
     95 
     96             std::vector<Edge*> currentHeap = visitHeap;
     97             visitHeap.clear();
     98 
     99             auto cmp = [](Edge* a, Edge* b) {
    100                 return a->weight < b->weight;
    101             };
    102             std::pop_heap(visitHeap.begin(), visitHeap.end(), cmp);
    103 
    104             Edge* vis = visitHeap.back();
    105             visitHeap.pop_back();
    106 
    107             if(visited.find(uintptr_t(vis->v1)) == visited.end() && visited.find(uintptr_t(vis->v2)) == visited.end()) {
    108                 continue;
    109             }
    110 
    111             if(visited.find(uintptr_t(vis->v1)) != visited.end() && visited.find(uintptr_t(vis->v2)) != visited.end()) {
    112                 continue;
    113             }
    114 
    115 
    116             Vertex* visiting = nullptr;
    117 
    118             if(visited.find(uintptr_t(vis->v1)) == visited.end()){
    119                 visited.insert(uintptr_t(vis->v1));
    120                 visiting = vis->v1;
    121             } else {
    122                 visited.insert(uintptr_t(vis->v2));
    123                 visiting = vis->v2;
    124             }
    125             vis->traversed = true;
    126             visit_vertex(visiting, mp[uintptr_t(visiting)], visitHeap, visited);
    127         }
    128 
    129         free(vertices);
    130         free(edges);
    131     }
    132 
    133     CloseWindow();
    134     return 0;
    135 }