patternMinor
Simple algorithm for listing all 6-cycles in a directed graph
Viewed 0 times
simplegraphalldirectedlistingalgorithmforcycles
Problem
What's an easy-to-program way of listing all 6-cycles in a directed graph? I've done some reading on the general case of even cycles, but it's rather complicated. I found a really neat approach for 4-cycles, in this post, and I was wondering if there's something similar for 6-cycles.
My graph isn't that big (maybe a few hundred nodes) so I'm not too worried about computation time.
My graph isn't that big (maybe a few hundred nodes) so I'm not too worried about computation time.
Solution
The easiest-to-program method will probably be a straightforward for-loop. In particular, for each combination of six vertices $v_1,v_2,\dots,v_6 \in V$, check whether the following conditions all hold:
If all the conditions hold, then you've found a cycle. Output it. Repeat for each possible combination of vertices.
The running time of this method is $\Theta(|V|^6)$. It is easy to see that in the worst case there can be $\Theta(|V|^6)$ different cycles (consider a complete graph), so any algorithm will have to take at least this long on some graphs.
You can also get a very easy-to-program algorithm with running time $\Theta(|E|^3)$. Enumerate all triples of edges $(v_1,v_2), (v_3,v_4), (v_5,v_6) \in E$, and then check the following conditions:
If all the conditions hold, you've found a cycle; output it
This algorithm has $\Theta(|E|^3)$ running time. Again, it's easy to see that there exist graphs where there are $\Theta(|E|^3)$ cycles and thus any algorithm will need to take at least $\Theta(|E|^3)$ time.
Both of those algorithms are easy to program. That doesn't mean they are necessarily optimal in running time. One could hope for an output-sensitive algorithm whose running time is a function of the number of 6-cycles as well as of $|V|,|E|$. I suspect there are more complex algorithms that might have better asymptotic running time, for some graphs, when considering all three of those parameters. However, they will be much more complex to program. Therefore, by your stated goal of "easiest-to-program", I recommend one of the two algorithms listed above.
- the $v_1,v_2,\dots,v_6$ are all distinct
- $(v_1,v_2) \in E$ and $(v_2,v_3) \in E$ and ... and $(v_5,v_6) \in E$ and $(v_6,v_1) \in E$.
If all the conditions hold, then you've found a cycle. Output it. Repeat for each possible combination of vertices.
The running time of this method is $\Theta(|V|^6)$. It is easy to see that in the worst case there can be $\Theta(|V|^6)$ different cycles (consider a complete graph), so any algorithm will have to take at least this long on some graphs.
You can also get a very easy-to-program algorithm with running time $\Theta(|E|^3)$. Enumerate all triples of edges $(v_1,v_2), (v_3,v_4), (v_5,v_6) \in E$, and then check the following conditions:
- the $v_1,v_2,\dots,v_6$ are all distinct
- $(v_2,v_3) \in E$ and $(v_4,v_5) \in E$ and $(v_6,v_1) \in E$.
If all the conditions hold, you've found a cycle; output it
This algorithm has $\Theta(|E|^3)$ running time. Again, it's easy to see that there exist graphs where there are $\Theta(|E|^3)$ cycles and thus any algorithm will need to take at least $\Theta(|E|^3)$ time.
Both of those algorithms are easy to program. That doesn't mean they are necessarily optimal in running time. One could hope for an output-sensitive algorithm whose running time is a function of the number of 6-cycles as well as of $|V|,|E|$. I suspect there are more complex algorithms that might have better asymptotic running time, for some graphs, when considering all three of those parameters. However, they will be much more complex to program. Therefore, by your stated goal of "easiest-to-program", I recommend one of the two algorithms listed above.
Context
StackExchange Computer Science Q#45176, answer score: 2
Revisions (0)
No revisions yet.