#include <memory>
#include <chrono>
#include <unistd.h>
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace std;
using namespace boost;
using std::chrono::steady_clock;
using namespace std::chrono;
typedef adjacency_list < vecS, vecS, undirectedS,
no_property, property < edge_weight_t, int > > graph_t;
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
typedef pair<int, int> Edge;
typedef struct Data
{
int n, m;
int src;
vector<Edge> edges;
vector<int> weights;
} Data;
void print_elapsed_time(steady_clock::time_point start, steady_clock::time_point end)
{
double elapsedSeconds = ((end - start).count()) * steady_clock::period::num / static_cast<double>(steady_clock::period::den);
printf("%lf\n", elapsedSeconds);
}
auto capture()
{
FILE *fichier=fopen("test_6000.in", "r");
auto pdata=make_unique<Data>();
int m, n, src;
fscanf(fichier,"%d %d %d", &n, &m, &src);
pdata->n=n;
pdata->m=m;
pdata->src=src;
for (int i=0; i<m; i++)
{
int a, b, w;
fscanf(fichier,"%d %d %d", &a, &b, &w);
(pdata->edges).push_back(make_pair(a, b));
(pdata->weights).push_back(w);
}
return pdata;
}
void test_dijkstra(Edge *edge_array, int *weights, int n, int m, int src)
{
auto start1 = steady_clock::now();
graph_t g(edge_array, edge_array + m, weights, n);
auto end1 = steady_clock::now();
printf("Buildin graph: ");
print_elapsed_time(start1, end1);
auto start2 = steady_clock::now();
vector<vertex_descriptor> p(num_vertices(g));
vector<int> d(num_vertices(g));
vertex_descriptor s = vertex(src, g);
auto end2 = steady_clock::now();
printf("Descriptor: ");
print_elapsed_time(start2, end2);
auto start3 = steady_clock::now();
dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));
auto end3 = steady_clock::now();
printf("Dijkstra: ");
print_elapsed_time(start3, end3);
// graph_traits < graph_t >::vertex_iterator vi, vend;
// for (tie(vi, vend) = vertices(g); vi != vend; ++vi) {
// printf("%lu %d\n", *vi, d[*vi]);
// }
}
int main (void)
{
auto pdata=capture();
auto data=*pdata;
auto edges=data.edges;
auto weights=data.weights;
auto pedges=&edges[0];
auto pweights=&weights[0];
int n, m, src;
n=data.n;
m=data.m;
src=data.src;
printf("Number of edges: %lu\n", edges.size());
auto start = steady_clock::now();
test_dijkstra(pedges, pweights, n, m, src);
auto end = steady_clock::now();
printf("Whole: ");
print_elapsed_time(start, end);
return 0;
}
