#ifndef NETWORK #define NETWORK #include<vector> using std::vector; #include<uti
ID: 3805033 • Letter: #
Question
#ifndef NETWORK
#define NETWORK
#include<vector>
using std::vector;
#include<utility>
using std::pair;
#include<string>
using std::string;
#include<fstream>
using std::ifstream;
#include<map>
using std::map;
struct Node{
int x;
int y;
string label;
Node()=default;
Node(int i, int j, string l) : x(i), y(j), label(l) {} ;
string to_string () const;
bool equal_nodes(const Node&);
double distance(const Node &)const;
};
struct Network{
string label;
map<string, Node> nodes;
vector<string> route;
Network()=default;
Network(ifstream &);
string to_string () const;
Node get_node(string);
void put_node(Node);
bool in_route(const Node&);
Node closest(Node &);
string calculate_route(const Node&, const Node&);
};
#endif
The Problem
Imagine that you are one of a number of people in a large shopping mall when all the wireless access points go out. Is it still possible to at least get a message via your phone to someone still in the mall?
The answer would be yes if you could set up what is called an "ad hoc" network. Such a network establishes a route between phones (or more generally, nodes) by passing a message from the source phone, through a series of other phones, to the destination phone. We are going to simulate (to some extent) creating an ad hoc network and creating routes through existing phones/nodes.
Basic Premise
The way this will work is as follows. The "network" knows (via GPS) the x,y location of all the other phones in the mall1. When the source phone sends a message, the networ establishes a route from the source phont to the destination phone using what is typically called a greedy method. A greedy method uses a simple rubric to solve a problem. In this case the rubric is that each step in the route is from the current phone (whatever the current phone is in the route being established) to the next phone that is closest in x,y coordinates. Note this is not a guarantee to create the shortest route to the destination, but it is a reasonable way to establish "which phone/node comes next" in the route.
Two structs
struct Node{ int x;
int y;
string label;
Node()=default;
Node(int i, int j, string l) : x(i), y(j), label(l) { } ;
string to_string () const;
bool equal_nodes(const Node&); double distance(const Node &)const;
};
struct Network{
string label;
map<string, Node> nodes; vector<string> route;
Network()=default;
Network(ifstream &);
string to_string () const;
Node get_node(string);
bool in_route(const Node&);
Node closest(Node &);
string calculate_route(const Node&, const Node&); string route_string();
};
A Node has an int x and int y 2D coordinate, as well as a string label.
1 This is an unreasonable assumption, but for now it makes our job easier so we go with it.
A Network has a string label and map<string, Node> nodes, mapping the label of each Node in the network to the actual Node. Thus the Network knows all the nodes in the network. Finally, a Network has a vector<string> route which is a sequence of node labels for a requested route.
Your Tasks
Your job is to complete the underlined methods above (all methods, no functions) in the two structs.
Node functions
string to_string () const; Converts a Node to a string. See the test cases for the format. The const at the end means the method is guaranteed not to change the variable pointed to by this.
double distance(const Node &)const Returns the Euclidean distance between two Nodes (look it up).
bool equal_nodes(const Node&) You cannot use the standard comparison operator == (and by extension != ) to check whether two nodes are equal. You can assume that two Nodes are equal if their labels are the same. This will come in handy.
Network functions
• Network(ifstream &) constructor.
o reads in a text description of the network from the provided (open) file stream
o for each line, creates a new Node and initializes it according to the provided Node
constructor (see test cases for format)
o adds the new node to the map<string, Node> nodes, where the string is the Node
label.
string to_string () const Prints all the nodes in nodes of net. Uses
Node::to_string. See test cases for format.
Node get_node(string) and void put_node(Node). Either return a Node (based on a
string, the label of a node in the map nodes) or adds a Node to the map nodes in a network.
o If get_node cannot find the indicated label in the nodes map, it throws an
out_of_range error
bool in_route(const Node &node) Useful to know if node is already in a network's
route vector. If so, then don't use that node in the route (it will create a cycle if you do).
Node closest(Node &n) For a given node n, return the closest node in the network (excluding
n itself) in terms of Euclidean distance.
string calculate_route(const Node &start, const Node &finish) Calculates a route from start to finish in the network. Returns a string with the total distance covered and the sequence of node labels in the route (see the test cases for format).
Test Cases
Test cases are provided in the subdirectory test of the project directory (because it is getting confusing), at least one for each function . However! It is time you start writing your own tests. The tests I provide are not complete, and we are free to write extra tests for grading purposes. Do a good job and test your code. Just because you pass the one (probably simple) test does not necessarily mean your code is fine. Think about your own testing!!!!
Assignment Notes
1. You are given the following files:
main.cpp – This file includes the main function where the test cases will be run. Do not modify this file.
functions.h – This file is the header file for your functions.cpp file. Do not modify this file.
input#.txt – These are text files that will be used to run the test cases.
correct_output_#.txt – These text files will be used to grade your output based on the corresponding input files. Be sure that your output matches these text files exactly to
get credit for the test cases.
You will write only functions.cpp and compile that file using functions.h and
main.cpp in the same directory (as you have done in the lab). You are only turning in
functions.cpp for the project.
Comparing outputs: You can use redirected output to compare the output of your program to
the correct output. Use redirected output and the “diff” command in the Unix terminal to accomplish this:
Run your executable on the desired input file. Let’s assume you’re testing input1.txt, the first test case. Redirect the output using the following line when in your proj06 directory: ./a.out < input1.txt > output1.txt
Now your output is in the file output1.txt. Compare output1.txt to correct_output1.txt using the following line: diff output1.txt correct_output1.txt
If the two files match, nothing will be output to the terminal. Otherwise, “diff “will print the two outputs.
----------main.cpp----------
#include<iostream>
using std::cout; using std::endl; using std::cin; using std::ostream;
using std::boolalpha;
#include<iomanip>
using std::setprecision;
#include<vector>
using std::vector;
#include<map>
using std::map;
#include<utility>
using std::pair; using std::make_pair;
#include<string>
using std::string; using std::getline;
#include<algorithm>
using std::copy; using std::sort; using std::transform;
#include<iterator>
using std::ostream_iterator;
#include<fstream>
using std::ifstream;
#include<sstream>
using std::istringstream; using std::ostringstream;
#include<stdexcept>
using std::out_of_range;
#include<cmath>
#include "functions.h"
int main(){
cout << boolalpha;
int test_no;
cin >> test_no;
switch(test_no){
case 1:{
Node n(10,10,"temp");
cout << n.to_string() << endl;
break;
}
case 2:{
Node n1(10,10, "tens");
Node n2(20, 20, "twentys");
cout << n1.equal_nodes(n2) << endl;
cout << n1.equal_nodes(n1) << endl;
break;
}
case 3:{
Node n1(10,10, "tens");
Node n2(20, 20, "twentys");
cout << n1.distance(n2) << endl;
break;
}
case 4:{
string fname;
cin >> fname;
ifstream fin(fname);
Network net(fin);
Node n = net.nodes["A"];
cout << n.to_string() << endl;
break;
}
case 5:{
string fname;
cin >> fname;
ifstream fin(fname);
Network net(fin);
cout << net.to_string() << endl;
break;
}
case 6:{
string fname;
cin >> fname;
ifstream fin(fname);
Network net(fin);
Node n1, n2;
try{
n1 = net.get_node("A");
n2 = net.get_node("X");
}
catch (out_of_range &e){
cout << "Error:"<< e.what() << endl;
}
cout << n1.to_string() << endl;
break;
}
case 7:{
Network net;
net.put_node( Node(10,10,"tens") );
net.put_node( Node(20, 20, "twentys") );
cout << net.to_string() << endl;
net.put_node( Node(100, 100, "tens") );
cout << net.to_string() << endl;
break;
}
case 8:{
Network net;
Node n1(10,10,"tens");
Node n2(100, 100, "hundreds");
net.route={"tens", "twentys"};
cout << net.in_route(n1) << endl;
cout << net.in_route(n2) << endl;
break;
}
case 9:{
string fname;
cin >> fname;
ifstream fin(fname);
Network net(fin);
auto n = net.get_node("A");
auto close = net.closest(n);
cout << close.to_string() << endl;
cout << close.distance(n) << endl;
break;
}
case 10:{
string fname;
cin >> fname;
ifstream fin(fname);
Network net(fin);
Node n1 = net.get_node("A");
Node n2 = net.get_node("D");
cout << net.calculate_route(n1,n2) << endl;
break;
}
}// of switch
} // of main
----------main.cpp ends----------
----------functions.h----------
#ifndef NETWORK
#define NETWORK
#include<vector>
using std::vector;
#include<utility>
using std::pair;
#include<string>
using std::string;
#include<fstream>
using std::ifstream;
#include<map>
using std::map;
struct Node{
int x;
int y;
string label;
Node()=default;
Node(int i, int j, string l) : x(i), y(j), label(l) {} ;
string to_string () const;
bool equal_nodes(const Node&);
double distance(const Node &)const;
};
struct Network{
string label;
map<string, Node> nodes;
vector<string> route;
Network()=default;
Network(ifstream &);
string to_string () const;
Node get_node(string);
void put_node(Node);
bool in_route(const Node&);
Node closest(Node &);
string calculate_route(const Node&, const Node&);
};
#endif
struct Node{ int x;
int y;
string label;
Node()=default;
Node(int i, int j, string l) : x(i), y(j), label(l) { } ;
string to_string () const;
bool equal_nodes(const Node&); double distance(const Node &)const;
};
struct Network{
string label;
map<string, Node> nodes; vector<string> route;
Network()=default;
Network(ifstream &);
string to_string () const;
Node get_node(string);
bool in_route(const Node&);
Node closest(Node &);
string calculate_route(const Node&, const Node&); string route_string();
};
Explanation / Answer
Given below is the implmentation of the functions.cpp. Since the question does not show exactly the output format, the output format may not match. Please tweak the output as needed. Also since the input file format is not shown, I assumed each line to be x y label format. Given below is the sample file I tested with. If the input file format is anything different from the assumption, please tweak the constructor of Network to load it correctly (i.e the order of reading )
functions.cpp
#include "functions.h"
#include <cmath>
using namespace std;
string Node::to_string () const
{
return label + "(" + std::to_string(x) + "," + std::to_string(y) +")";
}
bool Node::equal_nodes(const Node& n2)
{
return label == n2.label;
}
double Node::distance(const Node &n2)const
{
int dx = x - n2.x, dy = y - n2.y;
return sqrt(dx * dx + dy * dy);
}
//..........Network Functions
Network::Network(ifstream &ifs)
{
string label;
int x, y;
while(ifs >> x)
{
ifs >> y >> label;
put_node(Node(x, y, label));
}
ifs.close();
}
string Network::to_string () const
{
string str = "";
for(map<string, Node>::const_iterator it = nodes.begin(); it != nodes.end(); it++ )
{
str = str + (*it).second.to_string() + " ";
}
return str;
}
Node Network::get_node(string label)
{
return nodes.at(label);
}
void Network::put_node(Node n)
{
nodes[n.label] = n;
}
bool Network::in_route(const Node& n2)
{
for(int i = 0; i < route.size(); i++)
if(route[i] == n2.label)
return true;
return false;
}
Node Network::closest(Node &n1)
{
double minDist = -1;
string closest;
double dist;
for(map<string, Node>::iterator it = nodes.begin(); it != nodes.end(); it++ )
{
Node n2 = (*it).second;
if(n1.equal_nodes(n2) || in_route(n2))
continue;
dist = n1.distance(n2);
if(minDist == -1 || dist < minDist)
{
minDist = dist;
closest = n2.label;
}
}
return nodes[closest];
}
string Network::calculate_route(const Node &n1, const Node &n2)
{
route.clear();
//make sure they are in the network
get_node(n1.label);
get_node(n2.label);
route.push_back(n1.label);
string last = n1.label;
double distance = 0;
while(true)
{
Node n3 = closest(nodes[last]);
if(n3.label == "" )
throw std::out_of_range("Out of range " + n2.to_string());
route.push_back(n3.label);
distance += nodes[last].distance(n3);
if(n3.equal_nodes(n2))
break;
last = n3.label;
}
string str = "Total distance = " + std::to_string(distance) +" ";
str += "Route = " ;
for(int i = 0; i < route.size(); i++)
str += route[i] + " ";
return str;
}
input file: net.txt
4 5 A
8 9 B
7 7 C
10 12 D
output
$ g++ -std=c++11 functions.cpp phone_main.cpp
$ ./a.out
1
temp(10,10)
$ ./a.out
2
false
true
$ ./a.out
3
14.1421
$ ./a.out
4
net.txt
A(4,5)
$ ./a.out
5
net.txt
A(4,5)
B(8,9)
C(7,7)
D(10,12)
$ ./a.out
6
net.txt
Error:map::at: key not found
A(4,5)
$ ./a.out
7
tens(10,10)
twentys(20,20)
tens(100,100)
twentys(20,20)
$ ./a.out
8
true
false
$ ./a.out
9
net.txt
C(7,7)
3.60555
$ ./a.out
10
net.txt
Total distance = 9.447171
Route = A C B D
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.