Graph Theory: cycles from specific node

Posted on 2009-05-01
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
    LVL 20

    Expert Comment

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

    Author Comment

    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

    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.

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Free Trending Threat Insights Every Day

    Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

    Suggested Solutions

    Title # Comments Views Activity
    pressure on a wall 10 51
    Two list de-cypher 6 81
    Math Stumper 6 32
    Word Problem 6 37
    Introduction A frequently used term in Object-Oriented design is "SOLID" which is a mnemonic acronym that covers five principles of OO design.  These principles do not stand alone; there is interplay among them.  And they are not laws, merely princ…
    Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
    Migrating to Microsoft Office 365 is becoming increasingly popular for organizations both large and small. If you have made the leap to Microsoft’s cloud platform, you know that you will need to create a corporate email signature for your Office 365…
    In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor ( If you're interested in additional methods for monitoring bandwidt…

    779 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

    Need Help in Real-Time?

    Connect with top rated Experts

    12 Experts available now in Live!

    Get 1:1 Help Now