Merge pull request #286 from petgraph/graphmap-neighbors-directed
Include self loops in incoming edges
diff --git a/Cargo.toml b/Cargo.toml
index 4d559d2..c5f91a6 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -28,9 +28,9 @@
debug = true
[dependencies]
-fixedbitset = { version = "0.1.4" }
+fixedbitset = { version = "0.2.0", default-features = false }
quickcheck = { optional = true, version = "0.8", default-features = false }
-indexmap = { version = "1.0.2", optional = true }
+indexmap = { version = "1.0.2" }
serde = { version = "1.0", optional = true }
serde_derive = { version = "1.0", optional = true }
@@ -42,7 +42,7 @@
[features]
default = ["graphmap", "stable_graph", "matrix_graph"]
-graphmap = ["indexmap"]
+graphmap = []
serde-1 = ["serde", "serde_derive"]
stable_graph = []
matrix_graph = []
diff --git a/src/algo/dominators.rs b/src/algo/dominators.rs
index e6b22f4..5cbf281 100644
--- a/src/algo/dominators.rs
+++ b/src/algo/dominators.rs
@@ -46,7 +46,7 @@
}
}
- /// Iterate over the given node's that strict dominators.
+ /// Iterate over the given node's strict dominators.
///
/// If the given node is not reachable from the root, then `None` is
/// returned.
diff --git a/src/algo/mod.rs b/src/algo/mod.rs
index 2d3087f..d1771f9 100644
--- a/src/algo/mod.rs
+++ b/src/algo/mod.rs
@@ -46,6 +46,7 @@
};
pub use super::dijkstra::dijkstra;
pub use super::astar::astar;
+pub use super::simple_paths::all_simple_paths;
/// \[Generic\] Return the number of connected components of the graph.
///
diff --git a/src/graph_impl/mod.rs b/src/graph_impl/mod.rs
index 91eea58..1e8d1d6 100644
--- a/src/graph_impl/mod.rs
+++ b/src/graph_impl/mod.rs
@@ -262,6 +262,9 @@
/// - Edge type `Ty` that determines whether the graph edges are directed or undirected.
/// - Index type `Ix`, which determines the maximum size of the graph.
///
+/// The `Graph` is a regular Rust collection and is `Send` and `Sync` (as long
+/// as associated data `N` and `E` are).
+///
/// The graph uses **O(|V| + |E|)** space, and allows fast node and edge insert,
/// efficient graph search and graph algorithms.
/// It implements **O(e')** edge lookup and edge and node removals, where **e'**
@@ -296,17 +299,16 @@
/// example for *n* nodes indices are 0 to *n* - 1 inclusive.
///
/// `NodeIndex` and `EdgeIndex` are types that act as references to nodes and edges,
-/// but these are only stable across certain operations.
-/// **Adding nodes or edges keeps indices stable.
-/// Removing nodes or edges may shift other indices.**
-/// Removing a node will force the last node to shift its index to
-/// take its place. Similarly, removing an edge shifts the index of the last edge.
+/// but these are only stable across certain operations:
+///
+/// * **Removing nodes or edges may shift other indices.** Removing a node will
+/// force the last node to shift its index to take its place. Similarly,
+/// removing an edge shifts the index of the last edge.
+/// * Adding nodes or edges keeps indices stable.
///
/// The `Ix` parameter is `u32` by default. The goal is that you can ignore this parameter
/// completely unless you need a very big graph -- then you can use `usize`.
///
-/// ### Pros and Cons of Indices
-///
/// * The fact that the node and edge indices in the graph each are numbered in compact
/// intervals (from 0 to *n* - 1 for *n* nodes) simplifies some graph algorithms.
///
@@ -319,12 +321,7 @@
/// * You can create several graphs using the equal node indices but with
/// differing weights or differing edges.
///
-/// * The `Graph` is a regular rust collection and is `Send` and `Sync` (as long
-/// as associated data `N` and `E` are).
-///
-/// * Some indices shift during node or edge removal, so that is a drawback
-/// of removing elements. Indices don't allow as much compile time checking as
-/// references.
+/// * Indices don't allow as much compile time checking as references.
///
pub struct Graph<N, E, Ty = Directed, Ix = DefaultIx> {
nodes: Vec<Node<N, Ix>>,
@@ -854,6 +851,21 @@
}
}
+ /// Return an iterator over all the edges connecting `a` and `b`.
+ ///
+ /// - `Directed`: Outgoing edges from `a`.
+ /// - `Undirected`: All edges connected to `a`.
+ ///
+ /// Iterator element type is `EdgeReference<E, Ix>`.
+ pub fn edges_connecting(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> EdgesConnecting<E, Ty, Ix>
+ {
+ EdgesConnecting {
+ target_node: b,
+ edges: self.edges_directed(a, Direction::Outgoing),
+ ty: PhantomData,
+ }
+ }
+
/// Lookup if there is an edge from `a` to `b`.
///
/// Computes in **O(e')** time, where **e'** is the number of edges
@@ -1284,7 +1296,7 @@
weight: node_map(NodeIndex::new(i), &node.weight),
next: node.next,
}));
- g.edges.extend(enumerate(&self.edges).map(|(i, edge)|
+ g.edges.extend(enumerate(&self.edges).map(|(i, edge)|
Edge {
weight: edge_map(EdgeIndex::new(i), &edge.weight),
next: edge.next,
@@ -1603,6 +1615,34 @@
}
}
+/// Iterator over the multiple directed edges connecting a source node to a target node
+pub struct EdgesConnecting<'a, E: 'a, Ty, Ix: 'a = DefaultIx>
+ where Ty: EdgeType,
+ Ix: IndexType,
+{
+ target_node: NodeIndex<Ix>,
+ edges: Edges<'a, E, Ty, Ix>,
+ ty: PhantomData<Ty>,
+}
+
+impl<'a, E, Ty, Ix> Iterator for EdgesConnecting<'a, E, Ty, Ix>
+ where Ty: EdgeType,
+ Ix: IndexType,
+{
+ type Item = EdgeReference<'a, E, Ix>;
+
+ fn next(&mut self) -> Option<EdgeReference<'a, E, Ix>> {
+ while let Some(edge) = self.edges.next() {
+ if edge.node[1] == self.target_node {
+ return Some(edge);
+ }
+ }
+
+ None
+ }
+}
+
+
fn swap_pair<T>(mut x: [T; 2]) -> [T; 2] {
x.swap(0, 1);
x
@@ -1940,7 +1980,7 @@
type Item = (NodeIndex<Ix>, &'a N);
fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|(i, node)|
+ self.iter.next().map(|(i, node)|
(node_index(i), &node.weight)
)
}
@@ -1999,7 +2039,7 @@
type Item = EdgeReference<'a, E, Ix>;
fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|(i, edge)|
+ self.iter.next().map(|(i, edge)|
EdgeReference {
index: edge_index(i),
node: edge.node,
@@ -2047,4 +2087,3 @@
/// See indexing implementations and the traits `Data` and `DataMap`
/// for read-write access to the graph's weights.
pub struct Frozen<'a, G: 'a>(&'a mut G);
-
diff --git a/src/lib.rs b/src/lib.rs
index 4a76111..b8251a9 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -60,6 +60,7 @@
pub mod unionfind;
mod dijkstra;
mod astar;
+mod simple_paths;
pub mod csr;
mod iter_format;
mod iter_utils;
diff --git a/src/simple_paths.rs b/src/simple_paths.rs
new file mode 100644
index 0000000..7d698df
--- /dev/null
+++ b/src/simple_paths.rs
@@ -0,0 +1,163 @@
+use std::{
+ hash::Hash,
+ iter::{from_fn, FromIterator},
+};
+
+use indexmap::IndexSet;
+
+use crate::{
+ Direction::Outgoing,
+ visit::{
+ IntoNeighborsDirected,
+ NodeCount,
+ },
+};
+
+/// Returns iterator that produces all simple paths from `from` node to `to`, which contains at least `min_intermidiate_nodes` nodes
+/// and at most `max_intermidiate_nodes`, if given, limited by graph's order otherwise
+/// Simple path is path without repetitions
+/// Algorithm is adopted from https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html
+pub fn all_simple_paths<TargetColl, G>(graph: G,
+ from: G::NodeId,
+ to: G::NodeId,
+ min_intermidiate_nodes: usize,
+ max_intermidiate_nodes: Option<usize>) -> impl Iterator<Item=TargetColl>
+ where G: NodeCount,
+ G: IntoNeighborsDirected,
+ G::NodeId: Eq + Hash,
+ TargetColl: FromIterator<G::NodeId>
+{
+ // how many nodes are allowed in simple path up to target node
+ // it is min/max allowed path length minus one, because it is more appropriate when implementing lookahead
+ // than constantly add 1 to length of current path
+ let max_length = if let Some(l) = max_intermidiate_nodes {
+ l + 1
+ } else {
+ graph.node_count() - 1
+ };
+
+ let min_length = min_intermidiate_nodes + 1;
+
+ // list of visited nodes
+ let mut visited: IndexSet<G::NodeId> = IndexSet::from_iter(Some(from));
+ // list of childs of currently exploring path nodes,
+ // last elem is list of childs of last visited node
+ let mut stack = vec![graph.neighbors_directed(from, Outgoing)];
+
+ from_fn(move || {
+ while let Some(children) = stack.last_mut() {
+ if let Some(child) = children.next() {
+ if visited.len() < max_length {
+ if child == to {
+ if visited.len() >= min_length {
+ let path = visited.iter().cloned().chain(Some(to)).collect::<TargetColl>();
+ return Some(path);
+ }
+ } else if !visited.contains(&child) {
+ visited.insert(child);
+ stack.push(graph.neighbors_directed(child, Outgoing));
+ }
+ } else {
+ if (child == to || children.any(|v| v == to)) && visited.len() >= min_length {
+ let path = visited.iter().cloned().chain(Some(to)).collect::<TargetColl>();
+ return Some(path);
+ }
+ stack.pop();
+ visited.pop();
+ }
+ } else {
+ stack.pop();
+ visited.pop();
+ }
+ }
+ None
+ })
+}
+
+#[cfg(test)]
+mod test {
+ use std::{
+ collections::HashSet,
+ iter::FromIterator,
+ };
+
+ use itertools::assert_equal;
+
+ use crate::{
+ dot::Dot,
+ prelude::DiGraph,
+ };
+
+ use super::all_simple_paths;
+
+ #[test]
+ fn test_all_simple_paths() {
+ let graph = DiGraph::<i32, i32, _>::from_edges(&[
+ (0, 1),
+ (0, 2),
+ (0, 3),
+ (1, 2),
+ (1, 3),
+ (2, 3),
+ (2, 4),
+ (3, 2),
+ (3, 4),
+ (4, 2),
+ (4, 5),
+ (5, 2),
+ (5, 3)
+ ]);
+
+ let expexted_simple_paths_0_to_5 = vec![
+ vec![0usize, 1, 2, 3, 4, 5],
+ vec![0, 1, 2, 4, 5],
+ vec![0, 1, 3, 2, 4, 5],
+ vec![0, 1, 3, 4, 5],
+ vec![0, 2, 3, 4, 5],
+ vec![0, 2, 4, 5],
+ vec![0, 3, 2, 4, 5],
+ vec![0, 3, 4, 5],
+ ];
+
+ println!("{}", Dot::new(&graph));
+ let actual_simple_paths_0_to_5: HashSet<Vec<_>> = all_simple_paths(&graph, 0u32.into(), 5u32.into(), 0, None)
+ .map(|v: Vec<_>| v.into_iter().map(|i| i.index()).collect())
+ .collect();
+ assert_eq!(actual_simple_paths_0_to_5.len(), 8);
+ assert_eq!(HashSet::from_iter(expexted_simple_paths_0_to_5), actual_simple_paths_0_to_5);
+ }
+
+ #[test]
+ fn test_one_simple_path() {
+ let graph = DiGraph::<i32, i32, _>::from_edges(&[
+ (0, 1),
+ (2, 1)
+ ]);
+
+ let expexted_simple_paths_0_to_1 = &[
+ vec![0usize, 1],
+ ];
+ println!("{}", Dot::new(&graph));
+ let actual_simple_paths_0_to_1: Vec<Vec<_>> = all_simple_paths(&graph, 0u32.into(), 1u32.into(), 0, None)
+ .map(|v: Vec<_>| v.into_iter().map(|i| i.index()).collect())
+ .collect();
+
+ assert_eq!(actual_simple_paths_0_to_1.len(), 1);
+ assert_equal(expexted_simple_paths_0_to_1, &actual_simple_paths_0_to_1);
+ }
+
+ #[test]
+ fn test_no_simple_paths() {
+ let graph = DiGraph::<i32, i32, _>::from_edges(&[
+ (0, 1),
+ (2, 1)
+ ]);
+
+ println!("{}", Dot::new(&graph));
+ let actual_simple_paths_0_to_2: Vec<Vec<_>> = all_simple_paths(&graph, 0u32.into(), 2u32.into(), 0, None)
+ .map(|v: Vec<_>| v.into_iter().map(|i| i.index()).collect())
+ .collect();
+
+ assert_eq!(actual_simple_paths_0_to_2.len(), 0);
+ }
+}
diff --git a/tests/graph.rs b/tests/graph.rs
index 2dceb1a..8bdc077 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -283,6 +283,71 @@
assert_eq!(gr.edge_count(), 2);
}
+
+#[test]
+fn iter_multi_edges() {
+ let mut gr = Graph::new();
+ let a = gr.add_node("a");
+ let b = gr.add_node("b");
+ let c = gr.add_node("c");
+
+ let mut connecting_edges = HashSet::new();
+
+ gr.add_edge(a, a, ());
+ connecting_edges.insert(gr.add_edge(a, b, ()));
+ gr.add_edge(a, c, ());
+ gr.add_edge(c, b, ());
+ connecting_edges.insert(gr.add_edge(a, b, ()));
+ gr.add_edge(b, a, ());
+
+ let mut iter = gr.edges_connecting(a, b);
+
+ let edge_id = iter.next().unwrap().id();
+ assert!(connecting_edges.contains(&edge_id));
+ connecting_edges.remove(&edge_id);
+
+ let edge_id = iter.next().unwrap().id();
+ assert!(connecting_edges.contains(&edge_id));
+ connecting_edges.remove(&edge_id);
+
+ assert_eq!(None, iter.next());
+ assert!(connecting_edges.is_empty());
+}
+
+#[test]
+fn iter_multi_undirected_edges() {
+ let mut gr = Graph::new_undirected();
+ let a = gr.add_node("a");
+ let b = gr.add_node("b");
+ let c = gr.add_node("c");
+
+ let mut connecting_edges = HashSet::new();
+
+ gr.add_edge(a, a, ());
+ connecting_edges.insert(gr.add_edge(a, b, ()));
+ gr.add_edge(a, c, ());
+ gr.add_edge(c, b, ());
+ connecting_edges.insert(gr.add_edge(a, b, ()));
+ connecting_edges.insert(gr.add_edge(b, a, ()));
+
+ let mut iter = gr.edges_connecting(a, b);
+
+ let edge_id = iter.next().unwrap().id();
+ assert!(connecting_edges.contains(&edge_id));
+ connecting_edges.remove(&edge_id);
+
+ let edge_id = iter.next().unwrap().id();
+ assert!(connecting_edges.contains(&edge_id));
+ connecting_edges.remove(&edge_id);
+
+ let edge_id = iter.next().unwrap().id();
+ assert!(connecting_edges.contains(&edge_id));
+ connecting_edges.remove(&edge_id);
+
+ assert_eq!(None, iter.next());
+ assert!(connecting_edges.is_empty());
+}
+
#[test]
fn update_edge()
{
@@ -1565,7 +1630,7 @@
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");
