fera_graph/algs/
sets.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5//! Iterators for edge and vertex set complements.
6
7use params::IntoOwned;
8use prelude::*;
9
10pub trait Sets {
11    fn vertices_complement<I>(&self, vertices: I) -> VerticesComplement<Self>
12    where
13        Self: VertexList + WithVertexProp<bool>,
14        I: IntoIterator,
15        I::Item: IntoOwned<Vertex<Self>>,
16    {
17        let mut set = self.default_vertex_prop(false);
18        set.set_values(vertices, true);
19        VerticesComplement {
20            vertices: self.vertices(),
21            set,
22        }
23    }
24
25    fn edges_complement<I>(&self, edges: I) -> EdgesComplement<Self>
26    where
27        Self: EdgeList + WithEdgeProp<bool>,
28        I: IntoIterator,
29        I::Item: IntoOwned<Edge<Self>>,
30    {
31        let mut set = self.default_edge_prop(false);
32        set.set_values(edges, true);
33        EdgesComplement {
34            edges: self.edges(),
35            set,
36        }
37    }
38
39    fn independent_vertex_set_from_iter<I>(
40        &self,
41        vertices: I,
42    ) -> IndependentVertexSetFromIter<Self, I::IntoIter>
43    where
44        Self: Adjacency + WithVertexProp<bool>,
45        I: IntoIterator,
46        I::Item: IntoOwned<Vertex<Self>>,
47    {
48        IndependentVertexSetFromIter {
49            g: self,
50            vertices: vertices.into_iter(),
51            marked: self.default_vertex_prop(false),
52        }
53    }
54
55    fn is_independent_vertex_set<I>(&self, vertices: I) -> bool
56    where
57        Self: Adjacency + WithVertexProp<bool>,
58        I: IntoIterator,
59        I::Item: IntoOwned<Vertex<Self>>,
60    {
61        let mut marked = self.default_vertex_prop(false);
62        for v in vertices {
63            let v = v.into_owned();
64            if marked[v] {
65                return false;
66            }
67            marked.set_values(self.out_neighbors(v), true);
68        }
69        true
70    }
71}
72
73impl<G> Sets for G {}
74
75pub struct VerticesComplement<'a, G>
76where
77    G: 'a + WithVertex + WithVertexProp<bool>,
78{
79    vertices: VertexIter<'a, G>,
80    set: DefaultVertexPropMut<G, bool>,
81}
82
83impl<'a, G> Iterator for VerticesComplement<'a, G>
84where
85    G: 'a + WithVertex + WithVertexProp<bool>,
86{
87    type Item = Vertex<G>;
88
89    fn next(&mut self) -> Option<Self::Item> {
90        for e in self.vertices.by_ref() {
91            if !self.set[e] {
92                return Some(e);
93            }
94        }
95        None
96    }
97}
98
99pub struct EdgesComplement<'a, G>
100where
101    G: 'a + WithEdge + WithEdgeProp<bool>,
102{
103    edges: EdgeIter<'a, G>,
104    set: DefaultEdgePropMut<G, bool>,
105}
106
107impl<'a, G> Iterator for EdgesComplement<'a, G>
108where
109    G: 'a + WithEdge + WithEdgeProp<bool>,
110{
111    type Item = Edge<G>;
112
113    fn next(&mut self) -> Option<Self::Item> {
114        for e in self.edges.by_ref() {
115            if !self.set[e] {
116                return Some(e);
117            }
118        }
119        None
120    }
121}
122
123pub struct IndependentVertexSetFromIter<'a, G, I>
124where
125    G: 'a + Adjacency + WithVertexProp<bool>,
126{
127    g: &'a G,
128    vertices: I,
129    marked: DefaultVertexPropMut<G, bool>,
130}
131
132impl<'a, G, I> Iterator for IndependentVertexSetFromIter<'a, G, I>
133where
134    G: 'a + Adjacency + WithVertexProp<bool>,
135    I: Iterator,
136    I::Item: IntoOwned<Vertex<G>>,
137{
138    type Item = Vertex<G>;
139
140    fn next(&mut self) -> Option<Self::Item> {
141        for v in self.vertices.by_ref() {
142            let v = v.into_owned();
143            if self.marked[v] {
144                continue;
145            }
146            self.marked[v] = true;
147            self.marked.set_values(self.g.out_neighbors(v), true);
148            return Some(v);
149        }
150        None
151    }
152}
fera_graph/algs/sets.rs

fera_graph/algs/
sets.rs
