Sustainable Transportation Networks
In the previous project we discussed the importance of sustainable transportion networks. As communities have integrated sustainable approaches to mass transit, technology companies have been working on various solutions to assist in the move towards environmental sustainability and the so-called “Smart Cities” movement. Consider the GoLA app, rolled out by Xerox in 2016, which helps citizens plot the most efficient means of transportation based on they needs:
Efficient routes and transportation methods are critical components of sustainable transportation. Recall the abstract “Detroit” graph showing an interconnected set of towns and roads:
If we were asked to find the shortest tour by which each city could be visited by a regional bus service, starting from Detroit and returning to Detroit, there are a few known algorithms from which we can choose. However, all of them tend to be very slow – indeed, the problem itself is deemed to be extremely complex in mathematical circles.
Mathematically, the problem can be stated as follows: Given a weighted graph G of vertices and edges between them, find a cycle of minimum weight where no two vertices are visited twice (save for the source and destination, which are the same vertex). Since a graph often involves multiple cycles, the idea is to find the least-cost route using some metric. Writing down all possibilities is often impractical for large values of n (where n is the number of vertices). For example, a graph of n vertices having an edge between every pair of distinct vertices would result in (n-1)! different cycles. To put this in perspective, if we had 40 vertices, and each circuit could be found in one microsecond, it would still take 6.5 x 1044 years to find the solution.
An alternative problem would be to simply find the minimum weight paths between the starting vertex and the other vertices. Algorithms to produce these paths would produce a tree, defined as a graph with no cycles.
Choosing the minimum weight solution has its advantages. By choosing the minimum weight solution, you are choosing the one that perhaps uses the least amount of fuel. This helps to minimize the amount of greenhouse gas emissions produced in transportation. Greenhouse gases can ultimately make the planet warmer by helping to trap heat. In 2015 alone, transportation emissions were responsible for 27% of the greenhouse gas emissions in the United States, according to the EPA. Watch the following video on how greenhouse gases work:
Shortest Path Algorithm
The most famous of the known algorithms for the “shortest path” problem is Dijkstra’s Algorithm. This algorithm is greedy by nature; at each step the best local choice is taken in the hope that this choice will lead to a globally optimal solution. The end result is a shortest path tree from a given source node. The following pseudocode implements the algorithm:
The above algorithm assumes that Q is a priority queue. A Queue is a “First-In, First-Out” data structure, closely resembling a waiting line in terms of adding and removing elements from the list. Elements are added to the Queue at the rear of the list, and are removed from the Queue at the front of the list. There are many applications of a Queue where each element is assigned a priority; the highest priority elements leave the Queue first. This type of Queue is a priority queue.
Java Project: Finding the Shortest Path
This project will provide you with an introduction to the fundamentals of object-oriented development in Java. The focus of this project is on how to solve simple problems using Java classes. At the end of this project, you will…
- Develop Java classes based on user descriptions.
- Develop Javadoc documentation for user-defined classes.
- Perform unit testing on user-defined classes.
- Integrate user-defined classes into a large, predefined program.
Exercise #0: Download and extract the Transportation2.zip file. Place all your code for Exercise #1 and Exercise #2 in the same folder as this code.
Exercise #1: Create a class file called DijkstraVertex.java. This class is a necessary component of implementing Dijkstra’s Algorithm, given the prior algorithm and the limitations of the existing Java implementation. The class will be used to support the prioritization of the vertices within the priority queue. Use the instructor-provided Javadoc as a guide to how to construct your class. A Unit Test (DijkstraVertexUnitTest.java) is provided.
Exercise #2: Create a class file called DijkstraVertexComparator.java. This class will be used for the “compare” operation involved with prioritizing the vertices within the priority queue. Use the instructor-provided Javadoc as a guide to how to construct your class. A Unit Test (DijkstraVertexComparatorUnitTest.java) is provided.
Exercise #3: Modify Transportation2.java to (a) allow users to enter a weight when they add an edge, and (b) add new menu option, shown in red below, to implement Dijkstra’s algorithm (don’t forget to ask the user for the “source” vertex, with appropriate error checking):
- Add a Vertex – add a vertex to the graph, making sure that no duplicates are added
- Add an Edge – add an edge to the graph, making sure that no duplicates are added
- Shortest Path – display the tree resulting from Dijkstra’s algorithm
- Display Adjacent List – display the adjacent vertices for the graph
- Quit – end the program
Your program should implement Dijkstra’s algorithm and produce output to the screen showing the edges of the resulting tree (as text, of course). Further details will be provided in class.
Deliverables
See the instructor for submission instructions and due date(s).