petgraph/algo/
mod.rs

Help
1//! Graph algorithms.
2//!
3//! It is a goal to gradually migrate the algorithms to be based on graph traits
4//! so that they are generally applicable. For now, some of these still require
5//! the `Graph` type.
6
7pub mod articulation_points;
8pub mod astar;
9pub mod bellman_ford;
10pub mod coloring;
11pub mod dijkstra;
12pub mod dominators;
13pub mod feedback_arc_set;
14pub mod floyd_warshall;
15pub mod ford_fulkerson;
16pub mod isomorphism;
17pub mod k_shortest_path;
18pub mod matching;
19pub mod maximal_cliques;
20pub mod min_spanning_tree;
21pub mod page_rank;
22pub mod simple_paths;
23pub mod spfa;
24#[cfg(feature = "stable_graph")]
25pub mod steiner_tree;
26pub mod tred;
27
28use alloc::{vec, vec::Vec};
29use core::num::NonZeroUsize;
30
31use crate::prelude::*;
32
33use super::graph::IndexType;
34use super::unionfind::UnionFind;
35use super::visit::{
36    GraphBase, GraphRef, IntoEdgeReferences, IntoNeighbors, IntoNeighborsDirected,
37    IntoNodeIdentifiers, NodeCompactIndexable, NodeIndexable, Reversed, VisitMap, Visitable,
38};
39use super::EdgeType;
40use crate::visit::Walker;
41
42pub use astar::astar;
43pub use bellman_ford::{bellman_ford, find_negative_cycle};
44pub use coloring::dsatur_coloring;
45pub use dijkstra::dijkstra;
46pub use feedback_arc_set::greedy_feedback_arc_set;
47pub use floyd_warshall::floyd_warshall;
48pub use ford_fulkerson::ford_fulkerson;
49pub use isomorphism::{
50    is_isomorphic, is_isomorphic_matching, is_isomorphic_subgraph, is_isomorphic_subgraph_matching,
51    subgraph_isomorphisms_iter,
52};
53pub use k_shortest_path::k_shortest_path;
54pub use matching::{greedy_matching, maximum_matching, Matching};
55pub use maximal_cliques::maximal_cliques;
56pub use min_spanning_tree::{min_spanning_tree, min_spanning_tree_prim};
57pub use page_rank::page_rank;
58pub use simple_paths::all_simple_paths;
59pub use spfa::spfa;
60#[cfg(feature = "stable_graph")]
61pub use steiner_tree::steiner_tree;
62
63/// \[Generic\] Return the number of connected components of the graph.
64///
65/// For a directed graph, this is the *weakly* connected components.
66/// # Example
67/// ```rust
68/// use petgraph::Graph;
69/// use petgraph::algo::connected_components;
70/// use petgraph::prelude::*;
71///
72/// let mut graph : Graph<(),(),Directed>= Graph::new();
73/// let a = graph.add_node(()); // node with no weight
74/// let b = graph.add_node(());
75/// let c = graph.add_node(());
76/// let d = graph.add_node(());
77/// let e = graph.add_node(());
78/// let f = graph.add_node(());
79/// let g = graph.add_node(());
80/// let h = graph.add_node(());
81///
82/// graph.extend_with_edges(&[
83///     (a, b),
84///     (b, c),
85///     (c, d),
86///     (d, a),
87///     (e, f),
88///     (f, g),
89///     (g, h),
90///     (h, e)
91/// ]);
92/// // a ----> b       e ----> f
93/// // ^       |       ^       |
94/// // |       v       |       v
95/// // d <---- c       h <---- g
96///
97/// assert_eq!(connected_components(&graph),2);
98/// graph.add_edge(b,e,());
99/// assert_eq!(connected_components(&graph),1);
100/// ```
101pub fn connected_components<G>(g: G) -> usize
102where
103    G: NodeCompactIndexable + IntoEdgeReferences,
104{
105    let mut vertex_sets = UnionFind::new(g.node_bound());
106    for edge in g.edge_references() {
107        let (a, b) = (edge.source(), edge.target());
108
109        // union the two vertices of the edge
110        vertex_sets.union(g.to_index(a), g.to_index(b));
111    }
112    let mut labels = vertex_sets.into_labeling();
113    labels.sort_unstable();
114    labels.dedup();
115    labels.len()
116}
117
118/// \[Generic\] Return `true` if the input graph contains a cycle.
119///
120/// Always treats the input graph as if undirected.
121pub fn is_cyclic_undirected<G>(g: G) -> bool
122where
123    G: NodeIndexable + IntoEdgeReferences,
124{
125    let mut edge_sets = UnionFind::new(g.node_bound());
126    for edge in g.edge_references() {
127        let (a, b) = (edge.source(), edge.target());
128
129        // union the two vertices of the edge
130        //  -- if they were already the same, then we have a cycle
131        if !edge_sets.union(g.to_index(a), g.to_index(b)) {
132            return true;
133        }
134    }
135    false
136}
137
138/// \[Generic\] Perform a topological sort of a directed graph.
139///
140/// If the graph was acyclic, return a vector of nodes in topological order:
141/// each node is ordered before its successors.
142/// Otherwise, it will return a `Cycle` error. Self loops are also cycles.
143///
144/// To handle graphs with cycles, use the scc algorithms or `DfsPostOrder`
145/// instead of this function.
146///
147/// If `space` is not `None`, it is used instead of creating a new workspace for
148/// graph traversal. The implementation is iterative.
149pub fn toposort<G>(
150    g: G,
151    space: Option<&mut DfsSpace<G::NodeId, G::Map>>,
152) -> Result<Vec<G::NodeId>, Cycle<G::NodeId>>
153where
154    G: IntoNeighborsDirected + IntoNodeIdentifiers + Visitable,
155{
156    // based on kosaraju scc
157    with_dfs(g, space, |dfs| {
158        dfs.reset(g);
159        let mut finished = g.visit_map();
160
161        let mut finish_stack = Vec::new();
162        for i in g.node_identifiers() {
163            if dfs.discovered.is_visited(&i) {
164                continue;
165            }
166            dfs.stack.push(i);
167            while let Some(&nx) = dfs.stack.last() {
168                if dfs.discovered.visit(nx) {
169                    // First time visiting `nx`: Push neighbors, don't pop `nx`
170                    for succ in g.neighbors(nx) {
171                        if succ == nx {
172                            // self cycle
173                            return Err(Cycle(nx));
174                        }
175                        if !dfs.discovered.is_visited(&succ) {
176                            dfs.stack.push(succ);
177                        }
178                    }
179                } else {
180                    dfs.stack.pop();
181                    if finished.visit(nx) {
182                        // Second time: All reachable nodes must have been finished
183                        finish_stack.push(nx);
184                    }
185                }
186            }
187        }
188        finish_stack.reverse();
189
190        dfs.reset(g);
191        for &i in &finish_stack {
192            dfs.move_to(i);
193            let mut cycle = false;
194            while let Some(j) = dfs.next(Reversed(g)) {
195                if cycle {
196                    return Err(Cycle(j));
197                }
198                cycle = true;
199            }
200        }
201
202        Ok(finish_stack)
203    })
204}
205
206/// \[Generic\] Return `true` if the input directed graph contains a cycle.
207///
208/// This implementation is recursive; use `toposort` if an alternative is
209/// needed.
210pub fn is_cyclic_directed<G>(g: G) -> bool
211where
212    G: IntoNodeIdentifiers + IntoNeighbors + Visitable,
213{
214    use crate::visit::{depth_first_search, DfsEvent};
215
216    depth_first_search(g, g.node_identifiers(), |event| match event {
217        DfsEvent::BackEdge(_, _) => Err(()),
218        _ => Ok(()),
219    })
220    .is_err()
221}
222
223type DfsSpaceType<G> = DfsSpace<<G as GraphBase>::NodeId, <G as Visitable>::Map>;
224
225/// Workspace for a graph traversal.
226#[derive(Clone, Debug)]
227pub struct DfsSpace<N, VM> {
228    dfs: Dfs<N, VM>,
229}
230
231impl<N, VM> DfsSpace<N, VM>
232where
233    N: Copy + PartialEq,
234    VM: VisitMap<N>,
235{
236    pub fn new<G>(g: G) -> Self
237    where
238        G: GraphRef + Visitable<NodeId = N, Map = VM>,
239    {
240        DfsSpace { dfs: Dfs::empty(g) }
241    }
242}
243
244impl<N, VM> Default for DfsSpace<N, VM>
245where
246    VM: VisitMap<N> + Default,
247{
248    fn default() -> Self {
249        DfsSpace {
250            dfs: Dfs {
251                stack: <_>::default(),
252                discovered: <_>::default(),
253            },
254        }
255    }
256}
257
258/// Create a Dfs if it's needed
259fn with_dfs<G, F, R>(g: G, space: Option<&mut DfsSpaceType<G>>, f: F) -> R
260where
261    G: GraphRef + Visitable,
262    F: FnOnce(&mut Dfs<G::NodeId, G::Map>) -> R,
263{
264    let mut local_visitor;
265    let dfs = if let Some(v) = space {
266        &mut v.dfs
267    } else {
268        local_visitor = Dfs::empty(g);
269        &mut local_visitor
270    };
271    f(dfs)
272}
273
274/// \[Generic\] Check if there exists a path starting at `from` and reaching `to`.
275///
276/// If `from` and `to` are equal, this function returns true.
277///
278/// If `space` is not `None`, it is used instead of creating a new workspace for
279/// graph traversal.
280pub fn has_path_connecting<G>(
281    g: G,
282    from: G::NodeId,
283    to: G::NodeId,
284    space: Option<&mut DfsSpace<G::NodeId, G::Map>>,
285) -> bool
286where
287    G: IntoNeighbors + Visitable,
288{
289    with_dfs(g, space, |dfs| {
290        dfs.reset(g);
291        dfs.move_to(from);
292        dfs.iter(g).any(|x| x == to)
293    })
294}
295
296/// Renamed to `kosaraju_scc`.
297#[deprecated(note = "renamed to kosaraju_scc")]
298pub fn scc<G>(g: G) -> Vec<Vec<G::NodeId>>
299where
300    G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
301{
302    kosaraju_scc(g)
303}
304
305/// \[Generic\] Compute the *strongly connected components* using [Kosaraju's algorithm][1].
306///
307/// [1]: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
308///
309/// Return a vector where each element is a strongly connected component (scc).
310/// The order of node ids within each scc is arbitrary, but the order of
311/// the sccs is their postorder (reverse topological sort).
312///
313/// For an undirected graph, the sccs are simply the connected components.
314///
315/// This implementation is iterative and does two passes over the nodes.
316pub fn kosaraju_scc<G>(g: G) -> Vec<Vec<G::NodeId>>
317where
318    G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
319{
320    let mut dfs = DfsPostOrder::empty(g);
321
322    // First phase, reverse dfs pass, compute finishing times.
323    // http://stackoverflow.com/a/26780899/161659
324    let mut finish_order = Vec::with_capacity(0);
325    for i in g.node_identifiers() {
326        if dfs.discovered.is_visited(&i) {
327            continue;
328        }
329
330        dfs.move_to(i);
331        while let Some(nx) = dfs.next(Reversed(g)) {
332            finish_order.push(nx);
333        }
334    }
335
336    let mut dfs = Dfs::from_parts(dfs.stack, dfs.discovered);
337    dfs.reset(g);
338    let mut sccs = Vec::new();
339
340    // Second phase
341    // Process in decreasing finishing time order
342    for i in finish_order.into_iter().rev() {
343        if dfs.discovered.is_visited(&i) {
344            continue;
345        }
346        // Move to the leader node `i`.
347        dfs.move_to(i);
348        let mut scc = Vec::new();
349        while let Some(nx) = dfs.next(g) {
350            scc.push(nx);
351        }
352        sccs.push(scc);
353    }
354    sccs
355}
356
357#[derive(Copy, Clone, Debug)]
358struct NodeData {
359    rootindex: Option<NonZeroUsize>,
360}
361
362/// A reusable state for computing the *strongly connected components* using [Tarjan's algorithm][1].
363///
364/// [1]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
365#[derive(Debug)]
366pub struct TarjanScc<N> {
367    index: usize,
368    componentcount: usize,
369    nodes: Vec<NodeData>,
370    stack: Vec<N>,
371}
372
373impl<N> Default for TarjanScc<N> {
374    fn default() -> Self {
375        Self::new()
376    }
377}
378
379impl<N> TarjanScc<N> {
380    /// Creates a new `TarjanScc`
381    pub fn new() -> Self {
382        TarjanScc {
383            index: 1,                   // Invariant: index < componentcount at all times.
384            componentcount: usize::MAX, // Will hold if componentcount is initialized to number of nodes - 1 or higher.
385            nodes: Vec::new(),
386            stack: Vec::new(),
387        }
388    }
389
390    /// \[Generic\] Compute the *strongly connected components* using Algorithm 3 in
391    /// [A Space-Efficient Algorithm for Finding Strongly Connected Components][1] by David J. Pierce,
392    /// which is a memory-efficient variation of [Tarjan's algorithm][2].
393    ///
394    ///
395    /// [1]: https://homepages.ecs.vuw.ac.nz/~djp/files/P05.pdf
396    /// [2]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
397    ///
398    /// Calls `f` for each strongly strongly connected component (scc).
399    /// The order of node ids within each scc is arbitrary, but the order of
400    /// the sccs is their postorder (reverse topological sort).
401    ///
402    /// For an undirected graph, the sccs are simply the connected components.
403    ///
404    /// This implementation is recursive and does one pass over the nodes.
405    pub fn run<G, F>(&mut self, g: G, mut f: F)
406    where
407        G: IntoNodeIdentifiers<NodeId = N> + IntoNeighbors<NodeId = N> + NodeIndexable<NodeId = N>,
408        F: FnMut(&[N]),
409        N: Copy + PartialEq,
410    {
411        self.nodes.clear();
412        self.nodes
413            .resize(g.node_bound(), NodeData { rootindex: None });
414
415        for n in g.node_identifiers() {
416            let visited = self.nodes[g.to_index(n)].rootindex.is_some();
417            if !visited {
418                self.visit(n, g, &mut f);
419            }
420        }
421
422        debug_assert!(self.stack.is_empty());
423    }
424
425    fn visit<G, F>(&mut self, v: G::NodeId, g: G, f: &mut F)
426    where
427        G: IntoNeighbors<NodeId = N> + NodeIndexable<NodeId = N>,
428        F: FnMut(&[N]),
429        N: Copy + PartialEq,
430    {
431        macro_rules! node {
432            ($node:expr) => {
433                self.nodes[g.to_index($node)]
434            };
435        }
436
437        let node_v = &mut node![v];
438        debug_assert!(node_v.rootindex.is_none());
439
440        let mut v_is_local_root = true;
441        let v_index = self.index;
442        node_v.rootindex = NonZeroUsize::new(v_index);
443        self.index += 1;
444
445        for w in g.neighbors(v) {
446            if node![w].rootindex.is_none() {
447                self.visit(w, g, f);
448            }
449            if node![w].rootindex < node![v].rootindex {
450                node![v].rootindex = node![w].rootindex;
451                v_is_local_root = false
452            }
453        }
454
455        if v_is_local_root {
456            // Pop the stack and generate an SCC.
457            let mut indexadjustment = 1;
458            let c = NonZeroUsize::new(self.componentcount);
459            let nodes = &mut self.nodes;
460            let start = self
461                .stack
462                .iter()
463                .rposition(|&w| {
464                    if nodes[g.to_index(v)].rootindex > nodes[g.to_index(w)].rootindex {
465                        true
466                    } else {
467                        nodes[g.to_index(w)].rootindex = c;
468                        indexadjustment += 1;
469                        false
470                    }
471                })
472                .map(|x| x + 1)
473                .unwrap_or_default();
474            nodes[g.to_index(v)].rootindex = c;
475            self.stack.push(v); // Pushing the component root to the back right before getting rid of it is somewhat ugly, but it lets it be included in f.
476            f(&self.stack[start..]);
477            self.stack.truncate(start);
478            self.index -= indexadjustment; // Backtrack index back to where it was before we ever encountered the component.
479            self.componentcount -= 1;
480        } else {
481            self.stack.push(v); // Stack is filled up when backtracking, unlike in Tarjans original algorithm.
482        }
483    }
484
485    /// Returns the index of the component in which v has been assigned. Allows for using self as a lookup table for an scc decomposition produced by self.run().
486    pub fn node_component_index<G>(&self, g: G, v: N) -> usize
487    where
488        G: IntoNeighbors<NodeId = N> + NodeIndexable<NodeId = N>,
489        N: Copy + PartialEq,
490    {
491        let rindex: usize = self.nodes[g.to_index(v)]
492            .rootindex
493            .map(NonZeroUsize::get)
494            .unwrap_or(0); // Compiles to no-op.
495        debug_assert!(
496            rindex != 0,
497            "Tried to get the component index of an unvisited node."
498        );
499        debug_assert!(
500            rindex > self.componentcount,
501            "Given node has been visited but not yet assigned to a component."
502        );
503        usize::MAX - rindex
504    }
505}
506
507/// \[Generic\] Compute the *strongly connected components* using [Tarjan's algorithm][1].
508///
509/// [1]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
510/// [2]: https://homepages.ecs.vuw.ac.nz/~djp/files/P05.pdf
511///
512/// Return a vector where each element is a strongly connected component (scc).
513/// The order of node ids within each scc is arbitrary, but the order of
514/// the sccs is their postorder (reverse topological sort).
515///
516/// For an undirected graph, the sccs are simply the connected components.
517///
518/// This implementation is recursive and does one pass over the nodes. It is based on
519/// [A Space-Efficient Algorithm for Finding Strongly Connected Components][2] by David J. Pierce,
520/// to provide a memory-efficient implementation of [Tarjan's algorithm][1].
521pub fn tarjan_scc<G>(g: G) -> Vec<Vec<G::NodeId>>
522where
523    G: IntoNodeIdentifiers + IntoNeighbors + NodeIndexable,
524{
525    let mut sccs = Vec::new();
526    {
527        let mut tarjan_scc = TarjanScc::new();
528        tarjan_scc.run(g, |scc| sccs.push(scc.to_vec()));
529    }
530    sccs
531}
532
533/// [Graph] Condense every strongly connected component into a single node and return the result.
534///
535/// If `make_acyclic` is true, self-loops and multi edges are ignored, guaranteeing that
536/// the output is acyclic.
537/// # Example
538/// ```rust
539/// use petgraph::Graph;
540/// use petgraph::algo::condensation;
541/// use petgraph::prelude::*;
542///
543/// let mut graph : Graph<(),(),Directed> = Graph::new();
544/// let a = graph.add_node(()); // node with no weight
545/// let b = graph.add_node(());
546/// let c = graph.add_node(());
547/// let d = graph.add_node(());
548/// let e = graph.add_node(());
549/// let f = graph.add_node(());
550/// let g = graph.add_node(());
551/// let h = graph.add_node(());
552///
553/// graph.extend_with_edges(&[
554///     (a, b),
555///     (b, c),
556///     (c, d),
557///     (d, a),
558///     (b, e),
559///     (e, f),
560///     (f, g),
561///     (g, h),
562///     (h, e)
563/// ]);
564///
565/// // a ----> b ----> e ----> f
566/// // ^       |       ^       |
567/// // |       v       |       v
568/// // d <---- c       h <---- g
569///
570/// let condensed_graph = condensation(graph,false);
571/// let A = NodeIndex::new(0);
572/// let B = NodeIndex::new(1);
573/// assert_eq!(condensed_graph.node_count(), 2);
574/// assert_eq!(condensed_graph.edge_count(), 9);
575/// assert_eq!(condensed_graph.neighbors(A).collect::<Vec<_>>(), vec![A, A, A, A]);
576/// assert_eq!(condensed_graph.neighbors(B).collect::<Vec<_>>(), vec![A, B, B, B, B]);
577/// ```
578/// If `make_acyclic` is true, self-loops and multi edges are ignored:
579///
580/// ```rust
581/// # use petgraph::Graph;
582/// # use petgraph::algo::condensation;
583/// # use petgraph::prelude::*;
584/// #
585/// # let mut graph : Graph<(),(),Directed> = Graph::new();
586/// # let a = graph.add_node(()); // node with no weight
587/// # let b = graph.add_node(());
588/// # let c = graph.add_node(());
589/// # let d = graph.add_node(());
590/// # let e = graph.add_node(());
591/// # let f = graph.add_node(());
592/// # let g = graph.add_node(());
593/// # let h = graph.add_node(());
594/// #
595/// # graph.extend_with_edges(&[
596/// #    (a, b),
597/// #    (b, c),
598/// #    (c, d),
599/// #    (d, a),
600/// #    (b, e),
601/// #    (e, f),
602/// #    (f, g),
603/// #    (g, h),
604/// #    (h, e)
605/// # ]);
606/// let acyclic_condensed_graph = condensation(graph, true);
607/// let A = NodeIndex::new(0);
608/// let B = NodeIndex::new(1);
609/// assert_eq!(acyclic_condensed_graph.node_count(), 2);
610/// assert_eq!(acyclic_condensed_graph.edge_count(), 1);
611/// assert_eq!(acyclic_condensed_graph.neighbors(B).collect::<Vec<_>>(), vec![A]);
612/// ```
613pub fn condensation<N, E, Ty, Ix>(
614    g: Graph<N, E, Ty, Ix>,
615    make_acyclic: bool,
616) -> Graph<Vec<N>, E, Ty, Ix>
617where
618    Ty: EdgeType,
619    Ix: IndexType,
620{
621    let sccs = kosaraju_scc(&g);
622    let mut condensed: Graph<Vec<N>, E, Ty, Ix> = Graph::with_capacity(sccs.len(), g.edge_count());
623
624    // Build a map from old indices to new ones.
625    let mut node_map = vec![NodeIndex::end(); g.node_count()];
626    for comp in sccs {
627        let new_nix = condensed.add_node(Vec::new());
628        for nix in comp {
629            node_map[nix.index()] = new_nix;
630        }
631    }
632
633    // Consume nodes and edges of the old graph and insert them into the new one.
634    let (nodes, edges) = g.into_nodes_edges();
635    for (nix, node) in nodes.into_iter().enumerate() {
636        condensed[node_map[nix]].push(node.weight);
637    }
638    for edge in edges {
639        let source = node_map[edge.source().index()];
640        let target = node_map[edge.target().index()];
641        if make_acyclic {
642            if source != target {
643                condensed.update_edge(source, target, edge.weight);
644            }
645        } else {
646            condensed.add_edge(source, target, edge.weight);
647        }
648    }
649    condensed
650}
651
652/// An algorithm error: a cycle was found in the graph.
653#[derive(Clone, Debug, PartialEq)]
654pub struct Cycle<N>(pub(crate) N);
655
656impl<N> Cycle<N> {
657    /// Return a node id that participates in the cycle
658    pub fn node_id(&self) -> N
659    where
660        N: Copy,
661    {
662        self.0
663    }
664}
665
666/// An algorithm error: a cycle of negative weights was found in the graph.
667#[derive(Clone, Debug, PartialEq)]
668pub struct NegativeCycle(pub ());
669
670/// Return `true` if the graph is bipartite. A graph is bipartite if its nodes can be divided into
671/// two disjoint and indepedent sets U and V such that every edge connects U to one in V. This
672/// algorithm implements 2-coloring algorithm based on the BFS algorithm.
673///
674/// Always treats the input graph as if undirected.
675pub fn is_bipartite_undirected<G, N, VM>(g: G, start: N) -> bool
676where
677    G: GraphRef + Visitable<NodeId = N, Map = VM> + IntoNeighbors<NodeId = N>,
678    N: Copy + PartialEq + core::fmt::Debug,
679    VM: VisitMap<N>,
680{
681    let mut red = g.visit_map();
682    red.visit(start);
683    let mut blue = g.visit_map();
684
685    let mut stack = ::alloc::collections::VecDeque::new();
686    stack.push_front(start);
687
688    while let Some(node) = stack.pop_front() {
689        let is_red = red.is_visited(&node);
690        let is_blue = blue.is_visited(&node);
691
692        assert!(is_red ^ is_blue);
693
694        for neighbour in g.neighbors(node) {
695            let is_neigbour_red = red.is_visited(&neighbour);
696            let is_neigbour_blue = blue.is_visited(&neighbour);
697
698            if (is_red && is_neigbour_red) || (is_blue && is_neigbour_blue) {
699                return false;
700            }
701
702            if !is_neigbour_red && !is_neigbour_blue {
703                //hasn't been visited yet
704
705                match (is_red, is_blue) {
706                    (true, false) => {
707                        blue.visit(neighbour);
708                    }
709                    (false, true) => {
710                        red.visit(neighbour);
711                    }
712                    (_, _) => {
713                        panic!("Invariant doesn't hold");
714                    }
715                }
716
717                stack.push_back(neighbour);
718            }
719        }
720    }
721
722    true
723}
724
725use core::fmt::Debug;
726use core::ops::Add;
727
728/// Associated data that can be used for measures (such as length).
729pub trait Measure: Debug + PartialOrd + Add<Self, Output = Self> + Default + Clone {}
730
731impl<M> Measure for M where M: Debug + PartialOrd + Add<M, Output = M> + Default + Clone {}
732
733/// A floating-point measure.
734pub trait FloatMeasure: Measure + Copy {
735    fn zero() -> Self;
736    fn infinite() -> Self;
737    fn from_f32(val: f32) -> Self;
738    fn from_f64(val: f64) -> Self;
739}
740
741impl FloatMeasure for f32 {
742    fn zero() -> Self {
743        0.
744    }
745    fn infinite() -> Self {
746        1. / 0.
747    }
748    fn from_f32(val: f32) -> Self {
749        val
750    }
751    fn from_f64(val: f64) -> Self {
752        val as f32
753    }
754}
755
756impl FloatMeasure for f64 {
757    fn zero() -> Self {
758        0.
759    }
760    fn infinite() -> Self {
761        1. / 0.
762    }
763    fn from_f32(val: f32) -> Self {
764        val as f64
765    }
766    fn from_f64(val: f64) -> Self {
767        val
768    }
769}
770
771pub trait BoundedMeasure: Measure + core::ops::Sub<Self, Output = Self> {
772    fn min() -> Self;
773    fn max() -> Self;
774    fn overflowing_add(self, rhs: Self) -> (Self, bool);
775    fn from_f32(val: f32) -> Self;
776    fn from_f64(val: f64) -> Self;
777}
778
779macro_rules! impl_bounded_measure_integer(
780    ( $( $t:ident ),* ) => {
781        $(
782            impl BoundedMeasure for $t {
783                fn min() -> Self {
784                    $t::MIN
785                }
786
787                fn max() -> Self {
788                    $t::MAX
789                }
790
791                fn overflowing_add(self, rhs: Self) -> (Self, bool) {
792                    self.overflowing_add(rhs)
793                }
794
795                fn from_f32(val: f32) -> Self {
796                    val as $t
797                }
798
799                fn from_f64(val: f64) -> Self {
800                    val as $t
801                }
802            }
803        )*
804    };
805);
806
807impl_bounded_measure_integer!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize);
808
809macro_rules! impl_bounded_measure_float(
810    ( $( $t:ident ),* ) => {
811        $(
812            impl BoundedMeasure for $t {
813                fn min() -> Self {
814                    $t::MIN
815                }
816
817                fn max() -> Self {
818                    $t::MAX
819                }
820
821                fn overflowing_add(self, rhs: Self) -> (Self, bool) {
822                    // for an overflow: a + b > max: both values need to be positive and a > max - b must be satisfied
823                    let overflow = self > Self::default() && rhs > Self::default() && self > $t::MAX - rhs;
824
825                    // for an underflow: a + b < min: overflow can not happen and both values must be negative and a < min - b must be satisfied
826                    let underflow = !overflow && self < Self::default() && rhs < Self::default() && self < $t::MIN - rhs;
827
828                    (self + rhs, overflow || underflow)
829                }
830
831                fn from_f32(val: f32) -> Self {
832                    val as $t
833                }
834
835                fn from_f64(val: f64) -> Self {
836                    val as $t
837                }
838            }
839        )*
840    };
841);
842
843impl_bounded_measure_float!(f32, f64);
844
845/// A floating-point measure that can be computed from `usize`
846/// and with a default measure of proximity.  
847pub trait UnitMeasure:
848    Measure
849    + core::ops::Sub<Self, Output = Self>
850    + core::ops::Mul<Self, Output = Self>
851    + core::ops::Div<Self, Output = Self>
852    + core::iter::Sum
853{
854    fn zero() -> Self;
855    fn one() -> Self;
856    fn from_usize(nb: usize) -> Self;
857    fn default_tol() -> Self;
858    fn from_f32(val: f32) -> Self;
859    fn from_f64(val: f64) -> Self;
860}
861
862macro_rules! impl_unit_measure(
863    ( $( $t:ident ),* )=> {
864        $(
865            impl UnitMeasure for $t {
866                fn zero() -> Self {
867                    0 as $t
868                }
869                fn one() -> Self {
870                    1 as $t
871                }
872
873                fn from_usize(nb: usize) -> Self {
874                    nb as $t
875                }
876
877                fn default_tol() -> Self {
878                    1e-6 as $t
879                }
880
881                fn from_f32(val: f32) -> Self {
882                    val as $t
883                }
884
885                fn from_f64(val: f64) -> Self {
886                    val as $t
887                }
888            }
889
890        )*
891    }
892);
893impl_unit_measure!(f32, f64);
894
895/// Some measure of positive numbers, assuming positive
896/// float-pointing numbers
897pub trait PositiveMeasure: Measure + Copy {
898    fn zero() -> Self;
899    fn max() -> Self;
900}
901
902macro_rules! impl_positive_measure(
903    ( $( $t:ident ),* )=> {
904        $(
905            impl PositiveMeasure for $t {
906                fn zero() -> Self {
907                    0 as $t
908                }
909                fn max() -> Self {
910                    $t::MAX
911                }
912            }
913
914        )*
915    }
916);
917
918impl_positive_measure!(u8, u16, u32, u64, u128, usize, f32, f64);
petgraph/algo/mod.rs

petgraph/algo/
mod.rs
