blob: f970df7a5080bec277e2abbb0639d0e44eb4cdce [file] [log] [blame]
 //! Graph algorithms. //! //! It is a goal to gradually migrate the algorithms to be based on graph traits //! so that they are generally applicable. For now, most of these use only the //! **Graph** type. 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; /// Return `true` if the input graph contains a cycle. /// /// Always treats the input graph as if undirected. pub fn is_cyclic_undirected(g: &Graph) -> 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()); // union the two vertices of the edge // -- if they were already the same, then we have a cycle if !edge_sets.union(a.index(), b.index()) { return true } } false } /// **Deprecated: Renamed to `is_cyclic_undirected`.** pub fn is_cyclic(g: &Graph) -> bool where Ty: EdgeType, Ix: IndexType, { is_cyclic_undirected(g) } /// Perform a topological sort of a directed graph `g`. /// /// Visit each node in order (if it is part of a topological order). /// /// You can pass `g` as either **&Graph** or **&mut Graph**, and it /// will be passed on to the visitor closure. #[inline] fn toposort_generic(mut g: G, mut visit: F) where Ix: IndexType, G: Borrow>, F: FnMut(&mut G, NodeIndex), { let mut ordered = g.borrow().visit_map(); let mut tovisit = Vec::new(); // find all initial nodes tovisit.extend(g.borrow().externals(Incoming)); // Take an unvisited element and find which of its neighbors are next 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) { // Look at each neighbor, and those that only have incoming edges // from the already ordered list, they are the next to visit. if g.borrow().neighbors_directed(neigh, Incoming).all(|b| ordered.is_visited(&b)) { tovisit.push(neigh); } } } } /// Return `true` if the input directed graph contains a cycle. /// /// Using the topological sort algorithm. pub fn is_cyclic_directed(g: &Graph) -> bool where Ix: IndexType, { let mut n_ordered = 0; toposort_generic(g, |_, _| n_ordered += 1); n_ordered != g.node_count() } /// Perform a topological sort of a directed graph. /// /// Return a vector of nodes in topological order: each node is ordered /// before its successors. /// /// If the returned vec contains less than all the nodes of the graph, then /// the graph was cyclic. pub fn toposort(g: &Graph) -> Vec> where Ix: IndexType, { let mut order = Vec::with_capacity(g.node_count()); toposort_generic(g, |_, ix| order.push(ix)); order } /// Compute the *strongly connected components* using Kosaraju's algorithm. /// /// Return a vector where each element is an scc. /// /// For an undirected graph, the sccs are simply the connected components. pub fn scc(g: &Graph) -> Vec>> where Ty: EdgeType, Ix: IndexType, { let mut dfs = Dfs::empty(g); // First phase, reverse dfs pass, compute finishing times. // http://stackoverflow.com/a/26780899/161659 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) { // First time visiting `nx`: Push neighbors, don't pop `nx` for succ in g.neighbors_directed(nx, EdgeDirection::Incoming) { if !dfs.discovered.is_visited(&succ) { dfs.stack.push(succ); } } } else { dfs.stack.pop(); if finished.visit(nx) { // Second time: All reachable nodes must have been finished finish_order.push(nx); } } } } dfs.discovered.clear(); let mut sccs = Vec::new(); // Second phase // Process in decreasing finishing time order for &nindex in finish_order.iter().rev() { if dfs.discovered.is_visited(&nindex) { continue; } // Move to the leader node. dfs.move_to(nindex); //let leader = nindex; let mut scc = Vec::new(); while let Some(nx) = dfs.next(g) { scc.push(nx); } sccs.push(scc); } sccs } /// Condense every strongly connected component into a single node and return the result. /// /// If `make_acyclic` is true, self-loops and multi edges are ignored, guaranteeing that /// the output is acyclic. pub fn condensation(g: Graph, make_acyclic: bool) -> Graph, E, Ty, Ix> where Ty: EdgeType, Ix: IndexType, { let sccs = scc(&g); let mut condensed: Graph, E, Ty, Ix> = Graph::with_capacity(sccs.len(), g.edge_count()); // Build a map from old indices to new ones. 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; } } // Consume nodes and edges of the old graph and insert them into the new one. 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 } /// Return the number of connected components of the graph. /// /// For a directed graph, this is the *weakly* connected components. pub fn connected_components(g: &Graph) -> 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()); // union the two vertices of the edge vertex_sets.union(a.index(), b.index()); } let mut labels = vertex_sets.into_labeling(); labels.sort(); labels.dedup(); labels.len() } /// Compute a *minimum spanning tree* of a graph. /// /// Treat the input graph as undirected. /// /// Using Kruskal's algorithm with runtime **O(|E| log |E|)**. We actually /// return a minimum spanning forest, i.e. a minimum spanning tree for each connected /// component of the graph. /// /// The resulting graph has all the vertices of the input graph (with identical node indices), /// and **|V| - c** edges, where **c** is the number of connected components in `g`. pub fn min_spanning_tree(g: &Graph) -> Graph where N: Clone, E: Clone + PartialOrd, Ty: EdgeType, Ix: IndexType, { if g.node_count() == 0 { return Graph::with_capacity(0, 0) } // Create a mst skeleton by copying all nodes 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()); } // Initially each vertex is its own disjoint subgraph, track the connectedness // of the pre-MST with a union & find datastructure. 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()))); } // Kruskal's algorithm. // Algorithm is this: // // 1. Create a pre-MST with all the vertices and no edges. // 2. Repeat: // // a. Remove the shortest edge from the original graph. // b. If the edge connects two disjoint trees in the pre-MST, // add the edge. while let Some(MinScored(score, (a, b))) = sort_edges.pop() { // check if the edge would connect two disjoint parts 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 }