OSPF Link State (LS) Algorithm (using Dijkstra's shortest path)

ospf_dijkstra.cpp

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <queue>
#include <cstdio>
#include <unordered_set>
#include <limits>
#include <functional>

using namespace std;

// given the parent pointers and src and destination, computes a stringified path from src to destination
string construct_path(vector<int> parent, int src, int n) {
  // we will add the vertices in reverse order
  vector<int> vertices;

  // loop until we get to the source
  do {
    vertices.push_back(n);
    n = parent[n];
  } while (n != src);
  // start at the source
  vertices.push_back(src);

  // concatenate all the vertices in reverse order in a single string
  string path;
  for (auto it = vertices.crbegin(); it != vertices.crend(); it++) {
    path += to_string(*it);

    // add arrow if it's not the last vertex
    if (it != vertices.crend() - 1) {
      path += " --> ";
    }
  }

  return path;
}

void run_dijkstra(int src, int num_routers, const vector<vector<int>>& costs) {
  const int N = costs.size();

  // min known distances to each node
  vector<int> dist(N, numeric_limits<int>::max());
  dist[src] = costs[src][src];

  // parent pointers for each node, with a default sentinel value.
  vector<int> parent(N, -1);
  parent[src] = src;

  // comparator function for the min heap priority queue
  auto comp = [&](const int A, const int B) {
    return dist[A] > dist[B];
  };

  // min_heap to greedily get shortest distance yet
  priority_queue<int, vector<int>, function<bool(int, int)>> min_heap(comp);
  min_heap.push(src);

  // counts already visited nodes
  unordered_set<int> visited;

  // run the Dijkstra algorithm
  while (!min_heap.empty()) {
    // pop heap
    int node = min_heap.top();
    min_heap.pop();

    // mark node as visited
    visited.insert(node);

    // relax all the neighboring edges
    for (int nb = 0; nb < num_routers; nb++) {
      if (nb == node) continue; // skip self
      if (costs[node][nb] == -1) continue; // skip edges that don't exist

      // check if this path is shorter i.e. going to nb via 'node'
      int candidate_distance = dist[node] + costs[node][nb];

      // if distances to the current neighbor is infinity
      if (dist[nb] == numeric_limits<int>::max()) {
        // this is the min cost
        dist[nb] = candidate_distance;
      } else {
        // either use current distance, or go through node
        dist[nb] = min(dist[nb], candidate_distance);
      }

      // in any case, if we chose this path, update parent
      if (dist[nb] == candidate_distance) {
        parent[nb] = node;
      }

      // push neighbor into queue
      if (visited.count(nb) == 0) min_heap.push(nb);
    }
  }

  // Summarize results
  for (int n = 0; n < num_routers; n++) {
    printf("%d --> %d\n", src, n);
    printf("Path cost: %d\n", dist[n]);
    printf("Path taken: %s\n\n", construct_path(parent, src, n).c_str());
  }
}

int main() {
  printf("OSPF Link-State Routing:\n");
  printf("Please read the README first.\n");
  printf("-----------------------------\n");

  /* Grab input from the user */
  int num_routers; // total number of routers
  printf("Enter the number of routers: ");
  cin >> num_routers;

  string fname; // filename
  printf("Enter the filename with cost matrix values: ");
  cin >> fname;

  int source; // starting router
  printf("Enter the source router (between 0 and %d): ", num_routers - 1);
  cin >> source;

  // check if router index is in bounds
  if (source < 0 || source >= num_routers) {
    printf("Error: Please enter a valid router index between 0 and %d\n", num_routers - 1);
    return 1;
  }

  // open the file, handle errors
  fstream input(fname);
  if (input.fail()) {
    printf("Error: Could not open the file '%s'. Make sure it exists.\n", fname.c_str());
    return 1;
  }

  /* parse file into cost matrix of size num_routers x num_routers */
  vector<vector<int>> costs(num_routers, vector<int>(num_routers, -1));
  for (int i = 0; i < num_routers; i++) { // i = row
    // read a single line
    string line;
    getline(input, line);

    // parse the line
    int current;
    int next = -1;
    int j = 0; // column
    do
    {
      current = next + 1;
      next = line.find_first_of(' ', current);
      try {
        costs[i][j++] = stoi(line.substr(current, next - current));
      } catch (...) {
        printf("Error: Please ensure that your file has the right number of lines, and no extra spaces at the end of each line\n");
        return 1;
      }
    }
    while (next != string::npos);
  }

  run_dijkstra(source, num_routers, costs);
}