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
40// filter, reversed have their `mod` lines at the end,
41// so that they can use the trait template macros
42pub use self::filter::*;
43pub use self::reversed::*;
44
45#[macro_use] mod macros;
46
47mod dfsvisit;
48mod traversal;
49pub use self::dfsvisit::*;
50pub use self::traversal::*;
51
52use fixedbitset::FixedBitSet;
53use std::collections::{
54    HashSet,
55};
56use std::hash::{Hash, BuildHasher};
57
58use prelude::{Graph, Direction};
59#[cfg(feature = "graphmap")]
60use prelude::GraphMap;
61#[cfg(feature = "stable_graph")]
62use prelude::StableGraph;
63use graph::{NodeIndex};
64use super::{
65    graph,
66    EdgeType,
67};
68
69use graph::{
70    IndexType,
71};
72#[cfg(feature = "stable_graph")]
73use stable_graph;
74use graph::Frozen;
75
76#[cfg(feature = "graphmap")]
77use graphmap::{
78    self,
79    NodeTrait,
80};
81
82trait_template!{
83/// Base graph trait: defines the associated node identifier and
84/// edge identifier types.
85pub trait GraphBase {
86    // FIXME: We can drop this escape/nodelegate stuff in Rust 1.18
87    @escape [type NodeId]
88    @escape [type EdgeId]
89    @section nodelegate
90    /// edge identifier
91    type EdgeId: Copy + PartialEq;
92    /// node identifier
93    type NodeId: Copy + PartialEq;
94}
95}
96
97GraphBase!{delegate_impl []}
98GraphBase!{delegate_impl [['a, G], G, &'a mut G, deref]}
99
100/// A copyable reference to a graph.
101pub trait GraphRef : Copy + GraphBase { }
102
103impl<'a, G> GraphRef for &'a G where G: GraphBase { }
104
105impl<'a, G> GraphBase for Frozen<'a, G> where G: GraphBase {
106    type NodeId = G::NodeId;
107    type EdgeId = G::EdgeId;
108}
109
110#[cfg(feature = "stable_graph")]
111impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a StableGraph<N, E, Ty, Ix>
112    where Ty: EdgeType,
113          Ix: IndexType,
114{
115    type Neighbors = stable_graph::Neighbors<'a, E, Ix>;
116    fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
117        (*self).neighbors(n)
118    }
119}
120
121
122#[cfg(feature = "graphmap")]
123impl<'a, N: 'a, E, Ty> IntoNeighbors for &'a GraphMap<N, E, Ty>
124    where N: Copy + Ord + Hash,
125          Ty: EdgeType,
126{
127    type Neighbors = graphmap::Neighbors<'a, N, Ty>;
128    fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
129        self.neighbors(n)
130    }
131}
132
133
134trait_template! {
135/// Access to the neighbors of each node
136///
137/// The neighbors are, depending on the graph’s edge type:
138///
139/// - `Directed`: All targets of edges from `a`.
140/// - `Undirected`: All other endpoints of edges connected to `a`.
141pub trait IntoNeighbors : GraphRef {
142    @section type
143    type Neighbors: Iterator<Item=Self::NodeId>;
144    @section self
145    /// Return an iterator of the neighbors of node `a`.
146    fn neighbors(self: Self, a: Self::NodeId) -> Self::Neighbors;
147}
148}
149
150IntoNeighbors!{delegate_impl []}
151
152trait_template! {
153/// Access to the neighbors of each node, through incoming or outgoing edges.
154///
155/// Depending on the graph’s edge type, the neighbors of a given directionality
156/// are:
157///
158/// - `Directed`, `Outgoing`: All targets of edges from `a`.
159/// - `Directed`, `Incoming`: All sources of edges to `a`.
160/// - `Undirected`: All other endpoints of edges connected to `a`.
161pub trait IntoNeighborsDirected : IntoNeighbors {
162    @section type
163    type NeighborsDirected: Iterator<Item=Self::NodeId>;
164    @section self
165    fn neighbors_directed(self, n: Self::NodeId, d: Direction)
166        -> Self::NeighborsDirected;
167}
168}
169
170impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a Graph<N, E, Ty, Ix>
171    where Ty: EdgeType,
172          Ix: IndexType,
173{
174    type Neighbors = graph::Neighbors<'a, E, Ix>;
175    fn neighbors(self, n: graph::NodeIndex<Ix>)
176        -> graph::Neighbors<'a, E, Ix>
177    {
178        Graph::neighbors(self, n)
179    }
180}
181
182impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a Graph<N, E, Ty, Ix>
183    where Ty: EdgeType,
184          Ix: IndexType,
185{
186    type NeighborsDirected = graph::Neighbors<'a, E, Ix>;
187    fn neighbors_directed(self, n: graph::NodeIndex<Ix>, d: Direction)
188        -> graph::Neighbors<'a, E, Ix>
189    {
190        Graph::neighbors_directed(self, n, d)
191    }
192}
193
194#[cfg(feature = "stable_graph")]
195impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a StableGraph<N, E, Ty, Ix>
196    where Ty: EdgeType,
197          Ix: IndexType,
198{
199    type NeighborsDirected = stable_graph::Neighbors<'a, E, Ix>;
200    fn neighbors_directed(self, n: graph::NodeIndex<Ix>, d: Direction)
201        -> Self::NeighborsDirected
202    {
203        StableGraph::neighbors_directed(self, n, d)
204    }
205}
206
207#[cfg(feature = "graphmap")]
208impl<'a, N: 'a, E, Ty> IntoNeighborsDirected for &'a GraphMap<N, E, Ty>
209    where N: Copy + Ord + Hash,
210          Ty: EdgeType,
211{
212    type NeighborsDirected = graphmap::NeighborsDirected<'a, N, Ty>;
213    fn neighbors_directed(self, n: N, dir: Direction)
214        -> Self::NeighborsDirected
215    {
216        self.neighbors_directed(n, dir)
217    }
218}
219
220trait_template! {
221/// Access to the edges of each node.
222///
223/// The edges are, depending on the graph’s edge type:
224///
225/// - `Directed`: All edges from `a`.
226/// - `Undirected`: All edges connected to `a`.
227///
228/// This is an extended version of the trait `IntoNeighbors`; the former
229/// only iterates over the target node identifiers, while this trait
230/// yields edge references (trait [`EdgeRef`][er]).
231///
232/// [er]: trait.EdgeRef.html
233pub trait IntoEdges : IntoEdgeReferences + IntoNeighbors {
234    @section type
235    type Edges: Iterator<Item=Self::EdgeRef>;
236    @section self
237    fn edges(self, a: Self::NodeId) -> Self::Edges;
238}
239}
240
241IntoEdges!{delegate_impl []}
242
243trait_template! {
244/// Access to all edges of each node, in the specified direction.
245///
246/// The edges are, depending on the direction and the graph’s edge type:
247///
248///
249/// - `Directed`, `Outgoing`: All edges from `a`.
250/// - `Directed`, `Incoming`: All edges to `a`.
251/// - `Undirected`: All edges connected to `a`.
252///
253/// This is an extended version of the trait `IntoNeighborsDirected`; the former
254/// only iterates over the target node identifiers, while this trait
255/// yields edge references (trait [`EdgeRef`][er]).
256///
257/// [er]: trait.EdgeRef.html
258pub trait IntoEdgesDirected : IntoEdges + IntoNeighborsDirected {
259    @section type
260    type EdgesDirected: Iterator<Item=Self::EdgeRef>;
261    @section self
262    fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected;
263}
264}
265
266IntoEdgesDirected!{delegate_impl []}
267
268trait_template! {
269/// Access to the sequence of the graph’s `NodeId`s.
270pub trait IntoNodeIdentifiers : GraphRef {
271    @section type
272    type NodeIdentifiers: Iterator<Item=Self::NodeId>;
273    @section self
274    fn node_identifiers(self) -> Self::NodeIdentifiers;
275}
276}
277
278IntoNodeIdentifiers!{delegate_impl []}
279
280impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a Graph<N, E, Ty, Ix>
281    where Ty: EdgeType,
282          Ix: IndexType,
283{
284    type NodeIdentifiers = graph::NodeIndices<Ix>;
285    fn node_identifiers(self) -> graph::NodeIndices<Ix> {
286        Graph::node_indices(self)
287    }
288}
289
290impl<N, E, Ty, Ix> NodeCount for Graph<N, E, Ty, Ix>
291    where Ty: EdgeType,
292          Ix: IndexType,
293{
294    fn node_count(&self) -> usize {
295        self.node_count()
296    }
297}
298
299#[cfg(feature = "stable_graph")]
300impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a StableGraph<N, E, Ty, Ix>
301    where Ty: EdgeType,
302          Ix: IndexType,
303{
304    type NodeIdentifiers = stable_graph::NodeIndices<'a, N, Ix>;
305    fn node_identifiers(self) -> Self::NodeIdentifiers {
306        StableGraph::node_indices(self)
307    }
308}
309
310#[cfg(feature = "stable_graph")]
311impl<N, E, Ty, Ix> NodeCount for StableGraph<N, E, Ty, Ix>
312    where Ty: EdgeType,
313          Ix: IndexType,
314{
315    fn node_count(&self) -> usize {
316        self.node_count()
317    }
318}
319
320IntoNeighborsDirected!{delegate_impl []}
321
322trait_template! {
323/// Define associated data for nodes and edges
324pub trait Data : GraphBase {
325    @section type
326    type NodeWeight;
327    type EdgeWeight;
328}
329}
330
331Data!{delegate_impl []}
332Data!{delegate_impl [['a, G], G, &'a mut G, deref]}
333
334/// An edge reference.
335///
336/// Edge references are used by traits `IntoEdges` and `IntoEdgeReferences`.
337pub trait EdgeRef : Copy {
338    type NodeId;
339    type EdgeId;
340    type Weight;
341    /// The source node of the edge.
342    fn source(&self) -> Self::NodeId;
343    /// The target node of the edge.
344    fn target(&self) -> Self::NodeId;
345    /// A reference to the weight of the edge.
346    fn weight(&self) -> &Self::Weight;
347    /// The edge’s identifier.
348    fn id(&self) -> Self::EdgeId;
349}
350
351impl<'a, N, E> EdgeRef for (N, N, &'a E)
352    where N: Copy
353{
354    type NodeId = N;
355    type EdgeId = (N, N);
356    type Weight = E;
357
358    fn source(&self) -> N { self.0 }
359    fn target(&self) -> N { self.1 }
360    fn weight(&self) -> &E { self.2 }
361    fn id(&self) -> (N, N) { (self.0, self.1) }
362}
363
364/// A node reference.
365pub trait NodeRef : Copy {
366    type NodeId;
367    type Weight;
368    fn id(&self) -> Self::NodeId;
369    fn weight(&self) -> &Self::Weight;
370}
371
372trait_template! {
373/// Access to the sequence of the graph’s nodes
374pub trait IntoNodeReferences : Data + IntoNodeIdentifiers {
375    @section type
376    type NodeRef: NodeRef<NodeId=Self::NodeId, Weight=Self::NodeWeight>;
377    type NodeReferences: Iterator<Item=Self::NodeRef>;
378    @section self
379    fn node_references(self) -> Self::NodeReferences;
380}
381}
382
383IntoNodeReferences!{delegate_impl []}
384
385impl<Id> NodeRef for (Id, ())
386    where Id: Copy,
387{
388    type NodeId = Id;
389    type Weight = ();
390    fn id(&self) -> Self::NodeId { self.0 }
391    fn weight(&self) -> &Self::Weight {
392        static DUMMY: () = ();
393        &DUMMY
394    }
395}
396
397impl<'a, Id, W> NodeRef for (Id, &'a W)
398    where Id: Copy,
399{
400    type NodeId = Id;
401    type Weight = W;
402    fn id(&self) -> Self::NodeId { self.0 }
403    fn weight(&self) -> &Self::Weight { self.1 }
404}
405
406
407trait_template! {
408/// Access to the sequence of the graph’s edges
409pub trait IntoEdgeReferences : Data + GraphRef {
410    @section type
411    type EdgeRef: EdgeRef<NodeId=Self::NodeId, EdgeId=Self::EdgeId,
412                          Weight=Self::EdgeWeight>;
413    type EdgeReferences: Iterator<Item=Self::EdgeRef>;
414    @section self
415    fn edge_references(self) -> Self::EdgeReferences;
416}
417}
418
419IntoEdgeReferences!{delegate_impl [] }
420
421#[cfg(feature = "graphmap")]
422impl<N, E, Ty> Data for GraphMap<N, E, Ty>
423    where N: Copy + PartialEq,
424          Ty: EdgeType,
425{
426    type NodeWeight = N;
427    type EdgeWeight = E;
428}
429
430trait_template! {
431    /// Edge kind property (directed or undirected edges)
432pub trait GraphProp : GraphBase {
433    @section type
434    /// The kind edges in the graph.
435    type EdgeType: EdgeType;
436
437    @section nodelegate
438    fn is_directed(&self) -> bool {
439        <Self::EdgeType>::is_directed()
440    }
441}
442}
443
444GraphProp!{delegate_impl []}
445
446impl<N, E, Ty, Ix> GraphProp for Graph<N, E, Ty, Ix>
447    where Ty: EdgeType,
448          Ix: IndexType,
449{
450    type EdgeType = Ty;
451}
452
453#[cfg(feature = "stable_graph")]
454impl<N, E, Ty, Ix> GraphProp for StableGraph<N, E, Ty, Ix>
455    where Ty: EdgeType,
456          Ix: IndexType,
457{
458    type EdgeType = Ty;
459}
460
461#[cfg(feature = "graphmap")]
462impl<N, E, Ty> GraphProp for GraphMap<N, E, Ty>
463    where N: NodeTrait,
464          Ty: EdgeType,
465{
466    type EdgeType = Ty;
467}
468
469
470impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a Graph<N, E, Ty, Ix>
471    where Ty: EdgeType,
472          Ix: IndexType,
473{
474    type EdgeRef = graph::EdgeReference<'a, E, Ix>;
475    type EdgeReferences = graph::EdgeReferences<'a, E, Ix>;
476    fn edge_references(self) -> Self::EdgeReferences {
477        (*self).edge_references()
478    }
479}
480
481
482trait_template!{
483    /// The graph’s `NodeId`s map to indices
484    pub trait NodeIndexable : GraphBase {
485        @section self
486        /// Return an upper bound of the node indices in the graph
487        /// (suitable for the size of a bitmap).
488        fn node_bound(self: &Self) -> usize;
489        /// Convert `a` to an integer index.
490        fn to_index(self: &Self, a: Self::NodeId) -> usize;
491        /// Convert `i` to a node index
492        fn from_index(self: &Self, i: usize) -> Self::NodeId;
493    }
494}
495
496NodeIndexable!{delegate_impl []}
497
498trait_template! {
499/// A graph with a known node count.
500pub trait NodeCount : GraphBase {
501    @section self
502    fn node_count(self: &Self) -> usize;
503}
504}
505
506NodeCount!{delegate_impl []}
507
508trait_template! {
509/// The graph’s `NodeId`s map to indices, in a range without holes.
510///
511/// The graph's node identifiers correspond to exactly the indices
512/// `0..self.node_bound()`.
513pub trait NodeCompactIndexable : NodeIndexable + NodeCount { }
514}
515
516NodeCompactIndexable!{delegate_impl []}
517
518impl<N, E, Ty, Ix> NodeIndexable for Graph<N, E, Ty, Ix>
519    where Ty: EdgeType,
520          Ix: IndexType,
521{
522    fn node_bound(&self) -> usize { self.node_count() }
523    fn to_index(&self, ix: NodeIndex<Ix>) -> usize { ix.index() }
524    fn from_index(&self, ix: usize) -> Self::NodeId { NodeIndex::new(ix) }
525}
526
527impl<N, E, Ty, Ix> NodeCompactIndexable for Graph<N, E, Ty, Ix>
528    where Ty: EdgeType,
529          Ix: IndexType,
530{ }
531
532/// A mapping for storing the visited status for NodeId `N`.
533pub trait VisitMap<N> {
534    /// Mark `a` as visited.
535    ///
536    /// Return **true** if this is the first visit, false otherwise.
537    fn visit(&mut self, a: N) -> bool;
538
539    /// Return whether `a` has been visited before.
540    fn is_visited(&self, a: &N) -> bool;
541}
542
543impl<Ix> VisitMap<graph::NodeIndex<Ix>> for FixedBitSet
544    where Ix: IndexType,
545{
546    fn visit(&mut self, x: graph::NodeIndex<Ix>) -> bool {
547        !self.put(x.index())
548    }
549    fn is_visited(&self, x: &graph::NodeIndex<Ix>) -> bool {
550        self.contains(x.index())
551    }
552}
553
554impl<Ix> VisitMap<graph::EdgeIndex<Ix>> for FixedBitSet
555    where Ix: IndexType,
556{
557    fn visit(&mut self, x: graph::EdgeIndex<Ix>) -> bool {
558        !self.put(x.index())
559    }
560    fn is_visited(&self, x: &graph::EdgeIndex<Ix>) -> bool {
561        self.contains(x.index())
562    }
563}
564
565impl<Ix> VisitMap<Ix> for FixedBitSet
566    where Ix: IndexType,
567{
568    fn visit(&mut self, x: Ix) -> bool {
569        !self.put(x.index())
570    }
571    fn is_visited(&self, x: &Ix) -> bool {
572        self.contains(x.index())
573    }
574}
575
576impl<N, S> VisitMap<N> for HashSet<N, S>
577    where N: Hash + Eq,
578          S: BuildHasher,
579{
580    fn visit(&mut self, x: N) -> bool {
581        self.insert(x)
582    }
583    fn is_visited(&self, x: &N) -> bool {
584        self.contains(x)
585    }
586}
587
588trait_template!{
589/// A graph that can create a map that tracks the visited status of its nodes.
590pub trait Visitable : GraphBase {
591    @section type
592    /// The associated map type
593    type Map: VisitMap<Self::NodeId>;
594    @section self
595    /// Create a new visitor map
596    fn visit_map(self: &Self) -> Self::Map;
597    /// Reset the visitor map (and resize to new size of graph if needed)
598    fn reset_map(self: &Self, map: &mut Self::Map) -> ();
599}
600}
601Visitable!{delegate_impl []}
602
603impl<N, E, Ty, Ix> GraphBase for Graph<N, E, Ty, Ix>
604    where Ix: IndexType,
605{
606    type NodeId = graph::NodeIndex<Ix>;
607    type EdgeId = graph::EdgeIndex<Ix>;
608}
609
610impl<N, E, Ty, Ix> Visitable for Graph<N, E, Ty, Ix>
611    where Ty: EdgeType,
612          Ix: IndexType,
613{
614    type Map = FixedBitSet;
615    fn visit_map(&self) -> FixedBitSet { FixedBitSet::with_capacity(self.node_count()) }
616
617    fn reset_map(&self, map: &mut Self::Map) {
618        map.clear();
619        map.grow(self.node_count());
620    }
621}
622
623#[cfg(feature = "stable_graph")]
624impl<N, E, Ty, Ix> GraphBase for StableGraph<N, E, Ty, Ix>
625    where Ix: IndexType,
626{
627    type NodeId = graph::NodeIndex<Ix>;
628    type EdgeId = graph::EdgeIndex<Ix>;
629}
630
631#[cfg(feature = "stable_graph")]
632impl<N, E, Ty, Ix> Visitable for StableGraph<N, E, Ty, Ix>
633    where Ty: EdgeType,
634          Ix: IndexType,
635{
636    type Map = FixedBitSet;
637    fn visit_map(&self) -> FixedBitSet {
638        FixedBitSet::with_capacity(self.node_bound())
639    }
640    fn reset_map(&self, map: &mut Self::Map) {
641        map.clear();
642        map.grow(self.node_bound());
643    }
644}
645
646#[cfg(feature = "stable_graph")]
647impl<N, E, Ty, Ix> Data for StableGraph<N, E, Ty, Ix>
648    where Ty: EdgeType,
649          Ix: IndexType,
650{
651    type NodeWeight = N;
652    type EdgeWeight = E;
653}
654
655
656#[cfg(feature = "graphmap")]
657impl<N, E, Ty> GraphBase for GraphMap<N, E, Ty>
658    where N: Copy + PartialEq,
659{
660    type NodeId = N;
661    type EdgeId = (N, N);
662}
663
664#[cfg(feature = "graphmap")]
665impl<N, E, Ty> Visitable for GraphMap<N, E, Ty>
666    where N: Copy + Ord + Hash,
667          Ty: EdgeType,
668{
669    type Map = HashSet<N>;
670    fn visit_map(&self) -> HashSet<N> { HashSet::with_capacity(self.node_count()) }
671    fn reset_map(&self, map: &mut Self::Map) {
672        map.clear();
673    }
674}
675
676trait_template! {
677/// Create or access the adjacency matrix of a graph.
678///
679/// The implementor can either create an adjacency matrix, or it can return
680/// a placeholder if it has the needed representation internally.
681pub trait GetAdjacencyMatrix : GraphBase {
682    @section type
683    /// The associated adjacency matrix type
684    type AdjMatrix;
685    @section self
686    /// Create the adjacency matrix
687    fn adjacency_matrix(self: &Self) -> Self::AdjMatrix;
688    /// Return true if there is an edge from `a` to `b`, false otherwise.
689    ///
690    /// Computes in O(1) time.
691    fn is_adjacent(self: &Self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool;
692}
693}
694
695
696GetAdjacencyMatrix!{delegate_impl []}
697
698#[cfg(feature = "graphmap")]
699/// The `GraphMap` keeps an adjacency matrix internally.
700impl<N, E, Ty> GetAdjacencyMatrix for GraphMap<N, E, Ty>
701    where N: Copy + Ord + Hash,
702          Ty: EdgeType,
703{
704    type AdjMatrix = ();
705    #[inline]
706    fn adjacency_matrix(&self) { }
707    #[inline]
708    fn is_adjacent(&self, _: &(), a: N, b: N) -> bool {
709        self.contains_edge(a, b)
710    }
711}
712
713mod filter;
714mod reversed;