Fibonacci Heap Test

/*
n vertices, d density: binary_heap fibonacci_heap

512 vertices, 0.2 density: 0 0
512 vertices, 0.4 density: 0.003 0.001
512 vertices, 0.6 density: 0 0
512 vertices, 0.8 density: 0.008 0
512 vertices, 1 density: 0.016 0

1024 vertices, 0.2 density: 0 0.015
1024 vertices, 0.4 density: 0.016 0
1024 vertices, 0.6 density: 0.016 0
1024 vertices, 0.8 density: 0.022 0.016
1024 vertices, 1 density: 0.033 0.007

2048 vertices, 0.2 density: 0.017 0
2048 vertices, 0.4 density: 0.053 0
2048 vertices, 0.6 density: 0.058 0.016
2048 vertices, 0.8 density: 0.09 0.021
2048 vertices, 1 density: 0.113 0.026

4096 vertices, 0.2 density: 0.095 0.01
4096 vertices, 0.4 density: 0.171 0.056
4096 vertices, 0.6 density: 0.285 0.047
4096 vertices, 0.8 density: 0.357 0.085
4096 vertices, 1 density: 0.459 0.085

8192 vertices, 0.2 density: 0.385 0.085
8192 vertices, 0.4 density: 0.716 0.17
8192 vertices, 0.6 density: 1.116 0.263
8192 vertices, 0.8 density: 1.501 0.327
8192 vertices, 1 density: 1.946 0.406
*/

#include <iostream>
#include <queue>
#include <ctime>
#include "fibheap.h"

using namespace std;

vector<int> dijkstra(vector<vector<pair<int, int>>>& adj)
{
  priority_queue<pair<int,int>> q;
  vector<int> dist(adj.size(), -1);
  dist[0] = 0;
  q.push({0, 0});

  while( !q.empty() )
  {
    int i = q.top().second; q.pop();

    for(pair<int,int>& edge : adj[i])
      if( dist[edge.first] == -1 || dist[i] + edge.second < dist[edge.first] )
      {
        dist[edge.first] = dist[i] + edge.second;
        q.push({-dist[edge.first], edge.first});
      }
  }

  return dist;
}

vector<int> fibonacci_dijkstra(vector<vector<pair<int, int>>>& adj)
{
  fibonacci_queue<pair<int,int>> q;
  vector<int> dist(adj.size(), -1);
  vector<void*> nodes(adj.size(), NULL);
  dist[0] = 0;
  nodes[0] = q.insert({0, 0});

  while( q.size() > 0 )
  {
    int i = q.find_min().second; q.remove_min();

    for(pair<int,int>& edge : adj[i])
      if( dist[edge.first] == -1 || dist[i] + edge.second < dist[edge.first] )
      {
        dist[edge.first] = dist[i] + edge.second;
        if( nodes[edge.first] == NULL ) {
          nodes[edge.first] = q.insert({dist[edge.first], edge.first});
        } else {
          q.decrease_key(nodes[edge.first], {dist[edge.first], edge.first});
        }
      }
  }

  return dist;
}

// https://stackoverflow.com/questions/26237419/faster-than-rand
static unsigned int g_seed;

// Used to seed the generator.
inline void fast_srand(int seed) {
    g_seed = seed;
}

// Compute a pseudorandom integer.
// Output value in range [0, 32767]
inline int fast_rand(void) {
    g_seed = (214013*g_seed+2531011);
    return (g_seed>>16)&0x7FFF;
}

vector<vector<pair<int, int>>> generate_graph(int n, double density) {
  auto ret = vector<vector<pair<int, int>>>(n);
  for( int i = 0; i < n * (n-1) * density; ++i ) {
    int a = fast_rand() % n;
    int b = fast_rand() % n;
    ret[a].push_back({b, fast_rand() % 100 + 1});
    ret[b].push_back({a, fast_rand() % 100 + 1});
  }
  return ret;
}

pair<double, double> time_check(int n, double density) {
  pair<double, double> ret;

  auto graph = generate_graph(n, density);

  clock_t t1 = clock();
  vector<int> ans = dijkstra(graph);
  clock_t t2 = clock();
  ret.first = (t2-t1) / (double)CLOCKS_PER_SEC;

  t1 = clock();
  vector<int> ans2 = fibonacci_dijkstra(graph);
  t2 = clock();
  ret.second = (t2-t1) / (double)CLOCKS_PER_SEC;

  for( int i = 0; i < n; ++i ) {
    if( ans[i] != ans2[i] ) {
      return {-1, -1};
    }
  }

  return ret;
}

int main() {
  fast_srand(1234);
  cout << "n vertices, d density: binary_heap fibonacci_heap\n" << endl;
  for( int i = 512; i <= 10000; i *= 2 ) {
    for( double j = 0.2; j <= 1.1; j += 0.2 ) {
      pair<double, double> ret = time_check(i, j);
      cout << i << " vertices, " << j << " density: " << ret.first << " " << ret.second << endl;
    }
    cout << endl;
  }

  return 0;
}