use std::collections::BinaryHeap;
use super::{
Graph,
Directed,
Undirected,
EdgeType,
Outgoing,
Incoming,
Dfs,
MinScored,
};
use super::visit::{
Reversed,
Visitable,
VisitMap,
};
use super::unionfind::UnionFind;
use super::graph::{
NodeIndex,
IndexType,
};
pub use super::isomorphism::is_isomorphic;
pub use super::dijkstra::dijkstra;
pub fn toposort<N, E, Ix>(g: &Graph<N, E, Directed, Ix>) -> Vec<NodeIndex<Ix>> where
Ix: IndexType,
{
let mut order = Vec::with_capacity(g.node_count());
let mut ordered = g.visit_map();
let mut tovisit = Vec::new();
tovisit.extend(g.without_edges(Incoming));
while let Some(nix) = tovisit.pop() {
if ordered.is_visited(&nix) {
continue;
}
order.push(nix);
ordered.visit(nix);
for neigh in g.neighbors_directed(nix, Outgoing) {
if g.neighbors_directed(neigh, Incoming).all(|b| ordered.is_visited(&b)) {
tovisit.push(neigh);
}
}
}
order
}
pub fn scc<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) -> Vec<Vec<NodeIndex<Ix>>> where
Ty: EdgeType,
Ix: IndexType,
{
let mut dfs = Dfs::empty(g);
let mut finish_order = Vec::new();
for index in (0..g.node_count()) {
if dfs.discovered.is_visited(&NodeIndex::<Ix>::new(index)) {
continue
}
let pass_start = finish_order.len();
dfs.move_to(NodeIndex::new(index));
while let Some(nx) = dfs.next(&Reversed(g)) {
finish_order.push(nx);
}
finish_order[pass_start..].reverse();
}
dfs.discovered.clear();
let mut sccs = Vec::new();
for &nindex in finish_order.iter().rev() {
if dfs.discovered.is_visited(&nindex) {
continue;
}
dfs.move_to(nindex);
let mut scc = Vec::new();
while let Some(nx) = dfs.next(g) {
scc.push(nx);
}
sccs.push(scc);
}
sccs
}
pub fn is_cyclic<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) -> bool where
Ty: EdgeType,
Ix: IndexType,
{
let mut edge_sets = UnionFind::new(g.node_count());
for edge in g.raw_edges().iter() {
let (a, b) = (edge.source(), edge.target());
if !edge_sets.union(a.index(), b.index()) {
return true
}
}
false
}
pub fn connected_components<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) -> usize where
Ty: EdgeType,
Ix: IndexType,
{
let mut vertex_sets = UnionFind::new(g.node_count());
for edge in g.raw_edges().iter() {
let (a, b) = (edge.source(), edge.target());
vertex_sets.union(a.index(), b.index());
}
let mut labels = vertex_sets.into_labeling();
labels.sort();
labels.dedup();
labels.len()
}
pub fn min_spanning_tree<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) -> Graph<N, E, Undirected, Ix> where
N: Clone,
E: Clone + PartialOrd,
Ty: EdgeType,
Ix: IndexType,
{
if g.node_count() == 0 {
return Graph::with_capacity(0, 0)
}
let mut mst = Graph::with_capacity(g.node_count(), g.node_count() - 1);
for node in g.raw_nodes().iter() {
mst.add_node(node.weight.clone());
}
let mut subgraphs = UnionFind::new(g.node_count());
let mut sort_edges = BinaryHeap::with_capacity(g.edge_count());
for edge in g.raw_edges().iter() {
sort_edges.push(MinScored(edge.weight.clone(), (edge.source(), edge.target())));
}
while let Some(MinScored(score, (a, b))) = sort_edges.pop() {
if subgraphs.union(a.index(), b.index()) {
mst.add_edge(a, b, score);
}
}
debug_assert!(mst.node_count() == g.node_count());
debug_assert!(mst.edge_count() < g.node_count());
mst
}