Struct outils::graph::dynconn::hdt::DynamicGraph [−][src]
pub struct DynamicGraph<W = EmptyWeight> where
W: WeightType, { /* fields omitted */ }
DynamicGraph<W>
is general graph data structure providing deterministic fully-dynamic
connectivity for a graph with a fixed set of vertices.
That is, operations are provided to answer queries as to whether two vertices are connected in a graph through a path of edges. In this context, fully dynamic means that the graph can be updated by insertions or deletions of edges through the provided operations between queries (see also Dynamic Connectivity).
The data structure also supports vertex weights of type W
, dynamically maintaining the
total weight of connected components after insertion or deletion of edges.
The principal operations for a graph G = (V, E)
with |V| = n
have a poly-logarithmic
run-time cost:
insert_edge
: O(log^2 (n))delete_edge
: O(log^2 (n))is_connected
: O(log(n))
The space requirement of the data structure is O(log(n) * n).
This is achieved by maintaining the spanning forest of the graph under insertions and deletions of edges. The complexity in maintaining a spanning forest lies in the fact that the deletion of an edge might split a tree in the spanning forest into two trees but not disconnect the connected component. In this situation, the algorithm must try to reconnect the trees by finding a replacement edge - the component is only accepted to have been disconnected by the edge deletion if no replacement edge has been found.
In order to efficiently search for replacement edges, this data structure utilises the level structure, trading-off time for memory. The implemented version is outlined by Holm, de Lichtenberg and Thorup in Poly-Logarithmic Deterministic Fully-Dynamic Algorithms.
Note: The above-mentioned trade-off of time against memory does not affect the storage of vertex weights. Vertex and component weights are not managed within the level structure, and therefore have a constant additional space requirement of O(n).
The usage of DynamicGraph<W>
is straight-forward:
use outils::prelude::*; // Construct a unweighted dynamic graph with a fixed number of 10 vertices with an expected // degree (i.e. number of adjacent edges) of 3. let mut graph: DynamicGraph<EmptyWeight> = DynamicGraph::new(10, 3); let a = VertexIndex(0); let b = VertexIndex(1); let c = VertexIndex(2); let d = VertexIndex(3); // Create a cycle from a to d. let ab = graph.insert_edge(a, b).expect("No reason to fail here"); let bc = graph.insert_edge(b, c).expect("No reason to fail here"); let cd = graph.insert_edge(c, d).expect("No reason to fail here"); let da = graph.insert_edge(d, a).expect("No reason to fail here"); // a and c should be connected: assert!(graph.is_connected(a, c)); graph.delete_edge(bc); // a and c should still be connected: assert!(graph.is_connected(a, c)); graph.delete_edge(da); // NOW a and c should not be connected anymore: assert!(!graph.is_connected(a, c));
Methods
impl<W> DynamicGraph<W> where
W: WeightType,
[src]
impl<W> DynamicGraph<W> where
W: WeightType,
pub fn new(size: usize, adjacency_hint: usize) -> Self
[src]
pub fn new(size: usize, adjacency_hint: usize) -> Self
Construct a DynamicGraph
with a fixed number of vertices, i.e. size
and with an expected
degree (i.e. number of adjacent edges) of adjacency_hint
.
For a given value of size
, the DynamicGraph
will accept the vertex indices from
VertexIndex(0)
to VertexIndex(size-1)
. Values outside this range will be ignored by
the methods taking a VertexIndex
. Those methods, however, will not panic
in this case
but rather return None
.
Capacity to store edges incident to each vertex will be reserved according to the specified
value of adjacency_hint
. Re-allocation will occur if this capacity is exceeded.
pub fn max_level(&self) -> usize
[src]
pub fn max_level(&self) -> usize
Returns the number of levels in the level structure of the HDT algorithm, that is
for a graph G = (V, E)
with |V| = n
, the number of levels will be
floor(log(n))
.
pub fn size(&self) -> usize
[src]
pub fn size(&self) -> usize
Returns the number of vertices of this graph, that is for a graph G = (V, E)
this method will return |V| = n
.
pub fn adjacency_hint(&self) -> usize
[src]
pub fn adjacency_hint(&self) -> usize
Returns the initial capacity to store edges incident to each vertex
(see also: new
).
Trait Implementations
impl<W: Clone> Clone for DynamicGraph<W> where
W: WeightType,
[src]
impl<W: Clone> Clone for DynamicGraph<W> where
W: WeightType,
fn clone(&self) -> DynamicGraph<W>
[src]
fn clone(&self) -> DynamicGraph<W>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
impl<W: Debug> Debug for DynamicGraph<W> where
W: WeightType,
[src]
impl<W: Debug> Debug for DynamicGraph<W> where
W: WeightType,
fn fmt(&self, f: &mut Formatter) -> Result
[src]
fn fmt(&self, f: &mut Formatter) -> Result
Formats the value using the given formatter. Read more
impl<W> DynamicConnectivity<W> for DynamicGraph<W> where
W: WeightType,
[src]
impl<W> DynamicConnectivity<W> for DynamicGraph<W> where
W: WeightType,
fn insert_edge(&mut self, v: VertexIndex, w: VertexIndex) -> Option<Edge>
[src]
fn insert_edge(&mut self, v: VertexIndex, w: VertexIndex) -> Option<Edge>
Connects the vertices indexed by v
and w
and returns the index of the created edge.
If the vertices cannot be connected None
is returned. Vertices cannot be connected if
v
and w
are equal or if either of them denotes an index greater or equal the
size
of the DynamicGraph
.
use outils::prelude::*; // Construct a unweighted dynamic graph with a fixed number of 10 vertices with an expected // degree (i.e. number of adjacent edges) of 3. let mut graph: DynamicGraph<EmptyWeight> = DynamicGraph::new(10, 3); let a = VertexIndex(0); let b = VertexIndex(1); let c = VertexIndex(999); // Invalid vertex index! // Connect a and b: let ab = graph.insert_edge(a, b); assert!(ab.is_some()); assert!(graph.is_connected(a, b)); // Attempt to connect a and c, which is a vertex index greater than the size of the graph: let ac = graph.insert_edge(a, c); assert!(ac.is_none()); assert!(!graph.is_connected(a, c));
fn delete_edge(&mut self, e: Edge)
[src]
fn delete_edge(&mut self, e: Edge)
Deletes the edge e
from the graph if it exists.
Note: Usually, e
should be an instance of an Edge
that has been previously returned
by insert_edge
and has not yet been deleted. This method will
ignore any Edge
passed to it that is not equal to an instance stored internally.
fn is_connected(&self, v: VertexIndex, w: VertexIndex) -> bool
[src]
fn is_connected(&self, v: VertexIndex, w: VertexIndex) -> bool
Returns true
if the two vertices indexed by v
and w
are connected in self
through
a path of edges.
impl<'dyn, W> DynamicComponent<'dyn> for DynamicGraph<W> where
W: WeightType,
[src]
impl<'dyn, W> DynamicComponent<'dyn> for DynamicGraph<W> where
W: WeightType,
fn component_vertices(
&'dyn self,
v: VertexIndex
) -> Box<Iterator<Item = VertexIndex> + 'dyn>
[src]
fn component_vertices(
&'dyn self,
v: VertexIndex
) -> Box<Iterator<Item = VertexIndex> + 'dyn>
Returns a boxed iterator over the indices of the vertices which are connected to the
vertex indexed by v
.
use outils::prelude::*; // Construct a unweighted dynamic graph with a fixed number of 10 vertices with an expected // degree (i.e. number of adjacent edges) of 3. let mut graph: DynamicGraph<EmptyWeight> = DynamicGraph::new(10, 3); let a = VertexIndex(0); let b = VertexIndex(1); let c = VertexIndex(2); let d = VertexIndex(3); // Connect a and b and c: let ab = graph.insert_edge(a, b); let ac = graph.insert_edge(a, c); let vertices: Vec<VertexIndex> = graph.component_vertices(b).collect(); assert!(vertices.contains(&a)); assert!(vertices.contains(&b)); assert!(vertices.contains(&c)); assert!(!vertices.contains(&d)); // d is not part of the component b belongs to!
fn components(&'dyn self) -> Box<Iterator<Item = VertexIndex> + 'dyn>
[src]
fn components(&'dyn self) -> Box<Iterator<Item = VertexIndex> + 'dyn>
Returns a boxed iterator over vertices that are representatives of connected components. This implies that no vertices returned by this iterator are connected to each other.
use outils::prelude::*; // Construct a unweighted dynamic graph with a fixed number of 7 vertices with an expected // degree (i.e. number of adjacent edges) of 3. let mut graph: DynamicGraph<EmptyWeight> = DynamicGraph::new(7, 3); let a = VertexIndex(0); let b = VertexIndex(1); let c = VertexIndex(2); let d = VertexIndex(3); let e = VertexIndex(4); let f = VertexIndex(5); let g = VertexIndex(6); //Create four components: {a, b}, {c, d}, {e, f} and {g} graph.insert_edge(a, b); graph.insert_edge(c, d); graph.insert_edge(e, f); // Expect exactly one vertex of each component to be included by the components iterator: let vertices: Vec<VertexIndex> = graph.components().collect(); assert!(vertices.contains(&a) || vertices.contains(&b)); assert!(vertices.contains(&c) || vertices.contains(&d)); assert!(vertices.contains(&e) || vertices.contains(&f)); assert!(vertices.contains(&g));
fn component_edges(
&'dyn self,
v: VertexIndex
) -> Box<Iterator<Item = Edge> + 'dyn>
[src]
fn component_edges(
&'dyn self,
v: VertexIndex
) -> Box<Iterator<Item = Edge> + 'dyn>
Returns a boxed iterator over the indices of the edges which connect the component the
vertex indexed by v
is part of.
use outils::prelude::*; // Construct a unweighted dynamic graph with a fixed number of 10 vertices with an expected // degree (i.e. number of adjacent edges) of 3. let mut graph: DynamicGraph<EmptyWeight> = DynamicGraph::new(10, 3); let a = VertexIndex(0); let b = VertexIndex(1); let c = VertexIndex(2); let d = VertexIndex(3); let e = VertexIndex(4); let f = VertexIndex(5); let g = VertexIndex(6); //Create component: {a, b, c, d} let ab = graph.insert_edge(a, b).expect("No reason to fail here"); let bc = graph.insert_edge(b, c).expect("No reason to fail here"); let bd = graph.insert_edge(b, d).expect("No reason to fail here"); let da = graph.insert_edge(a, b).expect("No reason to fail here"); // Non-spanning edge! //Create component: {e, f, g} let ef = graph.insert_edge(e, f).expect("No reason to fail here"); let gf = graph.insert_edge(g, f).expect("No reason to fail here"); let eg = graph.insert_edge(e, g).expect("No reason to fail here"); // Non-spanning edge! let abcd_edges: Vec<Edge> = graph.component_edges(a).collect(); assert!(abcd_edges.contains(&ab)); assert!(abcd_edges.contains(&bc)); assert!(abcd_edges.contains(&bd)); assert!(abcd_edges.contains(&da)); let efg_edges: Vec<Edge> = graph.component_edges(e).collect(); assert!(efg_edges.contains(&ef)); assert!(efg_edges.contains(&gf)); assert!(efg_edges.contains(&eg));
fn disconnect_component(&mut self, v: VertexIndex) -> Vec<Edge>
[src]
fn disconnect_component(&mut self, v: VertexIndex) -> Vec<Edge>
Deletes all edges from this graph which connect the component the
vertex indexed by v
is part of.
Generally, this operation will be significantly faster than calling delete_edge
on each
edge of the component separately, the reason being that it is not necessary to attempt to
to reconnect the component with replacement edges when it is known beforehand that every
edge of the component is going to be deleted.
use outils::prelude::*; // Construct a unweighted dynamic graph with a fixed number of 10 vertices with an expected // degree (i.e. number of adjacent edges) of 3. let mut graph: DynamicGraph<EmptyWeight> = DynamicGraph::new(10, 3); let a = VertexIndex(0); let b = VertexIndex(1); let c = VertexIndex(2); let d = VertexIndex(3); //Create component: {a, b, c, d} let ab = graph.insert_edge(a, b).expect("No reason to fail here"); let bc = graph.insert_edge(b, c).expect("No reason to fail here"); let bd = graph.insert_edge(b, d).expect("No reason to fail here"); let da = graph.insert_edge(a, b).expect("No reason to fail here"); // Non-spanning edge! let abcd_edges: Vec<Edge> = graph.disconnect_component(a); assert!(abcd_edges.contains(&ab)); assert!(abcd_edges.contains(&bc)); assert!(abcd_edges.contains(&bd)); assert!(abcd_edges.contains(&da)); assert!(!graph.is_connected(a, b)); assert!(!graph.is_connected(a, c)); assert!(!graph.is_connected(a, d)); assert!(!graph.is_connected(b, c)); assert!(!graph.is_connected(b, d)); assert!(!graph.is_connected(c, d));
impl<W> DynamicWeightedComponent<W> for DynamicGraph<W> where
W: WeightType,
[src]
impl<W> DynamicWeightedComponent<W> for DynamicGraph<W> where
W: WeightType,
fn set_vertex_weight(&mut self, v: VertexIndex, weight: W) -> Option<W>
[src]
fn set_vertex_weight(&mut self, v: VertexIndex, weight: W) -> Option<W>
Set the weight of the vertex indexed by v
to weight
and update the weight of the
component this vertex belongs to. If v
was a valid index, the old weight is returned.
use outils::prelude::*; // Construct a dynamic graph with weights of type usize and a fixed number of 10 vertices // with an expected degree (i.e. number of adjacent edges) of 3. let mut graph: DynamicGraph<usize> = DynamicGraph::new(10, 3); let a = VertexIndex(0); assert_eq!(graph.set_vertex_weight(a, 2), Some(0));
fn vertex_weight(&self, v: VertexIndex) -> Option<&W>
[src]
fn vertex_weight(&self, v: VertexIndex) -> Option<&W>
Immutably access the weight of the vertex indexed by v
.
fn component_weight(&self, v: VertexIndex) -> Option<&W>
[src]
fn component_weight(&self, v: VertexIndex) -> Option<&W>
Immutably access the weight of the component to which the vertex indexed by v
belongs.
use outils::prelude::*; // Construct a dynamic graph with weights of type usize and a fixed number of 10 vertices // with an expected degree (i.e. number of adjacent edges) of 3. let mut graph: DynamicGraph<usize> = DynamicGraph::new(10, 3); let a = VertexIndex(0); let b = VertexIndex(1); let c = VertexIndex(2); let d = VertexIndex(3); graph.set_vertex_weight(a, 1); graph.set_vertex_weight(b, 1); graph.set_vertex_weight(c, 1); graph.set_vertex_weight(d, 1); // Create component {a, b, c, d} - since all vertices have a weight of 1, the resulting // component should have a weight of 4. let ab = graph.insert_edge(a, b).expect("No reason to fail here"); let bc = graph.insert_edge(b, c).expect("No reason to fail here"); let bd = graph.insert_edge(b, d).expect("No reason to fail here"); let da = graph.insert_edge(a, b).expect("No reason to fail here"); // Non-spanning edge! assert_eq!(graph.component_weight(a), Some(&4));
fn adjust_vertex_weight(&mut self, v: VertexIndex, f: &Fn(&mut W)) -> Option<&W>
[src]
fn adjust_vertex_weight(&mut self, v: VertexIndex, f: &Fn(&mut W)) -> Option<&W>
Change the weight of the vertex indexed by v
by applying the closure f
. After applying
the closure, the weight of the component this vertex belongs to will be updated accordingly.
If v
was a valid index a reference to the changed weight is returned.
use outils::prelude::*; // Construct a dynamic graph with weights of type usize and a fixed number of 10 vertices // with an expected degree (i.e. number of adjacent edges) of 3. let mut graph: DynamicGraph<usize> = DynamicGraph::new(10, 3); let a = VertexIndex(0); assert_eq!(graph.adjust_vertex_weight(a, &|w: &mut usize| *w += 2), Some(&2));
impl<'slf, W> Edges<'slf> for DynamicGraph<W> where
W: WeightType,
[src]
impl<'slf, W> Edges<'slf> for DynamicGraph<W> where
W: WeightType,
Auto Trait Implementations
impl<W> Send for DynamicGraph<W> where
W: Send,
impl<W> Send for DynamicGraph<W> where
W: Send,
impl<W> Sync for DynamicGraph<W> where
W: Sync,
impl<W> Sync for DynamicGraph<W> where
W: Sync,