[−][src]Struct net_ensembles::generic_graph::GenericGraph
Generic graph implementation
- contains multiple measurable quantities
Methods
impl<T: Node, A: AdjContainer<T>> GenericGraph<T, A>
[src]
pub fn new(size: u32) -> Self
[src]
Create new graph with size
nodes
and no edges
pub fn clear_edges(&mut self)
[src]
removes all edges from the graph
- inexpensive O(1), if there are no edges to begin with
- O(vertices) otherwise
pub fn sort_adj(&mut self)
[src]
Sort adjecency lists
If you depend on the order of the adjecency lists, you can sort them
Performance
- internally uses pattern-defeating quicksort as long as that is the standard
- sorts an adjecency list with length
d
in worst-case:O(d log(d))
- is called for each adjecency list, i.e.,
self.vertex_count()
times
pub fn parse_str(to_parse: &str) -> Option<(&str, Self)>
[src]
parse from str
- tries to parse
Graph
from astr
. - will ignore leading whitespaces and other chars, as long as they do not match
"next_id: "
- returns
None
if failed
Return
- returns string slice beginning directly after the part, that was used to parse
- the
Graph
resulting form the parsing
pub fn container(&self, index: usize) -> &A
[src]
get NodeContainer at index
- use this to iterate over neighbors
- use this to check, if vertices are adjacent
Warning
- panics if index out of bounds
pub fn container_iter(&self) -> Iter<A>
[src]
get iterator over NodeContainer in order of the indices
pub fn at(&self, index: usize) -> &T
[src]
For your calculations etc.
- read access to your struct T, stored at each vertex, that implements
Node
trait - see first code example (beginning of this page)
pub fn at_mut(&mut self, index: usize) -> &mut T
[src]
For your calculations etc.
- write access to your struct T, stored at each vertex, that implements
Node
trait - see first code example (beginning of this page)
pub fn vertex_count(&self) -> u32
[src]
returns number of vertices present in graph
pub fn average_degree(&self) -> f32
[src]
calculates the average degree of the graph
(2 * edge_count) / vertex_count
pub fn add_edge(&mut self, index1: u32, index2: u32) -> Result<(), GraphErrors>
[src]
Adds edge between nodes index1
and index2
ErrorCases:
Error | Reason |
---|---|
GraphErrors::IndexOutOfRange | index1 or index2 larger than self.vertex_count() |
GraphErrors::EdgeExists | requested edge already exists! |
panics
- if indices out of bounds
- in debug: If
index0 == index1
pub fn remove_edge(
&mut self,
index1: u32,
index2: u32
) -> Result<(), GraphErrors>
[src]
&mut self,
index1: u32,
index2: u32
) -> Result<(), GraphErrors>
Removes edge between nodes index1 and index2
ErrorCases:
Error | Reason |
---|---|
GraphErrors::IndexOutOfRange | index1 or index2 larger than self.vertex_count() |
GraphErrors::EdgeDoesNotExist | requested edge does not exists |
panics
- if index out of bounds
- in debug: If
index0 == index1
pub fn edge_count(&self) -> u32
[src]
returns total number of edges in graph
pub fn degree(&self, index: usize) -> Option<usize>
[src]
returns number of vertices adjacent to vertex index
pub fn dfs(&self, index: u32) -> Dfs<T, A>
[src]
returns Iterator
- the iterator will iterate over the vertices in depth first search order,
beginning with vertex
index
. - iterator returns
node
Order
Order is guaranteed to be in DFS order, however if this order is not unambigouse adding edges and especially removing edges will shuffle the order.
Note:
Will only iterate over vertices within the connected component that contains vertex index
pub fn dfs_with_index(&self, index: u32) -> DfsWithIndex<T, A>
[src]
returns Iterator
- the iterator will iterate over the vertices in depth first search order,
beginning with vertex
index
. - Iterator returns tuple
(index, node)
Order
Order is guaranteed to be in DFS order, however if this order is not unambigouse adding edges and especially removing edges will shuffle the order.
Note:
Will only iterate over vertices within the connected component that contains vertex index
pub fn bfs_index_depth(&self, index: u32) -> Bfs<T, A>
[src]
returns Iterator
- the iterator will iterate over the vertices in breadth first search order,
beginning with vertex
index
. - Iterator returns tuple
(index, node, depth)
depth
- starts at 0 (i.e. the first element in the iterator will have
depth = 0
) depth
equals number of edges in the shortest path from the current vertex to the first vertex (i.e. to the vertex with indexindex
)
Order
Order is guaranteed to be in BFS order, however if this order is not unambigouse adding edges and especially removing edges will shuffle the order.
Note:
Will only iterate over vertices within the connected component that contains vertex index
pub fn is_connected(&self) -> Option<bool>
[src]
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 |
pub fn q_core(&self, q: u32) -> Option<u32>
[src]
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
)
Example
use net_ensembles::EmptyNode; use net_ensembles::Graph; let graph: Graph<EmptyNode> = Graph::new(0); assert_eq!(graph.q_core(1), None); assert_eq!(graph.q_core(2), None); let graph2: Graph<EmptyNode> = Graph::new(1); assert_eq!(graph2.q_core(1), None); assert_eq!(graph2.q_core(2), Some(0)); // create complete graph let mut graph3: Graph<EmptyNode> = Graph::new(20); for i in 0..graph3.vertex_count() { for j in i+1..graph3.vertex_count() { graph3.add_edge(i, j).unwrap(); } } // since this is a complete graph, the q-core should always consist of 20 nodes // as long as q < 20, as every node has 19 neighbors for i in 2..20 { assert_eq!(graph3.q_core(i), Some(20)); } assert_eq!(graph3.q_core(20), Some(0));
pub fn connected_components(&self) -> Vec<u32>
[src]
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 sizeresult[result.len() - 1]
pub fn leaf_count(&self) -> usize
[src]
Count number of leaves in the graph, i.e. vertices with exactly one neighbor
pub fn to_dot(&self) -> String
[src]
- Creates String which contains the topology of the network in a format that can be used by circo etc. to generate a pdf of the graph.
- indices are used as labels
- search for graphviz to learn about .dot format
pub fn to_dot_with_labels_from_contained<F>(
&self,
dot_options: &str,
f: F
) -> String where
F: Fn(&T, usize) -> String,
[src]
&self,
dot_options: &str,
f: F
) -> String where
F: Fn(&T, usize) -> String,
Example
use std::fs::File; use std::io::prelude::*; use net_ensembles::{Graph, EmptyNode, dot_constants::EXAMPLE_DOT_OPTIONS}; let mut graph: Graph<EmptyNode> = Graph::new(3); graph.add_edge(0, 1).unwrap(); graph.add_edge(0, 2).unwrap(); graph.add_edge(1, 2).unwrap(); // create string of dotfile let s = graph.to_dot_with_labels_from_contained( EXAMPLE_DOT_OPTIONS, |_contained, index| format!("Hey {}!", index) ); // write to file let mut f = File::create("example.dot").expect("Unable to create file"); f.write_all(s.as_bytes()).expect("Unable to write data");
In this example, example.dot
now contains:
graph G{
bgcolor="transparent";
fontsize=50;
node [shape=ellipse, penwidth=1, fontname="Courier", pin=true ];
splines=true;
0 1 2 ;
"0" [label="Hey 0!"];
"1" [label="Hey 1!"];
"2" [label="Hey 2!"];
0 -- 1
0 -- 2
1 -- 2
}
Then you can use, e.g.,
foo@bar:~$ circo example.dot -Tpdf > example.pdf
to create a pdf representation from it. Search for graphviz to learn more.
pub fn to_dot_with_labels_from_container<F>(
&self,
dot_options: &str,
f: F
) -> String where
F: Fn(&A, usize) -> String,
[src]
&self,
dot_options: &str,
f: F
) -> String where
F: Fn(&A, usize) -> String,
Same as to_dot_with_labels_from_contained
but with access to neighbor information
Example
use std::fs::File; use std::io::prelude::*; use net_ensembles::traits::*; use net_ensembles::dot_constants::*; use net_ensembles::{Graph,EmptyNode}; let mut graph: Graph<EmptyNode> = Graph::new(5); graph.add_edge(0, 1).unwrap(); graph.add_edge(0, 2).unwrap(); graph.add_edge(1, 2).unwrap(); graph.add_edge(0, 3).unwrap(); graph.add_edge(3, 4).unwrap(); // create string of dotfile let s = graph.to_dot_with_labels_from_container( &[SPLINES, NO_OVERLAP].join("\n\t"), |container, index| { container.contained(); // does nothing in this example, but you can still access // contained, as you could in // to_dot_with_labels_from_contained format!("index {}, degree: {}", index, container.degree()) } ); // write to file let mut f = File::create("example_2.dot").expect("Unable to create file"); f.write_all(s.as_bytes()).expect("Unable to write data");
In this example, example_2.dot
now contains:
graph G{
splines=true;
overlap=false;
0 1 2 3 4 ;
"0" [label="index 0, degree: 3"];
"1" [label="index 1, degree: 2"];
"2" [label="index 2, degree: 2"];
"3" [label="index 3, degree: 2"];
"4" [label="index 4, degree: 1"];
0 -- 1
0 -- 2
0 -- 3
1 -- 2
3 -- 4
}
Then you can use, e.g.,
foo@bar:~$ circo example_2.dot -Tpdf > example_2.pdf
to create a pdf representation from it. Search for graphviz to learn more.
pub fn diameter(&self) -> Option<u32>
[src]
- returns
None
if graph not connected or does not contain any vertices - uses repeated breadth first search
pub fn longest_shortest_path_from_index(&self, index: u32) -> Option<u32>
[src]
calculate the size of the longest shortest path starting from vertex with index index
using breadth first search
pub fn vertex_biconnected_components(
self,
alternative_definition: bool
) -> Vec<usize>
[src]
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 sizeresult[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.
pub fn vertex_load(&self, include_endpoints: bool) -> Vec<f64>
[src]
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
pub fn transitivity(&self) -> f64
[src]
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.
impl<T: Node> GenericGraph<T, SwContainer<T>>
[src]
pub fn reset_edge(&mut self, index0: u32, index1: u32) -> SwChangeState
[src]
Reset small-world edge to its root state
- panics if index out of bounds
- in debug: panics if
index0 == index1
pub fn rewire_edge(
&mut self,
index0: u32,
index1: u32,
index2: u32
) -> SwChangeState
[src]
&mut self,
index0: u32,
index1: u32,
index2: u32
) -> SwChangeState
Rewire edges
- rewire edge
(index0, index1)
to(index0, index2)
panics
- if indices are out of bounds
- in debug: panics if
index0 == index2
- edge
(index0, index1)
has to be rooted atindex0
, else will panic in debug mode
Trait Implementations
impl<T: Clone + Node, A: Clone + AdjContainer<T>> Clone for GenericGraph<T, A>
[src]
fn clone(&self) -> GenericGraph<T, A>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<T: Debug + Node, A: Debug + AdjContainer<T>> Debug for GenericGraph<T, A>
[src]
impl<T: Node, A: AdjContainer<T>> Display for GenericGraph<T, A>
[src]
Auto Trait Implementations
impl<T, A> RefUnwindSafe for GenericGraph<T, A> where
A: RefUnwindSafe,
T: RefUnwindSafe,
A: RefUnwindSafe,
T: RefUnwindSafe,
impl<T, A> Send for GenericGraph<T, A> where
A: Send,
T: Send,
A: Send,
T: Send,
impl<T, A> Sync for GenericGraph<T, A> where
A: Sync,
T: Sync,
A: Sync,
T: Sync,
impl<T, A> Unpin for GenericGraph<T, A> where
A: Unpin,
T: Unpin,
A: Unpin,
T: Unpin,
impl<T, A> UnwindSafe for GenericGraph<T, A> where
A: UnwindSafe,
T: UnwindSafe,
A: UnwindSafe,
T: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T> ToString for T where
T: Display + ?Sized,
[src]
T: Display + ?Sized,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,