Skip to content

Instantly share code, notes, and snippets.

@Roytangrb

Roytangrb/dijkstra_prim.cpp

Last active December 9, 2020 15:42
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Roytangrb/3bcec95ae5833c8bb0a5748c8a240e40 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Roytangrb/3bcec95ae5833c8bb0a5748c8a240e40 to your computer and use it in GitHub Desktop.
Download ZIP
Implement Dijsktra's & Prim's algorithms
Raw
dijkstra_prim.cpp
// Implement Dijsktra's algorithm, calc avg shortest path length & MST
// By RT
// 9th Dec, 2020
#include <iostream>
#include <chrono>
#include <random>
#include <vector>
#include <iterator>
#include <fstream>
using namespace std;
class graph {
private:
int edges_count;
int max_cost;
vector< vector<int> > matrix; // using connectivity matrices implementation
public:
graph(
double density = 0.1,
int min_cost = 1,
int max_cost = 10,
int n = 50 //number of vertices
): max_cost(max_cost), matrix(n, vector<int>(n, 0)) {
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
default_random_engine gen(seed);
uniform_int_distribution<int> cost_distribution(min_cost, max_cost);
uniform_real_distribution<double> prob_distribution(0.0, 1.0);
//generate the random graph with density and cost in given range
edges_count = 0;
for (int i = 0; i < n; i ++){
for (int j = 0; j < n; j ++){
if (i != j && prob_distribution(gen) < density){
matrix[i][j] = matrix[j][i] = cost_distribution(gen);
edges_count++;
}
}
}
}
graph(const char* filename) {
ifstream data_file(filename);
istream_iterator<int> start(data_file), end;
// read first int and move cursor by 1
int n = *start++;
cout << "node size of graph input is : " << n << endl;
for (int i = 0; i < n; i ++) {
vector<int> row(n, 0);
matrix.push_back(row);
}
max_cost = 0;
edges_count = 0;
while (start != end) {
int i = *start++;
int j = *start++;
int cost = *start++;
cout << "(" << i << ", " << j << ", " << cost << ")" << endl;
if (cost > max_cost) max_cost = cost;
edges_count++;
matrix[i][j] = matrix[j][i] = cost;
}
}
friend ostream& operator<<(ostream& os, const graph& g);
int get_mst() {
int n = this->get_vertices_count();
int mst = 0;
// Prim's algorithm
vector<int> min_cost_to(n, max_cost+1); // cheapest cost to reach i
vector<int> visited(n, 0);
vector<int> visited_from(n, -1);
//start with first vertex
min_cost_to[0] = 0;
for (int count = 0; count < n; count ++) {
// find the cheapest not visited vertex to visit each time
int v = 0, min_cost = this->max_cost + 1;
for (int i = 0; i < n; i++) {
if (min_cost_to[i] < min_cost && !visited[i]){
v = i;
}
}
visited[v] = 1; // mark as visited
mst += min_cost_to[v];
for (int to = 0; to < n; to ++) {
if (to != v && !visited[to] && this->adjacent(v, to) && this->adjacent(v, to) < min_cost_to[to]){
min_cost_to[to] = this->adjacent(v, to); //update adjacent vertex cost to the spanning tree
visited_from[to] = v;
}
}
}
// check if all vertex is visited
for (int i = 0; i < n; i++){
if (!visited[i]){
cout << "Graph is not connected";
return 0;
}
}
//construct mst edges
cout << "MST edges (i, j, cost): " << endl;
for (int i = 1; i < n; i++){ //ignore start vertex
cout << "(" << i << ", " << visited_from[i] << ", " << min_cost_to[i] << ")" << endl;
}
cout << "total cost: " << mst << endl;
return mst;
}
double get_avg_path_length(){
int n = this->get_vertices_count();
// Dijsktra's algorithm
int shortest_paths_to[n];
int visited[n];
for (int i = 0; i < n; i++){
// max cost + 1 as initial value, store distance from 0 to i
shortest_paths_to[i] = this->max_cost+1;
// init all as not visited
visited[i] = 0;
}
// graph is random, pick vertex 0 as start, set distance to itself as 0
shortest_paths_to[0] = 0;
// pick a not visited vertex has min distance to start vertex each time
for (int count = 0; count < n; count ++){
int v = 0, min_distance = this->max_cost + 1;
for (int i = 0; i < n; i++) {
if (shortest_paths_to[i] < min_distance && !visited[i]){
v = i;
}
}
visited[v] = 1; // mark as visited
// update min distance by visiting adjacent vertes
for (int i = 0; i < n; i++){
// update shortest_paths_to[i] only if visiting i through v is shorter than current min
if (
!visited[i] &&
this->adjacent(v, i) &&
shortest_paths_to[v] + this->adjacent(v, i) < shortest_paths_to[i]
) {
shortest_paths_to[i] = shortest_paths_to[v] + this->adjacent(v, i);
}
}
}
// calc avg path length, ignore path to self and unreachable vertices
double avg = 0.0;
int path_count = 0;
for (int i = 0; i < n; i++){
// ignore min distance not updated -> unreachable
if (shortest_paths_to[i] < this->max_cost + 1){
avg += (shortest_paths_to[i] - avg) / (1 + path_count++);
}
}
return avg;
}
int get_vertices_count() const {
return matrix.size();
}
int get_edges_count() const {
return edges_count;
}
// return cost of edge, if not exists, return 0 (false)
int adjacent(int x, int y) const {
return matrix[x][y];
}
~graph(){
// members allocate on the stack
// should be realeased automatically
}
};
// print graph by overloading cout <<
ostream& operator<<(ostream& os, const graph& g) {
int n = g.get_vertices_count();
for (int i = 0; i < n; i ++){
for (int j = 0; j < n; j ++){
os << g.adjacent(i, j) << ", ";
}
os << endl;
}
return os;
}
int main(void) {
graph *graph_density_20 = new graph(0.2);
double avg_path_length1 = graph_density_20->get_avg_path_length();
cout << "Avg path length for density 20% graphc: " << avg_path_length1 << endl;
graph *graph_density_40 = new graph(0.4);
double avg_path_length2 = graph_density_40->get_avg_path_length();
cout << "Avg path length for density 40% graphc: " << avg_path_length2 << endl;
delete graph_density_20;
delete graph_density_40;
graph mst_graph("mst_data.txt");
cout << mst_graph << endl;
mst_graph.get_mst();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment