## Transcribed Text

Weighted Digraphs
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 Dijkstra’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<map<int,double>> or vector<vector<pair<int,double>>>. You may modify the constructor and destructor to initialize and cleanup these structures. Note that the constructor uses
InsertArc to set up the graph. You should ensure that your structure is properly initialized before
calling InsertArc.
• 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
• 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.
2 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
(b) Visual representation of g1
>./wgraph in pu t / g1 . t x t 0 3
The graph has 5 v e r t i c e s and 6 a r c s
Path from 0 t o 3 :
0 −> 2 −> 3
Path wei gh t : 4
>./wgraph in pu t / g1 . t x t 3 0
The graph has 5 v e r t i c e s and 6 a r c s
No path from 3 t o 0 e x i s t s !
(c) Sample input and output
Figure 1: Sample test

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.

#include "WeightedDigraph.h"

#include <iostream>

#include <fstream>

#include <sstream>

#include <limits>

#include <climits>

#include <queue>

#include <climits>

#include <cfloat>

using namespace std;

/**

* Constructs the digraph from a file.

* You may add any additional construction to this section.

*/

WeightedDigraph::WeightedDigraph(const string& filename) : numVertices(0), numArcs(0) {

ifstream in(filename);

if (!in.is_open()) {

cerr << "cannot open file!" << std::endl;

exit(EXIT_FAILURE);

}

string line;

getline(in, line);

istringstream vertexStream(line);

vertexStream >> numVertices;

// TODO : You can initialize your data structure here.

graph = new vector<map<int, double>>(numVertices);

while (getline(in, line)) {

istringstream iss(line);

int u, v;

float weight;

iss >> u >> v >> weight;

InsertArc(u, v, weight);

}

}

/**

* Destructor

* You can do any needed cleanup here.

*/

WeightedDigraph::~WeightedDigraph() {

// Intentionally left empty

// You may do any needed cleanup here

// free the vector

delete graph;

}

/**

* Inserts a weighted arc into the digraph.

* This is the sole mutator of this class and it is private

* so the digraph is immutable once created.

*/

void WeightedDigraph::InsertArc(int from, int to, double weight) {

// TODO

// add to map at index from

(*graph)[from].insert({to, weight});

}

/**

* Finds the sum weight of the given path.

* Returns infinity if the path is broken.

*/

double WeightedDigraph::GetPathWeight(const list<int> & path) const {

// TODO

double weight = 0;

// init it to a big number

int from = numeric_limits<int>::max();

// for each item in path

for (auto elem : path) {

// if it isn't the first element

if (from != numeric_limits<int>::max()) {

// get iterator

// find the weight

map<int, double>::const_iterator it

= (*graph)[from].find(elem);

// if the connection isn't there

if (it == (*graph)[from].end()) {

// return infinity

return numeric_limits<int>::max();

}

weight += it->second;

}...