Struct SubgraphWccs 

pub struct SubgraphWccs<D: AsRef<[usize]> = Box<[usize]>, V: SliceByValue<Value = usize> = BitFieldVec<usize>> { /* private fields */ }

A structure that gives access to connected components of a subgraph.

Implementations

impl SubgraphWccs<Box<[usize]>, BitFieldVec<usize>>

pub fn build_from_closure<G, I: IntoParallelIterator<Item = NodeId>>( graph: G, nodes: I, sort_by_size: bool, ) -> Result<Self>

where G: SwhForwardGraph + SwhBackwardGraph + SwhGraphWithProperties + Sync + Send + 'static, for<'succ> <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter: SortedIterator, for<'pred> <<G as SwhBackwardGraph>::Predecessors<'pred> as IntoIterator>::IntoIter: SortedIterator,

Given a set of nodes, computes the connected components in the whole graph that contain these nodes.

For example, if a graph is:

A -> B -> C
     ^
    /
D --
E -> F -> G

then:

• build_from_closure([A, D, F]) and build_from_closure([A, B, D, F]) compute [[A, B, C, D], [E, F, G]]
• build_from_closure([A]) computes [[A, B, C, D]]

pub fn build_from_nodes<G>( graph: G, nodes: Vec<NodeId>, sort_by_size: bool, ) -> Result<Self>

where G: SwhForwardGraph + SwhBackwardGraph + SwhGraphWithProperties + Sync + Send + 'static, for<'succ> <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter: SortedIterator, for<'pred> <<G as SwhBackwardGraph>::Predecessors<'pred> as IntoIterator>::IntoIter: SortedIterator,

Given a set of nodes, computes the connected components in the subgraph made of only these nodes.

For example, if a graph is:

A -> B -> C
     ^
    /
D --
E -> F -> G

then:

• build_from_nodes([A, D, F]) computes [[A], [D], [F]]
• build_from_nodes([A, B, D, F]) compute [[A, B, D], [F]]
• build_from_nodes([A]) computes [[A]]

pub unsafe fn build_from_sorted_nodes<G>( graph: G, nodes: Vec<NodeId>, sort_by_size: bool, ) -> Result<Self>

where G: SwhForwardGraph + SwhBackwardGraph + SwhGraphWithProperties + Sync + Send + 'static, for<'succ> <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter: SortedIterator, for<'pred> <<G as SwhBackwardGraph>::Predecessors<'pred> as IntoIterator>::IntoIter: SortedIterator,

Same as Self::build_from_nodes but assumes the vector of nodes is sorted.

Safety

Undefined behavior if the vector is not sorted

pub fn build_from_contraction<G>( graph: G, contraction: Contraction<EliasFano<SelectZeroAdaptConst<SelectAdaptConst<BitVec<Box<[usize]>>, Box<[usize]>, 12, 3>, Box<[usize]>, 12, 3>>>, sort_by_size: bool, ) -> Result<Self>

where G: SwhForwardGraph + SwhBackwardGraph + SwhGraphWithProperties + Sync + Send + 'static, for<'succ> <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter: SortedIterator, for<'pred> <<G as SwhBackwardGraph>::Predecessors<'pred> as IntoIterator>::IntoIter: SortedIterator,

Same as Self::build_from_nodes but takes a Contraction as input instead of a Vec<usize>

impl<D: AsRef<[usize]>, V: SliceByValue<Value = usize>> SubgraphWccs<D, V>

pub fn num_nodes(&self) -> usize

Returns the total number in all connected components

pub fn contraction(&self) -> Contraction<&impl MonotoneContractionBackend>

pub fn iter_nodes(&self) -> impl Iterator<Item = NodeId> + use<'_, D, V>

Returns an iterator on all the nodes in any connected component

Order is not guaranteed.

Updates the progress logger on every node id from 0 to self.num_nodes(), even those that are filtered out by an underlying subgraph.

pub fn par_iter_nodes( &self, ) -> impl ParallelIterator<Item = NodeId> + use<'_, D, V>

where D: Sync + Send, V: Sync + Send,

Returns a parallel iterator on all the nodes in any connected component

Order is not guaranteed.

Updates the progress logger on every node id from 0 to self.num_nodes(), even those that are filtered out by an underlying subgraph.

pub fn num_components(&self) -> usize

Returns the number of strongly connected components.

pub fn component(&self, node: NodeId) -> Option<usize>

Given a node, returns which component it belongs to, if any

pub fn component_size(&self, i: usize) -> Option<usize>

Returns None if component sizes were not computed, or the size of the ith component otherwise

pub fn component_sizes( &self, ) -> Option<impl Iterator<Item = usize> + use<'_, D, V>>

Returns None if component sizes were not computed, Some(size) otherwise

Trait Implementations

impl<D: AsRef<[usize]>, V> AlignHash for SubgraphWccs<D, V>

where usize: SerInner<SerType: AlignHash>, EliasFano<SelectZeroAdaptConst<SelectAdaptConst<BitVec<D>, D, 12, 3>, D, 12, 3>>: SerInner<SerType: AlignHash>, V: SerInner<SerType: AlignHash> + SliceByValue<Value = usize>, Option<EliasFano<SelectAdaptConst<BitVec<D>, D, 12, 3>>>: 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<D: AsRef<[usize]>, V: SliceByValue<Value = usize>> CopyType for SubgraphWccs<D, V>

type Copy = Deep

impl<D: AsRef<[usize]>, V> DeserInner for SubgraphWccs<D, V>

where usize: DeserInner, EliasFano<SelectZeroAdaptConst<SelectAdaptConst<BitVec<D>, D, 12, 3>, D, 12, 3>>: DeserInner, V: DeserInner + SliceByValue<Value = usize>, Option<EliasFano<SelectAdaptConst<BitVec<D>, D, 12, 3>>>: DeserInner, for<'__epserde_desertype> DeserType<'__epserde_desertype, V>: SliceByValue<Value = usize>,

type DeserType<'__epserde_desertype> = SubgraphWccs<D, <V 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<D: AsRef<[usize]>, V> SerInner for SubgraphWccs<D, V>

where usize: SerInner, EliasFano<SelectZeroAdaptConst<SelectAdaptConst<BitVec<D>, D, 12, 3>, D, 12, 3>>: SerInner, V: SerInner + SliceByValue<Value = usize>, Option<EliasFano<SelectAdaptConst<BitVec<D>, D, 12, 3>>>: SerInner, SerType<V>: SliceByValue<Value = usize>,

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 = SubgraphWccs<D, <V 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<D: AsRef<[usize]>, V> TypeHash for SubgraphWccs<D, V>

where usize: SerInner<SerType: TypeHash>, EliasFano<SelectZeroAdaptConst<SelectAdaptConst<BitVec<D>, D, 12, 3>, D, 12, 3>>: SerInner<SerType: TypeHash>, V: SerInner<SerType: TypeHash> + SliceByValue<Value = usize>, Option<EliasFano<SelectAdaptConst<BitVec<D>, D, 12, 3>>>: 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.