1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331
use{
std::fmt,
crate::{
IterWrapper,
sw::SwChangeState,
traits::SerdeStateConform,
GenericGraph
},
rand::Rng
};
#[cfg(feature = "serde_support")]
use serde::{Serialize, Deserialize};
/// What every node should be able to do
pub trait Node
where Self: Clone + SerdeStateConform {
/// how to construct a blank object
fn new_from_index(index: usize) -> Self;
}
/// Error messages
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "serde_support", derive(Serialize, Deserialize))]
pub enum GraphErrors{
/// ### somehow, the existing of the edge is a problem
/// Did you try to add an edge, which is already present?
EdgeExists,
/// ### ERROR 404: Edge not found ;)
/// Did you try to delete a non existing edge?
EdgeDoesNotExist,
}
impl GraphErrors {
/// get error message as `&str`, for printing etc.
pub fn to_str(&self) -> &'static str {
match self {
GraphErrors::EdgeExists => "EdgeExists",
GraphErrors::EdgeDoesNotExist => "EdgeDoesNotExist",
}
}
pub(crate) fn convert_to_sw_state(self) -> SwChangeState {
SwChangeState::GError(self)
}
}
impl fmt::Display for GraphErrors {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{}", self.to_str())
}
}
/// Defines methods all adjecency containers should have
/// such that `GenericGraph` can use it
pub trait AdjContainer<T>
{
/// Create new instance with id
fn new(id: usize, node: T) -> Self;
/// return reference to what the AdjContainer contains
fn contained(&self) -> & T;
/// return mut reference to what the AdjContainer contains
fn contained_mut(&mut self) -> &mut T;
/// returns iterator over indices of neighbors
fn neighbors(&self) -> IterWrapper;
/// count number of neighbors, i.e. number of edges incident to `self`
fn degree(&self) -> usize;
/// returns id of container
fn id(&self) -> usize;
/// returns `Some(first element from the adjecency List)` or `None`
fn get_adj_first(&self) -> Option<&usize>;
/// check if vertex with `other_id` is adjacent to self
/// ## Note:
/// (in `Graph<T>`: `id` equals the index corresponding to `self`)
fn is_adjacent(&self, other_id: usize) -> bool;
/// Sorting adjacency lists
fn sort_adj(&mut self);
/// shuffle adjacency list
fn shuffle_adj<R: Rng>(&mut self, rng: &mut R);
/// Remove all edges
/// # Important
/// * will not clear edges of other AdjContainer
/// * only call this if you know exactly what you are doing
#[doc(hidden)]
unsafe fn clear_edges(&mut self);
/// # What does it do?
/// Creates edge in `self` and `other`s adjecency Lists
/// # Why is it unsafe?
/// * No logic to see, if AdjContainer are part of the same graph
/// * Only intended for internal usage
/// ## What should I do?
/// * use members of `net_ensembles::GenericGraph` instead, that handles the logic
#[doc(hidden)]
unsafe fn push(&mut self, other: &mut Self)
-> Result<(), GraphErrors>;
/// # What does it do?
/// Removes edge in `self` and `other`s adjecency Lists
/// # Why is it unsafe?
/// * No logic to see, if AdjContainer are part of the same graph
/// * Only intended for internal usage
/// ## What should I do?
/// * use members of `net_ensembles::GenericGraph` instead, that handles the logic
#[doc(hidden)]
unsafe fn remove(&mut self, other: &mut Self)
-> Result<(), GraphErrors>;
}
/// Get the adjacency list of a AdjContainer
pub trait AdjList<Edge>
{
/// Intended for all [AdjContainer], which store all their
/// edges in a continouse slice/vector. This will return
/// a reference to the edge slice, which you can use
/// to iterate or do other stuff
fn edges(&self) -> &[Edge];
}
/// Trait for types that have an underlying graph with nodes which each contain some `T`.
/// Used to access said `T`
pub trait Contained<T>
{
/// Returns a reference to the element stored in the specified node or `None` if out of Bounds
fn get_contained(&self, index: usize) -> Option<&T>;
/// Returns a mutable reference to the element stored in the specified node or `None` if out of Bounds
fn get_contained_mut(&mut self, index: usize) -> Option<&mut T>;
// Returns a reference to the element stored in the specified node
///
/// For a save alternative see [get_contained](`Self::get_contained`)
/// # Safety
/// Calling this method with an out-of-bounds index is [undefined behavior](https://doc.rust-lang.org/reference/behavior-considered-undefined.html) even if the resulting reference is not used.
unsafe fn get_contained_unchecked(&self, index: usize) -> &T;
/// Returns a mutable reference to the element stored in the specified node
///
/// For a save alternative see [get_contained_mut](`Self::get_contained_mut`)
/// # Safety
/// Calling this method with an out-of-bounds index is [undefined behavior](https://doc.rust-lang.org/reference/behavior-considered-undefined.html) even if the resulting reference is not used.
unsafe fn get_contained_unchecked_mut(&mut self, index: usize) -> &mut T;
}
/// Trait for measuring topological properties of a Graph
pub trait MeasurableGraphQuantities<G>
{
/// calculates the average degree of the graph
/// * `(2 * edge_count) / vertex_count`
fn average_degree(&self) -> f32;
/// * returns number of vertices adjacent to vertex `index`
/// * `None` if index out of bounds
fn degree(&self, index: usize) -> Option<usize>;
/// # compute sizes of all *connected components*
///
/// * the **number** of connected components is the **size** of the returned vector, i.e. `result.len()`
/// * returns **empty** vector, if graph does not contain vertices
/// * returns (reverse) **ordered vector of sizes** of the connected components,
/// i.e. the biggest component is of size `result[0]` and the smallest is of size `result[result.len() - 1]`
fn connected_components(&self) -> Vec<usize>;
/// * returns `None` **if** graph not connected **or** does not contain any vertices
/// * uses repeated breadth first search
fn diameter(&self) -> Option<usize>;
/// returns total number of edges in graph
fn edge_count(&self) -> usize;
/// | result | condition |
/// |--------------|----------------------------------------------------------|
/// | `None` | **if** graph does not contain any vertices |
/// | `Some(true)` | **else if** all vertices are connected by paths of edges |
/// | `Some(false)`| **otherwise** |
fn is_connected(&self) -> Option<bool>;
/// Count number of leaves in the graph, i.e. vertices with exactly one neighbor
fn leaf_count(&self) -> usize;
/// calculate the size of the longest shortest path **starting from** vertex with **index** `index`
/// using breadth first search
fn longest_shortest_path_from_index(&self, index: usize) -> Option<usize>;
/// # definition
/// Calculates the size of the **q-core** (i.e. number of nodes in the biggest possible set of nodes,
/// where all nodes from the set are connected with at least `q` other nodes from the set)
///
/// returns `None` if impossible to calculate (e.g. `vertex_count == 0` or `q <= 1`)
fn q_core(&self, q: usize) -> Option<usize>;
/// # Calculates transitivity of graph
/// * related to cluster coefficient (Note: transitivity and cluster coefficient are similar,
/// but **not** necessarily equal)
/// * returns `NaN`, if there are no paths of length two in the graph
/// ## Definition
/// > transitivity = (number of closed paths of length two) / (number of paths of length two)
/// ## Citations
/// For the definition see for example:
/// > M. E. J. Newman, "Networks: an Introduction" *Oxfort University Press*, 2010, ISBN: 978-0-19-920665-0.
fn transitivity(&self) -> f64;
/// # calculate sizes of all binode connected components
/// * returns (reverse) **ordered vector of sizes**
/// i.e. the biggest component is of size `result[0]` and the smallest is of size `result[result.len() - 1]`
/// * destroys the underlying topology and therefore moves `self`
/// * if you still need your graph,
/// use `self.clone().vertex_biconnected_components(false/true)` for your calculations
/// # Definition: `vertex_biconnected_components(false)`
/// Here, the (vertex) biconnected component of a graph is defined as maximal subset of nodes,
/// where any one node could be removed and the remaining nodes would still be a connected component.
/// ## Note
/// Two vertices connected by an edge are considered to be biconnected, since after the
/// removal of one vertex (and the corresponding edge), only one vertex remains.
/// This vertex is in a connected component with itself.
/// # Alternative Definition: `vertex_biconnected_components(true)`
/// If you want to use the alternative definition:
/// > The biconnected component is defined as maximal subset of vertices, where each vertex can be
/// > reached by at least two node independent paths
///
/// The alternative definition just removes all 2s from the result vector.
/// # Citations
/// I used the algorithm described in this paper:
/// > J. Hobcroft and R. Tarjan, "Algorithm 447: Efficient Algorithms for Graph Manipulation"
/// > *Commun. ACM*, **16**:372-378, 1973, DOI: [10.1145/362248.362272](https://doi.org/10.1145/362248.362272)
///
/// You can also take a look at:
/// > M. E. J. Newman, "Networks: an Introduction" *Oxfort University Press*, 2010, ISBN: 978-0-19-920665-0.
fn vertex_biconnected_components(&self, alternative_definition: bool) -> Vec<usize>;
/// returns number of vertices present in graph
fn vertex_count(&self) -> usize;
/// # Closely related (most of the time equal) to betweeness
/// ## calculates vertex_load of all vertices in O(edges * vertices)
/// * calculates the vertex_load for every vertex
/// * defined as how many shortest paths pass through each vertex
///
/// | variant | |
/// |---------------------|------------------------------------------------------------------------------------------------------------------------|
/// | `vertex_load(true)` | includes endpoints in calculation (for a complete graph with `N` vertices, every node will have vertex_load `N - 1`) |
/// | `vertex_load(false)` | excludes endpoints in calculation (for a complete graph with `N` vertices, every node will have vertex_load `0`) |
/// # Citations
/// I used the algorithm described in
/// > M. E. J. Newman, "Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality",
/// > Phys. Rev. E **64**, 016132, 2001, DOI: [10.1103/PhysRevE.64.016132](https://doi.org/10.1103/PhysRevE.64.016132)
///
/// see also:
/// > M. E. J. Newman, "Erratum: Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality",
/// > Phys. Rev. E **73**, 039906, 2006, DOI: [10.1103/PhysRevE.73.039906](https://doi.org/10.1103/PhysRevE.73.039906)
fn vertex_load(&self, include_endpoints: bool) -> Vec<f64>;
}
impl<T, A, E> MeasurableGraphQuantities<GenericGraph<T, A>> for E
where
T: Node,
A: AdjContainer<T>,
GenericGraph<T, A>: Clone,
E: AsRef<GenericGraph<T, A>>,
{
fn average_degree(&self) -> f32 {
self.as_ref().average_degree()
}
fn degree(&self, index: usize) -> Option<usize> {
self.as_ref().degree(index)
}
fn connected_components(&self) -> Vec<usize> {
self.as_ref().connected_components()
}
fn diameter(&self) -> Option<usize> {
self.as_ref().diameter()
}
fn edge_count(&self) -> usize {
self.as_ref().edge_count()
}
fn is_connected(&self) -> Option<bool> {
self.as_ref().is_connected()
}
fn leaf_count(&self) -> usize {
self.as_ref().leaf_count()
}
fn longest_shortest_path_from_index(&self, index: usize) -> Option<usize> {
self.as_ref().longest_shortest_path_from_index(index)
}
fn q_core(&self, q: usize) -> Option<usize>{
self.as_ref().q_core(q)
}
fn transitivity(&self) -> f64 {
self.as_ref().transitivity()
}
fn vertex_biconnected_components(&self, alternative_definition: bool) -> Vec<usize> {
let clone = (*self.as_ref()).clone();
clone.vertex_biconnected_components(alternative_definition)
}
fn vertex_count(&self) -> usize {
self.as_ref().vertex_count()
}
fn vertex_load(&self, include_endpoints: bool) -> Vec<f64> {
self.as_ref().vertex_load(include_endpoints)
}
}