The Problem: Imagine that you are one of a number of people in a large shopping

ID: 3805832 • Letter: T

Question

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 nodes;

vector 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.

A Network has a string label and map 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 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 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).

main.cpp

#include
using std::cout; using std::endl; using std::cin; using std::ostream;
using std::boolalpha;
#include
using std::setprecision;
#include
using std::vector;
#include
using std::map;
#include
using std::pair; using std::make_pair;
#include
using std::string; using std::getline;
#include
using std::copy; using std::sort; using std::transform;
#include
using std::ostream_iterator;
#include
using std::ifstream;
#include
using std::istringstream; using std::ostringstream;
#include
using std::out_of_range;
#include

#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

functions.h

#ifndef NETWORK
#define NETWORK

#include
using std::vector;
#include
using std::pair;
#include
using std::string;
#include
using std::ifstream;
#include
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 nodes;
vector 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

network.txt

1 1 A
2 2 B
3 3 C
4 4 D

This is my assignment and everything I am given. I need helping writing it but I am having the most trouble with the network functions. Help on all functions would be appreicated but I specifically do not have code for calculate_route, Node closest(Node &n), bool in_route, Node get_node, and Network::string_to_string().

Explanation / Answer