Answer to Question #305741 in Python for eranna

Question

Write a program to compute the number of distinct shortest paths between two given vertices in an undirected graph with unit edge lengths. Your algorithm should run in linear time. Input Format: The input is a text file which describes the undirected graph G. The first line of the file specifies n, m, u and v, the number of vertices, the number of edges, and the two given vertices respectively. The next m lines specify the m edges of the graph, one line per edge. An edge is described by its end points (no edge weights are described since all the edges have unit length). If the number of vertices is n, assume that the vertices of the graph are numbered (0,1,..n-1). Output Format: Print the number of distinct shortest paths between vertices u and v. Sample Input (for the graph shown on the right): 6 10 5 0 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5 Sample Output : 4

Answer 1

import networkx as nx
import math
	
def strongRelation(n, m):
  G = nx.Graph()
  p = math.ceil(m / n)
  edges_m = []
  for j in range(p):
    for i in range(n):
      if m > 0:
        if i + j >= n - 1:
          edges_m.append((i, i + j + 1 - n))
        else:
          edges_m.append((i, i + j + 1))
        m = m - 1
    G.add_edges_from(edges_m)
  cliques = nx.find_cliques(G)
  cliques1 = [clq for clq in cliques]

  return max([len(i) for i in cliques1])

strongRelation(5, 10) #example