UCR - CS 010C
Assignment 4
Deliverables:
Create a single PDF file that contains your answers to the questions. Then create a zip file that contains this PDF file along with all your code source files. Submit this zip file on iLearn.
Deadline:
12/11/2020 11:59 pm.
Exercise 1
Use provided C++ skeleton to insert your code.
Define Graph, which stores an
undirected
graph using
adjacency list, where each node stores a CityName (string) and each edge has a double weight (distance between two cities).
Implement the following functions in Graph:
bool hasTripletClique(): returns true if there are three nodes in the graph that are all connected to each other. E.g., a, b, c, with edges (a, b), (b, c), and (a, c)
bool isConnected(): returns true if graph is connected
double getMinDistance(string city1,string city2): returns the shortest path distance between city1 and city 2. Hint: You may use Dijkstra Algorithm.
[extra credit] double getLongestSimplePath(): returns length of longest simple path (no cycle allowed)
What is the big-Oh complexity of your functions above if graph has nodes and edges?
Test your functions. Write code to create a random graph of 100 nodes, with 500 random edges with weight 1.0, 500 random edges with weight 2.0 and 500 random edges with weight 3.0. (For function in A(d) use a smaller graph if too slow.) Measure the time of each function in nanoseconds or microseconds.
Assume there can be at most 1 edge between 2 nodes.
Assume there is no self-loop (edge from one node to itself).