Cycles

cycle detection ( generic )

the general way to do is use a visited enum with 3 states.

• 0 : new
• 1 : exploring
• 2 : explored

visited[...all nodes] = new
 
def dfs(u):
    visited[u] = exploring
    for v in neighbors(u):
        visited(v) is:
            exploring => CYCLE
            new => dfs to this
            explored => skip
    mark explored

(cycle start, cycle end) would be the (v, u) tuple when in CYCLE branch. idea being, we have v as exploring (in the dfs stack) and now see another edge that can lead us there.

just rem that start is obv from what was explored already ⇒ v

now to get the cycle path; two ways

• you can obv make a “parent” array, go from end to start and reverse
• OR and the cleaner way is to keep storing the current node stack ( just like backtracking in a vec )

if found cycle:
    cycle = nodes[ find cycle start... ]

you don’t even need to reverse this way

simplification when undirected

you can get down to just new and exploring states while maintaining a “prev” var.

idea being when I’m exploring neighbors

if visited(neighbor) and neighbor != parent:
    then cycle is path from neighbor to current + this edge from cur to neighbor (to close the loop)

the simplification depends on whether the node being already visited implies that a back edge exists. it may or may not depending on if the node is STILL in the dfs stack

all cycles?

• directed: johnson’s algo ( uses SCCs ), skipping for now
• undirected: nothing polynomial time really, you do an all cycle dfs basically

a counting all cycles optimisation

using a dp you can get a better upper bound of exponential compared to $n!$ of dfs

we solve for EACH start := s so this below is all in another loop

note that dp is on number of paths not cycles

base:
f(1<<s,s) = 1

transition
for cnt = f(mask,u)
    for v:= neigh(u) and not in mask:
        f(mask | v, v) += cnt

to actually get cycles:

for mask,u:
    if |mask| >= 3 and edge(u -> s):
        ans += f(mask,u)

now to avoid duplicates, when you count you would want to force this invariant: “s is the smallest in mask”

for undirected graphs even after ^ you would have fwd and reverse cycles from same s