Is there a heuristic way to find the longest simple cycle from a particular node in a directed graph?

So far ,I could only think of a brute force method using networkx. However , for a large dataset , execution takes a very long time. I am aware that this a NP-hard problem so is there a heuristic solution that gives a near optimal solution ?

adj_list refers to a 2d-list of nodes labelled as integers

eg. [[1,2],[3,4],[3],[4],[]]

In the graph , each node is labelled as an integer where nodes are from 0 and above in increasing order

if adj_list is [[1,2],[3,4],[3],[4],[]] , then the nodes present are 0,1,2,3,4,

import networkx as nx


def create_graph(adj_list):
  length = len(adj_list)
  g = nx.DiGraph()

  for node in range(length):
    for towards in adj_list[node]:
      g.add_edge(node, towards)

  return g


def get_longest_cycle(adj_list, s):
  g = create_graph(adj_list)

  cycles = nx.simple_cycles(g)

  # print(cycles)
  largest = 0
  to_return = []
  for c in cycles:
    if s in c:
      if len(c)>largest:
          to_return=list(c)
          largest=len(c)

  

  return to_return

Source: Python Questions

LEAVE A COMMENT