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

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


}

• 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
• I just posted a more FP immutable answer on a related StackOverflow thread: stackoverflow.com/a/36144158/501113 – chaotic3quilibrium Mar 22 '16 at 0:41

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

• The key is using the RETURN to jump out of the recursion earlier. – Qi Qi Dec 13 '12 at 20:44
• @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)


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)


}

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