[−][src]Trait outils::graph::dynconn::DynamicConnectivity

pub trait DynamicConnectivity<W = EmptyWeight, Ix = DefaultIndexType> where
    Ix: IndexType, {
    fn insert_edge(
        &mut self, 
        v: VertexIndex<Ix>, 
        w: VertexIndex<Ix>
    ) -> Option<Edge<Ix>>;

    fn delete_edge(&mut self, e: Edge<Ix>);

    fn is_connected(&self, v: VertexIndex<Ix>, w: VertexIndex<Ix>) -> bool;
}

This trait defines the fundamental operations of a dynamic graph, that is a graph providing a fully dynamic connectivity interface.

A dynamic graph data structure is able 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 between queries (see also Dynamic Connectivity).

Required methods

fn insert_edge(
    &mut self,
    v: VertexIndex<Ix>,
    w: VertexIndex<Ix>
) -> Option<Edge<Ix>>

Connects the vertices indexed by v and w and returns index of the created edge. If the vertices cannot be connected - the reasons for this dependant on the implementation of this trait - None is returned.

fn delete_edge(&mut self, e: Edge<Ix>)

Deletes the edge e from the graph if it exists.

fn is_connected(&self, v: VertexIndex<Ix>, w: VertexIndex<Ix>) -> bool

Returns true if the two vertices indexed by v and w are connected in self through a path of edges.

Loading content...

Implementors

impl<W> DynamicConnectivity<W, usize> for DynamicGraph<W> where
    W: WeightType, [src]

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.

Loading content...