Struct CsrGraph 

pub struct CsrGraph<DCF = Box<[usize]>, S = Box<[usize]>> { /* private fields */ }

A compressed sparse-row graph.

It is a graph representation that stores the degree cumulative function (DCF) and the successors in a compressed format. The DCF is a sequence of offsets that indicates the start of the neighbors for each node in the graph. Building a CSR graph requires always a sorted lender.

The lenders returned by a CSR graph are sorted; however, the successors may be unsorted. If you need the additional guarantee that the successors are sorted, use CsrSortedGraph, which however requires a lender returning sorted successors.

Depending on the performance and memory requirements, both the DCF and successors can be stored in different formats. The default is to use boxed slices for both the DCF and successors, which is the fastest choice.

A CompressedCsrGraph, instead, is a CsrGraph where the DCF is represented using an Elias-Fano encoding, and the successors are represented using a BitFieldVec. There is also a version with sorted successors. Their construction requires a sequential graph providing the number of arcs.

Implementations

impl<DCF, S> CsrGraph<DCF, S>

pub unsafe fn from_parts(dcf: DCF, successors: S) -> Self

Creates a new CSR graph from the given degree cumulative function and successors.

Safety

The degree cumulative function must be monotone and coherent with the successors.

pub fn dcf(&self) -> &DCF

Returns a reference to the degree cumulative function.

pub fn successors(&self) -> &S

Returns a reference to the successors.

pub fn into_inner(self) -> (DCF, S)

Consumes the graph, returning the degree cumulative function and the successors.

impl CsrGraph

pub fn new() -> Self

Creates an empty CSR graph.

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

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

Creates a new CSR graph from an IntoLender yielding a NodeLabelsLender.

This method will determine the number of nodes from the maximum node ID encountered.

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 CSR graph from a sorted IntoLender yielding a sorted NodeLabelsLender.

This method is an alias for from_lender, as both sorted and unsorted lenders are handled identically in the unsorted case.

pub fn from_seq_graph<G: SequentialGraph>(g: &G) -> Self

where for<'a> G::Lender<'a>: SortedLender,

Creates a new CSR graph from a SequentialGraph.

This method uses the graph’s size hints for efficient pre-allocation.

impl CsrGraph<EliasFano<SelectAdaptConst<BitVec<Box<[usize]>>, Box<[usize]>, 12, 4>>, BitFieldVec>

pub fn try_from_graph<G: SequentialGraph>(g: &G) -> Result<Self>

where for<'a> G::Lender<'a>: SortedLender,

Creates a new compressed CSR graph from a sequential graph with sorted lender and providing the number of arcs.

This method will return an error if the graph does not provide the number of arcs.

Trait Implementations

impl<DCF, S> AlignHash for CsrGraph<DCF, S>

where DCF: SerInner<SerType: AlignHash>, S: 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<DCF: Clone, S: Clone> Clone for CsrGraph<DCF, S>

fn clone(&self) -> CsrGraph<DCF, S>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<DCF, S> CopyType for CsrGraph<DCF, S>

type Copy = Deep

impl<DCF: Debug, S: Debug> Debug for CsrGraph<DCF, S>

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

Formats the value using the given formatter.

impl Default for CsrGraph

fn default() -> Self

Returns the “default value” for a type.

impl<DCF, S> DeserInner for CsrGraph<DCF, S>

where DCF: DeserInner, S: DeserInner,

type DeserType<'__epserde_desertype> = CsrGraph<<DCF as DeserInner>::DeserType<'__epserde_desertype>, <S as DeserInner>::DeserType<'__epserde_desertype>>

The deserialization type associated with this type. It can be retrieved conveniently with the alias 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<'a, DCF, S> IntoLender for &'a CsrGraph<DCF, S>

where DCF: SliceByValue + IterateByValueFrom<Item = usize>, S: SliceByValue + IterateByValueFrom<Item = usize>,

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

type Lender = LenderImpl<<DCF as IterateByValueFromGat<'a>>::IterFrom, <S as IterateByValueFromGat<'a>>::IterFrom>

The lender type that this type converts into.

fn into_lender(self) -> Self::Lender

Converts this type into a Lender.

impl<DCF, S> RandomAccessGraph for CsrGraph<DCF, S>

where DCF: SliceByValue<Value = usize> + IterateByValueFrom<Item = usize>, S: SliceByValue<Value = usize> + IterateByValueFrom<Item = usize>,

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<DCF, S> RandomAccessLabeling for CsrGraph<DCF, S>

where DCF: SliceByValue<Value = usize> + IterateByValueFrom<Item = usize>, S: SliceByValue<Value = usize> + IterateByValueFrom<Item = usize>,

type Labels<'succ> = Take<<S as IterateByValueFromGat<'succ>>::IterFrom> where Self: '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<DCF, S> SequentialLabeling for CsrGraph<DCF, S>

where DCF: SliceByValue + IterateByValueFrom<Item = usize>, S: SliceByValue + IterateByValueFrom<Item = usize>,

type Label = usize

type Lender<'a> = LenderImpl<<DCF as IterateByValueFromGat<'a>>::IterFrom, <S as IterateByValueFromGat<'a>>::IterFrom> 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 build_dcf(&self) -> DCF

Builds the degree cumulative function for this labeling.

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, 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<DCF, S> SerInner for CsrGraph<DCF, S>

where DCF: SerInner, S: 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 = CsrGraph<<DCF as SerInner>::SerType, <S as SerInner>::SerType>

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<DCF, S> TypeHash for CsrGraph<DCF, S>

where DCF: SerInner<SerType: TypeHash>, S: 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<D, S> SequentialGraph for CsrGraph<D, S>

where D: SliceByValue + IterateByValueFrom<Item = usize>, S: SliceByValue + IterateByValueFrom<Item = usize>,