Prim's algorithm using cgraph.

prims_algorithm.cpp

//
// Created by Ben Napier on 08/03/2019.
//
#include <iostream>
#include "Graph.h"

int main() {
    // Lets implement a bit of Prim's...
    // First set up our graph.
    Graph graph;
    graph.AddNodesFrom({0,1,2,3,4,5});
    graph.AddEdgesToNode(0, {{1, 3}, {4, 1}, {3, 6}}, false);
    graph.AddEdgesToNode(1, {{0, 3}, {4, 5}, {2, 3}}, false);
    graph.AddEdgesToNode(2, {{1, 3}, {4, 6}, {5, 6}}, false);
    graph.AddEdgesToNode(3, {{0, 6}, {4, 5}, {5, 2}}, false);
    graph.AddEdgesToNode(4, {{1, 5}, {2, 6}, {0, 1}, {3, 5}, {5 ,4}}, false);
    graph.AddEdgesToNode(5, {{2, 6}, {4, 4}, {3, 2}}, false);
    // Ok now Prim's
    // We need a list of discovered nodes to ensure we don't have any cycles (N = E - 1)
    // Getting the smallest node as the starting point.
    int minimum_node = graph.GetNodesData()[0];
    for (int i = 1; i < graph.GetNodesData().size(); ++i) {
        if (graph.GetNodesData()[i] < minimum_node) {
            minimum_node = graph.GetNodesData()[i];
        }
    }
    // Now performing Prim's, we will have to run this n-1 times.
    Graph minimum_spanning_tree;
    minimum_spanning_tree.AddNode(minimum_node);
    std::vector<std::tuple<int, Edge>> edge_vector;
    std::vector<std::tuple<int, Edge>> temp;
    for (int i = 0; i < graph.GetNodesData().size() - 1; ++i) {
        edge_vector = std::vector<std::tuple<int, Edge>>();
        temp = std::vector<std::tuple<int, Edge>>();
        for (auto node : minimum_spanning_tree.GetNodesData()) {
            for (auto edge : graph.Neighbours(node)) {
                edge_vector.emplace_back(node, edge);
            }
        }
        for (auto edge : edge_vector) {
            bool cycle = false;
            for (auto node : minimum_spanning_tree.GetNodesData()) {
                if (std::get<1>(edge).to == node) {
                    cycle = true;
                    break;
                }
            }
            if (!cycle) {
                temp.push_back(edge);
            }
        }
        std::tuple<int, Edge> minimum_edge = temp[0];
        for (int j = 1; j < temp.size(); ++j) {
            if (std::get<1>(temp[j]).weight < std::get<1>(minimum_edge).weight) {
                minimum_edge = temp[j];
            }
        }
        minimum_spanning_tree.AddNode(std::get<1>(minimum_edge).to);
        minimum_spanning_tree.AddEdge(std::get<0>(minimum_edge),
                std::get<1>(minimum_edge).to,
                std::get<1>(minimum_edge).weight, false);
    }

    minimum_spanning_tree.Debug();
    return 0;
}