How to break this curse by a pure functional recursive function?

Question

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

}

Answer 1

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)
}

Answer 2

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)

Answer 3

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)

}

Answer 4

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