What does DFS output result mean ?

[hwchen1]

from clrs._src.algorithms import graphs
import networkx as nx

DIRECTED = np.array(
    [
        [0, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 1, 0],
        [0, 0, 0, 0, 1, 1],
        [0, 1, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 1],
    ]
)
out, _ = graphs.dfs(DIRECTED)
print(out)  # [0 0 2 4 1 2]

What does the result of executing the code output mean? If there are multiple results in DFS, how to judge whether it is right or wrong?

[PetarV-]

Hi, thanks for your issue!

The results (the array [0 0 2 4 1 2] in this case), completely specify the DFS tree.

Specifically, the DFS algorithm traverses the graph in a specific way, and whenever it explores a new node from a neighbour, that neighbour becomes the "parent" of the node in the DFS tree. The array you referenced contains all the parents.

So the tree (more specifically, forest in this case) looks something like:

2 <- 5
0 <- 1 <- 4 <- 3

And the predecessors are represented in the array you see. Note that, by convention, we make the roots (0 and 2) predecessors of themselves.

Your second question (on judging right vs. wrong) can be interpreted in two ways; let me try to answer both of them:

• If you meant "what if there are many possible DFS trees?", CLRS-30 automatically does tie-breaking (in all algorithms) by preferring nodes with a smaller index. Hence, there will always be exactly one "true" result for the variant of DFS we're learning here.
• If you meant "how to judge if an entire answer is right if only some predecessors are properly predicted" -- you can decide yourself how to evaluate correctness of the model outputs! In the "standard" CLRS-30 approach, we separately treat each node predecessor prediction as one classification problem, and report the overall accuracy across all nodes. The more "correct" approach is to check if the entire array is exactly the same, but this one has significantly more discontinuities, so it is harder to track the model's improvements when iterating.

I hope this is helpful! Please let me know if there are any other questions you might have.

Thanks, Petar