Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement