Struct BvGraph 

pub struct BvGraph<F> { /* private fields */ }

A random-access graph in the BV format.

The graph depends on a RandomAccessDecoderFactory that can be used to create decoders for the graph. This allows to decouple the graph from the underlying storage format, and to use different storage formats for the same graph. For example, one can use a memory-mapped file for the graph, or load it in memory, or even generate it on the fly.

Note that the knowledge of the codes used by the graph is in the factory, which provides methods to read each component of the BV format (outdegree, reference offset, block count, etc.), whereas the knowledge of the compression parameters (compression window and minimum interval length) is in this structure.

Implementations

impl BvGraph<()>

pub fn with_basename( basename: impl AsRef<Path>, ) -> LoadConfig<BE, Random, Dynamic, Mmap, Mmap>

Returns a load configuration that can be customized.

impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> BvGraph<DynCodesDecoderFactory<E, F, OFF>>

where for<'a> &'a OFF::DeserType<'a>: IntoIterator<Item = usize>,

pub fn offsets_to_slice( self, ) -> BvGraph<DynCodesDecoderFactory<E, F, Owned<Box<[usize]>>>>

Remaps the offsets in a slice of usize.

This method is mainly useful for benchmarking and testing purposes, as representing the offsets as a slice increasing significantly the memory footprint. It just replaces current decoder factory with the result of DynCodesDecoderFactory::offsets_to_slice.

impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> BvGraph<ConstCodesDecoderFactory<E, F, OFF>>

pub fn offsets_to_slice( self, ) -> BvGraph<ConstCodesDecoderFactory<E, F, Owned<Box<[usize]>>>>

Remaps the offsets in a slice of usize.

This method is mainly useful for benchmarking and testing purposes, as representing the offsets as a slice increasing significantly the memory footprint. It just replaces current decoder factory with the result of ConstCodesDecoderFactory::offsets_to_slice.

impl<F> BvGraph<F>

where F: RandomAccessDecoderFactory,

pub fn new( factory: F, number_of_nodes: usize, number_of_arcs: u64, compression_window: usize, min_interval_length: usize, ) -> Self

Creates a new BvGraph from the given parameters.

Arguments

• reader_factory: backend that can create objects that allows us to read the bitstream of the graph to decode the edges.
• offsets: the bit offset at which we will have to start for decoding the edges of each node. (This is needed for the random accesses, BvGraphSeq does not need them)
• min_interval_length: the minimum size of the intervals we are going to decode.
• compression_window: the maximum distance between two nodes that reference each other.
• number_of_nodes: the number of nodes in the graph.
• number_of_arcs: the number of arcs in the graph.

pub fn into_inner(self) -> F

Consumes self and returns the factory.

impl<F: SequentialDecoderFactory> BvGraph<F>

pub fn offset_deg_iter(&self) -> OffsetDegIter<F::Decoder<'_>>

Creates an iterator specialized in the degrees of the nodes. This is slightly faster because it can avoid decoding some of the nodes and completely skip the merging step.

impl<F: RandomAccessDecoderFactory> BvGraph<F>

where for<'a> F::Decoder<'a>: Decode,

pub fn offset_deg_iter_from(&self, node: usize) -> OffsetDegIter<F::Decoder<'_>>

Creates an iterator specialized in the degrees of the nodes starting from a given node.

Trait Implementations

impl<F: Clone> Clone for BvGraph<F>

fn clone(&self) -> BvGraph<F>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Debug> Debug for BvGraph<F>

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

Formats the value using the given formatter.

impl<'a, F: RandomAccessDecoderFactory> IntoLender for &'a BvGraph<F>

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

type Lender = <BvGraph<F> 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<F> RandomAccessGraph for BvGraph<F>

where F: RandomAccessDecoderFactory,

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<F> RandomAccessLabeling for BvGraph<F>

where F: RandomAccessDecoderFactory,

fn outdegree(&self, node_id: usize) -> usize

Returns the outdegree of a node.

fn labels(&self, node_id: usize) -> Succ<F::Decoder<'_>>

Returns a random access iterator over the successors of a node.

type Labels<'a> = Succ<<F as RandomAccessDecoderFactory>::Decoder<'a>> where Self: 'a, F: 'a

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.

impl<F> SequentialLabeling for BvGraph<F>

where F: RandomAccessDecoderFactory,

fn iter_from(&self, start_node: usize) -> Self::Lender<'_>

Returns a fast sequential iterator over the nodes of the graph and their successors.

type Label = usize

type Lender<'b> = NodeLabels<<F as RandomAccessDecoderFactory>::Decoder<'b>> where Self: 'b, F: 'b

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(&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<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>

where for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,

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

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

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

impl<F> SequentialGraph for BvGraph<F>

where F: RandomAccessDecoderFactory,