Question
Please answer with c++. sample main #include #include #include graphl.h #include graphm.h using namespace std; int main() { // part 1 ifstream infile1(data31.txt); if (!infile1)
Please answer with c++.
sample main
#include#include #include "graphl.h" #include "graphm.h" using namespace std; int main() { // part 1 ifstream infile1("data31.txt"); if (!infile1) { cout data31.txt
5 Aurora and 85th Green Lake Starbucks Woodland Park Zoo Troll under bridge PCC 1 2 50 1 3 20 1 5 30 2 4 10 3 2 20 3 4 40 5 2 20 5 4 25 0 0 0 3 aaa bbb ccc 1 2 10 1 3 5 2 3 20 3 2 4 0 0 0output.txt
Description From node To node Dijkstra's Path Aurora and 85th 1 2 40 1 3 2 1 3 20 1 3 1 4 50 1 3 2 4 1 5 30 1 5 Green Lake Starbucks 2 1 --- 2 3 --- 2 4 10 2 4 2 5 --- Woodland Park Zoo 3 1 --- 3 2 20 3 2 3 4 30 3 2 4 3 5 --- Troll under bridge 4 1 --- 4 2 --- 4 3 --- 4 5 --- PCC 5 1 --- 5 2 20 5 2 5 3 --- 5 4 25 5 4 3 1 --- Description From node To node Dijkstra's Path aaa 1 2 9 1 3 2 1 3 5 1 3 bbb 2 1 --- 2 3 20 2 3 ccc 3 1 --- 3 2 4 3 2 3 1 ---nodedata.h
#ifndef NODEDATA_H #define NODEDATA_H #include#include #include using namespace std; // simple class containing one string to use for testing // not necessary to comment further class NodeData { friend ostream & operator(const NodeData &) const; bool operator=(const NodeData &) const; private: string data; }; #endif nodedata.cpp
#include "nodedata.h" //---------------------------------------------------------------------------- // constructors/destructor NodeData::NodeData() { data = ""; } // default NodeData::~NodeData() { } // needed so strings are deleted properly NodeData::NodeData(const NodeData& nd) { data = nd.data; } // copy NodeData::NodeData(const string& s) { data = s; } // cast string to NodeData //---------------------------------------------------------------------------- // operator= NodeData& NodeData::operator=(const NodeData& rhs) { if (this != &rhs) { data = rhs.data; } return *this; } //---------------------------------------------------------------------------- // operator==,!= bool NodeData::operator==(const NodeData& rhs) const { return data == rhs.data; } bool NodeData::operator!=(const NodeData& rhs) const { return data != rhs.data; } //---------------------------------------------------------------------------- // operator,= bool NodeData::operator(const NodeData& rhs) const { return data > rhs.data; } bool NodeData::operator=(const NodeData& rhs) const { return data >= rhs.data; } //---------------------------------------------------------------------------- // setData // returns true if the data is set, false when bad data, i.e., is eof bool NodeData::setData(istream& infile) { getline(infile, data); return !infile.eof(); // eof function is true when eof char is read } //---------------------------------------------------------------------------- // operatorTo line up numbers use setw() (must #include
). For example, if n is an int, 10 chars are printed including n. Default is right justified, padding with blanks on the left: cout (When you read the size -- e.g., infile >> size; -- you need to read its end-of-line char so the next getLine() of setData works properly. To read any extra white space and the end-of-line char, use an extra getline() after reading size. And, always test for eof() on the first read attempt after the last line of real data (the data that isn't actually there) so the EOF character is read which triggers eof() to be true. )
I need graphm.h, graphm.cpp
Part 1, Programming Graph ADT (emphasis on Dijkstra's shortest path algorithm) Implement Dijkstra's shortest path algorithm, including recovering the paths. You will find the lowest cost paths and display the cost and path from every node to every other node. Another display routine will output one path in detail. In the data, the first line tells the number of nodes, say n (assume nonnegative integer). Following is a text description of each of the 1 through n nodes, one description per line (assume 50 chars max length). After that, each line consists of 3 ints representing an edge. (Assume correctly formatted data, int data.) If there is an edge from node 1 to node 2 with a label of 10, the data is: 12 10. A zero for the first integer signifies the end of the data for that one graph. There are several graphs, each having at most 100 nodes. For example: -- For this lab (including part 2,) you may assume the input data file has correctly formatted data, e.g., that there will be 3 ints on one line of data for an edge (not 4 ints or chars, etc.). You must always do data error checking, e.g., that an int you get is a valid value for the problem. Ignore invalid data, meaning don't use in graph. You may assume the first int, the number of nodes in the graph, is valid. -- Class includes the adjacency matrix, number of nodes, TableType array, and an array of NodeData. You do not need to implement a complete Graph class. The only methods you must have are the constructor, buildGraph (put in edge costs), insertEdge(), removeEdge(), findShortestPath(), displayAll() (not general output, uses couts to demonstrate that the algorithm works properly as shown), and display (to display one shortest distance with path). (Some utility functions are needed.) For insertEdge() and removeEdge(), you figure out reasonable parameters, return type and document their use. class GraphM \{ public: private: struct Tabletype \{ bool visited; // whether node has been visited int dist; // currently known shortest distance from source int path; // previous node in path of min dist \} ; NodeData data[MAXNODES]; // data for graph nodes information int C[MAXNODES] [MAXNODES]; // Cost array, the adjacency matrix int size; // number of nodes in the graph TableType T[MAXNODES][MAXNODES]; // stores Dijkstra information \} ; -- The T in Dijkstra's algorithm (has dist, visited, and path), is a 2-dimensional array of structs. T is used to keep the current shortest distance (and associated path info) known at any point in the algorithm. In lecture it was shown as onedimensional since the source was fixed at one. This is row one in the 2D array. To adjust in use, add [source] as the row. For example, T[w].dist becomes T[ source][w].dist . The data member T is initialized in the constructor (or a routine that the constructor calls): sets all dist for the source node (source row) to infinity, sets all visited to false, and sets all path to 0. -- The pseudocode given is for only one source node. Another loop, controlling the source, allows for the shortest distance from all nodes to all other nodes. (The nodes start at array element one. The zero element is not used, or used otherwise.) for (int source =1; source
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started