Finding and returning a loopy path in a directed graph

Question

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.

• tb-: 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.
• Qi Qi: @tb, I will look into these. Thanks for your suggestions! Fantastic!

Answer 1

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.