Instructions
Objective
Write a python homework to create a function number of shortest paths.
Requirements and Specifications
This problem you will implement the first part of the Girvan Newman Algorithm. That is, given a source vertex, source, determine, for each vertex v the number of shortest paths starting at the source that pass-through v. You may not use any imports besides the queue module for this problem. Define a function called number_of_shortest_ paths that will take as input a vertex label called source and a graph G. The function will return a dictionary whose keys are the vertices in G and the values will be the number of shortest paths in G that begin at the source and pass through those vertices. You may want to consider the following strategy. The idea is to modify the code for the breadth-first search so that when a vertex is discovered you will store its level in the BFS presentation that begins at the source as part of its value in G. The other part of the value will be the vertices with a level one lower than itself that are adjacent to it. To begin you can assign the source a level of 0. Generally, if a vertex is discovered by a vertex with level m it will have level m + 1. For a vertex at level m + 1 you will also need to store 1 the vertices at level m that are adjacent to it. Using this information, you can calculate the number of shortest paths by starting at the highest level and working backwards. A vertex that does not discover any new vertices has only one shortest path passing through it. This information can be sent back level by level to determine the number of shortest paths for each vertex. Note that the source should have a value which is equal to the total number of vertices in the graph. Here we consider the path with just one vertex to be the shortest path from the source to itself.
Source Code
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import queue
def number_of_shortest_paths(source, G):
'''1. Maintain two dictionaries. One that stores the level of each vertex
and another that stores, for each vertex, the vertices one level lower that connects to it.
2. Maintain a list of the vertices that do not discover any new vertices.
3. Maintain a queue as in the BFS algorithm.
4. Loop while the queue is not empty as in the BFS. Gather the necessary data
for the collections in parts 1 and 2
5. Create a dictionary to store the number of shortest paths for each vertex.
Give each end vertex a value of 1.
6. Get a collection of all vertices and sort it based on level. The vertices
with the highest level should come first. So the source should be in this list.
7. Loop through the sorted collection. For each vertex add one to the value for
each vertex that connected to it from one level lower. You will have to make sure that
keys are in the dictionary when adding one to their value.
8. Return the dictionary from part 5.'''
levels = {source : 0}
queue = [source]
visited = [source]
result = {}
max_level = 0
while len(queue) > 0:
curr = queue.pop(0)
max_level = max(max_level, levels[curr])
for next in G[curr]:
if next not in visited:
visited.append(next)
queue.append(next)
levels[next] = levels[curr] + 1
for i in range(max_level + 1):
for v in levels:
if levels[v] == i:
if i == 0:
result[v] = 0
else:
counter = 0
for w in levels:
if levels[w] == i-1 and v in G[w]:
counter += 1
result[v] = counter
return result
if __name__ == '__main__':
G = {0 : {1 : 1, 2 : 1}, 1 : {2 : 1, 3 : 1}, 2 : {3 : 1}, 3 : {0 : 1, 4 : 1}, 4 : {0 : 1}}
print(number_of_shortest_paths(0, G))