Last modified: Thu Aug 16 2018 22:49:02 GMT+0800 (Malay Peninsula Standard Time)

## Chapter 7. Shortest Path Finder

This Shortest Path Finder Web Application will be build on top of Chapter 6’s Application. In Chapter 6, we created an application that is able to retrieve coordinates from the database and plot on the map. We are going to use Dijkstra Shortest Path algorithm and available library to plot the shortest path between two routers. The use case for this application would allow Network Engineer to travel the least distance while doing a monthly maintenance.

Do note that this example is a class project. Do not duplicate this project and submit as your class project without seeking the permission of the author. You may put yourself into trouble due to this is the author’s original work.

### 7.1 Initial Setup

To begin, follow the instruction the instruction in Chapter 6.1, 6.2, and 6.3 to install the require Gem. At this point, we have everything setup correctly. The example in this chapter will also use the Router example.

In order for our application to calculate the distance and find the shortest path between two points, we need to generate a table that store the distance between two points. You may need to look up how Dijkstra Shortest Path algorithm works before continue reading this chapter.

To create a database table that stores two points, `begin` and `end`, and the distance or cost between two points, unit, we use the command below. Depending on your preference, you may use a reference key instead of the method that I use below.

`rails g scaffold Point begin:string end:string unit:float`

After that, perform a database migration.

By default, when we are creating a new point, there are three input parameters: `begin`, end, and unit. Since we are going to allow user to choose the points from our table that contains coordinates, we only need two fields: `begin` and `end`. The unit or distance between two points will be calculated based on the formula we will create later.

Perform the modification as shown in Table 7.1.1 to allow user to choose the `begin` and `end` point from the coordinates database that we have. In this case, the coordinates are coming from Router database table.

Table 7.1.1: Code to remove and add from form

``````#MyApp/app/views/points/_form.html.erb

#Code to remove
<div class="field">
<%= f.label :begin %>
<%= f.text_field :begin %>
</div>

<div class="field">
<%= f.label :end %>
<%= f.text_field :end %>
</div>

<div class="field">
<%= f.label :unit %>
<%= f.text_field :unit %>
</div>

<div class="field">
<%= f.collection_select :begin, Router.order(:name), :name, :name, :prompt => "Select Start Point" %>
</div>

<div class="field">
<%= f.collection_select :end, Router.order(:name), :name, :name, :prompt => "Select End Point" %>
</div>
``````

API for connection_select method can be found here. You may have to read the documentation in order to understand what is each field in the method.

``````collection_select(object, method, collection, value_method, text_method, options = {}, html_options = {})
``````

Figure 7.1.1 shows the new point after the modification is made according to Table 7.1.1. Figure 7.1.1: Creating new point

Figure 7.1.2 shows a drop down menu with information populated from Router database table. Select two different `begin` and `end` point and you should be able to create a point without any issue. Figure 7.1.3 shows a point is created successfully with different `begin` and `end` point.  Figure 7.1.3: Point was successfully created

### 7.2 Distance Calculation

To calculate the distance between two coordinates, we need to define a method and use some math formula. Add the following code in Table 7.2.1 to your `controller`. The method distance_between will take in four parameters and it will return the distance in meters.

Table 7.2.1: Code to add to `controller`

``````#MyApp/app/controllers/points_controller.rb

def distance_between(lat1, lon1, lat2, lon2)
rm = 6371000 # Earth radius in meters

c = 2 * Math::atan2(Math::sqrt(a), Math::sqrt(1 - a))

rm * c # Delta in meters
end
``````

After that, follow the instruction in Table 7.2.2 to add the code to controller. In Table 7.2.2, we create a `load_distance_to_db` method to obtain the name from the dropdown menu where user selects. The selected values will then assigned to `@start_point` and `@end_point`. We then look up the Router database table to find the row where it matches the name. .first method is used to get the first row of the result. The coordinates of start and end points will be parsed into the distrance_between method and the result will then assigned to `@ans`.

Table 7.2.2: Code to add to `controller`

``````#MyApp/app/controllers/points_controller.rb

@start_point = params[:point][:begin]
@end_point = params[:point][:end]

@get_start_point = Router.all.where('name' => @start_point).first
@get_end_point = Router.all.where('name' => @end_point).first

@start_long = @get_start_point.longitude
@start_lat = @get_start_point.latitude

@end_long = @get_end_point.longitude
@end_lat = @get_end_point.latitude

@ans = distance_between(@start_lat, @start_long, @end_lat, @end_long)
end
``````

After that, follow the instruction in Table 7.2.3 to add the code to controller. In Table 7.2.3, we create a `check_param` method to check if the begin is equal to the end point. If begin is equal to the end point, it will redirect user back to the form and alert them that they have chosen the same point. The create and update method are altered slightly to make include the calculation method that we defined earlier.

Table 7.2.3: Code to add to `controller`

``````MyApp/app/controllers/points_controller.rb

#Code to delete
def create
@point = Point.new(point_params)

respond_to do |format|
if @point.save
format.html { redirect_to @point, notice: 'Point was successfully created.' }
format.json { render :show, status: :created, location: @point }
else
format.html { render :new }
format.json { render json: @point.errors, status: :unprocessable_entity }
end
end
end

def update
respond_to do |format|
if @point.update(point_params)
format.html { redirect_to @point, notice: 'Point was successfully updated.' }
format.json { render :show, status: :ok, location: @point }
else
format.html { render :edit }
format.json { render json: @point.errors, status: :unprocessable_entity }
end
end
end

def check_param
if params[:point][:begin].blank? || params[:point][:end].blank?
redirect_to(:back, notice: "Select something!") and return
end
end

def create
check_param
@point = Point.new
@point.begin = params[:point][:begin]
@point.end = params[:point][:end]
@point.unit = @ans

respond_to do |format|
if @point.begin == @point.end
redirect_to(:back, notice: "Begin and End are the same!") and return
elsif @point.save
format.html { redirect_to action: "index", notice: 'Point was successfully created.' }
format.json { render :show, status: :created, location: @point }
else
format.html { render :new }
format.json { render json: @point.errors, status: :unprocessable_entity }
end
end
end

def update
check_param

@point.begin = params[:point][:begin]
@point.end = params[:point][:end]
@point.unit = @ans

respond_to do |format|
if @point.begin == @point.end
redirect_to(:back, notice: "Begin and End are the same!") and return
elsif @point.update(point_params)
format.html { redirect_to action: "index", notice: 'Point was successfully updated.' }
format.json { render :show, status: :ok, location: @point }
else
format.html { render :edit }
format.json { render json: @point.errors, status: :unprocessable_entity }
end
end
end
``````

After the modification is made, remove the existing points. Create a new points by choosing two different locations and the distance will then be calculated and stored in unit field in database. Figure 7.2.1 shows the distance between two points is calculated successfully. Figure 7.2.1: Distance between two points is calculated successfully

### 7.3 Dijkstra Library

There is one `Dijkstra` Gem, dijkstra, available that can calculate the shortest distance between two points. However, I found out that the Gem is not really useful for what I am doing. I extracted the main class and include it in my Web Application’s library folder. You may obtain the main class from the `dijkstra` Gem’s repository or use the code in Table 7.3.1.

Table 7.3.1: Main class of `Dijkstra` Gem

``````#File to create
MyApp/lib/dijkstra.rb

# Class that calculates the smallest path using Dijkstra Algorithm
class Dijkstra                # constructor of the class
@start = startpoint   # start node
@end = endpoint     # end node
@path = []
@infinit = Float::INFINITY

# Recreating matrix_of_road to avoid passing the number
# of vertices in the first element.

dijkstra                      # Dijkstra's algorithm in action and good luck
end

# Calculates the number of vertices (unique elements) in a matrix of road
def number_of_vertices(matrix)
# Ignoring the weight element (third element)
matrix = matrix.collect { |x| [x, x] }
matrix = matrix.zip.flatten.compact   # Merging all the path arrays
@nodes = matrix.uniq.dup               # All the vertices
matrix.uniq.count                # Returning the number of unique elements (vertices)
end

# This method determines the minimum cost of the shortest path
def cost
@r[@end]
end

# get the shortest path
def shortest_path
@path
end

@path.push(node)
end

def dijkstra
min = @infinit
pos_min = @infinit

@nodes.each do |i|
@f[i] = @start if i != @start && @r[i] < @infinit
end

@s[@start] = 1

@nodes[0..@nodes.size - 2].each do
min = @infinit

@nodes.each do |i|
if @s[i] == 0 && @r[i] < min
min = @r[i]
pos_min = i
end
end

@s[pos_min] = 1

@nodes.each do|j|
if @s[j] == 0
if @r[j] > @r[pos_min] + @road[[pos_min, j]]
@r[j] = @r[pos_min] + @road[[pos_min, j]]
@f[j] = pos_min
end
end
end
end
end

n = arr.size - 1

@r = Hash.new(@nodes)
@s = Hash.new(@nodes)
@f = Hash.new(@nodes)

@nodes.each do |i|
@r[i] = 0
end

@nodes.each do |i|
@s[i] = 0
end

@nodes.each do |i|
@f[i] = 0
end

@nodes.each do |i|
@nodes.each do |j|
if i == j
else
end
end
end

(1..n).each do |i|
x = arr[i]
y = arr[i]
c = arr[i]
end
end
end
``````

To use the library, include the `dijkstra` library by specifying `require 'dijkstra'` at the beginning of your `controller`.

### 7.4 Search and Result Page

Now, we need to create a search page and a result page. You can use any existing `controller` for two of the pages. For my choice, I am going to leave it in my `points_controller`. Table 7.4.1 shows the newly created method for two new pages.

Table 7.4.1: Code to add to `controller`

``````#MyApp/app/controllers/points_controller.rb

def search
end

def result
end
``````

In my `routes.rb`, I have to add the route as shown in Table 7.4.2 to two of the pages.

Table 7.4.2: Code to add to `routes`

``````#MyApp/app/config/routes.rb

get '/search' => 'points#search', :as => ‘points_search’
post '/result' => 'points#result', :as => ‘points_result’
``````

Then, we have to create two new files for the view. Table 7.4.3 shows two of the new pages are located in `Points`’ view.

Table 7.4.3: Code to add to view

``````#File to create
MyApp/app/views/points/search.html.erb
MyApp/app/views/points/result.html.erb
``````

Since we do not have anything in the two newly created files yet, the page should show a blank page. Figure 7.4.1 shows an empty page for `localhost:3000/search`. Figure 7.4.1: Empty page

You should be able to visit `localhost:3000/search` but not `localhost:3000/result` since POST method (refer to Table 7.4.2) will create a new resources.

In our `search` page, we are going to have a Google Map and drop down menus to allow user to choose from two points while the result page will show the result on a Google Map. Table 7.4.4 shows the code for dropdown menu, Google Map, and required Google Map script.

Table 7.4.4: Code to add to `search` page

``````#MyApp/app/views/points/search.html.erb

<h1>Input Path</h1>

<%= form_tag(points_result_path, method: "post") do |f| %>
<%= collection_select :point, :begin, Router.order(:name), :name, :name, :prompt => "Select Start Point" %>
<%= collection_select :point, :end, Router.order(:name), :name, :name, :prompt => "Select End Point" %>
<%= submit_tag 'Submit', class: "button btn btn-primary" %>
<% end %>

<div style='width: auto;'>
<div id="map" style='width: auto; height: 500px;'></div>
</div>

<script type="text/javascript">
handler.buildMap({ provider: {}, internal: {id: 'map'}}, function(){
handler.bounds.extendWith(markers);
handler.fitMapToBounds();
});
</script>
``````

You may need to look up the documentation for collection_select helper. Do note that `f.collection_select` and `collection_select` are two different helpers.

Table 7.4.5 shows the code for result page. The page contains a Google Map and a table to show the visited path in detail. The table will provide starting point, ending point, distance travelled in km and distance travelled in miles,

Table 7.4.5: Code to add to result page

``````#MyApp/app/views/points/search.html.erb

<h1>Shortest Path</h1>

<div style='width: auto;'>
<div id="map" style='width: auto; height: 500px;'></div>
</div>

<script type="text/javascript">
handler.buildMap({ provider: {}, internal: {id: 'map'}}, function(){
polyline = <%=raw @output.to_json %>;
handler.bounds.extend(polyline);
handler.bounds.extend(polyline[ polyline.length - 1]);
handler.fitMapToBounds();
});
</script>

<h3>Results</h3>
Starting Point: <%= @start_point %><br>
Ending Point: <%= @end_point %><br>
<br>
Distance travelled (km): <%= @distance_km %> km<br>
Distance travelled (miles): <%= @distance_mi %> mi<br>
``````

### 7.5 Define Search and Result in Controller

The only thing we are missing right now is we have to puzzle everything we have in controller. In Table 7.5.1, we created a new method, `load_plot`. The method will create fetch @plots object and place it in `Gmaps4rails` class and method, a method in the Google Map Gem. The name of each of the Router’s name will be put into the info window on the Google Map in `load_plot` method.

Table 7.5.1: Code to add to controller

``````#MyApp/app/controllers/points_controller.rb

def search
@plots = Router.all
end

@search_default = Gmaps4rails.build_markers(@plots) do |plot, marker|
marker.lat plot.latitude
marker.lng plot.longitude
marker.infowindow plot.name
end
end
``````

Figure 7.5.1 shows a Google Map with router’s name showing on the info window. Figure 7.5.1: Result of the View

After the modification above is made, in my search page, we are able to see the name of each router on the map in the info window. We are still unable to perform any search since we have not completely defined our result method. Table 7.5.2 shows the updated method for search and result.

Table 7.5.2: Code to add to `controller`

``````#MyApp/app/controllers/points_controller.rb

def search
@plots = Router.all
end

def result
@c = Router.pluck(:name, :longitude, :latitude)
@r_left = Point.pluck(:begin, :end, :unit)
@r_right = Point.pluck(:end, :begin, :unit)
@r = @r_left+@r_right

@start_point = params[:point][:begin]
@end_point = params[:point][:end]

@ob = Dijkstra.new(@start_point, @end_point, @r)
@shortest_path = @ob.shortest_path
@distance = @ob.cost
@distance_km = (@distance/1000).round(3)
@distance_mi = (@distance*0.00062137).round(3)
@count = @shortest_path.count

\$i = 0;
\$num = @count;

@output = []

while \$i < \$num do
@result = Router.all.where('name' => @shortest_path[\$i])
@result.each do |result|
@output << { :lat => result.latitude, :lng => result.longitude}
end
\$i +=1
end

search
end
``````

### 7.6 Test and Verify Feature

In order to test and verify my newly added feature, I went to Google Map and obtained a new coordinates. The coordinates are stored in router database table. Then, I create new point by specifying the begin and end location. Figure 7.6.1 shows a list of `routers`’ location loaded to the database. Figure 7.6.1: A list of sample coordinates loaded to the Application

Figure 7.6.2 shows a list of points that I created. The points I loaded to my application are the walkable locations. Each location is connected to the junction. Figure 7.6.2: A list of points and the distance between two points were generated

In the search page, choose a starting and an ending point. Figure 7.6.3 shows “Associate Student House” is chosen as the starting point and “D1_05” is chosen as the ending point. The walkable distance is then drawn on the Google Map. The distance travelled in kilometer (km) and miles are also shown in the Results section. Figure 7.6.3: Result of the shortest path drawn on the screen