Struct BTreeGraph

pub struct BTreeGraph(/* private fields */);

A mutable RandomAccessGraph implementation based on a vector of BTreeSet.

This implementation is slower and uses more resources than a VecGraph, 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.

Implementation Notes

This is just a newtype for a LabeledBTreeGraph with () labels. All mutation methods are delegated.

Implementations

impl BTreeGraph

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.

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

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

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

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

Add nodes and 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>,

Creates a new graph from an IntoLender yielding a NodeLabelsLender.

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

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

The items must be pairs of the form (usize, usize) specifying an arc.

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

Creates a new graph from an IntoIterator.

The items must be pairs of the form (usize, usize) specifying an arc.

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 Clone for BTreeGraph

fn clone(&self) -> BTreeGraph

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for BTreeGraph

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

Formats the value using the given formatter.

impl Default for BTreeGraph

fn default() -> BTreeGraph

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> IntoLender for &'a BTreeGraph

type Lender = <BTreeGraph as SequentialLabeling>::Lender<'a>

fn into_lender(self) -> Self::Lender

impl PartialEq for BTreeGraph

fn eq(&self, other: &BTreeGraph) -> 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 RandomAccessGraph for BTreeGraph

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

Returns the successors of a node.

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 RandomAccessLabeling for BTreeGraph

type Labels<'succ> = Map<Iter<'succ, Successor<()>>, fn(&Successor<()>) -> usize>

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 SequentialLabeling for BTreeGraph

type Label = usize

type Lender<'a> = IteratorImpl<'a, BTreeGraph> 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 Eq for BTreeGraph

impl SequentialGraph for BTreeGraph

impl StructuralPartialEq for BTreeGraph