Bus Trip Planning - Java Classes For Graph And Bus Lines Essay.

Your program will store the city map and bus lines as an undirected graph. Every edge of the graph represents a street and every node represents either the intersection of two streets or the end of a dead-end street. There are two special nodes in this graph denoting the starting point S and the destination D. A modified depth first search traversal, for example, can be used to find a path as required.

The following figure shows an example of a map with three bus lines, a (pink), b (yellow), and (blue). The starting point is marked S and the destination is D. In all the maps that we will consider for this assignment, the streets will be arranged in a grid. Furthermore, only buses of one bus line will run on any given street (so buses from two different lines cannot drive along the same street; however, they can go through intersections with streets where buses from other lines run).

You are to implement at least four Java classes: GraphNode, GraphEdge, Graph, and BusLines.You can implement more classes if you need to, as long as you follow good program design and information-hiding principles.You must write all code yourself. You cannot use code from the textbook, the Internet, other students, or any other sources. However, you are allowed to use the algorithms discussed in class. For each one of the classes below, you can implement more private methods if you want to, but you cannot implement additional public methods.

GraphNode Class

Bus Trip Planning

* GraphNode class implements a node of the graph

* Represents intersection of two streets, starting & end point, or a dead-end street

public class GraphNode {

private int nodeName;

private boolean isMarked = false; // a new node is not marked by default/**

 * Constructor for GraphNode: creates an unmarked node with the given name

 * @param name an integer value between 0 and n-1, where n is the number of nodes on the graph

 */

public GraphNode(int name) {

nodeName = name;

isMarked = false; // a new node is not marked by default**

 * Setter method for node mark status

 * Marks the node with the specified value (true or false)

 * useful when traversing the graph to know which vertices have already been visited

 * @param mark boolean status for the node mark

 */

public void setMark(boolean mark) {

isMarked = mark;*

 * Getter method for the node mark status

 * @return cthe value with which the node has been marked */

public boolean getMark() {

return isMarked;**

 * Getter method for node name

 * @return name this is the name of the node

 */

public int getName() {

return nodeName;

}

Bus Trip Planning

* GraphEdge class implements the edge of the graph

* Edges represent streets public class GraphEdge

private GraphNode U, V; // the first ad second points

private char Busline;/**

* Constructor method for GraphEdge:  creates an edge for the busline*

* @param u       first endpoint of the edge

* @param v       second endpoint of the edge

* @param busLine a character representing the busline associated for the given edge*/

public GraphEdge(GraphNode u, GraphNode v, char busLine) {

U = u;

V = v;

Busline = busLine;/**

* Getter method for the first end point of the edge

* @return U    The first end point of the edge*/

public GraphNode firstEndpoint() {

return U;

/**

* Getter method for the second end point of the edge

* @return V    The second end point of the edge

*/

public GraphNode secondEndpoint() {

return V;

/**

* Getter method for the busline to which the edge belongs

* @return Busline  The bus line associated with the edges (street)

*/

public char getBusLine() {

return Busline;

Bus Trip Planning*

* Graph class implements an undirected graph

* makes use of adjacency matrix representation for the graph

* Implements GraphADT interface.

import java.util.*;

public class Graph {

private GraphNode nodes[];

private GraphEdge edges[][];/**

* Constructor for Graph class creates a graph with n nodes and no edges

* @param n number of nodes - 1

nodes = new GraphNode[n];

// Multidimentional array for Edges

edges = new GraphEdge[n][n];

// Nodes initialization loop

for (int i = 0; i < n; i++) nodes[i] = new GraphNode(i);/**

* insertEdge method adds an edge connecting two nodes (u,v) on a busline specified

* @param u first edge end point

* @param v second edge end point

* @param busLine   busline to have the edge

* @throws GraphException thrown when a node does not exist or when the edge already exists*/

GraphEdge Class

public void insertEdge(GraphNode u, GraphNode v, char busLine) throws GraphException{

// Node Names

int uName = u.getName();

int vName = v.getName();

boolean hasValid_u_length = uName < nodes.length;

boolean hasValid_v_length = vName < nodes.length;

boolean hasValid_u_name = uName >= 0;

boolean hasValid_v_name = vName >= 0;

// Proceed only on valid nodes (names and length)

if (hasValid_u_name && hasValid_v_name && hasValid_u_length && hasValid_v_length){

// Proceed to insert the edges given that they do not exist.

if ((edges[uName][vName] == null) && (edges[vName][uName] == null)){

edges[uName][vName] = new GraphEdge(u, v, busLine);

edges[vName][uName] = new GraphEdge(v, u, busLine);}

else throw new GraphException("ERROR 404: Edge already exists"); // Throw GraphException error when the edge already exists}

else throw new GraphException("ERROR 404: invalid node"); // Throw GraphException error on an invalid node

getNode method returns the node specified  by the name

* @param name  the name of the node to return

* @return node as specified by the name passed

* @throws GraphException when the node does not exist*/

public GraphNode getNode(int name) throws GraphException{

boolean hasNodeName = !(name < 0);

boolean isValidNode = name < nodes.length;

// return the node given that a valid name has been provided

if (hasNodeName && isValidNode) {

GraphNode node = nodes[name];

return node; // return the node}

throw new GraphException("Invalid node"); // throw GraphException on invalid node/**

* incidentEdges method gets an iterator to stores all edges incident on node u

* @param u The node whose incident edge are to be searched

* @return iterator for the incident edges else null when incident edges lacking

* @throws GraphException thrown on an invalid node encounter*/

public Iterator<GraphEdge> incidentEdges(GraphNode u) throws GraphException{

boolean hasUname = u.getName() >= 0;

boolean isValidUname = u.getName() < nodes.length;

// given that the node is valid, create a stack of edges and return the iterator for the stack

if (hasUname && isValidUname){

// create a stack of edges

Stack<GraphEdge> incidentEdges = new Stack<GraphEdge>();

// push edge to the stack for every edge in the graph that are incident to u

int i = 0;

while (i < nodes.length) {

if (edges[u.getName()][i] != null) incidentEdges.push(edges[u.getName()][i]); // push edge to the stack

/ return the iterator for the stack given that it's not empty

if (!incidentEdges.isEmpty()) return incidentEdges.iterator();

return null; // return null on an empty stack

}

throw new GraphException("Invalid node"); // throw an exception if a node is invalid/**

* getEdge method returns the edge connecting the two specified nodes

* @param u the first edge end point

* @param v the second edge end point

* @return edge connecting the two nodes (u,v) or null when no such edge exists

* @throws GraphException   thrown on an invalid node, or when no edge connecting the two nodes exists

*/

public GraphEdge getEdge(GraphNode u, GraphNode v) throws GraphException{

/ no valid nodes, return the edge. Throw GraphException otherwise

if (u.getName()>=0 && v.getName()>=0 && u.getName()<nodes.length && v.getName()<nodes.length){

// given that there is an existing edge, return it.

GraphEdge edge = edges[u.getName()][v.getName()];

if (edge != null) return edge;

Graph Class

throw new GraphException("No edge between specified nodes");}

throw new GraphException("Invalid node"); method returns true or false on whether the two specified nodes are adjacent

* @param u first node

* @param v second node

* @return boolean  true when the two nodes are adjacent, else false

* @throws GraphException   thrown on an invalid node*/

public boolean areAdjacent(GraphNode u, GraphNode v) throws GraphException{

boolean hasUname = u.getName() >= 0;

boolean hasVname = v.getName() >= 0;

boolean isValidUname = u.getName() < nodes.length;

boolean isValidVname = v.getName() < nodes.length;

// given valid nodes, check whether there exists an edge connecting them

if (hasUname && hasVname && isValidUname && isValidVname)

return edges[u.getName()][v.getName()] != null;

throw new GraphException("Invalid node"); // throw an exception if a node is invalid

import java.util.Stack;

import java.io.FileReader;

import java.io.BufferedReader;

import java.util.Iterator;

public class BusLines {

private Stack<GraphNode> stack = new Stack<GraphNode>();

private Graph buslines;

private GraphNode start, end;

private int changes;/**

* BusLines constructor method builds a city map with bus lines as described by the input file specified

* @param inputFile file contaning description of city streets bus lines

* @throws MapException Thrown on an invalid input file.*/

public BusLines(String inputFile) throws MapException{

try {

BufferedReader input = new BufferedReader(new FileReader(inputFile));

String line = input.readLine(); // read the first line, which has map specifications

String[] specs = line.split(""); // spit the line into an array of columns

int width = Integer.parseInt(specs[1]);

int length = Integer.parseInt(specs[2]);

buslines = new Graph(width * length); // Create a graph with (width * length) nodes

int changes = Integer.parseInt(specs[3]); // number of bus line changes

// Read the first line of elements

line = input.readLine();

// Initialize counters

int countGraphNode = 0, columnGraphNode = 0, columnCount = 0, counter = 0;

for(int i = 0; i < (length*2)-1; i++){

// given an even row

for(int j = 0; j < (width*2)-1; j++)

if (i % 2 == 0) { // given an even column

if (j % 2 == 0) {

// given character S, set the starting point

if (line.charAt(j) == 'S') start = buslines.getNode((i / 2 * width) + (j / 2));

// given character D, set the end point

else if (line.charAt(j) == 'D') end = buslines.getNode((i / 2 * width) + (j / 2));

// given character '.' (dot), do nothing

else if (line.charAt(j) == '.') {

// given '' (space) character, increment the node counter

else if (line.charAt(j) == '') countGraphNode++;

else {  // else insert an edge

Create a String for the bus line

char s = line.charAt(j);

// insert an edge into the graph

buslines.insertEdge(buslines.getNode(countGraphNode), buslines.getNode(countGraphNode + 1), s);

countGraphNode++; // increment the node counter}

} else { // given that the column is odd:

// set the start-point given that the character is S

if (line.charAt(j) == 'S') start = buslines.getNode((i / 2 * width) + (j / 2));

// set the end-point given that the character is D

else if (line.charAt(j) == 'D') end = buslines.getNode((i / 2 * width) + (j / 2));

// do nothing when the character is a dot (.)

BusLines Class

else if (line.charAt(j) == '.') {

// increment the node counter given the character is a space

else if (line.charAt(j) == '') countGraphNode++;

//  insert an edge given that the character is a letter

else {

char s = line.charAt(j); // get busline character

buslines.insertEdge(buslines.getNode(countGraphNode), buslines.getNode(countGraphNode + 1), s);

countGraphNode++;

Given an odd row

else {

// If the column is even

if (j % 2 == 0) {

// given that the character is a space, increment the column counters

if (line.charAt(j) == '') {

columnGraphNode++;

columnCount++;

// given that the character is a letter, insert an edge and increment the column counters

else {

char s = line.charAt(j); // get busline charecter

buslines.insertEdge(buslines.getNode(columnCount), buslines.getNode(columnGraphNode), s);

columnGraphNode++;

columnCount++;

// given an odd column

else if (line.charAt(j) != '') {  // set a busline character given that it is not a space,

char s = line.charAt(j);

buslines.insertEdge(buslines.getNode(columnCount), buslines.getNode(columnGraphNode), s);

columnGraphNode++;

columnCount++;

// read the next line of characters

line = input.readLine();

// Increment the node counter given that the counter is even

if(counter%2==0) countGraphNode++;

// set the column node counter to width given that counter is zero

if(counter==0) columnGraphNode = width;

catch (Exception e) {

throw new MapException("Problem with input file");

* Getter method for Graph: returns the buslines graph

* @return buslines a graph with bus lines initialized

* @throws MapException thrown when there are no bus lines to be initialized

*/

public Graph getGraph() throws MapException{

if (buslines != null) return buslines;

throw new MapException("Graph not initalized");

* trip method finds the path from the starting node to the ending node

* @return stack    iterator with nodes along the nodes path

* @return null when no path is found

* @throws GraphException thrown on an improper buslines graph

public Iterator<GraphNode> trip(){

try {

// Create iterator for the incident edges from start

Iterator<GraphEdge> incident = buslines.incidentEdges(start);

// Create an edge to be use in path method

GraphEdge check = new GraphEdge(start, end, 'C');

// While the iterator is not empty

if (incident.hasNext()) {

do {

// set check to be the next element in the iterator and find path

check = incident.next();

path(start, end, check);

// given an empty stack return the iterator

if (!stack.empty()) return stack.iterator();

} while (incident.hasNext());}

catch (GraphException e) { // improper graph

System.out.println("Error: Exception caught. Improper Graph");}

return null; // path does not exist/**

* path method finds the path from a starting node to the destination node

* @param start starting node

* @param end   destination node

@param check edge used to check bus lines

* @return true when a path is found, false otherwise*/

private boolean path(GraphNode start, GraphNode end, GraphEdge check){

// push starting node into stack

stack.push(start);try {

// set starting nodes mark to true

start.setMark(true);

// Create an iterator that has the nodes incident to start

Iterator<GraphEdge> incident = buslines.incidentEdges(start);

// While the iterator has next, create a node that is the next edge on the iterator

while(incident.hasNext()){

GraphEdge discovery = incident.next();

GraphNode u = discovery.secondEndpoint();

// given u has no mark

if(u.getMark() != true){

if(discovery.getBusLine()==check.getBusLine()){

check = discovery;

if(path(u, end, check)) return true; // path found

else // given same bus lines

if (changes > 0) {

changes--; // decrement changes

check = discovery; // let check reference discover

// Call path recursively with u has the start point

if (path(u, end, check)) return true; // path found

changes++; // increment changes when no path has been found

start.setMark(false); // set the starting nodes mark to false when no path

stack.pop(); // pop the stack

atch (GraphException e) {

System.out.println("ERROR: Invalid Graph");

return false; // no path found