Struct prepona::algo::VertexEdgeCut

pub struct VertexEdgeCut<'a, W, E: Edge<W>> { /* fields omitted */ }

Finds cut vertices(articulation points) and cut edges(bridges).

Examples

use prepona::prelude::*;
use prepona::storage::Mat;
use prepona::graph::MatGraph;
use prepona::algo::VertexEdgeCut;

// Given:
//            .-- c --.
//            |       |
//      a --- b ----- d --- e
//
let mut graph = MatGraph::init(Mat::<usize>::init());
let a = graph.add_vertex();
let b = graph.add_vertex();
let c = graph.add_vertex();
let d = graph.add_vertex();
let e = graph.add_vertex();
let ab = graph.add_edge_unchecked(a, b, 1.into());
graph.add_edge_unchecked(b, c, 1.into());
graph.add_edge_unchecked(c, d, 1.into());
graph.add_edge_unchecked(b, d, 1.into());
let de = graph.add_edge_unchecked(d, e, 1.into());

let (cut_vertices, cut_edges) = VertexEdgeCut::init(&graph).execute(&graph);

assert_eq!(cut_vertices.len(), 2);
assert!(vec![b, d]
    .iter()
    .all(|vertex_id| cut_vertices.contains(vertex_id)));
assert_eq!(cut_edges.len(), 2);
assert!(vec![ab, de].into_iter().all(|edge_id| cut_edges
    .iter()
    .find(|(_, _, edge)| edge.get_id() == edge_id)
    .is_some()))

Implementations

impl<'a, W, E: Edge<W>> VertexEdgeCut<'a, W, E>

pub fn init<G>(graph: &G) -> Self where
    G: Vertices + Edges<W, E> + Graph<W, E, UndirectedEdge>, 

Initializes the structure.

pub fn execute<G>(self, graph: &'a G) -> (Vec<usize>, Vec<(usize, usize, &E)>) where
    G: Vertices + Edges<W, E> + Graph<W, E, UndirectedEdge>, 

Finds cut vertices(articulation points) and cut edges(bridges).

Arguments

graph: Graph to search for cut vertices and edges in it.

Returns

Cut vertices(first) and cut edges(second).
Cut vertices will be a vector of vertex ids.
Cut edges will be vector of (src_id, dst_id, edge reference).