Answer to Question #303886 in Python for eranna

Question

Given a directed graph, write a program to print all the strongly connected components of the graph. The runtime of your algorithm should be linear. Input Format: The input is a text file which describes an directed graph. The first line of the file specifies n & m, the number of vertices and number of edges in the graph respectively. The next m lines specify the m edges of the graph, one line per edge. An edge is described by its end points. If the number of vertices is n, assume that the vertices of the graph are numbered (0,1,..n-1). Output Format: Print the list of vertices in each strongly connected component, one line per component. (The order in which the SCCs are printed, and the relative order of the vertices within a given SCC does not matter.) Sample Input (for the graph shown on the right): 11 15 0 1 1 2 2 0 1 3 3 5 5 4 4 3 5 7 7 6 6 7 5 8 7 8 8 9 9 10 10 8 Sample Output : SCC 1: 8, 9, 10 SCC 2: 6, 7 SCC 3: 3, 4, 5 SCC 4: 0, 1, 2

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