Merge pull request #213 from jrraymond/optimize-is_isomorphic
Optimize is isomorphic
diff --git a/.travis.yml b/.travis.yml
index ee1d3fd..3d19f3d 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -2,16 +2,10 @@
sudo: false
matrix:
include:
- - rust: 1.12.0
- before_script:
- # rand 0.4.2 requires rust 1.15, and rand-0.3.22 requires rand-0.4 :/
- # manually hacking the lockfile due to the limitations of cargo#2773
- - cargo generate-lockfile
- - sed -i -e 's/"rand 0.[34].[0-9]\+/"rand 0.3.20/' Cargo.lock
- - sed -i -e '/^name = "rand"/,/^$/s/version = "0.3.[0-9]\+"/version = "0.3.20"/' Cargo.lock
+ - rust: 1.15.0
env:
- ALL=' '
- - rust: 1.15.0
+ - rust: 1.25.0
env:
- ALL=' '
- rust: stable
diff --git a/Cargo.toml b/Cargo.toml
index 0e72c8c..04be09d 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,7 +1,7 @@
[package]
name = "petgraph"
-version = "0.4.11"
+version = "0.4.13"
license = "MIT/Apache-2.0"
authors = [
"bluss",
@@ -27,20 +27,20 @@
[dependencies]
fixedbitset = { version = "0.1.4" }
-quickcheck = { optional = true, version = "0.4", default-features = false }
-ordermap = { version = "0.3.0", optional = true }
+quickcheck = { optional = true, version = "0.7.1", default-features = false }
+indexmap = { version = "1.0.2", optional = true }
serde = { version = "1.0", optional = true }
serde_derive = { version = "1.0", optional = true }
[dev-dependencies]
-rand = "0.3"
+rand = "0.5.5"
odds = { version = "0.2.19" }
defmac = "0.1"
itertools = { version = "0.7.0", default-features = false }
[features]
default = ["graphmap", "stable_graph"]
-graphmap = ["ordermap"]
+graphmap = ["indexmap"]
serde-1 = ["serde", "serde_derive"]
stable_graph = []
diff --git a/README.rst b/README.rst
index 3ccd7ca..383a709 100644
--- a/README.rst
+++ b/README.rst
@@ -26,6 +26,17 @@
Recent Changes
--------------
+- 0.4.13
+
+ - Fix clippy warnings by @jonasbb
+ - Add docs for ``Csr`` by @ksadorf
+ - Fix conflict with new stable method ``find_map`` in new Rust
+
+- 0.4.12
+
+ - Newtype ``Time`` now also implements ``Hash``
+ - Documentation updates for ``Frozen``.
+
- 0.4.11
- Fix ``petgraph::graph::NodeReferences`` to be publically visible
@@ -187,7 +198,7 @@
- ``GraphMap`` can now have directed edges. ``GraphMap::new`` is now generic
in the edge type. ``DiGraphMap`` and ``UnGraphMap`` are new type aliases.
- Add type aliases ``DiGraph, UnGraph, StableDiGraph, StableUnGraph``
- - ``GraphMap`` is based on the ordermap crate. Deterministic iteration
+ - ``GraphMap`` is based on the indexmap crate. Deterministic iteration
order, faster iteration, no side tables needed to convert to ``Graph``.
- Improved docs for a lot of types and functions.
- Add graph visitor ``DfsPostOrder``
@@ -297,7 +308,7 @@
- Add Graph::capacity(), GraphMap::capacity()
- Fix bug in Graph::reverse()
- Graph and GraphMap have `quickcheck::Arbitrary` implementations,
- if optional feature `quickcheck` is enabled.
+ if optional feature `check` is enabled.
- 0.1.16
diff --git a/serialization-tests/Cargo.toml b/serialization-tests/Cargo.toml
index 8837c0d..063fd44 100644
--- a/serialization-tests/Cargo.toml
+++ b/serialization-tests/Cargo.toml
@@ -19,6 +19,6 @@
[dev-dependencies]
serde_json = "1.0"
-quickcheck = { version = "0.4", default-features = false }
-bincode = { version = "0.9" }
+quickcheck = { version = "0.7.1", default-features = false }
+bincode = "1.0.1"
defmac = "0.1"
diff --git a/serialization-tests/tests/serialization.rs b/serialization-tests/tests/serialization.rs
index 069304f..a82ff88 100644
--- a/serialization-tests/tests/serialization.rs
+++ b/serialization-tests/tests/serialization.rs
@@ -352,7 +352,7 @@
// bincode macros
-defmac!(encode ref g => bincode::serialize(g, bincode::Infinite).unwrap());
+defmac!(encode ref g => bincode::serialize(g).unwrap());
defmac!(decode ref data => bincode::deserialize(data).unwrap());
defmac!(recode ref g => decode!(encode!(g)));
diff --git a/src/algo/dominators.rs b/src/algo/dominators.rs
index 6d08f61..80380af 100644
--- a/src/algo/dominators.rs
+++ b/src/algo/dominators.rs
@@ -213,7 +213,7 @@
.map(|p| *node_to_post_order_idx.get(&p).unwrap())
.collect()
})
- .unwrap_or(vec![])
+ .unwrap_or_else(Vec::new)
})
.collect()
}
diff --git a/src/algo/mod.rs b/src/algo/mod.rs
index 4fc05c2..b64f536 100644
--- a/src/algo/mod.rs
+++ b/src/algo/mod.rs
@@ -35,6 +35,7 @@
IndexType,
};
use visit::{Data, NodeRef, IntoNodeReferences};
+use visit::Walker;
use data::{
Element,
};
@@ -49,6 +50,41 @@
/// [Generic] Return the number of connected components of the graph.
///
/// For a directed graph, this is the *weakly* connected components.
+/// # Example
+/// ```rust
+/// use petgraph::Graph;
+/// use petgraph::algo::connected_components;
+/// use petgraph::prelude::*;
+///
+/// let mut graph : Graph<(),(),Directed>= Graph::new();
+/// let a = graph.add_node(()); // node with no weight
+/// let b = graph.add_node(());
+/// let c = graph.add_node(());
+/// let d = graph.add_node(());
+/// let e = graph.add_node(());
+/// let f = graph.add_node(());
+/// let g = graph.add_node(());
+/// let h = graph.add_node(());
+///
+/// graph.extend_with_edges(&[
+/// (a, b),
+/// (b, c),
+/// (c, d),
+/// (d, a),
+/// (e, f),
+/// (f, g),
+/// (g, h),
+/// (h, e)
+/// ]);
+/// // a ----> b e ----> f
+/// // ^ | ^ |
+/// // | v | v
+/// // d <---- c h <---- g
+///
+/// assert_eq!(connected_components(&graph),2);
+/// graph.add_edge(b,e,());
+/// assert_eq!(connected_components(&graph),1);
+/// ```
pub fn connected_components<G>(g: G) -> usize
where G: NodeCompactIndexable + IntoEdgeReferences,
{
@@ -122,7 +158,7 @@
}
if !dfs.discovered.is_visited(&succ) {
dfs.stack.push(succ);
- }
+ }
}
} else {
dfs.stack.pop();
@@ -229,12 +265,7 @@
with_dfs(g, space, |dfs| {
dfs.reset(g);
dfs.move_to(from);
- while let Some(x) = dfs.next(g) {
- if x == to {
- return true;
- }
- }
- false
+ dfs.iter(g).any(|x| x == to)
})
}
@@ -321,7 +352,7 @@
#[derive(Debug)]
struct Data<'a, G>
- where G: NodeIndexable,
+ where G: NodeIndexable,
G::NodeId: 'a
{
index: usize,
@@ -330,7 +361,7 @@
sccs: &'a mut Vec<Vec<G::NodeId>>,
}
- fn scc_visit<G>(v: G::NodeId, g: G, data: &mut Data<G>)
+ fn scc_visit<G>(v: G::NodeId, g: G, data: &mut Data<G>)
where G: IntoNeighbors + NodeIndexable
{
macro_rules! node {
@@ -402,6 +433,82 @@
///
/// If `make_acyclic` is true, self-loops and multi edges are ignored, guaranteeing that
/// the output is acyclic.
+/// # Example
+/// ```rust
+/// use petgraph::Graph;
+/// use petgraph::algo::condensation;
+/// use petgraph::prelude::*;
+///
+/// let mut graph : Graph<(),(),Directed> = Graph::new();
+/// let a = graph.add_node(()); // node with no weight
+/// let b = graph.add_node(());
+/// let c = graph.add_node(());
+/// let d = graph.add_node(());
+/// let e = graph.add_node(());
+/// let f = graph.add_node(());
+/// let g = graph.add_node(());
+/// let h = graph.add_node(());
+///
+/// graph.extend_with_edges(&[
+/// (a, b),
+/// (b, c),
+/// (c, d),
+/// (d, a),
+/// (b, e),
+/// (e, f),
+/// (f, g),
+/// (g, h),
+/// (h, e)
+/// ]);
+///
+/// // a ----> b ----> e ----> f
+/// // ^ | ^ |
+/// // | v | v
+/// // d <---- c h <---- g
+///
+/// let condensed_graph = condensation(graph,false);
+/// let A = NodeIndex::new(0);
+/// let B = NodeIndex::new(1);
+/// assert_eq!(condensed_graph.node_count(), 2);
+/// assert_eq!(condensed_graph.edge_count(), 9);
+/// assert_eq!(condensed_graph.neighbors(A).collect::<Vec<_>>(), vec![A, A, A, A]);
+/// assert_eq!(condensed_graph.neighbors(B).collect::<Vec<_>>(), vec![A, B, B, B, B]);
+/// ```
+/// If `make_acyclic` is true, self-loops and multi edges are ignored:
+///
+/// ```rust
+/// # use petgraph::Graph;
+/// # use petgraph::algo::condensation;
+/// # use petgraph::prelude::*;
+/// #
+/// # let mut graph : Graph<(),(),Directed> = Graph::new();
+/// # let a = graph.add_node(()); // node with no weight
+/// # let b = graph.add_node(());
+/// # let c = graph.add_node(());
+/// # let d = graph.add_node(());
+/// # let e = graph.add_node(());
+/// # let f = graph.add_node(());
+/// # let g = graph.add_node(());
+/// # let h = graph.add_node(());
+/// #
+/// # graph.extend_with_edges(&[
+/// # (a, b),
+/// # (b, c),
+/// # (c, d),
+/// # (d, a),
+/// # (b, e),
+/// # (e, f),
+/// # (f, g),
+/// # (g, h),
+/// # (h, e)
+/// # ]);
+/// let acyclic_condensed_graph = condensation(graph, true);
+/// let A = NodeIndex::new(0);
+/// let B = NodeIndex::new(1);
+/// assert_eq!(acyclic_condensed_graph.node_count(), 2);
+/// assert_eq!(acyclic_condensed_graph.edge_count(), 1);
+/// assert_eq!(acyclic_condensed_graph.neighbors(B).collect::<Vec<_>>(), vec![A]);
+/// ```
pub fn condensation<N, E, Ty, Ix>(g: Graph<N, E, Ty, Ix>, make_acyclic: bool) -> Graph<Vec<N>, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
@@ -551,6 +658,60 @@
/// are indexed by the graph's node indices.
///
/// [bf]: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
+///
+/// # Example
+/// ```rust
+/// use petgraph::Graph;
+/// use petgraph::algo::bellman_ford;
+/// use petgraph::prelude::*;
+///
+/// let mut g = Graph::new();
+/// let a = g.add_node(()); // node with no weight
+/// let b = g.add_node(());
+/// let c = g.add_node(());
+/// let d = g.add_node(());
+/// let e = g.add_node(());
+/// let f = g.add_node(());
+/// g.extend_with_edges(&[
+/// (0, 1, 2.0),
+/// (0, 3, 4.0),
+/// (1, 2, 1.0),
+/// (1, 5, 7.0),
+/// (2, 4, 5.0),
+/// (4, 5, 1.0),
+/// (3, 4, 1.0),
+/// ]);
+///
+/// // Graph represented with the weight of each edge
+/// //
+/// // 2 1
+/// // a ----- b ----- c
+/// // | 4 | 7 |
+/// // d f | 5
+/// // | 1 | 1 |
+/// // \------ e ------/
+///
+/// let path = bellman_ford(&g, a);
+/// assert_eq!(path, Ok((vec![0.0 , 2.0, 3.0, 4.0, 5.0, 6.0],
+/// vec![None, Some(a),Some(b),Some(a), Some(d), Some(e)]
+/// ))
+/// );
+/// // Node f (indice 5) can be reach from a with a path costing 6.
+/// // Predecessor of f is Some(e) which predecessor is Some(d) which predecessor is Some(a).
+/// // Thus the path from a to f is a <-> d <-> e <-> f
+///
+/// let graph_with_neg_cycle = Graph::<(), f32, Undirected>::from_edges(&[
+/// (0, 1, -2.0),
+/// (0, 3, -4.0),
+/// (1, 2, -1.0),
+/// (1, 5, -25.0),
+/// (2, 4, -5.0),
+/// (4, 5, -25.0),
+/// (3, 4, -1.0),
+/// ]);
+///
+/// assert!(bellman_ford(&graph_with_neg_cycle, NodeIndex::new(0)).is_err());
+/// ```
pub fn bellman_ford<G>(g: G, source: G::NodeId)
-> Result<(Vec<G::EdgeWeight>, Vec<Option<G::NodeId>>), NegativeCycle>
where G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable,
@@ -623,4 +784,3 @@
fn zero() -> Self { 0. }
fn infinite() -> Self { 1./0. }
}
-
diff --git a/src/astar.rs b/src/astar.rs
index 565953d..0ebd4fe 100644
--- a/src/astar.rs
+++ b/src/astar.rs
@@ -37,6 +37,7 @@
///
/// The graph should be `Visitable` and implement `IntoEdges`.
///
+/// # Example
/// ```
/// use petgraph::Graph;
/// use petgraph::algo::astar;
@@ -58,6 +59,16 @@
/// (d, e, 1),
/// ]);
///
+/// // Graph represented with the weight of each edge
+/// // Edges with '*' are part of the optimal path.
+/// //
+/// // 2 1
+/// // a ----- b ----- c
+/// // | 4* | 7 |
+/// // d f | 5
+/// // | 1* | 1* |
+/// // \------ e ------/
+///
/// let path = astar(&g, a, |finish| finish == f, |e| *e.weight(), |_| 0);
/// assert_eq!(path, Some((6, vec![a, d, e, f])));
/// ```
@@ -157,13 +168,9 @@
let mut path = vec![last];
let mut current = last;
- loop {
- if let Some(&previous) = self.came_from.get(¤t) {
- path.push(previous);
- current = previous;
- } else {
- break
- }
+ while let Some(&previous) = self.came_from.get(¤t) {
+ path.push(previous);
+ current = previous;
}
path.reverse();
diff --git a/src/csr.rs b/src/csr.rs
index 1a237bb..1ce87cc 100644
--- a/src/csr.rs
+++ b/src/csr.rs
@@ -341,7 +341,7 @@
fn neighbors_range(&self, a: NodeIndex<Ix>) -> Range<usize> {
let index = self.row[a.index()];
- let end = self.row.get(a.index() + 1).cloned().unwrap_or(self.column.len());
+ let end = self.row.get(a.index() + 1).cloned().unwrap_or_else(|| self.column.len());
index..end
}
diff --git a/src/dijkstra.rs b/src/dijkstra.rs
index fe9c401..e7b6feb 100644
--- a/src/dijkstra.rs
+++ b/src/dijkstra.rs
@@ -31,6 +31,55 @@
/// cost is calculated.
///
/// Returns a `HashMap` that maps `NodeId` to path cost.
+/// # Example
+/// ```rust
+/// use petgraph::Graph;
+/// use petgraph::algo::dijkstra;
+/// use petgraph::prelude::*;
+/// use std::collections::HashMap;
+///
+/// let mut graph : Graph<(),(),Directed>= Graph::new();
+/// let a = graph.add_node(()); // node with no weight
+/// let b = graph.add_node(());
+/// let c = graph.add_node(());
+/// let d = graph.add_node(());
+/// let e = graph.add_node(());
+/// let f = graph.add_node(());
+/// let g = graph.add_node(());
+/// let h = graph.add_node(());
+/// // z will be in another connected component
+/// let z = graph.add_node(());
+///
+/// graph.extend_with_edges(&[
+/// (a, b),
+/// (b, c),
+/// (c, d),
+/// (d, a),
+/// (e, f),
+/// (b, e),
+/// (f, g),
+/// (g, h),
+/// (h, e)
+/// ]);
+/// // a ----> b ----> e ----> f
+/// // ^ | ^ |
+/// // | v | v
+/// // d <---- c h <---- g
+///
+/// let expected_res: HashMap<NodeIndex, usize> = [
+/// (a, 3),
+/// (b, 0),
+/// (c, 1),
+/// (d, 2),
+/// (e, 1),
+/// (f, 2),
+/// (g, 3),
+/// (h, 4)
+/// ].iter().cloned().collect();
+/// let res = dijkstra(&graph,b,None, |_| 1);
+/// assert_eq!(res, expected_res);
+/// // z is not inside res because there is not path from b to z.
+/// ```
pub fn dijkstra<G, F, K>(graph: G, start: G::NodeId, goal: Option<G::NodeId>,
mut edge_cost: F)
-> HashMap<G::NodeId, K>
diff --git a/src/dot.rs b/src/dot.rs
index fbd78fb..09bf26b 100644
--- a/src/dot.rs
+++ b/src/dot.rs
@@ -29,7 +29,7 @@
/// println!("{:?}", Dot::with_config(&graph, &[Config::EdgeNoLabel]));
///
/// // In this case the output looks like this:
-/// //
+/// //
/// // digraph {
/// // 0 [label="\"A\""]
/// // 1 [label="\"B\""]
@@ -171,10 +171,10 @@
fn write_char(&mut self, c: char) -> fmt::Result {
match c {
- '"' => try!(self.0.write_char('\\')),
+ '"' | '\\' => try!(self.0.write_char('\\')),
// \l is for left justified linebreak
- '\n' => return self.0.write_str(r#"\l"#),
- _ => { }
+ '\n' => return self.0.write_str("\\l"),
+ _ => {}
}
self.0.write_char(c)
}
@@ -188,7 +188,7 @@
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if f.alternate() {
- write!(&mut Escaper(f), "{:#}\\l", &self.0)
+ write!(&mut Escaper(f), "{:#}\n", &self.0)
} else {
write!(&mut Escaper(f), "{}", &self.0)
}
@@ -205,3 +205,13 @@
self.0.fmt(f)
}
}
+
+#[test]
+fn test_escape() {
+ let mut buff = String::new();
+ {
+ let mut e = Escaper(&mut buff);
+ let _ = e.write_str("\" \\ \n");
+ }
+ assert_eq!(buff, "\\\" \\\\ \\l");
+}
diff --git a/src/graph_impl/stable_graph/mod.rs b/src/graph_impl/stable_graph/mod.rs
index fda91c1..20582a5 100644
--- a/src/graph_impl/stable_graph/mod.rs
+++ b/src/graph_impl/stable_graph/mod.rs
@@ -685,6 +685,22 @@
}
}
+ /// Return an iterator over either the nodes without edges to them
+ /// (`Incoming`) or from them (`Outgoing`).
+ ///
+ /// An *internal* node has both incoming and outgoing edges.
+ /// The nodes in `.externals(Incoming)` are the source nodes and
+ /// `.externals(Outgoing)` are the sinks of the graph.
+ ///
+ /// For a graph with undirected edges, both the sinks and the sources are
+ /// just the nodes without edges.
+ ///
+ /// The whole iteration computes in **O(|V|)** time.
+ pub fn externals(&self, dir: Direction) -> Externals<N, Ty, Ix>
+ {
+ Externals { iter: self.raw_nodes().iter().enumerate(), dir: dir, ty: PhantomData }
+ }
+
/// Index the `StableGraph` by two indices, any combination of
/// node or edge indices is fine.
///
@@ -1168,7 +1184,7 @@
type Item = (NodeIndex<Ix>, &'a N);
fn next(&mut self) -> Option<Self::Item> {
- self.iter.find_map(|(i, node)| {
+ self.iter.ex_find_map(|(i, node)| {
node.weight.as_ref().map(move |w| (node_index(i), w))
})
}
@@ -1183,7 +1199,7 @@
where Ix: IndexType
{
fn next_back(&mut self) -> Option<Self::Item> {
- self.iter.rfind_map(|(i, node)| {
+ self.iter.ex_rfind_map(|(i, node)| {
node.weight.as_ref().map(move |w| (node_index(i), w))
})
}
@@ -1360,7 +1376,7 @@
type Item = EdgeReference<'a, E, Ix>;
fn next(&mut self) -> Option<Self::Item> {
- self.iter.find_map(|(i, edge)|
+ self.iter.ex_find_map(|(i, edge)|
edge.weight.as_ref().map(move |weight| {
EdgeReference {
index: edge_index(i),
@@ -1375,7 +1391,7 @@
where Ix: IndexType
{
fn next_back(&mut self) -> Option<Self::Item> {
- self.iter.rfind_map(|(i, edge)|
+ self.iter.ex_rfind_map(|(i, edge)|
edge.weight.as_ref().map(move |weight| {
EdgeReference {
index: edge_index(i),
@@ -1386,6 +1402,38 @@
}
}
+/// An iterator over either the nodes without edges to them or from them.
+pub struct Externals<'a, N: 'a, Ty, Ix: IndexType = DefaultIx> {
+ iter: iter::Enumerate<slice::Iter<'a, Node<Option<N>, Ix>>>,
+ dir: Direction,
+ ty: PhantomData<Ty>,
+}
+
+impl<'a, N: 'a, Ty, Ix> Iterator for Externals<'a, N, Ty, Ix> where
+ Ty: EdgeType,
+ Ix: IndexType,
+{
+ type Item = NodeIndex<Ix>;
+ fn next(&mut self) -> Option<NodeIndex<Ix>>
+ {
+ let k = self.dir.index();
+ loop {
+ match self.iter.next() {
+ None => return None,
+ Some((index, node)) => {
+ if node.weight.is_some() &&
+ node.next[k] == EdgeIndex::end() &&
+ (Ty::is_directed() ||
+ node.next[1-k] == EdgeIndex::end()) {
+ return Some(NodeIndex::new(index))
+ } else {
+ continue
+ }
+ },
+ }
+ }
+ }
+}
/// Iterator over the neighbors of a node.
///
@@ -1524,7 +1572,7 @@
type Item = NodeIndex<Ix>;
fn next(&mut self) -> Option<Self::Item> {
- self.iter.find_map(|(i, node)| {
+ self.iter.ex_find_map(|(i, node)| {
if node.weight.is_some() {
Some(node_index(i))
} else { None }
@@ -1539,7 +1587,7 @@
impl<'a, N, Ix: IndexType> DoubleEndedIterator for NodeIndices<'a, N, Ix> {
fn next_back(&mut self) -> Option<Self::Item> {
- self.iter.rfind_map(|(i, node)| {
+ self.iter.ex_rfind_map(|(i, node)| {
if node.weight.is_some() {
Some(node_index(i))
} else { None }
@@ -1570,7 +1618,7 @@
type Item = EdgeIndex<Ix>;
fn next(&mut self) -> Option<Self::Item> {
- self.iter.find_map(|(i, node)| {
+ self.iter.ex_find_map(|(i, node)| {
if node.weight.is_some() {
Some(edge_index(i))
} else { None }
@@ -1585,7 +1633,7 @@
impl<'a, E, Ix: IndexType> DoubleEndedIterator for EdgeIndices<'a, E, Ix> {
fn next_back(&mut self) -> Option<Self::Item> {
- self.iter.rfind_map(|(i, node)| {
+ self.iter.ex_rfind_map(|(i, node)| {
if node.weight.is_some() {
Some(edge_index(i))
} else { None }
diff --git a/src/graphmap.rs b/src/graphmap.rs
index 945abe0..6b6cab4 100644
--- a/src/graphmap.rs
+++ b/src/graphmap.rs
@@ -14,11 +14,11 @@
use std::ops::{Index, IndexMut, Deref};
use std::iter::FromIterator;
use std::marker::PhantomData;
-use ordermap::OrderMap;
-use ordermap::{
- Iter as OrderMapIter, IterMut as OrderMapIterMut
+use indexmap::IndexMap;
+use indexmap::map::{
+ Iter as IndexMapIter, IterMut as IndexMapIterMut
};
-use ordermap::Keys;
+use indexmap::map::Keys;
use {
EdgeType,
@@ -72,8 +72,8 @@
/// Depends on crate feature `graphmap` (default).
#[derive(Clone)]
pub struct GraphMap<N, E, Ty> {
- nodes: OrderMap<N, Vec<(N, CompactDirection)>>,
- edges: OrderMap<(N, N), E>,
+ nodes: IndexMap<N, Vec<(N, CompactDirection)>>,
+ edges: IndexMap<(N, N), E>,
ty: PhantomData<Ty>,
}
@@ -121,8 +121,8 @@
/// Create a new `GraphMap` with estimated capacity.
pub fn with_capacity(nodes: usize, edges: usize) -> Self {
GraphMap {
- nodes: OrderMap::with_capacity(nodes),
- edges: OrderMap::with_capacity(edges),
+ nodes: IndexMap::with_capacity(nodes),
+ edges: IndexMap::with_capacity(edges),
ty: PhantomData,
}
}
@@ -559,7 +559,7 @@
Ty: EdgeType
{
from: N,
- edges: &'a OrderMap<(N, N), E>,
+ edges: &'a IndexMap<(N, N), E>,
iter: Neighbors<'a, N, Ty>,
}
@@ -596,7 +596,7 @@
}
pub struct AllEdges<'a, N, E: 'a, Ty> where N: 'a + NodeTrait {
- inner: OrderMapIter<'a, (N, N), E>,
+ inner: IndexMapIter<'a, (N, N), E>,
ty: PhantomData<Ty>,
}
@@ -640,7 +640,7 @@
}
pub struct AllEdgesMut<'a, N, E: 'a, Ty> where N: 'a + NodeTrait {
- inner: OrderMapIterMut<'a, (N, N), E>,
+ inner: IndexMapIterMut<'a, (N, N), E>,
ty: PhantomData<Ty>,
}
@@ -815,7 +815,7 @@
}
pub struct NodeIdentifiers<'a, N, E: 'a, Ty> where N: 'a + NodeTrait {
- iter: OrderMapIter<'a, N, Vec<(N, CompactDirection)>>,
+ iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
ty: PhantomData<Ty>,
edge_ty: PhantomData<E>,
}
@@ -847,7 +847,7 @@
}
pub struct NodeReferences<'a, N, E: 'a, Ty> where N: 'a + NodeTrait {
- iter: OrderMapIter<'a, N, Vec<(N, CompactDirection)>>,
+ iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
ty: PhantomData<Ty>,
edge_ty: PhantomData<E>,
}
diff --git a/src/iter_utils.rs b/src/iter_utils.rs
index 62a0183..30db2d5 100644
--- a/src/iter_utils.rs
+++ b/src/iter_utils.rs
@@ -2,10 +2,10 @@
pub trait IterUtilsExt : Iterator {
/// Return the first element that maps to `Some(_)`, or None if the iterator
/// was exhausted.
- fn find_map<F, R>(&mut self, mut f: F) -> Option<R>
+ fn ex_find_map<F, R>(&mut self, mut f: F) -> Option<R>
where F: FnMut(Self::Item) -> Option<R>
{
- while let Some(elt) = self.next() {
+ for elt in self {
if let result @ Some(_) = f(elt) {
return result;
}
@@ -15,7 +15,7 @@
/// Return the last element from the back that maps to `Some(_)`, or
/// None if the iterator was exhausted.
- fn rfind_map<F, R>(&mut self, mut f: F) -> Option<R>
+ fn ex_rfind_map<F, R>(&mut self, mut f: F) -> Option<R>
where F: FnMut(Self::Item) -> Option<R>,
Self: DoubleEndedIterator,
{
diff --git a/src/lib.rs b/src/lib.rs
index 6523894..7554774 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -19,7 +19,7 @@
extern crate fixedbitset;
#[cfg(feature = "graphmap")]
-extern crate ordermap;
+extern crate indexmap;
#[cfg(feature = "serde-1")]
extern crate serde;
diff --git a/src/quickcheck.rs b/src/quickcheck.rs
index 18d40c7..bda1594 100644
--- a/src/quickcheck.rs
+++ b/src/quickcheck.rs
@@ -1,5 +1,4 @@
extern crate quickcheck;
-
use self::quickcheck::{Gen, Arbitrary};
use {
@@ -20,6 +19,15 @@
};
use visit::NodeIndexable;
+/// Return a random float in the range [0, 1.)
+fn random_01<G: Gen>(g: &mut G) -> f64 {
+ // from rand
+ let bits = 53;
+ let scale = 1. / ((1u64 << bits) as f64);
+ let x = g.next_u64();
+ (x >> (64 - bits)) as f64 * scale
+}
+
/// `Arbitrary` for `Graph` creates a graph by selecting a node count
/// and a probability for each possible edge to exist.
///
@@ -41,7 +49,7 @@
return Graph::with_capacity(0, 0);
}
// use X² for edge probability (bias towards lower)
- let edge_prob = g.gen_range(0., 1.) * g.gen_range(0., 1.);
+ let edge_prob = random_01(g) * random_01(g);
let edges = ((nodes as f64).powi(2) * edge_prob) as usize;
let mut gr = Graph::with_capacity(nodes, edges);
for _ in 0..nodes {
@@ -52,7 +60,7 @@
if !gr.is_directed() && i > j {
continue;
}
- let p: f64 = g.gen();
+ let p: f64 = random_01(g);
if p <= edge_prob {
gr.add_edge(i, j, E::arbitrary(g));
}
@@ -107,7 +115,7 @@
return StableGraph::with_capacity(0, 0);
}
// use X² for edge probability (bias towards lower)
- let edge_prob = g.gen_range(0., 1.) * g.gen_range(0., 1.);
+ let edge_prob = random_01(g) * random_01(g);
let edges = ((nodes as f64).powi(2) * edge_prob) as usize;
let mut gr = StableGraph::with_capacity(nodes, edges);
for _ in 0..nodes {
@@ -120,7 +128,7 @@
if !gr.is_directed() && i > j {
continue;
}
- let p: f64 = g.gen();
+ let p: f64 = random_01(g);
if p <= edge_prob {
gr.add_edge(i, j, E::arbitrary(g));
}
@@ -188,7 +196,7 @@
nodes.dedup();
// use X² for edge probability (bias towards lower)
- let edge_prob = g.gen_range(0., 1.) * g.gen_range(0., 1.);
+ let edge_prob = random_01(g) * random_01(g);
let edges = ((nodes.len() as f64).powi(2) * edge_prob) as usize;
let mut gr = GraphMap::with_capacity(nodes.len(), edges);
for &node in &nodes {
@@ -197,7 +205,7 @@
for (index, &i) in nodes.iter().enumerate() {
let js = if Ty::is_directed() { &nodes[..] } else { &nodes[index..] };
for &j in js {
- let p: f64 = g.gen();
+ let p: f64 = random_01(g);
if p <= edge_prob {
gr.add_edge(i, j, E::arbitrary(g));
}
diff --git a/src/visit/dfsvisit.rs b/src/visit/dfsvisit.rs
index 91ea1b2..e0ba22e 100644
--- a/src/visit/dfsvisit.rs
+++ b/src/visit/dfsvisit.rs
@@ -20,26 +20,35 @@
/// For an edge *(u, v)*, if the discover time of *v* is greater than *u*,
/// then it is a forward edge, else a cross edge.
CrossForwardEdge(N, N),
+ /// All edges from a node have been reported.
Finish(N, Time),
}
-/// Return if the expression is a break value.
+/// Return if the expression is a break value, execute the provided statement
+/// if it is a prune value.
macro_rules! try_control {
- ($e:expr) => {
+ ($e:expr, $p:stmt) => {
match $e {
x => if x.should_break() {
return x;
+ } else if x.should_prune() {
+ $p;
}
}
}
}
-/// Control flow for callbacks.
-///
-/// `Break` can carry a value.
+/// Control flow for `depth_first_search` callbacks.
#[derive(Copy, Clone, Debug)]
pub enum Control<B> {
+ /// Continue the DFS traversal as normal.
Continue,
+ /// Prune the current node from the DFS traversal. No more edges from this
+ /// node will be reported to the callback. A `DfsEvent::Finish` for this
+ /// node will still be reported. This can be returned in response to any
+ /// `DfsEvent`, except `Finish`, which will panic.
+ Prune,
+ /// Stop the DFS traversal and return the provided value.
Break(B),
}
@@ -48,7 +57,7 @@
/// Get the value in `Control::Break(_)`, if present.
pub fn break_value(self) -> Option<B> {
match self {
- Control::Continue => None,
+ Control::Continue | Control::Prune => None,
Control::Break(b) => Some(b),
}
}
@@ -60,12 +69,15 @@
pub trait ControlFlow {
fn continuing() -> Self;
fn should_break(&self) -> bool;
+ fn should_prune(&self) -> bool;
}
impl ControlFlow for () {
fn continuing() { }
#[inline]
fn should_break(&self) -> bool { false }
+ #[inline]
+ fn should_prune(&self) -> bool { false }
}
impl<B> ControlFlow for Control<B> {
@@ -73,12 +85,21 @@
fn should_break(&self) -> bool {
if let Control::Break(_) = *self { true } else { false }
}
+ fn should_prune(&self) -> bool {
+ match *self {
+ Control::Prune => true,
+ Control::Continue | Control::Break(_) => false,
+ }
+ }
}
-impl<E> ControlFlow for Result<(), E> {
- fn continuing() -> Self { Ok(()) }
+impl<C: ControlFlow, E> ControlFlow for Result<C, E> {
+ fn continuing() -> Self { Ok(C::continuing()) }
fn should_break(&self) -> bool {
- if let Err(_) = *self { true } else { false }
+ if let Ok(ref c) = *self { c.should_break() } else { true }
+ }
+ fn should_prune(&self) -> bool {
+ if let Ok(ref c) = *self { c.should_prune() } else { false }
}
}
@@ -98,8 +119,12 @@
///
/// If the return value of the visitor is simply `()`, the visit runs until it
/// is finished. If the return value is a `Control<B>`, it can be used to
-/// break the visit early, and the last control value is returned by the
-/// function.
+/// change the control flow of the search. `Control::Break` will stop the
+/// the visit early, returning the contained value from the function.
+/// `Control::Prune` will stop traversing any additional edges from the current
+/// node and proceed immediately to the `Finish` event.
+///
+/// ***Panics** if you attempt to prune a node from its `Finish` event.
///
/// [de]: enum.DfsEvent.html
///
@@ -156,7 +181,8 @@
let finished = &mut graph.visit_map();
for start in starts {
- try_control!(dfs_visitor(graph, start, &mut visitor, discovered, finished, time));
+ try_control!(dfs_visitor(graph, start, &mut visitor, discovered, finished, time),
+ unreachable!());
}
C::continuing()
}
@@ -171,20 +197,27 @@
if !discovered.visit(u) {
return C::continuing();
}
- try_control!(visitor(DfsEvent::Discover(u, time_post_inc(time))));
- for v in graph.neighbors(u) {
- if !discovered.is_visited(&v) {
- try_control!(visitor(DfsEvent::TreeEdge(u, v)));
- try_control!(dfs_visitor(graph, v, visitor, discovered, finished, time));
- } else if !finished.is_visited(&v) {
- try_control!(visitor(DfsEvent::BackEdge(u, v)));
- } else {
- try_control!(visitor(DfsEvent::CrossForwardEdge(u, v)));
+
+ 'prune: loop {
+ try_control!(visitor(DfsEvent::Discover(u, time_post_inc(time))), break 'prune);
+ for v in graph.neighbors(u) {
+ if !discovered.is_visited(&v) {
+ try_control!(visitor(DfsEvent::TreeEdge(u, v)), continue);
+ try_control!(dfs_visitor(graph, v, visitor, discovered, finished, time),
+ unreachable!());
+ } else if !finished.is_visited(&v) {
+ try_control!(visitor(DfsEvent::BackEdge(u, v)), continue);
+ } else {
+ try_control!(visitor(DfsEvent::CrossForwardEdge(u, v)), continue);
+ }
}
+
+ break;
}
let first_finish = finished.visit(u);
debug_assert!(first_finish);
- try_control!(visitor(DfsEvent::Finish(u, time_post_inc(time))));
+ try_control!(visitor(DfsEvent::Finish(u, time_post_inc(time))),
+ panic!("Pruning on the `DfsEvent::Finish` is not supported!"));
C::continuing()
}
diff --git a/src/visit/filter.rs b/src/visit/filter.rs
index 07b3ae9..cb64c79 100644
--- a/src/visit/filter.rs
+++ b/src/visit/filter.rs
@@ -10,6 +10,7 @@
GraphProp,
IntoEdgeReferences,
IntoEdges,
+ IntoEdgesDirected,
IntoNeighbors,
IntoNeighborsDirected,
IntoNodeIdentifiers,
@@ -337,6 +338,21 @@
}
}
+impl<'a, G, F> IntoNeighborsDirected for &'a EdgeFiltered<G, F>
+where
+ G: IntoEdgesDirected,
+ F: FilterEdge<G::EdgeRef>,
+{
+ type NeighborsDirected = EdgeFilteredNeighborsDirected<'a, G, F>;
+ fn neighbors_directed(self, n: G::NodeId, dir: Direction) -> Self::NeighborsDirected {
+ EdgeFilteredNeighborsDirected {
+ iter: self.0.edges_directed(n, dir),
+ f: &self.1,
+ from: n,
+ }
+ }
+}
+
/// A filtered neighbors iterator.
pub struct EdgeFilteredNeighbors<'a, G, F: 'a>
where G: IntoEdges,
@@ -409,6 +425,41 @@
}
}
+/// A filtered neighbors-directed iterator.
+pub struct EdgeFilteredNeighborsDirected<'a, G, F: 'a>
+where
+ G: IntoEdgesDirected,
+{
+ iter: G::EdgesDirected,
+ f: &'a F,
+ from: G::NodeId,
+}
+
+impl<'a, G, F> Iterator for EdgeFilteredNeighborsDirected<'a, G, F>
+where
+ F: FilterEdge<G::EdgeRef>,
+ G: IntoEdgesDirected,
+{
+ type Item = G::NodeId;
+ fn next(&mut self) -> Option<Self::Item> {
+ let f = self.f;
+ let from = self.from;
+ (&mut self.iter)
+ .filter_map(move |edge| {
+ if f.include_edge(edge) {
+ if edge.source() != from {
+ Some(edge.source())
+ } else {
+ Some(edge.target()) // includes case where from == source == target
+ }
+ } else {
+ None
+ }
+ })
+ .next()
+ }
+}
+
Data!{delegate_impl [[G, F], G, EdgeFiltered<G, F>, access0]}
GraphProp!{delegate_impl [[G, F], G, EdgeFiltered<G, F>, access0]}
IntoNodeIdentifiers!{delegate_impl [['a, G, F], G, &'a EdgeFiltered<G, F>, access0]}
diff --git a/src/visit/traversal.rs b/src/visit/traversal.rs
index 9aa6f93..d48d083 100644
--- a/src/visit/traversal.rs
+++ b/src/visit/traversal.rs
@@ -95,7 +95,7 @@
pub fn next<G>(&mut self, graph: G) -> Option<N>
where G: IntoNeighbors<NodeId=N>,
{
- while let Some(node) = self.stack.pop() {
+ if let Some(node) = self.stack.pop() {
for succ in graph.neighbors(node) {
if self.discovered.visit(succ) {
self.stack.push(succ);
@@ -251,7 +251,7 @@
pub fn next<G>(&mut self, graph: G) -> Option<N>
where G: IntoNeighbors<NodeId=N>
{
- while let Some(node) = self.stack.pop_front() {
+ if let Some(node) = self.stack.pop_front() {
for succ in graph.neighbors(node) {
if self.discovered.visit(succ) {
self.stack.push_back(succ);
@@ -403,6 +403,15 @@
}
}
+impl<'a, C, W: ?Sized> Walker<C> for &'a mut W
+ where W: Walker<C>,
+{
+ type Item = W::Item;
+ fn walk_next(&mut self, context: C) -> Option<Self::Item> {
+ (**self).walk_next(context)
+ }
+}
+
impl<G> Walker<G> for Dfs<G::NodeId, G::Map>
where G: IntoNeighbors + Visitable
{
diff --git a/tests/graph.rs b/tests/graph.rs
index 773a993..78a49ea 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -1420,12 +1420,13 @@
b: &'static str,
};
let mut gr = Graph::new();
- let a = gr.add_node(Record { a: 1, b: "abc" });
+ let a = gr.add_node(Record { a: 1, b: r"abc\" });
gr.add_edge(a, a, (1, 2));
let dot_output = format!("{:#?}", Dot::new(&gr));
assert_eq!(dot_output,
+ // The single \ turns into four \\\\ because of Debug which turns it to \\ and then escaping each \ to \\.
r#"digraph {
- 0 [label="Record {\l a: 1,\l b: \"abc\"\l}\l"]
+ 0 [label="Record {\l a: 1,\l b: \"abc\\\\\"\l}\l"]
0 -> 0 [label="(\l 1,\l 2\l)\l"]
}
"#);
@@ -1462,7 +1463,145 @@
assert_eq!(set(po), set(g.node_identifiers().filter(|n| (filt.1)(*n))));
}
+#[test]
+fn filtered_edge_reverse() {
+ use petgraph::visit::EdgeFiltered;
+ #[derive(Eq, PartialEq)]
+ enum E {
+ A,
+ B,
+ }
+ // Start with single node graph with loop
+ let mut g = Graph::new();
+ let a = g.add_node("A");
+ g.add_edge(a, a, E::A);
+ let ef_a = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::A);
+ let mut po = Vec::new();
+ let mut dfs = Dfs::new(&ef_a, a);
+ while let Some(next_n_ix) = dfs.next(&ef_a) {
+ po.push(next_n_ix);
+ }
+ assert_eq!(set(po), set(vec![a]));
+
+ // Check in reverse
+ let mut po = Vec::new();
+ let mut dfs = Dfs::new(&Reversed(&ef_a), a);
+ while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
+ po.push(next_n_ix);
+ }
+ assert_eq!(set(po), set(vec![a]));
+
+
+ let mut g = Graph::new();
+ let a = g.add_node("A");
+ let b = g.add_node("B");
+ let c = g.add_node("C");
+ let d = g.add_node("D");
+ let e = g.add_node("E");
+ let f = g.add_node("F");
+ let h = g.add_node("H");
+ let i = g.add_node("I");
+ let j = g.add_node("J");
+
+ g.add_edge(a, b, E::A);
+ g.add_edge(b, c, E::A);
+ g.add_edge(c, d, E::B);
+ g.add_edge(d, e, E::A);
+ g.add_edge(e, f, E::A);
+ g.add_edge(e, h, E::A);
+ g.add_edge(e, i, E::A);
+ g.add_edge(i, j, E::A);
+
+ let ef_a = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::A);
+ let ef_b = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::B);
+
+ // DFS down from a, filtered by E::A.
+ let mut po = Vec::new();
+ let mut dfs = Dfs::new(&ef_a, a);
+ while let Some(next_n_ix) = dfs.next(&ef_a) {
+ po.push(next_n_ix);
+ }
+ assert_eq!(set(po), set(vec![a, b, c]));
+
+ // Reversed DFS from f, filtered by E::A.
+ let mut dfs = Dfs::new(&Reversed(&ef_a), f);
+ let mut po = Vec::new();
+ while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
+ po.push(next_n_ix);
+ }
+ assert_eq!(set(po), set(vec![d, e, f]));
+
+ // Reversed DFS from j, filtered by E::A.
+ let mut dfs = Dfs::new(&Reversed(&ef_a), j);
+ let mut po = Vec::new();
+ while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
+ po.push(next_n_ix);
+ }
+ assert_eq!(set(po), set(vec![d, e, i, j]));
+
+ // Reversed DFS from c, filtered by E::A.
+ let mut dfs = Dfs::new(&Reversed(&ef_a), c);
+ let mut po = Vec::new();
+ while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
+ po.push(next_n_ix);
+ }
+ assert_eq!(set(po), set(vec![a, b, c]));
+
+ // Reversed DFS from c, filtered by E::B.
+ let mut dfs = Dfs::new(&Reversed(&ef_b), c);
+ let mut po = Vec::new();
+ while let Some(next_n_ix) = dfs.next(&Reversed(&ef_b)) {
+ po.push(next_n_ix);
+ }
+ assert_eq!(set(po), set(vec![c]));
+
+ // Reversed DFS from d, filtered by E::B.
+ let mut dfs = Dfs::new(&Reversed(&ef_b), d);
+ let mut po = Vec::new();
+ while let Some(next_n_ix) = dfs.next(&Reversed(&ef_b)) {
+ po.push(next_n_ix);
+ }
+ assert_eq!(set(po), set(vec![c, d]));
+
+ // Now let's test the same graph but undirected
+
+ let mut g = Graph::new_undirected();
+ let a = g.add_node("A");
+ let b = g.add_node("B");
+ let c = g.add_node("C");
+ let d = g.add_node("D");
+ let e = g.add_node("E");
+ let f = g.add_node("F");
+ let h = g.add_node("H");
+ let i = g.add_node("I");
+ let j = g.add_node("J");
+
+ g.add_edge(a, b, E::A);
+ g.add_edge(b, c, E::A);
+ g.add_edge(c, d, E::B);
+ g.add_edge(d, e, E::A);
+ g.add_edge(e, f, E::A);
+ g.add_edge(e, h, E::A);
+ g.add_edge(e, i, E::A);
+ g.add_edge(i, j, E::A);
+
+ let ef_a = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::A);
+ let ef_b = EdgeFiltered::from_fn(&g, |edge| *edge.weight() == E::B);
+ let mut po = Vec::new();
+ let mut dfs = Dfs::new(&Reversed(&ef_b), d);
+ while let Some(next_n_ix) = dfs.next(&Reversed(&ef_b)) {
+ po.push(next_n_ix);
+ }
+ assert_eq!(set(po), set(vec![c, d]));
+
+ let mut po = Vec::new();
+ let mut dfs = Dfs::new(&Reversed(&ef_a), h);
+ while let Some(next_n_ix) = dfs.next(&Reversed(&ef_a)) {
+ po.push(next_n_ix);
+ }
+ assert_eq!(set(po), set(vec![d, e, f, h, i, j]));
+}
#[test]
fn dfs_visit() {
@@ -1539,6 +1678,24 @@
}
path.reverse();
assert_eq!(&path, &[n(0), n(2), n(4)]);
+
+ // check that if we prune 2, we never see 4.
+ let start = n(0);
+ let prune = n(2);
+ let nongoal = n(4);
+ let ret = depth_first_search(&gr, Some(start), |event| {
+ if let Discover(n, _) = event {
+ if n == prune {
+ return Control::Prune;
+ }
+ } else if let TreeEdge(u, v) = event {
+ if v == nongoal {
+ return Control::Break(u);
+ }
+ }
+ Control::Continue
+ });
+ assert!(ret.break_value().is_none());
}
@@ -1711,7 +1868,7 @@
// http://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf.
let mut graph = DiGraph::<_, _>::new();
-
+
let r = graph.add_node("r");
let a = graph.add_node("a");
let b = graph.add_node("b");
diff --git a/tests/unionfind.rs b/tests/unionfind.rs
index f5e2bcf..ba3bdc5 100644
--- a/tests/unionfind.rs
+++ b/tests/unionfind.rs
@@ -1,7 +1,7 @@
extern crate rand;
extern crate petgraph;
-use rand::{Rng, thread_rng, ChaChaRng};
+use rand::{Rng, thread_rng, ChaChaRng, SeedableRng};
use std::collections::HashSet;
use petgraph::unionfind::UnionFind;
@@ -36,7 +36,7 @@
#[test]
fn uf_rand() {
let n = 1 << 14;
- let mut rng: ChaChaRng = thread_rng().gen();
+ let mut rng = ChaChaRng::from_rng(thread_rng()).unwrap();
let mut u = UnionFind::new(n);
for _ in 0..100 {
let a = rng.gen_range(0, n);
@@ -50,7 +50,7 @@
#[test]
fn uf_u8() {
let n = 256;
- let mut rng: ChaChaRng = thread_rng().gen();
+ let mut rng = ChaChaRng::from_rng(thread_rng()).unwrap();
let mut u = UnionFind::<u8>::new(n);
for _ in 0..(n * 8) {
let a = rng.gen();
