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

petgraph/algo/
mod.rs
