portfolio

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<WRAP round info>
====== cs20pf22as13: Path Finding ======

===== Goals =====

  * Apply your knowledge of graphs and related algorithms to a real-world problem.
  * Define a class with methods that can produce driving directions.
</WRAP>

-----

<WRAP round help>
====== Prerequisites ======

This assignment requires familiarity with the [[:lecture materials/]] presented in class through [[:lecture materials/week 13]].
</WRAP>

-----

====== Background ======

[[https://en.wikipedia.org/wiki/International_E-road_network|Quoth the arbiter of all human information]]:

> The **international E-road network** is a numbering system for roads in Europe developed by the United Nations Economic Commission for Europe (UNECE). The network is numbered from E1 up and its roads cross national borders. It also reaches Central Asian countries like Kyrgyzstan, since they are members of the UNECE.

[[https://github.com/lassewesth|GitHub user Lasse Westh-Nielsen]] posted a [[https://gist.github.com/lassewesth/634281cced11147432cf232a2c36e080|CSV representation]] of much of the E-road network in September of 2016. A slightly modified version of this data (with country names more amenable to Google Maps) is available on our server in file ''[[http://jeff.cis.cabrillo.edu/datasets/e-roads.csv|/srv/datasets/e-roads.csv]]''.

Each of the 1239 lines in the file consists of 7 comma-delimited tokens describing a road segment:
  - A **road number**, e.g. ''E05''
  - An **origin country name**, e.g. ''Denmark''
  - An **origin place name**, e.g. ''Ålborg''
  - A **destination country name**
  - A **destination place name**
  - The **distance** of the segment (as an integer in km)
  - Whether the segment is a **water crossing** (''true'' or ''false'')

Here are the lines from the file regarding [[https://en.wikipedia.org/wiki/European_route_E5|E-road E5]]:

<wrap right>
{{:e-road-e5.png?nolink|Diagram/map of E-road E5}}
</wrap>

<code>
E05,UK,Greenock,UK,Glasgow,40,false
E05,UK,Glasgow,UK,Gretna,142,false
E05,UK,Gretna,UK,Carlisle,16,false
E05,UK,Carlisle,UK,Penrith,40,false
E05,UK,Penrith,UK,Preston,109,false
E05,UK,Preston,UK,Warrington,49,false
E05,UK,Warrington,UK,Birmingham,128,false
E05,UK,Birmingham,UK,Newbury,166,false
E05,UK,Newbury,UK,Southampton,71,false
E05,UK,Southampton,France,Le Havre,207,true
E05,France,Le Havre,France,Paris,196,false
E05,France,Paris,France,Orléans,134,false
E05,France,Orléans,France,Tours,118,false
E05,France,Tours,France,Poitiers,101,false
E05,France,Poitiers,France,Bordeaux,256,false
E05,France,Bordeaux,Spain,San Sebastián,243,false
E05,Spain,San Sebastián,Spain,Burgos,246,false
E05,Spain,Burgos,Spain,Madrid,250,false
E05,Spain,Madrid,Spain,Cordóba,391,false
E05,Spain,Cordóba,Spain,Sevilla,141,false
E05,Spain,Sevilla,Spain,Cádiz,122,false
E05,Spain,Cádiz,Spain,Algeciras,117,false
</code>

<wrap tip>For the purposes of this assignment, consider each road segment to be an undirected (or bidirectional) edge in a graph representing the E-road network.</wrap>

-----

<WRAP round todo>
====== Assignment ======

You shall define a class named ''ERoadNetwork'' in a module named ''e_roads'', instances of which contain a method to determine the shortest path between two locations in the road network defined by file ''e-roads.csv'', optionally excluding water crossings.

Method ''shortest_path()'' accepts two string arguments of the form '''place_name, country_name''' and returns the shortest path between those places in three different forms, e.g. for the shortest path between ''Greenock, UK'' and ''Edinburgh, UK'':
  - A tuple of place names along the path: <code python>('Greenock, UK', 'Glasgow, UK', 'Edinburgh, UK')</code>
  - A tuple of segments for each road traveled: <code python>(('E05', ('Greenock, UK', 'Glasgow, UK')), ('E16', ('Glasgow, UK', 'Edinburgh, UK')))</code>
  - A string formatted to be a Google Maps URL requesting directions between the place names: <code python>'https://www.google.com/maps/dir/Greenock,+UK/Glasgow,+UK/Edinburgh,+UK'</code>

The paths should look relatively sane compared with Google Maps' suggested driving directions, though there will likely be many differences due to the small dataset we are using:

{{:rotterdam_berlin_default.jpg?nolink|Default Google Maps driving directions from Rotterdam, Netherlands to Berlin, Germany}}

{{:rotterdam_berlin_path_url.jpg?nolink|Directions for URL produced by ERoadNetwork().shortest_path('Rotterdam, Netherlands', 'Berlin, Germany')}}
</WRAP>

===== Specifications =====

Use the following skeleton code as a template for your class. Several doctests are included for testing purposes, and to demonstrate the expected return value of method ''shortest_path()''. Note the potentially [[https://www.google.com/maps/dir/Stockholm,+Sweden/Tallinn,+Estonia|different]] [[https://www.google.com/maps/dir/Stockholm,+Sweden/Sundsvall,+Sweden/Umeå,+Sweden/Luleå,+Sweden/Haparanda,+Sweden/Tornio,+Finland/Kemi,+Finland/Oulu,+Finland/Jyväskylä,+Finland/Lahti,+Finland/Helsinki,+Finland/Vaalimaa,+Finland/Sankt-Peterburg,+Russia/Tallinn,+Estonia|paths]] when water crossings are included vs. excluded.

<file python e_roads.py>
"""
CS 20P: Shortest paths in the international E-road network.
"""

import collections
import heapq
import sys


class ERoadNetwork:
  """ Graph-based representation of the E-road network. """

  def __init__(self, include_water=True):
    """
    Initializes a path-finding object, optionally excluding water crossings.
    """
    pass  # TODO

  def shortest_path(self, src: str, dst: str) -> tuple[tuple, tuple, str] | None:
    """
    Returns several representations of the shortest path from `src` to `dst`.
    :param src: the starting location
    :param dst: the ending location
    :return: `None` if no path exists, or a tuple of three representations of the shortest path,
             as in the doctests below:

    >>> path_finder = ERoadNetwork()
    >>> import pprint
    >>> pprint.pprint(path_finder.shortest_path('Greenock, UK', 'Edinburgh, UK'))
    (('Greenock, UK', 'Glasgow, UK', 'Edinburgh, UK'),
     (('E05', ('Greenock, UK', 'Glasgow, UK')),
      ('E16', ('Glasgow, UK', 'Edinburgh, UK'))),
     'https://www.google.com/maps/dir/Greenock,+UK/Glasgow,+UK/Edinburgh,+UK')
    >>> pprint.pprint(path_finder.shortest_path('Stockholm, Sweden', 'Tallinn, Estonia'))
    (('Stockholm, Sweden', 'Tallinn, Estonia'),
     (('E20', ('Stockholm, Sweden', 'Tallinn, Estonia')),),
     'https://www.google.com/maps/dir/Stockholm,+Sweden/Tallinn,+Estonia')
    >>> land_only = ERoadNetwork(include_water=False)
    >>> pprint.pprint(land_only.shortest_path('Stockholm, Sweden', 'Tallinn, Estonia'))
    (('Stockholm, Sweden',
      'Sundsvall, Sweden',
      'Umeå, Sweden',
      'Luleå, Sweden',
      'Haparanda, Sweden',
      'Tornio, Finland',
      'Kemi, Finland',
      'Oulu, Finland',
      'Jyväskylä, Finland',
      'Lahti, Finland',
      'Helsinki, Finland',
      'Vaalimaa, Finland',
      'Sankt-Peterburg, Russia',
      'Tallinn, Estonia'),
     (('E04',
       ('Stockholm, Sweden',
        'Sundsvall, Sweden',
        'Umeå, Sweden',
        'Luleå, Sweden',
        'Haparanda, Sweden',
        'Tornio, Finland',
        'Kemi, Finland')),
      ('E75',
       ('Kemi, Finland',
        'Oulu, Finland',
        'Jyväskylä, Finland',
        'Lahti, Finland',
        'Helsinki, Finland')),
      ('E18',
       ('Helsinki, Finland', 'Vaalimaa, Finland', 'Sankt-Peterburg, Russia')),
      ('E20', ('Sankt-Peterburg, Russia', 'Tallinn, Estonia'))),
     'https://www.google.com/maps/dir/Stockholm,+Sweden/Sundsvall,+Sweden/Umeå,+Sweden/Luleå,+Sweden/Haparanda,+Sweden/Tornio,+Finland/Kemi,+Finland/Oulu,+Finland/Jyväskylä,+Finland/Lahti,+Finland/Helsinki,+Finland/Vaalimaa,+Finland/Sankt-Peterburg,+Russia/Tallinn,+Estonia')
    """
    pass  # TODO
</file>

===== Sample Executable =====

Sample executable ''cs20p_e_roads'' exists on the server and prints the expected path and Google Maps URL given two locations as command-line arguments, optionally excluding water crossings if you add a third command-line argument:

<code bash>
% cs20p_e_roads 'Greenock, UK' 'Madrid, Spain'
Greenock, UK
Glasgow, UK
Gretna, UK
Carlisle, UK
Penrith, UK
Preston, UK
Warrington, UK
Birmingham, UK
Newbury, UK
Southampton, UK
Le Havre, France
Paris, France
Orléans, France
Tours, France
Poitiers, France
Bordeaux, France
San Sebastián, Spain
Burgos, Spain
Madrid, Spain
https://www.google.com/maps/dir/Greenock,+UK/Glasgow,+UK/Gretna,+UK/Carlisle,+UK/Penrith,+UK/Preston,+UK/Warrington,+UK/Birmingham,+UK/Newbury,+UK/Southampton,+UK/Le+Havre,+France/Paris,+France/Orléans,+France/Tours,+France/Poitiers,+France/Bordeaux,+France/San+Sebastián,+Spain/Burgos,+Spain/Madrid,+Spain

% cs20p_e_roads 'Greenock, UK' 'Madrid, Spain' uh oh 
No path from Greenock, UK to Madrid, Spain!
</code>

===== Map Demo =====

(Geocoding for this map was done using the [[https://developers.google.com/maps/documentation/geocoding/overview|Google Geocoding API]], which may not exactly match the intent of some of these place names. But should be roughly correct.)

<html>
<label for="src-vertex">Start city:</label>
<select id="src-vertex" onchange="updateMap()"></select>
<label for="dst-vertex">End city:</label>
<select id="dst-vertex" onchange="updateMap()"></select>
<label for="xw">Exclude water crossings:</label>
<input type="checkbox" id="xw" onchange="updateMap()"></input>

<script>
function getCityNames() {
window.fetch('/datasets/e-roads.csv.all_cities.txt', {
  method: 'get'
}).then(response =>
  response.text()
).then(text => {
  cityNames = text.split('\n');
  cityNames.sort();
  ['src-vertex', 'dst-vertex'].forEach(id => {
    const select = document.getElementById(id);
    cityNames.forEach(cityName => {
      if (cityName === undefined)
         return;
      const option = document.createElement('option');
      option.value = cityName;
      option.innerText = cityName;
      if (id == 'src-vertex' && cityName == 'Greenock, UK' || id == 'dst-vertex' && cityName == 'Madrid, Spain')
        option.setAttribute('selected', true);
      select.appendChild(option);
    });
  });
}).catch(err => {
  console.log('Something bad happened: ' + err);
});
}

function updateMap() {
  const srcVertex = document.getElementById("src-vertex").value;
  const dstVertex = document.getElementById("dst-vertex").value;
  if (document.getElementById("xw").checked)
    document.getElementById("map-demo").src = `/util/e_roads?src=${srcVertex}&dst=${dstVertex}&xw=exclude_water`;
  else
    document.getElementById("map-demo").src = `/util/e_roads?src=${srcVertex}&dst=${dstVertex}`;
  document.getElementById("sample-executable-command").innerText = `cs20p_e_roads "${srcVertex}" "${dstVertex}"`;
}

getCityNames();

</script>
<iframe id="map-demo" src="/util/e_roads?src=Greenock, UK&dst=Madrid, Spain" width="900" height="500" frameborder="0"></iframe>
<pre id='sample-executable-command' class='code'>cs20p_e_roads "Greenock, UK" "Madrid, Spain"</pre>
</html>

-----

====== Submission ======

Submit ''e_roads.py'' via [[info:turnin]].

<WRAP round box>
{{https://jeff.cis.cabrillo.edu/images/feedback-robot.png?nolink }} //**Feedback Robot**//

This project has a feedback robot that will run some tests on your submission and provide you with a feedback report via email within roughly one minute.

<wrap em>Please read the feedback carefully.</wrap>
</WRAP>

====== Due Date and Point Value ======

<WRAP round important>
Due at 23:59:59 on the date listed on the [[:syllabus|syllabus]].

''Assignment 13'' is worth 60 points.

<code>
Possible point values per category:
---------------------------------------
Correct paths, with/without water:
  Between place names                20
  Broken into roads                  20
  As a Google Maps URL               20
Possible deductions:
  Style and practices            10–20%
Possible extra credit:
  Submission via Git                 5%
---------------------------------------
</code>
</WRAP>