Struct blossom::graph::Graph

pub struct Graph { /* fields omitted */ }

An undirected graph

Methods

impl Graph

fn new(vertices: &[Vertex], edges: &[Edge]) -> Graph

Returns a person with the name given them

Arguments

• vertices - All vertices
• edges - All edges; undirected edges should be specified once, it suffices to specify one direction

Example

use blossom::graph::Graph;
let graph = Graph::new(&[0, 1, 2], &[(0, 1), (1, 2)]);

fn is_empty(&self) -> bool

Returns a value indicating whether the graph is empty, i.e. whether is has no vertices.

fn len(&self) -> usize

Returns the number of vertices in the graph.

fn vertices(&self) -> Vec<Vertex>

Exports all vertices in a vector.

fn vertices_from(&self, vertex: Vertex) -> &[Vertex]

Gets a slice of all vertices connected to the given vertex. Panics if graph does not contain a vertex vertex.

Arguments

• vertex - The start vertex

fn exposed(&self, matching: &Matching) -> Vec<Vertex>

Gets all exposed vertices with respect to the given matching.

Arguments

• matching - Some matching - possibly not maximum - in this graph.

fn contract(&self, root: Vertex, leafs: &[Vertex]) -> Graph

Creates a new graph with all vertices in leafs contracted into root.

Arguments

• root - Root vertex - will reappear in resulting graph.
• leafs - Leaf vertices - will not reappear in resulting graph.

fn maximum_matching(&self) -> Matching

Determines a maximum matching in the current graph.

Note: the (undirected) edges may be represented in reverse direction from the initial graph construction.

Example

use blossom::graph::Graph;
let graph = Graph::new(&[0, 1, 2, 3], &[(0, 1), (0, 2), (0, 3), (1, 2)]);
let matching = graph.maximum_matching();
let matching_edges = matching.edges();
assert!(!matching_edges.contains(&(0, 1)) && !matching_edges.contains(&(1, 0)));
assert!(matching_edges.contains(&(0, 3)) || matching_edges.contains(&(3, 0)));

Trait Implementations

impl Clone for Graph

fn clone(&self) -> Graph

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Graph

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.