Transcribed TextTranscribed 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

Solution PreviewSolution Preview

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;

    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;

By purchasing this solution you'll be able to access the following files:

for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Computer Science - Other Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats