/rust/registry/src/index.crates.io-1949cf8c6b5b557f/petgraph-0.8.3/src/visit/mod.rs

Source
//! Graph traits and graph traversals.
//!
//! ### The `Into-` Traits
//!
//! Graph traits like [`IntoNeighbors`][in] create iterators and use the same
//! pattern that `IntoIterator` does: the trait takes a reference to a graph,
//! and produces an iterator. These traits are quite composable, but with the
//! limitation that they only use shared references to graphs.
//!
//! ### Graph Traversal
//!
//! [`Dfs`](struct.Dfs.html), [`Bfs`][bfs], [`DfsPostOrder`][dfspo] and
//! [`Topo`][topo]  are basic visitors and they use “walker” methods: the
//! visitors don't hold the graph as borrowed during traversal, only for the
//! `.next()` call on the walker. They can be converted to iterators
//! through the [`Walker`][w] trait.
//!
//! There is also the callback based traversal [`depth_first_search`][dfs].
//!
//! [bfs]: struct.Bfs.html
//! [dfspo]: struct.DfsPostOrder.html
//! [topo]: struct.Topo.html
//! [dfs]: fn.depth_first_search.html
//! [w]: trait.Walker.html
//!
//! ### Other Graph Traits
//!
//! The traits are rather loosely coupled at the moment (which is intentional,
//! but will develop a bit), and there are traits missing that could be added.
//!
//! Not much is needed to be able to use the visitors on a graph. A graph
//! needs to define [`GraphBase`][gb], [`IntoNeighbors`][in] and
//! [`Visitable`][vis] as a minimum.
//!
//! [gb]: trait.GraphBase.html
//! [in]: trait.IntoNeighbors.html
//! [vis]: trait.Visitable.html
//!
//! ### Graph Trait Implementations
//!
//! The following table lists the traits that are implemented for each graph type:
//!
//! |                       | Graph | StableGraph | GraphMap | MatrixGraph | Csr   | List  |
//! | --------------------- | :---: | :---------: | :------: | :---------: | :---: | :---: |
//! | GraphBase             | x     |  x          |    x     | x           | x     |  x    |
//! | GraphProp             | x     |  x          |    x     | x           | x     |  x    |
//! | NodeCount             | x     |  x          |    x     | x           | x     |  x    |
//! | NodeIndexable         | x     |  x          |    x     | x           | x     |  x    |
//! | NodeCompactIndexable  | x     |             |    x     |             | x     |  x    |
//! | EdgeCount             | x     |  x          |    x     | x           | x     |  x    |
//! | EdgeIndexable         | x     |  x          |    x     |             |       |       |
//! | Data                  | x     |  x          |    x     | x           | x     |  x    |
//! | IntoNodeIdentifiers   | x     |  x          |    x     | x           | x     |  x    |
//! | IntoNodeReferences    | x     |  x          |    x     | x           | x     |  x    |
//! | IntoEdgeReferences    | x     |  x          |    x     | x           | x     |  x    |
//! | IntoNeighbors         | x     |  x          |    x     | x           | x     |  x    |
//! | IntoNeighborsDirected | x     |  x          |    x     | x           |       |       |
//! | IntoEdges             | x     |  x          |    x     | x           | x     |  x    |
//! | IntoEdgesDirected     | x     |  x          |    x     | x           |       |       |
//! | Visitable             | x     |  x          |    x     | x           | x     |  x    |
//! | GetAdjacencyMatrix    | x     |  x          |    x     | x           | x     |  x    |

// filter, reversed have their `mod` lines at the end,
// so that they can use the trait template macros
pub use self::filter::*;
pub use self::reversed::*;
pub use self::undirected_adaptor::*;

#[macro_use]
mod macros;

mod dfsvisit;
mod traversal;
pub use self::dfsvisit::*;
pub use self::traversal::*;

use core::hash::{BuildHasher, Hash};

use fixedbitset::FixedBitSet;
use hashbrown::HashSet;

use super::EdgeType;
use crate::prelude::Direction;

use crate::graph::IndexType;

trait_template! {
/// Base graph trait: defines the associated node identifier and
/// edge identifier types.
pub trait GraphBase {
    // FIXME: We can drop this escape/nodelegate stuff in Rust 1.18
    @escape [type NodeId]
    @escape [type EdgeId]
    @section nodelegate
    /// edge identifier
    type EdgeId: Copy + PartialEq;
    /// node identifier
    type NodeId: Copy + PartialEq;
}
}

GraphBase! {delegate_impl []}
GraphBase! {delegate_impl [['a, G], G, &'a mut G, deref]}

/// A copyable reference to a graph.
pub trait GraphRef: Copy + GraphBase {}

impl<G> GraphRef for &G where G: GraphBase {}

trait_template! {
/// Access to the neighbors of each node
///
/// The neighbors are, depending on the graph’s edge type:
///
/// - `Directed`: All targets of edges from `a`.
/// - `Undirected`: All other endpoints of edges connected to `a`.
pub trait IntoNeighbors : GraphRef {
    @section type
    type Neighbors: Iterator<Item=Self::NodeId>;
    @section self
    /// Return an iterator of the neighbors of node `a`.
    fn neighbors(self, a: Self::NodeId) -> Self::Neighbors;
}
}

IntoNeighbors! {delegate_impl []}

trait_template! {
/// Access to the neighbors of each node, through incoming or outgoing edges.
///
/// Depending on the graph’s edge type, the neighbors of a given directionality
/// are:
///
/// - `Directed`, `Outgoing`: All targets of edges from `a`.
/// - `Directed`, `Incoming`: All sources of edges to `a`.
/// - `Undirected`: All other endpoints of edges connected to `a`.
pub trait IntoNeighborsDirected : IntoNeighbors {
    @section type
    type NeighborsDirected: Iterator<Item=Self::NodeId>;
    @section self
    fn neighbors_directed(self, n: Self::NodeId, d: Direction)
        -> Self::NeighborsDirected;
}
}

trait_template! {
/// Access to the edges of each node.
///
/// The edges are, depending on the graph’s edge type:
///
/// - `Directed`: All edges from `a`.
/// - `Undirected`: All edges connected to `a`, with `a` being the source of each edge.
///
/// This is an extended version of the trait `IntoNeighbors`; the former
/// only iterates over the target node identifiers, while this trait
/// yields edge references (trait [`EdgeRef`][er]).
///
/// [er]: trait.EdgeRef.html
pub trait IntoEdges : IntoEdgeReferences + IntoNeighbors {
    @section type
    type Edges: Iterator<Item=Self::EdgeRef>;
    @section self
    fn edges(self, a: Self::NodeId) -> Self::Edges;
}
}

IntoEdges! {delegate_impl []}

trait_template! {
/// Access to all edges of each node, in the specified direction.
///
/// The edges are, depending on the direction and the graph’s edge type:
///
///
/// - `Directed`, `Outgoing`: All edges from `a`.
/// - `Directed`, `Incoming`: All edges to `a`.
/// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each edge.
/// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each edge.
///
/// This is an extended version of the trait `IntoNeighborsDirected`; the former
/// only iterates over the target node identifiers, while this trait
/// yields edge references (trait [`EdgeRef`][er]).
///
/// [er]: trait.EdgeRef.html
pub trait IntoEdgesDirected : IntoEdges + IntoNeighborsDirected {
    @section type
    type EdgesDirected: Iterator<Item=Self::EdgeRef>;
    @section self
    fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected;
}
}

IntoEdgesDirected! {delegate_impl []}

trait_template! {
/// Access to the sequence of the graph’s `NodeId`s.
pub trait IntoNodeIdentifiers : GraphRef {
    @section type
    type NodeIdentifiers: Iterator<Item=Self::NodeId>;
    @section self
    fn node_identifiers(self) -> Self::NodeIdentifiers;
}
}

IntoNodeIdentifiers! {delegate_impl []}
IntoNeighborsDirected! {delegate_impl []}

trait_template! {
/// Define associated data for nodes and edges
pub trait Data : GraphBase {
    @section type
    type NodeWeight;
    type EdgeWeight;
}
}

Data! {delegate_impl []}
Data! {delegate_impl [['a, G], G, &'a mut G, deref]}

/// An edge reference.
///
/// Edge references are used by traits `IntoEdges` and `IntoEdgeReferences`.
pub trait EdgeRef: Copy {
    type NodeId;
    type EdgeId;
    type Weight;
    /// The source node of the edge.
    fn source(&self) -> Self::NodeId;
    /// The target node of the edge.
    fn target(&self) -> Self::NodeId;
    /// A reference to the weight of the edge.
    fn weight(&self) -> &Self::Weight;
    /// The edge’s identifier.
    fn id(&self) -> Self::EdgeId;
}

impl<N, E> EdgeRef for (N, N, &E)
where
    N: Copy,
{
    type NodeId = N;
    type EdgeId = (N, N);
    type Weight = E;

    fn source(&self) -> N {
        self.0
    }
    fn target(&self) -> N {
        self.1
    }
    fn weight(&self) -> &E {
        self.2
    }
    fn id(&self) -> (N, N) {
        (self.0, self.1)
    }
}

/// A node reference.
pub trait NodeRef: Copy {
    type NodeId;
    type Weight;
    fn id(&self) -> Self::NodeId;
    fn weight(&self) -> &Self::Weight;
}

trait_template! {
/// Access to the sequence of the graph’s nodes
pub trait IntoNodeReferences : Data + IntoNodeIdentifiers {
    @section type
    type NodeRef: NodeRef<NodeId=Self::NodeId, Weight=Self::NodeWeight>;
    type NodeReferences: Iterator<Item=Self::NodeRef>;
    @section self
    fn node_references(self) -> Self::NodeReferences;
}
}

IntoNodeReferences! {delegate_impl []}

impl<Id> NodeRef for (Id, ())
where
    Id: Copy,
{
    type NodeId = Id;
    type Weight = ();
    fn id(&self) -> Self::NodeId {
        self.0
    }
    fn weight(&self) -> &Self::Weight {
        static DUMMY: () = ();
        &DUMMY
    }
}

impl<Id, W> NodeRef for (Id, &W)
where
    Id: Copy,
{
    type NodeId = Id;
    type Weight = W;
    fn id(&self) -> Self::NodeId {
        self.0
    }
    fn weight(&self) -> &Self::Weight {
        self.1
    }
}

trait_template! {
/// Access to the sequence of the graph’s edges
pub trait IntoEdgeReferences : Data + GraphRef {
    @section type
    type EdgeRef: EdgeRef<NodeId=Self::NodeId, EdgeId=Self::EdgeId,
                          Weight=Self::EdgeWeight>;
    type EdgeReferences: Iterator<Item=Self::EdgeRef>;
    @section self
    fn edge_references(self) -> Self::EdgeReferences;
}
}

IntoEdgeReferences! {delegate_impl [] }

trait_template! {
    /// Edge kind property (directed or undirected edges)
pub trait GraphProp : GraphBase {
    @section type
    /// The kind of edges in the graph.
    type EdgeType: EdgeType;

    @section nodelegate
    fn is_directed(&self) -> bool {
        <Self::EdgeType>::is_directed()
    }
}
}

GraphProp! {delegate_impl []}

trait_template! {
    /// The graph’s `NodeId`s map to indices
    #[allow(clippy::needless_arbitrary_self_type)]
    pub trait NodeIndexable : GraphBase {
        @section self
        /// Return an upper bound of the node indices in the graph
        /// (suitable for the size of a bitmap).
        fn node_bound(self: &Self) -> usize;
        /// Convert `a` to an integer index.
        #[track_caller]
        fn to_index(self: &Self, a: Self::NodeId) -> usize;
        /// Convert `i` to a node index. `i` must be a valid value in the graph.
        #[track_caller]
        fn from_index(self: &Self, i: usize) -> Self::NodeId;
    }
}

NodeIndexable! {delegate_impl []}

trait_template! {
    /// The graph’s `NodeId`s map to indices
    #[allow(clippy::needless_arbitrary_self_type)]
    pub trait EdgeIndexable : GraphBase {
        @section self
        /// Return an upper bound of the edge indices in the graph
        /// (suitable for the size of a bitmap).
        fn edge_bound(self: &Self) -> usize;
        /// Convert `a` to an integer index.
        #[track_caller]
        fn to_index(self: &Self, a: Self::EdgeId) -> usize;
        /// Convert `i` to an edge index. `i` must be a valid value in the graph.
        #[track_caller]
        fn from_index(self: &Self, i: usize) -> Self::EdgeId;
    }
}

EdgeIndexable! {delegate_impl []}

trait_template! {
/// A graph with a known node count.
#[allow(clippy::needless_arbitrary_self_type)]
pub trait NodeCount : GraphBase {
    @section self
    fn node_count(self: &Self) -> usize;
}
}

NodeCount! {delegate_impl []}

trait_template! {
/// The graph’s `NodeId`s map to indices, in a range without holes.
///
/// The graph's node identifiers correspond to exactly the indices
/// `0..self.node_bound()`.
pub trait NodeCompactIndexable : NodeIndexable + NodeCount { }
}

NodeCompactIndexable! {delegate_impl []}

/// A mapping for storing the visited status for NodeId `N`.
pub trait VisitMap<N> {
    /// Mark `a` as visited.
    ///
    /// Return **true** if this is the first visit, false otherwise.
    fn visit(&mut self, a: N) -> bool;

    /// Return whether `a` has been visited before.
    fn is_visited(&self, a: &N) -> bool;

    /// Mark `a` as unvisited.
    ///
    /// Return **true** if this vertex was marked as visited at the time of unsetting it, false otherwise.
    fn unvisit(&mut self, _a: N) -> bool;
}

impl<Ix> VisitMap<Ix> for FixedBitSet
where
    Ix: IndexType,
{
    fn visit(&mut self, x: Ix) -> bool {
        !self.put(x.index())
    }
    fn is_visited(&self, x: &Ix) -> bool {
        self.contains(x.index())
    }

    fn unvisit(&mut self, x: Ix) -> bool {
        if self.is_visited(&x) {
            self.toggle(x.index());
            return true;
        }
        false
    }
}

impl<N, S> VisitMap<N> for HashSet<N, S>
where
    N: Hash + Eq,
    S: BuildHasher,
{
    fn visit(&mut self, x: N) -> bool {
        self.insert(x)
    }
    fn is_visited(&self, x: &N) -> bool {
        self.contains(x)
    }

    fn unvisit(&mut self, x: N) -> bool {
        self.remove(&x)
    }
}

#[cfg(feature = "std")]
impl<N, S> VisitMap<N> for std::collections::HashSet<N, S>
where
    N: Hash + Eq,
    S: BuildHasher,
{
    fn visit(&mut self, x: N) -> bool {
        self.insert(x)
    }
    fn is_visited(&self, x: &N) -> bool {
        self.contains(x)
    }

    fn unvisit(&mut self, x: N) -> bool {
        self.remove(&x)
    }
}

trait_template! {
/// A graph that can create a map that tracks the visited status of its nodes.
#[allow(clippy::needless_arbitrary_self_type)]
pub trait Visitable : GraphBase {
    @section type
    /// The associated map type
    type Map: VisitMap<Self::NodeId>;
    @section self
    /// Create a new visitor map
    fn visit_map(self: &Self) -> Self::Map;
    /// Reset the visitor map (and resize to new size of graph if needed)
    fn reset_map(self: &Self, map: &mut Self::Map);
}
}
Visitable! {delegate_impl []}

trait_template! {
/// Create or access the adjacency matrix of a graph.
///
/// The implementor can either create an adjacency matrix, or it can return
/// a placeholder if it has the needed representation internally.
#[allow(clippy::needless_arbitrary_self_type)]
pub trait GetAdjacencyMatrix : GraphBase {
    @section type
    /// The associated adjacency matrix type
    type AdjMatrix;
    @section self
    /// Create the adjacency matrix
    fn adjacency_matrix(self: &Self) -> Self::AdjMatrix;
    /// Return true if there is an edge from `a` to `b`, false otherwise.
    ///
    /// Computes in O(1) time.
    fn is_adjacent(self: &Self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool;
}
}

GetAdjacencyMatrix! {delegate_impl []}

trait_template! {
/// A graph with a known edge count.
#[allow(clippy::needless_arbitrary_self_type)]
pub trait EdgeCount : GraphBase {
    @section self
    /// Return the number of edges in the graph.
    fn edge_count(self: &Self) -> usize;
}
}

EdgeCount! {delegate_impl []}

mod filter;
mod reversed;
mod undirected_adaptor;

Coverage Report

Created: 2025-12-10 06:37

Line	Count	Source
1		//! Graph traits and graph traversals.
2		//!
3		//! ### The `Into-` Traits
4		//!
5		//! Graph traits like [`IntoNeighbors`][in] create iterators and use the same
6		//! pattern that `IntoIterator` does: the trait takes a reference to a graph,
7		//! and produces an iterator. These traits are quite composable, but with the
8		//! limitation that they only use shared references to graphs.
9		//!
10		//! ### Graph Traversal
11		//!
12		//! [`Dfs`](struct.Dfs.html), [`Bfs`][bfs], [`DfsPostOrder`][dfspo] and
13		//! [`Topo`][topo] are basic visitors and they use “walker” methods: the
14		//! visitors don't hold the graph as borrowed during traversal, only for the
15		//! `.next()` call on the walker. They can be converted to iterators
16		//! through the [`Walker`][w] trait.
17		//!
18		//! There is also the callback based traversal [`depth_first_search`][dfs].
19		//!
20		//! [bfs]: struct.Bfs.html
21		//! [dfspo]: struct.DfsPostOrder.html
22		//! [topo]: struct.Topo.html
23		//! [dfs]: fn.depth_first_search.html
24		//! [w]: trait.Walker.html
25		//!
26		//! ### Other Graph Traits
27		//!
28		//! The traits are rather loosely coupled at the moment (which is intentional,
29		//! but will develop a bit), and there are traits missing that could be added.
30		//!
31		//! Not much is needed to be able to use the visitors on a graph. A graph
32		//! needs to define [`GraphBase`][gb], [`IntoNeighbors`][in] and
33		//! [`Visitable`][vis] as a minimum.
34		//!
35		//! [gb]: trait.GraphBase.html
36		//! [in]: trait.IntoNeighbors.html
37		//! [vis]: trait.Visitable.html
38		//!
39		//! ### Graph Trait Implementations
40		//!
41		//! The following table lists the traits that are implemented for each graph type:
42		//!
43		//! \| \| Graph \| StableGraph \| GraphMap \| MatrixGraph \| Csr \| List \|
44		//! \| --------------------- \| :---: \| :---------: \| :------: \| :---------: \| :---: \| :---: \|
45		//! \| GraphBase \| x \| x \| x \| x \| x \| x \|
46		//! \| GraphProp \| x \| x \| x \| x \| x \| x \|
47		//! \| NodeCount \| x \| x \| x \| x \| x \| x \|
48		//! \| NodeIndexable \| x \| x \| x \| x \| x \| x \|
49		//! \| NodeCompactIndexable \| x \| \| x \| \| x \| x \|
50		//! \| EdgeCount \| x \| x \| x \| x \| x \| x \|
51		//! \| EdgeIndexable \| x \| x \| x \| \| \| \|
52		//! \| Data \| x \| x \| x \| x \| x \| x \|
53		//! \| IntoNodeIdentifiers \| x \| x \| x \| x \| x \| x \|
54		//! \| IntoNodeReferences \| x \| x \| x \| x \| x \| x \|
55		//! \| IntoEdgeReferences \| x \| x \| x \| x \| x \| x \|
56		//! \| IntoNeighbors \| x \| x \| x \| x \| x \| x \|
57		//! \| IntoNeighborsDirected \| x \| x \| x \| x \| \| \|
58		//! \| IntoEdges \| x \| x \| x \| x \| x \| x \|
59		//! \| IntoEdgesDirected \| x \| x \| x \| x \| \| \|
60		//! \| Visitable \| x \| x \| x \| x \| x \| x \|
61		//! \| GetAdjacencyMatrix \| x \| x \| x \| x \| x \| x \|
62
63		// filter, reversed have their `mod` lines at the end,
64		// so that they can use the trait template macros
65		pub use self::filter::*;
66		pub use self::reversed::*;
67		pub use self::undirected_adaptor::*;
68
69		#[macro_use]
70		mod macros;
71
72		mod dfsvisit;
73		mod traversal;
74		pub use self::dfsvisit::*;
75		pub use self::traversal::*;
76
77		use core::hash::{BuildHasher, Hash};
78
79		use fixedbitset::FixedBitSet;
80		use hashbrown::HashSet;
81
82		use super::EdgeType;
83		use crate::prelude::Direction;
84
85		use crate::graph::IndexType;
86
87		trait_template! {
88		/// Base graph trait: defines the associated node identifier and
89		/// edge identifier types.
90		pub trait GraphBase {
91		// FIXME: We can drop this escape/nodelegate stuff in Rust 1.18
92		@escape [type NodeId]
93		@escape [type EdgeId]
94		@section nodelegate
95		/// edge identifier
96		type EdgeId: Copy + PartialEq;
97		/// node identifier
98		type NodeId: Copy + PartialEq;
99		}
100		}
101
102		GraphBase! {delegate_impl []}
103		GraphBase! {delegate_impl [['a, G], G, &'a mut G, deref]}
104
105		/// A copyable reference to a graph.
106		pub trait GraphRef: Copy + GraphBase {}
107
108		impl<G> GraphRef for &G where G: GraphBase {}
109
110		trait_template! {
111		/// Access to the neighbors of each node
112		///
113		/// The neighbors are, depending on the graph’s edge type:
114		///
115		/// - `Directed`: All targets of edges from `a`.
116		/// - `Undirected`: All other endpoints of edges connected to `a`.
117		pub trait IntoNeighbors : GraphRef {
118		@section type
119		type Neighbors: Iterator<Item=Self::NodeId>;
120		@section self
121		/// Return an iterator of the neighbors of node `a`.
122		fn neighbors(self, a: Self::NodeId) -> Self::Neighbors;
123		}
124		}
125
126		IntoNeighbors! {delegate_impl []}
127
128		trait_template! {
129		/// Access to the neighbors of each node, through incoming or outgoing edges.
130		///
131		/// Depending on the graph’s edge type, the neighbors of a given directionality
132		/// are:
133		///
134		/// - `Directed`, `Outgoing`: All targets of edges from `a`.
135		/// - `Directed`, `Incoming`: All sources of edges to `a`.
136		/// - `Undirected`: All other endpoints of edges connected to `a`.
137		pub trait IntoNeighborsDirected : IntoNeighbors {
138		@section type
139		type NeighborsDirected: Iterator<Item=Self::NodeId>;
140		@section self
141		fn neighbors_directed(self, n: Self::NodeId, d: Direction)
142		-> Self::NeighborsDirected;
143		}
144		}
145
146		trait_template! {
147		/// Access to the edges of each node.
148		///
149		/// The edges are, depending on the graph’s edge type:
150		///
151		/// - `Directed`: All edges from `a`.
152		/// - `Undirected`: All edges connected to `a`, with `a` being the source of each edge.
153		///
154		/// This is an extended version of the trait `IntoNeighbors`; the former
155		/// only iterates over the target node identifiers, while this trait
156		/// yields edge references (trait [`EdgeRef`][er]).
157		///
158		/// [er]: trait.EdgeRef.html
159		pub trait IntoEdges : IntoEdgeReferences + IntoNeighbors {
160		@section type
161		type Edges: Iterator<Item=Self::EdgeRef>;
162		@section self
163		fn edges(self, a: Self::NodeId) -> Self::Edges;
164		}
165		}
166
167		IntoEdges! {delegate_impl []}
168
169		trait_template! {
170		/// Access to all edges of each node, in the specified direction.
171		///
172		/// The edges are, depending on the direction and the graph’s edge type:
173		///
174		///
175		/// - `Directed`, `Outgoing`: All edges from `a`.
176		/// - `Directed`, `Incoming`: All edges to `a`.
177		/// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each edge.
178		/// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each edge.
179		///
180		/// This is an extended version of the trait `IntoNeighborsDirected`; the former
181		/// only iterates over the target node identifiers, while this trait
182		/// yields edge references (trait [`EdgeRef`][er]).
183		///
184		/// [er]: trait.EdgeRef.html
185		pub trait IntoEdgesDirected : IntoEdges + IntoNeighborsDirected {
186		@section type
187		type EdgesDirected: Iterator<Item=Self::EdgeRef>;
188		@section self
189		fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected;
190		}
191		}
192
193		IntoEdgesDirected! {delegate_impl []}
194
195		trait_template! {
196		/// Access to the sequence of the graph’s `NodeId`s.
197		pub trait IntoNodeIdentifiers : GraphRef {
198		@section type
199		type NodeIdentifiers: Iterator<Item=Self::NodeId>;
200		@section self
201		fn node_identifiers(self) -> Self::NodeIdentifiers;
202		}
203		}
204
205		IntoNodeIdentifiers! {delegate_impl []}
206		IntoNeighborsDirected! {delegate_impl []}
207
208		trait_template! {
209		/// Define associated data for nodes and edges
210		pub trait Data : GraphBase {
211		@section type
212		type NodeWeight;
213		type EdgeWeight;
214		}
215		}
216
217		Data! {delegate_impl []}
218		Data! {delegate_impl [['a, G], G, &'a mut G, deref]}
219
220		/// An edge reference.
221		///
222		/// Edge references are used by traits `IntoEdges` and `IntoEdgeReferences`.
223		pub trait EdgeRef: Copy {
224		type NodeId;
225		type EdgeId;
226		type Weight;
227		/// The source node of the edge.
228		fn source(&self) -> Self::NodeId;
229		/// The target node of the edge.
230		fn target(&self) -> Self::NodeId;
231		/// A reference to the weight of the edge.
232		fn weight(&self) -> &Self::Weight;
233		/// The edge’s identifier.
234		fn id(&self) -> Self::EdgeId;
235		}
236
237		impl<N, E> EdgeRef for (N, N, &E)
238		where
239		N: Copy,
240		{
241		type NodeId = N;
242		type EdgeId = (N, N);
243		type Weight = E;
244
245	0	fn source(&self) -> N {
246	0	self.0
247	0	}
248	0	fn target(&self) -> N {
249	0	self.1
250	0	}
251	0	fn weight(&self) -> &E {
252	0	self.2
253	0	}
254	0	fn id(&self) -> (N, N) {
255	0	(self.0, self.1)
256	0	}
257		}
258
259		/// A node reference.
260		pub trait NodeRef: Copy {
261		type NodeId;
262		type Weight;
263		fn id(&self) -> Self::NodeId;
264		fn weight(&self) -> &Self::Weight;
265		}
266
267		trait_template! {
268		/// Access to the sequence of the graph’s nodes
269		pub trait IntoNodeReferences : Data + IntoNodeIdentifiers {
270		@section type
271		type NodeRef: NodeRef<NodeId=Self::NodeId, Weight=Self::NodeWeight>;
272		type NodeReferences: Iterator<Item=Self::NodeRef>;
273		@section self
274		fn node_references(self) -> Self::NodeReferences;
275		}
276		}
277
278		IntoNodeReferences! {delegate_impl []}
279
280		impl<Id> NodeRef for (Id, ())
281		where
282		Id: Copy,
283		{
284		type NodeId = Id;
285		type Weight = ();
286	0	fn id(&self) -> Self::NodeId {
287	0	self.0
288	0	}
289	0	fn weight(&self) -> &Self::Weight {
290		static DUMMY: () = ();
291	0	&DUMMY
292	0	}
293		}
294
295		impl<Id, W> NodeRef for (Id, &W)
296		where
297		Id: Copy,
298		{
299		type NodeId = Id;
300		type Weight = W;
301	0	fn id(&self) -> Self::NodeId {
302	0	self.0
303	0	}
304	0	fn weight(&self) -> &Self::Weight {
305	0	self.1
306	0	}
307		}
308
309		trait_template! {
310		/// Access to the sequence of the graph’s edges
311		pub trait IntoEdgeReferences : Data + GraphRef {
312		@section type
313		type EdgeRef: EdgeRef<NodeId=Self::NodeId, EdgeId=Self::EdgeId,
314		Weight=Self::EdgeWeight>;
315		type EdgeReferences: Iterator<Item=Self::EdgeRef>;
316		@section self
317		fn edge_references(self) -> Self::EdgeReferences;
318		}
319		}
320
321		IntoEdgeReferences! {delegate_impl [] }
322
323		trait_template! {
324		/// Edge kind property (directed or undirected edges)
325		pub trait GraphProp : GraphBase {
326		@section type
327		/// The kind of edges in the graph.
328		type EdgeType: EdgeType;
329
330		@section nodelegate
331	0	fn is_directed(&self) -> bool {
332	0	<Self::EdgeType>::is_directed()
333	0	}
334		}
335		}
336
337		GraphProp! {delegate_impl []}
338
339		trait_template! {
340		/// The graph’s `NodeId`s map to indices
341		#[allow(clippy::needless_arbitrary_self_type)]
342		pub trait NodeIndexable : GraphBase {
343		@section self
344		/// Return an upper bound of the node indices in the graph
345		/// (suitable for the size of a bitmap).
346		fn node_bound(self: &Self) -> usize;
347		/// Convert `a` to an integer index.
348		#[track_caller]
349		fn to_index(self: &Self, a: Self::NodeId) -> usize;
350		/// Convert `i` to a node index. `i` must be a valid value in the graph.
351		#[track_caller]
352		fn from_index(self: &Self, i: usize) -> Self::NodeId;
353		}
354		}
355
356		NodeIndexable! {delegate_impl []}
357
358		trait_template! {
359		/// The graph’s `NodeId`s map to indices
360		#[allow(clippy::needless_arbitrary_self_type)]
361		pub trait EdgeIndexable : GraphBase {
362		@section self
363		/// Return an upper bound of the edge indices in the graph
364		/// (suitable for the size of a bitmap).
365		fn edge_bound(self: &Self) -> usize;
366		/// Convert `a` to an integer index.
367		#[track_caller]
368		fn to_index(self: &Self, a: Self::EdgeId) -> usize;
369		/// Convert `i` to an edge index. `i` must be a valid value in the graph.
370		#[track_caller]
371		fn from_index(self: &Self, i: usize) -> Self::EdgeId;
372		}
373		}
374
375		EdgeIndexable! {delegate_impl []}
376
377		trait_template! {
378		/// A graph with a known node count.
379		#[allow(clippy::needless_arbitrary_self_type)]
380		pub trait NodeCount : GraphBase {
381		@section self
382		fn node_count(self: &Self) -> usize;
383		}
384		}
385
386		NodeCount! {delegate_impl []}
387
388		trait_template! {
389		/// The graph’s `NodeId`s map to indices, in a range without holes.
390		///
391		/// The graph's node identifiers correspond to exactly the indices
392		/// `0..self.node_bound()`.
393		pub trait NodeCompactIndexable : NodeIndexable + NodeCount { }
394		}
395
396		NodeCompactIndexable! {delegate_impl []}
397
398		/// A mapping for storing the visited status for NodeId `N`.
399		pub trait VisitMap<N> {
400		/// Mark `a` as visited.
401		///
402		/// Return true if this is the first visit, false otherwise.
403		fn visit(&mut self, a: N) -> bool;
404
405		/// Return whether `a` has been visited before.
406		fn is_visited(&self, a: &N) -> bool;
407
408		/// Mark `a` as unvisited.
409		///
410		/// Return true if this vertex was marked as visited at the time of unsetting it, false otherwise.
411		fn unvisit(&mut self, _a: N) -> bool;
412		}
413
414		impl<Ix> VisitMap<Ix> for FixedBitSet
415		where
416		Ix: IndexType,
417		{
418	0	fn visit(&mut self, x: Ix) -> bool {
419	0	!self.put(x.index())
420	0	}
421	0	fn is_visited(&self, x: &Ix) -> bool {
422	0	self.contains(x.index())
423	0	}
424
425	0	fn unvisit(&mut self, x: Ix) -> bool {
426	0	if self.is_visited(&x) {
427	0	self.toggle(x.index());
428	0	return true;
429	0	}
430	0	false
431	0	}
432		}
433
434		impl<N, S> VisitMap<N> for HashSet<N, S>
435		where
436		N: Hash + Eq,
437		S: BuildHasher,
438		{
439	0	fn visit(&mut self, x: N) -> bool {
440	0	self.insert(x)
441	0	} Unexecuted instantiation: <hashbrown::set::HashSet<u32> as petgraph::visit::VisitMap<u32>>::visit Unexecuted instantiation: <hashbrown::set::HashSet<_, _> as petgraph::visit::VisitMap<_>>::visit
442	0	fn is_visited(&self, x: &N) -> bool {
443	0	self.contains(x)
444	0	} Unexecuted instantiation: <hashbrown::set::HashSet<u32> as petgraph::visit::VisitMap<u32>>::is_visited Unexecuted instantiation: <hashbrown::set::HashSet<_, _> as petgraph::visit::VisitMap<_>>::is_visited
445
446	0	fn unvisit(&mut self, x: N) -> bool {
447	0	self.remove(&x)
448	0	}
449		}
450
451		#[cfg(feature = "std")]
452		impl<N, S> VisitMap<N> for std::collections::HashSet<N, S>
453		where
454		N: Hash + Eq,
455		S: BuildHasher,
456		{
457		fn visit(&mut self, x: N) -> bool {
458		self.insert(x)
459		}
460		fn is_visited(&self, x: &N) -> bool {
461		self.contains(x)
462		}
463
464		fn unvisit(&mut self, x: N) -> bool {
465		self.remove(&x)
466		}
467		}
468
469		trait_template! {
470		/// A graph that can create a map that tracks the visited status of its nodes.
471		#[allow(clippy::needless_arbitrary_self_type)]
472		pub trait Visitable : GraphBase {
473		@section type
474		/// The associated map type
475		type Map: VisitMap<Self::NodeId>;
476		@section self
477		/// Create a new visitor map
478		fn visit_map(self: &Self) -> Self::Map;
479		/// Reset the visitor map (and resize to new size of graph if needed)
480		fn reset_map(self: &Self, map: &mut Self::Map);
481		}
482		}
483		Visitable! {delegate_impl []}
484
485		trait_template! {
486		/// Create or access the adjacency matrix of a graph.
487		///
488		/// The implementor can either create an adjacency matrix, or it can return
489		/// a placeholder if it has the needed representation internally.
490		#[allow(clippy::needless_arbitrary_self_type)]
491		pub trait GetAdjacencyMatrix : GraphBase {
492		@section type
493		/// The associated adjacency matrix type
494		type AdjMatrix;
495		@section self
496		/// Create the adjacency matrix
497		fn adjacency_matrix(self: &Self) -> Self::AdjMatrix;
498		/// Return true if there is an edge from `a` to `b`, false otherwise.
499		///
500		/// Computes in O(1) time.
501		fn is_adjacent(self: &Self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool;
502		}
503		}
504
505		GetAdjacencyMatrix! {delegate_impl []}
506
507		trait_template! {
508		/// A graph with a known edge count.
509		#[allow(clippy::needless_arbitrary_self_type)]
510		pub trait EdgeCount : GraphBase {
511		@section self
512		/// Return the number of edges in the graph.
513		fn edge_count(self: &Self) -> usize;
514		}
515		}
516
517		EdgeCount! {delegate_impl []}
518
519		mod filter;
520		mod reversed;
521		mod undirected_adaptor;