Struct LabeledBTreeGraph

pub struct LabeledBTreeGraph<L: Clone + 'static = ()> { /* private fields */ }

A mutable LabeledRandomAccessGraph implementation based on a vector of BTreeSet.

This implementation is slower and uses more resources than a LabeledVecGraph, but it is more flexible as arcs can be added in any order.

By setting the feature serde, this struct can be serialized and deserialized using serde.

Implementations

impl<L: Clone + 'static> LabeledBTreeGraph<L>

pub fn new() -> Self

Creates a new empty graph.

pub fn empty(n: usize) -> Self

Creates a new empty graph with n nodes.

pub fn add_node(&mut self, node: usize) -> bool

Add an isolated node to the graph and return true if it is a new node.

Panics

This method will panic if one of the given nodes is greater or equal than the number of nodes in the graph.

pub fn add_arc(&mut self, u: usize, v: usize, l: L) -> bool

Add a labeled arc to the graph and return whether it is a new one.

pub fn remove_arc(&mut self, u: usize, v: usize) -> bool

Remove an arc from the graph and return whether it was present or not.

pub fn add_lender<I: IntoLender>(&mut self, iter_nodes: I)

where I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,

Add nodes and labeled successors from an IntoLender yielding a NodeLabelsLender.

pub fn from_lender<I: IntoLender>(iter_nodes: I) -> Self

where I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,

Creates a new graph from an IntoLender yielding a NodeLabelsLender.

pub fn add_arcs(&mut self, arcs: impl IntoIterator<Item = (usize, usize, L)>)

Add labeled arcs from an IntoIterator, adding new nodes as needed.

The items must be triples of the form (usize, usize, l) specifying an arc and its label.

pub fn from_arcs(arcs: impl IntoIterator<Item = (usize, usize, L)>) -> Self

Creates a new graph from an IntoIterator.

The items must be triples of the form (usize, usize, l) specifying an arc and its label.

pub fn shrink_to_fit(&mut self)

Shrink the capacity of the graph to fit its current size.

Implementation Notes

This method just shrinks the capacity of the successor vector, as BTreeSet does not have a shrink_to_fit method.

Trait Implementations

impl<L: Clone + Clone + 'static> Clone for LabeledBTreeGraph<L>

fn clone(&self) -> LabeledBTreeGraph<L>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<L: Debug + Clone + 'static> Debug for LabeledBTreeGraph<L>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<L: Clone + 'static> Default for LabeledBTreeGraph<L>

fn default() -> Self

Returns the “default value” for a type.

impl From<LabeledBTreeGraph> for BTreeGraph

fn from(g: LabeledBTreeGraph<()>) -> Self

Converts to this type from the input type.

impl<'a, L: Clone + 'static> IntoLender for &'a LabeledBTreeGraph<L>

type Lender = <LabeledBTreeGraph<L> as SequentialLabeling>::Lender<'a>

fn into_lender(self) -> Self::Lender

impl<L: Clone + 'static> LabeledRandomAccessGraph<L> for LabeledBTreeGraph<L>

fn successors( &self, node_id: usize, ) -> <Self as RandomAccessLabeling>::Labels<'_>

Returns pairs given by successors of a node and their labels.

fn has_arc(&self, src_node_id: usize, dst_node_id: usize) -> bool

Returns whether there is an arc going from src_node_id to dst_node_id.

impl<L: Clone + 'static + PartialEq> PartialEq for LabeledBTreeGraph<L>

Manual implementation of PartialEq. This implementation is necessary because the private struct [Successor] that we use to store in a BTreeSet the tuple (usize, Label) implements PartialEq ignoring the label so to enforce the absence of duplicate arcs. This implies that the derived implementation of PartialEq would not check labels, so the same graph with different labels would be equal, and this is not the intended semantics.

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<L: Clone + 'static> RandomAccessLabeling for LabeledBTreeGraph<L>

type Labels<'succ> = Successors<'succ, L> where L: 'succ

The type of the iterator over the labels of a node returned by labels.

fn num_arcs(&self) -> u64

Returns the number of arcs in the graph.

fn outdegree(&self, node: usize) -> usize

Returns the number of labels associated with a node.

fn labels(&self, node: usize) -> <Self as RandomAccessLabeling>::Labels<'_>

Returns the labels associated with a node.

impl<L: Clone + 'static> SequentialLabeling for LabeledBTreeGraph<L>

type Label = (usize, L)

type Lender<'a> = IteratorImpl<'a, LabeledBTreeGraph<L>> where Self: 'a

The type of Lender over the successors of a node returned by iter.

fn num_nodes(&self) -> usize

Returns the number of nodes in the graph.

fn num_arcs_hint(&self) -> Option<u64>

Returns the number of arcs in the graph, if available.

fn iter_from(&self, from: usize) -> Self::Lender<'_>

Returns an iterator over the labeling starting at from (included).

fn iter(&self) -> Self::Lender<'_>

Returns an iterator over the labeling.

fn par_node_apply<A: Default + Send, F: Fn(Range<usize>) -> A + Sync, R: Fn(A, A) -> A + Sync>( &self, func: F, fold: R, granularity: Granularity, thread_pool: &ThreadPool, pl: &mut impl ConcurrentProgressLog, ) -> A

Applies func to each chunk of nodes of size node_granularity in parallel, and folds the results using fold.

fn par_apply<F: Fn(Range<usize>) -> A + Sync, A: Default + Send, R: Fn(A, A) -> A + Sync, D: Succ<Input = usize, Output = usize>>( &self, func: F, fold: R, granularity: Granularity, deg_cumul: &D, thread_pool: &ThreadPool, pl: &mut impl ConcurrentProgressLog, ) -> A

Apply func to each chunk of nodes containing approximately arc_granularity arcs in parallel and folds the results using fold.

impl<L: Clone + 'static + Eq> Eq for LabeledBTreeGraph<L>

impl<L: Clone + 'static> LabeledSequentialGraph<L> for LabeledBTreeGraph<L>