Enhance traversal docs #1375
Enhance traversal docs #1375
Conversation
|
|
|
|
|
Thanks for submitting this! I will try to review it when I can, but again this is a welcome contribution. |
Pull Request Test Coverage Report for Build 13229065253Details
💛 - Coveralls |
rustworkx/__init__.py
Outdated
| end while | ||
|
|
||
| If an exception is raised inside the callback function, the graph traversal | ||
| def BFSIterator(G, I, F): |
There was a problem hiding this comment.
For Python I think it makes more sense to talk about BFS than BFSIterator. I'd rewrite it to keep the old signature BFS(G, s)
rustworkx/__init__.py
Outdated
| @@ -1565,38 +1633,68 @@ def tree_edge(self, edge): | |||
|
|
|||
| @_rustworkx_dispatch | |||
| def dfs_search(graph, source, visitor): | |||
| """Depth-first traversal of a directed/undirected graph. | |||
| """Iterative depth-first traversal of a directed/undirected graph. | |||
There was a problem hiding this comment.
We could have a recursive DFS with something like https://crates.io/crates/recursive these days, so I am not opposed to saying this.
With that in mind, DFS order is implementation dependent and even the order we iterate edges is not promised to be stable so it is what it is.
There was a problem hiding this comment.
I copied the Iterative prefix from the rustworkx-core since it made sense to me to differentiate this method from the DFS algorithm which has a single source vertex.
I didn't know about DFS (the CLRS ref you sent me was helpful!) but my friends who do know (both the algo and of CLRS) were confused a bit by how several source vertices are incorporated.
If the implementation detail of how several source vertices are incorporated into DFS is not guaranteed, the docs should probably mention that as well.
There was a problem hiding this comment.
I will double check Georgios’ implementation in the source code and check.
I myself forgot the specifics, either the user passes it as an input or we pick an arbitrary node I think
There was a problem hiding this comment.
I thought that the source vertices are added to the stack in reverse order. I know that it is not implemented like that, but it is close to it.
That way when you pop from the stack you start with the first source node as the user specified, etc...
This behavior is similar in the BFS (just with a stack instead of a queue).
This is one the behaviors that I wanted to clarify in the docs.
How about I rewrite the pseudocode like that? That way its clear how the many source nodes relate to the single source node in the DFS algo.
PS if the user does not specify the source the docs already specify the behavior:
If this is not specified then a source will be chosen arbitrarily and repeated until all components of the graph are searched.
There was a problem hiding this comment.
I think if you rewrite the pseudo code to be similar to the implementation, users will like it. Go for it
There was a problem hiding this comment.
I'll try to get to it tomorrow.
rustworkx/__init__.py
Outdated
| color[u] := BLACK finish vertex u | ||
|
|
||
| If an exception is raised inside the callback function, the graph traversal | ||
| def DFSIterator(G, I, F): |
There was a problem hiding this comment.
Same comment from BFS
rustworkx/__init__.py
Outdated
| color[s] = GRAY | ||
| time += 1 | ||
| F.Discover(s, time) | ||
| Q = [s] # LIFO vertex queue |
There was a problem hiding this comment.
You can call it a stack
|
I reverted to the pseudo-code styling of the algorithms. I couldn't simplify the algorithms while staying similar to the implementation, so I thought going with pseudo-code conveys better that this does not follow the implementation. I also redid the Dijkstra search as it was similarly unclear (to me). I fixed a minor type annotation issue in the universal I checked that that |
There was a problem hiding this comment.
Thanks for the documentation improvements!
I will merge #1380 with this and then lets check the docs. I revised but there are multiple repetitions of the same docstring (unfortunately, that is how the docs work). So let's see the end result in the website and judge. I have a feeling it will be better
This PR fixes #1361.
It add some elaboration to the traversal BFS and DFS functions, mainly with a more concrete pseudo-code.
I also fixed small doc errors in betweenness function's docstrings.
In the issue I also suggested doing a face-lift to the dijkstra_search. I can add this in to this PR in the style of the other docstrings changes I'm proposing If you'd like.
nox -e docsandcargo docto see that the result is good.