Comments (3)
Indeed, it may seem confusing at first sight. But there is nothing wrong with this API (unless I'm mistaken).
The idea is that the meaningful functions are rather iter/fold_component, where the starting point of the DFS is user-provided. I guess this is exactly what you suggest in your third solution.
If you look for instance in Sedgewick&Wayne's Algorithms, you'll see that this is the only function in the DFS API. See https://algs4.cs.princeton.edu/41graph/DepthFirstSearch.java.html
The iter and fold functions are also provided, for your convenience. Indeed they perform as you observed: they run the user-provided iter/fold_vertex functions and, for each vertex not yet visited, start a new DFS from this vertex. Hence the rather cryptic comment saying that iterating over DFS roots only is fine. Said otherwise, it is up to you to come up with an iter_vertex function that will identify suitable DFS roots, e.g. vertices with no predecessors.
My understanding is that you'd like some additional function in the DFS API that would identify vertices with no predecessors for you and run DFS from these vertices. Indeed we could do that, though it would raise some issues such as what to do when you have a strongly-connected component (i.e. with no vertex with no predecessors).
I hope I understood your question correctly.
from ocamlgraph.
You perfectly understood my question and carefully answered it.
I had missed the documentation of fold
in DFS
that could have hinted me in the right direction.
The function is applied each time a node is reached for the first time, before idoterating1 over its successors. Tail-recursive.
I think the main issue, here, is documentation. A few points could be improved:
- The functions in
BFS
could get the same documentation as inDFS
. For instance, the documentation quoted above appears only inDFS
. - The documentation could highlight that the
*_component
versions are probably the ones to be used. - The descriptions of
iter_vertex
andfold_vertex
could explain that the order is important if the user wants to use the non-component versions of the functions.
Thanks for taking the time to answer me!
1The typo is present in the documentation.
from ocamlgraph.
Fixed in commit a2d7918.
from ocamlgraph.
Related Issues (20)
- find_edge Not_found depricated HOT 2
- doc link is broken HOT 1
- META file does not contain the version string
- Exposing viewer/editor executables with public_name dune entry
- building bytecode libraries ? HOT 3
- Tests fail on OCaml 5.00 HOT 3
- mem_vertex and iter_vertex disagreeing on vertex HOT 1
- Test test_components.ml is bound to fail sometimes HOT 1
- Improve the (graphviz) dot parser
- Save graphs as dot files HOT 1
- [question] how to list all cycles in an undirected graph? HOT 2
- opam ocamlgraph version update HOT 2
- HTTP 403 error code HOT 2
- Question : initial size of hash table HOT 3
- Question on the implementation of intersect HOT 1
- Changing the label of a vertex in an imperative graph? HOT 1
- Add the old release tarballs referenced in opam-repository HOT 4
- [Graphviz] xlabel node attribute HOT 2
- [Graphviz.Neato] attribute "Pos" does not implement the "pin" option for a node HOT 3
- Transitive reduction disconnects graph HOT 6
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 ocamlgraph.