Data Structures and Algorithms:
Phone Towers Assignment

A phone company is planning to install microwave towers to establish a packet-switched communications network. They use three types of towers, designated by the letters A, B, and C. Type A towers are the most powerful (and hence most expensive to use), and are able to transmit 8 miles at a cost of 3c per packet. Type B towers are intermediate, and are able to transmit 5 miles at a cost of 2c per packet. Type C towers are cheap, but are able to transmit only 3 miles at a cost of 1c per packet. It costs 1c to receive a packet at any type of tower. (The tranmission and recption costs may change in the future.) A packet to be sent from a source tower to a destination tower is sent directly if the destination tower is within the transmission range of the source tower. Otherwise the packet must be sent to some other tower within the source's transmission range, and passed on to eventually reach the destination tower.

The company is now investigating where they should install what types of towers. They have divided the country up into a rectangular grid, with X and Y coordinates starting at 0. For any proposed tower configuration, they need to know:

Whether or not every tower can send a transmission to every other tower (either directly or via other towers).
The cheapest packet path between all pairs of towers, where the cost is the sum of the transmission and reception costs for the towers used.

Assignment

Write a LEDA program that uses a parameterized digraph to represent a tower configuration, and computes the required information. The program takes as input (from the keyboard) a sequence of tower records, each being the tower type and the X and Y coordinates. The sequence is terminated by a ".". Here's a sample sequence:

Each tower is a node in the graph, with the node type and coordinates as parameters. For each tower pair, you have to compute whether or not the source tower is able to transmit to the destination tower. If transmission is possible, add an edge to the graph, with the edge parameter being the total cost of using that link, i.e., the transmission cost plus the reception cost. Once created, the graph must be printed, e.g., for the sample configuration given above:

[0](A 0,0) : [0]--(4)-->[1][0]--(4)-->[2][0]--(4)-->[3][0]--(4)-->[5][0]--(4)-->[6]
[1](B 1,2) : [1]--(3)-->[0][1]--(3)-->[2][1]--(3)-->[3]
[2](A 3,0) : [2]--(4)-->[0][2]--(4)-->[1][2]--(4)-->[3][2]--(4)-->[5][2]--(4)-->[6]
[3](B 1,5) : [3]--(3)-->[1][3]--(3)-->[4]
[4](C 2,8) :
[5](C 6,4) : [5]--(2)-->[6]
[6](B 7,2) : [6]--(3)-->[2][6]--(3)-->[5]

After that, the shortest paths must be computed and output. The output must show, for each pair of towers, the cheapest path between them, the cost of each link in the paths, and the overall cost of the path. If there is no path between a pair of towers, that is indicated by the statement "NO PATH". For example, here is the output for the sample configuration given above:

A 0,0 --(4)--> B 1,2  of cost 4
A 0,0 --(4)--> A 3,0  of cost 4
A 0,0 --(4)--> B 1,5  of cost 4
A 0,0 --(4)--> B 1,5 B 1,5 --(3)--> C 2,8  of cost 7
A 0,0 --(4)--> C 6,4  of cost 4
A 0,0 --(4)--> B 7,2  of cost 4
B 1,2 --(3)--> A 0,0  of cost 3
B 1,2 --(3)--> A 3,0  of cost 3
B 1,2 --(3)--> B 1,5  of cost 3
B 1,2 --(3)--> B 1,5 B 1,5 --(3)--> C 2,8  of cost 6
B 1,2 --(3)--> A 0,0 A 0,0 --(4)--> C 6,4  of cost 7
B 1,2 --(3)--> A 0,0 A 0,0 --(4)--> B 7,2  of cost 7
A 3,0 --(4)--> A 0,0  of cost 4
A 3,0 --(4)--> B 1,2  of cost 4
A 3,0 --(4)--> B 1,5  of cost 4
A 3,0 --(4)--> B 1,5 B 1,5 --(3)--> C 2,8  of cost 7
A 3,0 --(4)--> C 6,4  of cost 4
A 3,0 --(4)--> B 7,2  of cost 4
B 1,5 --(3)--> B 1,2 B 1,2 --(3)--> A 0,0  of cost 6
B 1,5 --(3)--> B 1,2  of cost 3
B 1,5 --(3)--> B 1,2 B 1,2 --(3)--> A 3,0  of cost 6
B 1,5 --(3)--> C 2,8  of cost 3
B 1,5 --(3)--> B 1,2 B 1,2 --(3)--> A 0,0 A 0,0 --(4)--> C 6,4  of cost 10
B 1,5 --(3)--> B 1,2 B 1,2 --(3)--> A 0,0 A 0,0 --(4)--> B 7,2  of cost 10
C 2,8 --(NO PATH)--> A 0,0
C 2,8 --(NO PATH)--> B 1,2
C 2,8 --(NO PATH)--> A 3,0
C 2,8 --(NO PATH)--> B 1,5
C 2,8 --(NO PATH)--> C 6,4
C 2,8 --(NO PATH)--> B 7,2
C 6,4 --(2)--> B 7,2 B 7,2 --(3)--> A 3,0 A 3,0 --(4)--> A 0,0  of cost 9
C 6,4 --(2)--> B 7,2 B 7,2 --(3)--> A 3,0 A 3,0 --(4)--> B 1,2  of cost 9
C 6,4 --(2)--> B 7,2 B 7,2 --(3)--> A 3,0  of cost 5
C 6,4 --(2)--> B 7,2 B 7,2 --(3)--> A 3,0 A 3,0 --(4)--> B 1,5  of cost 9
C 6,4 --(2)--> B 7,2 B 7,2 --(3)--> A 3,0 A 3,0 --(4)--> B 1,5 B 1,5 --(3)--> C 2,8  of cost 12
C 6,4 --(2)--> B 7,2  of cost 2
B 7,2 --(3)--> A 3,0 A 3,0 --(4)--> A 0,0  of cost 7
B 7,2 --(3)--> A 3,0 A 3,0 --(4)--> B 1,2  of cost 7
B 7,2 --(3)--> A 3,0  of cost 3
B 7,2 --(3)--> A 3,0 A 3,0 --(4)--> B 1,5  of cost 7
B 7,2 --(3)--> A 3,0 A 3,0 --(4)--> B 1,5 B 1,5 --(3)--> C 2,8  of cost 10
B 7,2 --(3)--> C 6,4  of cost 3

There's an executable version available on duck in ~geoff/c++ for you to experiment with.

Hints

You'll need a struct to hold the node parameters, e.g.,

typedef struct {
    char TowerType;
    int XCoordinate,YCoordinate;
    } tower_info;

You'll need to define input and output operators for your struct, e.g.,

//-----------------------------------------------------------------------------
//----Input operator for nodes, required by LEDA
istream& operator>>(istream& Stream,tower_info& NodeData) {

Stream >> NodeData.TowerType >> NodeData.XCoordinate >> NodeData.YCoordinate;

return(Stream);
}
//-----------------------------------------------------------------------------
//----Output operator for nodes, required by LEDA
ostream& operator<<(ostream& Stream,const tower_info& NodeData) {

Stream << NodeData.TowerType << " " << NodeData.XCoordinate << ","
       << NodeData.YCoordinate;

return(Stream);
}
//-----------------------------------------------------------------------------

When computing the shortest paths, you'll need a node_matrix in which each entry is a struct, e.g.,

typedef struct {
    node Intermediate;
    int Cost;
    } matrix_data;

node_matrix Paths(MyGraph);

Submission

You must place the source code files of your program in a directory called MTH517/PhoneTowers off your home directory on duck, by 3:00pm on 26th April. You must submit a printout of your source code to the teaching assistant, or instructor by 3:15pm on 26th April. There will be no extension for this assignment! Aim to finish by 18th April so you have time to cope with unforeseen difficulties.

Your work will be assessed on:

Program execution - 60%
Appropriate use of LEDA - 20%
Programming style - 20%

It is worth 10% of the subject's assessment.

Data Structures and Algorithms: Phone Towers Assignment

Assignment

Hints

Submission

Data Structures and Algorithms:
Phone Towers Assignment