Struct VecGraph 

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

A mutable RandomAccessGraph implementation based on a vector of vectors.

This implementation is faster and uses less resources than a BTreeGraph, 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.

Implementation Notes

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

Implementations

impl VecGraph

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)

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>,

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>,

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> + 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> + 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> + 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> + 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)>)

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.

Trait Implementations

impl AlignHash for VecGraph

where LabeledVecGraph<()>: 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 Clone for VecGraph

fn clone(&self) -> VecGraph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl CopyType for VecGraph

type Copy = Deep

impl Debug for VecGraph

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

Formats the value using the given formatter.

impl Default for VecGraph

fn default() -> VecGraph

Returns the “default value” for a type.

impl DeserInner for VecGraph

where LabeledVecGraph<()>: DeserInner,

type DeserType<'__epserde_desertype> = VecGraph

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

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

type Lender = <VecGraph 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 PartialEq for VecGraph

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

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 VecGraph

type Labels<'succ> = AssumeSortedIterator<Map<Copied<Iter<'succ, LabeledArc<()>>>, fn(LabeledArc<()>) -> 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 VecGraph

type Label = usize

type Lender<'a> = LenderImpl<'a, VecGraph> 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 SerInner for VecGraph

where LabeledVecGraph<()>: 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 = VecGraph

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 SplitLabeling for VecGraph

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

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

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

impl TypeHash for VecGraph

where LabeledVecGraph<()>: 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 Eq for VecGraph

impl SequentialGraph for VecGraph

impl StructuralPartialEq for VecGraph