CODEWITHSUNDEEP
javadepth-first-searchbreadth-first-searchgraph-traversal
RicardoC
RicardoC

Reputation: 109

Java - Breadth-first search on a multigraph of flights

I have a graph with cities as nodes and a class Flight as edges. Each flight has a departure time, arrival time, flight number and an array of days in which the flight operates. Multiple edges can connect each pair of nodes, making the graph a multigraph. I need to answer the question: What are the available flights from Place1 to Place2 on a given day, with transfers being possible?

The following two methods use depth-first search to find and print an answer:

public static void printRoutes(String day,String source,String place1, String place2, boolean[] visited, LinkedList<Edge> Route,Grafo g) {

    int index = hash.get(place1);
    visited[index] = true;


    if(place1.equals(place2)) 
        if(isTransferable(day,Route,source))
            writeRoute(Route,source);

    if(place1 != place2) {
        LinkedList<Edge> adjs = g.adjs_no(place1);


        for(Edge a: adjs) {
            if(!visited[hash.get(a.node_final)]) {
                Route.add(a);
                printRoutes(day,source,a.node_final,place2,visited,Route,g);
                Route.remove(a);
            }
        }
    }
    visited[indice] = false;            
}

public static void writeRoute(LinkedList<Edge> Route,String source) {
        System.out.print(source + " -> ");
        for (int i = 0; i < Route.size(); i++) {
            System.out.print(Route.get(i).vertex_final() + " | Flight Number:");
            System.out.print(Route.get(i).flight.flightNumber + " | Departure Time:" + Route.get(i).flight.departureTime);
            System.out.println();
            if(i != Route.size()- 1)System.out.print(Route.get(i).vertex_final() + " -> ");

        }
        System.out.println();
        System.out.println();    
    }

isTransferable checks if there is at least a 40 min time window between an arrival and a departure of two flights.

I would like to answer this question using breadth-first search instead of DFS, so that shorter trips appear first. The algorithm I have for BFS doesn't work for multigraphs though. Is there a way to perform BFS on this graph, so that I can successfully print all the possible trips between two cities on a given day?

Upvotes: 1

Views: 790

Answers (1)

John Bollinger
John Bollinger

Reputation: 180113

It's important to understand that your data don't exactly form a multigraph for the purposes of your route-search algorithm. This is because the outbound edges that one can traverse from a given node depend on which inbound edge was traversed to reach that node. That's why you need your isTransferable() method for the DFS.

Instead, what you have would be better characterized as a compact representation of an ordinary graph in which the nodes represent (city, arrival flight, flight date) triples. Or inasmuch as each flight has exactly one destination, the characteristic data for each node are really just arrival flight and date. Or if you chop that up into a separate graphs for each day then you're left with arrival flight being the characteristic data for each node.

With that in mind, you ought to be able to adapt an ordinary BFS algorithm to your data representation. Your existing isTransferable() method can help, but the key is to identify nodes appropriately (by inbound flight, not (directly) by city).

Upvotes: 1

Related Questions