/rust/registry/src/index.crates.io-1949cf8c6b5b557f/petgraph-0.8.3/src/data.rs

Source
//! Graph traits for associated data and graph construction.

use alloc::vec::Vec;

use crate::graph::IndexType;
use crate::visit::{Data, NodeCount, NodeIndexable, Reversed};
use crate::EdgeType;
use crate::Graph;

#[cfg(feature = "stable_graph")]
use crate::stable_graph::StableGraph;

#[cfg(feature = "graphmap")]
use {
    crate::graphmap::{GraphMap, NodeTrait},
    core::hash::BuildHasher,
};

trait_template! {
    /// Access node and edge weights (associated data).
#[allow(clippy::needless_arbitrary_self_type)]
pub trait DataMap : Data {
    @section self
    fn node_weight(self: &Self, id: Self::NodeId) -> Option<&Self::NodeWeight>;
    fn edge_weight(self: &Self, id: Self::EdgeId) -> Option<&Self::EdgeWeight>;
}
}

macro_rules! access0 {
    ($e:expr) => {
        $e.0
    };
}

DataMap! {delegate_impl []}
DataMap! {delegate_impl [['a, G], G, &'a mut G, deref_twice]}
DataMap! {delegate_impl [[G], G, Reversed<G>, access0]}

trait_template! {
    /// Access node and edge weights mutably.
#[allow(clippy::needless_arbitrary_self_type)]
pub trait DataMapMut : DataMap {
    @section self
    fn node_weight_mut(self: &mut Self, id: Self::NodeId) -> Option<&mut Self::NodeWeight>;
    fn edge_weight_mut(self: &mut Self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight>;
}
}

DataMapMut! {delegate_impl [['a, G], G, &'a mut G, deref_twice]}
DataMapMut! {delegate_impl [[G], G, Reversed<G>, access0]}

/// A graph that can be extended with further nodes and edges
pub trait Build: Data + NodeCount {
    fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId;
    /// Add a new edge. If parallel edges (duplicate) are not allowed and
    /// the edge already exists, return `None`.
    ///
    /// Might panic if `a` or `b` are out of bounds.
    #[track_caller]
    fn add_edge(
        &mut self,
        a: Self::NodeId,
        b: Self::NodeId,
        weight: Self::EdgeWeight,
    ) -> Option<Self::EdgeId> {
        Some(self.update_edge(a, b, weight))
    }
    /// Add or update the edge from `a` to `b`. Return the id of the affected
    /// edge.
    ///
    /// Might panic if `a` or `b` are out of bounds.
    #[track_caller]
    fn update_edge(
        &mut self,
        a: Self::NodeId,
        b: Self::NodeId,
        weight: Self::EdgeWeight,
    ) -> Self::EdgeId;
}

/// A graph that can be created
pub trait Create: Build + Default {
    fn with_capacity(nodes: usize, edges: usize) -> Self;
}

impl<N, E, Ty, Ix> Data for Graph<N, E, Ty, Ix>
where
    Ix: IndexType,
{
    type NodeWeight = N;
    type EdgeWeight = E;
}

impl<N, E, Ty, Ix> DataMap for Graph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
        self.node_weight(id)
    }
    fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
        self.edge_weight(id)
    }
}

impl<N, E, Ty, Ix> DataMapMut for Graph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn node_weight_mut(&mut self, id: Self::NodeId) -> Option<&mut Self::NodeWeight> {
        self.node_weight_mut(id)
    }
    fn edge_weight_mut(&mut self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight> {
        self.edge_weight_mut(id)
    }
}

#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> DataMap for StableGraph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
        self.node_weight(id)
    }
    fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
        self.edge_weight(id)
    }
}

#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> DataMapMut for StableGraph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn node_weight_mut(&mut self, id: Self::NodeId) -> Option<&mut Self::NodeWeight> {
        self.node_weight_mut(id)
    }
    fn edge_weight_mut(&mut self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight> {
        self.edge_weight_mut(id)
    }
}

impl<N, E, Ty, Ix> Build for Graph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
        self.add_node(weight)
    }
    fn add_edge(
        &mut self,
        a: Self::NodeId,
        b: Self::NodeId,
        weight: Self::EdgeWeight,
    ) -> Option<Self::EdgeId> {
        Some(self.add_edge(a, b, weight))
    }
    fn update_edge(
        &mut self,
        a: Self::NodeId,
        b: Self::NodeId,
        weight: Self::EdgeWeight,
    ) -> Self::EdgeId {
        self.update_edge(a, b, weight)
    }
}

#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> Build for StableGraph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
        self.add_node(weight)
    }
    fn add_edge(
        &mut self,
        a: Self::NodeId,
        b: Self::NodeId,
        weight: Self::EdgeWeight,
    ) -> Option<Self::EdgeId> {
        Some(self.add_edge(a, b, weight))
    }
    fn update_edge(
        &mut self,
        a: Self::NodeId,
        b: Self::NodeId,
        weight: Self::EdgeWeight,
    ) -> Self::EdgeId {
        self.update_edge(a, b, weight)
    }
}

#[cfg(feature = "graphmap")]
impl<N, E, Ty, S> Build for GraphMap<N, E, Ty, S>
where
    Ty: EdgeType,
    N: NodeTrait,
    S: BuildHasher,
{
    fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
        self.add_node(weight)
    }
    fn add_edge(
        &mut self,
        a: Self::NodeId,
        b: Self::NodeId,
        weight: Self::EdgeWeight,
    ) -> Option<Self::EdgeId> {
        if self.contains_edge(a, b) {
            None
        } else {
            let r = self.add_edge(a, b, weight);
            debug_assert!(r.is_none());
            Some((a, b))
        }
    }
    fn update_edge(
        &mut self,
        a: Self::NodeId,
        b: Self::NodeId,
        weight: Self::EdgeWeight,
    ) -> Self::EdgeId {
        self.add_edge(a, b, weight);
        (a, b)
    }
}

impl<N, E, Ty, Ix> Create for Graph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn with_capacity(nodes: usize, edges: usize) -> Self {
        Self::with_capacity(nodes, edges)
    }
}

#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> Create for StableGraph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn with_capacity(nodes: usize, edges: usize) -> Self {
        Self::with_capacity(nodes, edges)
    }
}

#[cfg(feature = "graphmap")]
impl<N, E, Ty, S> Create for GraphMap<N, E, Ty, S>
where
    Ty: EdgeType,
    N: NodeTrait,
    S: BuildHasher + Default,
{
    fn with_capacity(nodes: usize, edges: usize) -> Self {
        Self::with_capacity(nodes, edges)
    }
}

/// A graph element.
///
/// A sequence of Elements, for example an iterator, is laid out as follows:
/// Nodes are implicitly given the index of their appearance in the sequence.
/// The edges’ source and target fields refer to these indices.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Element<N, E> {
    /// A graph node.
    Node { weight: N },
    /// A graph edge.
    Edge {
        source: usize,
        target: usize,
        weight: E,
    },
}

/// Create a graph from an iterator of elements.
pub trait FromElements: Create {
    fn from_elements<I>(iterable: I) -> Self
    where
        Self: Sized,
        I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
    {
        let mut gr = Self::with_capacity(0, 0);
        // usize -> NodeId map
        let mut map = Vec::new();
        for element in iterable {
            match element {
                Element::Node { weight } => {
                    map.push(gr.add_node(weight));
                }
                Element::Edge {
                    source,
                    target,
                    weight,
                } => {
                    gr.add_edge(map[source], map[target], weight);
                }
            }
        }
        gr
    }
}

fn from_elements_indexable<G, I>(iterable: I) -> G
where
    G: Create + NodeIndexable,
    I: IntoIterator<Item = Element<G::NodeWeight, G::EdgeWeight>>,
{
    let mut gr = G::with_capacity(0, 0);
    let map = |gr: &G, i| gr.from_index(i);
    for element in iterable {
        match element {
            Element::Node { weight } => {
                gr.add_node(weight);
            }
            Element::Edge {
                source,
                target,
                weight,
            } => {
                let from = map(&gr, source);
                let to = map(&gr, target);
                gr.add_edge(from, to, weight);
            }
        }
    }
    gr
}

impl<N, E, Ty, Ix> FromElements for Graph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn from_elements<I>(iterable: I) -> Self
    where
        Self: Sized,
        I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
    {
        from_elements_indexable(iterable)
    }
}

#[cfg(feature = "stable_graph")]
impl<N, E, Ty, Ix> FromElements for StableGraph<N, E, Ty, Ix>
where
    Ty: EdgeType,
    Ix: IndexType,
{
    fn from_elements<I>(iterable: I) -> Self
    where
        Self: Sized,
        I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
    {
        from_elements_indexable(iterable)
    }
}

#[cfg(feature = "graphmap")]
impl<N, E, Ty, S> FromElements for GraphMap<N, E, Ty, S>
where
    Ty: EdgeType,
    N: NodeTrait,
    S: BuildHasher + Default,
{
    fn from_elements<I>(iterable: I) -> Self
    where
        Self: Sized,
        I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
    {
        from_elements_indexable(iterable)
    }
}

/// Iterator adaptors for iterators of `Element`.
pub trait ElementIterator<N, E>: Iterator<Item = Element<N, E>> {
    /// Create an iterator adaptor that filters graph elements.
    ///
    /// The function `f` is called with each element and if its return value
    /// is `true` the element is accepted and if `false` it is removed.
    /// `f` is called with mutable references to the node and edge weights,
    /// so that they can be mutated (but the edge endpoints can not).
    ///
    /// This filter adapts the edge source and target indices in the
    /// stream so that they are correct after the removals.
    fn filter_elements<F>(self, f: F) -> FilterElements<Self, F>
    where
        Self: Sized,
        F: FnMut(Element<&mut N, &mut E>) -> bool,
    {
        FilterElements {
            iter: self,
            node_index: 0,
            map: Vec::new(),
            f,
        }
    }
}

impl<N, E, I: ?Sized> ElementIterator<N, E> for I where I: Iterator<Item = Element<N, E>> {}

/// An iterator that filters graph elements.
///
/// See [`.filter_elements()`][1] for more information.
///
/// [1]: trait.ElementIterator.html#method.filter_elements
#[derive(Debug, Clone)]
pub struct FilterElements<I, F> {
    iter: I,
    node_index: usize,
    map: Vec<usize>,
    f: F,
}

impl<I, F, N, E> Iterator for FilterElements<I, F>
where
    I: Iterator<Item = Element<N, E>>,
    F: FnMut(Element<&mut N, &mut E>) -> bool,
{
    type Item = Element<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let mut elt = self.iter.next()?;
            let keep = (self.f)(match elt {
                Element::Node { ref mut weight } => Element::Node { weight },
                Element::Edge {
                    source,
                    target,
                    ref mut weight,
                } => Element::Edge {
                    source,
                    target,
                    weight,
                },
            });
            let is_node = matches!(elt, Element::Node { .. });
            if !keep && is_node {
                self.map.push(self.node_index);
            }
            if is_node {
                self.node_index += 1;
            }
            if !keep {
                continue;
            }

            // map edge parts
            match elt {
                Element::Edge {
                    ref mut source,
                    ref mut target,
                    ..
                } => {
                    // Find the node indices in the map of removed ones.
                    // If a node was removed, the edge is as well.
                    // Otherwise the counts are adjusted by the number of nodes
                    // removed.
                    // Example: map: [1, 3, 4, 6]
                    // binary search for 2, result is Err(1). One node has been
                    // removed before 2.
                    match self.map.binary_search(source) {
                        Ok(_) => continue,
                        Err(i) => *source -= i,
                    }
                    match self.map.binary_search(target) {
                        Ok(_) => continue,
                        Err(i) => *target -= i,
                    }
                }
                Element::Node { .. } => {}
            }
            return Some(elt);
        }
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        let (_, upper) = self.iter.size_hint();
        (0, upper)
    }
}

Coverage Report

Created: 2025-12-11 06:38

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