Graph

Defined in include/graph.hpp

struct perfData

Struct to hold performance metrics (Total MST weight and elapsed time to calculate)

Public Members

int mstWeight

double duration

enum Algorithm

List of algorithms used in MST calculation

Values:

enumerator KRUSKAL

enumerator PRIM

template<Algorithm alg = KRUSKAL>
class Graph

Public Functions

Graph() = default

Graph(std::string &filename)

Constructor to create Graph object from a file.

Template Parameters

• alg: which algorithm to be used in MST calculation

Parameters

• filename: File that contains the adjacency list representation of graph

Graph(const char *filename)

Constructor to create Graph object from a file.

Template Parameters

• alg: which algorithm to be used in MST calculation

Parameters

• filename: File that contains the adjacency list representation of graph

perfData computeMST()

Calculate MST of the entire graph by either Kruskal’s or Prim’s based on the initialization of the graph.

Return

perfData struct that has elapsed time and MST weight

perfData recomputeMST(const Edge &e)

Update the existing MST with the additional edge provided.

Return

perfData struct that has elapsed time and MST weight

Parameters

• e: Edge to be added

struct Edge

Struct to hold weighted directed edge information

Public Members

unsigned src

unsigned dest

int weight