Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I wrote a function in Scala to find out and return a loopy path in a directed graph.

One of the arguments is a graph presented in an adjacent list, and the other is a start node. It returns a pair including a loopy path by a list of nodes.

I wonder if there are more elegant ways of doing this.

  def GetACycle(start: String, maps: Map[String, List[String]]): (Boolean, List[String]) = {
    def explore(node: String, visits: List[String]): (Boolean, List[String]) = {
      if (visits.contains(node)) (true, (visits.+:(node)).reverse)
      else {
        if (maps(node).isEmpty) (false, List())
        else {
          val id = maps(node).indexWhere(x => explore(x, visits.+:(node))._1)
          if (id.!=(-1))
            explore(maps(node)(id), visits.+:(node))
          else
            (false, List())
        }
      }
    }
    explore(start, List())
  }

I felt I had to use the indexWhere in this situation, but I suppose it would have other ways to do that.

share|improve this question
    
I am not familiar with scala. If the question is about the algorithm, yes there are some interesting ones. Start here: ostermiller.org/find_loop_singly_linked_list.html go there en.wikipedia.org/wiki/Cycle_detection or there: stackoverflow.com/questions/546655/finding-all-cycles-in-graph and continue with any scientific research for cycle detection (+ graphs). The Tortoise and Hare algorithm could be called short and easy while still valid. If this counts for elegant, you may give it a try. –  tb- Dec 10 '12 at 14:33
    
@tb, I will look into these. Thanks for your suggestions! Fantastic! –  Qi Qi Dec 10 '12 at 14:42

1 Answer 1

up vote 1 down vote accepted

You should use an array to check if you have already visited a node and not visits.contains(node), it would give you the answer in constant time instead of linear time.

The overall complexity of your algorithm is exponential. For instance, if you run your algorithm on this graph:

0 -> 1, 2, ..., n
1 -> 2, ..., n
...

where there are n nodes and there are edges from i to j iff i<j then the node i will be explored 2^i times.

Again you can solve this problem using an array (one array for all nodes) to ensure that each node is explored at most one time.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.