use crate::adj::{List, UnweightedList};
use crate::graph::IndexType;
use crate::visit::{
GraphBase, IntoNeighbors, IntoNeighborsDirected, NodeCompactIndexable, NodeCount,
};
use crate::Direction;
use fixedbitset::FixedBitSet;
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());
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)
}
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());
}
for i in g.node_indices().rev() {
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());
}