Algorithmics and Data Management 201920
Project 2: Cities and Rivers
The Mondial database contains information about cities and rivers. Each row of the located table indicates on which water body river, lake, or sea a city is located. The City column contains the city name and the River column contains the river name, or null if the the city is not on a river. In the river table each row describes a river. The Name column contains the river name and the River column contains the name of the river into which this river flows.
The goal of the project is to write an application that, given a city C located on a river R finds all the cities from which one can reach C by navigating on R or by navigating on rivers that flow directly or indirectly into R.
For example, if C is Geneva, one can reach Geneva from Sion by navigating on the Rhone, or from Lyon that is on the Saone that flows into the Rhone, or from Besancon that is on the Doubs that flows into the Saone that flows into the Rhone.
Specifications
Your program must
1. read the name of a city from the terminal 2. if the city is on a river print
the cities that are on the same river
the cities that are on a river that flows into this river
the cities that are on a river that flows into a river that flows into this river
etc.
For example if the entered name is Geneva the result should be
Sion, Villeurbanne
Lyon, Grenoble
Besancon
In this example there are only three levels from Besancon one can reach Geneva by navigating three rivers but the program must be able to handle any number of levels rivers.
G. FalquetS. Aljalbout Page 1
Algorithmics and Data Management 201920
Technical considerations
To query the Mondial database from a Scala program you can adapt the follow ing piece of code:
import java.net.
a method to find all the cities on river r
def citiesOnRiverr: String: SetString
val q select city from located where river r
val eq URLEncoder.encodeq, UTF8
val u new java.net.URL
http:kr.unige.chphpmyadminquery.php?dbMondialsqleq
val in scala.io.Source.fromURLu, iso88591
var res SetString
for line in.getLines
val cols line.splitt
res cols0
in.close
res
test
val r citiesOnRiverRhone
printlnr
Extra bonus not mandatory
You can improve your application by taking the lakes into account. For instance, Lausanne is not on the Rhone river but on the lake Lac Leman that flows into Rhone. Thus Geneva can be reached from Lausanne. In addition some rivers do not flow into a river but into a lake that flows into another river. In the river table if River and Sea are null and Lake is not null then Lake is the final destination of the river.
G. FalquetS. Aljalbout Page 2