Introduction

Recently I took up a small project of developing a Python package and deploying it on PyPI. The package is based on the famous problem in Graph Theory - Travelling Salesman Problem.

The simple procedure to solve this is by taking random nodes with random distance measures between the nodes and apply the concept of Dynamic Programming that breaks the bigger problem into smaller sub-problems and thus try to obtain the optimal solution for the bigger problem by first finding the optimal solution for smaller sub-problems. Recursive methods are applied subsequently to solve each sub-problem and thus solve the original problem.

Note

• To understand how to implement this programmatically, it is recommended that you refer to my medium blog where I explain the procedure in detail.

• I have implemented the same but taken it to the advanced level by considering the authentic place coordinates and finding the shortest path by taking appropriate distance measures.

Credits of Cover Image - Photo by Nicolas Van Leekwijck on Unsplash

Inception

The name of the package is dora-explorer. If you had watched any cartoons when you were a child, then you probably already know who Dora was. Dora The Explorer is the name of one such cartoon program in which Dora explores different places. I have just combined the concept of both cartoon and the traveling salesman problem where the programmer or the user can be beneficial.

Instead of just solving the problem by dynamic programming, I wanted to make it work for the real place names that are passed. In the background, it has to fetch the coordinate values and compute the distances and thus find the optimal shortest path. The package has certain methods to visualize the shortest path including the place coordinates on the map. Not just joining the lines from point A to point B, it can get the exact route that is required to reach point B from point A. Hence, all these features make the package very unique and new.

Installation

The current version of the package is 0.2.2 and the link can be found below.

It can be easily installed via pip.

pip install dora-explorer --user

Requirements

plotly
mpu
unidecode
geonamescache
requests

The pip command automatically installs the requirements.

import the package

from dora_explorer.distance_locator import DistanceLocator
from dora_explorer.travel_places import GeoTraveller
from dora_explorer.tiny_explore import DoraTheExplorer

Creating objects.

dis_loc = DistanceLocator()
geo_travel = GeoTraveller()

Defining from_place and to_place.

from_place = 'singapore'
to_place = 'new zealand'

Distance checking

The method get_distance() is used to get the distance between two places. The default distance is taken in km. Allowed options are -

• Miles
• Meters
• Feet and
• Yards

## kilometers
from_to_dis_km = dis_loc.get_distance(from_=from_place, to_=to_place)
print("The distance in kms from {} to {} - {} kms".format(from_place, to_place, from_to_dis_km))

## miles
from_to_dis_miles = dis_loc.get_distance(from_=from_place, to_=to_place, in_miles=True)
print("The distance in miles from {} to {} - {} miles".format(from_place, to_place, from_to_dis_miles))

## meters
from_to_dis_meters = dis_loc.get_distance(from_=from_place, to_=to_place, in_meters=True)
print("The distance in meters from {} to {} - {} meters".format(from_place, to_place, from_to_dis_meters))

## feet
from_to_dis_feet = dis_loc.get_distance(from_=from_place, to_=to_place, in_feet=True)
print("The distance in feet from {} to {} - {} feet".format(from_place, to_place, from_to_dis_feet))

## yards
from_to_dis_yards = dis_loc.get_distance(from_=from_place, to_=to_place, in_yards=True)
print("The distance in yards from {} to {} - {} yards".format(from_place, to_place, from_to_dis_yards))

Output

'The distance in kms from singapore to new zealand - 8358.12 kms'
'The distance in miles from singapore to new zealand - 5194.6 miles'
'The distance in meters from singapore to new zealand - 8358116.45 meters'
'The distance in feet from singapore to new zealand - 27422980.08 feet'
'The distance in yards from singapore to new zealand - 9143779.4 yards'

We can also visualize the distance plot from from_place to to_place. To do this, we require a map. Hence, it is preferred to have MapBox API that can be obtained from the official website.

I have saved my API in a mapbox_api.txt file.

read() the MapBox API

with open(file='mapbox_api.txt', mode='r') as api_file:
    map_api = api_file.read()

To get the distance plot, we have to use the method get_distance_plot() and the argument geo_token should take a string value (API).

There are two main conditions to get the appropriate distance plot.

Case - 1: If geo_token=map_api then

• If from_place and to_place belong to the same country, then with_map=True and with_directions=True.

## belong to the same country - India
from_place = 'delhi'
to_place = 'bengaluru'

dis_loc.get_distance_plot(
    from_=from_place, 
    to_=to_place, 
    with_map=True, 
    with_directions=True, 
    geo_token=map_api
)

• If from_place and to_place belong to differernt countries, then with_map=True and with_directions=False.

from_place = 'singapore'
to_place = 'new zealand'

dis_loc.get_distance_plot(
    from_=from_place, 
    to_=to_place, 
    with_map=True, 
    with_directions=False, 
    geo_token=map_api
)

Case - 2: If geo_token=None or geo_token="" then with_map=False and with_directions=False.

• The distance plot will be simply a line plot from two coordinates (latitudes and longitudes).

from_place = 'delhi'
to_place = 'bengaluru'

dis_loc.get_distance_plot(from_=from_place, to_=to_place)

Shortest Path

In order to get the shortest path, a list of places should be given as input. There are two possible conditions to get the result.

Case - 1: If the list of places belong to the same country considering geo_token=map_api.

• Let's take the places belonging to Spain country.

place_list = ["madrid", "barcelona", "alicante", "palma"]
explore = DoraTheExplorer(place_list=place_list)

explore.get_path(
    source_city='palma',
    with_map=True,
    with_directions=True,
    geo_token=map_api
)

Output

'plot is saved successfully ...'
'palma >> barcelona >> madrid >> alicante >> palma'

Note - If geo_token=None and all the places belong to the same country, then a line plot is plotted after joining the coordinates (latitudes and longitudes).

Minimum distance to cover all the places

## kilometers
min_distance_km = explore.get_min_dis(source_city='palma')
print("The minimun distance to cover {} in kms - {}".format(place_list, min_distance_km))

## miles
min_distance_miles = explore.get_min_dis(source_city='palma', in_miles=True)
print("The minimum distance to cover {} in miles - {}".format(place_list, min_distance_miles))

## meters
min_distance_meters = explore.get_min_dis(source_city='palma', in_meters=True)
print("The minimum distance to cover {} in meters - {}".format(place_list, min_distance_meters))

## feet
min_distance_feet = explore.get_min_dis(source_city='palma', in_feet=True)
print("The minimum distance to cover {} in feet - {}".format(place_list, min_distance_feet))

## yards
min_distance_yards = explore.get_min_dis(source_city='palma', in_yards=True)
print("The minimum distance to cover {} in yards - {}".format(place_list, min_distance_yards))

Output

"The minimun distance to cover ['madrid', 'barcelona', 'alicante', 'palma'] in kms - 1372.78"
"The minimum distance to cover ['madrid', 'barcelona', 'alicante', 'palma'] in miles - 853.19"
"The minimum distance to cover ['madrid', 'barcelona', 'alicante', 'palma'] in meters - 1372780.0"
"The minimum distance to cover ['madrid', 'barcelona', 'alicante', 'palma'] in feet - 4504091.18"
"The minimum distance to cover ['madrid', 'barcelona', 'alicante', 'palma'] in yards - 1501821.32"

Case - 2: If the list of places belong to different countries considering geo_token=map_api or geo_token=None.

• Let's take the places belonging to different countries.

place_list = ['london', 'madrid', 'bengaluru', 'delhi']
explore = DoraTheExplorer(place_list=place_list)

explore.get_path(
    source_city='london',
    with_map=True,
    with_directions=True,
    geo_token=map_api
)

Note - Finding the shortest path or visualizing it can be difficult. The route directions API does not work if places belong to different countries.

Output

"Cannot find the shortest path, as the cities ['london', 'madrid', 'bengaluru', 'delhi'] do not belong to the same country."

Minimum distance to cover all the places

min_distance = explore.get_min_dis(source_city='london')
print(min_distance)

Output

"Cannot find the minimum distance to cover the cities ['london', 'madrid', 'bengaluru', 'delhi'] as they do not belong to the same country."

---

That's it. A simple package to explore the details of the places finally deployed and documented.

Additional Details

• The package is still under development. Quite a few features and bugs need to be added and resolved respectively.
• If you have liked the idea and the package, you can star it on my GitHub page.
• If you would like to contribute, you are welcome to open a PR.
• If you would like to report an issue, I would be happy to check and resolve the same.

End