petgraph/algo/
mod.rs

1//! Graph algorithms.
2//!
3//! It is a goal to gradually migrate the algorithms to be based on graph traits
4//! so that they are generally applicable. For now, some of these still require
5//! the `Graph` type.
6
7pub mod dominators;
8
9use std::collections::BinaryHeap;
10use std::cmp::min;
11
12use prelude::*;
13
14use super::{
15    EdgeType,
16};
17use scored::MinScored;
18use super::visit::{
19    GraphRef,
20    GraphBase,
21    Visitable,
22    VisitMap,
23    IntoNeighbors,
24    IntoNeighborsDirected,
25    IntoNodeIdentifiers,
26    NodeCount,
27    NodeIndexable,
28    NodeCompactIndexable,
29    IntoEdgeReferences,
30    IntoEdges,
31    Reversed,
32};
33use super::unionfind::UnionFind;
34use super::graph::{
35    IndexType,
36};
37use visit::{Data, NodeRef, IntoNodeReferences};
38use data::{
39    Element,
40};
41
42pub use super::isomorphism::{
43    is_isomorphic,
44    is_isomorphic_matching,
45};
46pub use super::dijkstra::dijkstra;
47pub use super::astar::astar;
48
49/// [Generic] Return the number of connected components of the graph.
50///
51/// For a directed graph, this is the *weakly* connected components.
52pub fn connected_components<G>(g: G) -> usize
53    where G: NodeCompactIndexable + IntoEdgeReferences,
54{
55    let mut vertex_sets = UnionFind::new(g.node_bound());
56    for edge in g.edge_references() {
57        let (a, b) = (edge.source(), edge.target());
58
59        // union the two vertices of the edge
60        vertex_sets.union(g.to_index(a), g.to_index(b));
61    }
62    let mut labels = vertex_sets.into_labeling();
63    labels.sort();
64    labels.dedup();
65    labels.len()
66}
67
68
69/// [Generic] Return `true` if the input graph contains a cycle.
70///
71/// Always treats the input graph as if undirected.
72pub fn is_cyclic_undirected<G>(g: G) -> bool
73    where G: NodeIndexable + IntoEdgeReferences
74{
75    let mut edge_sets = UnionFind::new(g.node_bound());
76    for edge in g.edge_references() {
77        let (a, b) = (edge.source(), edge.target());
78
79        // union the two vertices of the edge
80        //  -- if they were already the same, then we have a cycle
81        if !edge_sets.union(g.to_index(a), g.to_index(b)) {
82            return true
83        }
84    }
85    false
86}
87
88
89/// [Generic] Perform a topological sort of a directed graph.
90///
91/// If the graph was acyclic, return a vector of nodes in topological order:
92/// each node is ordered before its successors.
93/// Otherwise, it will return a `Cycle` error. Self loops are also cycles.
94///
95/// To handle graphs with cycles, use the scc algorithms or `DfsPostOrder`
96/// instead of this function.
97///
98/// If `space` is not `None`, it is used instead of creating a new workspace for
99/// graph traversal. The implementation is iterative.
100pub fn toposort<G>(g: G, space: Option<&mut DfsSpace<G::NodeId, G::Map>>)
101    -> Result<Vec<G::NodeId>, Cycle<G::NodeId>>
102    where G: IntoNeighborsDirected + IntoNodeIdentifiers + Visitable,
103{
104    // based on kosaraju scc
105    with_dfs(g, space, |dfs| {
106        dfs.reset(g);
107        let mut finished = g.visit_map();
108
109        let mut finish_stack = Vec::new();
110        for i in g.node_identifiers() {
111            if dfs.discovered.is_visited(&i) {
112                continue;
113            }
114            dfs.stack.push(i);
115            while let Some(&nx) = dfs.stack.last() {
116                if dfs.discovered.visit(nx) {
117                    // First time visiting `nx`: Push neighbors, don't pop `nx`
118                    for succ in g.neighbors(nx) {
119                        if succ == nx {
120                            // self cycle
121                            return Err(Cycle(nx));
122                        }
123                        if !dfs.discovered.is_visited(&succ) {
124                            dfs.stack.push(succ);
125                        } 
126                    }
127                } else {
128                    dfs.stack.pop();
129                    if finished.visit(nx) {
130                        // Second time: All reachable nodes must have been finished
131                        finish_stack.push(nx);
132                    }
133                }
134            }
135        }
136        finish_stack.reverse();
137
138        dfs.reset(g);
139        for &i in &finish_stack {
140            dfs.move_to(i);
141            let mut cycle = false;
142            while let Some(j) = dfs.next(Reversed(g)) {
143                if cycle {
144                    return Err(Cycle(j));
145                }
146                cycle = true;
147            }
148        }
149
150        Ok(finish_stack)
151    })
152}
153
154/// [Generic] Return `true` if the input directed graph contains a cycle.
155///
156/// This implementation is recursive; use `toposort` if an alternative is
157/// needed.
158pub fn is_cyclic_directed<G>(g: G) -> bool
159    where G: IntoNodeIdentifiers + IntoNeighbors + Visitable,
160{
161    use visit::{depth_first_search, DfsEvent};
162
163    depth_first_search(g, g.node_identifiers(), |event| {
164        match event {
165            DfsEvent::BackEdge(_, _) => Err(()),
166            _ => Ok(()),
167        }
168    }).is_err()
169}
170
171type DfsSpaceType<G> = DfsSpace<<G as GraphBase>::NodeId, <G as Visitable>::Map>;
172
173/// Workspace for a graph traversal.
174#[derive(Clone, Debug)]
175pub struct DfsSpace<N, VM> {
176    dfs: Dfs<N, VM>,
177}
178
179impl<N, VM> DfsSpace<N, VM>
180    where N: Copy + PartialEq,
181          VM: VisitMap<N>,
182{
183    pub fn new<G>(g: G) -> Self
184        where G: GraphRef + Visitable<NodeId=N, Map=VM>,
185    {
186        DfsSpace {
187            dfs: Dfs::empty(g)
188        }
189    }
190}
191
192impl<N, VM> Default for DfsSpace<N, VM>
193    where VM: VisitMap<N> + Default,
194{
195    fn default() -> Self {
196        DfsSpace {
197            dfs: Dfs {
198                stack: <_>::default(),
199                discovered: <_>::default(),
200            }
201        }
202    }
203}
204
205/// Create a Dfs if it's needed
206fn with_dfs<G, F, R>(g: G, space: Option<&mut DfsSpaceType<G>>, f: F) -> R
207    where G: GraphRef + Visitable,
208          F: FnOnce(&mut Dfs<G::NodeId, G::Map>) -> R
209{
210    let mut local_visitor;
211    let dfs = if let Some(v) = space { &mut v.dfs } else {
212        local_visitor = Dfs::empty(g);
213        &mut local_visitor
214    };
215    f(dfs)
216}
217
218/// [Generic] Check if there exists a path starting at `from` and reaching `to`.
219///
220/// If `from` and `to` are equal, this function returns true.
221///
222/// If `space` is not `None`, it is used instead of creating a new workspace for
223/// graph traversal.
224pub fn has_path_connecting<G>(g: G, from: G::NodeId, to: G::NodeId,
225                              space: Option<&mut DfsSpace<G::NodeId, G::Map>>)
226    -> bool
227    where G: IntoNeighbors + Visitable,
228{
229    with_dfs(g, space, |dfs| {
230        dfs.reset(g);
231        dfs.move_to(from);
232        while let Some(x) = dfs.next(g) {
233            if x == to {
234                return true;
235            }
236        }
237        false
238    })
239}
240
241/// Renamed to `kosaraju_scc`.
242#[deprecated(note = "renamed to kosaraju_scc")]
243pub fn scc<G>(g: G) -> Vec<Vec<G::NodeId>>
244    where G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
245{
246    kosaraju_scc(g)
247}
248
249/// [Generic] Compute the *strongly connected components* using [Kosaraju's algorithm][1].
250///
251/// [1]: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
252///
253/// Return a vector where each element is a strongly connected component (scc).
254/// The order of node ids within each scc is arbitrary, but the order of
255/// the sccs is their postorder (reverse topological sort).
256///
257/// For an undirected graph, the sccs are simply the connected components.
258///
259/// This implementation is iterative and does two passes over the nodes.
260pub fn kosaraju_scc<G>(g: G) -> Vec<Vec<G::NodeId>>
261    where G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
262{
263    let mut dfs = DfsPostOrder::empty(g);
264
265    // First phase, reverse dfs pass, compute finishing times.
266    // http://stackoverflow.com/a/26780899/161659
267    let mut finish_order = Vec::with_capacity(0);
268    for i in g.node_identifiers() {
269        if dfs.discovered.is_visited(&i) {
270            continue
271        }
272
273        dfs.move_to(i);
274        while let Some(nx) = dfs.next(Reversed(g)) {
275            finish_order.push(nx);
276        }
277    }
278
279    let mut dfs = Dfs::from_parts(dfs.stack, dfs.discovered);
280    dfs.reset(g);
281    let mut sccs = Vec::new();
282
283    // Second phase
284    // Process in decreasing finishing time order
285    for i in finish_order.into_iter().rev() {
286        if dfs.discovered.is_visited(&i) {
287            continue;
288        }
289        // Move to the leader node `i`.
290        dfs.move_to(i);
291        let mut scc = Vec::new();
292        while let Some(nx) = dfs.next(g) {
293            scc.push(nx);
294        }
295        sccs.push(scc);
296    }
297    sccs
298}
299
300/// [Generic] Compute the *strongly connected components* using [Tarjan's algorithm][1].
301///
302/// [1]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
303///
304/// Return a vector where each element is a strongly connected component (scc).
305/// The order of node ids within each scc is arbitrary, but the order of
306/// the sccs is their postorder (reverse topological sort).
307///
308/// For an undirected graph, the sccs are simply the connected components.
309///
310/// This implementation is recursive and does one pass over the nodes.
311pub fn tarjan_scc<G>(g: G) -> Vec<Vec<G::NodeId>>
312    where G: IntoNodeIdentifiers + IntoNeighbors + NodeIndexable
313{
314    #[derive(Copy, Clone)]
315    #[derive(Debug)]
316    struct NodeData {
317        index: Option<usize>,
318        lowlink: usize,
319        on_stack: bool,
320    }
321
322    #[derive(Debug)]
323    struct Data<'a, G>
324        where G: NodeIndexable, 
325          G::NodeId: 'a
326    {
327        index: usize,
328        nodes: Vec<NodeData>,
329        stack: Vec<G::NodeId>,
330        sccs: &'a mut Vec<Vec<G::NodeId>>,
331    }
332
333    fn scc_visit<G>(v: G::NodeId, g: G, data: &mut Data<G>) 
334        where G: IntoNeighbors + NodeIndexable
335    {
336        macro_rules! node {
337            ($node:expr) => (data.nodes[g.to_index($node)])
338        }
339
340        if node![v].index.is_some() {
341            // already visited
342            return;
343        }
344
345        let v_index = data.index;
346        node![v].index = Some(v_index);
347        node![v].lowlink = v_index;
348        node![v].on_stack = true;
349        data.stack.push(v);
350        data.index += 1;
351
352        for w in g.neighbors(v) {
353            match node![w].index {
354                None => {
355                    scc_visit(w, g, data);
356                    node![v].lowlink = min(node![v].lowlink, node![w].lowlink);
357                }
358                Some(w_index) => {
359                    if node![w].on_stack {
360                        // Successor w is in stack S and hence in the current SCC
361                        let v_lowlink = &mut node![v].lowlink;
362                        *v_lowlink = min(*v_lowlink, w_index);
363                    }
364                }
365            }
366        }
367
368        // If v is a root node, pop the stack and generate an SCC
369        if let Some(v_index) = node![v].index {
370            if node![v].lowlink == v_index {
371                let mut cur_scc = Vec::new();
372                loop {
373                    let w = data.stack.pop().unwrap();
374                    node![w].on_stack = false;
375                    cur_scc.push(w);
376                    if g.to_index(w) == g.to_index(v) { break; }
377                }
378                data.sccs.push(cur_scc);
379            }
380        }
381    }
382
383    let mut sccs = Vec::new();
384    {
385        let map = vec![NodeData { index: None, lowlink: !0, on_stack: false }; g.node_bound()];
386
387        let mut data = Data {
388            index: 0,
389            nodes: map,
390            stack: Vec::new(),
391            sccs: &mut sccs,
392        };
393
394        for n in g.node_identifiers() {
395            scc_visit(n, g, &mut data);
396        }
397    }
398    sccs
399}
400
401/// [Graph] Condense every strongly connected component into a single node and return the result.
402///
403/// If `make_acyclic` is true, self-loops and multi edges are ignored, guaranteeing that
404/// the output is acyclic.
405pub fn condensation<N, E, Ty, Ix>(g: Graph<N, E, Ty, Ix>, make_acyclic: bool) -> Graph<Vec<N>, E, Ty, Ix>
406    where Ty: EdgeType,
407          Ix: IndexType,
408{
409    let sccs = kosaraju_scc(&g);
410    let mut condensed: Graph<Vec<N>, E, Ty, Ix> = Graph::with_capacity(sccs.len(), g.edge_count());
411
412    // Build a map from old indices to new ones.
413    let mut node_map = vec![NodeIndex::end(); g.node_count()];
414    for comp in sccs {
415        let new_nix = condensed.add_node(Vec::new());
416        for nix in comp {
417            node_map[nix.index()] = new_nix;
418        }
419    }
420
421    // Consume nodes and edges of the old graph and insert them into the new one.
422    let (nodes, edges) = g.into_nodes_edges();
423    for (nix, node) in nodes.into_iter().enumerate() {
424        condensed[node_map[nix]].push(node.weight);
425    }
426    for edge in edges {
427        let source = node_map[edge.source().index()];
428        let target = node_map[edge.target().index()];
429        if make_acyclic {
430            if source != target {
431                condensed.update_edge(source, target, edge.weight);
432            }
433        } else {
434            condensed.add_edge(source, target, edge.weight);
435        }
436    }
437    condensed
438}
439
440/// [Generic] Compute a *minimum spanning tree* of a graph.
441///
442/// The input graph is treated as if undirected.
443///
444/// Using Kruskal's algorithm with runtime **O(|E| log |E|)**. We actually
445/// return a minimum spanning forest, i.e. a minimum spanning tree for each connected
446/// component of the graph.
447///
448/// The resulting graph has all the vertices of the input graph (with identical node indices),
449/// and **|V| - c** edges, where **c** is the number of connected components in `g`.
450///
451/// Use `from_elements` to create a graph from the resulting iterator.
452pub fn min_spanning_tree<G>(g: G) -> MinSpanningTree<G>
453    where G::NodeWeight: Clone,
454          G::EdgeWeight: Clone + PartialOrd,
455          G: IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
456{
457
458    // Initially each vertex is its own disjoint subgraph, track the connectedness
459    // of the pre-MST with a union & find datastructure.
460    let subgraphs = UnionFind::new(g.node_bound());
461
462    let edges = g.edge_references();
463    let mut sort_edges = BinaryHeap::with_capacity(edges.size_hint().0);
464    for edge in edges {
465        sort_edges.push(MinScored(edge.weight().clone(), (edge.source(), edge.target())));
466    }
467
468    MinSpanningTree {
469        graph: g,
470        node_ids: Some(g.node_references()),
471        subgraphs: subgraphs,
472        sort_edges: sort_edges,
473    }
474
475}
476
477/// An iterator producing a minimum spanning forest of a graph.
478pub struct MinSpanningTree<G>
479    where G: Data + IntoNodeReferences,
480{
481    graph: G,
482    node_ids: Option<G::NodeReferences>,
483    subgraphs: UnionFind<usize>,
484    sort_edges: BinaryHeap<MinScored<G::EdgeWeight, (G::NodeId, G::NodeId)>>,
485}
486
487
488impl<G> Iterator for MinSpanningTree<G>
489    where G: IntoNodeReferences + NodeIndexable,
490          G::NodeWeight: Clone,
491          G::EdgeWeight: PartialOrd,
492{
493    type Item = Element<G::NodeWeight, G::EdgeWeight>;
494
495    fn next(&mut self) -> Option<Self::Item> {
496        if let Some(ref mut iter) = self.node_ids {
497            if let Some(node) = iter.next() {
498                return Some(Element::Node { weight: node.weight().clone() });
499            }
500        }
501        self.node_ids = None;
502
503        // Kruskal's algorithm.
504        // Algorithm is this:
505        //
506        // 1. Create a pre-MST with all the vertices and no edges.
507        // 2. Repeat:
508        //
509        //  a. Remove the shortest edge from the original graph.
510        //  b. If the edge connects two disjoint trees in the pre-MST,
511        //     add the edge.
512        while let Some(MinScored(score, (a, b))) = self.sort_edges.pop() {
513            let g = self.graph;
514            // check if the edge would connect two disjoint parts
515            if self.subgraphs.union(g.to_index(a), g.to_index(b)) {
516                return Some(Element::Edge {
517                    source: g.to_index(a),
518                    target: g.to_index(b),
519                    weight: score,
520                });
521            }
522        }
523        None
524    }
525}
526
527/// An algorithm error: a cycle was found in the graph.
528#[derive(Clone, Debug, PartialEq)]
529pub struct Cycle<N>(N);
530
531impl<N> Cycle<N> {
532    /// Return a node id that participates in the cycle
533    pub fn node_id(&self) -> N
534        where N: Copy
535    {
536        self.0
537    }
538}
539/// An algorithm error: a cycle of negative weights was found in the graph.
540#[derive(Clone, Debug, PartialEq)]
541pub struct NegativeCycle(());
542
543/// [Generic] Compute shortest paths from node `source` to all other.
544///
545/// Using the [Bellman–Ford algorithm][bf]; negative edge costs are
546/// permitted, but the graph must not have a cycle of negative weights
547/// (in that case it will return an error).
548///
549/// On success, return one vec with path costs, and another one which points
550/// out the predecessor of a node along a shortest path. The vectors
551/// are indexed by the graph's node indices.
552///
553/// [bf]: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
554pub fn bellman_ford<G>(g: G, source: G::NodeId)
555    -> Result<(Vec<G::EdgeWeight>, Vec<Option<G::NodeId>>), NegativeCycle>
556    where G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable,
557          G::EdgeWeight: FloatMeasure,
558{
559    let mut predecessor = vec![None; g.node_bound()];
560    let mut distance = vec![<_>::infinite(); g.node_bound()];
561
562    let ix = |i| g.to_index(i);
563
564    distance[ix(source)] = <_>::zero();
565    // scan up to |V| - 1 times.
566    for _ in 1..g.node_count() {
567        let mut did_update = false;
568        for i in g.node_identifiers() {
569            for edge in g.edges(i) {
570                let i = edge.source();
571                let j = edge.target();
572                let w = *edge.weight();
573                if distance[ix(i)] + w < distance[ix(j)] {
574                    distance[ix(j)] = distance[ix(i)] + w;
575                    predecessor[ix(j)] = Some(i);
576                    did_update = true;
577                }
578            }
579        }
580        if !did_update {
581            break;
582        }
583    }
584
585    // check for negative weight cycle
586    for i in g.node_identifiers() {
587        for edge in g.edges(i) {
588            let j = edge.target();
589            let w = *edge.weight();
590            if distance[ix(i)] + w < distance[ix(j)] {
591                //println!("neg cycle, detected from {} to {}, weight={}", i, j, w);
592                return Err(NegativeCycle(()));
593            }
594        }
595    }
596
597    Ok((distance, predecessor))
598}
599
600use std::ops::Add;
601use std::fmt::Debug;
602
603/// Associated data that can be used for measures (such as length).
604pub trait Measure : Debug + PartialOrd + Add<Self, Output=Self> + Default + Clone {
605}
606
607impl<M> Measure for M
608    where M: Debug + PartialOrd + Add<M, Output=M> + Default + Clone,
609{ }
610
611/// A floating-point measure.
612pub trait FloatMeasure : Measure + Copy {
613    fn zero() -> Self;
614    fn infinite() -> Self;
615}
616
617impl FloatMeasure for f32 {
618    fn zero() -> Self { 0. }
619    fn infinite() -> Self { 1./0. }
620}
621
622impl FloatMeasure for f64 {
623    fn zero() -> Self { 0. }
624    fn infinite() -> Self { 1./0. }
625}
626
petgraph/algo/mod.rs

petgraph/algo/
mod.rs
