Struct CompactIdMap 

pub struct CompactIdMap<I> { /* private fields */ }

Mapping from graph IDs to a contiguous sequence of virtual IDs that can be used in algorithms.

For compact storages (e.g., AdjList) that do not have any holes in ID sequences even after removing, the mapping is a noop and doesn’t take any memory. Use CompactIdMap::isomorphic constructor in these cases.

For storages with holes and N vertices or edges, the time and space properties are:

• memory used: O(N)
• virtual to real mapping: O(1)
• real to virtual mapping: O(log(N))

For non-integer IDs, the time and space properties are unspecified, but they are expected to be slower than integer IDs.

Implementations

impl<I: IdType> CompactIdMap<I>

pub fn new<A>(iter: A) -> Self

where A: Iterator<Item = I>,

Constructs the map from the iterator of IDs.

pub fn isomorphic(len: usize) -> Self

where I: IntegerIdType,

Constructs a noop map where real IDs are already in contiguous sequence.

pub fn len(&self) -> usize

Returns the number of IDs in the map.

pub fn is_empty(&self) -> bool

Returns true if the map contains no IDs.

pub fn is_isomorphic(&self) -> bool

Returns true if the mapping is noop.

pub fn to_real<V: Into<Virtual<I>>>(&self, id: V) -> Option<I>

Maps given virtual ID to the corresponding real ID in the original graph.

Into<Virtual<I>> is used instead of Virtual<I> because the algorithms often work with usize and that can be used instead of explicitly constructing the Virtual type.

pub fn to_virt(&self, id: I) -> Option<Virtual<I>>

Maps given real ID from the original graph to a virtual ID in the contiguous sequence.

Trait Implementations

impl<I: Debug> Debug for CompactIdMap<I>

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

Formats the value using the given formatter.