Scala - Use DFS for detecting a cycle? My code is buggy, and I can't seem to figure out why

Question

I am trying to write a function that returns true if the graph has a cycle but I am dreadfully struggling. I represent a graph in Scala as shown below, where the index of each sublist represent a node 0,1,2 onwards, and the components of that sublist indicate an edge from index of sublist to node 2 at cost 1 for example. Note this is a undirected graph representation. Below is an example of a undirected graph that does have a cycle.

ListBuffer(
  ListBuffer((1, 1), (2, 1), (3, 1)),
  ListBuffer((0, 1), (2, 2), (3, 2)),
  ListBuffer((0, 1), (1, 2)),
  ListBuffer((0, 1), (1, 2)))
)

Here is the code I have but it does not work, and I cannot seem to figure out why.

def hasCycle(graph: ListBuffer[ListBuffer[(Int, Int)]]): Boolean = {
  var visited: HashSet[Int] = HashSet()
  var lst: ListBuffer[Int] = ListBuffer()
  for (node <- graph.indices) {
    if (visited.contains(node)) {
      true
    } else {
      visited += node
      for (item <- getChildren(graph, node)) {
        visited += item
        lst += item
      }
      for (i <- lst) {
        visit(graph, i, node)
        lst = ListBuffer()
      }
    }
  }
  def visit(g: ListBuffer[ListBuffer[(Int, Int)]], node: Int, parent: Int): Unit = {
    for (child <- getChildren(g, node)) {
      if (visited.contains(child) && (child != parent)) {
          true
      } else if (!visited.contains(child) && (child != parent)) {
        visit(g, child, child)
      }
    }
  }
  false
 }
 /* Return the adjacent nodes to parent in graph */
 def getChildren(graph:  ListBuffer[ListBuffer[(Int, Int)]], parent: Int): ListBuffer[Int] = {
    var parentToChildren: Map[Int, ListBuffer[Int]] = Map()
    var childrenOfI: ListBuffer[Int] = ListBuffer()
    for (i <- graph.indices) {
      for (j <- graph(i)) {
        childrenOfI += j._1
      }
      parentToChildren += (i -> childrenOfI)
      childrenOfI = ListBuffer()
    }
    parentToChildren(parent)
  }

You should add the code in the question (instead of describing it): what have you tried, what doesn't work, what you would like to improve/make more idiomatic. — laughedelic, Nov 09 '16 at 02:56

score 2 · Accepted Answer · edited May 23 '17 at 12:24

2

Here is an approach (admittedly not rigorously tested, so let me know!), sub-optimal but which does contain some Scala idiom (use of find on collection, Set, immutable List...):

type Graph = List[List[(Int, Int)]]

val g: Graph = List(
  List((1, 1), (2, 1)),
  ...
  )

def hasCycle(g: Graph): Boolean = {
  (0 to g.length - 1).find { source => //-- is there a cycle starting at this node?
    pathTo(source, source, (0 to source).toSet)
  }.isDefined
}

def pathTo(source: Int, destination: Int, visited: Set[Int]): Boolean = {
  //-- Is there a path from source to destination excluding visited?
  g(source).find { node => //-- find first case where
    node._1 == destination || ( //-- we've reached destination, or ...
      //-- we're allowed to continue (not yet visited), and there's a path this way
      !visited.contains(node._1) && pathTo(node._1, destination, visited + node._1))
  }.isDefined
}

As an aside, if you haven't seen them, you might also be interested in the answers to How do I check if a Graph is Acyclic

edited May 23 '17 at 12:24

Community

1
1

answered Nov 09 '16 at 05:31

wwkudu

2,778
3
28
41

I do not think it is a correct solution, consider `var j : Graph = ListBuffer(ListBuffer((1,1),(2,1),(3,1)),ListBuffer((0,1)),ListBuffer((0,1)),ListBuffer((0,1)))` This is a graph with no cycles, but the code provided returns true. – Teodorico Levoff Nov 09 '16 at 20:41
Your node 0 has edge to 1 (very first element), then your node 1 has an edge to 0 (ListBuffer((0,1))... have I misunderstood? – wwkudu Nov 10 '16 at 07:59
Yes you understand correctly. I am dealing with undirected graphs. – Teodorico Levoff Nov 10 '16 at 12:51
i'm definitely missing something... i understand your graph look like a flower with node 0 in the middle and 3 petals. there are edges from 0 to each of the petal points 1, 2, 3 and edges back from the petal points to 0. so there are 3 cycles 0-1-0, 0-2-0 and 0-3-0. or not? – wwkudu Nov 10 '16 at 13:00
The edges back from the petal points to 0, are the same edge. You should have a graph with three edges only, and these three edges are from node 0 out to each node 1, 2, 3. Can you see why there exist no cycle in this graph? – Teodorico Levoff Nov 10 '16 at 14:01
ok, i understand what you are getting at. but you are "storing" two edges, when in fact there is only one. I'll have to rework it now that i understand your approach. – wwkudu Nov 10 '16 at 14:41
Would your solution work if I store a `ListBuffer[(Int, Int, Int)]` where the triple is `(x, y, z)` which means there exist an edge from `x` to `y` at cost `z`? – Teodorico Levoff Nov 11 '16 at 01:12
My solution should work if you only store a single edge per node pair, i.e. `List(List((1,1),(2,1),(3,1)),List(),List(),List())` which would be equivalent to say `List(List((1,1),(2,1)),List(),List(),List((0,1)))` where the edge between 0 and 3 is now specified in node 3's list rather than in node 0's list. Does that make sense? Your current (in the question) way of specifying the graphs has redundant information in afaiu, you specify two edges between each node when you only mean a single edge. – wwkudu Nov 11 '16 at 04:14

Scala - Use DFS for detecting a cycle? My code is buggy, and I can't seem to figure out why

1 Answers1