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
Order an Essay Now & Get These Features For Free:
Turnitin Report
Formatting
Title Page
Citation
Outline
