Eurotunnel between France and Great Britain
SuperClassCSI 321
Program 4
Now that the Eurotunnel between France and Great Britain is in operation, the French government is thinking about a new project to expand the connections with their British neighbors. Inspired by the move “Bridges of Madison County,” their prime architect Clouseau has been working on a plan to connect France to the Channel Islands by building a number of bridges.
To minimize the costs of the bridges, a necessity to get the plan approved, Cloueau has been working hard to find the best places to build the bridges that connect the islands to France. He has figured out that connecting each island to France individually is not the cheapest solution; it is cheaper to construct a bridge between one island and France, and build additional bridges to connect the other islands indirectly. Clouseau, however, is unable to find the best places to build the bridges because of the irregular shapes of the islands.
By approximating the islands as circles, Clouseau was able to report his boss, Mr. Dreyfus, an estimate of the length of the interconnecting bridges. Mr. Dreyfus, however, is not satisified and demands that Clouseau report by Monday the exact length of the bridges needed based on the actual shapes of the Channel Islands. If Clouseau does not report on time he will be fired. Would you be so kind to help out Clouseau and write a program that computes the minimum length of the bridges needed to interconnect the Channel Islands?
Input
The program should promote the user to enter the name of the input file from the interactive keyboard. Unless a path is provided with the file name, the file is assumed to be in the current directory. The first line of input will contain the number of n of islands (2<= n <= 100). This is followed by N lines that describe the islands. An island is a convex polygon which is described as a number (3 <= P <= 25) that gives the number of points followed by P pairs of coordinates. Each coordinate is an integer in the range [-1000…1000]. The points are listed in order such that by connecting consecutive points, and the last point to the first, the perimeter of the island is given. It is guaranteed that islands do not touch or intersect.
Output
For each test case output one line to the screen reporting the minimal interconnect as follows:
The minimal interconnect consists of N bridges with a total of length of L.
Where N is the number of bridges, and l is the total length, which should be printed as a floating point number with an accuracy of three digits.
Sample Input (from datafile)
3 (indicates how many lines below, each line is for an polygon object)
4 (indicates polygon sides) 0 0 0 1 1 1 1 0 (every consecutive 2 integers represents an x, y coordinate)
4 2 0 2 1 3 1 3 0
3 4 0 5 0 5 1
Therefore, the second line:
4 0 0 0 1 1 1 1 0 would be read as:
4 = how many sides there are to the given polygon
The rest of the values 0 0 0 1 1 1 1 0 would represent (x, Y) coordinates such as:
(0, 0) (0, 1) (1, 1) (1, 0)
(first polygon)
Sample Output
The minimal interconnect consists of 2 bridges with a total length of 2.000.
Test the Program with the following 3 datafiles:
Program4a.dat(contents of data file listed below)
3 3 = numOfIsands
4 0 0 0 1 1 1 1 0 4 = the number of vertices, (0,0) (0, 1), (1,1), (1,0) 4 sets of x,y coordinates
4 2 0 2 1 3 1 3 0
3 4 0 5 0 5 1
Correct Output for this data file should be:
The minimal interconnect consists of 2 bridges with a total length of 2.000.
Program4b.dat (contents of data file listed below)
13
4 21 93 21 100 5 100 5 93
4 1 1 7 1 7 5 1 5
4 54 18 58 18 58 20 54 20
4 25 81 27 81 27 90 25 90
4 58 90 60 90 60 84 58 84
4 35 23 34 23 34 24 35 24
4 30 19 30 20 23 20 23 19
4 61 14 61 10 65 10 65 14
4 55 80 55 75 50 75 50 80
4 7 13 20 13 20 15 7 15
4 45 25 50 25 50 23 45 23
4 64 93 65 93 65 101 64 101
4 30 75 40 75 40 77 30 77
Correct Output for this data file should be:
The minimal connect consists of 12 bridge with a total length of 118.0.
Program4c.dat (this will be uploaded separately)
Correct Output for this data file should be:
The minimal connect consists of ___ bridges with a total length of 492.83
Notes:
As I understand it, you compare each x,y set on a line and calculate the distance between each vertices set on everyone other line, but not with vertices that reside on the same line as each other.
EX:
On Line 2: 4 21 93 21 100 5 100 5 93 4 = the number of vertices sets of x,y coordinates on that line
Vertices sets on Line 2 would be: (21, 93) (21, 100) (5, 100) (5, 93) where x 1= 21 & y1 = 93
Vertices sets on Line 3 would be: (1, 1) (7, 1) (7, 5) (1, 5) where x2= 1 & y2 = 1
So you would calculate the distance using the distance formula:
Take the square root of ((x1-x2)2 + (y1-Y2)2) which would be the square root of ((21-1)2 + (93-1)2)
Set the variable minIslandDistance = (the calculated distance). You will calculate the distance of each verticies from the same line with all of the vertices on a different line then move on to the next line until all lines have been calculated against one another. So we will calculate the distance between vertices in Line 1 with the verticies in Line 2. Then:
Line1 to Line3
Line1 to Line4
Line1 to Line5, and so on.
Then Line2 to Line3
Line2 to Line4
Line2 to Line5, and so on.
We will calculate between vertices 2 specific Lines at a time, EX: between Line1 and Line2. We set the variable minIslandDistance = the calculated distance of the first calculated set of vertices between Line1 and Line2. If the next distance calculated by the next set of vertices on Line1 and Line2 is smaller, we make minIslandDistance = the new calculated distance, if it is not smaller, we do not change the value to the new distance. When all of the distances have been calculated between the 2 specific lines, (Line1 and Line2), we set PQItem = minIslandDistance which should now hold the shortest distance between Line 1 and Line 2 and send it into the PriorityQueue. Then we reset the minIslandDistance = 0 and then calculate the distances of vertices between two new lines line Line 2 and Line4 until all lines have been calculated and the shortest distance between all possible combinations of Lines have been determined and sent into the PriorityQueue.
Rules To Follow Regarding the Use of the Required Algorithm:
Maintaining a CheckPad array to avoid cycles when constructing a Minimal Spanning Tree using Kruskal’s Algorithm
Prime the CheckPad array by placing a different negative number in each component. If the graph has N nodes, then a loop something like the following would suffice:
for( J=0; j<N; j++)
CheckPad[j] = -1 –i;
//end for
Set a variable named FootPrint to Zero.
Systematically remove one edge (a,b) at a time from a PriorityQueue until you have N-1 edges, each time subjecting the removed edge to the following analysis:
if CheckPad[a] = CheckPad[b], edge (a,b) is unusable.
Using it would create a cycle or duplicate.
Throw it away and remove another edge from the PriorityQueue.
If CheckPad[a] and CheckPad[b] are both negative (and different), edge (a,b) is usable.
Set CheckPad[a] and CheckPad[b] to FootPrint.
Add 1 to FootPrint.
If only one of CheckPad[a] and CheckPad[b] are non-negative and different, edge (a,b) is usable.
Let P be the smaller of the two values and q be the larger. Set every occurrence of q in the CheckPad array to p.
EXAMPLE GRAPH
4TH 3rd 7th 11th
G
A H i
C B K E d J L M F
10th 5th 12th 9th 2nd 8th 13th 6th 1st
1st – has a weight of 1 for edge between I & K
2nd – has a weight of 1 for edge between G & J
3rd – has a weight of 1 for edge between B & G
4th – has a weight of 1 for edge between A & B
5th – has a weight of 1 for edge between F & D
6th – has a weight of 1 for edge between J & K
7th – has a weight of 1 for edge between E & G
8th – has a weight of 1 for edge between L & M
9th – has a weight of 2 for edge between B & D
10th – has a weight of 2 for edge between A & F
11th – has a weight of 2 for edge between H & i
12th – has a weight of 2 for edge between F & E
13th – has a weight of 2 for edge between J & K
CheckPad Array Values - Edges thrown in PriorityQueue – FootPrint Values
A | B | C | D | E | F | G | H | I | J | K | L | M |
| P | Q | U | E | FootPrint |
-1 | -2 | -3 | -4 | -5 | -6 | -7 | -8 | -9 | -10 | -11 | -12 | -13 |
|
|
|
|
| 0 |
-1 | -2 | -3 | -4 | -5 | -6 | -7 | -8 | 0 | -10 | 0 | -12 | -13 |
| i | K | 1 |
| 1 |
-1 | -2 | -3 | -4 | -5 | -6 | 1 | -8 | 0 | 1 | 0 | -12 | 13 |
| G | J | 1 |
| 2 |
-1 | 2 | 2 | -4 | -5 | -6 | 1 | -8 | 0 | 1 | 0 | -12 | 13 |
| B | C | 1 |
| 3 |
2 | 2 | 2 | -4 | -5 | -6 | 1 | -8 | 0 | 1 | 0 | -12 | 13 |
| A | B | 1 |
|
|
2 | 2 | 2 | 3 | -5 | 3 | 1 | -8 | 0 | 1 | 0 | -12 | 13 |
| F | D | 1 |
| 4 |
2 | 2 | 2 | 3 | -5 | 3 | 0 | -8 | 0 | 0 | 0 | -12 | -13 |
| J | K | 1 |
|
|
2 | 2 | 2 | 3 | 0 | 3 | 0 | -8 | 0 | 0 | 0 | -12 | -13 |
| E | G | 1 |
|
|
2 | 2 | 2 | 3 | 0 | 3 | 0 | -8 | 0 | 0 | 0 | 4 | 4 |
| L | M | 1 |
| 5 |
2 | 2 | 2 | 2 | 0 | 2 | 0 | -8 | 0 | 0 | 0 | 4 | 4 |
| B | D | 2 |
|
|
2 | 2 | 2 | 2 | 0 | 2 | 0 | -8 | 0 | 0 | 0 | 4 | 4 |
| A | F | 2 |
|
|
2 | 2 | 2 | 2 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 4 | 4 |
| H | i | 2 |
|
|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 |
| F | E | 2 |
|
|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| J | M | 2 |
|
|
Kruskal’s Algorithm – Follow this methodology
Let G be a connected weighted graph with N vertices. The following algorithm produces a subgraph T which is guaranteed to be a minimal spanning tree for G.
1. Let T be the subgraph of G consisting of the N vertices, but no edges.
2. Add 1 edge to T in such a way that the added edge
-does not create a cycle in T, and
-is otherwise the edge of minimal weight of all remaining edges of G, not currently in T.
3. Repeat step 2 until the number of edges is N-1.
Requirements for Program:
1. Prompt the user for the name and location of the data file
2. Build the check pad with the same number is islands and initially populated with different negative numbers
3. Check the edges against the values in the checkpad to see if they can be used or should be thrown away
4. Cumulate the number of bridges and total distance from their edges and print those values to the screen
5. Use the existing code from islands.java and PriorityQueue which I will list below
RESTRICTIONS:
1. Se the arrays, PriorityQueue, islands.java code. Do not use any other more sophisticated data structures. I am limited to using the types of data structures that I have listed in this document. You may have a better way to do it, but I have to use the arrays, priorityqueue, check pad array, distance formula, calculate the total distances with what I have. For example I cannot use vectors, other more sophisticated algorithms, etc.
2. Test the program with all 3 data files and check against the provided answers. Data files were program4a.dat, program4b.dat, program4c.dat (attaching this last one separately).
islands.java
import java.util.Arrays;
import java.util.Scanner;
import java.io.*;
public class islands
{
public static class Point
{
int x;
int y;
}
// end class Point
public static class Polygon
{
int NumOfVertices;
Point[] Vertices;
public Polygon()
{
Vertices = new Point[25];
for (int i = 0; i < 25; i++)
Vertices[i] = new Point();
// end for
}
// end Polygon constructor
}
// end class Polygon
public static void main(String[] args) throws IOException
{
int NumOfIslands, i=0, FootPrint=0, Temp;
Polygon[] Islands = new Polygon[100];
NumOfIslands = ReadInput(Islands);
int[] checkPad = new int[NumOfIslands];
BuildMinimalSpanningTree(NumOfIslands, Islands[]);
Scanner scan = new Scanner(System.in);
String NameOfTheInputFile;
System.out.println("Please enter the name of the input file:");
System.out.print("(include path if not in current directory) ");
NameOfTheInputFile = scan.nextLine();
InputFile = new Scanner(new File(NameOfTheInputFile));
while(InputFile.hasNext())
Islands[i++] = InputFile.next90;
//end while
for(i=0; i<NumOfIslands; i++)
CheckPad[i] = -1-i;
//end for
}
// end main method
/*********************************************************************
* *
* Function Name : BuildMinimalSpanningTree *
* Purpose : Use Kruskal's Algorithm to build the MST *
* Called by : Main *
* Functions Called: None *
* *
*********************************************************************/
public static class PQItem implements Comparable<PQItem>
{
int Node1;
int Node2;
double Edge;
public int compareTo(PQItem S)
{
if (Edge - S.Edge < 0)
return 1;
else if (Edge - S.Edge > 0)
return -1;
else
return 0;
// end if
}
// end public method compareTo
}
// end class PQItem
public static void BuildMinimalSpanningTree(int N, Polygon[] Islands)
{
}
}
PriorityQueue.java
public class PriorityQueue
{
private Comparable[] HeapArray;
int Last, Limit;
public PriorityQueue(int Capacity)
{
HeapArray = new Comparable[Capacity+1];
Last = 0;
Limit = Capacity;
return;
}
// end constructor
public PriorityQueue()
{
HeapArray = new Comparable[101];
Last = 0;
Limit = 100;
return;
}
// end constructor
public void Insert(Comparable PQI)
{
if (Last == Limit)
{
System.out.println("Priority Queue Overflow!");
System.exit(0);
}
// end if
HeapArray[++Last] = PQI;
this.UpHeap(Last);
return;
}
// end public method Insert
private void UpHeap(int k)
{
Comparable V;
V = HeapArray[k];
while (k > 1 && HeapArray[k/2].compareTo(V) < 0)
{
HeapArray[k] = HeapArray[k/2];
k = k/2;
}
// end while
HeapArray[k] = V;
return;
}
// end private method UpHeap
public Comparable Remove()
{
Comparable PQI ;
if (Last == 0)
{
System.out.println("Priority Queue Underflow!");
System.exit(0);
}
// end if
PQI = HeapArray[1];
HeapArray[1] = HeapArray[Last--];
this.DownHeap(1);
return PQI;
}
// end public method Remove
private void DownHeap(int k)
{
Comparable V;
int j;
V = HeapArray[k];
while (k <= Last/2)
{
j = k+k;
if (j < Last && HeapArray[j].compareTo(HeapArray[j+1]) < 0)
j++;
// end if
if (V.compareTo(HeapArray[j]) >= 0)
break;
// end if
HeapArray[k] = HeapArray[j];
k = j;
}
// end while
HeapArray[k] = V;
return;
}
// end private method DownHeap
public boolean IsEmpty()
{
if (Last == 0)
return true;
else
return false;
// end if
}
// end public method IsEmpty
public boolean IsFull()
{
if (Last == Limit)
return true;
else
return false;
// end if
}
// end public method IsFull
public int Length()
{
return Last;
}
// end public method Length
}
// end class PriorityQueue
11 years ago
Purchase the answer to view it
eurotunnel_between_france_and_great_britain.txt
