Code in Java Programming Language, Data Structure(s), Adjacency List Structure, Code for Airline Industry

In response to this assignment, students are required to write solution in form of code in Java programming language. Students are required to create a generic data structure(s) which would  be used for storage of graphs. They have to make use of adjacency list structure. The objects of generic type V would  be stored in the vertices and objects of generic type E in the edges.  All entries must be aware of the location. Addition or removal of given vertex or edge in the data structure must be supported.

Secondly, a program has to be created that has its relevance in data analysis for airline industry. The program would give the connection travel time between various airports as output by accepting certain commands as input.

SOLUTION : –

import java.util.Objects;

public class Route {

int distance;

String method;

public Route(int distance) {

this.distance = distance;

method = “plane”;

}

@Override

public boolean equals(Object o) {

if (this == o) return true;

if (o == null || getClass() != o.getClass()) return false;

Route route = (Route) o;

return distance == route.distance &&

method.equals(route.method);

}

@Override

public String toString() {

final StringBuilder sb = new StringBuilder();

sb.append(distance).append(‘ ‘);

sb.append(method);

return sb.toString();

}

@Override

public int hashCode() {

return Objects.hash(distance, method);

}

}

import java.util.*;

public class Graph<V, E> {

private Map<V, List<E>> adjacent;

private Map<E, Pair<V>> edges;

public Graph() {

adjacent = new HashMap<>(20);

edges = new HashMap<>(20);

}

ArrayList<V> endVertices(E edge) {

ArrayList<V> v = new ArrayList<>(2);

Pair<V> pair = edges.get(edge);

if (pair == null) return null;

v.add(pair.a);

v.add(pair.b);

return v;

}

V opposite(V vertex, E edge) {

Pair<V> pair = edges.get(edge);

if (pair.a.equals(vertex)) return pair.b;

return pair.a;

}

boolean areAdjacent(V v, V w) {

List<E> list = adjacent.get(v);

for (E edge : list) {

if (opposite(v, edge).equals(w)) return true;

}

return false;

}

boolean insertVertex(V v) {

if (adjacent.containsKey(v)) return false;

adjacent.put(v, new ArrayList<>(10));

return true;

}

boolean insertEdge(V v, V w, E o) {

insertVertex(v);

insertVertex(w);

adjacent.get(v).add(o);

adjacent.get(w).add(o);

edges.put(o, new Pair<>(v, w));

return true;

}

boolean removeVertex(V v) {

if (!adjacent.containsKey(v)) return false;

List<E> list = adjacent.get(v);

for (E edge : list) {

V w = opposite(v, edge);

List<E> remove = adjacent.get(w);

remove.remove(edge);

edges.remove(edge);

adjacent.put(w, remove);

}

adjacent.remove(v);

return true;

}

boolean removeEdge(E edge) {

if (!edges.containsKey(edge)) return false;

Pair<V> pair = edges.get(edge);

List<E> remove = adjacent.get(pair.a);

remove.remove(edge);

adjacent.put(pair.a, remove);

remove = adjacent.get(pair.b);

remove.remove(edge);

adjacent.put(pair.b, remove);

edges.remove(edge);

return true;

}

Iterator<E> incidentEdges(V v) {

return adjacent.get(v).iterator();

}

Iterator<V> vertices() {

return adjacent.keySet().iterator();

}

Iterator<E> edges() {

return edges.keySet().iterator();

}

private class Pair<V> {

final V a, b;

public Pair(V a, V b) {

this.a = a;

this.b = b;

}

boolean has(V v) {

return a.equals(v) || b.equals(v);

}

}

}

import java.util.*;

public class Flights {

private Graph<String, Route> flights;

public Flights() {

flights = new Graph<>();

}

public boolean cmd(String s) {

if (s.equalsIgnoreCase(“quit”) || s.equalsIgnoreCase(“q”)) return false;

if (s.startsWith(“+”)) return addRoute(s.split(” “));

if (s.startsWith(“?”)) {

String args[] = s.split(” “);

switch (args.length) {

case 1: return showRoutes();

case 2: return showRoutes(args[1]);

case 3: return showRoutes(args[1], args[2]);

}

}

if (s.startsWith(“-“)) {

String args[] = s.split(” “);

switch (args.length) {

case 2: return removeAirport(args[1]);

case 5: return removeRoute(args);

}

}

System.out.println(“Unrecognized command”);

return true;

}

private boolean removeRoute(String[] args) {

Route route = new Route(Integer.parseInt(args[3]));

flights.removeEdge(route);

return true;

}

private boolean removeAirport(String arg) {

flights.removeVertex(arg);

return true;

}

private boolean showRoutes(String start, String dest) {

int numVerts = 0, startIdx = -1, destIdx = -1;

Map<String, Integer> index = new HashMap<>();

for (Iterator<String> it = flights.vertices(); it.hasNext(); ) {

it.next();

numVerts++;

}

String cities[] = new String[numVerts];

int i = 0, j = 0;

for (Iterator<String> it = flights.vertices(); it.hasNext(); ) {

String city = it.next();

if (city.equalsIgnoreCase(start)) startIdx = i;

if (city.equalsIgnoreCase(dest)) destIdx = i;

index.put(city, i);

cities[i++] = city;

}

//System.out.println(Arrays.toString(cities) + ” ” + startIdx + ” – ” + destIdx);

if (startIdx < 0 || destIdx < 0) {

System.out.println(“City not found”);

return true;

}

if (startIdx == destIdx) {

System.out.printf(“Nowhere to go”);

return true;

}

Routes routes[][] = new Routes[numVerts][numVerts];

for (j = 0; j < numVerts; j++) {

for (i = 0; i < numVerts; i++) {

routes[i][j] = new Routes();

}

}

boolean more = true;

while (more) {

more = false;

for (i = 0; i < numVerts; i++) {

String city = cities[i];

for (Iterator<Route> it = flights.incidentEdges(city); it.hasNext(); ) {

Route route = it.next();

String to = flights.opposite(city, route);

j = index.get(to);

Routes curr = routes[i][j];

if (!curr.visited(to)) {                                                                                                curr.add(route);                                                                                                more = true;                                                                                }

}

}

}

routes[startIdx][destIdx].display();

return true;

}

private boolean showRoutes(String arg) {

for (Iterator<Route> it = flights.incidentEdges(arg); it.hasNext(); ) {

Route route = it.next();

show(route);

}

return true;

}

private boolean showRoutes() {

for (Iterator<Route> it = flights.edges(); it.hasNext(); ) {

Route route = it.next();

show(route);

}

return true;

}

private void show(Route route) {

if (route == null) {

System.out.println(“No route found”);

return;

}

ArrayList<String> cities = flights.endVertices(route);

if (cities == null) {

System.out.println(“No route found”);

return;

}

System.out.println(cities.get(0) + ” ” + cities.get(1) + ” ” + route);

}

private boolean addRoute(String[] args) {

if (args.length != 4) {

System.out.println(“Needs to be + CODE CODE distance”);

return true;

}

int distance = Integer.parseInt(args[3]);

flights.insertEdge(args[1], args[2], new Route(distance));

return true;

}

private class Routes {

int distance;

ArrayList<Route> path;

HashSet<String> visited;

public Routes() {

path = new ArrayList<>(10);

distance = 0;

visited = new HashSet<>();

}

public void add(Route route) {

distance += route.distance;

path.add(route);

ArrayList<String> cities = flights.endVertices(route);

visited.add(cities.get(0));

visited.add(cities.get(1));

}

public boolean visited(String city) {

return visited.contains(city);

}

public void display() {

for (Route route : path) {

show(route);

}

}

}

}

import java.util.Scanner;

public class Command {

public static void main(String args[]) {

Flights flights = new Flights();

flights.cmd(“+ HNL LAX 2555”);

flights.cmd(“+ LAX DFW 1233”);

flights.cmd(“+ LAX SFO 337”);

flights.cmd(“+ LAX ORD 1743”);

flights.cmd(“+ SFO ORD 1843”);

flights.cmd(“+ DFW ORD 802”);

flights.cmd(“+ DFW MIA 1120”);

flights.cmd(“+ MIA LGA 1099”);

flights.cmd(“+ ORD PVD 849”);

flights.cmd(“+ LGA PVD 142”);

flights.cmd(“+ DFW LGA 1387”);

flights.cmd(“? DFW HNL”);

//flights.cmd(“? PVD HNL”);

Scanner scanner = new Scanner(System.in);

boolean status = true;

while (status) {

System.out.print(“> “);

String cmd = scanner.nextLine();

status = flights.cmd(cmd);

}

}

}