[−][src]Struct outils::graph::dynconn::hdt::DynamicGraph
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));
Implementations
impl<W> DynamicGraph<W> where
W: WeightType,
[src]
W: WeightType,
pub fn new(size: usize, adjacency_hint: usize) -> Self
[src]
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]
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]
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]
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]
W: WeightType,
fn clone(&self) -> DynamicGraph<W>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<W: Debug> Debug for DynamicGraph<W> where
W: WeightType,
[src]
W: WeightType,
impl<'dc, W> DynamicComponent<'dc, usize> for DynamicGraph<W> where
W: WeightType,
[src]
W: WeightType,
fn component_vertices(
&'dc self,
v: VertexIndex
) -> Box<dyn Iterator<Item = VertexIndex> + 'dc>
[src]
&'dc self,
v: VertexIndex
) -> Box<dyn Iterator<Item = VertexIndex> + 'dc>
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(&'dc self) -> Box<dyn Iterator<Item = VertexIndex> + 'dc>
[src]
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(
&'dc self,
v: VertexIndex
) -> Box<dyn Iterator<Item = Edge> + 'dc>
[src]
&'dc self,
v: VertexIndex
) -> Box<dyn Iterator<Item = Edge> + 'dc>
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]
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> DynamicConnectivity<W, usize> for DynamicGraph<W> where
W: WeightType,
[src]
W: WeightType,
fn insert_edge(&mut self, v: VertexIndex, w: VertexIndex) -> Option<Edge>
[src]
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]
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]
Returns true
if the two vertices indexed by v
and w
are connected in self
through
a path of edges.
impl<W> DynamicWeightedComponent<W, usize> for DynamicGraph<W> where
W: WeightType,
[src]
W: WeightType,
fn set_vertex_weight(&mut self, v: VertexIndex, weight: W) -> Option<W>
[src]
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]
Immutably access the weight of the vertex indexed by v
.
fn component_weight(&self, v: VertexIndex) -> Option<&W>
[src]
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: &dyn Fn(&mut W)
) -> Option<&W>
[src]
&mut self,
v: VertexIndex,
f: &dyn 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, usize> for DynamicGraph<W> where
W: WeightType,
[src]
W: WeightType,
Auto Trait Implementations
impl<W> RefUnwindSafe for DynamicGraph<W> where
W: RefUnwindSafe,
W: RefUnwindSafe,
impl<W> Send for DynamicGraph<W> where
W: Send,
W: Send,
impl<W> Sync for DynamicGraph<W> where
W: Sync,
W: Sync,
impl<W> Unpin for DynamicGraph<W> where
W: Unpin,
W: Unpin,
impl<W> UnwindSafe for DynamicGraph<W> where
W: UnwindSafe,
W: 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, 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>,