use std::collections::BinaryHeap;
use std::borrow::{Borrow};
use super::{
Graph,
Directed,
Undirected,
EdgeDirection,
EdgeType,
Outgoing,
Incoming,
Dfs,
};
use scored::MinScored;
use super::visit::{
Visitable,
VisitMap,
};
use super::unionfind::UnionFind;
use super::graph::{
NodeIndex,
IndexType,
};
pub use super::isomorphism::{
is_isomorphic,
is_isomorphic_matching,
};
pub use super::dijkstra::dijkstra;
pub fn is_cyclic_undirected<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() {
let (a, b) = (edge.source(), edge.target());
if !edge_sets.union(a.index(), b.index()) {
return true
}
}
false
}
pub fn is_cyclic<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) -> bool
where Ty: EdgeType,
Ix: IndexType,
{
is_cyclic_undirected(g)
}
#[inline]
fn toposort_generic<N, E, Ix, G, F>(mut g: G, mut visit: F)
where Ix: IndexType,
G: Borrow<Graph<N, E, Directed, Ix>>,
F: FnMut(&mut G, NodeIndex<Ix>),
{
let mut ordered = g.borrow().visit_map();
let mut tovisit = Vec::new();
tovisit.extend(g.borrow().externals(Incoming));
while let Some(nix) = tovisit.pop() {
if ordered.is_visited(&nix) {
continue;
}
visit(&mut g, nix);
ordered.visit(nix);
for neigh in g.borrow().neighbors_directed(nix, Outgoing) {
if g.borrow().neighbors_directed(neigh, Incoming).all(|b| ordered.is_visited(&b)) {
tovisit.push(neigh);
}
}
}
}
pub fn is_cyclic_directed<N, E, Ix>(g: &Graph<N, E, Directed, Ix>) -> bool
where Ix: IndexType,
{
let mut n_ordered = 0;
toposort_generic(g, |_, _| n_ordered += 1);
n_ordered != g.node_count()
}
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());
toposort_generic(g, |_, ix| order.push(ix));
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 finished = g.visit_map();
let mut finish_order = Vec::new();
for i in 0..g.node_count() {
let nindex = NodeIndex::new(i);
if dfs.discovered.is_visited(&nindex) {
continue
}
dfs.stack.push(nindex);
while let Some(&nx) = dfs.stack.last() {
if dfs.discovered.visit(nx) {
for succ in g.neighbors_directed(nx.clone(), EdgeDirection::Incoming) {
if !dfs.discovered.is_visited(&succ) {
dfs.stack.push(succ);
}
}
} else {
dfs.stack.pop();
if finished.visit(nx) {
finish_order.push(nx);
}
}
}
}
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 condensation<N, E, Ty, Ix>(g: Graph<N, E, Ty, Ix>, make_acyclic: bool) -> Graph<Vec<N>, E, Ty, Ix>
where Ty: EdgeType,
Ix: IndexType,
{
let sccs = scc(&g);
let mut condensed: Graph<Vec<N>, E, Ty, Ix> = Graph::with_capacity(sccs.len(), g.edge_count());
let mut node_map = vec![NodeIndex::end(); g.node_count()];
for comp in sccs {
let new_nix = condensed.add_node(Vec::new());
for nix in comp {
node_map[nix.index()] = new_nix;
}
}
let (nodes, edges) = g.into_nodes_edges();
for (nix, node) in nodes.into_iter().enumerate() {
condensed[node_map[nix]].push(node.weight);
}
for edge in edges {
let source = node_map[edge.source().index()];
let target = node_map[edge.target().index()];
if make_acyclic {
if source != target {
condensed.update_edge(source, target, edge.weight);
}
} else {
condensed.add_edge(source, target, edge.weight);
}
}
condensed
}
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() {
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() {
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() {
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
}