Struct CsrSortedGraph 

pub struct CsrSortedGraph<DCF = Box<[usize]>, S = Box<[usize]>>(/* private fields */);

A wrapper for a CsrGraph with the additional guarantee that the successors are sorted.

Implementations

impl CsrSortedGraph

pub fn from_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 sorted CSR graph from an IntoLender yielding a sorted NodeLabelsLender with sorted successors.

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

where for<'a> G::Lender<'a>: SortedLender, for<'a, 'b> LenderIntoIter<'b, G::Lender<'a>>: SortedIterator,

Creates a new sorted CSR graph from a SequentialGraph with sorted lenders and sorted successors.

impl CsrSortedGraph<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, for<'a, 'b> LenderIntoIter<'b, G::Lender<'a>>: SortedIterator,

Creates a new compressed CSR sorted graph from a sequential graph with sorted lender, sorted successors, 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 CsrSortedGraph<DCF, S>

where CsrGraph<DCF, 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 CsrSortedGraph<DCF, S>

fn clone(&self) -> CsrSortedGraph<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 CsrSortedGraph<DCF, S>

type Copy = Deep

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

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

Formats the value using the given formatter.

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

where CsrGraph<DCF, S>: DeserInner,

type DeserType<'__epserde_desertype> = CsrSortedGraph<DCF, S>

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<'a, DCF, S> IntoLender for &'a CsrSortedGraph<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 = <&'a CsrSortedGraph<DCF, S> 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<DCF, S> RandomAccessGraph for CsrSortedGraph<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 CsrSortedGraph<DCF, S>

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

type Labels<'succ> = AssumeSortedIterator<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 CsrSortedGraph<DCF, S>

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

type Label = usize

type Lender<'a> = LenderSortedImpl<<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 CsrSortedGraph<DCF, S>

where CsrGraph<DCF, 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 = CsrSortedGraph<DCF, S>

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 CsrSortedGraph<DCF, S>

where CsrGraph<DCF, 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 CsrSortedGraph<D, S>

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