import java.util.*;
import java.lang.Math.*;
/**
* Write a description of class Luchthaven here.
*
* @author Arne Vanhoof
* @version (a version number or a date)
*/
public class Luchthaven
{
private int[] XCoordArray;
private int[] YCoordArray;
private int[] VerbindingenA;
private int[] VerbindingenB;
private ArrayList<Double> Afstandenlijst;
private ArrayList<Integer> Route;
private ArrayList<Double> RouteAfstand;
public Luchthaven() {
XCoordArray = new int[8];
YCoordArray = new int[8];
VerbindingenA = new int[9];
VerbindingenB = new int[9];
Afstandenlijst = new ArrayList<Double>();
Route = new ArrayList<Integer>();
RouteAfstand = new ArrayList<Double>();
XCoordArray[0] = 10;
YCoordArray[0] = 29;
XCoordArray[1] = 25;
YCoordArray[1] = 46;
XCoordArray[2] = 54;
YCoordArray[2] = 46;
XCoordArray[3] = 83;
YCoordArray[3] = 46;
XCoordArray[4] = 32;
YCoordArray[4] = 10;
XCoordArray[5] = 47;
YCoordArray[5] = 10;
XCoordArray[6] = 76;
YCoordArray[6] = 10;
XCoordArray[7] = 91;
YCoordArray[7] = 26;
VerbindingenA[0] = 1;
VerbindingenB[0] = 2;
VerbindingenA[1] = 1;
VerbindingenB[1] = 5;
VerbindingenA[2] = 2;
VerbindingenB[2] = 3;
VerbindingenA[3] = 2;
VerbindingenB[3] = 5;
VerbindingenA[4] = 3;
VerbindingenB[4] = 4;
VerbindingenA[5] = 3;
VerbindingenB[5] = 6;
VerbindingenA[6] = 5;
VerbindingenB[6] = 6;
VerbindingenA[7] = 6;
VerbindingenB[7] = 7;
VerbindingenA[8] = 7;
VerbindingenB[8] = 8;
}
// We controleren met een boolean of de 2 opgegeven steden is verbinding staan met elkaar
public boolean Verbinding(int stad1, int stad2) {
boolean waarde = false;
for(int i = 0; i < VerbindingenA.length; i++) {
if ( ((VerbindingenA[i] == stad1) && (VerbindingenB[i] == stad2)) || ((VerbindingenB[i] == stad1) && (VerbindingenA[i] == stad2)) ) {
waarde = true;
}
}
return waarde;
}
public boolean ZoekOplossing(int stad1, int stad2) {
if (Verbinding(stad1, stad2)){
//blablabla...
System.out.println("wii onze steden staan in direct contact");
Route.add(stad2);
RouteAfstand.add(BerekenAfstand(stad1,stad2));
return true;
}
else {
//Nu moeten we gaan zoeken met welke steden stad 1 in contact staat en daarvan de kortste route kiezen.
int stad3;
if(BerekenKortste(stad1, stad2) != 0) {
stad3 = BerekenKortste(stad1, stad2);//We stellen de nieuwe stad in
Route.add(stad3);
RouteAfstand.add(BerekenAfstand(stad1,stad3));
System.out.println("de stad die het kortste licht is: " + stad3);
if ( ZoekOplossing(stad3,stad2) ) {
return true;
}
VerwijderLaatste();
}
return false;
}
}
public void VerwijderLaatste() {
int plaats = (Route.size() - 1);
System.out.println("We verwijderen de laatste in de lijst: " + Route.get(plaats) + "wat staat op " + plaats);
Route.remove(plaats);
RouteAfstand.remove(plaats-1);// in onze RouteAfstand staat er eentje minder dan in de gewone route, want in de route array werd de beginpositie toegevoegd
}
public int BerekenKortste(int stad1, int stad2){
ArrayList<Integer> Stedenlijst = new ArrayList<Integer>();
//Nu moeten we gaan zoeken met welke steden stad1 in contact staat en daarvan de kortste route kiezen.
for(int i = 0; i < VerbindingenA.length; i++) {
if (VerbindingenA[i] == stad1 && !Route.contains(VerbindingenB[i])) {
Stedenlijst.add( VerbindingenB[i] );
}
if (VerbindingenB[i] == stad1 && !Route.contains(VerbindingenA[i])) {
Stedenlijst.add( VerbindingenA[i] );
}
}
System.out.println("Onze steden stonden niet in direct contact. Maar stad: " + stad1 + " staat in contact met " + Stedenlijst.size() + " steden.");
for(int i = 0; i < Stedenlijst.size(); i++) {
System.out.println(" Stad : " + stad1 + " staat in contact met stad : " + Stedenlijst.get(i));
}
// Nu moeten we alle afstanden gaan zoeken tussen stad1 en zijn verbindingen. Deze slaan we eveneens op in een arraylist
if(Stedenlijst.size() == 0) {
System.out.println("vanaf hier zitten we vast, onze stad heeft geen verbindingen meer, we moeten teruggaan");
return 0;
}
else if( Stedenlijst.size() == 1) {
System.out.println("Onze stad staat maar met 1 stad in verbinding, nl stad: " + Stedenlijst.get(0));
return Stedenlijst.get(0);//Onze stad staat maar met 1 stad in verbinding dus dit is sowieso de kortste!
}
else {// Er is maar dan 1 stad dus moeten we de afstanden gaan vergelijken.
for(int i = 0; i < Stedenlijst.size(); i++) {
Afstandenlijst.add(BerekenAfstand(Stedenlijst.get(i), stad2));
System.out.println(" Stad : " + stad1 + " staat in contact met stad : " + Stedenlijst.get(i) + " en de afstand is : " + Afstandenlijst.get(i));
}
//De bijhorende steden staan nu in de Stedenlijst ArrayList en de bijhorende afstanden in de Afstandenlijst Arraylist, we zoeken nu de kortste
return Stedenlijst.get(Minimum());
}
}
public double BerekenAfstand(int stad1, int stad2) {
double afstand;
int stad1X = XCoordArray[stad1-1];
int stad1Y = YCoordArray[stad1-1];
int stad2X = XCoordArray[stad2-1];
int stad2Y = YCoordArray[stad2-1];
afstand = Math.sqrt(((stad2X - stad1X) * (stad2X - stad1X)) + ((stad2Y - stad1Y) * (stad2Y - stad1Y)));
return afstand;
}
public int Minimum() {
if(Afstandenlijst.size() == 1){
Afstandenlijst.clear();
return 0;//Het minimum bevindt zich dan op de 0de positie in de array, dus de stad ook.
}
else {
double minimum = Afstandenlijst.get(0); // we zetten de eerste waarde als minimum
int arraywaarde = 0; // Het minimum bevindt zich momenteel op arraywaarde 0
for (int i=1; i<Afstandenlijst.size(); i++) {
if (Afstandenlijst.get(i) < minimum) {
minimum = Afstandenlijst.get(i); // Nieuwe minimum wordt ingesteld.
arraywaarde = i; // Nieuwe arraywaarde wordt ingesteld.
}
}
Afstandenlijst.clear();//Zodat de waarden er voor de volgende berekening niet meer instaan
return arraywaarde;
}
}
public void ControleerOplossing(int stad1, int stad2) {
Route.add(stad1);
if(ZoekOplossing(stad1, stad2)) {
System.out.println("Enter start city (1-8): " + stad1);
System.out.println("Enter destination (1-8): " + stad2);
print(stad1,stad2);
Route.clear();
RouteAfstand.clear();
}
else {
System.out.println("Sorry, maar er is iets fout gelopen");
}
}
public void print(int stad1, int stad2){
double afstand = 0;
System.out.print("Route: ");
for(int i =0; i < Route.size(); i++) {
System.out.print( Route.get(i) + " ," );
}
System.out.print("\n");
System.out.print("Route-afstand: ");
for(int i =0; i < RouteAfstand.size(); i++) {
System.out.print( RouteAfstand.get(i) + " ," );
}
System.out.print("\n");
System.out.print("Totale afstand:");
for(int i =0; i < RouteAfstand.size(); i++) {
afstand = afstand + RouteAfstand.get(i);
}
System.out.print( afstand );
}
}