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

pub trait DynamicComponent<'a, Ix = DefaultIndexType> where
    Ix: IndexType, {
    fn component_vertices(
        &'a self, 
        v: VertexIndex<Ix>
    ) -> Box<dyn Iterator<Item = VertexIndex<Ix>> + 'a>;

    fn components(&'a self) -> Box<dyn Iterator<Item = VertexIndex<Ix>> + 'a>;

    fn component_edges(
        &'a self, 
        v: VertexIndex<Ix>
    ) -> Box<dyn Iterator<Item = Edge> + 'a>;

    fn disconnect_component(&mut self, v: VertexIndex<Ix>) -> Vec<Edge>;
}

This trait defines the fundamental operations of a dynamic graph, that can be applied to a connected sub-graph, that is, the connected components of the graph.

Required methods

fn component_vertices(
    &'a self,
    v: VertexIndex<Ix>
) -> Box<dyn Iterator<Item = VertexIndex<Ix>> + 'a>

Returns a boxed iterator over the indices of the vertices which are connected to the vertex indexed by v.

fn components(&'a self) -> Box<dyn Iterator<Item = VertexIndex<Ix>> + 'a>

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.

fn component_edges(
    &'a self,
    v: VertexIndex<Ix>
) -> Box<dyn Iterator<Item = Edge> + 'a>

Returns a boxed iterator over the indices of the edges which connect the component the vertex indexed by v is part of.

fn disconnect_component(&mut self, v: VertexIndex<Ix>) -> Vec<Edge>

Deletes all edges from this graph which connect the component the vertex indexed by v is part of.

Loading content...

Implementors

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

fn component_vertices(
    &'dc self,
    v: VertexIndex
) -> Box<dyn Iterator<Item = VertexIndex> + 'dc>[src]

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]

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));
Loading content...