prepona/graph/subgraph/
mod.rs

1mod def_mut_subgraph;
2mod def_subgraph;
3mod mr_subgraph;
4mod sp_subgraph;
5
6use crate::graph::Edge;
7use crate::provide::{Edges, Neighbors, Vertices};
8
9use anyhow::Result;
10pub use def_mut_subgraph::MutSubgraph;
11pub use def_subgraph::Subgraph;
12pub use mr_subgraph::MultiRootSubgraph;
13pub use sp_subgraph::ShortestPathSubgraph;
14
15/// Describes a subgraph that can not get mutated(Not itself nor the graph it's representing).
16///
17/// ## Generic Parameters
18/// * `W`: **W**eight type associated with edges.
19/// * `E`: **E**dge type that subgraph uses.
20pub trait AsFrozenSubgraph<W, E: Edge<W>>: Neighbors + Vertices + Edges<W, E> {}
21
22/// Describes a subgraph that can mutate but the graph that it represents, can not mutate.
23///
24/// Obviously you can remove vertices and edges from the subgraph but it does not remove them from the graph.
25/// You can also add already existing vertices and edges from graph to subgraph.
26///
27/// ## Note
28/// Functions defined in this trait are abstractions of what is expected from a subgraph.
29/// For concrete information about why/when these functions may panic or return `Err`, refer to the specific subgraph struct that you are using.
30///
31/// ## Generic Parameters
32/// * `W`: **W**eight type associated with edges.
33/// * `E`: **E**dge type that subgraph uses.
34pub trait AsSubgraph<W, E: Edge<W>>: AsFrozenSubgraph<W, E> {
35    /// Removes the edge with id: `edge_id`.
36    ///
37    /// # Arguments
38    /// * `src_id`: Id of source vertex.
39    /// * `dst_id`: Id of destination vertex.
40    /// * `edge_id`: Id of edge to be removed.
41    ///
42    /// # Returns
43    /// * `Err`
44    /// * `Ok`: If removal was successful.
45    fn remove_edge(&mut self, src_id: usize, dst_id: usize, edge_id: usize) -> Result<()>;
46
47    /// Removes the edge with id: `edge_id`.
48    ///
49    /// # Arguments
50    /// * `src_id`: Id of source vertex.
51    /// * `dst_id`: Id of destination vertex.
52    /// * `edge_id`: Id of edge to be removed.
53    fn remove_edge_unchecked(&mut self, src_id: usize, dst_id: usize, edge_id: usize);
54
55    /// Removes the vertex with id: `vertex_id` from subgraph.
56    ///
57    /// # Arguments
58    /// `vertex_id`: Id of the vertex to be removed.
59    ///
60    /// # Returns
61    /// * `Err`
62    /// * `Ok`: If removal was successful.
63    fn remove_vertex(&mut self, vertex_id: usize) -> Result<()>;
64
65    /// Removes the vertex with id: `vertex_id` from subgraph.
66    ///
67    /// # Arguments
68    /// `vertex_id`: Id of the vertex to be removed.
69    fn remove_vertex_unchecked(&mut self, vertex_id: usize);
70
71    /// Adds a vertex that is already in the graph, to the subgraph.
72    ///
73    /// # Arguments
74    /// `vertex_id`: Id of the vertex to be added from graph to subgraph.
75    ///
76    /// # Returns
77    /// * `Err`
78    /// * `Ok`: If addition was successful.
79    fn add_vertex_from_graph(&mut self, vertex_id: usize) -> Result<()>;
80
81    /// Adds a vertex that is already in the graph, to the subgraph.
82    ///
83    /// # Arguments
84    /// `vertex_id`: Id of the vertex to be added from graph to subgraph.
85    fn add_vertex_from_graph_unchecked(&mut self, vertex_id: usize);
86
87    /// Adds an edge that is already in the graph, to the subgraph.
88    ///
89    /// # Arguments
90    /// * `src_id`: Id of the source vertex.
91    /// * `dst_id`: Id of the destination vertex.
92    /// * `edge_id`: Id of the edge from source vertex to destination vertex.
93    ///
94    /// # Returns
95    /// * `Err`
96    /// * `Ok`: If addition was successful.
97    fn add_edge_from_graph(&mut self, src_id: usize, dst_id: usize, edge_id: usize) -> Result<()>;
98
99    /// Adds an edge that is already in the graph, to the subgraph.
100    ///
101    /// # Arguments
102    /// * `src_id`: Id of the source vertex.
103    /// * `dst_id`: Id of the destination vertex.
104    /// * `edge_id`: Id of the edge from source vertex to destination vertex.
105    fn add_edge_from_graph_unchecked(&mut self, src_id: usize, dst_id: usize, edge_id: usize);
106}
107
108/// Describes a subgraph that can mutate and also can mutate the graph it's representing.
109///
110/// Adding an edge or a vertex to the subgraph that is completely new(is not already present in the graph), will be added to the graph as well.
111/// Also removing an edge or vertex from the graph that is also present in the subgraph, will get removed from the subgraph as well.
112///
113/// /// ## Note
114/// Functions defined in this trait are abstractions of what is expected from a mutable subgraph.
115/// For concrete information about why/when these functions may panic or return `Err`, refer to the specific mutable subgraph struct that you are using.
116///
117/// ## Generic Parameters
118/// * `W`: **W**eight type associated with edges.
119/// * `E`: **E**dge type that subgraph uses.
120pub trait AsMutSubgraph<W, E: Edge<W>>: AsSubgraph<W, E> {
121    /// Removes a vertex from the graph.
122    /// If the vertex is present in the subgraph, It will get removed from the subgraph as well.
123    ///
124    /// # Arguments
125    /// `vertex_id`: Id of the vertex to get removed.
126    ///
127    /// # Returns
128    /// * `Err`
129    /// * `Ok`: If removal was successful.
130    fn remove_vertex_from_graph(&mut self, vertex_id: usize) -> Result<()>;
131
132    /// Removes a vertex from the graph.
133    /// If the vertex is present in the subgraph, It will get removed from the subgraph as well.
134    ///
135    /// # Arguments
136    /// `vertex_id`: Id of the vertex to get removed.
137    fn remove_vertex_from_graph_unchecked(&mut self, vertex_id: usize);
138
139    /// Removes an edge from the graph.
140    /// If the edge is present in the subgraph, It will get removed from the subgraph as well.
141    ///
142    /// # Arguments
143    /// * `src_id`: Id of the source vertex.
144    /// * `dst_id`: Id of the destination vertex.
145    /// * `edge_id`: Id of the edge from source vertex to destination vertex.
146    ///
147    /// # Returns
148    /// * `Err`:
149    /// * `Ok`: Containing the removed edge.
150    fn remove_edge_from_graph(&mut self, src_id: usize, dst_id: usize, edge_id: usize)
151        -> Result<E>;
152
153    /// Removes an edge from the graph.
154    /// If the edge is present in the subgraph, It will get removed from the subgraph as well.
155    ///
156    /// # Arguments
157    /// * `src_id`: Id of the source vertex.
158    /// * `dst_id`: Id of the destination vertex.
159    /// * `edge_id`: Id of the edge from source vertex to destination vertex.
160    ///
161    /// # Returns
162    /// The removed edge.
163    fn remove_edge_from_graph_unchecked(
164        &mut self,
165        src_id: usize,
166        dst_id: usize,
167        edge_id: usize,
168    ) -> E;
169
170    /// Adds a new vertex to subgraph and the graph it's representing.
171    ///
172    /// # Returns
173    /// Id of the new added vertex.
174    fn add_vertex(&mut self) -> usize;
175
176    /// Adds a new edge to subgraph and the graph it's representing.
177    ///
178    /// # Arguments
179    /// * `src_id`: Id of the source vertex.
180    /// * `dst_id`: Id of the destination vertex.
181    /// * `edge`: Edge to be added to subgraph.
182    ///
183    /// # Returns
184    /// * `Err`:
185    /// * `Ok`: Containing the id of the newly added edge.
186    fn add_edge(&mut self, src_id: usize, dst_id: usize, edge: E) -> Result<usize>;
187
188    /// Adds a new edge to subgraph and the graph it's representing.
189    ///
190    /// # Arguments
191    /// * `src_id`: Id of the source vertex.
192    /// * `dst_id`: Id of the destination vertex.
193    /// * `edge`: Edge to be added to subgraph.
194    ///
195    /// # Returns
196    /// The id of the newly added edge.
197    fn add_edge_unchecked(&mut self, src_id: usize, dst_id: usize, edge: E) -> usize;
198}
prepona/graph/subgraph/mod.rs

prepona/graph/subgraph/
mod.rs
