pub mod astar;
pub mod bellman_ford;
pub mod dijkstra;
pub mod dominators;
pub mod feedback_arc_set;
pub mod floyd_warshall;
pub mod isomorphism;
pub mod k_shortest_path;
pub mod matching;
pub mod simple_paths;
pub mod tred;
use std::collections::{BinaryHeap, HashMap};
use std::num::NonZeroUsize;
use crate::prelude::*;
use super::graph::IndexType;
use super::unionfind::UnionFind;
use super::visit::{
GraphBase, GraphRef, IntoEdgeReferences, IntoNeighbors, IntoNeighborsDirected,
IntoNodeIdentifiers, NodeCompactIndexable, NodeIndexable, Reversed, VisitMap, Visitable,
};
use super::EdgeType;
use crate::data::Element;
use crate::scored::MinScored;
use crate::visit::Walker;
use crate::visit::{Data, IntoNodeReferences, NodeRef};
pub use astar::astar;
pub use bellman_ford::{bellman_ford, find_negative_cycle};
pub use dijkstra::dijkstra;
pub use feedback_arc_set::greedy_feedback_arc_set;
pub use floyd_warshall::floyd_warshall;
pub use isomorphism::{
is_isomorphic, is_isomorphic_matching, is_isomorphic_subgraph, is_isomorphic_subgraph_matching,
};
pub use k_shortest_path::k_shortest_path;
pub use matching::{greedy_matching, maximum_matching, Matching};
pub use simple_paths::all_simple_paths;
pub fn connected_components<G>(g: G) -> usize
where
G: NodeCompactIndexable + IntoEdgeReferences,
{
let mut vertex_sets = UnionFind::new(g.node_bound());
for edge in g.edge_references() {
let (a, b) = (edge.source(), edge.target());
vertex_sets.union(g.to_index(a), g.to_index(b));
}
let mut labels = vertex_sets.into_labeling();
labels.sort_unstable();
labels.dedup();
labels.len()
}
pub fn is_cyclic_undirected<G>(g: G) -> bool
where
G: NodeIndexable + IntoEdgeReferences,
{
let mut edge_sets = UnionFind::new(g.node_bound());
for edge in g.edge_references() {
let (a, b) = (edge.source(), edge.target());
if !edge_sets.union(g.to_index(a), g.to_index(b)) {
return true;
}
}
false
}
pub fn toposort<G>(
g: G,
space: Option<&mut DfsSpace<G::NodeId, G::Map>>,
) -> Result<Vec<G::NodeId>, Cycle<G::NodeId>>
where
G: IntoNeighborsDirected + IntoNodeIdentifiers + Visitable,
{
with_dfs(g, space, |dfs| {
dfs.reset(g);
let mut finished = g.visit_map();
let mut finish_stack = Vec::new();
for i in g.node_identifiers() {
if dfs.discovered.is_visited(&i) {
continue;
}
dfs.stack.push(i);
while let Some(&nx) = dfs.stack.last() {
if dfs.discovered.visit(nx) {
for succ in g.neighbors(nx) {
if succ == nx {
return Err(Cycle(nx));
}
if !dfs.discovered.is_visited(&succ) {
dfs.stack.push(succ);
}
}
} else {
dfs.stack.pop();
if finished.visit(nx) {
finish_stack.push(nx);
}
}
}
}
finish_stack.reverse();
dfs.reset(g);
for &i in &finish_stack {
dfs.move_to(i);
let mut cycle = false;
while let Some(j) = dfs.next(Reversed(g)) {
if cycle {
return Err(Cycle(j));
}
cycle = true;
}
}
Ok(finish_stack)
})
}
pub fn is_cyclic_directed<G>(g: G) -> bool
where
G: IntoNodeIdentifiers + IntoNeighbors + Visitable,
{
use crate::visit::{depth_first_search, DfsEvent};
depth_first_search(g, g.node_identifiers(), |event| match event {
DfsEvent::BackEdge(_, _) => Err(()),
_ => Ok(()),
})
.is_err()
}
type DfsSpaceType<G> = DfsSpace<<G as GraphBase>::NodeId, <G as Visitable>::Map>;
#[derive(Clone, Debug)]
pub struct DfsSpace<N, VM> {
dfs: Dfs<N, VM>,
}
impl<N, VM> DfsSpace<N, VM>
where
N: Copy + PartialEq,
VM: VisitMap<N>,
{
pub fn new<G>(g: G) -> Self
where
G: GraphRef + Visitable<NodeId = N, Map = VM>,
{
DfsSpace { dfs: Dfs::empty(g) }
}
}
impl<N, VM> Default for DfsSpace<N, VM>
where
VM: VisitMap<N> + Default,
{
fn default() -> Self {
DfsSpace {
dfs: Dfs {
stack: <_>::default(),
discovered: <_>::default(),
},
}
}
}
fn with_dfs<G, F, R>(g: G, space: Option<&mut DfsSpaceType<G>>, f: F) -> R
where
G: GraphRef + Visitable,
F: FnOnce(&mut Dfs<G::NodeId, G::Map>) -> R,
{
let mut local_visitor;
let dfs = if let Some(v) = space {
&mut v.dfs
} else {
local_visitor = Dfs::empty(g);
&mut local_visitor
};
f(dfs)
}
pub fn has_path_connecting<G>(
g: G,
from: G::NodeId,
to: G::NodeId,
space: Option<&mut DfsSpace<G::NodeId, G::Map>>,
) -> bool
where
G: IntoNeighbors + Visitable,
{
with_dfs(g, space, |dfs| {
dfs.reset(g);
dfs.move_to(from);
dfs.iter(g).any(|x| x == to)
})
}
#[deprecated(note = "renamed to kosaraju_scc")]
pub fn scc<G>(g: G) -> Vec<Vec<G::NodeId>>
where
G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
{
kosaraju_scc(g)
}
pub fn kosaraju_scc<G>(g: G) -> Vec<Vec<G::NodeId>>
where
G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
{
let mut dfs = DfsPostOrder::empty(g);
let mut finish_order = Vec::with_capacity(0);
for i in g.node_identifiers() {
if dfs.discovered.is_visited(&i) {
continue;
}
dfs.move_to(i);
while let Some(nx) = dfs.next(Reversed(g)) {
finish_order.push(nx);
}
}
let mut dfs = Dfs::from_parts(dfs.stack, dfs.discovered);
dfs.reset(g);
let mut sccs = Vec::new();
for i in finish_order.into_iter().rev() {
if dfs.discovered.is_visited(&i) {
continue;
}
dfs.move_to(i);
let mut scc = Vec::new();
while let Some(nx) = dfs.next(g) {
scc.push(nx);
}
sccs.push(scc);
}
sccs
}
#[derive(Copy, Clone, Debug)]
struct NodeData {
rootindex: Option<NonZeroUsize>,
}
#[derive(Debug)]
pub struct TarjanScc<N> {
index: usize,
componentcount: usize,
nodes: Vec<NodeData>,
stack: Vec<N>,
}
impl<N> Default for TarjanScc<N> {
fn default() -> Self {
Self::new()
}
}
impl<N> TarjanScc<N> {
pub fn new() -> Self {
TarjanScc {
index: 1, componentcount: std::usize::MAX, nodes: Vec::new(),
stack: Vec::new(),
}
}
pub fn run<G, F>(&mut self, g: G, mut f: F)
where
G: IntoNodeIdentifiers<NodeId = N> + IntoNeighbors<NodeId = N> + NodeIndexable<NodeId = N>,
F: FnMut(&[N]),
N: Copy + PartialEq,
{
self.nodes.clear();
self.nodes
.resize(g.node_bound(), NodeData { rootindex: None });
for n in g.node_identifiers() {
let visited = self.nodes[g.to_index(n)].rootindex.is_some();
if !visited {
self.visit(n, g, &mut f);
}
}
debug_assert!(self.stack.is_empty());
}
fn visit<G, F>(&mut self, v: G::NodeId, g: G, f: &mut F)
where
G: IntoNeighbors<NodeId = N> + NodeIndexable<NodeId = N>,
F: FnMut(&[N]),
N: Copy + PartialEq,
{
macro_rules! node {
($node:expr) => {
self.nodes[g.to_index($node)]
};
}
let node_v = &mut node![v];
debug_assert!(node_v.rootindex.is_none());
let mut v_is_local_root = true;
let v_index = self.index;
node_v.rootindex = NonZeroUsize::new(v_index);
self.index += 1;
for w in g.neighbors(v) {
if node![w].rootindex.is_none() {
self.visit(w, g, f);
}
if node![w].rootindex < node![v].rootindex {
node![v].rootindex = node![w].rootindex;
v_is_local_root = false
}
}
if v_is_local_root {
let mut indexadjustment = 1;
let c = NonZeroUsize::new(self.componentcount);
let nodes = &mut self.nodes;
let start = self
.stack
.iter()
.rposition(|&w| {
if nodes[g.to_index(v)].rootindex > nodes[g.to_index(w)].rootindex {
true
} else {
nodes[g.to_index(w)].rootindex = c;
indexadjustment += 1;
false
}
})
.map(|x| x + 1)
.unwrap_or_default();
nodes[g.to_index(v)].rootindex = c;
self.stack.push(v); f(&self.stack[start..]);
self.stack.truncate(start);
self.index -= indexadjustment; self.componentcount -= 1;
} else {
self.stack.push(v); }
}
pub fn node_component_index<G>(&self, g: G, v: N) -> usize
where
G: IntoNeighbors<NodeId = N> + NodeIndexable<NodeId = N>,
N: Copy + PartialEq,
{
let rindex: usize = self.nodes[g.to_index(v)]
.rootindex
.map(NonZeroUsize::get)
.unwrap_or(0); debug_assert!(
rindex != 0,
"Tried to get the component index of an unvisited node."
);
debug_assert!(
rindex > self.componentcount,
"Given node has been visited but not yet assigned to a component."
);
std::usize::MAX - rindex
}
}
pub fn tarjan_scc<G>(g: G) -> Vec<Vec<G::NodeId>>
where
G: IntoNodeIdentifiers + IntoNeighbors + NodeIndexable,
{
let mut sccs = Vec::new();
{
let mut tarjan_scc = TarjanScc::new();
tarjan_scc.run(g, |scc| sccs.push(scc.to_vec()));
}
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 = kosaraju_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 min_spanning_tree<G>(g: G) -> MinSpanningTree<G>
where
G::NodeWeight: Clone,
G::EdgeWeight: Clone + PartialOrd,
G: IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
{
let subgraphs = UnionFind::new(g.node_bound());
let edges = g.edge_references();
let mut sort_edges = BinaryHeap::with_capacity(edges.size_hint().0);
for edge in edges {
sort_edges.push(MinScored(
edge.weight().clone(),
(edge.source(), edge.target()),
));
}
MinSpanningTree {
graph: g,
node_ids: Some(g.node_references()),
subgraphs,
sort_edges,
node_map: HashMap::new(),
node_count: 0,
}
}
#[derive(Debug, Clone)]
pub struct MinSpanningTree<G>
where
G: Data + IntoNodeReferences,
{
graph: G,
node_ids: Option<G::NodeReferences>,
subgraphs: UnionFind<usize>,
#[allow(clippy::type_complexity)]
sort_edges: BinaryHeap<MinScored<G::EdgeWeight, (G::NodeId, G::NodeId)>>,
node_map: HashMap<usize, usize>,
node_count: usize,
}
impl<G> Iterator for MinSpanningTree<G>
where
G: IntoNodeReferences + NodeIndexable,
G::NodeWeight: Clone,
G::EdgeWeight: PartialOrd,
{
type Item = Element<G::NodeWeight, G::EdgeWeight>;
fn next(&mut self) -> Option<Self::Item> {
let g = self.graph;
if let Some(ref mut iter) = self.node_ids {
if let Some(node) = iter.next() {
self.node_map.insert(g.to_index(node.id()), self.node_count);
self.node_count += 1;
return Some(Element::Node {
weight: node.weight().clone(),
});
}
}
self.node_ids = None;
while let Some(MinScored(score, (a, b))) = self.sort_edges.pop() {
let (a_index, b_index) = (g.to_index(a), g.to_index(b));
if self.subgraphs.union(a_index, b_index) {
let (&a_order, &b_order) =
match (self.node_map.get(&a_index), self.node_map.get(&b_index)) {
(Some(a_id), Some(b_id)) => (a_id, b_id),
_ => panic!("Edge references unknown node"),
};
return Some(Element::Edge {
source: a_order,
target: b_order,
weight: score,
});
}
}
None
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct Cycle<N>(N);
impl<N> Cycle<N> {
pub fn node_id(&self) -> N
where
N: Copy,
{
self.0
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct NegativeCycle(pub ());
pub fn is_bipartite_undirected<G, N, VM>(g: G, start: N) -> bool
where
G: GraphRef + Visitable<NodeId = N, Map = VM> + IntoNeighbors<NodeId = N>,
N: Copy + PartialEq + std::fmt::Debug,
VM: VisitMap<N>,
{
let mut red = g.visit_map();
red.visit(start);
let mut blue = g.visit_map();
let mut stack = ::std::collections::VecDeque::new();
stack.push_front(start);
while let Some(node) = stack.pop_front() {
let is_red = red.is_visited(&node);
let is_blue = blue.is_visited(&node);
assert!(is_red ^ is_blue);
for neighbour in g.neighbors(node) {
let is_neigbour_red = red.is_visited(&neighbour);
let is_neigbour_blue = blue.is_visited(&neighbour);
if (is_red && is_neigbour_red) || (is_blue && is_neigbour_blue) {
return false;
}
if !is_neigbour_red && !is_neigbour_blue {
match (is_red, is_blue) {
(true, false) => {
blue.visit(neighbour);
}
(false, true) => {
red.visit(neighbour);
}
(_, _) => {
panic!("Invariant doesn't hold");
}
}
stack.push_back(neighbour);
}
}
}
true
}
use std::fmt::Debug;
use std::ops::Add;
pub trait Measure: Debug + PartialOrd + Add<Self, Output = Self> + Default + Clone {}
impl<M> Measure for M where M: Debug + PartialOrd + Add<M, Output = M> + Default + Clone {}
pub trait FloatMeasure: Measure + Copy {
fn zero() -> Self;
fn infinite() -> Self;
}
impl FloatMeasure for f32 {
fn zero() -> Self {
0.
}
fn infinite() -> Self {
1. / 0.
}
}
impl FloatMeasure for f64 {
fn zero() -> Self {
0.
}
fn infinite() -> Self {
1. / 0.
}
}
pub trait BoundedMeasure: Measure + std::ops::Sub<Self, Output = Self> {
fn min() -> Self;
fn max() -> Self;
fn overflowing_add(self, rhs: Self) -> (Self, bool);
}
macro_rules! impl_bounded_measure_integer(
( $( $t:ident ),* ) => {
$(
impl BoundedMeasure for $t {
fn min() -> Self {
std::$t::MIN
}
fn max() -> Self {
std::$t::MAX
}
fn overflowing_add(self, rhs: Self) -> (Self, bool) {
self.overflowing_add(rhs)
}
}
)*
};
);
impl_bounded_measure_integer!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize);
macro_rules! impl_bounded_measure_float(
( $( $t:ident ),* ) => {
$(
impl BoundedMeasure for $t {
fn min() -> Self {
std::$t::MIN
}
fn max() -> Self {
std::$t::MAX
}
fn overflowing_add(self, rhs: Self) -> (Self, bool) {
let overflow = self > Self::default() && rhs > Self::default() && self > std::$t::MAX - rhs;
let underflow = !overflow && self < Self::default() && rhs < Self::default() && self < std::$t::MIN - rhs;
(self + rhs, overflow || underflow)
}
}
)*
};
);
impl_bounded_measure_float!(f32, f64);