# Trait net_ensembles::traits::MeasurableGraphQuantities [−][src]

```
pub trait MeasurableGraphQuantities<G> {
```## Show 13 methods

fn average_degree(&self) -> f32;
fn degree(&self, index: usize) -> Option<usize>;
fn connected_components(&self) -> Vec<usize>;
fn diameter(&self) -> Option<usize>;
fn edge_count(&self) -> usize;
fn is_connected(&self) -> Option<bool>;
fn leaf_count(&self) -> usize;
fn longest_shortest_path_from_index(&self, index: usize) -> Option<usize>;
fn q_core(&self, q: usize) -> Option<usize>;
fn transitivity(&self) -> f64;
fn vertex_biconnected_components(

&self,

alternative_definition: bool

) -> Vec<usize>;
fn vertex_count(&self) -> usize;
fn vertex_load(&self, include_endpoints: bool) -> Vec<f64>;
}

## Expand description

Trait for measuring topological properties of a Graph

## Required methods

#### fn average_degree(&self) -> f32

#### fn average_degree(&self) -> f32

calculates the average degree of the graph

`(2 * edge_count) / vertex_count`

- returns number of vertices adjacent to vertex
`index`

`None`

if index out of bounds

#### fn connected_components(&self) -> Vec<usize>

#### fn connected_components(&self) -> Vec<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]`

- returns
`None`

**if**graph not connected**or**does not contain any vertices - uses repeated breadth first search

#### fn edge_count(&self) -> usize

#### fn edge_count(&self) -> usize

returns total number of edges in graph

#### fn is_connected(&self) -> Option<bool>

#### fn is_connected(&self) -> Option<bool>

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 leaf_count(&self) -> usize

#### fn leaf_count(&self) -> usize

Count number of leaves in the graph, i.e. vertices with exactly one neighbor

#### fn longest_shortest_path_from_index(&self, index: usize) -> Option<usize>

#### fn longest_shortest_path_from_index(&self, index: usize) -> Option<usize>

calculate the size of the longest shortest path **starting from** vertex with **index** `index`

using breadth first search

##### 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 transitivity(&self) -> f64

#### fn transitivity(&self) -> f64

##### 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 vertex_biconnected_components(

&self,

alternative_definition: bool

) -> Vec<usize>

#### fn vertex_biconnected_components(

&self,

alternative_definition: bool

) -> Vec<usize>

##### 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

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_count(&self) -> usize

#### fn vertex_count(&self) -> usize

returns number of vertices present in graph

#### fn vertex_load(&self, include_endpoints: bool) -> Vec<f64>

#### fn vertex_load(&self, include_endpoints: bool) -> Vec<f64>

##### 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

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