Airline project

Introduction:

This project designs an interactive airports and airline routes map. The project includes 3 parts:

  • 1st, airport and airline data is imported, parsed, and displayed on top of google maps.

  • 2nd, user-interactive features are included, for example, when mouse hovers over one airport, show airport information; when mouse clicks one airport, show connecting airline routes and connecting

  • 3rd, to support user request like shortest path between two cities, Dijkstra's algorithm is appied with graph data structure to fullfill this requirment.

Details

Libraries

  • Use PApplet for GUI, class extends PApplet
import processing.core.PApplet;

public class HelloWorld extends PApplet
{
}
  • unfoldingmap class: An interactive map. Used to import Google maps and enable interactivity with map.

Prepare map

  1. Create, set up and draw map
  2. Class public void setup()

Prepare airports

  1. Parse airport data and get all airports features
  2. Create airports markers from features and display on top of map
  3. Change the mark's appearance based on the altitude of the airports
  4. Add legend on the left to help interpret the map

Prepare routes

  1. Pares routes data, get features, put into "SimpleLinesMarker"
  2. Get location information from airports (hashmap)

Prepare for events

  1. mouseMoved() If mouse move upon an airport, show airport basic information
  2. mouseClicked()
    • if already has clicked airport, unhide all airports and routes, set lastClicked to null
    • if no airport is clicked, loop over all airport, if there is one airport that is not hidden and is under the mouse
      • set lastClicked to that airport
      • hide all the other airports that is not connected with the clicked airport
      • show routes connected with this airport

Find minimum distance between two airports

  • Loop over airlines, get destination and source, add all the edges to adjancy list
  • Graph representation. We use the adjacency-lists representation, where we maintain a vertex-indexed array of lists of the vertices connected by an edge to each vertex.

Definition for undirected graph.


  class UndirectedGraphNode {
      int label;
      double weight;
      List<UndirectedGraphNode> neighbors;
      UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
  }
  • Find shortest path between a & b: Dijkstra's algorithm
    • Use an edge-weighted digraph
    • Consider vertices in increasing order of distance from s (non-tree vertex with the lowest distTo[] value)
    • Add vertex to priority queue and relax all edges pointing from that vertex.
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex>
{
    public final String name;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;
    public Vertex(String argName) { name = argName; }
    public String toString() { return name; }
    public int compareTo(Vertex other)
    {
        return Double.compare(minDistance, other.minDistance);
    }

}


class Edge
{
    public final Vertex target;
    public final double weight;
    public Edge(Vertex argTarget, double argWeight)
    { target = argTarget; weight = argWeight; }
}

public class Dijkstra
{
    public static void computePaths(Vertex source)
    {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
    vertexQueue.add(source);

    while (!vertexQueue.isEmpty()) {
        Vertex u = vertexQueue.poll();

            // Visit each edge exiting u
            for (Edge e : u.adjacencies)
            {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
        if (distanceThroughU < v.minDistance) {
            vertexQueue.remove(v);

            v.minDistance = distanceThroughU ;
            v.previous = u;
            vertexQueue.add(v);
        }
            }
        }
    }

    public static List<Vertex> getShortestPathTo(Vertex target)
    {
        List<Vertex> path = new ArrayList<Vertex>();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args)
    {
        // mark all the vertices 
        Vertex A = new Vertex("A");
        Vertex B = new Vertex("B");
        Vertex D = new Vertex("D");
        Vertex F = new Vertex("F");
        Vertex K = new Vertex("K");
        Vertex J = new Vertex("J");
        Vertex M = new Vertex("M");
        Vertex O = new Vertex("O");
        Vertex P = new Vertex("P");
        Vertex R = new Vertex("R");
        Vertex Z = new Vertex("Z");

        // set the edges and weight
        A.adjacencies = new Edge[]{ new Edge(M, 8) };
        B.adjacencies = new Edge[]{ new Edge(D, 11) };
        D.adjacencies = new Edge[]{ new Edge(B, 11) };
        F.adjacencies = new Edge[]{ new Edge(K, 23) };
        K.adjacencies = new Edge[]{ new Edge(O, 40) };
        J.adjacencies = new Edge[]{ new Edge(K, 25) };
        M.adjacencies = new Edge[]{ new Edge(R, 8) };
        O.adjacencies = new Edge[]{ new Edge(K, 40) };
        P.adjacencies = new Edge[]{ new Edge(Z, 18) };
        R.adjacencies = new Edge[]{ new Edge(P, 15) };
        Z.adjacencies = new Edge[]{ new Edge(P, 18) };


        computePaths(A); // run Dijkstra
        System.out.println("Distance to " + Z + ": " + Z.minDistance);
        List<Vertex> path = getShortestPathTo(Z);
        System.out.println("Path: " + path);
    }
}

Others

  • Understand SimplePointMarker and PointFeature.: include location and properties(hashmap)

  • extends is for extending a class, implements is for implementing an interface.

  • The difference between an interface and a regular class is that in an interface you can not implement any of the declared methods. Only the class that "implements" the interface can implement the methods. The C++ equivalent of an interface would be an abstract class (not EXACTLY the same but pretty much).

  • airport.dat from Open-flight

  • Depth-first search. Depth-first search is a classic recursive method for systematically examining each of the vertices and edges in a graph. To visit a vertex:

    • Mark it as having been visited.
    • Visit (recursively) all the vertices that are adjacent to it and that have not yet been marked.

  • Breadth-first search is a classic method based on this goal. To find a shortest path from s to v, we start at s and check for v among all the vertices that we can reach by following one edge, then we check for v among all the vertices that we can reach from s by following two edges, and so forth.

    • To implement this strategy, we maintain a queue of all vertices that have been marked but whose adjacency lists have not been checked. We put the source vertex on the queue, then perform the following steps until the queue is empty:
    • Remove the next vertex v from the queue.
    • Put onto the queue all unmarked vertices that are adjacent to v and mark them.