vendor/petgraph/src/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
   7 pub mod dominators;
   8
   9 use std::cmp::min;
  10 use std::collections::{BinaryHeap, HashMap};
  11
  12 use crate::prelude::*;
  13
  14 use super::graph::IndexType;
  15 use super::unionfind::UnionFind;
  16 use super::visit::{
  17     GraphBase, GraphRef, IntoEdgeReferences, IntoEdges, IntoNeighbors, IntoNeighborsDirected,
  18     IntoNodeIdentifiers, NodeCompactIndexable, NodeCount, NodeIndexable, Reversed, VisitMap,
  19     Visitable,
  20 };
  21 use super::EdgeType;
  22 use crate::data::Element;
  23 use crate::scored::MinScored;
  24 use crate::visit::Walker;
  25 use crate::visit::{Data, IntoNodeReferences, NodeRef};
  26
  27 pub use super::astar::astar;
  28 pub use super::dijkstra::dijkstra;
  29 pub use super::isomorphism::{is_isomorphic, is_isomorphic_matching};
  30 pub use super::simple_paths::all_simple_paths;
  31
  32 /// \[Generic\] Return the number of connected components of the graph.
  33 ///
  34 /// For a directed graph, this is the *weakly* connected components.
  35 /// # Example
  36 /// ```rust
  37 /// use petgraph::Graph;
  38 /// use petgraph::algo::connected_components;
  39 /// use petgraph::prelude::*;
  40 ///
  41 /// let mut graph : Graph<(),(),Directed>= Graph::new();
  42 /// let a = graph.add_node(()); // node with no weight
  43 /// let b = graph.add_node(());
  44 /// let c = graph.add_node(());
  45 /// let d = graph.add_node(());
  46 /// let e = graph.add_node(());
  47 /// let f = graph.add_node(());
  48 /// let g = graph.add_node(());
  49 /// let h = graph.add_node(());
  50 ///
  51 /// graph.extend_with_edges(&[
  52 ///     (a, b),
  53 ///     (b, c),
  54 ///     (c, d),
  55 ///     (d, a),
  56 ///     (e, f),
  57 ///     (f, g),
  58 ///     (g, h),
  59 ///     (h, e)
  60 /// ]);
  61 /// // a ----> b       e ----> f
  62 /// // ^       |       ^       |
  63 /// // |       v       |       v
  64 /// // d <---- c       h <---- g
  65 ///
  66 /// assert_eq!(connected_components(&graph),2);
  67 /// graph.add_edge(b,e,());
  68 /// assert_eq!(connected_components(&graph),1);
  69 /// ```
  70 pub fn connected_components<G>(g: G) -> usize
  71 where
  72     G: NodeCompactIndexable + IntoEdgeReferences,
  73 {
  74     let mut vertex_sets = UnionFind::new(g.node_bound());
  75     for edge in g.edge_references() {
  76         let (a, b) = (edge.source(), edge.target());
  77
  78         // union the two vertices of the edge
  79         vertex_sets.union(g.to_index(a), g.to_index(b));
  80     }
  81     let mut labels = vertex_sets.into_labeling();
  82     labels.sort();
  83     labels.dedup();
  84     labels.len()
  85 }
  86
  87 /// \[Generic\] Return `true` if the input graph contains a cycle.
  88 ///
  89 /// Always treats the input graph as if undirected.
  90 pub fn is_cyclic_undirected<G>(g: G) -> bool
  91 where
  92     G: NodeIndexable + IntoEdgeReferences,
  93 {
  94     let mut edge_sets = UnionFind::new(g.node_bound());
  95     for edge in g.edge_references() {
  96         let (a, b) = (edge.source(), edge.target());
  97
  98         // union the two vertices of the edge
  99         //  -- if they were already the same, then we have a cycle
 100         if !edge_sets.union(g.to_index(a), g.to_index(b)) {
 101             return true;
 102         }
 103     }
 104     false
 105 }
 106
 107 /// \[Generic\] Perform a topological sort of a directed graph.
 108 ///
 109 /// If the graph was acyclic, return a vector of nodes in topological order:
 110 /// each node is ordered before its successors.
 111 /// Otherwise, it will return a `Cycle` error. Self loops are also cycles.
 112 ///
 113 /// To handle graphs with cycles, use the scc algorithms or `DfsPostOrder`
 114 /// instead of this function.
 115 ///
 116 /// If `space` is not `None`, it is used instead of creating a new workspace for
 117 /// graph traversal. The implementation is iterative.
 118 pub fn toposort<G>(
 119     g: G,
 120     space: Option<&mut DfsSpace<G::NodeId, G::Map>>,
 121 ) -> Result<Vec<G::NodeId>, Cycle<G::NodeId>>
 122 where
 123     G: IntoNeighborsDirected + IntoNodeIdentifiers + Visitable,
 124 {
 125     // based on kosaraju scc
 126     with_dfs(g, space, |dfs| {
 127         dfs.reset(g);
 128         let mut finished = g.visit_map();
 129
 130         let mut finish_stack = Vec::new();
 131         for i in g.node_identifiers() {
 132             if dfs.discovered.is_visited(&i) {
 133                 continue;
 134             }
 135             dfs.stack.push(i);
 136             while let Some(&nx) = dfs.stack.last() {
 137                 if dfs.discovered.visit(nx) {
 138                     // First time visiting `nx`: Push neighbors, don't pop `nx`
 139                     for succ in g.neighbors(nx) {
 140                         if succ == nx {
 141                             // self cycle
 142                             return Err(Cycle(nx));
 143                         }
 144                         if !dfs.discovered.is_visited(&succ) {
 145                             dfs.stack.push(succ);
 146                         }
 147                     }
 148                 } else {
 149                     dfs.stack.pop();
 150                     if finished.visit(nx) {
 151                         // Second time: All reachable nodes must have been finished
 152                         finish_stack.push(nx);
 153                     }
 154                 }
 155             }
 156         }
 157         finish_stack.reverse();
 158
 159         dfs.reset(g);
 160         for &i in &finish_stack {
 161             dfs.move_to(i);
 162             let mut cycle = false;
 163             while let Some(j) = dfs.next(Reversed(g)) {
 164                 if cycle {
 165                     return Err(Cycle(j));
 166                 }
 167                 cycle = true;
 168             }
 169         }
 170
 171         Ok(finish_stack)
 172     })
 173 }
 174
 175 /// \[Generic\] Return `true` if the input directed graph contains a cycle.
 176 ///
 177 /// This implementation is recursive; use `toposort` if an alternative is
 178 /// needed.
 179 pub fn is_cyclic_directed<G>(g: G) -> bool
 180 where
 181     G: IntoNodeIdentifiers + IntoNeighbors + Visitable,
 182 {
 183     use crate::visit::{depth_first_search, DfsEvent};
 184
 185     depth_first_search(g, g.node_identifiers(), |event| match event {
 186         DfsEvent::BackEdge(_, _) => Err(()),
 187         _ => Ok(()),
 188     })
 189     .is_err()
 190 }
 191
 192 type DfsSpaceType<G> = DfsSpace<<G as GraphBase>::NodeId, <G as Visitable>::Map>;
 193
 194 /// Workspace for a graph traversal.
 195 #[derive(Clone, Debug)]
 196 pub struct DfsSpace<N, VM> {
 197     dfs: Dfs<N, VM>,
 198 }
 199
 200 impl<N, VM> DfsSpace<N, VM>
 201 where
 202     N: Copy + PartialEq,
 203     VM: VisitMap<N>,
 204 {
 205     pub fn new<G>(g: G) -> Self
 206     where
 207         G: GraphRef + Visitable<NodeId = N, Map = VM>,
 208     {
 209         DfsSpace { dfs: Dfs::empty(g) }
 210     }
 211 }
 212
 213 impl<N, VM> Default for DfsSpace<N, VM>
 214 where
 215     VM: VisitMap<N> + Default,
 216 {
 217     fn default() -> Self {
 218         DfsSpace {
 219             dfs: Dfs {
 220                 stack: <_>::default(),
 221                 discovered: <_>::default(),
 222             },
 223         }
 224     }
 225 }
 226
 227 /// Create a Dfs if it's needed
 228 fn with_dfs<G, F, R>(g: G, space: Option<&mut DfsSpaceType<G>>, f: F) -> R
 229 where
 230     G: GraphRef + Visitable,
 231     F: FnOnce(&mut Dfs<G::NodeId, G::Map>) -> R,
 232 {
 233     let mut local_visitor;
 234     let dfs = if let Some(v) = space {
 235         &mut v.dfs
 236     } else {
 237         local_visitor = Dfs::empty(g);
 238         &mut local_visitor
 239     };
 240     f(dfs)
 241 }
 242
 243 /// \[Generic\] Check if there exists a path starting at `from` and reaching `to`.
 244 ///
 245 /// If `from` and `to` are equal, this function returns true.
 246 ///
 247 /// If `space` is not `None`, it is used instead of creating a new workspace for
 248 /// graph traversal.
 249 pub fn has_path_connecting<G>(
 250     g: G,
 251     from: G::NodeId,
 252     to: G::NodeId,
 253     space: Option<&mut DfsSpace<G::NodeId, G::Map>>,
 254 ) -> bool
 255 where
 256     G: IntoNeighbors + Visitable,
 257 {
 258     with_dfs(g, space, |dfs| {
 259         dfs.reset(g);
 260         dfs.move_to(from);
 261         dfs.iter(g).any(|x| x == to)
 262     })
 263 }
 264
 265 /// Renamed to `kosaraju_scc`.
 266 #[deprecated(note = "renamed to kosaraju_scc")]
 267 pub fn scc<G>(g: G) -> Vec<Vec<G::NodeId>>
 268 where
 269     G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
 270 {
 271     kosaraju_scc(g)
 272 }
 273
 274 /// \[Generic\] Compute the *strongly connected components* using [Kosaraju's algorithm][1].
 275 ///
 276 /// [1]: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
 277 ///
 278 /// Return a vector where each element is a strongly connected component (scc).
 279 /// The order of node ids within each scc is arbitrary, but the order of
 280 /// the sccs is their postorder (reverse topological sort).
 281 ///
 282 /// For an undirected graph, the sccs are simply the connected components.
 283 ///
 284 /// This implementation is iterative and does two passes over the nodes.
 285 pub fn kosaraju_scc<G>(g: G) -> Vec<Vec<G::NodeId>>
 286 where
 287     G: IntoNeighborsDirected + Visitable + IntoNodeIdentifiers,
 288 {
 289     let mut dfs = DfsPostOrder::empty(g);
 290
 291     // First phase, reverse dfs pass, compute finishing times.
 292     // http://stackoverflow.com/a/26780899/161659
 293     let mut finish_order = Vec::with_capacity(0);
 294     for i in g.node_identifiers() {
 295         if dfs.discovered.is_visited(&i) {
 296             continue;
 297         }
 298
 299         dfs.move_to(i);
 300         while let Some(nx) = dfs.next(Reversed(g)) {
 301             finish_order.push(nx);
 302         }
 303     }
 304
 305     let mut dfs = Dfs::from_parts(dfs.stack, dfs.discovered);
 306     dfs.reset(g);
 307     let mut sccs = Vec::new();
 308
 309     // Second phase
 310     // Process in decreasing finishing time order
 311     for i in finish_order.into_iter().rev() {
 312         if dfs.discovered.is_visited(&i) {
 313             continue;
 314         }
 315         // Move to the leader node `i`.
 316         dfs.move_to(i);
 317         let mut scc = Vec::new();
 318         while let Some(nx) = dfs.next(g) {
 319             scc.push(nx);
 320         }
 321         sccs.push(scc);
 322     }
 323     sccs
 324 }
 325
 326 /// \[Generic\] Compute the *strongly connected components* using [Tarjan's algorithm][1].
 327 ///
 328 /// [1]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
 329 ///
 330 /// Return a vector where each element is a strongly connected component (scc).
 331 /// The order of node ids within each scc is arbitrary, but the order of
 332 /// the sccs is their postorder (reverse topological sort).
 333 ///
 334 /// For an undirected graph, the sccs are simply the connected components.
 335 ///
 336 /// This implementation is recursive and does one pass over the nodes.
 337 pub fn tarjan_scc<G>(g: G) -> Vec<Vec<G::NodeId>>
 338 where
 339     G: IntoNodeIdentifiers + IntoNeighbors + NodeIndexable,
 340 {
 341     #[derive(Copy, Clone, Debug)]
 342     struct NodeData {
 343         index: Option<usize>,
 344         lowlink: usize,
 345         on_stack: bool,
 346     }
 347
 348     #[derive(Debug)]
 349     struct Data<'a, G>
 350     where
 351         G: NodeIndexable,
 352         G::NodeId: 'a,
 353     {
 354         index: usize,
 355         nodes: Vec<NodeData>,
 356         stack: Vec<G::NodeId>,
 357         sccs: &'a mut Vec<Vec<G::NodeId>>,
 358     }
 359
 360     fn scc_visit<G>(v: G::NodeId, g: G, data: &mut Data<G>)
 361     where
 362         G: IntoNeighbors + NodeIndexable,
 363     {
 364         macro_rules! node {
 365             ($node:expr) => {
 366                 data.nodes[g.to_index($node)]
 367             };
 368         }
 369
 370         if node![v].index.is_some() {
 371             // already visited
 372             return;
 373         }
 374
 375         let v_index = data.index;
 376         node![v].index = Some(v_index);
 377         node![v].lowlink = v_index;
 378         node![v].on_stack = true;
 379         data.stack.push(v);
 380         data.index += 1;
 381
 382         for w in g.neighbors(v) {
 383             match node![w].index {
 384                 None => {
 385                     scc_visit(w, g, data);
 386                     node![v].lowlink = min(node![v].lowlink, node![w].lowlink);
 387                 }
 388                 Some(w_index) => {
 389                     if node![w].on_stack {
 390                         // Successor w is in stack S and hence in the current SCC
 391                         let v_lowlink = &mut node![v].lowlink;
 392                         *v_lowlink = min(*v_lowlink, w_index);
 393                     }
 394                 }
 395             }
 396         }
 397
 398         // If v is a root node, pop the stack and generate an SCC
 399         if let Some(v_index) = node![v].index {
 400             if node![v].lowlink == v_index {
 401                 let mut cur_scc = Vec::new();
 402                 loop {
 403                     let w = data.stack.pop().unwrap();
 404                     node![w].on_stack = false;
 405                     cur_scc.push(w);
 406                     if g.to_index(w) == g.to_index(v) {
 407                         break;
 408                     }
 409                 }
 410                 data.sccs.push(cur_scc);
 411             }
 412         }
 413     }
 414
 415     let mut sccs = Vec::new();
 416     {
 417         let map = vec![
 418             NodeData {
 419                 index: None,
 420                 lowlink: !0,
 421                 on_stack: false
 422             };
 423             g.node_bound()
 424         ];
 425
 426         let mut data = Data {
 427             index: 0,
 428             nodes: map,
 429             stack: Vec::new(),
 430             sccs: &mut sccs,
 431         };
 432
 433         for n in g.node_identifiers() {
 434             scc_visit(n, g, &mut data);
 435         }
 436     }
 437     sccs
 438 }
 439
 440 /// [Graph] Condense every strongly connected component into a single node and return the result.
 441 ///
 442 /// If `make_acyclic` is true, self-loops and multi edges are ignored, guaranteeing that
 443 /// the output is acyclic.
 444 /// # Example
 445 /// ```rust
 446 /// use petgraph::Graph;
 447 /// use petgraph::algo::condensation;
 448 /// use petgraph::prelude::*;
 449 ///
 450 /// let mut graph : Graph<(),(),Directed> = Graph::new();
 451 /// let a = graph.add_node(()); // node with no weight
 452 /// let b = graph.add_node(());
 453 /// let c = graph.add_node(());
 454 /// let d = graph.add_node(());
 455 /// let e = graph.add_node(());
 456 /// let f = graph.add_node(());
 457 /// let g = graph.add_node(());
 458 /// let h = graph.add_node(());
 459 ///
 460 /// graph.extend_with_edges(&[
 461 ///     (a, b),
 462 ///     (b, c),
 463 ///     (c, d),
 464 ///     (d, a),
 465 ///     (b, e),
 466 ///     (e, f),
 467 ///     (f, g),
 468 ///     (g, h),
 469 ///     (h, e)
 470 /// ]);
 471 ///
 472 /// // a ----> b ----> e ----> f
 473 /// // ^       |       ^       |
 474 /// // |       v       |       v
 475 /// // d <---- c       h <---- g
 476 ///
 477 /// let condensed_graph = condensation(graph,false);
 478 /// let A = NodeIndex::new(0);
 479 /// let B = NodeIndex::new(1);
 480 /// assert_eq!(condensed_graph.node_count(), 2);
 481 /// assert_eq!(condensed_graph.edge_count(), 9);
 482 /// assert_eq!(condensed_graph.neighbors(A).collect::<Vec<_>>(), vec![A, A, A, A]);
 483 /// assert_eq!(condensed_graph.neighbors(B).collect::<Vec<_>>(), vec![A, B, B, B, B]);
 484 /// ```
 485 /// If `make_acyclic` is true, self-loops and multi edges are ignored:
 486 ///
 487 /// ```rust
 488 /// # use petgraph::Graph;
 489 /// # use petgraph::algo::condensation;
 490 /// # use petgraph::prelude::*;
 491 /// #
 492 /// # let mut graph : Graph<(),(),Directed> = Graph::new();
 493 /// # let a = graph.add_node(()); // node with no weight
 494 /// # let b = graph.add_node(());
 495 /// # let c = graph.add_node(());
 496 /// # let d = graph.add_node(());
 497 /// # let e = graph.add_node(());
 498 /// # let f = graph.add_node(());
 499 /// # let g = graph.add_node(());
 500 /// # let h = graph.add_node(());
 501 /// #
 502 /// # graph.extend_with_edges(&[
 503 /// #    (a, b),
 504 /// #    (b, c),
 505 /// #    (c, d),
 506 /// #    (d, a),
 507 /// #    (b, e),
 508 /// #    (e, f),
 509 /// #    (f, g),
 510 /// #    (g, h),
 511 /// #    (h, e)
 512 /// # ]);
 513 /// let acyclic_condensed_graph = condensation(graph, true);
 514 /// let A = NodeIndex::new(0);
 515 /// let B = NodeIndex::new(1);
 516 /// assert_eq!(acyclic_condensed_graph.node_count(), 2);
 517 /// assert_eq!(acyclic_condensed_graph.edge_count(), 1);
 518 /// assert_eq!(acyclic_condensed_graph.neighbors(B).collect::<Vec<_>>(), vec![A]);
 519 /// ```
 520 pub fn condensation<N, E, Ty, Ix>(
 521     g: Graph<N, E, Ty, Ix>,
 522     make_acyclic: bool,
 523 ) -> Graph<Vec<N>, E, Ty, Ix>
 524 where
 525     Ty: EdgeType,
 526     Ix: IndexType,
 527 {
 528     let sccs = kosaraju_scc(&g);
 529     let mut condensed: Graph<Vec<N>, E, Ty, Ix> = Graph::with_capacity(sccs.len(), g.edge_count());
 530
 531     // Build a map from old indices to new ones.
 532     let mut node_map = vec![NodeIndex::end(); g.node_count()];
 533     for comp in sccs {
 534         let new_nix = condensed.add_node(Vec::new());
 535         for nix in comp {
 536             node_map[nix.index()] = new_nix;
 537         }
 538     }
 539
 540     // Consume nodes and edges of the old graph and insert them into the new one.
 541     let (nodes, edges) = g.into_nodes_edges();
 542     for (nix, node) in nodes.into_iter().enumerate() {
 543         condensed[node_map[nix]].push(node.weight);
 544     }
 545     for edge in edges {
 546         let source = node_map[edge.source().index()];
 547         let target = node_map[edge.target().index()];
 548         if make_acyclic {
 549             if source != target {
 550                 condensed.update_edge(source, target, edge.weight);
 551             }
 552         } else {
 553             condensed.add_edge(source, target, edge.weight);
 554         }
 555     }
 556     condensed
 557 }
 558
 559 /// \[Generic\] Compute a *minimum spanning tree* of a graph.
 560 ///
 561 /// The input graph is treated as if undirected.
 562 ///
 563 /// Using Kruskal's algorithm with runtime **O(|E| log |E|)**. We actually
 564 /// return a minimum spanning forest, i.e. a minimum spanning tree for each connected
 565 /// component of the graph.
 566 ///
 567 /// The resulting graph has all the vertices of the input graph (with identical node indices),
 568 /// and **|V| - c** edges, where **c** is the number of connected components in `g`.
 569 ///
 570 /// Use `from_elements` to create a graph from the resulting iterator.
 571 pub fn min_spanning_tree<G>(g: G) -> MinSpanningTree<G>
 572 where
 573     G::NodeWeight: Clone,
 574     G::EdgeWeight: Clone + PartialOrd,
 575     G: IntoNodeReferences + IntoEdgeReferences + NodeIndexable,
 576 {
 577     // Initially each vertex is its own disjoint subgraph, track the connectedness
 578     // of the pre-MST with a union & find datastructure.
 579     let subgraphs = UnionFind::new(g.node_bound());
 580
 581     let edges = g.edge_references();
 582     let mut sort_edges = BinaryHeap::with_capacity(edges.size_hint().0);
 583     for edge in edges {
 584         sort_edges.push(MinScored(
 585             edge.weight().clone(),
 586             (edge.source(), edge.target()),
 587         ));
 588     }
 589
 590     MinSpanningTree {
 591         graph: g,
 592         node_ids: Some(g.node_references()),
 593         subgraphs,
 594         sort_edges,
 595         node_map: HashMap::new(),
 596         node_count: 0,
 597     }
 598 }
 599
 600 /// An iterator producing a minimum spanning forest of a graph.
 601 pub struct MinSpanningTree<G>
 602 where
 603     G: Data + IntoNodeReferences,
 604 {
 605     graph: G,
 606     node_ids: Option<G::NodeReferences>,
 607     subgraphs: UnionFind<usize>,
 608     sort_edges: BinaryHeap<MinScored<G::EdgeWeight, (G::NodeId, G::NodeId)>>,
 609     node_map: HashMap<usize, usize>,
 610     node_count: usize,
 611 }
 612
 613 impl<G> Iterator for MinSpanningTree<G>
 614 where
 615     G: IntoNodeReferences + NodeIndexable,
 616     G::NodeWeight: Clone,
 617     G::EdgeWeight: PartialOrd,
 618 {
 619     type Item = Element<G::NodeWeight, G::EdgeWeight>;
 620
 621     fn next(&mut self) -> Option<Self::Item> {
 622         let g = self.graph;
 623         if let Some(ref mut iter) = self.node_ids {
 624             if let Some(node) = iter.next() {
 625                 self.node_map.insert(g.to_index(node.id()), self.node_count);
 626                 self.node_count += 1;
 627                 return Some(Element::Node {
 628                     weight: node.weight().clone(),
 629                 });
 630             }
 631         }
 632         self.node_ids = None;
 633
 634         // Kruskal's algorithm.
 635         // Algorithm is this:
 636         //
 637         // 1. Create a pre-MST with all the vertices and no edges.
 638         // 2. Repeat:
 639         //
 640         //  a. Remove the shortest edge from the original graph.
 641         //  b. If the edge connects two disjoint trees in the pre-MST,
 642         //     add the edge.
 643         while let Some(MinScored(score, (a, b))) = self.sort_edges.pop() {
 644             // check if the edge would connect two disjoint parts
 645             let (a_index, b_index) = (g.to_index(a), g.to_index(b));
 646             if self.subgraphs.union(a_index, b_index) {
 647                 let (&a_order, &b_order) =
 648                     match (self.node_map.get(&a_index), self.node_map.get(&b_index)) {
 649                         (Some(a_id), Some(b_id)) => (a_id, b_id),
 650                         _ => panic!("Edge references unknown node"),
 651                     };
 652                 return Some(Element::Edge {
 653                     source: a_order,
 654                     target: b_order,
 655                     weight: score,
 656                 });
 657             }
 658         }
 659         None
 660     }
 661 }
 662
 663 /// An algorithm error: a cycle was found in the graph.
 664 #[derive(Clone, Debug, PartialEq)]
 665 pub struct Cycle<N>(N);
 666
 667 impl<N> Cycle<N> {
 668     /// Return a node id that participates in the cycle
 669     pub fn node_id(&self) -> N
 670     where
 671         N: Copy,
 672     {
 673         self.0
 674     }
 675 }
 676 /// An algorithm error: a cycle of negative weights was found in the graph.
 677 #[derive(Clone, Debug, PartialEq)]
 678 pub struct NegativeCycle(());
 679
 680 /// \[Generic\] Compute shortest paths from node `source` to all other.
 681 ///
 682 /// Using the [Bellman–Ford algorithm][bf]; negative edge costs are
 683 /// permitted, but the graph must not have a cycle of negative weights
 684 /// (in that case it will return an error).
 685 ///
 686 /// On success, return one vec with path costs, and another one which points
 687 /// out the predecessor of a node along a shortest path. The vectors
 688 /// are indexed by the graph's node indices.
 689 ///
 690 /// [bf]: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
 691 ///
 692 /// # Example
 693 /// ```rust
 694 /// use petgraph::Graph;
 695 /// use petgraph::algo::bellman_ford;
 696 /// use petgraph::prelude::*;
 697 ///
 698 /// let mut g = Graph::new();
 699 /// let a = g.add_node(()); // node with no weight
 700 /// let b = g.add_node(());
 701 /// let c = g.add_node(());
 702 /// let d = g.add_node(());
 703 /// let e = g.add_node(());
 704 /// let f = g.add_node(());
 705 /// g.extend_with_edges(&[
 706 ///     (0, 1, 2.0),
 707 ///     (0, 3, 4.0),
 708 ///     (1, 2, 1.0),
 709 ///     (1, 5, 7.0),
 710 ///     (2, 4, 5.0),
 711 ///     (4, 5, 1.0),
 712 ///     (3, 4, 1.0),
 713 /// ]);
 714 ///
 715 /// // Graph represented with the weight of each edge
 716 /// //
 717 /// //     2       1
 718 /// // a ----- b ----- c
 719 /// // | 4     | 7     |
 720 /// // d       f       | 5
 721 /// // | 1     | 1     |
 722 /// // \------ e ------/
 723 ///
 724 /// let path = bellman_ford(&g, a);
 725 /// assert_eq!(path, Ok((vec![0.0 ,     2.0,    3.0,    4.0,     5.0,     6.0],
 726 ///                      vec![None, Some(a),Some(b),Some(a), Some(d), Some(e)]
 727 ///                    ))
 728 ///           );
 729 /// // Node f (indice 5) can be reach from a with a path costing 6.
 730 /// // Predecessor of f is Some(e) which predecessor is Some(d) which predecessor is Some(a).
 731 /// // Thus the path from a to f is a <-> d <-> e <-> f
 732 ///
 733 /// let graph_with_neg_cycle = Graph::<(), f32, Undirected>::from_edges(&[
 734 ///         (0, 1, -2.0),
 735 ///         (0, 3, -4.0),
 736 ///         (1, 2, -1.0),
 737 ///         (1, 5, -25.0),
 738 ///         (2, 4, -5.0),
 739 ///         (4, 5, -25.0),
 740 ///         (3, 4, -1.0),
 741 /// ]);
 742 ///
 743 /// assert!(bellman_ford(&graph_with_neg_cycle, NodeIndex::new(0)).is_err());
 744 /// ```
 745 pub fn bellman_ford<G>(
 746     g: G,
 747     source: G::NodeId,
 748 ) -> Result<(Vec<G::EdgeWeight>, Vec<Option<G::NodeId>>), NegativeCycle>
 749 where
 750     G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable,
 751     G::EdgeWeight: FloatMeasure,
 752 {
 753     let mut predecessor = vec![None; g.node_bound()];
 754     let mut distance = vec![<_>::infinite(); g.node_bound()];
 755
 756     let ix = |i| g.to_index(i);
 757
 758     distance[ix(source)] = <_>::zero();
 759     // scan up to |V| - 1 times.
 760     for _ in 1..g.node_count() {
 761         let mut did_update = false;
 762         for i in g.node_identifiers() {
 763             for edge in g.edges(i) {
 764                 let i = edge.source();
 765                 let j = edge.target();
 766                 let w = *edge.weight();
 767                 if distance[ix(i)] + w < distance[ix(j)] {
 768                     distance[ix(j)] = distance[ix(i)] + w;
 769                     predecessor[ix(j)] = Some(i);
 770                     did_update = true;
 771                 }
 772             }
 773         }
 774         if !did_update {
 775             break;
 776         }
 777     }
 778
 779     // check for negative weight cycle
 780     for i in g.node_identifiers() {
 781         for edge in g.edges(i) {
 782             let j = edge.target();
 783             let w = *edge.weight();
 784             if distance[ix(i)] + w < distance[ix(j)] {
 785                 //println!("neg cycle, detected from {} to {}, weight={}", i, j, w);
 786                 return Err(NegativeCycle(()));
 787             }
 788         }
 789     }
 790
 791     Ok((distance, predecessor))
 792 }
 793
 794 /// Return `true` if the graph is bipartite. A graph is bipartite if it's nodes can be divided into
 795 /// two disjoint and indepedent sets U and V such that every edge connects U to one in V. This
 796 /// algorithm implements 2-coloring algorithm based on the BFS algorithm.
 797 ///
 798 /// Always treats the input graph as if undirected.
 799 pub fn is_bipartite_undirected<G, N, VM>(g: G, start: N) -> bool
 800 where
 801     G: GraphRef + Visitable<NodeId = N, Map = VM> + IntoNeighbors<NodeId = N>,
 802     N: Copy + PartialEq + std::fmt::Debug,
 803     VM: VisitMap<N>,
 804 {
 805     let mut red = g.visit_map();
 806     red.visit(start);
 807     let mut blue = g.visit_map();
 808
 809     let mut stack = ::std::collections::VecDeque::new();
 810     stack.push_front(start);
 811
 812     while let Some(node) = stack.pop_front() {
 813         let is_red = red.is_visited(&node);
 814         let is_blue = blue.is_visited(&node);
 815
 816         assert!(is_red ^ is_blue);
 817
 818         for neighbour in g.neighbors(node) {
 819             let is_neigbour_red = red.is_visited(&neighbour);
 820             let is_neigbour_blue = blue.is_visited(&neighbour);
 821
 822             if (is_red && is_neigbour_red) || (is_blue && is_neigbour_blue) {
 823                 return false;
 824             }
 825
 826             if !is_neigbour_red && !is_neigbour_blue {
 827                 //hasn't been visited yet
 828
 829                 match (is_red, is_blue) {
 830                     (true, false) => {
 831                         blue.visit(neighbour);
 832                     }
 833                     (false, true) => {
 834                         red.visit(neighbour);
 835                     }
 836                     (_, _) => {
 837                         panic!("Invariant doesn't hold");
 838                     }
 839                 }
 840
 841                 stack.push_back(neighbour);
 842             }
 843         }
 844     }
 845
 846     true
 847 }
 848
 849 use std::fmt::Debug;
 850 use std::ops::Add;
 851
 852 /// Associated data that can be used for measures (such as length).
 853 pub trait Measure: Debug + PartialOrd + Add<Self, Output = Self> + Default + Clone {}
 854
 855 impl<M> Measure for M where M: Debug + PartialOrd + Add<M, Output = M> + Default + Clone {}
 856
 857 /// A floating-point measure.
 858 pub trait FloatMeasure: Measure + Copy {
 859     fn zero() -> Self;
 860     fn infinite() -> Self;
 861 }
 862
 863 impl FloatMeasure for f32 {
 864     fn zero() -> Self {
 865         0.
 866     }
 867     fn infinite() -> Self {
 868         1. / 0.
 869     }
 870 }
 871
 872 impl FloatMeasure for f64 {
 873     fn zero() -> Self {
 874         0.
 875     }
 876     fn infinite() -> Self {
 877         1. / 0.
 878     }
 879 }