petgraph/visit/
mod.rs

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
65pub use self::filter::*;
66pub use self::reversed::*;
67pub use self::undirected_adaptor::*;
68
69#[macro_use]
70mod macros;
71
72mod dfsvisit;
73mod traversal;
74pub use self::dfsvisit::*;
75pub use self::traversal::*;
76
77use core::hash::{BuildHasher, Hash};
78
79use fixedbitset::FixedBitSet;
80use hashbrown::HashSet;
81
82use super::EdgeType;
83use crate::prelude::Direction;
84
85use crate::graph::IndexType;
86
87trait_template! {
88/// Base graph trait: defines the associated node identifier and
89/// edge identifier types.
90pub 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
102GraphBase! {delegate_impl []}
103GraphBase! {delegate_impl [['a, G], G, &'a mut G, deref]}
104
105/// A copyable reference to a graph.
106pub trait GraphRef: Copy + GraphBase {}
107
108impl<G> GraphRef for &G where G: GraphBase {}
109
110trait_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`.
117pub 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
126IntoNeighbors! {delegate_impl []}
127
128trait_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`.
137pub 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
146trait_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
159pub 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
167IntoEdges! {delegate_impl []}
168
169trait_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
185pub 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
193IntoEdgesDirected! {delegate_impl []}
194
195trait_template! {
196/// Access to the sequence of the graph’s `NodeId`s.
197pub 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
205IntoNodeIdentifiers! {delegate_impl []}
206IntoNeighborsDirected! {delegate_impl []}
207
208trait_template! {
209/// Define associated data for nodes and edges
210pub trait Data : GraphBase {
211    @section type
212    type NodeWeight;
213    type EdgeWeight;
214}
215}
216
217Data! {delegate_impl []}
218Data! {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`.
223pub 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
237impl<N, E> EdgeRef for (N, N, &E)
238where
239    N: Copy,
240{
241    type NodeId = N;
242    type EdgeId = (N, N);
243    type Weight = E;
244
245    fn source(&self) -> N {
246        self.0
247    }
248    fn target(&self) -> N {
249        self.1
250    }
251    fn weight(&self) -> &E {
252        self.2
253    }
254    fn id(&self) -> (N, N) {
255        (self.0, self.1)
256    }
257}
258
259/// A node reference.
260pub trait NodeRef: Copy {
261    type NodeId;
262    type Weight;
263    fn id(&self) -> Self::NodeId;
264    fn weight(&self) -> &Self::Weight;
265}
266
267trait_template! {
268/// Access to the sequence of the graph’s nodes
269pub 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
278IntoNodeReferences! {delegate_impl []}
279
280impl<Id> NodeRef for (Id, ())
281where
282    Id: Copy,
283{
284    type NodeId = Id;
285    type Weight = ();
286    fn id(&self) -> Self::NodeId {
287        self.0
288    }
289    fn weight(&self) -> &Self::Weight {
290        static DUMMY: () = ();
291        &DUMMY
292    }
293}
294
295impl<Id, W> NodeRef for (Id, &W)
296where
297    Id: Copy,
298{
299    type NodeId = Id;
300    type Weight = W;
301    fn id(&self) -> Self::NodeId {
302        self.0
303    }
304    fn weight(&self) -> &Self::Weight {
305        self.1
306    }
307}
308
309trait_template! {
310/// Access to the sequence of the graph’s edges
311pub 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
321IntoEdgeReferences! {delegate_impl [] }
322
323trait_template! {
324    /// Edge kind property (directed or undirected edges)
325pub trait GraphProp : GraphBase {
326    @section type
327    /// The kind of edges in the graph.
328    type EdgeType: EdgeType;
329
330    @section nodelegate
331    fn is_directed(&self) -> bool {
332        <Self::EdgeType>::is_directed()
333    }
334}
335}
336
337GraphProp! {delegate_impl []}
338
339trait_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
356NodeIndexable! {delegate_impl []}
357
358trait_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
375EdgeIndexable! {delegate_impl []}
376
377trait_template! {
378/// A graph with a known node count.
379#[allow(clippy::needless_arbitrary_self_type)]
380pub trait NodeCount : GraphBase {
381    @section self
382    fn node_count(self: &Self) -> usize;
383}
384}
385
386NodeCount! {delegate_impl []}
387
388trait_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()`.
393pub trait NodeCompactIndexable : NodeIndexable + NodeCount { }
394}
395
396NodeCompactIndexable! {delegate_impl []}
397
398/// A mapping for storing the visited status for NodeId `N`.
399pub 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
414impl<Ix> VisitMap<Ix> for FixedBitSet
415where
416    Ix: IndexType,
417{
418    fn visit(&mut self, x: Ix) -> bool {
419        !self.put(x.index())
420    }
421    fn is_visited(&self, x: &Ix) -> bool {
422        self.contains(x.index())
423    }
424
425    fn unvisit(&mut self, x: Ix) -> bool {
426        if self.is_visited(&x) {
427            self.toggle(x.index());
428            return true;
429        }
430        false
431    }
432}
433
434impl<N, S> VisitMap<N> for HashSet<N, S>
435where
436    N: Hash + Eq,
437    S: BuildHasher,
438{
439    fn visit(&mut self, x: N) -> bool {
440        self.insert(x)
441    }
442    fn is_visited(&self, x: &N) -> bool {
443        self.contains(x)
444    }
445
446    fn unvisit(&mut self, x: N) -> bool {
447        self.remove(&x)
448    }
449}
450
451#[cfg(feature = "std")]
452impl<N, S> VisitMap<N> for std::collections::HashSet<N, S>
453where
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
469trait_template! {
470/// A graph that can create a map that tracks the visited status of its nodes.
471#[allow(clippy::needless_arbitrary_self_type)]
472pub 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}
483Visitable! {delegate_impl []}
484
485trait_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)]
491pub 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
505GetAdjacencyMatrix! {delegate_impl []}
506
507trait_template! {
508/// A graph with a known edge count.
509#[allow(clippy::needless_arbitrary_self_type)]
510pub 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
517EdgeCount! {delegate_impl []}
518
519mod filter;
520mod reversed;
521mod undirected_adaptor;