prepona/graph/subgraph/
mr_subgraph.rs

1use std::collections::HashSet;
2
3use anyhow::{Context, Result};
4
5use crate::{
6    graph::error::Error,
7    provide::{Edges, Graph, Neighbors, Vertices},
8};
9
10use super::{AsFrozenSubgraph, AsSubgraph, Subgraph};
11use crate::graph::{Edge, EdgeDir};
12
13/// A subgraph with some vertices elected as root.
14///
15/// ## Note
16/// From now on:
17/// * |R|: Means number of roots in the subgraph.
18///
19/// ## Generic Parameters
20/// * `W`: **W**eight type associated with edges.
21/// * `E`: **E**dge type that graph uses.
22/// * `Dir`: **Dir**ection of edges: [`Directed`](crate::graph::DirectedEdge) or [`Undirected`](crate::graph::UndirectedEdge).
23/// * `G`: **G**raph type that subgraph is representing.
24pub struct MultiRootSubgraph<'a, W, E, Dir, G>
25where
26    E: Edge<W>,
27    Dir: EdgeDir,
28    G: Graph<W, E, Dir> + Edges<W, E> + Neighbors,
29{
30    roots: Vec<usize>,
31    subgraph: Subgraph<'a, W, E, Dir, G>,
32}
33
34impl<'a, W, E, Dir, G> MultiRootSubgraph<'a, W, E, Dir, G>
35where
36    E: Edge<W>,
37    Dir: EdgeDir,
38    G: Graph<W, E, Dir> + Edges<W, E> + Neighbors + Vertices,
39{
40    /// # Arguments
41    /// * `graph`: Graph that owns the `edges` and `vertices`.
42    /// * `edges`: Edges that are in the subgraph in the format of: (src_id, dst_id, edge).
43    /// * `vertices`: Vertices that are in the subgraph.
44    /// * `roots`: Roots of the subgraph.
45    ///
46    /// # Returns
47    /// Initialized subgraph containing the specified `edges` and `vertices` and `roots` as roots of the subgraph.
48    pub fn init(
49        graph: &'a G,
50        edges: Vec<(usize, usize, usize)>,
51        vertices: HashSet<usize>,
52        roots: Vec<usize>,
53    ) -> Self {
54        MultiRootSubgraph {
55            roots,
56            subgraph: Subgraph::init(graph, edges, vertices),
57        }
58    }
59
60    /// # Returns
61    /// Roots of the subgraph.
62    ///
63    /// # Complexity
64    /// O(1)
65    pub fn roots(&self) -> &Vec<usize> {
66        &self.roots
67    }
68
69    /// # Arguments
70    /// `vertex_id`: Id of the vertex to be checked wether is a root or not.
71    ///
72    /// # Returns
73    /// * `true`: If vertex with id: `vertex_id` is a root.
74    /// * `false`: Otherwise.
75    ///
76    /// # Complexity
77    /// O(|R|)
78    pub fn is_root(&self, vertex_id: usize) -> bool {
79        self.roots.contains(&vertex_id)
80    }
81
82    /// Adds a new root to the set of roots.
83    ///
84    /// # Arguments
85    /// `vertex_id`: Id of the vertex to be added as root.
86    ///
87    /// # Returns
88    /// * `Err`:
89    ///     * If root with specified id already exists
90    ///     * Error of calling `add_vertex_from_graph`.
91    /// * `Ok`:
92    pub fn add_root(&mut self, vertex_id: usize) -> Result<()> {
93        if self.is_root(vertex_id) {
94            Err(Error::new_rae(vertex_id)).with_context(|| "MultiRootSubgraph failed")?
95        } else {
96            self.add_vertex_from_graph(vertex_id)?;
97
98            self.roots.push(vertex_id);
99
100            Ok(())
101        }
102    }
103
104    /// Adds a new root to the set of roots.
105    ///
106    /// # Arguments
107    /// `vertex_id`: Id of the vertex to be added as root.
108    pub fn add_root_unchecked(&mut self, vertex_id: usize) {
109        self.add_vertex_from_graph_unchecked(vertex_id);
110
111        self.roots.push(vertex_id);
112    }
113}
114
115/// `MultiRootSubgraph` uses `Subgraph` internally so for more info checkout [`Subgraph`](crate::graph::subgraph::Subgraph).
116impl<'a, W, E, Dir, G> Neighbors for MultiRootSubgraph<'a, W, E, Dir, G>
117where
118    E: Edge<W>,
119    Dir: EdgeDir,
120    G: Graph<W, E, Dir> + Edges<W, E> + Neighbors,
121{
122    fn neighbors(&self, src_id: usize) -> anyhow::Result<Vec<usize>> {
123        self.subgraph.neighbors(src_id)
124    }
125
126    fn neighbors_unchecked(&self, src_id: usize) -> Vec<usize> {
127        self.subgraph.neighbors_unchecked(src_id)
128    }
129}
130
131/// `MultiRootSubgraph` uses `Subgraph` internally so for more info checkout [`Subgraph`](crate::graph::subgraph::Subgraph).
132impl<'a, W, E, Dir, G> Vertices for MultiRootSubgraph<'a, W, E, Dir, G>
133where
134    E: Edge<W>,
135    Dir: EdgeDir,
136    G: Graph<W, E, Dir> + Edges<W, E> + Neighbors,
137{
138    fn vertices(&self) -> Vec<usize> {
139        self.subgraph.vertices()
140    }
141
142    fn contains_vertex(&self, vertex_id: usize) -> bool {
143        self.subgraph.contains_vertex(vertex_id)
144    }
145}
146
147/// `MultiRootSubgraph` uses `Subgraph` internally so for more info checkout [`Subgraph`](crate::graph::subgraph::Subgraph).
148impl<'a, W, E, Dir, G> Edges<W, E> for MultiRootSubgraph<'a, W, E, Dir, G>
149where
150    E: Edge<W>,
151    Dir: EdgeDir,
152    G: Graph<W, E, Dir> + Edges<W, E> + Neighbors,
153{
154    fn edges_from(&self, src_id: usize) -> anyhow::Result<Vec<(usize, &E)>> {
155        self.subgraph.edges_from(src_id)
156    }
157
158    fn edges_from_unchecked(&self, src_id: usize) -> Vec<(usize, &E)> {
159        self.subgraph.edges_from_unchecked(src_id)
160    }
161
162    fn edges_between(&self, src_id: usize, dst_id: usize) -> anyhow::Result<Vec<&E>> {
163        self.subgraph.edges_between(src_id, dst_id)
164    }
165
166    fn edges_between_unchecked(&self, src_id: usize, dst_id: usize) -> Vec<&E> {
167        self.subgraph.edges_between_unchecked(src_id, dst_id)
168    }
169
170    fn edge_between(&self, src_id: usize, dst_id: usize, edge_id: usize) -> anyhow::Result<&E> {
171        self.subgraph.edge_between(src_id, dst_id, edge_id)
172    }
173
174    fn edge_between_unchecked(&self, src_id: usize, dst_id: usize, edge_id: usize) -> &E {
175        self.subgraph
176            .edge_between_unchecked(src_id, dst_id, edge_id)
177    }
178
179    fn edge(&self, edge_id: usize) -> anyhow::Result<&E> {
180        self.subgraph.edge(edge_id)
181    }
182
183    fn edge_unchecked(&self, edge_id: usize) -> &E {
184        self.subgraph.edge_unchecked(edge_id)
185    }
186
187    fn has_any_edge(&self, src_id: usize, dst_id: usize) -> anyhow::Result<bool> {
188        self.subgraph.has_any_edge(src_id, dst_id)
189    }
190
191    fn has_any_edge_unchecked(&self, src_id: usize, dst_id: usize) -> bool {
192        self.subgraph.has_any_edge_unchecked(src_id, dst_id)
193    }
194
195    fn edges(&self) -> Vec<(usize, usize, &E)> {
196        self.subgraph.edges()
197    }
198
199    fn as_directed_edges(&self) -> Vec<(usize, usize, &E)> {
200        self.subgraph.as_directed_edges()
201    }
202
203    fn edges_count(&self) -> usize {
204        self.subgraph.edges_count()
205    }
206
207    fn contains_edge(&self, edge_id: usize) -> bool {
208        self.subgraph.contains_edge(edge_id)
209    }
210}
211
212impl<'a, W, E, Dir, G> AsFrozenSubgraph<W, E> for MultiRootSubgraph<'a, W, E, Dir, G>
213where
214    E: Edge<W>,
215    Dir: EdgeDir,
216    G: Graph<W, E, Dir> + Edges<W, E> + Neighbors,
217{
218}
219
220/// `MultiRootSubgraph` uses `Subgraph` internally so for more info checkout [`Subgraph`](crate::graph::subgraph::Subgraph).
221impl<'a, W, E, Dir, G> AsSubgraph<W, E> for MultiRootSubgraph<'a, W, E, Dir, G>
222where
223    E: Edge<W>,
224    Dir: EdgeDir,
225    G: Graph<W, E, Dir> + Edges<W, E> + Neighbors + Vertices,
226{
227    fn remove_edge(&mut self, src_id: usize, dst_id: usize, edge_id: usize) -> Result<()> {
228        self.subgraph.remove_edge(src_id, dst_id, edge_id)
229    }
230
231    fn remove_edge_unchecked(&mut self, src_id: usize, dst_id: usize, edge_id: usize) {
232        self.subgraph.remove_edge_unchecked(src_id, dst_id, edge_id)
233    }
234
235    fn remove_vertex(&mut self, vertex_id: usize) -> Result<()> {
236        self.subgraph.remove_vertex(vertex_id)?;
237
238        self.roots.retain(|v_id| *v_id != vertex_id);
239
240        Ok(())
241    }
242
243    fn remove_vertex_unchecked(&mut self, vertex_id: usize) {
244        self.subgraph.remove_vertex_unchecked(vertex_id);
245
246        self.roots.retain(|v_id| *v_id != vertex_id);
247    }
248
249    fn add_vertex_from_graph(&mut self, vertex_id: usize) -> Result<()> {
250        self.subgraph.add_vertex_from_graph(vertex_id)
251    }
252
253    fn add_vertex_from_graph_unchecked(&mut self, vertex_id: usize) {
254        self.subgraph.add_vertex_from_graph_unchecked(vertex_id)
255    }
256
257    fn add_edge_from_graph(&mut self, src_id: usize, dst_id: usize, edge_id: usize) -> Result<()> {
258        self.subgraph.add_edge_from_graph(src_id, dst_id, edge_id)
259    }
260
261    fn add_edge_from_graph_unchecked(&mut self, src_id: usize, dst_id: usize, edge_id: usize) {
262        self.subgraph
263            .add_edge_from_graph_unchecked(src_id, dst_id, edge_id)
264    }
265}
prepona/graph/subgraph/mr_subgraph.rs

prepona/graph/subgraph/
mr_subgraph.rs
