Maxim, there are a whole bunch of errors in your code. It looks as if you had an idea for what you wanted to do, and then threw some code at it until something emerged and worked a bit, but there's no clear concept here and thus it's no wonder it's not really working.
The core of this program is the Flights collection (why is Flights uppercased?), and it's very possible to build a working route finder around it. I'm not sure whether it would help you more to give you some hints or to simply build the program for you.
Update: I've meanwhile found a flight schedule for a Polish airline (don't ask!) with 203 distinct routings that I can use to fill and test a flight connection structure. I'm going to start hacking and we'll see how it goes.
Update: Here's the code.
To be at all useful for your apparent purpose, it's probably not enough to just find a routing (i.e. an itinerary of airports visited); you probably want a list of flights taken to get there. Note, of course, that there may be multiple combinations of flights that have the same itinerary - this code just finds the first.
You may want to modify the algorithm to place a weight (= cost) on travel time, if you have those, so your passengers get not just the smallest number of legs (= hops from one airport to the next) but also the shortest combined travel time. This more general form of the algorithm would be called Dijkstra's Algorithm, and is also described in Wikipedia.
Interestingly enough, it seems that BFS is not really suited to a recursive solution. Like your original code, my code is essentially imperative with a few loops. Note that the correct "main" data structure for doing BFS is not a stack but a queue!
public class Maxim {
/**
* Create a Maxim instance and run a search on it.
*/
public static void main(String[] args) {
try {
Maxim maxim = new Maxim();
Route r = maxim.findRoute("FCO", "DNV"); // tests a single origin/destination pair
if (r == null) {
System.out.println("No route found");
} else {
System.out.println(Arrays.deepToString(r.toArray()));
}
} catch (Exception e) {
e.printStackTrace();
}
}
/**
* A simple Flight. Contains a flight number and only a single leg.
* number: Flight number
* dep: Departure airport
* arr: Arrival airport
*/
class Flight {
final String number, dep, arr;
public Flight(String number, String departure, String arrival) {
this.number = number; this.dep = departure; this.arr = arrival;
}
public String toString() {
return "Flight [number=" + this.number + ", dep=" + this.dep + ", arr=" + this.arr + "]";
}
}
/**
* Airport: A city and a list of Flights originating from it.
*/
class Airport {
public final String city;
public List<Flight> flights = new ArrayList<Flight>();
public Airport(String city) {
this.city = city;
}
public String toString() {
return "Airport [city=" + this.city + ", flights=" + this.flights + "]";
}
}
/**
* Route: A list of flights that get a traveller from a given origin to a destination.
*/
static class Route extends ArrayList<Flight> { }
/**
* Our known list of flights. It's not really needed after initialization.
*/
private List<Flight> flights = new ArrayList<Flight>();
/**
* List of airports. These constitute the graph we search.
*/
private Map<String, Airport> airports = new HashMap<String, Airport>();
/**
* Constructor. Constructs the "airports" graph from a list of "flights" read from a file.
*/
public Maxim() throws Exception {
// Read flights from file into list "flights".
// The file contains strings like " 696KGDWAW" = flight number, departure airport, arrival airport
BufferedReader flightReader = new BufferedReader(new FileReader("/home/carl/XX.flights"));
while (true) {
String flt = flightReader.readLine();
if (flt == null) break;
flights.add(new Flight(flt.substring(0,4), flt.substring(4, 7), flt.substring(7, 10)));
}
flightReader.close();
// Create a map of each airport to a list of Flights departing from it.
// This is the graph we'll be doing BFS on.
for (Flight flight : flights) {
String from = flight.dep;
if (!airports.containsKey(from)) {
Airport port = new Airport(from);
port.flights.add(flight);
airports.put(from, port);
} else {
Airport port = airports.get(from);
port.flights.add(flight);
}
}
}
/**
Algorithm (from Wikipedia):
1. Enqueue the root node.
2. Dequeue a node and examine it.
If the element sought is found in this node, quit the search and return a result.
Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
3. If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
4. Repeat from Step 2.
*/
public Route findRoute(String origin, String destination) {
Queue<Airport> queue = new LinkedList<Airport>();
Map<Airport, Flight> backtrack = new HashMap<Airport, Flight>();
Airport oriApt = this.airports.get(origin);
if (oriApt == null) return null; // origin airport not found - no solution
queue.add(oriApt);
while (!queue.isEmpty()) {
Airport apt = queue.remove();
if (apt == null) break;
if (apt.city.equals(destination)) { // Made it to destination; create the route and return it
Route toHere = new Route();
while (apt != oriApt) {
Flight flt = backtrack.get(apt);
toHere.add(flt);
apt = airports.get(flt.dep);
}
Collections.reverse(toHere);
return toHere;
}
// enqueue all new airports reachable from this airport.
// record the flight that got us there in backtrack.
for (Flight flt: apt.flights) {
Airport destApt = airports.get(flt.arr);
if (backtrack.containsKey(destApt)) continue; // we've been to this destination before - ignore
backtrack.put(destApt, flt);
queue.add(destApt);
}
}
// if we're here, we didn't find anything.
return null;
}
}