vendor/petgraph/src/traits_graph.rs

   1
   2 use fixedbitset::FixedBitSet;
   3
   4 use super::{
   5     EdgeType,
   6 };
   7
   8 use super::graph::{
   9     Graph,
  10     IndexType,
  11     NodeIndex,
  12 };
  13 #[cfg(feature = "stable_graph")]
  14 use stable_graph::StableGraph;
  15 #[cfg(feature = "stable_graph")]
  16 use visit::{NodeIndexable, IntoEdgeReferences};
  17 use visit::EdgeRef;
  18
  19 use super::visit::GetAdjacencyMatrix;
  20
  21 /// The adjacency matrix for **Graph** is a bitmap that's computed by
  22 /// `.adjacency_matrix()`.
  23 impl<N, E, Ty, Ix> GetAdjacencyMatrix for Graph<N, E, Ty, Ix> where
  24     Ty: EdgeType,
  25     Ix: IndexType,
  26 {
  27     type AdjMatrix = FixedBitSet;
  28
  29     fn adjacency_matrix(&self) -> FixedBitSet
  30     {
  31         let n = self.node_count();
  32         let mut matrix = FixedBitSet::with_capacity(n * n);
  33         for edge in self.edge_references() {
  34             let i = edge.source().index() * n + edge.target().index();
  35             matrix.put(i);
  36             if !self.is_directed() {
  37                 let j = edge.source().index() + n * edge.target().index();
  38                 matrix.put(j);
  39             }
  40         }
  41         matrix
  42     }
  43
  44     fn is_adjacent(&self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool
  45     {
  46         let n = self.node_count();
  47         let index = n * a.index() + b.index();
  48         matrix.contains(index)
  49     }
  50 }
  51
  52
  53 #[cfg(feature = "stable_graph")]
  54 /// The adjacency matrix for **Graph** is a bitmap that's computed by
  55 /// `.adjacency_matrix()`.
  56 impl<N, E, Ty, Ix> GetAdjacencyMatrix for StableGraph<N, E, Ty, Ix> where
  57     Ty: EdgeType,
  58     Ix: IndexType,
  59 {
  60     type AdjMatrix = FixedBitSet;
  61
  62     fn adjacency_matrix(&self) -> FixedBitSet
  63     {
  64         let n = self.node_bound();
  65         let mut matrix = FixedBitSet::with_capacity(n * n);
  66         for edge in self.edge_references() {
  67             let i = edge.source().index() * n + edge.target().index();
  68             matrix.put(i);
  69             if !self.is_directed() {
  70                 let j = edge.source().index() + n * edge.target().index();
  71                 matrix.put(j);
  72             }
  73         }
  74         matrix
  75     }
  76
  77     fn is_adjacent(&self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool
  78     {
  79         let n = self.node_count();
  80         let index = n * a.index() + b.index();
  81         matrix.contains(index)
  82     }
  83 }
  84
  85