[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now


Graph Theory: cycles from specific node

Posted on 2009-05-01
Medium Priority
Last Modified: 2012-05-06
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?
Question by:nitramke
  • 2
LVL 20

Expert Comment

ID: 24285146
What do you mean with "no repeated paths"?
You don't want to count ABCDABNCDA?
What about ABCADEFA?

Author Comment

ID: 24285776
Sorry, I mean that ABCDA is fine, but not ABCDABA.
the reverse direction is also acceptable: ABCDA and ADCBA are both fine
LVL 20

Accepted Solution

thehagman earned 375 total points
ID: 24287452
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.

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Software development teams often use in-memory caches to improve performance. They want to speed up access to, or reduce load on, a backing store (database, file system, etc.) by keeping some or all of the data in memory.   You should implement a…
Introduction This question got me thinking... (http://www.experts-exchange.com/questions/28707487/GLOBALS.html) Why shouldn't we use Globals? This is a simple question without a simple answer.  How do you explain these concepts to a programmer w…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Suggested Courses

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question