Exercise 2: Coding Portion

CMPUT 275 Wi18 - INTRO TO TANGIBLE COMPUT II
Combined LBL Wi18
Exercise 2: Coding Portion
This coding portion has three main parts:
Implement a function that efficiently counts the number of connected components in an
undirected graph (modelled as a directed graph where both (u,v) and (v,u) directed edges are
present for each undirected edge uv). (6 marks)
1.
Implement a function that reads the data in a comma-separated values (CSV) file that describes a
city's road network and returns an instance of the Graph class developed in the lecture (and
included with the files for Assignment 1) corresponding to the undirected version of that road
network.
That is, for every edge in the graph file you should add both directions of that edge to the
directed graph. (3 marks)
2.
When your code run via
python3 count_components.py
it should build the undirected version of the Edmonton road network, call the function to count
the number of components, and then print this number to the terminal. (1 mark)
3.
You will add the above-mentioned two functions to a new script count_components.py.
The script should work when placed in the same directory as the files graph.py and
breadth_first_search.py in the Google Drive directory for lecture 5 as well as the .txt file with the
Edmonton graph from Assignment 1. All your code should be contained in the file
count_components.py. Do not modify the script files we provided.
Submit only count_components.py and do not zip it. If you needed to modify the other files to get a
working solution, then submit them all in one .zip and include a README file describing the changes.
However, modifying the other files will result in a deduction.
The details of the individual tasks mentioned are described below.
1) Counting Components
Implement a function count_components(g) that takes a single parameter g, an instance of the class
Graph that we constructed in the lectures. The function should return a single integer that is the
number of connected components in the graph g. This function assumes for each directed edge (u,v)
in g that there is also a directed edge (v,u) in g. As discussed in the lectures, this is a way to model an
undirected graph using our directed graph class.
Recall a connected component of an undirected graph is a subset of vertices C such that there is a
path between any two nodes in C and there is no path between a vertex in C and a vertex lying outside
of C.
For full marks this function should run in linear time, i.e. O(n+m) where n is the number of vertices
in the graph and m is the number of edges. Recall that our convention is to say that a single dictionary
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
1 of 4 2018-04-14, 12:57 p.m.
insertion or lookup take O(1) time.
An example of an interaction is the following. It uses ipython3, which is started from the same
directory where all the scripts are.
from graph import Graph
from count_components import count_components
g = Graph()
vertices = {1, 2, 3, 4, 5, 6}
edges = [(1, 2), (3, 4), (3, 5), (4, 5)]
for v in vertices: g.add_vertex(v)
for e in edges: g.add_edge( (e[0], e[1]) )
for e in edges: g.add_edge( (e[1], e[0]) )
count_components(g)
3
g.add_edge( (1, 4) )
g.add_edge( (4, 1) )
count_components(g)
2
To illustrate this interaction, the graph g in the first call to count_components looks like
and has connected components {1,2}, {3,4,5} and {6}. The function should return 3.
After the edge (1,4) is added, the graph then looks like
and the two connected components are {1,2,3,4,5} and {6}. The function should return 2.
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
2 of 4 2018-04-14, 12:57 p.m.
2) Reading a Graph
Implement a function read_city_graph_undirected(filename) that takes the name of a plain text file
as the argument. The file describes a road network. The function should return the graph (an instance
of our Graph() class) corresponding to the undirected version of that graph.
The file format will be in exactly the same format as the Edmonton graph file. That is, there are two
types of lines:
A line of the form V,ID,Lat,Lon describing a vertex.
Here V is the single character 'V', ID is an integer that is the vertex identifier, and both Lat and Lon
are floating point numbers that describe the geographic coordinates the the vertex.
Important: No two lines describing a vertex will have the same ID value. The vertices of the graph
you return should be the ID values of these lines.
A line of the form E,start,end,name describing an edge/street.
Here E is the single character 'E', start and end are the IDs of two vertices connected by the edge,
and name is a nonempty string giving the name of the street.
Important: There may be spaces in name, but no commas. Every vertex ID in an edge will appear
earlier in the file in a vertex description line.
The following is an example of a very simple city with 4 vertices and 3 edges.
V,1,53.430996,-113.491331
V,2,53.434340,-113.490152
V,3,53.414340,-113.470152
V,4,53.435320,-113.480152
E,1,3,St Albert Road
E,2,3,80 Avenue North-west
E,2,1,None
The file describes a directed road network, but you should treat each edge as undirected in this
exercise. Note that the geographic coordinates and street names are not used in this part (the
coordinates will be used in assignment 1).
3) Components in the Edmonton graph
Your last task is to simply count the number of components described in the undirected version of the
Edmonton graph. The file is found with the files for Assignment 1 on eClass. You should print this
number when the script is run via
python3 count_components.py
However, you should not just hard code the integer and print it. Your script first should build the
undirected version of the Edmonton graph using read_city_graph_undirected("edmontonroads-2.0.1.txt")
You must call the function with exactly this file name in your code (the file name should be hard-coded
into your script). Then your script should print the value returned from the count_components
function when it is supplied with this graph.
Why will there be more than one? Because we obtained this data from OpenStreetMap by asking for
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
3 of 4 2018-04-14, 12:57 p.m.
all vertices and edges in a bounding box around Edmonton. This omitted the roads that crossed the
boundary of our box, thus disconnecting some small parts near the border.
Submission status
Feedback
Attempt number This is attempt 1.
Submission status Submitted for grading
Grading status Graded
Due date Monday, 29 January 2018, 11:55 PM
Time remaining Assignment was submitted 3 hours 25 mins early
Last modified Monday, 29 January 2018, 8:29 PM
File submissions
Export to portfolio
count_components.py
Submission comments Comments (0)
Grade 10.00 / 10.00
Graded on Monday, 19 February 2018, 11:55 AM
Graded by Jesse Farebrother
Feedback
comments Not sure why you didn't want to pop from the `vertices` set. It is more efficient,
behind the scenes when you do `for x in something` Python creates an iterator
which will have to iterate over the entire set. If the set is large this could take a while.
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
4 of 4 2018-04-14, 12:57 p.m.