petgraph/
data.rs

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

petgraph/
data.rs
