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;