1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
//! Compute the transitive reduction and closure of a directed acyclic graph
//!
//! ## Transitive reduction and closure
//! The *transitive closure* of a graph **G = (V, E)** is the graph **Gc = (V, Ec)**
//! such that **(i, j)** belongs to **Ec** if and only if there is a path connecting
//! **i** to **j** in **G**. The *transitive reduction* of **G** is the graph **Gr
//! = (V, Er)** such that **Er** is minimal wrt. inclusion in **E** and the transitive
//! closure of **Gr** is the same as that of **G**.
//! The transitive reduction is well-defined for acyclic graphs only.
use crate::adj::{List, UnweightedList};
use crate::graph::IndexType;
use crate::visit::{
GraphBase, IntoNeighbors, IntoNeighborsDirected, NodeCompactIndexable, NodeCount,
};
use crate::Direction;
use fixedbitset::FixedBitSet;
/// Creates a representation of the same graph respecting topological order for use in `tred::dag_transitive_reduction_closure`.
///
/// `toposort` must be a topological order on the node indices of `g` (for example obtained
/// from [`toposort`]).
///
/// [`toposort`]: ../fn.toposort.html
///
/// Returns a pair of a graph `res` and the reciprocal of the topological sort `revmap`.
///
/// `res` is the same graph as `g` with the following differences:
/// * Node and edge weights are stripped,
/// * Node indices are replaced by the corresponding rank in `toposort`,
/// * Iterating on the neighbors of a node respects topological order.
///
/// `revmap` is handy to get back to map indices in `g` to indices in `res`.
/// ```
/// use petgraph::prelude::*;
/// use petgraph::graph::DefaultIx;
/// use petgraph::visit::IntoNeighbors;
/// use petgraph::algo::tred::dag_to_toposorted_adjacency_list;
///
/// let mut g = Graph::<&str, (), Directed, DefaultIx>::new();
/// let second = g.add_node("second child");
/// let top = g.add_node("top");
/// let first = g.add_node("first child");
/// g.extend_with_edges(&[(top, second), (top, first), (first, second)]);
///
/// let toposort = vec![top, first, second];
///
/// let (res, revmap) = dag_to_toposorted_adjacency_list(&g, &toposort);
///
/// // let's compute the children of top in topological order
/// let children: Vec<NodeIndex> = res
/// .neighbors(revmap[top.index()])
/// .map(|ix: NodeIndex| toposort[ix.index()])
/// .collect();
/// assert_eq!(children, vec![first, second])
/// ```
///
/// Runtime: **O(|V| + |E|)**.
///
/// Space complexity: **O(|V| + |E|)**.
pub fn dag_to_toposorted_adjacency_list<G, Ix: IndexType>(
g: G,
toposort: &[G::NodeId],
) -> (UnweightedList<Ix>, Vec<Ix>)
where
G: GraphBase + IntoNeighborsDirected + NodeCompactIndexable + NodeCount,
G::NodeId: IndexType,
{
let mut res = List::with_capacity(g.node_count());
// map from old node index to rank in toposort
let mut revmap = vec![Ix::default(); g.node_bound()];
for (ix, &old_ix) in toposort.iter().enumerate() {
let ix = Ix::new(ix);
revmap[old_ix.index()] = ix;
let iter = g.neighbors_directed(old_ix, Direction::Incoming);
let new_ix: Ix = res.add_node_with_capacity(iter.size_hint().0);
debug_assert_eq!(new_ix.index(), ix.index());
for old_pre in iter {
let pre: Ix = revmap[old_pre.index()];
res.add_edge(pre, ix, ());
}
}
(res, revmap)
}
/// Computes the transitive reduction and closure of a DAG.
///
/// The algorithm implemented here comes from [On the calculation of
/// transitive reduction-closure of
/// orders](https://www.sciencedirect.com/science/article/pii/0012365X9390164O) by Habib, Morvan
/// and Rampon.
///
/// The input graph must be in a very specific format: an adjacency
/// list such that:
/// * Node indices are a toposort, and
/// * The neighbors of all nodes are stored in topological order.
/// To get such a representation, use the function [`dag_to_toposorted_adjacency_list`].
///
/// [`dag_to_toposorted_adjacency_list`]: ./fn.dag_to_toposorted_adjacency_list.html
///
/// The output is the pair of the transitive reduction and the transitive closure.
///
/// Runtime complexity: **O(|V| + \sum_{(x, y) \in Er} d(y))** where **d(y)**
/// denotes the outgoing degree of **y** in the transitive closure of **G**.
/// This is still **O(|V|³)** in the worst case like the naive algorithm but
/// should perform better for some classes of graphs.
///
/// Space complexity: **O(|E|)**.
pub fn dag_transitive_reduction_closure<E, Ix: IndexType>(
g: &List<E, Ix>,
) -> (UnweightedList<Ix>, UnweightedList<Ix>) {
let mut tred = List::with_capacity(g.node_count());
let mut tclos = List::with_capacity(g.node_count());
let mut mark = FixedBitSet::with_capacity(g.node_count());
for i in g.node_indices() {
tred.add_node();
tclos.add_node_with_capacity(g.neighbors(i).len());
}
// the algorithm relies on this iterator being toposorted
for i in g.node_indices().rev() {
// the algorighm relies on this iterator being toposorted
for x in g.neighbors(i) {
if !mark[x.index()] {
tred.add_edge(i, x, ());
tclos.add_edge(i, x, ());
for e in tclos.edge_indices_from(x) {
let y = tclos.edge_endpoints(e).unwrap().1;
if !mark[y.index()] {
mark.insert(y.index());
tclos.add_edge(i, y, ());
}
}
}
}
for y in tclos.neighbors(i) {
mark.set(y.index(), false);
}
}
(tred, tclos)
}
#[cfg(test)]
#[test]
fn test_easy_tred() {
let mut input = List::new();
let a: u8 = input.add_node();
let b = input.add_node();
let c = input.add_node();
input.add_edge(a, b, ());
input.add_edge(a, c, ());
input.add_edge(b, c, ());
let (tred, tclos) = dag_transitive_reduction_closure(&input);
assert_eq!(tred.node_count(), 3);
assert_eq!(tclos.node_count(), 3);
assert!(tred.find_edge(a, b).is_some());
assert!(tred.find_edge(b, c).is_some());
assert!(tred.find_edge(a, c).is_none());
assert!(tclos.find_edge(a, b).is_some());
assert!(tclos.find_edge(b, c).is_some());
assert!(tclos.find_edge(a, c).is_some());
}