DFS depends on the order source nodes are added -- LEMON 1.3-1

[Robert Lieck]

The nodes that are reached by DFS are wrong and depend on the order source nodes are added. The attached code implements a simple graph n0-->n3, n1-->n2 and adds n0 and n1 to the source nodes of DFS. Depending on the order either n2 or n3 is not reached.

---

output

---

add node 1 add node 0 node 3: reached node 2: NOT reached node 1: reached node 0: reached

add node 0 add node 1 node 3: NOT reached node 2: reached node 1: reached node 0: reached

[Robert Lieck]

source code

[Alpar Juttner]

This is actually the expected behavior. Using Dfs, it is not allowed to add more than one sources at once. The doc also states this --- though I admit that it might not be obvious to all readers what "The stack must be empty" means.

The good news is, that compiling your code with LEMON_ENABLE_DEBUG turned on, you will get an exception when the second source is added. In recent versions of LEMON, this extra check is turned on by default in Debug and Maintainer build types.

But its easy to fix your code. Simply call start() immediately after each addSource():

  //...
  lemon::Dfs<graph_t> search(graph);
  search.init();
  for(Node node : list) {
    cout << "add node " << graph.id(node) << endl;
    search.addSource(node);
    search.start();
  }
  //...

[Robert Lieck]

I see, thanks for the explanation. To me the meaning of "The stack must be empty" was indeed not clear. And it's also good to know that calling start() multiple times is OK. I thought about resorting to temporally adding a virtual common ancestor of all source nodes to be used as root. But I guess your suggestion is more efficient -- and works for static graphs, too.