petgraph/algo/
mod.rs

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

petgraph/algo/
mod.rs
