dijkstra-shortest-path-algorithm/graph.cpp

#include "graph.h"
#include <cstdlib>
#include <iostream>
#include <stdlib.h>

using namespace std;

// ctor
Graph::Graph(int size, float range, float density) : V(size), distance_range(range), edge_density(density)
{
    generate_graph();
    reset_path_calculation();
}

// destructor
Graph::~Graph() {}

void Graph::reset_path_calculation()
{
    // (re)initialise helper members
    unvisited = V; // reset num of unvisited nodes back to all
    src_node_dist.assign(V, INF); // assign all values to infinity
    visited.assign(V, false); // mark all nodes as yet unvisited (false)
    parents.assign(V, 0); // set all parent elements to 0
}

void Graph::generate_graph()
{
    // initialize graph with V vectors of V size
    vector<float> row(V, 0.0f);
    graph_matrix.assign(V, row);

    // walk through all combinations of nodes without repeating
    float probability; // hold the probability of edge between nodes
    float edge_rand_value; // hold the generated random value for edge

    for(int i = 0; i < V; ++i) {
        for (int j = i + 1; j < V; ++j) {
            // get random value between 0 and 1
            probability = static_cast<float>(rand()) / static_cast<float>(RAND_MAX);

            // if probability is bellow edge density, we create an edge
            if (probability < edge_density)
            {
                // generate random value between 1.0 and maximum distance limit
                edge_rand_value =
                        1.0 + static_cast<float>(rand()) / (static_cast<float>(RAND_MAX / (distance_range - 1.0)));

                // truncate digits after one decimal place
                float scale = 0.1; // round to the nearest one tenth
                edge_rand_value = (int)(edge_rand_value / scale) * scale;

                // assign edge value to (node1, node2) and (node2, node1) positions
                graph_matrix[i][j] = edge_rand_value;
                graph_matrix[j][i] = edge_rand_value;
            }
        }
    }
}

void Graph::print_graph()
{
    // red for nonzero values, green for 0.0 values
    const string red = "\033[0;31m";
    const string green = "\033[0;32m";
    const string stop = "\033[0m";

    cout.precision(1);
    for(int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            // colorize output - nonzero values in red, zeroes in green color
            if (graph_matrix[i][j] != 0)
                cout << stop << red;
            else
                cout << stop << green;

            cout << fixed << graph_matrix[i][j] << " ";
        }
        cout << "\n"; // print new line after each row
    }
    cout << stop; // reset the colouring of output after printing
}