Comments (1)
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
from clrs.
Related Issues (15)
- Is the paper still available? HOT 3
- Hint `A_t` in SCC HOT 2
- Why no directed graph for FloydWarshall, Dijkstra, BFS and BellmanFord HOT 2
- Issue with distribution of undirected graphs HOT 2
- Repetition of indexes in pred
- Update of PyPI version
- Why the outputs of bfs and dfs algorithms are the same HOT 2
- Tarjan's strongly connected components algorithm
- Sampling bug on undirected weighted graphs HOT 2
- More input signals for evaluation HOT 9
- Bug in KMP implementation HOT 3
- tensorflow-macos and tensorflow-metal
- Inability to reproduce paper results HOT 5
- Problems with jax HOT 9
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from clrs.