Struct blossom::graph::AnnotatedGraph

pub struct AnnotatedGraph<Annotation> where
    Annotation: Copy + Sized,  { /* fields omitted */ }

A graph with annotations on edges

Methods

impl<Annotation> AnnotatedGraph<Annotation> where
    Annotation: Copy + Sized, 

fn new(edges: HashMap<Vertex, (Vec<Vertex>, Vec<Annotation>)>) -> Self

Returns a new AnnotatedGraph instance

Arguments

• edges - HashMap from vertex to edges and their meta data

Remarks

Edges is inherently redundant. It is the responsibility of the caller to guarantee consistency.

Example

use blossom::graph::AnnotatedGraph;
let graph = AnnotatedGraph::new([
  (0, (vec![1, 2], vec![0.1, 0.4])),
  (2, (vec![0], vec![0.4])),
  (1, (vec![0], vec![0.1]))
].iter().cloned().collect());

fn is_empty(&self) -> bool

Gets a value indicating whether the graph is empty

fn len(&self) -> usize

Gets the number of vertices in the graph

fn vertices(&self) -> &[Vertex]

Gets the vertices in the graph

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

Gets the vertices adjacent to the given vertex

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

Gets the edges adjacent to the given vertex

fn filter_vertices<P>(&self, predicate: P) -> Self where
    P: Fn(&Vertex) -> bool, 

Creates a new AnnotatedGraph with vertices filtered by given predicate.

fn filter_edges<P>(&self, predicate: P) -> Self where
    P: Fn(&Vertex, &Vertex, &Annotation) -> bool, 

Creates a new AnnotatedGraph with edges filtered by given predicate.

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;
let graph: Graph = [
  (0, vec![1, 2, 3]),
  (1, vec![0, 2]),
  (2, vec![0, 1]),
  (3, vec![0])
].iter().collect();
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)));

fn full_matching(&self) -> Option<Matching>

Determines a full matching in the current graph. If a full matching is not possible, None is returned.

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

Note 2: in a graph with 2n+1 vertices, a matching consisting of n edges is considered full.

Trait Implementations

impl<Annotation: Clone> Clone for AnnotatedGraph<Annotation> where
    Annotation: Copy + Sized, 

fn clone(&self) -> AnnotatedGraph<Annotation>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Annotation: Debug> Debug for AnnotatedGraph<Annotation> where
    Annotation: Copy + Sized, 

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

Formats the value using the given formatter.

impl<Annotation> FromIterator<(Vertex, (Vec<Vertex>, Vec<Annotation>))> for AnnotatedGraph<Annotation> where
    Annotation: Copy + Sized, 

fn from_iter<I: IntoIterator<Item = (Vertex, (Vec<Vertex>, Vec<Annotation>))>>(
    iter: I
) -> Self

Creates a value from an iterator.

impl<'a, Annotation> FromIterator<&'a (Vertex, (Vec<Vertex>, Vec<Annotation>))> for AnnotatedGraph<Annotation> where
    Annotation: 'a + Copy + Sized, 

fn from_iter<I: IntoIterator<Item = &'a (Vertex, (Vec<Vertex>, Vec<Annotation>))>>(
    iter: I
) -> Self

Creates a value from an iterator.