vendor/petgraph/src/data.rs

   1 //! Graph traits for associated data and graph construction.
   2
   3 use crate::graph::IndexType;
   4 #[cfg(feature = "graphmap")]
   5 use crate::graphmap::{GraphMap, NodeTrait};
   6 #[cfg(feature = "stable_graph")]
   7 use crate::stable_graph::StableGraph;
   8 use crate::visit::{Data, NodeCount, NodeIndexable, Reversed};
   9 use crate::EdgeType;
  10 use crate::Graph;
  11
  12 trait_template! {
  13     /// Access node and edge weights (associated data).
  14 pub trait DataMap : Data {
  15     @section self
  16     fn node_weight(self: &Self, id: Self::NodeId) -> Option<&Self::NodeWeight>;
  17     fn edge_weight(self: &Self, id: Self::EdgeId) -> Option<&Self::EdgeWeight>;
  18 }
  19 }
  20
  21 macro_rules! access0 {
  22     ($e:expr) => {
  23         $e.0
  24     };
  25 }
  26
  27 DataMap! {delegate_impl []}
  28 DataMap! {delegate_impl [['a, G], G, &'a mut G, deref_twice]}
  29 DataMap! {delegate_impl [[G], G, Reversed<G>, access0]}
  30
  31 trait_template! {
  32     /// Access node and edge weights mutably.
  33 pub trait DataMapMut : DataMap {
  34     @section self
  35     fn node_weight_mut(self: &mut Self, id: Self::NodeId) -> Option<&mut Self::NodeWeight>;
  36     fn edge_weight_mut(self: &mut Self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight>;
  37 }
  38 }
  39
  40 DataMapMut! {delegate_impl [['a, G], G, &'a mut G, deref_twice]}
  41 DataMapMut! {delegate_impl [[G], G, Reversed<G>, access0]}
  42
  43 /// A graph that can be extended with further nodes and edges
  44 pub trait Build: Data + NodeCount {
  45     fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId;
  46     /// Add a new edge. If parallel edges (duplicate) are not allowed and
  47     /// the edge already exists, return `None`.
  48     fn add_edge(
  49         &mut self,
  50         a: Self::NodeId,
  51         b: Self::NodeId,
  52         weight: Self::EdgeWeight,
  53     ) -> Option<Self::EdgeId> {
  54         Some(self.update_edge(a, b, weight))
  55     }
  56     /// Add or update the edge from `a` to `b`. Return the id of the affected
  57     /// edge.
  58     fn update_edge(
  59         &mut self,
  60         a: Self::NodeId,
  61         b: Self::NodeId,
  62         weight: Self::EdgeWeight,
  63     ) -> Self::EdgeId;
  64 }
  65
  66 /// A graph that can be created
  67 pub trait Create: Build + Default {
  68     fn with_capacity(nodes: usize, edges: usize) -> Self;
  69 }
  70
  71 impl<N, E, Ty, Ix> Data for Graph<N, E, Ty, Ix>
  72 where
  73     Ix: IndexType,
  74 {
  75     type NodeWeight = N;
  76     type EdgeWeight = E;
  77 }
  78
  79 impl<N, E, Ty, Ix> DataMap for Graph<N, E, Ty, Ix>
  80 where
  81     Ty: EdgeType,
  82     Ix: IndexType,
  83 {
  84     fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
  85         self.node_weight(id)
  86     }
  87     fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
  88         self.edge_weight(id)
  89     }
  90 }
  91
  92 impl<N, E, Ty, Ix> DataMapMut for Graph<N, E, Ty, Ix>
  93 where
  94     Ty: EdgeType,
  95     Ix: IndexType,
  96 {
  97     fn node_weight_mut(&mut self, id: Self::NodeId) -> Option<&mut Self::NodeWeight> {
  98         self.node_weight_mut(id)
  99     }
 100     fn edge_weight_mut(&mut self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight> {
 101         self.edge_weight_mut(id)
 102     }
 103 }
 104
 105 #[cfg(feature = "stable_graph")]
 106 impl<N, E, Ty, Ix> DataMap for StableGraph<N, E, Ty, Ix>
 107 where
 108     Ty: EdgeType,
 109     Ix: IndexType,
 110 {
 111     fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
 112         self.node_weight(id)
 113     }
 114     fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
 115         self.edge_weight(id)
 116     }
 117 }
 118
 119 #[cfg(feature = "stable_graph")]
 120 impl<N, E, Ty, Ix> DataMapMut for StableGraph<N, E, Ty, Ix>
 121 where
 122     Ty: EdgeType,
 123     Ix: IndexType,
 124 {
 125     fn node_weight_mut(&mut self, id: Self::NodeId) -> Option<&mut Self::NodeWeight> {
 126         self.node_weight_mut(id)
 127     }
 128     fn edge_weight_mut(&mut self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight> {
 129         self.edge_weight_mut(id)
 130     }
 131 }
 132
 133 impl<N, E, Ty, Ix> Build for Graph<N, E, Ty, Ix>
 134 where
 135     Ty: EdgeType,
 136     Ix: IndexType,
 137 {
 138     fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
 139         self.add_node(weight)
 140     }
 141     fn add_edge(
 142         &mut self,
 143         a: Self::NodeId,
 144         b: Self::NodeId,
 145         weight: Self::EdgeWeight,
 146     ) -> Option<Self::EdgeId> {
 147         Some(self.add_edge(a, b, weight))
 148     }
 149     fn update_edge(
 150         &mut self,
 151         a: Self::NodeId,
 152         b: Self::NodeId,
 153         weight: Self::EdgeWeight,
 154     ) -> Self::EdgeId {
 155         self.update_edge(a, b, weight)
 156     }
 157 }
 158
 159 #[cfg(feature = "stable_graph")]
 160 impl<N, E, Ty, Ix> Build for StableGraph<N, E, Ty, Ix>
 161 where
 162     Ty: EdgeType,
 163     Ix: IndexType,
 164 {
 165     fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
 166         self.add_node(weight)
 167     }
 168     fn add_edge(
 169         &mut self,
 170         a: Self::NodeId,
 171         b: Self::NodeId,
 172         weight: Self::EdgeWeight,
 173     ) -> Option<Self::EdgeId> {
 174         Some(self.add_edge(a, b, weight))
 175     }
 176     fn update_edge(
 177         &mut self,
 178         a: Self::NodeId,
 179         b: Self::NodeId,
 180         weight: Self::EdgeWeight,
 181     ) -> Self::EdgeId {
 182         self.update_edge(a, b, weight)
 183     }
 184 }
 185
 186 #[cfg(feature = "graphmap")]
 187 impl<N, E, Ty> Build for GraphMap<N, E, Ty>
 188 where
 189     Ty: EdgeType,
 190     N: NodeTrait,
 191 {
 192     fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
 193         self.add_node(weight)
 194     }
 195     fn add_edge(
 196         &mut self,
 197         a: Self::NodeId,
 198         b: Self::NodeId,
 199         weight: Self::EdgeWeight,
 200     ) -> Option<Self::EdgeId> {
 201         if self.contains_edge(a, b) {
 202             None
 203         } else {
 204             let r = self.add_edge(a, b, weight);
 205             debug_assert!(r.is_none());
 206             Some((a, b))
 207         }
 208     }
 209     fn update_edge(
 210         &mut self,
 211         a: Self::NodeId,
 212         b: Self::NodeId,
 213         weight: Self::EdgeWeight,
 214     ) -> Self::EdgeId {
 215         self.add_edge(a, b, weight);
 216         (a, b)
 217     }
 218 }
 219
 220 impl<N, E, Ty, Ix> Create for Graph<N, E, Ty, Ix>
 221 where
 222     Ty: EdgeType,
 223     Ix: IndexType,
 224 {
 225     fn with_capacity(nodes: usize, edges: usize) -> Self {
 226         Self::with_capacity(nodes, edges)
 227     }
 228 }
 229
 230 #[cfg(feature = "stable_graph")]
 231 impl<N, E, Ty, Ix> Create for StableGraph<N, E, Ty, Ix>
 232 where
 233     Ty: EdgeType,
 234     Ix: IndexType,
 235 {
 236     fn with_capacity(nodes: usize, edges: usize) -> Self {
 237         Self::with_capacity(nodes, edges)
 238     }
 239 }
 240
 241 #[cfg(feature = "graphmap")]
 242 impl<N, E, Ty> Create for GraphMap<N, E, Ty>
 243 where
 244     Ty: EdgeType,
 245     N: NodeTrait,
 246 {
 247     fn with_capacity(nodes: usize, edges: usize) -> Self {
 248         Self::with_capacity(nodes, edges)
 249     }
 250 }
 251
 252 /// A graph element.
 253 ///
 254 /// A sequence of Elements, for example an iterator, is laid out as follows:
 255 /// Nodes are implicitly given the index of their appearance in the sequence.
 256 /// The edges’ source and target fields refer to these indices.
 257 #[derive(Clone, Debug, PartialEq, Eq)]
 258 pub enum Element<N, E> {
 259     /// A graph node.
 260     Node { weight: N },
 261     /// A graph edge.
 262     Edge {
 263         source: usize,
 264         target: usize,
 265         weight: E,
 266     },
 267 }
 268
 269 /// Create a graph from an iterator of elements.
 270 pub trait FromElements: Create {
 271     fn from_elements<I>(iterable: I) -> Self
 272     where
 273         Self: Sized,
 274         I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
 275     {
 276         let mut gr = Self::with_capacity(0, 0);
 277         // usize -> NodeId map
 278         let mut map = Vec::new();
 279         for element in iterable {
 280             match element {
 281                 Element::Node { weight } => {
 282                     map.push(gr.add_node(weight));
 283                 }
 284                 Element::Edge {
 285                     source,
 286                     target,
 287                     weight,
 288                 } => {
 289                     gr.add_edge(map[source], map[target], weight);
 290                 }
 291             }
 292         }
 293         gr
 294     }
 295 }
 296
 297 fn from_elements_indexable<G, I>(iterable: I) -> G
 298 where
 299     G: Create + NodeIndexable,
 300     I: IntoIterator<Item = Element<G::NodeWeight, G::EdgeWeight>>,
 301 {
 302     let mut gr = G::with_capacity(0, 0);
 303     let map = |gr: &G, i| gr.from_index(i);
 304     for element in iterable {
 305         match element {
 306             Element::Node { weight } => {
 307                 gr.add_node(weight);
 308             }
 309             Element::Edge {
 310                 source,
 311                 target,
 312                 weight,
 313             } => {
 314                 let from = map(&gr, source);
 315                 let to = map(&gr, target);
 316                 gr.add_edge(from, to, weight);
 317             }
 318         }
 319     }
 320     gr
 321 }
 322
 323 impl<N, E, Ty, Ix> FromElements for Graph<N, E, Ty, Ix>
 324 where
 325     Ty: EdgeType,
 326     Ix: IndexType,
 327 {
 328     fn from_elements<I>(iterable: I) -> Self
 329     where
 330         Self: Sized,
 331         I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
 332     {
 333         from_elements_indexable(iterable)
 334     }
 335 }
 336
 337 #[cfg(feature = "stable_graph")]
 338 impl<N, E, Ty, Ix> FromElements for StableGraph<N, E, Ty, Ix>
 339 where
 340     Ty: EdgeType,
 341     Ix: IndexType,
 342 {
 343     fn from_elements<I>(iterable: I) -> Self
 344     where
 345         Self: Sized,
 346         I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
 347     {
 348         from_elements_indexable(iterable)
 349     }
 350 }
 351
 352 #[cfg(feature = "graphmap")]
 353 impl<N, E, Ty> FromElements for GraphMap<N, E, Ty>
 354 where
 355     Ty: EdgeType,
 356     N: NodeTrait,
 357 {
 358     fn from_elements<I>(iterable: I) -> Self
 359     where
 360         Self: Sized,
 361         I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
 362     {
 363         from_elements_indexable(iterable)
 364     }
 365 }
 366
 367 /// Iterator adaptors for iterators of `Element`.
 368 pub trait ElementIterator<N, E>: Iterator<Item = Element<N, E>> {
 369     /// Create an iterator adaptor that filters graph elements.
 370     ///
 371     /// The function `f` is called with each element and if its return value
 372     /// is `true` the element is accepted and if `false` it is removed.
 373     /// `f` is called with mutable references to the node and edge weights,
 374     /// so that they can be mutated (but the edge endpoints can not).
 375     ///
 376     /// This filter adapts the edge source and target indices in the
 377     /// stream so that they are correct after the removals.
 378     fn filter_elements<F>(self, f: F) -> FilterElements<Self, F>
 379     where
 380         Self: Sized,
 381         F: FnMut(Element<&mut N, &mut E>) -> bool,
 382     {
 383         FilterElements {
 384             iter: self,
 385             node_index: 0,
 386             map: Vec::new(),
 387             f,
 388         }
 389     }
 390 }
 391
 392 impl<N, E, I: ?Sized> ElementIterator<N, E> for I where I: Iterator<Item = Element<N, E>> {}
 393
 394 /// An iterator that filters graph elements.
 395 ///
 396 /// See [`.filter_elements()`][1] for more information.
 397 ///
 398 /// [1]: trait.ElementIterator.html#method.filter_elements
 399 pub struct FilterElements<I, F> {
 400     iter: I,
 401     node_index: usize,
 402     map: Vec<usize>,
 403     f: F,
 404 }
 405
 406 impl<I, F, N, E> Iterator for FilterElements<I, F>
 407 where
 408     I: Iterator<Item = Element<N, E>>,
 409     F: FnMut(Element<&mut N, &mut E>) -> bool,
 410 {
 411     type Item = Element<N, E>;
 412
 413     fn next(&mut self) -> Option<Self::Item> {
 414         loop {
 415             let mut elt = match self.iter.next() {
 416                 None => return None,
 417                 Some(elt) => elt,
 418             };
 419             let keep = (self.f)(match elt {
 420                 Element::Node { ref mut weight } => Element::Node { weight },
 421                 Element::Edge {
 422                     source,
 423                     target,
 424                     ref mut weight,
 425                 } => Element::Edge {
 426                     source,
 427                     target,
 428                     weight,
 429                 },
 430             });
 431             let is_node = if let Element::Node { .. } = elt {
 432                 true
 433             } else {
 434                 false
 435             };
 436             if !keep && is_node {
 437                 self.map.push(self.node_index);
 438             }
 439             if is_node {
 440                 self.node_index += 1;
 441             }
 442             if !keep {
 443                 continue;
 444             }
 445
 446             // map edge parts
 447             match elt {
 448                 Element::Edge {
 449                     ref mut source,
 450                     ref mut target,
 451                     ..
 452                 } => {
 453                     // Find the node indices in the map of removed ones.
 454                     // If a node was removed, the edge is as well.
 455                     // Otherwise the counts are adjusted by the number of nodes
 456                     // removed.
 457                     // Example: map: [1, 3, 4, 6]
 458                     // binary search for 2, result is Err(1). One node has been
 459                     // removed before 2.
 460                     match self.map.binary_search(source) {
 461                         Ok(_) => continue,
 462                         Err(i) => *source -= i,
 463                     }
 464                     match self.map.binary_search(target) {
 465                         Ok(_) => continue,
 466                         Err(i) => *target -= i,
 467                     }
 468                 }
 469                 Element::Node { .. } => {}
 470             }
 471             return Some(elt);
 472         }
 473     }
 474 }