Merge pull request #215 from sbstp/dot-escape
Support more escape codes inside labels
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/astar.rs b/src/astar.rs
index 565953d..794f1c0 100644
--- a/src/astar.rs
+++ b/src/astar.rs
@@ -157,13 +157,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/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..4e8a57b 100644
--- a/src/visit/dfsvisit.rs
+++ b/src/visit/dfsvisit.rs
@@ -78,7 +78,7 @@
impl<E> ControlFlow for Result<(), E> {
fn continuing() -> Self { Ok(()) }
fn should_break(&self) -> bool {
- if let Err(_) = *self { true } else { false }
+ self.is_err()
}
}
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..cc17f82 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);
diff --git a/tests/graph.rs b/tests/graph.rs
index d16e176..04de259 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -1463,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() {
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();
