Struct outils::graph::dynconn::hdt::DynamicGraph

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));

Implementations

impl<W> DynamicGraph<W> where
    W: WeightType, 

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

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

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

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, 

fn clone(&self) -> DynamicGraph<W>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<W: Debug> Debug for DynamicGraph<W> where
    W: WeightType, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'dc, W> DynamicComponent<'dc, usize> for DynamicGraph<W> where
    W: WeightType, 

fn component_vertices(
    &'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>

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>

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>

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, 

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)

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

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, 

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>

Immutably access the weight of the vertex indexed by v.

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: &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, 

fn edges(&'slf self) -> Box<dyn Iterator<Item = Edge> + 'slf>

Returns a boxed iterator over the indices or the edges held by self, along with their associated vertex indices.