Graph Theory: cycles from specific node

If i have a directed graph, with various numbers of nodes and connections, how can I calculate the number of cycles originating from a specific node, of any length, with no repeated paths?
nitramkeAsked:
Who is Participating?
 
thehagmanCommented:
Okay, but what about ABCDECFGA ?
I guess that one is disallowed, too.
Hence you want the cycles without repeated *nodes*, aka. simple cycles.

If there are not too many nodes, one can use methods of dynamic programming:
For a subset S (containing A)  of the node set and a node B in S, let  n(S,B) be the number of paths startinng in A, ending in B and visiting exactly the nodes in S exactly once.
The total number of simple cycles starting at A is the sum of all n(S,B) where S rund over all subsets and B over all elemens of S having an edge B->A.
n(S,B) can be computed as sum of all n(S\{B},C) where C runs over all elements in S\{B} having an edge C->B.
0
 
thehagmanCommented:
What do you mean with "no repeated paths"?
You don't want to count ABCDABNCDA?
What about ABCADEFA?
0
 
nitramkeAuthor Commented:
Sorry, I mean that ABCDA is fine, but not ABCDABA.
the reverse direction is also acceptable: ABCDA and ADCBA are both fine
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.