lOMoARc PSD|44557567
EXPERIMENT -6
DATE:
Aim: Use MapReduce to find the shortest path between two people in a social graph
Install the mrjob package to colab
Upload the required data files
Here is the code to find shortest path
from collections import defaultdict
class MapReduceShortestPath:
def init (self, adjacency_list):
self.adjacency_list = adjacency_list
DEAPARTMENT OF COMPUTER SCIENCE
Downloaded ANDJaiprakash
by Konakalla. ENGINEERING POTHULA NANI BABU(PhD)
(konakallajaiprakash@[Link])
lOMoARc PSD|44557567
[Link] = defaultdict(lambda: float('inf'))
self.back_pointers = {}
def map_step(self, node, distance):
for neighbor, edge_weight in self.adjacency_list[node]:
if distance + edge_weight < [Link][neighbor]:
[Link][neighbor] = distance + edge_weight
self.back_pointers[neighbor] = node
yield neighbor, [Link][neighbor]
def reduce_step(self, mapped_nodes):
updated = False
for node, distance in mapped_nodes:
if distance < [Link][node]:
[Link][node] = distance
updated = True
return updated
def shortest_path(self, source, target):
[Link][source] = 0
iteration = 0
while True:
iteration += 1
print(f"Iteration {iteration}")
# Map Step
mapped_nodes = []
for node in self.adjacency_list:
mapped_nodes.extend(self.map_step(node, [Link][node]))
DEAPARTMENT OF COMPUTER SCIENCE
Downloaded ANDJaiprakash
by Konakalla. ENGINEERING POTHULA NANI BABU(PhD)
(konakallajaiprakash@[Link])
# Reduce Step
updated = self.reduce_step(mapped_nodes)
if not updated or [Link][target] == float('inf'):
break
path = []
node = target
while node is not None:
[Link](node)
node = self.back_pointers.get(node)
return path[::-1]
def read_adjacency_list(file_path):
adjacency_list = defaultdict(list)
with open(file_path, 'r') as file:
for line in file:
node1, node2, weight = [Link]()
adjacency_list[node1].append((node2, int(weight)))
adjacency_list[node2].append((node1, int(weight))) # Assuming undirected graph
return adjacency_list
# Example usage:
if name == " main ":
file_path = "/content/sample_data/adjacency_list.txt" # Replace with the path to your adjacency list text
file
adjacency_list = read_adjacency_list(file_path)
map_reduce_sp = MapReduceShortestPath(adjacency_list)
shortest_path = map_reduce_sp.shortest_path('A', 'F')
print("Shortest path:", shortest_path)
DEAPARTMENT OF COMPUTER SCIENCE
Downloaded ANDJaiprakash
by Konakalla. ENGINEERING POTHULA NANI BABU(PhD)
(konakallajaiprakash@[Link])
Here is the input data to the path
AB 5
AC 3
BD7
CD2
DE4
EF 6
Here is the output for the data
DEAPARTMENT OF COMPUTER SCIENCE
Downloaded ANDJaiprakash
by Konakalla. ENGINEERING POTHULA NANI BABU(PhD)
(konakallajaiprakash@[Link])