Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Document Bfs.stack behavior #634

Open
vporton opened this issue Apr 20, 2024 · 0 comments
Open

Document Bfs.stack behavior #634

vporton opened this issue Apr 20, 2024 · 0 comments

Comments

@vporton
Copy link

vporton commented Apr 20, 2024

Document that Bfs.stack stores node in the order reverse to adding them and does not add the start node to the stack, as revealed during debugging of the following code:

use std::iter::once;

// TODO: Somebody, adopt this code (and DFS) to `petgraph`.
use petgraph::{data::DataMap, visit::{Bfs, IntoNeighbors, VisitMap}};

pub struct BfsFiltered<NodeId, VM> {
    base: Bfs<NodeId, VM>,
    // node_filter: P,
}

impl<NodeId, VM> BfsFiltered<NodeId, VM> {
    pub fn new(base: Bfs<NodeId, VM>) -> Self {
        Self {
            base
        }
    }

    pub fn traverse<G, P, C, NodeWeight>(&mut self, graph: G, mut predicate: P, mut call: C)
    where C: FnMut(&NodeId, &NodeId) -> (),
          G: IntoNeighbors<NodeId = NodeId> + DataMap<NodeWeight = NodeWeight>,
          P: FnMut(&NodeId) -> bool,
          NodeId: Copy + Eq,
          VM: VisitMap<NodeId>,
    {
        if let Some(first_id) = self.base.next(graph) {
            while let Some(source_child_id) = &self.base.next(graph) {
                if (&mut predicate)(source_child_id) {
                    // TODO: Create a `petgraph` issue asking to explain the next line of code workings.
                    let source_parent_id = self.base.stack.iter().map(|e| *e).chain(once(first_id)).find(&mut predicate);
                    if let Some(source_parent_id) = &source_parent_id {
                        (&mut call)(source_parent_id, &source_child_id);
                    }
                }
            }
        }
    }
}

Also document the similar Dfs behavior.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant