Bridges-C++ 3.5.0-dev2-1-ge3e57bf
Bridges(C++ API)
BFSBenchmark.h
Go to the documentation of this file.
1#ifndef BFS_BENCHMARK_H
2#define BFS_BENCHMARK_H
3
4#include <LineChart.h>
5#include <limits>
6#include <vector>
7#include <chrono>
8#include <stdlib.h>
9#include <iostream>
10#include <GraphBenchmark.h>
11
12namespace bridges {
13 namespace benchmark {
14 using namespace bridges::datastructure;
15
44 private:
45 LineChart& plot;
46
47 public:
49 : plot (p) {
50 p.setXLabel("Number of Edges");
51 p.setYLabel("Runtime (in s)");
52
53 }
54
61 void run(std::string algoName,
62 void (*bfsalgo)(const GraphAdjList<std::string>& gr,
63 std::string root,
64 std::unordered_map<std::string, int>& level,
65 std::unordered_map<std::string, std::string>& parent)) {
66 std::vector<double> time;
67 std::vector<double> vtxCounts;
68 std::vector<double> edgeCounts;
69
70 for (int years = 0; years < 120; years = 1.2 * years + 1) {
71 int year = 2019 - years;
72 std::cerr << "*" << std::flush;
74 long vertexCount;
75 long edgeCount;
76 std::tie(vertexCount, edgeCount) = generateWikidataMovieActor(year, 2019, graph);
77
78 std::string root = highestDegreeVertex(graph);
79
80 std::unordered_map<std::string, int> level;
81 std::unordered_map<std::string, std::string> parent;
82
83 std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now();
84
85 bfsalgo(graph, root, level, parent);
86
87 std::chrono::time_point<std::chrono::system_clock> end = std::chrono::system_clock::now();
88
89 std::chrono::duration<double> elapsed_seconds = end - start;
90
91 time.push_back ((double)elapsed_seconds.count() );
92 vtxCounts.push_back ( (double)vertexCount );
93 edgeCounts.push_back ( (double)edgeCount );
94
95 if (elapsed_seconds.count() > time_cap) {
96 break;
97 }
98 }
99 plot.setXData(algoName, edgeCounts);
100 plot.setYData(algoName, time);
101 std::cerr << "\n" << std::flush;
102 }
103 };
104 }
105}
106
107#endif
Benchmarks Breadth First Search algorithms.
Definition: BFSBenchmark.h:43
void run(std::string algoName, void(*bfsalgo)(const GraphAdjList< std::string > &gr, std::string root, std::unordered_map< std::string, int > &level, std::unordered_map< std::string, std::string > &parent))
benchmark one implementation
Definition: BFSBenchmark.h:61
BFSBenchmark(LineChart &p)
Definition: BFSBenchmark.h:48
Base class for a variety of graph based benchmark.
Definition: GraphBenchmark.h:15
double time_cap
Definition: GraphBenchmark.h:17
std::string highestDegreeVertex(GraphAdjList< std::string > &gr)
Definition: GraphBenchmark.h:57
std::tuple< long, long > generateWikidataMovieActor(int yearmin, int yearmax, GraphAdjList< std::string > &moviegraph)
Definition: GraphBenchmark.h:23
This class provides methods to represent adjacency list based graphs.
Definition: GraphAdjList.h:110
Show series of data or functions using a line chart.
Definition: LineChart.h:43
void setYData(string series, vector< double > ydata)
Changes the Y data for a series.
Definition: LineChart.h:234
void setXData(string series, vector< double > xdata)
Changes the X data for a series.
Definition: LineChart.h:214
Definition: Array.h:9
these methods convert byte arrays in to base64 codes and are used in BRIDGES to represent the color a...
Definition: alltypes.h:4