vendor/petgraph/src/visit/mod.rs

   1 //! Graph traits and graph traversals.
   2 //!
   3 //! ### The `Into-` Traits
   4 //!
   5 //! Graph traits like [`IntoNeighbors`][in] create iterators and use the same
   6 //! pattern that `IntoIterator` does: the trait takes a reference to a graph,
   7 //! and produces an iterator. These traits are quite composable, but with the
   8 //! limitation that they only use shared references to graphs.
   9 //!
  10 //! ### Graph Traversal
  11 //!
  12 //! [`Dfs`](struct.Dfs.html), [`Bfs`][bfs], [`DfsPostOrder`][dfspo] and
  13 //! [`Topo`][topo]  are basic visitors and they use “walker” methods: the
  14 //! visitors don't hold the graph as borrowed during traversal, only for the
  15 //! `.next()` call on the walker. They can be converted to iterators
  16 //! through the [`Walker`][w] trait.
  17 //!
  18 //! There is also the callback based traversal [`depth_first_search`][dfs].
  19 //!
  20 //! [bfs]: struct.Bfs.html
  21 //! [dfspo]: struct.DfsPostOrder.html
  22 //! [topo]: struct.Topo.html
  23 //! [dfs]: fn.depth_first_search.html
  24 //! [w]: trait.Walker.html
  25 //!
  26 //! ### Other Graph Traits
  27 //!
  28 //! The traits are rather loosely coupled at the moment (which is intentional,
  29 //! but will develop a bit), and there are traits missing that could be added.
  30 //!
  31 //! Not much is needed to be able to use the visitors on a graph. A graph
  32 //! needs to define [`GraphBase`][gb], [`IntoNeighbors`][in] and
  33 //! [`Visitable`][vis] as a minimum.
  34 //!
  35 //! [gb]: trait.GraphBase.html
  36 //! [in]: trait.IntoNeighbors.html
  37 //! [vis]: trait.Visitable.html
  38 //!
  39
  40 // filter, reversed have their `mod` lines at the end,
  41 // so that they can use the trait template macros
  42 pub use self::filter::*;
  43 pub use self::reversed::*;
  44
  45 #[macro_use]
  46 mod macros;
  47
  48 mod dfsvisit;
  49 mod traversal;
  50 pub use self::dfsvisit::*;
  51 pub use self::traversal::*;
  52
  53 use fixedbitset::FixedBitSet;
  54 use std::collections::HashSet;
  55 use std::hash::{BuildHasher, Hash};
  56
  57 use super::{graph, EdgeType};
  58 use crate::graph::NodeIndex;
  59 #[cfg(feature = "graphmap")]
  60 use crate::prelude::GraphMap;
  61 #[cfg(feature = "stable_graph")]
  62 use crate::prelude::StableGraph;
  63 use crate::prelude::{Direction, Graph};
  64
  65 use crate::graph::Frozen;
  66 use crate::graph::IndexType;
  67 #[cfg(feature = "stable_graph")]
  68 use crate::stable_graph;
  69
  70 #[cfg(feature = "graphmap")]
  71 use crate::graphmap::{self, NodeTrait};
  72
  73 trait_template! {
  74 /// Base graph trait: defines the associated node identifier and
  75 /// edge identifier types.
  76 pub trait GraphBase {
  77     // FIXME: We can drop this escape/nodelegate stuff in Rust 1.18
  78     @escape [type NodeId]
  79     @escape [type EdgeId]
  80     @section nodelegate
  81     /// edge identifier
  82     type EdgeId: Copy + PartialEq;
  83     /// node identifier
  84     type NodeId: Copy + PartialEq;
  85 }
  86 }
  87
  88 GraphBase! {delegate_impl []}
  89 GraphBase! {delegate_impl [['a, G], G, &'a mut G, deref]}
  90
  91 /// A copyable reference to a graph.
  92 pub trait GraphRef: Copy + GraphBase {}
  93
  94 impl<'a, G> GraphRef for &'a G where G: GraphBase {}
  95
  96 impl<'a, G> GraphBase for Frozen<'a, G>
  97 where
  98     G: GraphBase,
  99 {
 100     type NodeId = G::NodeId;
 101     type EdgeId = G::EdgeId;
 102 }
 103
 104 #[cfg(feature = "stable_graph")]
 105 impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a StableGraph<N, E, Ty, Ix>
 106 where
 107     Ty: EdgeType,
 108     Ix: IndexType,
 109 {
 110     type Neighbors = stable_graph::Neighbors<'a, E, Ix>;
 111     fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
 112         (*self).neighbors(n)
 113     }
 114 }
 115
 116 #[cfg(feature = "graphmap")]
 117 impl<'a, N: 'a, E, Ty> IntoNeighbors for &'a GraphMap<N, E, Ty>
 118 where
 119     N: Copy + Ord + Hash,
 120     Ty: EdgeType,
 121 {
 122     type Neighbors = graphmap::Neighbors<'a, N, Ty>;
 123     fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
 124         self.neighbors(n)
 125     }
 126 }
 127
 128 trait_template! {
 129 /// Access to the neighbors of each node
 130 ///
 131 /// The neighbors are, depending on the graph’s edge type:
 132 ///
 133 /// - `Directed`: All targets of edges from `a`.
 134 /// - `Undirected`: All other endpoints of edges connected to `a`.
 135 pub trait IntoNeighbors : GraphRef {
 136     @section type
 137     type Neighbors: Iterator<Item=Self::NodeId>;
 138     @section self
 139     /// Return an iterator of the neighbors of node `a`.
 140     fn neighbors(self: Self, a: Self::NodeId) -> Self::Neighbors;
 141 }
 142 }
 143
 144 IntoNeighbors! {delegate_impl []}
 145
 146 trait_template! {
 147 /// Access to the neighbors of each node, through incoming or outgoing edges.
 148 ///
 149 /// Depending on the graph’s edge type, the neighbors of a given directionality
 150 /// are:
 151 ///
 152 /// - `Directed`, `Outgoing`: All targets of edges from `a`.
 153 /// - `Directed`, `Incoming`: All sources of edges to `a`.
 154 /// - `Undirected`: All other endpoints of edges connected to `a`.
 155 pub trait IntoNeighborsDirected : IntoNeighbors {
 156     @section type
 157     type NeighborsDirected: Iterator<Item=Self::NodeId>;
 158     @section self
 159     fn neighbors_directed(self, n: Self::NodeId, d: Direction)
 160         -> Self::NeighborsDirected;
 161 }
 162 }
 163
 164 impl<'a, N, E: 'a, Ty, Ix> IntoNeighbors for &'a Graph<N, E, Ty, Ix>
 165 where
 166     Ty: EdgeType,
 167     Ix: IndexType,
 168 {
 169     type Neighbors = graph::Neighbors<'a, E, Ix>;
 170     fn neighbors(self, n: graph::NodeIndex<Ix>) -> graph::Neighbors<'a, E, Ix> {
 171         Graph::neighbors(self, n)
 172     }
 173 }
 174
 175 impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a Graph<N, E, Ty, Ix>
 176 where
 177     Ty: EdgeType,
 178     Ix: IndexType,
 179 {
 180     type NeighborsDirected = graph::Neighbors<'a, E, Ix>;
 181     fn neighbors_directed(
 182         self,
 183         n: graph::NodeIndex<Ix>,
 184         d: Direction,
 185     ) -> graph::Neighbors<'a, E, Ix> {
 186         Graph::neighbors_directed(self, n, d)
 187     }
 188 }
 189
 190 #[cfg(feature = "stable_graph")]
 191 impl<'a, N, E: 'a, Ty, Ix> IntoNeighborsDirected for &'a StableGraph<N, E, Ty, Ix>
 192 where
 193     Ty: EdgeType,
 194     Ix: IndexType,
 195 {
 196     type NeighborsDirected = stable_graph::Neighbors<'a, E, Ix>;
 197     fn neighbors_directed(self, n: graph::NodeIndex<Ix>, d: Direction) -> Self::NeighborsDirected {
 198         StableGraph::neighbors_directed(self, n, d)
 199     }
 200 }
 201
 202 #[cfg(feature = "graphmap")]
 203 impl<'a, N: 'a, E, Ty> IntoNeighborsDirected for &'a GraphMap<N, E, Ty>
 204 where
 205     N: Copy + Ord + Hash,
 206     Ty: EdgeType,
 207 {
 208     type NeighborsDirected = graphmap::NeighborsDirected<'a, N, Ty>;
 209     fn neighbors_directed(self, n: N, dir: Direction) -> Self::NeighborsDirected {
 210         self.neighbors_directed(n, dir)
 211     }
 212 }
 213
 214 trait_template! {
 215 /// Access to the edges of each node.
 216 ///
 217 /// The edges are, depending on the graph’s edge type:
 218 ///
 219 /// - `Directed`: All edges from `a`.
 220 /// - `Undirected`: All edges connected to `a`.
 221 ///
 222 /// This is an extended version of the trait `IntoNeighbors`; the former
 223 /// only iterates over the target node identifiers, while this trait
 224 /// yields edge references (trait [`EdgeRef`][er]).
 225 ///
 226 /// [er]: trait.EdgeRef.html
 227 pub trait IntoEdges : IntoEdgeReferences + IntoNeighbors {
 228     @section type
 229     type Edges: Iterator<Item=Self::EdgeRef>;
 230     @section self
 231     fn edges(self, a: Self::NodeId) -> Self::Edges;
 232 }
 233 }
 234
 235 IntoEdges! {delegate_impl []}
 236
 237 trait_template! {
 238 /// Access to all edges of each node, in the specified direction.
 239 ///
 240 /// The edges are, depending on the direction and the graph’s edge type:
 241 ///
 242 ///
 243 /// - `Directed`, `Outgoing`: All edges from `a`.
 244 /// - `Directed`, `Incoming`: All edges to `a`.
 245 /// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each edge.
 246 /// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each edge.
 247 ///
 248 /// This is an extended version of the trait `IntoNeighborsDirected`; the former
 249 /// only iterates over the target node identifiers, while this trait
 250 /// yields edge references (trait [`EdgeRef`][er]).
 251 ///
 252 /// [er]: trait.EdgeRef.html
 253 pub trait IntoEdgesDirected : IntoEdges + IntoNeighborsDirected {
 254     @section type
 255     type EdgesDirected: Iterator<Item=Self::EdgeRef>;
 256     @section self
 257     fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected;
 258 }
 259 }
 260
 261 IntoEdgesDirected! {delegate_impl []}
 262
 263 trait_template! {
 264 /// Access to the sequence of the graph’s `NodeId`s.
 265 pub trait IntoNodeIdentifiers : GraphRef {
 266     @section type
 267     type NodeIdentifiers: Iterator<Item=Self::NodeId>;
 268     @section self
 269     fn node_identifiers(self) -> Self::NodeIdentifiers;
 270 }
 271 }
 272
 273 IntoNodeIdentifiers! {delegate_impl []}
 274
 275 impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a Graph<N, E, Ty, Ix>
 276 where
 277     Ty: EdgeType,
 278     Ix: IndexType,
 279 {
 280     type NodeIdentifiers = graph::NodeIndices<Ix>;
 281     fn node_identifiers(self) -> graph::NodeIndices<Ix> {
 282         Graph::node_indices(self)
 283     }
 284 }
 285
 286 impl<N, E, Ty, Ix> NodeCount for Graph<N, E, Ty, Ix>
 287 where
 288     Ty: EdgeType,
 289     Ix: IndexType,
 290 {
 291     fn node_count(&self) -> usize {
 292         self.node_count()
 293     }
 294 }
 295
 296 #[cfg(feature = "stable_graph")]
 297 impl<'a, N, E: 'a, Ty, Ix> IntoNodeIdentifiers for &'a StableGraph<N, E, Ty, Ix>
 298 where
 299     Ty: EdgeType,
 300     Ix: IndexType,
 301 {
 302     type NodeIdentifiers = stable_graph::NodeIndices<'a, N, Ix>;
 303     fn node_identifiers(self) -> Self::NodeIdentifiers {
 304         StableGraph::node_indices(self)
 305     }
 306 }
 307
 308 #[cfg(feature = "stable_graph")]
 309 impl<N, E, Ty, Ix> NodeCount for StableGraph<N, E, Ty, Ix>
 310 where
 311     Ty: EdgeType,
 312     Ix: IndexType,
 313 {
 314     fn node_count(&self) -> usize {
 315         self.node_count()
 316     }
 317 }
 318
 319 IntoNeighborsDirected! {delegate_impl []}
 320
 321 trait_template! {
 322 /// Define associated data for nodes and edges
 323 pub trait Data : GraphBase {
 324     @section type
 325     type NodeWeight;
 326     type EdgeWeight;
 327 }
 328 }
 329
 330 Data! {delegate_impl []}
 331 Data! {delegate_impl [['a, G], G, &'a mut G, deref]}
 332
 333 /// An edge reference.
 334 ///
 335 /// Edge references are used by traits `IntoEdges` and `IntoEdgeReferences`.
 336 pub trait EdgeRef: Copy {
 337     type NodeId;
 338     type EdgeId;
 339     type Weight;
 340     /// The source node of the edge.
 341     fn source(&self) -> Self::NodeId;
 342     /// The target node of the edge.
 343     fn target(&self) -> Self::NodeId;
 344     /// A reference to the weight of the edge.
 345     fn weight(&self) -> &Self::Weight;
 346     /// The edge’s identifier.
 347     fn id(&self) -> Self::EdgeId;
 348 }
 349
 350 impl<'a, N, E> EdgeRef for (N, N, &'a E)
 351 where
 352     N: Copy,
 353 {
 354     type NodeId = N;
 355     type EdgeId = (N, N);
 356     type Weight = E;
 357
 358     fn source(&self) -> N {
 359         self.0
 360     }
 361     fn target(&self) -> N {
 362         self.1
 363     }
 364     fn weight(&self) -> &E {
 365         self.2
 366     }
 367     fn id(&self) -> (N, N) {
 368         (self.0, self.1)
 369     }
 370 }
 371
 372 /// A node reference.
 373 pub trait NodeRef: Copy {
 374     type NodeId;
 375     type Weight;
 376     fn id(&self) -> Self::NodeId;
 377     fn weight(&self) -> &Self::Weight;
 378 }
 379
 380 trait_template! {
 381 /// Access to the sequence of the graph’s nodes
 382 pub trait IntoNodeReferences : Data + IntoNodeIdentifiers {
 383     @section type
 384     type NodeRef: NodeRef<NodeId=Self::NodeId, Weight=Self::NodeWeight>;
 385     type NodeReferences: Iterator<Item=Self::NodeRef>;
 386     @section self
 387     fn node_references(self) -> Self::NodeReferences;
 388 }
 389 }
 390
 391 IntoNodeReferences! {delegate_impl []}
 392
 393 impl<Id> NodeRef for (Id, ())
 394 where
 395     Id: Copy,
 396 {
 397     type NodeId = Id;
 398     type Weight = ();
 399     fn id(&self) -> Self::NodeId {
 400         self.0
 401     }
 402     fn weight(&self) -> &Self::Weight {
 403         static DUMMY: () = ();
 404         &DUMMY
 405     }
 406 }
 407
 408 impl<'a, Id, W> NodeRef for (Id, &'a W)
 409 where
 410     Id: Copy,
 411 {
 412     type NodeId = Id;
 413     type Weight = W;
 414     fn id(&self) -> Self::NodeId {
 415         self.0
 416     }
 417     fn weight(&self) -> &Self::Weight {
 418         self.1
 419     }
 420 }
 421
 422 trait_template! {
 423 /// Access to the sequence of the graph’s edges
 424 pub trait IntoEdgeReferences : Data + GraphRef {
 425     @section type
 426     type EdgeRef: EdgeRef<NodeId=Self::NodeId, EdgeId=Self::EdgeId,
 427                           Weight=Self::EdgeWeight>;
 428     type EdgeReferences: Iterator<Item=Self::EdgeRef>;
 429     @section self
 430     fn edge_references(self) -> Self::EdgeReferences;
 431 }
 432 }
 433
 434 IntoEdgeReferences! {delegate_impl [] }
 435
 436 #[cfg(feature = "graphmap")]
 437 impl<N, E, Ty> Data for GraphMap<N, E, Ty>
 438 where
 439     N: Copy + PartialEq,
 440     Ty: EdgeType,
 441 {
 442     type NodeWeight = N;
 443     type EdgeWeight = E;
 444 }
 445
 446 trait_template! {
 447     /// Edge kind property (directed or undirected edges)
 448 pub trait GraphProp : GraphBase {
 449     @section type
 450     /// The kind edges in the graph.
 451     type EdgeType: EdgeType;
 452
 453     @section nodelegate
 454     fn is_directed(&self) -> bool {
 455         <Self::EdgeType>::is_directed()
 456     }
 457 }
 458 }
 459
 460 GraphProp! {delegate_impl []}
 461
 462 impl<N, E, Ty, Ix> GraphProp for Graph<N, E, Ty, Ix>
 463 where
 464     Ty: EdgeType,
 465     Ix: IndexType,
 466 {
 467     type EdgeType = Ty;
 468 }
 469
 470 #[cfg(feature = "stable_graph")]
 471 impl<N, E, Ty, Ix> GraphProp for StableGraph<N, E, Ty, Ix>
 472 where
 473     Ty: EdgeType,
 474     Ix: IndexType,
 475 {
 476     type EdgeType = Ty;
 477 }
 478
 479 #[cfg(feature = "graphmap")]
 480 impl<N, E, Ty> GraphProp for GraphMap<N, E, Ty>
 481 where
 482     N: NodeTrait,
 483     Ty: EdgeType,
 484 {
 485     type EdgeType = Ty;
 486 }
 487
 488 impl<'a, N: 'a, E: 'a, Ty, Ix> IntoEdgeReferences for &'a Graph<N, E, Ty, Ix>
 489 where
 490     Ty: EdgeType,
 491     Ix: IndexType,
 492 {
 493     type EdgeRef = graph::EdgeReference<'a, E, Ix>;
 494     type EdgeReferences = graph::EdgeReferences<'a, E, Ix>;
 495     fn edge_references(self) -> Self::EdgeReferences {
 496         (*self).edge_references()
 497     }
 498 }
 499
 500 trait_template! {
 501     /// The graph’s `NodeId`s map to indices
 502     pub trait NodeIndexable : GraphBase {
 503         @section self
 504         /// Return an upper bound of the node indices in the graph
 505         /// (suitable for the size of a bitmap).
 506         fn node_bound(self: &Self) -> usize;
 507         /// Convert `a` to an integer index.
 508         fn to_index(self: &Self, a: Self::NodeId) -> usize;
 509         /// Convert `i` to a node index
 510         fn from_index(self: &Self, i: usize) -> Self::NodeId;
 511     }
 512 }
 513
 514 NodeIndexable! {delegate_impl []}
 515
 516 trait_template! {
 517 /// A graph with a known node count.
 518 pub trait NodeCount : GraphBase {
 519     @section self
 520     fn node_count(self: &Self) -> usize;
 521 }
 522 }
 523
 524 NodeCount! {delegate_impl []}
 525
 526 trait_template! {
 527 /// The graph’s `NodeId`s map to indices, in a range without holes.
 528 ///
 529 /// The graph's node identifiers correspond to exactly the indices
 530 /// `0..self.node_bound()`.
 531 pub trait NodeCompactIndexable : NodeIndexable + NodeCount { }
 532 }
 533
 534 NodeCompactIndexable! {delegate_impl []}
 535
 536 impl<N, E, Ty, Ix> NodeIndexable for Graph<N, E, Ty, Ix>
 537 where
 538     Ty: EdgeType,
 539     Ix: IndexType,
 540 {
 541     fn node_bound(&self) -> usize {
 542         self.node_count()
 543     }
 544     fn to_index(&self, ix: NodeIndex<Ix>) -> usize {
 545         ix.index()
 546     }
 547     fn from_index(&self, ix: usize) -> Self::NodeId {
 548         NodeIndex::new(ix)
 549     }
 550 }
 551
 552 impl<N, E, Ty, Ix> NodeCompactIndexable for Graph<N, E, Ty, Ix>
 553 where
 554     Ty: EdgeType,
 555     Ix: IndexType,
 556 {
 557 }
 558
 559 /// A mapping for storing the visited status for NodeId `N`.
 560 pub trait VisitMap<N> {
 561     /// Mark `a` as visited.
 562     ///
 563     /// Return **true** if this is the first visit, false otherwise.
 564     fn visit(&mut self, a: N) -> bool;
 565
 566     /// Return whether `a` has been visited before.
 567     fn is_visited(&self, a: &N) -> bool;
 568 }
 569
 570 impl<Ix> VisitMap<graph::NodeIndex<Ix>> for FixedBitSet
 571 where
 572     Ix: IndexType,
 573 {
 574     fn visit(&mut self, x: graph::NodeIndex<Ix>) -> bool {
 575         !self.put(x.index())
 576     }
 577     fn is_visited(&self, x: &graph::NodeIndex<Ix>) -> bool {
 578         self.contains(x.index())
 579     }
 580 }
 581
 582 impl<Ix> VisitMap<graph::EdgeIndex<Ix>> for FixedBitSet
 583 where
 584     Ix: IndexType,
 585 {
 586     fn visit(&mut self, x: graph::EdgeIndex<Ix>) -> bool {
 587         !self.put(x.index())
 588     }
 589     fn is_visited(&self, x: &graph::EdgeIndex<Ix>) -> bool {
 590         self.contains(x.index())
 591     }
 592 }
 593
 594 impl<Ix> VisitMap<Ix> for FixedBitSet
 595 where
 596     Ix: IndexType,
 597 {
 598     fn visit(&mut self, x: Ix) -> bool {
 599         !self.put(x.index())
 600     }
 601     fn is_visited(&self, x: &Ix) -> bool {
 602         self.contains(x.index())
 603     }
 604 }
 605
 606 impl<N, S> VisitMap<N> for HashSet<N, S>
 607 where
 608     N: Hash + Eq,
 609     S: BuildHasher,
 610 {
 611     fn visit(&mut self, x: N) -> bool {
 612         self.insert(x)
 613     }
 614     fn is_visited(&self, x: &N) -> bool {
 615         self.contains(x)
 616     }
 617 }
 618
 619 trait_template! {
 620 /// A graph that can create a map that tracks the visited status of its nodes.
 621 pub trait Visitable : GraphBase {
 622     @section type
 623     /// The associated map type
 624     type Map: VisitMap<Self::NodeId>;
 625     @section self
 626     /// Create a new visitor map
 627     fn visit_map(self: &Self) -> Self::Map;
 628     /// Reset the visitor map (and resize to new size of graph if needed)
 629     fn reset_map(self: &Self, map: &mut Self::Map);
 630 }
 631 }
 632 Visitable! {delegate_impl []}
 633
 634 impl<N, E, Ty, Ix> GraphBase for Graph<N, E, Ty, Ix>
 635 where
 636     Ix: IndexType,
 637 {
 638     type NodeId = graph::NodeIndex<Ix>;
 639     type EdgeId = graph::EdgeIndex<Ix>;
 640 }
 641
 642 impl<N, E, Ty, Ix> Visitable for Graph<N, E, Ty, Ix>
 643 where
 644     Ty: EdgeType,
 645     Ix: IndexType,
 646 {
 647     type Map = FixedBitSet;
 648     fn visit_map(&self) -> FixedBitSet {
 649         FixedBitSet::with_capacity(self.node_count())
 650     }
 651
 652     fn reset_map(&self, map: &mut Self::Map) {
 653         map.clear();
 654         map.grow(self.node_count());
 655     }
 656 }
 657
 658 #[cfg(feature = "stable_graph")]
 659 impl<N, E, Ty, Ix> GraphBase for StableGraph<N, E, Ty, Ix>
 660 where
 661     Ix: IndexType,
 662 {
 663     type NodeId = graph::NodeIndex<Ix>;
 664     type EdgeId = graph::EdgeIndex<Ix>;
 665 }
 666
 667 #[cfg(feature = "stable_graph")]
 668 impl<N, E, Ty, Ix> Visitable for StableGraph<N, E, Ty, Ix>
 669 where
 670     Ty: EdgeType,
 671     Ix: IndexType,
 672 {
 673     type Map = FixedBitSet;
 674     fn visit_map(&self) -> FixedBitSet {
 675         FixedBitSet::with_capacity(self.node_bound())
 676     }
 677     fn reset_map(&self, map: &mut Self::Map) {
 678         map.clear();
 679         map.grow(self.node_bound());
 680     }
 681 }
 682
 683 #[cfg(feature = "stable_graph")]
 684 impl<N, E, Ty, Ix> Data for StableGraph<N, E, Ty, Ix>
 685 where
 686     Ty: EdgeType,
 687     Ix: IndexType,
 688 {
 689     type NodeWeight = N;
 690     type EdgeWeight = E;
 691 }
 692
 693 #[cfg(feature = "graphmap")]
 694 impl<N, E, Ty> GraphBase for GraphMap<N, E, Ty>
 695 where
 696     N: Copy + PartialEq,
 697 {
 698     type NodeId = N;
 699     type EdgeId = (N, N);
 700 }
 701
 702 #[cfg(feature = "graphmap")]
 703 impl<N, E, Ty> Visitable for GraphMap<N, E, Ty>
 704 where
 705     N: Copy + Ord + Hash,
 706     Ty: EdgeType,
 707 {
 708     type Map = HashSet<N>;
 709     fn visit_map(&self) -> HashSet<N> {
 710         HashSet::with_capacity(self.node_count())
 711     }
 712     fn reset_map(&self, map: &mut Self::Map) {
 713         map.clear();
 714     }
 715 }
 716
 717 trait_template! {
 718 /// Create or access the adjacency matrix of a graph.
 719 ///
 720 /// The implementor can either create an adjacency matrix, or it can return
 721 /// a placeholder if it has the needed representation internally.
 722 pub trait GetAdjacencyMatrix : GraphBase {
 723     @section type
 724     /// The associated adjacency matrix type
 725     type AdjMatrix;
 726     @section self
 727     /// Create the adjacency matrix
 728     fn adjacency_matrix(self: &Self) -> Self::AdjMatrix;
 729     /// Return true if there is an edge from `a` to `b`, false otherwise.
 730     ///
 731     /// Computes in O(1) time.
 732     fn is_adjacent(self: &Self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool;
 733 }
 734 }
 735
 736 GetAdjacencyMatrix! {delegate_impl []}
 737
 738 #[cfg(feature = "graphmap")]
 739 /// The `GraphMap` keeps an adjacency matrix internally.
 740 impl<N, E, Ty> GetAdjacencyMatrix for GraphMap<N, E, Ty>
 741 where
 742     N: Copy + Ord + Hash,
 743     Ty: EdgeType,
 744 {
 745     type AdjMatrix = ();
 746     #[inline]
 747     fn adjacency_matrix(&self) {}
 748     #[inline]
 749     fn is_adjacent(&self, _: &(), a: N, b: N) -> bool {
 750         self.contains_edge(a, b)
 751     }
 752 }
 753
 754 mod filter;
 755 mod reversed;