COMP9313 2018s2 Assignment
Question 1. MapReduce (5 pts)
Problem Background: Given an undirected graph G, its “line graph” is another graph L(G)
that represents the adjacencies between edges of G, such that:
• each vertex of L(G) represents an edge of G; and
• two vertices of L(G) are adjacent if and only if their corresponding edges share a
common endpoint ("are incident") in G.
The following figures show a graph (left) and its line graph (right). Each vertex of the line
graph is shown labelled with the pair of endpoints of the corresponding edge in the original
graph. For instance, the vertex on the right labelled (1,3) corresponds to the edge on the left
between the vertices 1 and 3. Vertex (1,3) is adjacent to three other vertices: (1,2) and (1,4)
(corresponding to edges sharing the endpoint 1 in G) and (3,4) (corresponding to an edge
sharing the endpoint 3 in G).
Problem: Given you the adjacency list of an undirected graph G, use MapReduce to generate
the adjacency list of its line graph L(G). Note that each edge connecting two nodes i and j is
represented by (i, j) in L(G) (if i