Help about finding cycles in infinite graph.

[nguyenhieuec]

Could you please add an example that implement this statement in the lib document: If a graph contains a path that starts at some vertex and ends at the same vertex, the path is called a cycle.

I have gone through all the document and nearly found a solution but it's not sufficient yet. My special case is I want to find all cycles in graph like networkx simple_cycles method by using this library.

My test implement so far.

next_vertices_1b = nog.adapt_edge_index(data_for_graph, add_inverted=True, attributes=True)

traversal = nog.TraversalDepthFirst(next_labeled_edges=next_vertices_1b).start_from('A', build_paths=True)

  for j in range(20):
      v = next(traversal)
      c = copy.deepcopy(traversal.paths[v])
      c = list(c)
      # if c[0] == c[-1]:
      print(f"Vertex {v} in depth {traversal.depth}, path: {traversal.paths[v]}")

the traversal.paths[v] itself return the path it goes through but not return the cycles. When using list(nog.TraversalDepthFirst(next_labeled_edges=next_vertices_1b).start_from('A', build_paths=True).go_to('A')) I got exhausted vertices.
Thanks in advances.

[leshabirukov]

Do you cite this?

Supported special cases
NoGraphs supports graphs with multiple edges, cycles and self loops:

If a graph contains several edges with the same start and end vertex, these edges are called multiple edges.

As far as I can tell, It says, engine could process graphs with cycles, not find (all?) cycles in graph for you.
The Lib provides fast and efficient graph traversals, it can be helpful for various graph related tasks, but not 'out of the box', it is engine, not a swiss knife.

[HeWeMel]

Dear nguyenhieuec,

NoGraphs supports the following algorithms (see feature overview: DFS, BFS, topological search, Dijkstra, A* and MST. None of these algorithms can directly be used for finding all cycles in a graph.

The topological search of NoGraphs finds a single reachable cycle in a directed graph (can be seen here ) and reports it. But the existence of a reachable cycle violates the precondition of the algorithm, is interpreted as an error, and thus, the algorithm stops after reporting the cycle. So, you get one cycle, but not all the others.

This discussion might help you. Here, the difference between simple cycles, a cycle base and all cycles is explained. This could be helpful for defining your exact goal. And some algorithms are sketched or linked, one is even based on DFS. (From the argument add_inverted=True in your code I guess that you like to find cycles in an undirected graph).

Here you can find information for the case of directed graphs. One of the comments says that simple_cycles of NetworkX implements the Johnson algorithm. And this algorithm is highly recommended by many comments. For small graphs, there is also an easy and short, but slow algorithm given. And there is an explanation, why DFS cannot be easily extended for finding all cycles.

I hope that helps you with your problem.

Regards

[nguyenhieuec]

Thanks for the helpful comment. I will try to implement the Johnson algorithm.
At this moment I'm using another loop to check any last vertices of path can connect back to the start vertices at it works just fine.