Why the outputs of bfs and dfs algorithms are the same about clrs HOT 2 CLOSED

Great response, thanks. Looking at https://github.com/google-deepmind/clrs/blob/master/clrs/_src/algorithms/graphs_test.py, test_dfs() and test_bfs() actually produce different outputs for the DIRECTED graph.

from clrs.

Hi Daniel,

Thank you for raising this issue!
Let me try to address your points in turn:

How can I evaluate my DL model to conduct BFS or DFS algorithms if both algorithms provide the same output in probes?

You've picked a particular example where BFS and DFS will retrieve the same output value. But actually, for the particular case of BFS and DFS, in most input cases the two algorithms will yield different output values -- this is due to the fact the former explores nodes in a parallel manner, whereas the latter explores them in a sequential / recursive manner. So as long as you train / evaluate across a large enough number of samples, you will tend to observe very different behaviours when learning BFS vs. DFS.

Is it a mistake in how these algorithms are implemented in the CLRS benchmark or I miss something?

No, the algorithms were deliberately implemented in this way.

To clarify on why only the predecessor pointers are the outputs of BFS and DFS and nothing else, our benchmark is guided by the representations utilised in the CLRS textbook (3rd edition) wherever possible (+ parallelisation improvements to hints where simple to do, and tiebreaking to avoid ambiguous outputs). And as can be seen for both BFS (Figure 22.3 in the book) and DFS (Figure 22.4 in the book), the final output of the algorithm is a collection of predecessor pointers for every node.

What if I want to train a DL model without hints?

Then, on those particular examples, your model will receive the same supervision signal. But, as already explained above, for BFS and DFS, this difference is not so important in a distributional sense. There are far more grave offenders, for example, we have four sorting algorithms which always yield exactly the same input/output pairs :)

However, the way in which you propose to "fix" this problem is, if I understand it correctly, to take auxiliary information (order of visiting of nodes), which is already implicitly encoded e.g. in the 'u' hint of DFS and create an output version of it. I would argue that when you do things this way, at least from the perspective of what is "input" and "output" in the textbook, you are effectively learning with a hint. :)

In conclusion: based on my understanding of your issue, the framework is working exactly as we intended it to. It is true that different variants of the algorithms and specs can be constructed such that more auxiliary information is preserved in the outputs, and this might help disambiguate some of the algorithms. We did not want to do this in our reference implementation, because it would arguably deviate from what's inside the textbook.

But there's nothing in CLRS-30 that stops you from doing this modification: in fact, the library is designed to be extensible with new algorithms or algorithm variants.

To give just a few recent examples from published work that relate to DFS:

• Hint-ReLIC (ICML'23; https://proceedings.mlr.press/v202/bevilacqua23a.html) reverses all the node pointers in DFS to enable perfect generalisation on the default CLRS test distribution.
• RAR (LoG'23; https://arxiv.org/abs/2307.00337) makes a very different variant of DFS' hint structure, which enables explicitly-recursive models to perform better.

How about adding better documentation for bfs/dfs algorithms to explain what the output is.

I agree that adding more docs would help the code's readability. This is something we hope to get around to but we're reasonably constrained by time: already the main framework (with all of its internal automations) took several years to build, and we need to balance any maintenance work on CLRS-30 with our other daily commitments.

We of course welcome pull requests of this kind; if you (or anyone else) are keen to contribute by writing some documentation for the algorithms' outputs, this would of course be much appreciated!

Thanks,
Petar

from clrs.