Struct LabeledVecGraph 

pub struct LabeledVecGraph<L: Clone + 'static> { /* private fields */ }

A mutable LabeledRandomAccessGraph implementation based on a vector of vectors.

This implementation is faster and uses less resources than a LabeledBTreeGraph, but it is less flexible as arcs can be added only in increasing successor order.

This struct can be serialized with ε-serde. By setting the feature serde, this struct can be serialized using serde, too.

Implementations

impl<L: Clone + 'static> LabeledVecGraph<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.

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

Add an arc to the graph.

New arcs must be added in increasing successor order, or this method will panic.

Panics

This method will panic:

• if one of the given nodes is greater or equal than the number of nodes in the graph;
• if the successor is lesser than or equal to the current last successor of the source node.

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

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

Add nodes and successors from an IntoLender yielding a NodeLabelsLender.

If the lender is sorted, consider using add_sorted_lender, as it does not need to sort the output of the lender.

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.

If the lender is sorted, consider using from_sorted_lender, as it does not need to sort the output of the lender.

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

where I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)> + SortedLender, for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator,

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

This method is faster than add_lender as it does not need to sort the output of the lender.

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

where I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)> + SortedLender, for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator,

Creates a new graph from a sorted IntoLender yielding a NodeLabelsLender.

This method is faster than from_lender as it does not need to sort the output of the lender.

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

where I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)> + SortedLender, for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator + ExactSizeIterator,

Add nodes and successors from an IntoLender yielding a sorted NodeLabelsLender whose successors implement ExactSizeIterator.

This method has a better memory behavior than add_sorted_lender as it can allocate the right amount of memory for each node at once.

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

where I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)> + SortedLender, for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator + ExactSizeIterator,

Creates a new graph from a sorted IntoLender yielding a NodeLabelsLender whose successors implement ExactSizeIterator.

This method has a better memory behavior than from_sorted_lender as it can allocate the right amount of memory for each node at once.

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 labeled pairs 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 labeled pairs 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.

Trait Implementations

impl<L: Clone + 'static> AlignHash for LabeledVecGraph<L>

where u64: SerInner<SerType: AlignHash>, Vec<Vec<LabeledArc<L>>>: SerInner<SerType: AlignHash>,

fn align_hash(hasher: &mut impl Hasher, offset_of: &mut usize)

Accumulates alignment information in hasher assuming to be positioned at offset_of.

fn align_hash_val(&self, hasher: &mut impl Hasher, offset_of: &mut usize)

Calls AlignHash::align_hash on a value.

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

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<L: Clone + 'static> CopyType for LabeledVecGraph<L>

type Copy = Deep

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

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

impl<L: Clone + 'static> DeserInner for LabeledVecGraph<L>

where u64: DeserInner, Vec<Vec<LabeledArc<L>>>: DeserInner,

type DeserType<'__epserde_desertype> = LabeledVecGraph<L>

The deserialization type associated with this type. It can be retrieved conveniently with the alias DeserType.

fn __check_covariance<'__long: '__short, '__short>( proof: CovariantProof<Self::DeserType<'__long>>, ) -> CovariantProof<Self::DeserType<'__short>>

Compile-time covariance check for DeserType.

unsafe fn _deser_full_inner( backend: &mut impl ReadWithPos, ) -> Result<Self, Error>

Safety

unsafe fn _deser_eps_inner<'deser_eps_inner_lifetime>( backend: &mut SliceWithPos<'deser_eps_inner_lifetime>, ) -> Result<Self::DeserType<'deser_eps_inner_lifetime>, Error>

Safety

impl From<LabeledVecGraph<()>> for VecGraph

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

Converts to this type from the input type.

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

Convenience implementation that makes it possible to iterate over the graph using the for_ macro (see the crate documentation).

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

The lender type that this type converts into.

fn into_lender(self) -> Self::Lender

Converts this type into a Lender.

impl<L: Clone + 'static> LabeledRandomAccessGraph<L> for LabeledVecGraph<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: usize, dst: usize) -> bool

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

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

fn eq(&self, other: &LabeledVecGraph<L>) -> 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 LabeledVecGraph<L>

type Labels<'succ> = AssumeSortedIterator<Map<Cloned<Iter<'succ, LabeledArc<L>>>, fn(LabeledArc<L>) -> (usize, L)>>

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 LabeledVecGraph<L>

type Label = (usize, L)

type Lender<'a> = LenderImpl<'a, LabeledVecGraph<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 build_dcf(&self) -> DCF

Builds the degree cumulative function for this 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, 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: for<'a> Succ<Input = usize, Output<'a> = usize>>( &self, func: F, fold: R, granularity: Granularity, deg_cumul: &D, pl: &mut impl ConcurrentProgressLog, ) -> A

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

impl<L: Clone + 'static> SerInner for LabeledVecGraph<L>

where u64: SerInner, Vec<Vec<LabeledArc<L>>>: SerInner,

const IS_ZERO_COPY: bool

Inner constant used by the derive macros to keep track recursively of whether the type satisfies the conditions for being zero-copy. It is checked at runtime against the trait implemented by the type, and if a ZeroCopy type has this constant set to false serialization will panic.

type SerType = LabeledVecGraph<L>

This is the type that will be written in the header of the file, and thus the type that will be deserialized. In most cases it is Self, but in some cases, as for references to slices, it is customized.

unsafe fn _ser_inner(&self, backend: &mut impl WriteWithNames) -> Result<()>

Serializes this structure using the given backend.

impl<L: Clone + Sync> SplitLabeling for LabeledVecGraph<L>

type SplitLender<'a> = Take<<LabeledVecGraph<L> as SequentialLabeling>::Lender<'a>> where Self: 'a

type IntoIterator<'a> = Iter<'a, LabeledVecGraph<L>> where Self: 'a

fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_>

impl<L: Clone + 'static> TypeHash for LabeledVecGraph<L>

where u64: SerInner<SerType: TypeHash>, Vec<Vec<LabeledArc<L>>>: SerInner<SerType: TypeHash>,

fn type_hash(hasher: &mut impl Hasher)

Accumulates type information in hasher.

fn type_hash_val(&self, hasher: &mut impl Hasher)

Calls TypeHash::type_hash on a value.

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

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

impl<L: Clone + 'static> StructuralPartialEq for LabeledVecGraph<L>