- [X] constructors for declaring and initializing a graph
- [X] Have a procedure that produces a randomly generated set of edges with positive distances
- [X] The random graph procedure should have edge density as a parameter and distance range as a parameter. So a graph whose density is 0.1 would have 10% of its edges picked at random and its edge distance would be selected at random from the distance range. The procedure should run through all possible undirected edges, say (i,j) and place the edge in the graph if a random probability calculation is less than the density
- [X] Compute for a set of randomly generated graphs an average shortest path
- [ ] Printout of program, 200 words on what you learned, and output showing the average path length calculation.
- [ ] Use densities: 20% and 40% on a graph of 50 nodes with a distance range of 1.0 to 10.0. To get an average path length, compute the 49 paths: 1 to 2, 1 to 3, 1 to 4, …, 1 to 50. In an instance where there is no path between 1 and n, omit that value from the average
- [X] Graph (G = (V, E)
- [X] PriorityQueue
- [X] ShortestPath algorithm.
- [X] V (G): returns the number of vertices in the graph
- [X] E (G): returns the number of edges in the graph
- [X] adjacent (G, x, y): tests whether there is an edge from node x to node y.
- [X] neighbors (G, x): lists all nodes y such that there is an edge from x to y.
- [X] add (G, x, y): adds to G the edge from x to y, if it is not there.
- [X] delete (G, x, y): removes the edge from x to y, if it is there.
- [X] get_node_value (G, x): returns the value associated with the node x.
- [X] set_node_value( G, x, a): sets the value associated with the node x to a.
- [X] set_edge_value (G, x, y, v): sets the value associated to the edge (x,y) to v.
- [X] get_edge_value( G, x, y): returns the value associated to the edge (x,y).
Note in some cases such as add(G, x, y) you may also want to have the edge carry along its cost. Another approach could be to use (x, y) to index a cost stored in an associated array or map.
- [X] chgPrioirity(PQ, priority): changes the priority (node value) of queue element.
- [X] minPrioirty(PQ): removes the top element of the queue.
- [X] contains(PQ, queue_element): does the queue contain queue_element.
- [X] Insert(PQ, queue_element): insert queue_element into queue
- [X] top(PQ):returns the top element of the queue.
- [X] size(PQ): return the number of queue_elements.
- [X] path(u, w): find shortest path between u-w and returns the sequence of vertices representing shorest path u-v1-v2-…-vn-w.
- [X] path_size(u, w): return the path cost associated with the shortest path.
The class implementing your Monte Carlo simulation is the workflow manager for this assignment, but other helper classes may be necessary depending on your particular implementation
- Write an appropriate set of constructors for each of your classes ensuring proper initialization – especially think about the process for declaring and initializing a graph.
- In this implementation, assume that an edge will have a positive cost function like distance (no negative edge cost).
- Assume the graph edges (E) are undirected.
- Ensure that your ADTs support a graph of at least size 50.
- The random graph procedure should have edge density as a parameter and distance range as a parameter.
- Random graph generator should generate a sufficient set of edges to satisfy the edge density parameter, and each edge should be assigned a randomly generated cost based on the distance range parameter.
- So a graph whose density is 0.1 would have 10% of its edges picked at random and its edge distance would be selected at random from the distance range.
- Compute for a set of randomly generated graphs an average shortest path.