use bigraph::traitgraph::interface::NavigableGraph;
use traitgraph::implementation::subgraphs::incremental_subgraph::IncrementalSubgraph;
use traitgraph::interface::subgraph::{MutableSubgraph, SubgraphBase};
use traitgraph::interface::{GraphBase, ImmutableGraphContainer, NodeOrEdge, StaticGraph};
use traitgraph_algo::traversal::{
BackwardNeighborStrategy, BfsQueueStrategy, ForbiddenEdge, ForbiddenNode,
ForwardNeighborStrategy, PreOrderTraversal, TraversalNeighborStrategy,
};
pub fn compute_restricted_edge_reachability<
NeighborStrategy: TraversalNeighborStrategy<SubgraphType::RootGraph>,
SubgraphType: SubgraphBase + MutableSubgraph,
>(
graph: &SubgraphType::RootGraph,
start_node: <SubgraphType as GraphBase>::NodeIndex,
forbidden_edge: <SubgraphType as GraphBase>::EdgeIndex,
target_subgraph: &mut SubgraphType,
) where
<SubgraphType as SubgraphBase>::RootGraph: NavigableGraph,
{
let mut traversal = PreOrderTraversal::<
_,
NeighborStrategy,
BfsQueueStrategy,
std::collections::VecDeque<_>,
>::new(graph, start_node);
let forbidden_edge = ForbiddenEdge::new(forbidden_edge);
while let Some(node_or_edge) = traversal.next_with_forbidden_subgraph(&forbidden_edge) {
match node_or_edge {
NodeOrEdge::Node(node) => target_subgraph.enable_node(node),
NodeOrEdge::Edge(edge) => target_subgraph.enable_edge(edge),
}
}
}
pub fn compute_incremental_restricted_forward_edge_reachability<
'a,
Graph: StaticGraph + SubgraphBase,
>(
graph: &'a Graph,
walk: &[Graph::EdgeIndex],
) -> IncrementalSubgraph<'a, Graph> {
debug_assert!({
let mut sorted_walk = walk.to_owned();
sorted_walk.sort_unstable();
sorted_walk.windows(2).all(|w| w[0] != w[1])
});
let mut subgraph = IncrementalSubgraph::new_with_incremental_steps(graph, walk.len());
let mut traversal = PreOrderTraversal::<
_,
ForwardNeighborStrategy,
BfsQueueStrategy,
std::collections::VecDeque<_>,
>::new_without_start(graph);
let mut start_edge = *walk
.first()
.expect("Cannot compute hydrostructure from empty walk");
for (edge_number, &edge) in walk.iter().enumerate().skip(1) {
subgraph.set_current_step(edge_number);
subgraph.enable_edge(start_edge);
let start_node = graph.edge_endpoints(start_edge).to_node;
traversal.continue_traversal_from(start_node);
let forbidden_edge = ForbiddenEdge::new(edge);
while let Some(node_or_edge) = traversal.next_with_forbidden_subgraph(&forbidden_edge) {
match node_or_edge {
NodeOrEdge::Node(node) => {
debug_assert!(
!subgraph.contains_node_index(node),
"node: {node:?}; walk: {walk:?}"
);
subgraph.enable_node(node)
}
NodeOrEdge::Edge(edge) => {
if !subgraph.contains_edge_index(edge) {
subgraph.enable_edge(edge)
} else {
debug_assert!(walk.contains(&edge))
}
}
}
}
start_edge = edge;
}
subgraph
}
pub fn compute_incremental_restricted_backward_edge_reachability<
'a,
Graph: StaticGraph + SubgraphBase,
>(
graph: &'a Graph,
walk: &[Graph::EdgeIndex],
) -> IncrementalSubgraph<'a, Graph> {
let mut subgraph = IncrementalSubgraph::new_with_incremental_steps(graph, walk.len());
let mut traversal = PreOrderTraversal::<
_,
BackwardNeighborStrategy,
BfsQueueStrategy,
std::collections::VecDeque<_>,
>::new_without_start(graph);
let mut start_edge = *walk
.last()
.expect("Cannot compute hydrostructure from empty walk");
for (edge_number, &edge) in walk.iter().rev().enumerate().skip(1) {
subgraph.set_current_step(edge_number);
subgraph.enable_edge(start_edge);
let start_node = graph.edge_endpoints(start_edge).from_node;
traversal.continue_traversal_from(start_node);
let forbidden_edge = ForbiddenEdge::new(edge);
while let Some(node_or_edge) = traversal.next_with_forbidden_subgraph(&forbidden_edge) {
match node_or_edge {
NodeOrEdge::Node(node) => subgraph.enable_node(node),
NodeOrEdge::Edge(edge) => {
if !subgraph.contains_edge_index(edge) {
subgraph.enable_edge(edge)
} else {
debug_assert!(walk.contains(&edge))
}
}
}
}
start_edge = edge;
}
subgraph
}
pub fn compute_restricted_node_reachability<
NeighborStrategy: TraversalNeighborStrategy<SubgraphType::RootGraph>,
SubgraphType: SubgraphBase + MutableSubgraph,
>(
graph: &SubgraphType::RootGraph,
start_node: <SubgraphType as GraphBase>::NodeIndex,
forbidden_node: <SubgraphType as GraphBase>::NodeIndex,
target_subgraph: &mut SubgraphType,
) where
<SubgraphType as SubgraphBase>::RootGraph: NavigableGraph,
{
let mut traversal = PreOrderTraversal::<
_,
NeighborStrategy,
BfsQueueStrategy,
std::collections::VecDeque<_>,
>::new(graph, start_node);
let forbidden_node = ForbiddenNode::new(forbidden_node);
while let Some(node_or_edge) = traversal.next_with_forbidden_subgraph(&forbidden_node) {
match node_or_edge {
NodeOrEdge::Node(node) => target_subgraph.enable_node(node),
NodeOrEdge::Edge(edge) => target_subgraph.enable_edge(edge),
}
}
}
pub fn compute_restricted_forward_reachability<SubgraphType: SubgraphBase + MutableSubgraph>(
graph: &SubgraphType::RootGraph,
edge: <SubgraphType as GraphBase>::EdgeIndex,
target_subgraph: &mut SubgraphType,
) where
SubgraphType::RootGraph: ImmutableGraphContainer + NavigableGraph,
{
let start_node = graph.edge_endpoints(edge).from_node;
compute_restricted_edge_reachability::<ForwardNeighborStrategy, _>(
graph,
start_node,
edge,
target_subgraph,
)
}
pub fn compute_restricted_backward_reachability<SubgraphType: SubgraphBase + MutableSubgraph>(
graph: &SubgraphType::RootGraph,
edge: <SubgraphType as GraphBase>::EdgeIndex,
target_subgraph: &mut SubgraphType,
) where
SubgraphType::RootGraph: ImmutableGraphContainer + NavigableGraph,
{
let start_node = graph.edge_endpoints(edge).to_node;
compute_restricted_edge_reachability::<BackwardNeighborStrategy, _>(
graph,
start_node,
edge,
target_subgraph,
)
}
pub fn compute_inverse_restricted_forward_reachability<
SubgraphType: SubgraphBase + MutableSubgraph,
>(
graph: &SubgraphType::RootGraph,
edge: <SubgraphType as GraphBase>::EdgeIndex,
target_subgraph: &mut SubgraphType,
) where
SubgraphType::RootGraph: ImmutableGraphContainer + NavigableGraph,
{
let forbidden_node = graph.edge_endpoints(edge).from_node;
let start_node = graph.edge_endpoints(edge).to_node;
if start_node != forbidden_node {
compute_restricted_node_reachability::<ForwardNeighborStrategy, _>(
graph,
start_node,
forbidden_node,
target_subgraph,
)
};
target_subgraph.enable_edge(edge);
}
pub fn compute_inverse_restricted_backward_reachability<
SubgraphType: SubgraphBase + MutableSubgraph,
>(
graph: &SubgraphType::RootGraph,
edge: <SubgraphType as GraphBase>::EdgeIndex,
target_subgraph: &mut SubgraphType,
) where
SubgraphType::RootGraph: ImmutableGraphContainer + NavigableGraph,
{
let forbidden_node = graph.edge_endpoints(edge).to_node;
let start_node = graph.edge_endpoints(edge).from_node;
if start_node != forbidden_node {
compute_restricted_node_reachability::<BackwardNeighborStrategy, _>(
graph,
start_node,
forbidden_node,
target_subgraph,
)
};
target_subgraph.enable_edge(edge);
}
#[must_use]
pub fn compute_hydrostructure_forward_reachability<
SubgraphType: SubgraphBase + MutableSubgraph + ImmutableGraphContainer,
>(
graph: &SubgraphType::RootGraph,
azb: &[<SubgraphType as GraphBase>::EdgeIndex],
target_subgraph: &mut SubgraphType,
) -> bool
where
SubgraphType::RootGraph: ImmutableGraphContainer + NavigableGraph,
{
let a = *azb.iter().next().unwrap();
let b = *azb.iter().last().unwrap();
let start_node = graph.edge_endpoints(a).to_node;
compute_restricted_edge_reachability::<ForwardNeighborStrategy, _>(
graph,
start_node,
b,
target_subgraph,
);
for &edge in azb.iter().take(azb.len() - 1) {
let node = graph.edge_endpoints(edge).to_node;
for incoming in graph.in_neighbors(node) {
let incoming = incoming.edge_id;
if incoming != edge && target_subgraph.contains_edge_index(incoming) {
return false;
}
}
}
target_subgraph.enable_edge(a);
true
}
#[must_use]
pub fn compute_hydrostructure_backward_reachability<
SubgraphType: SubgraphBase + MutableSubgraph + ImmutableGraphContainer,
>(
graph: &SubgraphType::RootGraph,
azb: &[<SubgraphType as GraphBase>::EdgeIndex],
target_subgraph: &mut SubgraphType,
) -> bool
where
SubgraphType::RootGraph: ImmutableGraphContainer + NavigableGraph,
{
let a = *azb.iter().next().unwrap();
let b = *azb.iter().last().unwrap();
let start_node = graph.edge_endpoints(b).from_node;
compute_restricted_edge_reachability::<BackwardNeighborStrategy, SubgraphType>(
graph,
start_node,
a,
target_subgraph,
);
for &edge in azb.iter().skip(1) {
let node = graph.edge_endpoints(edge).from_node;
for outgoing in graph.out_neighbors(node) {
let outgoing = outgoing.edge_id;
if outgoing != edge && target_subgraph.contains_edge_index(outgoing) {
return false;
}
}
}
target_subgraph.enable_edge(b);
true
}
#[cfg(test)]
mod tests {
use crate::restricted_reachability::compute_restricted_forward_reachability;
use crate::restricted_reachability::{
compute_incremental_restricted_backward_edge_reachability,
compute_incremental_restricted_forward_edge_reachability,
compute_restricted_backward_reachability,
};
use traitgraph::implementation::petgraph_impl::PetGraph;
use traitgraph::implementation::subgraphs::bit_vector_subgraph::BitVectorSubgraph;
use traitgraph::interface::{ImmutableGraphContainer, MutableGraphContainer, WalkableGraph};
#[test]
fn test_restricted_forward_reachability_simple() {
let mut graph = PetGraph::new();
let n0 = graph.add_node(0);
let n1 = graph.add_node(1);
let n2 = graph.add_node(2);
let e1 = graph.add_edge(n0, n1, -1);
let _e2 = graph.add_edge(n1, n1, -2);
let e3 = graph.add_edge(n0, n0, -3);
let _e4 = graph.add_edge(n1, n0, -4);
let e5 = graph.add_edge(n0, n2, -5);
let _e6 = graph.add_edge(n1, n2, -6);
let mut subgraph = BitVectorSubgraph::new_empty(&graph);
compute_restricted_forward_reachability(&graph, e1, &mut subgraph);
debug_assert_eq!(subgraph.node_count(), 2);
debug_assert!(subgraph.contains_node_index(n0));
debug_assert!(subgraph.contains_node_index(n2));
debug_assert_eq!(subgraph.edge_count(), 2);
debug_assert!(subgraph.contains_edge_index(e3));
debug_assert!(subgraph.contains_edge_index(e5));
}
#[test]
fn test_restricted_backward_reachability_simple() {
let mut graph = PetGraph::new();
let n0 = graph.add_node(0);
let n1 = graph.add_node(1);
let n2 = graph.add_node(2);
let e1 = graph.add_edge(n1, n0, -1);
let _e2 = graph.add_edge(n1, n1, -2);
let e3 = graph.add_edge(n0, n0, -3);
let _e4 = graph.add_edge(n0, n1, -4);
let e5 = graph.add_edge(n2, n0, -5);
let _e6 = graph.add_edge(n2, n1, -6);
let mut subgraph = BitVectorSubgraph::new_empty(&graph);
compute_restricted_backward_reachability(&graph, e1, &mut subgraph);
debug_assert_eq!(subgraph.node_count(), 2);
debug_assert!(subgraph.contains_node_index(n0));
debug_assert!(subgraph.contains_node_index(n2));
debug_assert_eq!(subgraph.edge_count(), 2);
debug_assert!(subgraph.contains_edge_index(e3));
debug_assert!(subgraph.contains_edge_index(e5));
}
#[test]
fn test_incremental_restricted_forwards_reachability() {
let mut graph = PetGraph::new();
let n: Vec<_> = (0..10).map(|i| graph.add_node(i)).collect();
let mut e: Vec<_> = (0..9)
.map(|i| graph.add_edge(n[i], n[i + 1], i + 100))
.collect();
e.push(graph.add_edge(n[9], n[0], 110));
e.extend((0..10).map(|i| graph.add_edge(n[i], n[0], i + 110)));
e.push(graph.add_edge(n[4], n[2], 120));
e.push(graph.add_edge(n[7], n[3], 121));
let walk: Vec<_> = graph.create_edge_walk(&e[0..10]);
let mut subgraph = compute_incremental_restricted_forward_edge_reachability(&graph, &walk);
for i in 0..10 {
subgraph.set_current_step(i);
let (expected_nodes, expected_edges) = if i == 0 {
(Vec::new(), Vec::new())
} else {
let expected_nodes = n[0..i + 1].to_owned();
let mut expected_edges = e[0..i].to_owned();
expected_edges.extend(&e[10..i + 11]);
if i >= 4 {
expected_edges.push(e[20]);
}
if i >= 7 {
expected_edges.push(e[21]);
}
(expected_nodes, expected_edges)
};
let actual_nodes: Vec<_> = subgraph.node_indices().collect();
let actual_edges: Vec<_> = subgraph.edge_indices().collect();
assert_eq!(expected_nodes, actual_nodes, "expected_nodes: {expected_nodes:?}\nactual_nodes: {actual_nodes:?}\nexpected_edges: {expected_edges:?}\nactual_edges: {actual_edges:?}");
assert_eq!(expected_edges, actual_edges, "expected_nodes: {expected_nodes:?}\nactual_nodes: {actual_nodes:?}\nexpected_edges: {expected_edges:?}\nactual_edges: {actual_edges:?}");
}
}
#[test]
fn test_incremental_restricted_backwards_reachability() {
let mut graph = PetGraph::new();
let n: Vec<_> = (0..10).map(|i| graph.add_node(i)).collect();
let mut e: Vec<_> = (0..9)
.map(|i| graph.add_edge(n[i], n[i + 1], i + 100))
.collect();
e.push(graph.add_edge(n[9], n[0], 110));
e.extend((0..10).map(|i| graph.add_edge(n[i], n[0], i + 110)));
e.push(graph.add_edge(n[4], n[2], 120));
e.push(graph.add_edge(n[7], n[3], 121));
let walk: Vec<_> = graph.create_edge_walk(&e[0..10]);
let mut subgraph = compute_incremental_restricted_backward_edge_reachability(&graph, &walk);
for i in 0..10 {
subgraph.set_current_step(i);
let (expected_nodes, expected_edges) = if i == 0 {
(Vec::new(), Vec::new())
} else {
let expected_nodes = n[10 - i..10].to_owned();
let mut expected_edges = e[10 - i..10].to_owned();
if i >= 8 {
expected_edges.push(e[20]);
}
if i >= 7 {
expected_edges.push(e[21]);
}
(expected_nodes, expected_edges)
};
let actual_nodes: Vec<_> = subgraph.node_indices().collect();
let actual_edges: Vec<_> = subgraph.edge_indices().collect();
assert_eq!(expected_nodes, actual_nodes, "expected_nodes: {expected_nodes:?}\nactual_nodes: {actual_nodes:?}\nexpected_edges: {expected_edges:?}\nactual_edges: {actual_edges:?}");
assert_eq!(expected_edges, actual_edges, "expected_nodes: {expected_nodes:?}\nactual_nodes: {actual_nodes:?}\nexpected_edges: {expected_edges:?}\nactual_edges: {actual_edges:?}");
}
}
}