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 have written two programs to find out a loopy path in a directed graphs.

The first version is a pure functional recursive solution, but its complexity is exponential. The second version following it achieves a linear complexity, but it doesn't look perfect either.

 def GetACycle(start: String, maps: Map[String, List[String]]): List[String] = {

    def explore(node: String, visits: List[String], steps: Int): List[String] = {
      println(List.fill(steps)("\t").mkString + node)
      if (visits.contains(node)) (visits.+:(node)).reverse
      else {
        if (maps(node).isEmpty) Nil
        else {
          val id = maps(node).indexWhere(x => !explore(x, visits.+:(node), steps + 1).isEmpty)
          if (id.!=(-1))
            explore(maps(node)(id), visits.+:(node), steps + 1)
          else
            Nil
        }
      }
    }

    explore(start, List(), 0)
  }

The second version uses mutable variables, the "visits" and "path", though it achieves a linear complexity in terms of number of visited nodes.

Would it be possible to achieve such a linear complexity in this situation while using a pure functional recursion without any mutable variables?

  def GetACycle2(start: String, maps: Map[String, List[String]]): List[String] = {
val nodes = maps.:\(Set[String]())((item, set) =>
  item._2.:\(set)(((i, set) => set.+(i))).+(item._1))
val pairs = nodes.toList.zip(List.fill(nodes.size)(false))

var visits = pairs.toMap
var path = List[String]()

def explore(node: String, steps: Int): Boolean = {
   println(List.fill(steps)("\t").mkString + node)
  path = path.+:(node)
  if (visits(node)) { visits = visits.updated(node, true); true }
  else {
    visits = visits.updated(node, true)
    if (maps(node).isEmpty) false
    else {
      maps(node).exists( x => explore(x, steps+1))
    }
  }
}

explore(start, 0)
path

}

share|improve this question
    
path = path.+:(node) is very bad. Add values to the front of a list, and reverse it when you are finished. –  Landei Dec 12 '12 at 14:03
    
Landei, you're right about it. –  Qi Qi Dec 12 '12 at 14:40

4 Answers 4

up vote 2 down vote accepted

What about something like this (Please excuse my style/form - As with the other poster, I'm not very familiar with coding in Scala either):

def GetACycle(start: String, maps: Map[String, List[String]]): List[String] = {

//entry function
def explore(node: String): List[String] = {
    explore_r(node, List(), List())
}

//main recursive
def explore_r(node: String, visited: List[String], path: List[String]): List[String] = {
    println(node)
    if (!maps.contains(node)) return Nil
    if (visited.contains(node)) return path++List(node)
    val branches = maps(node)
    for (nextnode <- branches){
        val loop = explore_r(nextnode, visited++List(node), path++List(node))
        if (loop != Nil) return loop
    }
    Nil
}
explore(start)
}
share|improve this answer
    
it works! Thank you, @tandem5. –  Qi Qi Dec 13 '12 at 19:56
    
The key is using the RETURN to jump out of the recursion earlier. –  Qi Qi Dec 13 '12 at 20:44
1  
@Qi Qi Glad I could help! To acknowledge Landei's comment to the original question, my solution should also be edited to prepend elements to the lists. –  tandem5 Dec 14 '12 at 4:18

Here is a solution in OCaml (I don't know Scala).

module M = Map.Make(String)

let rec loopy (graph: string list M.t) (node: string) (path_from_start: string list) (visited: string list M.t) =
  if M.mem node visited then
    (true, visited, path_from_start, M.find node visited)
  else
    let rec explore visited = function
    | [] -> (false, visited, [], [])
    | h :: t ->
      match loopy graph h (h::path_from_start) visited with
      | (true, _, _, _) as ans -> ans
      | (false, visited, _, _) -> explore visited t
    in
    explore (M.add node path_from_start visited) (M.find node graph)

let get_a_cycle (graph: string list M.t) (start: string) =
  match loopy graph start [start] (M.add start [start] M.empty) with
  | false, _, _, _ -> None
  | true, _, l1, l2 -> Some (List.rev_append l1 l2)
share|improve this answer
    
Thanks, Thomash. I will look into this. –  Qi Qi Dec 12 '12 at 14:14

The key is to using "return" keyword. Here is the improved version based on @Thomash and @tandem5 suggestions.

  def GetACycle_perfect(start: String, maps: Map[String, List[String]]): List[String] = {

def explore(node: String, visits: List[String], steps: Int): List[String] = {
  println(List.fill(steps)("\t").mkString + node)
  if (visits.contains(node)) (visits.+:(node)).reverse
  else {
    if (maps(node).isEmpty) Nil
    else {
      maps(node).foreach(v => {
        val loop = explore(v, visits.+:(node), steps + 1) 
        if (!loop.isEmpty) return loop
        })
      Nil
    }
  }
}
explore(start, List(), 0)

}

share|improve this answer

I had a similar problem lately. The thing that bothers me in the above solution is, that the function explore is not tail recursive! This solution works of course for small trees, but if you have a large tree or - as in my case - a generated tree, you would have to come up with a solution with tail recursion. So, I wouldn't say that my solution is "perfect", but I think it would be worth a while (I also added a small main function so that others might test the code). The trick here is to use stacks (for backtracking) and an exception for the result (which might look a bit awkward - but isn't a loop kind of an exception?)

import scala.annotation.tailrec
import scala.collection.mutable.ArrayStack

object CheckCycle {
  def GetACycle(start: String, maps: Map[String, List[String]]): List[String] = {
    // the loop is returned in an exception
    case class ResultException(val loop: List[String]) extends Exception
    val visited = ArrayStack[String]()
    val branchesStack = ArrayStack[Iterator[String]]()

    def explore(node: String): List[String] = {
      try {
        // the "normal" result is Nil
        explore_tr(List(node).iterator)
      }
      catch {
        // the exceptional result is a loop
        case ResultException(loop) => loop
      }
    }

    @tailrec
    def explore_tr(branches: Iterator[String]): List[String] = {
      if (branches.hasNext) {
        val node = branches.next
        if (visited.contains(node)) {
          visited.push(node)
          // we found the loop
          throw new ResultException(visited.toList.reverse)
        }
        else
          maps.get(node) match {
            case None =>
              // go to siblings
              if (branches.hasNext) 
                 explore_tr(branches)
              else {
                  // track back
                  if (!branchesStack.isEmpty) {
                    visited.pop
                    explore_tr(branchesStack.pop)
                  }
                  else Nil // we're done
              }
            case Some(children) =>
              // go deeper
              visited.push(node)
              branchesStack.push(branches)
              explore_tr(children.iterator)
          }
      }
      else Nil
    }

    explore(start)
  }

  def main(args: Array[String]) {
    def maps = Map(
      "1" -> List("2", "3"),
      "2" -> List("4"),
      "3" -> List("4", "5"),
      "4" -> List("6", "1"))
    println(GetACycle("1", maps))
  }
}

Cheers Michael

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.