MITB B..88 – ISSS606
Social Analytics and Applications
Assignment 1
[QQuestion 1 ] Shortest – Path and Minimum Spanning Tree
Fort canning park is just beside SMU,, and it is where many SMU students jog to destress . In this question,, you are provided with a data file that describes the graph as shown on the right (eedge weights are ignored in the figure)).. The first line describes the number of vertices n um – v ert and the number of edges n um – e dge . Each of the next num – vert lines contains two decimals,, which are the latitude and longitude of each vertex.. This is then followed by num – edge lines on edge weights;; each line contains a pair of vertex indices and the distance in meters between the two vertices,, as the weight of the edge.. You are given a Python code to read the data file and generate a figure like the one on the right.. Each of y ou will be assigned with a vertex v to start with,, please
(11)) find the shortest paths from v to all other vertices;; and
(22)) construct a minimum spanning tree rooted at v
Your output (nname it ‘ Q 1 .ooutput ‘ ) should be in the following format::
The first line describes the distances from v to any vertex including v , separated by tab ‘ \ t”,, in the sequence of vertex indices.. The distances should be all integers..
The second line is a p o st – order traversal of the minimum spanning tree rooted at v . Child with smaller index should appear fi rst.. Vertices are separated by tab ‘ \ t”..
No other information should be included,, just the two lines mentioned above..
[QQuestion 2 ] Best Restaurant in a neighborhood
In this exercise,, you are employed by a F&&BB company to investigate existing restaurants in a neighborhood.. With the web crawling skills that you have learnt in class , you are to answer the following questions from the F&&BB company with data from foursquare..ccom .
(11)) What are the 5 most commented restaurants in the area??
(22)) What are the 5 best restaura nts in the area,, by looking at the overall ratings??
(33)) What are the 5 best rest aurants in the area,, by judging from the comments??
E ach of you are given a different neighborhood to work with,, which is a circle centered at one MRT station with radius 4 00 meters ( If you feel there are t oo fe w rest aurants , you may increase this limit to 800 meters ) . You need to submit both codes and results (tthe set of restaurants you crawled,, and t he set of comments you crawled))..