Language is Java, SDK 8

Here is a couple sample input files:

pilot_routes.txt

Mirage 1 14 22 28 Mickey 35 1 22 35 14 Aztec 22 28 10

galaxy.txt

22 28,6 14,2 35,3 14 22,2 1,3 35 28,3 22,3 1,4 1 35,4 14,3 28 22,6 35,3

Here is my code for a graph class to use:

import java.util.*;

//Abstract graph abstract class AbstractGraph implements Graph { protected List vertices = new ArrayList(); // Store vertices protected List> neighbors = new ArrayList(); // Adjacency lists

/** Construct an empty graph */ protected AbstractGraph() { } /** Construct a graph from vertices and edges stored in arrays */ protected AbstractGraph(V[] vertices, int[][] edges) { for (int i = 0; i

/** Construct a graph from vertices and edges stored in List */ protected AbstractGraph(List vertices, List edges) { for (int i = 0; i

/** Construct a graph for integer vertices 0, 1, 2 and edge list */ protected AbstractGraph(List edges, int numberOfVertices) { for (int i = 0; i

/** Construct a graph from integer vertices 0, 1, and edge array */ protected AbstractGraph(int[][] edges, int numberOfVertices) { for (int i = 0; i

/** Create adjacency lists for each vertex */ private void createAdjacencyLists( int[][] edges, int numberOfVertices) { for (int i = 0; i

/** Create adjacency lists for each vertex */ private void createAdjacencyLists( List edges, int numberOfVertices) { for (Edge edge: edges) { addEdge(edge.u, edge.v); } }

@Override /** Return the number of vertices in the graph */ public int getSize() { return vertices.size(); }

@Override /** Return the vertices in the graph */ public List getVertices() { return vertices; }

@Override /** Return the object for the specified vertex */ public V getVertex(int index) { return vertices.get(index); }

@Override /** Return the index for the specified vertex object */ public int getIndex(V v) { return vertices.indexOf(v); }

@Override /** Return the neighbors of the specified vertex */ public List getNeighbors(int index) { List result = new ArrayList(); for (Edge e: neighbors.get(index)) result.add(e.v); return result; }

@Override /** Return the degree for a specified vertex */ public int getDegree(int v) { return neighbors.get(v).size(); }

@Override /** Print the edges */ public void printEdges() { for (int u = 0; u

@Override /** Clear the graph */ public void clear() { vertices.clear(); neighbors.clear(); } @Override /** Add a vertex to the graph */ public boolean addVertex(V vertex) { if (!vertices.contains(vertex)) { vertices.add(vertex); neighbors.add(new ArrayList()); return true; } else { return false; } }

/** Add an edge to the graph */ protected boolean addEdge(Edge e) { if (e.u getSize() - 1) throw new IllegalArgumentException("No such index: " + e.u);

if (e.v getSize() - 1) throw new IllegalArgumentException("No such index: " + e.v); if (!neighbors.get(e.u).contains(e)) { neighbors.get(e.u).add(e); return true; } else { return false; } } @Override /** Add an edge to the graph */ public boolean addEdge(int u, int v) { return addEdge(new Edge(u, v)); } } //regular graph interface Graph { /** Return the number of vertices in the graph */ public int getSize();

/** Return the vertices in the graph */ public java.util.List getVertices();

/** Return the object for the specified vertex index */ public V getVertex(int index);

/** Return the index for the specified vertex object */ public int getIndex(V v);

/** Return the neighbors of vertex with the specified index */ public java.util.List getNeighbors(int index);

/** Return the degree for a specified vertex */ public int getDegree(int v);

/** Print the edges */ public void printEdges();

/** Clear the graph */ public void clear();

/** Add a vertex to the graph */ public boolean addVertex(V vertex);

/** Add an edge to the graph */ public boolean addEdge(int u, int v);

/** Obtain a depth-first search tree */ public AbstractGraph.Tree dfs(int v);

/** Obtain a breadth-first search tree */ public AbstractGraph.Tree bfs(int v); }

//weighted edge class

class WeightedEdge extends AbstractGraph.Edge implements Comparable { public double weight; // The weight on edge (u, v)

/** Create a weighted edge on (u, v) */ public WeightedEdge(int u, int v, double weight) { super(u, v); this.weight = weight; }

/** Compare two edges on weights */ public int compareTo(WeightedEdge edge) { if (weight > edge.weight) { return 1; } else if (weight == edge.weight) { return 0; } else { return -1; } } }

//weighted graph

class WeightedGraph extends AbstractGraph { /** Construct an empty */ public WeightedGraph() { } /** Construct a WeightedGraph from vertices and edged in arrays */ public WeightedGraph(V[] vertices, int[][] edges) { createWeightedGraph(java.util.Arrays.asList(vertices), edges); }

/** Construct a WeightedGraph from vertices and edges in list */ public WeightedGraph(int[][] edges, int numberOfVertices) { List vertices = new ArrayList(); for (int i = 0; i

/** Construct a WeightedGraph for vertices 0, 1, 2 and edge list */ public WeightedGraph(List vertices, List edges) { createWeightedGraph(vertices, edges); }

/** Construct a WeightedGraph from vertices 0, 1, and edge array */ public WeightedGraph(List edges, int numberOfVertices) { List vertices = new ArrayList(); for (int i = 0; i

/** Create adjacency lists from edge arrays */ private void createWeightedGraph(List vertices, int[][] edges) { this.vertices = vertices;

for (int i = 0; i ()); // Create a list for vertices }

for (int i = 0; i

/** Create adjacency lists from edge lists */ private void createWeightedGraph( List vertices, List edges) { this.vertices = vertices;

for (int i = 0; i ()); // Create a list for vertices }

for (WeightedEdge edge: edges) { neighbors.get(edge.u).add(edge); // Add an edge into the list } }

/** Return the weight on the edge (u, v) */ public double getWeight(int u, int v) throws Exception { for (Edge edge : neighbors.get(u)) { if (edge.v == v) { return ((WeightedEdge)edge).weight; } } throw new Exception("Edge does not exit"); } /** Display edges with weights */ public void printWeightedEdges() { for (int i = 0; i

/** Get a minimum spanning tree rooted at vertex 0 */ public MST getMinimumSpanningTree() { return getMinimumSpanningTree(0); } /** Get a minimum spanning tree rooted at a specified vertex */ public MST getMinimumSpanningTree(int startingVertex) { // cost[v] stores the cost by adding v to the tree double[] cost = new double[getSize()]; for (int i = 0; i

int[] parent = new int[getSize()]; // Parent of a vertex parent[startingVertex] = -1; // startingVertex is the root double totalWeight = 0; // Total weight of the tree thus far

List T = new ArrayList(); // Expand T while (T.size()

T.add(u); // Add a new vertex to T totalWeight += cost[u]; // Add cost[u] to the tree

// Adjust cost[v] for v that is adjacent to u and v in V - T for (Edge e : neighbors.get(u)) { if (!T.contains(e.v) && cost[e.v] > ((WeightedEdge)e).weight) { cost[e.v] = ((WeightedEdge)e).weight; parent[e.v] = u; } } } // End of while

return new MST(startingVertex, parent, T, totalWeight); }

/** MST is an inner class in WeightedGraph */ public class MST extends Tree { private double totalWeight; // Total weight of all edges in the tree

public MST(int root, int[] parent, List searchOrder, double totalWeight) { super(root, parent, searchOrder); this.totalWeight = totalWeight; }

public double getTotalWeight() { return totalWeight; } }

/** Find single source shortest paths */ public ShortestPathTree getShortestPath(int sourceVertex) { // cost[v] stores the cost of the path from v to the source double[] cost = new double[getSize()]; for (int i = 0; i

// parent[v] stores the previous vertex of v in the path int[] parent = new int[getSize()]; parent[sourceVertex] = -1; // The parent of source is set to -1 // T stores the vertices whose path found so far List T = new ArrayList(); // Expand T while (T.size() cost[u] + ((WeightedEdge)e).weight) { cost[e.v] = cost[u] + ((WeightedEdge)e).weight; parent[e.v] = u; } } } // End of while

// Create a ShortestPathTree return new ShortestPathTree(sourceVertex, parent, T, cost); }

/** ShortestPathTree is an inner class in WeightedGraph */ public class ShortestPathTree extends Tree { private double[] cost; // cost[v] is the cost from v to source

/** Construct a path */ public ShortestPathTree(int source, int[] parent, List searchOrder, double[] cost) { super(source, parent, searchOrder); this.cost = cost; }

/** Return the cost for a path from the root to vertex v */ public double getCost(int v) { return cost[v]; }

/** Print paths from all vertices to the source */ public void printAllPaths() { System.out.println("All shortest paths from " + vertices.get(getRoot()) + " are:"); for (int i = 0; i Objectives: Create and utilize a graph in Java Problem: Darth Vader wants to check that his TIE fighter pilots are patrolling adequately-sized regions of the galaxy. He has files of data that contain the patrol coordinates for each of his pilots. With the fear of being force choked, you have agreed to write a program that analyzes the data and determines if the patrol path is valid Pseudocode Details: Since this project focuses on the use of pre-made classes, detail your main class What functions will you create other than main . o What parameters will you have o What will the function return o What is the logic of the function What will the logic of main be? Details: A map of the galaxy will be given and will be stored in a graph o Utilize the provided Graph class in eLearning to hold the graph information .Each pilot will have a patrol route associated with the name You must determine if a given patrol route is valid based on the graph structure o Does the given path exist in the graph? . The number of pilots in each file is unknown The number of destinations in the patrol route for each pilot is unknown Pilot names may contain multiple words All input will be valicd. User Interface: There will be no user interface for this program. AIl I/O will be performed with files Objectives: Create and utilize a graph in Java Problem: Darth Vader wants to check that his TIE fighter pilots are patrolling adequately-sized regions of the galaxy. He has files of data that contain the patrol coordinates for each of his pilots. With the fear of being force choked, you have agreed to write a program that analyzes the data and determines if the patrol path is valid Pseudocode Details: Since this project focuses on the use of pre-made classes, detail your main class What functions will you create other than main . o What parameters will you have o What will the function return o What is the logic of the function What will the logic of main be? Details: A map of the galaxy will be given and will be stored in a graph o Utilize the provided Graph class in eLearning to hold the graph information .Each pilot will have a patrol route associated with the name You must determine if a given patrol route is valid based on the graph structure o Does the given path exist in the graph? . The number of pilots in each file is unknown The number of destinations in the patrol route for each pilot is unknown Pilot names may contain multiple words All input will be valicd. User Interface: There will be no user interface for this program. AIl I/O will be performed with files