COIN-OR::LEMON - Graph Library

Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#596 closed defect (invalid)

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

Reported by: Robert Lieck Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.4 release
Component: core Version: release branch 1.3
Keywords: DFS Cc:
Revision id:

Description

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

Attachments (1)

main.cpp (1.2 KB) - added by Robert Lieck 5 years ago.
source code

Download all attachments as: .zip

Change History (3)

Changed 5 years ago by Robert Lieck

Attachment: main.cpp added

source code

comment:1 Changed 5 years ago by Alpar Juttner

Resolution: invalid
Status: newclosed

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();
  }
  //...

comment:2 Changed 5 years ago by 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.

Note: See TracTickets for help on using tickets.