1 use super::{GraphRef, IntoNodeIdentifiers, Reversed}; 2 use super::{IntoNeighbors, IntoNeighborsDirected, VisitMap, Visitable}; 3 use crate::Incoming; 4 use std::collections::VecDeque; 5 6 /// Visit nodes of a graph in a depth-first-search (DFS) emitting nodes in 7 /// preorder (when they are first discovered). 8 /// 9 /// The traversal starts at a given node and only traverses nodes reachable 10 /// from it. 11 /// 12 /// `Dfs` is not recursive. 13 /// 14 /// `Dfs` does not itself borrow the graph, and because of this you can run 15 /// a traversal over a graph while still retaining mutable access to it, if you 16 /// use it like the following example: 17 /// 18 /// ``` 19 /// use petgraph::Graph; 20 /// use petgraph::visit::Dfs; 21 /// 22 /// let mut graph = Graph::<_,()>::new(); 23 /// let a = graph.add_node(0); 24 /// 25 /// let mut dfs = Dfs::new(&graph, a); 26 /// while let Some(nx) = dfs.next(&graph) { 27 /// // we can access `graph` mutably here still 28 /// graph[nx] += 1; 29 /// } 30 /// 31 /// assert_eq!(graph[a], 1); 32 /// ``` 33 /// 34 /// **Note:** The algorithm may not behave correctly if nodes are removed 35 /// during iteration. It may not necessarily visit added nodes or edges. 36 #[derive(Clone, Debug)] 37 pub struct Dfs<N, VM> { 38 /// The stack of nodes to visit 39 pub stack: Vec<N>, 40 /// The map of discovered nodes 41 pub discovered: VM, 42 } 43 44 impl<N, VM> Default for Dfs<N, VM> 45 where 46 VM: Default, 47 { default() -> Self48 fn default() -> Self { 49 Dfs { 50 stack: Vec::new(), 51 discovered: VM::default(), 52 } 53 } 54 } 55 56 impl<N, VM> Dfs<N, VM> 57 where 58 N: Copy + PartialEq, 59 VM: VisitMap<N>, 60 { 61 /// Create a new **Dfs**, using the graph's visitor map, and put **start** 62 /// in the stack of nodes to visit. new<G>(graph: G, start: N) -> Self where G: GraphRef + Visitable<NodeId = N, Map = VM>,63 pub fn new<G>(graph: G, start: N) -> Self 64 where 65 G: GraphRef + Visitable<NodeId = N, Map = VM>, 66 { 67 let mut dfs = Dfs::empty(graph); 68 dfs.move_to(start); 69 dfs 70 } 71 72 /// Create a `Dfs` from a vector and a visit map from_parts(stack: Vec<N>, discovered: VM) -> Self73 pub fn from_parts(stack: Vec<N>, discovered: VM) -> Self { 74 Dfs { stack, discovered } 75 } 76 77 /// Clear the visit state reset<G>(&mut self, graph: G) where G: GraphRef + Visitable<NodeId = N, Map = VM>,78 pub fn reset<G>(&mut self, graph: G) 79 where 80 G: GraphRef + Visitable<NodeId = N, Map = VM>, 81 { 82 graph.reset_map(&mut self.discovered); 83 self.stack.clear(); 84 } 85 86 /// Create a new **Dfs** using the graph's visitor map, and no stack. empty<G>(graph: G) -> Self where G: GraphRef + Visitable<NodeId = N, Map = VM>,87 pub fn empty<G>(graph: G) -> Self 88 where 89 G: GraphRef + Visitable<NodeId = N, Map = VM>, 90 { 91 Dfs { 92 stack: Vec::new(), 93 discovered: graph.visit_map(), 94 } 95 } 96 97 /// Keep the discovered map, but clear the visit stack and restart 98 /// the dfs from a particular node. move_to(&mut self, start: N)99 pub fn move_to(&mut self, start: N) { 100 self.stack.clear(); 101 self.stack.push(start); 102 } 103 104 /// Return the next node in the dfs, or **None** if the traversal is done. next<G>(&mut self, graph: G) -> Option<N> where G: IntoNeighbors<NodeId = N>,105 pub fn next<G>(&mut self, graph: G) -> Option<N> 106 where 107 G: IntoNeighbors<NodeId = N>, 108 { 109 while let Some(node) = self.stack.pop() { 110 if self.discovered.visit(node) { 111 for succ in graph.neighbors(node) { 112 if !self.discovered.is_visited(&succ) { 113 self.stack.push(succ); 114 } 115 } 116 return Some(node); 117 } 118 } 119 None 120 } 121 } 122 123 /// Visit nodes in a depth-first-search (DFS) emitting nodes in postorder 124 /// (each node after all its descendants have been emitted). 125 /// 126 /// `DfsPostOrder` is not recursive. 127 /// 128 /// The traversal starts at a given node and only traverses nodes reachable 129 /// from it. 130 #[derive(Clone, Debug)] 131 pub struct DfsPostOrder<N, VM> { 132 /// The stack of nodes to visit 133 pub stack: Vec<N>, 134 /// The map of discovered nodes 135 pub discovered: VM, 136 /// The map of finished nodes 137 pub finished: VM, 138 } 139 140 impl<N, VM> Default for DfsPostOrder<N, VM> 141 where 142 VM: Default, 143 { default() -> Self144 fn default() -> Self { 145 DfsPostOrder { 146 stack: Vec::new(), 147 discovered: VM::default(), 148 finished: VM::default(), 149 } 150 } 151 } 152 153 impl<N, VM> DfsPostOrder<N, VM> 154 where 155 N: Copy + PartialEq, 156 VM: VisitMap<N>, 157 { 158 /// Create a new `DfsPostOrder` using the graph's visitor map, and put 159 /// `start` in the stack of nodes to visit. new<G>(graph: G, start: N) -> Self where G: GraphRef + Visitable<NodeId = N, Map = VM>,160 pub fn new<G>(graph: G, start: N) -> Self 161 where 162 G: GraphRef + Visitable<NodeId = N, Map = VM>, 163 { 164 let mut dfs = Self::empty(graph); 165 dfs.move_to(start); 166 dfs 167 } 168 169 /// Create a new `DfsPostOrder` using the graph's visitor map, and no stack. empty<G>(graph: G) -> Self where G: GraphRef + Visitable<NodeId = N, Map = VM>,170 pub fn empty<G>(graph: G) -> Self 171 where 172 G: GraphRef + Visitable<NodeId = N, Map = VM>, 173 { 174 DfsPostOrder { 175 stack: Vec::new(), 176 discovered: graph.visit_map(), 177 finished: graph.visit_map(), 178 } 179 } 180 181 /// Clear the visit state reset<G>(&mut self, graph: G) where G: GraphRef + Visitable<NodeId = N, Map = VM>,182 pub fn reset<G>(&mut self, graph: G) 183 where 184 G: GraphRef + Visitable<NodeId = N, Map = VM>, 185 { 186 graph.reset_map(&mut self.discovered); 187 graph.reset_map(&mut self.finished); 188 self.stack.clear(); 189 } 190 191 /// Keep the discovered and finished map, but clear the visit stack and restart 192 /// the dfs from a particular node. move_to(&mut self, start: N)193 pub fn move_to(&mut self, start: N) { 194 self.stack.clear(); 195 self.stack.push(start); 196 } 197 198 /// Return the next node in the traversal, or `None` if the traversal is done. next<G>(&mut self, graph: G) -> Option<N> where G: IntoNeighbors<NodeId = N>,199 pub fn next<G>(&mut self, graph: G) -> Option<N> 200 where 201 G: IntoNeighbors<NodeId = N>, 202 { 203 while let Some(&nx) = self.stack.last() { 204 if self.discovered.visit(nx) { 205 // First time visiting `nx`: Push neighbors, don't pop `nx` 206 for succ in graph.neighbors(nx) { 207 if !self.discovered.is_visited(&succ) { 208 self.stack.push(succ); 209 } 210 } 211 } else { 212 self.stack.pop(); 213 if self.finished.visit(nx) { 214 // Second time: All reachable nodes must have been finished 215 return Some(nx); 216 } 217 } 218 } 219 None 220 } 221 } 222 223 /// A breadth first search (BFS) of a graph. 224 /// 225 /// The traversal starts at a given node and only traverses nodes reachable 226 /// from it. 227 /// 228 /// `Bfs` is not recursive. 229 /// 230 /// `Bfs` does not itself borrow the graph, and because of this you can run 231 /// a traversal over a graph while still retaining mutable access to it, if you 232 /// use it like the following example: 233 /// 234 /// ``` 235 /// use petgraph::Graph; 236 /// use petgraph::visit::Bfs; 237 /// 238 /// let mut graph = Graph::<_,()>::new(); 239 /// let a = graph.add_node(0); 240 /// 241 /// let mut bfs = Bfs::new(&graph, a); 242 /// while let Some(nx) = bfs.next(&graph) { 243 /// // we can access `graph` mutably here still 244 /// graph[nx] += 1; 245 /// } 246 /// 247 /// assert_eq!(graph[a], 1); 248 /// ``` 249 /// 250 /// **Note:** The algorithm may not behave correctly if nodes are removed 251 /// during iteration. It may not necessarily visit added nodes or edges. 252 #[derive(Clone)] 253 pub struct Bfs<N, VM> { 254 /// The queue of nodes to visit 255 pub stack: VecDeque<N>, 256 /// The map of discovered nodes 257 pub discovered: VM, 258 } 259 260 impl<N, VM> Default for Bfs<N, VM> 261 where 262 VM: Default, 263 { default() -> Self264 fn default() -> Self { 265 Bfs { 266 stack: VecDeque::new(), 267 discovered: VM::default(), 268 } 269 } 270 } 271 272 impl<N, VM> Bfs<N, VM> 273 where 274 N: Copy + PartialEq, 275 VM: VisitMap<N>, 276 { 277 /// Create a new **Bfs**, using the graph's visitor map, and put **start** 278 /// in the stack of nodes to visit. new<G>(graph: G, start: N) -> Self where G: GraphRef + Visitable<NodeId = N, Map = VM>,279 pub fn new<G>(graph: G, start: N) -> Self 280 where 281 G: GraphRef + Visitable<NodeId = N, Map = VM>, 282 { 283 let mut discovered = graph.visit_map(); 284 discovered.visit(start); 285 let mut stack = VecDeque::new(); 286 stack.push_front(start); 287 Bfs { stack, discovered } 288 } 289 290 /// Return the next node in the bfs, or **None** if the traversal is done. next<G>(&mut self, graph: G) -> Option<N> where G: IntoNeighbors<NodeId = N>,291 pub fn next<G>(&mut self, graph: G) -> Option<N> 292 where 293 G: IntoNeighbors<NodeId = N>, 294 { 295 if let Some(node) = self.stack.pop_front() { 296 for succ in graph.neighbors(node) { 297 if self.discovered.visit(succ) { 298 self.stack.push_back(succ); 299 } 300 } 301 302 return Some(node); 303 } 304 None 305 } 306 } 307 308 /// A topological order traversal for a graph. 309 /// 310 /// **Note** that `Topo` only visits nodes that are not part of cycles, 311 /// i.e. nodes in a true DAG. Use other visitors like `DfsPostOrder` or 312 /// algorithms like kosaraju_scc to handle graphs with possible cycles. 313 #[derive(Clone)] 314 pub struct Topo<N, VM> { 315 tovisit: Vec<N>, 316 ordered: VM, 317 } 318 319 impl<N, VM> Default for Topo<N, VM> 320 where 321 VM: Default, 322 { default() -> Self323 fn default() -> Self { 324 Topo { 325 tovisit: Vec::new(), 326 ordered: VM::default(), 327 } 328 } 329 } 330 331 impl<N, VM> Topo<N, VM> 332 where 333 N: Copy + PartialEq, 334 VM: VisitMap<N>, 335 { 336 /// Create a new `Topo`, using the graph's visitor map, and put all 337 /// initial nodes in the to visit list. new<G>(graph: G) -> Self where G: IntoNodeIdentifiers + IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>,338 pub fn new<G>(graph: G) -> Self 339 where 340 G: IntoNodeIdentifiers + IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>, 341 { 342 let mut topo = Self::empty(graph); 343 topo.extend_with_initials(graph); 344 topo 345 } 346 extend_with_initials<G>(&mut self, g: G) where G: IntoNodeIdentifiers + IntoNeighborsDirected<NodeId = N>,347 fn extend_with_initials<G>(&mut self, g: G) 348 where 349 G: IntoNodeIdentifiers + IntoNeighborsDirected<NodeId = N>, 350 { 351 // find all initial nodes (nodes without incoming edges) 352 self.tovisit.extend( 353 g.node_identifiers() 354 .filter(move |&a| g.neighbors_directed(a, Incoming).next().is_none()), 355 ); 356 } 357 358 /* Private until it has a use */ 359 /// Create a new `Topo`, using the graph's visitor map with *no* starting 360 /// index specified. empty<G>(graph: G) -> Self where G: GraphRef + Visitable<NodeId = N, Map = VM>,361 fn empty<G>(graph: G) -> Self 362 where 363 G: GraphRef + Visitable<NodeId = N, Map = VM>, 364 { 365 Topo { 366 ordered: graph.visit_map(), 367 tovisit: Vec::new(), 368 } 369 } 370 371 /// Clear visited state, and put all initial nodes in the to visit list. reset<G>(&mut self, graph: G) where G: IntoNodeIdentifiers + IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>,372 pub fn reset<G>(&mut self, graph: G) 373 where 374 G: IntoNodeIdentifiers + IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>, 375 { 376 graph.reset_map(&mut self.ordered); 377 self.tovisit.clear(); 378 self.extend_with_initials(graph); 379 } 380 381 /// Return the next node in the current topological order traversal, or 382 /// `None` if the traversal is at the end. 383 /// 384 /// *Note:* The graph may not have a complete topological order, and the only 385 /// way to know is to run the whole traversal and make sure it visits every node. next<G>(&mut self, g: G) -> Option<N> where G: IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>,386 pub fn next<G>(&mut self, g: G) -> Option<N> 387 where 388 G: IntoNeighborsDirected + Visitable<NodeId = N, Map = VM>, 389 { 390 // Take an unvisited element and find which of its neighbors are next 391 while let Some(nix) = self.tovisit.pop() { 392 if self.ordered.is_visited(&nix) { 393 continue; 394 } 395 self.ordered.visit(nix); 396 for neigh in g.neighbors(nix) { 397 // Look at each neighbor, and those that only have incoming edges 398 // from the already ordered list, they are the next to visit. 399 if Reversed(g) 400 .neighbors(neigh) 401 .all(|b| self.ordered.is_visited(&b)) 402 { 403 self.tovisit.push(neigh); 404 } 405 } 406 return Some(nix); 407 } 408 None 409 } 410 } 411 412 /// A walker is a traversal state, but where part of the traversal 413 /// information is supplied manually to each next call. 414 /// 415 /// This for example allows graph traversals that don't hold a borrow of the 416 /// graph they are traversing. 417 pub trait Walker<Context> { 418 type Item; 419 /// Advance to the next item walk_next(&mut self, context: Context) -> Option<Self::Item>420 fn walk_next(&mut self, context: Context) -> Option<Self::Item>; 421 422 /// Create an iterator out of the walker and given `context`. iter(self, context: Context) -> WalkerIter<Self, Context> where Self: Sized, Context: Clone,423 fn iter(self, context: Context) -> WalkerIter<Self, Context> 424 where 425 Self: Sized, 426 Context: Clone, 427 { 428 WalkerIter { 429 walker: self, 430 context, 431 } 432 } 433 } 434 435 /// A walker and its context wrapped into an iterator. 436 #[derive(Clone, Debug)] 437 pub struct WalkerIter<W, C> { 438 walker: W, 439 context: C, 440 } 441 442 impl<W, C> WalkerIter<W, C> 443 where 444 W: Walker<C>, 445 C: Clone, 446 { context(&self) -> C447 pub fn context(&self) -> C { 448 self.context.clone() 449 } 450 inner_ref(&self) -> &W451 pub fn inner_ref(&self) -> &W { 452 &self.walker 453 } 454 inner_mut(&mut self) -> &mut W455 pub fn inner_mut(&mut self) -> &mut W { 456 &mut self.walker 457 } 458 } 459 460 impl<W, C> Iterator for WalkerIter<W, C> 461 where 462 W: Walker<C>, 463 C: Clone, 464 { 465 type Item = W::Item; next(&mut self) -> Option<Self::Item>466 fn next(&mut self) -> Option<Self::Item> { 467 self.walker.walk_next(self.context.clone()) 468 } 469 } 470 471 impl<'a, C, W: ?Sized> Walker<C> for &'a mut W 472 where 473 W: Walker<C>, 474 { 475 type Item = W::Item; walk_next(&mut self, context: C) -> Option<Self::Item>476 fn walk_next(&mut self, context: C) -> Option<Self::Item> { 477 (**self).walk_next(context) 478 } 479 } 480 481 impl<G> Walker<G> for Dfs<G::NodeId, G::Map> 482 where 483 G: IntoNeighbors + Visitable, 484 { 485 type Item = G::NodeId; walk_next(&mut self, context: G) -> Option<Self::Item>486 fn walk_next(&mut self, context: G) -> Option<Self::Item> { 487 self.next(context) 488 } 489 } 490 491 impl<G> Walker<G> for DfsPostOrder<G::NodeId, G::Map> 492 where 493 G: IntoNeighbors + Visitable, 494 { 495 type Item = G::NodeId; walk_next(&mut self, context: G) -> Option<Self::Item>496 fn walk_next(&mut self, context: G) -> Option<Self::Item> { 497 self.next(context) 498 } 499 } 500 501 impl<G> Walker<G> for Bfs<G::NodeId, G::Map> 502 where 503 G: IntoNeighbors + Visitable, 504 { 505 type Item = G::NodeId; walk_next(&mut self, context: G) -> Option<Self::Item>506 fn walk_next(&mut self, context: G) -> Option<Self::Item> { 507 self.next(context) 508 } 509 } 510 511 impl<G> Walker<G> for Topo<G::NodeId, G::Map> 512 where 513 G: IntoNeighborsDirected + Visitable, 514 { 515 type Item = G::NodeId; walk_next(&mut self, context: G) -> Option<Self::Item>516 fn walk_next(&mut self, context: G) -> Option<Self::Item> { 517 self.next(context) 518 } 519 } 520