This C++ code implements a Graph data structure and includes various graph algorithms such as Dijkstra's shortest path algorithm and Kruskal's Minimum Spanning Tree (MST) algorithm. It is divided into two main parts: a basic graph operations section and an "additional challenge" section featuring graphs with colored edges.
The first part of this codebase is dedicated to defining and implementing a generic graph class, designed for the representation and manipulation of graph data.
At its core, the graph class utilizes an Edge struct to define individual connections within the graph. Each Edge comprises a src (source node), a dest (destination node), and a weight associated with that connection.
The graph class itself manages several private members that dictate its structure and behavior. These include density, which determines the probability of an edge being created during graph generation; minimum and maximum, which set the lower and upper bounds for randomly assigned edge weights; and size, representing the total number of nodes within the graph. The graph's structure is maintained using adjMatrix, a 2D array serving as an adjacency matrix to store the weights of the edges. A helper function, prob(), is also included to generate random floating-point numbers between 0 and 1.
The class provides two primary constructors for graph initialization. The Random Graph Constructor facilitates the creation of a graph based on specified density, minimum and maximum weight values, and a given number of nodes (defaulting to 50). In this setup, edge weights are randomly generated within the defined range, with a weight of 0 indicating the absence of an edge. Alternatively, the File Reading Constructor allows for graph construction by reading data from a specified file. In this file format, the first line denotes the total number of nodes, and subsequent lines detail individual edges in the format u v w, signifying an edge from node u to node v with a weight of w. To ensure proper memory management, a destructor is implemented to release any dynamically allocated memory associated with the adjacency matrix.
For utility and debugging, the print_graph() method is available to display the current state of the adjacency matrix. Beyond basic representation, the graph class implements key algorithms. The Dijkstra(int start_node, int end_node) method provides an implementation of Dijkstra's algorithm, designed to find the shortest path between a specified start_node and end_node. It returns the total weight of this shortest path, or std::numeric_limits::max() if the destination is unreachable. Building upon this, average_path_length(int path) calculates the average shortest path length from node 1 to all other reachable nodes in the graph, excluding unreachable nodes from the calculation. For network optimization, mst_K(vector<Edge> &mstEdges) implements Kruskal's algorithm to determine the Minimum Spanning Tree (MST) of the graph. This method systematically collects and sorts all edges by weight, then utilizes a Union-Find data structure to prevent the formation of cycles, incrementally constructing the MST. It returns the total weight of the MST and populates the mstEdges vector with the edges that comprise it.
The main() function in Part One serves as an example of how to utilize these functionalities. It demonstrates the creation of a graph by reading from a Sample_test.txt file, prints the generated graph, and then proceeds to calculate and display the total weight of the MST for this graph, along with a list of its constituent edges.
The second part of the codebase introduces an "additional challenge" by extending the basic graph concept to include a "color" attribute for its edges. This enhancement allows for more nuanced graph analysis, particularly in the context of Minimum Spanning Tree algorithms.
To accommodate this new attribute, a RoadColor enum class is defined, providing three distinct road colors: GREEN, RED, and BLUE. Furthermore, a WeightedColor struct is introduced. This struct expands upon the standard edge properties by including weight, color, and a hasEdge boolean flag, which explicitly indicates the presence or absence of an edge.
The graph class in Part Two largely mirrors its counterpart in Part One, but with a significant modification: its adjMatrix now stores WeightedColor objects, enabling the representation of colored edges. The constructor for this version of the graph is similar to the random graph constructor from Part One, but it additionally assigns a random color (either GREEN, RED, or BLUE) to each newly created edge. As with the first part, a destructor is provided to ensure proper memory deallocation.
A key algorithmic addition in this section is mst_K_color(RoadColor colorFilter, vector<Edge> &mstEdges). This method is a specialized variant of Kruskal's algorithm. Its unique feature is that it only considers edges that precisely match the specified colorFilter when constructing the Minimum Spanning Tree. The function returns the total weight of this color-filtered MST and populates the mstEdges vector with the edges that form it.
The main() function for Part Two illustrates the usage of this extended graph functionality. It begins by initializing the random number generator. Subsequently, it creates a random graph with a density of 0.2, edge weights ranging from 1.0 to 10.0, and 50 nodes. The core demonstration involves calculating and printing the total weight of the MST, specifically considering only RED colored edges, along with the details of these edges.
In summary, this codebase offers a comprehensive and flexible framework for graph processing. It covers a wide spectrum of operations, from fundamental graph generation, data reading, and basic traversal to the implementation of more sophisticated algorithms like shortest path determination and Minimum Spanning Tree calculations. The second part of the project effectively showcases how to extend graph functionalities by incorporating additional edge attributes, thereby enabling the execution of more specialized algorithmic requirements, such as color-filtered MSTs. This robust and adaptable foundation is well-suited for a diverse range of applications that involve the analysis and manipulation of network, map, or any form of relational data.