Ask Your Question
2

Find all cycles in an undirected graph

asked 1 year ago

licheng gravatar image

updated 1 year ago

For directed graphs, we have a built-in command all_simple_cycles to search for specific length cycles or all cycles. However, it is indeed strange that there is no readily available command for undirected graphs. Although, we can convert an undirected graph into a directed graph by assigning two directions to each edge. For example:

g = graphs.CompleteGraph(4).to_directed();
all_cycles=g.all_simple_cycles()
print(all_cycles)

[[0, 1, 0], [0, 2, 0], [0, 3, 0], [1, 2, 1], [1, 3, 1], [2, 3, 2], [0, 1, 2, 0], [0, 1, 3, 0], [0, 2, 1, 0], [0, 2, 3, 0], [0, 3, 1, 0], [0, 3, 2, 0], [1, 2, 3, 1], [1, 3, 2, 1]]

allcycles = []
for array in all_dcycles:
    if len(array)>=4:
       reversed_array = array[::-1] 
       if reversed_array not in allcycles:
          allcycles.append(array)
print(allcycles)

[[0, 2, 1, 0], [0, 3, 1, 0], [0, 3, 2, 0], [1, 3, 2, 1], [0, 3, 2, 1, 0], [0, 2, 3, 1, 0], [0, 3, 1, 2, 0]]

Reversing lists and eliminating all 2-cycles seems tedious. Does SageMath provide a direct command for undirected graphs to find all cycles or cycles of a specific length? It's somewhat similar to Mathematica's FindCycle (FindCycle[CompleteGraph[4], Infinity, All]).

Preview: (hide)

2 Answers

Sort by » oldest newest most voted
2

answered 1 year ago

Max Alekseyev gravatar image

updated 1 year ago

There is no need to reverse and eliminate cycles - instead, to fix a cycle direction it's enough to compare the second vertex with the second but last vertex:

g = graphs.CompleteGraph(4)
undirected_cycles = [ c for c in g.to_directed().all_simple_cycles() if len(c)>=4 and c[1]<c[-2] ]

Alternatively, all simple cycles can be constructed from .cycle_basis():

def gen_simple_cycles(G):
    C = [frozenset(tuple(sorted(e[:2])) for e in c) for c in G.cycle_basis(output='edge')]
    for S in Subsets(C):
        T = set()
        for c in S:
            T = T.symmetric_difference(c)
        H = Graph(T, format='list_of_edges')
        if H.is_eulerian() and max(H.degree(),default=0)==2:
            yield H.eulerian_circuit(return_vertices=True)[1]

list( gen_simple_cycles( graphs.CompleteGraph(4) ) )
Preview: (hide)
link
1

answered 0 years ago

licheng gravatar image

The following is an alternative solution (using networkx).

import networkx as nx
G=graphs.PetersenGraph()
NG = G.networkx_graph()
sorted(nx.simple_cycles(NG))
Preview: (hide)
link

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 1 year ago

Seen: 691 times

Last updated: Jan 12