CSE 331 – Project 4 Weighted Digraphs
TA: Emily Ribando-Gros, ribandog@msu.edu
Office Hours: Tues 8:00 -10:00 pm and Thurs 4:00 – 6:00 pm EST https://msu.zoom.us/j/651112624
Due Date: 11:59 pm April 19, 2020
1 Project Description
In this project, you will complete an implementation of a weighted directed graph, or digraph. You are given starter code (i.e., main.cpp) that reads inputs and prints outputs as well as a class declaration for a weighted digraph in WeightedDigraph.h and stub implementation in WeightedDigraph.cpp. Your job is to complete the implementation of the following methods in the WeightedDigraph class:
1. InsertArc: Adds an arc of the given weight between the two vertices.
2. DoesPathExist: Checks whether a directed path exists between two vertices.
3. IsPathValid: Determines whether an arc exists along each step of the path.
4. GetPathWeight: Finds the sum weight of a directed path. You may assume that the input is a valid path.
5. FindMinimumWeightedPath: Finds a path of minimum sum weight between two vertices using Dijk- stra’s algorithm. For your reference, Dijkstra’s algorithm can be found on page 392 of our textbook [Weiss, 2014] and in lecture 11.
1.1 Implementation details
• Digraph storage
You may use any classes from the STL that you need to store your digraph. For example you can use vector
• Digraph immutability
InsertArc is the only method that is not marked const and it is a private method. As such, once constructed, your digraph will be immutable. You will lose points if you modify the digraph declaration such that it is not immutable.
• Time and memory requirements
Let V be the set of vertices and A the set of arcs for an input digraph. Your digraph memory requirements must be O(|V | + |A|). InsertArc must run in constant time. GetPathWeight and IsPathValid should run in time linear in the length of the input list. Each of them should use a fixed amount of extra memory. DoesPathExist should use at most O(|A|) time and O(|V |) extra memory. FindMinimumWeightedPath should use O(|A| log |V |) time and O(|V | + |A|) extra memory.
1
2
3
Project Deliverables
•
•
Input assumptions
You may assume that there are no negative weights in the digraph. You may assume that the input paths for GetPathWeight and IsPathValid are non-empty (contain at least two vertices). You may not assume that all of the arcs in the path exist. You may assume that FindMinimumWeightedPath will only be called if a path exists.
Testing notes
Not all of the above methods are directly tested by the supplied test harness in main.cpp described in the next section. However, you will probably want to use the untested methods to implement the tested ones. It is your responsibility to ensure that all of the required methods work properly.
Testing with main.cpp
The program has three inputs.
1. The first is a file containing the digraph.
• The first line of the file contains the number of vertices in the graph.
• Each remaining line contains three values separated by spaces which represent an arc. The first is the source vertex for the arc. The second is the destination vertex of the arc. The third is the arc weight.
2. The second is the source vertex index.
3. The third is the destination vertex index.
The main.cpp first constructs a digraph from the input file. Next, it will determine if a path from the source vertex to the destination vertex exists. If so, it will find such a path of minimum weight and compute its weight. Please see Figure 1 for a sample test.
5
0 1 5.0 0 2 2.0 2 3 2.0 1 3 3.0 4 1 2.5 4 3 3.5
(a) g1.txt
>./wgraph input/g1 . txt 0 3
The graph has 5 vertices and 6 arcs Path from 0 to 3:
0 −> 2 −> 3
Path weight : 4
>./wgraph input/g1 . txt 3 0
The graph has 5 vertices and 6 arcs No path from 3 to 0 exists!
(c) Sample input and output
(b) Visual representation of g1
Figure 1: Sample test
The following files must be submitted to Mimir no later than 11:59 pm April 19, 2020.
1. WeightedDigraph.h – contains the declaration for the WeightedDigraph class.
2. WeightedDigraph.cpp – contains your implementation of the WeightedDigraph class.
2