petgraph · jonimake · Feb 1, 2019 · Feb 4, 2020 · Feb 4, 2020 · Aug 25, 2020
diff --git a/.travis.yml b/.travis.yml
@@ -4,15 +4,24 @@ jobs:
     - rust: 1.37.0
       env:
       - ALL=' '
+      - FEATURES='default'
     - rust: stable
       env:
-        - FEATURES='unstable quickcheck'
+        - FEATURES='unstable quickcheck default'
         - CHECKFMT=1
     - rust: beta
+      env:
+       - FEATURES='default'
     - rust: nightly
+      env:
+        - FEATURES='default'
     - rust: nightly
       env:
-       - FEATURES='unstable quickcheck'
+       - ALL='--package petgraph'
+       - FEATURES='no_std'
+    - rust: nightly
+      env:
+       - FEATURES='unstable quickcheck default'
        - BENCH=1
 branches:
   only:
@@ -24,11 +33,10 @@ before_script:
       fi
 script:
   - |
-      cargo build --verbose --no-default-features &&
-      cargo test --verbose --no-default-features &&
-      cargo build --verbose --features "$FEATURES" &&
-      cargo test ${ALL:---all} --verbose --features "$FEATURES" &&
+      cargo build --verbose --no-default-features --features "$FEATURES" &&
+      cargo test ${ALL:---all} --verbose --no-default-features --features "$FEATURES" &&
       if [ "${CHECKFMT}" == "1"]; then
         cargo +stable fmt -- --check
       fi
 
+
diff --git a/Cargo.toml b/Cargo.toml
@@ -5,7 +5,7 @@ version = "0.5.1"
 license = "MIT/Apache-2.0"
 authors = [
 "bluss",
-"mitchmindtree",
+"mitchmindtree"
 ]
 
 description = "Graph data structure library. Provides graph types and graph algorithms."
@@ -31,7 +31,7 @@ debug = true
 fixedbitset = { version = "0.3.0", default-features = false }
 quickcheck = { optional = true, version = "0.8", default-features = false }
 indexmap = { version = "1.0.2" }
-serde = { version = "1.0", optional = true }
+serde = { version = "1.0", optional = true, default-features = false }
 serde_derive = { version = "1.0", optional = true }
 
 [dev-dependencies]
@@ -41,11 +41,15 @@ defmac = "0.1"
 itertools = { version = "0.8", default-features = false }
 
 [features]
-default = ["graphmap", "stable_graph", "matrix_graph"]
+default = ["graphmap", "stable_graph", "matrix_graph", "std"]
+std = []
 graphmap = []
-serde-1 = ["serde", "serde_derive"]
+serde-1 = ["serde/default", "serde_derive"]
+serde-1-no_std = ["serde", "serde_derive"]
 stable_graph = []
 matrix_graph = []
+no_std = ["alloc"]
+alloc = []
 
 # For unstable features
 generate = []

diff --git a/src/algo/dominators.rs b/src/algo/dominators.rs
@@ -12,9 +12,25 @@
 //! strictly dominates **B** and there does not exist any node **C** where **A**
 //! dominates **C** and **C** dominates **B**.
 
-use std::cmp::Ordering;
-use std::collections::{HashMap, HashSet, hash_map::Iter};
-use std::hash::Hash;
+#[cfg(feature = "alloc")]
+use alloc::{
+    collections::{BTreeSet as HashSet, btree_map::Iter},
+    vec::Vec,
+};
+
+#[cfg(feature = "alloc")]
+use indexmap::IndexMap as HashMap;
+
+#[cfg(feature = "no_std")]
+use core::{cmp::Ordering, hash::Hash, usize, iter::Iterator};
+
+#[cfg(feature = "std")]
+use std::{
+    cmp::Ordering,
+    collections::{HashMap, HashSet},
+    hash::Hash,
+    usize,
+};
 
 use crate::visit::{DfsPostOrder, GraphBase, IntoNeighbors, Visitable, Walker};
 
@@ -49,7 +65,7 @@ where
         }
     }
 
-    /// Iterate over the given node's strict dominators.
+    /// Iterate over the given node's that strict dominators.
     ///
     /// If the given node is not reachable from the root, then `None` is
     /// returned.
@@ -141,7 +157,7 @@ where
 
 /// The undefined dominator sentinel, for when we have not yet discovered a
 /// node's dominator.
-const UNDEFINED: usize = ::std::usize::MAX;
+const UNDEFINED: usize = usize::MAX;
 
 /// This is an implementation of the engineered ["Simple, Fast Dominance
 /// Algorithm"][0] discovered by Cooper et al.
@@ -155,7 +171,7 @@ const UNDEFINED: usize = ::std::usize::MAX;
 pub fn simple_fast<G>(graph: G, root: G::NodeId) -> Dominators<G::NodeId>
 where
     G: IntoNeighbors + Visitable,
-    <G as GraphBase>::NodeId: Eq + Hash,
+    <G as GraphBase>::NodeId: Eq + Hash + Ord,
 {
     let (post_order, predecessor_sets) = simple_fast_post_order(graph, root);
     let length = post_order.len();
@@ -223,7 +239,7 @@ where
     debug_assert!(!dominators.iter().any(|&dom| dom == UNDEFINED));
 
     Dominators {
-        root,
+        root: root,
         dominators: dominators
             .into_iter()
             .enumerate()
@@ -242,6 +258,7 @@ fn intersect(dominators: &[usize], mut finger1: usize, mut finger2: usize) -> us
     }
 }
 
+#[cfg(feature = "std")]
 fn predecessor_sets_to_idx_vecs<N>(
     post_order: &[N],
     node_to_post_order_idx: &HashMap<N, usize>,
@@ -266,6 +283,32 @@ where
         .collect()
 }
 
+#[cfg(feature = "alloc")]
+fn predecessor_sets_to_idx_vecs<N>(
+    post_order: &[N],
+    node_to_post_order_idx: &HashMap<N, usize>,
+    mut predecessor_sets: HashMap<N, HashSet<N>>,
+) -> Vec<Vec<usize>>
+where
+    N: Copy + Eq + Hash + Ord,
+{
+    post_order
+        .iter()
+        .map(|node| {
+            predecessor_sets
+                .remove(node)
+                .map(|predecessors| {
+                    predecessors
+                        .into_iter()
+                        .map(|p| *node_to_post_order_idx.get(&p).unwrap())
+                        .collect()
+                })
+                .unwrap_or_else(Vec::new)
+        })
+        .collect()
+}
+
+#[cfg(feature = "std")]
 fn simple_fast_post_order<G>(
     graph: G,
     root: G::NodeId,
@@ -291,7 +334,34 @@ where
     (post_order, predecessor_sets)
 }
 
+#[cfg(feature = "alloc")]
+fn simple_fast_post_order<G>(
+    graph: G,
+    root: G::NodeId,
+) -> (Vec<G::NodeId>, HashMap<G::NodeId, HashSet<G::NodeId>>)
+where
+    G: IntoNeighbors + Visitable,
+    <G as GraphBase>::NodeId: Eq + Hash + Ord,
+{
+    let mut post_order = vec![];
+    let mut predecessor_sets = HashMap::new();
+
+    for node in DfsPostOrder::new(graph, root).iter(graph) {
+        post_order.push(node);
+
+        for successor in graph.neighbors(node) {
+            predecessor_sets
+                .entry(successor)
+                .or_insert_with(HashSet::new)
+                .insert(node);
+        }
+    }
+
+    (post_order, predecessor_sets)
+}
+
 #[cfg(test)]
+#[cfg(feature = "alloc")]
 mod tests {
     use super::*;
 

diff --git a/src/algo/mod.rs b/src/algo/mod.rs
@@ -6,8 +6,14 @@
 
 pub mod dominators;
 
-use std::cmp::min;
-use std::collections::{BinaryHeap, HashMap};
+#[cfg(feature = "std")]
+use std::{cmp::min, collections::{BinaryHeap, HashMap, VecDeque}, fmt::Debug, ops::Add};
+
+#[cfg(feature = "no_std")]
+use core::{cmp::min, fmt::Debug, ops::Add};
+
+#[cfg(feature = "alloc")]
+use alloc::{collections::{BinaryHeap, BTreeMap as HashMap}, vec::Vec, collections::vec_deque::VecDeque};
 
 use crate::prelude::*;
 
@@ -839,14 +845,14 @@ where
 pub fn is_bipartite_undirected<G, N, VM>(g: G, start: N) -> bool
 where
     G: GraphRef + Visitable<NodeId = N, Map = VM> + IntoNeighbors<NodeId = N>,
-    N: Copy + PartialEq + std::fmt::Debug,
+    N: Copy + PartialEq + Debug,
     VM: VisitMap<N>,
 {
     let mut red = g.visit_map();
     red.visit(start);
     let mut blue = g.visit_map();
 
-    let mut stack = ::std::collections::VecDeque::new();
+    let mut stack = VecDeque::new();
     stack.push_front(start);
 
     while let Some(node) = stack.pop_front() {
@@ -886,9 +892,6 @@ where
     true
 }
 
-use std::fmt::Debug;
-use std::ops::Add;
-
 /// Associated data that can be used for measures (such as length).
 pub trait Measure: Debug + PartialOrd + Add<Self, Output = Self> + Default + Clone {}