4 Replies Latest reply: Aug 16, 2010 4:16 AM by 843853 RSS

    I need an algorithm, HELP!

    843853
      If I input something like this:
      a->b,
      a->c,
      b->d,
      d->a,
      and so on, could be many,

      the the output is this: a->b->d->a, which is a circle from the input.
      I need such a algorithm to help me find out all the circles from the input.
        • 1. Re: I need an algorithm, HELP!
          EJP
          Topological sort.
          • 2. Re: I need an algorithm, HELP!
            843853
            Cross post of [http://forums.sun.com/thread.jspa?threadID=5447698&tstart=0|http://forums.sun.com/thread.jspa?threadID=5447698&tstart=0].

            Please don't post the same question in multiple forums since people may waste their time answering in one forum when a perfectly good response has been posted in another forum. If you feel the need to get a wider exposure of your problem then create a thread that links to the master thread and request responses be made only in the master thread.

            I shall lock this thread.
            • 3. Re: I need an algorithm, HELP!
              EJP
              I had quarantined the other thread, at exactly the same time, and this is the best place for the question, so I'm unlocking.
              • 4. Re: I need an algorithm, HELP!
                843853
                ejp wrote:
                Topological sort.
                I'm not very familiar with topological sort but it seems that it only works on DAGs which won't be the typical input for the OP. At best the t-sorting would give one cycle if it fails, but not all of them.

                @linus_lui: have you googled for something like "graph find all cycles"?