Struct dfir_lang::graph::DiMulGraph

pub struct DiMulGraph<V, E>
where
    V: Key,
    E: Key,
{ /* private fields */ }

A directed multigraph where an vertex’s inbound and outbound edges are indexed.

DiMulGraph does not allocate vertices V. The user shall use an external SlotMap<V, _> for allocating vertices, which also allows the user to associate data with each vertex.

DiMulGraph does allocate edges E as they are added. Additional data can be associated with edges via an external SecondaryMap<E, _>.

Implementations

impl<V, E> DiMulGraph<V, E>

where V: Key, E: Key,

pub fn new() -> Self

Creates an empty DiMulGraph.

pub fn with_capacity(capacity: usize) -> Self

Creates a DiMulGraph with pre-allocated memory for capacity vertices and capacity edges.

pub fn assert_valid(&self)

Assert that self is in a consistent state, for debugging. This is computationally expensive for large graphs.

pub fn insert_edge(&mut self, src: V, dst: V) -> E

Creates an edge going from src to dst and returns the edge ID.

pub fn insert_intermediate_vertex( &mut self, new_vertex: V, edge: E, ) -> Option<(E, E)>

For an edge from A --> B, insert a new vertex V along that edge to create A --e0--> V --e1--> B. Returns the pair of new edge IDs in and out of V, i.e. (e0, e1).

Returns None if the edge doesn’t exist.

edge is removed from the graph, both returned edge IDs are new.

pub fn remove_intermediate_vertex(&mut self, vertex: V) -> Option<(E, (E, E))>

For a vertex with one incoming edge and one outgoing edge, removes the vertex. Inserts a new edge. Returns (new edge, (old edge in, old edge out)). Returns None if vertex is not in the graph or does not have the right degree in/out.

pub fn remove_edge(&mut self, e: E) -> Option<(V, V)>

Remove an edge from the graph. If the edgeId is found then the edge is removed from the graph and returned. If the edgeId was not found in the graph then nothing is returned and nothing is done.

pub fn remove_vertex(&mut self, v: V)

Remove a vertex from the graph, it must have no edges to or from it when doing this.

pub fn edge(&self, e: E) -> Option<(V, V)>

Get the source and destination vertex IDs for the given edge ID.

pub fn edge_ids(&self) -> Keys<'_, E, (V, V)>

Return an iterator over all edge IDs E.

pub fn edges( &self, ) -> impl '_ + ExactSizeIterator<Item = (E, (V, V))> + FusedIterator + Clone + Debug

Return an iterator over all edges in form (E, (V, V)).

pub fn successor_edges(&self, v: V) -> Copied<Iter<'_, E>>

Return an iterator of all edge IDs coming out of v.

pub fn predecessor_edges(&self, v: V) -> Copied<Iter<'_, E>>

Return an iterator of all edge IDs going into v.

pub fn successor_vertices( &self, v: V, ) -> impl '_ + DoubleEndedIterator<Item = V> + ExactSizeIterator + FusedIterator + Clone + Debug

Return an iterator of all successor vertex IDs of v.

pub fn predecessor_vertices( &self, v: V, ) -> impl '_ + DoubleEndedIterator<Item = V> + ExactSizeIterator + FusedIterator + Clone + Debug

Return an iterator of all predecessor vertex IDs of v.

pub fn successors( &self, v: V, ) -> impl '_ + DoubleEndedIterator<Item = (E, V)> + ExactSizeIterator + FusedIterator + Clone + Debug

Return an iterator of all successor edge IDs and vertex IDs of v in form (E, V).

pub fn predecessors( &self, v: V, ) -> impl '_ + DoubleEndedIterator<Item = (E, V)> + ExactSizeIterator + FusedIterator + Clone + Debug

Return an iterator of all predecessor edge IDs and vertex IDs of v in form (E, V).

pub fn degree_out(&self, v: V) -> usize

The degree (number of edges/vertices) coming out of v, i.e. the number of successors.

pub fn degree_in(&self, v: V) -> usize

The degree (number of edges/vertices) going into v, i.e. the number of predecessors.

Trait Implementations

impl<V, E> Clone for DiMulGraph<V, E>

where V: Key + Clone, E: Key + Clone,

fn clone(&self) -> DiMulGraph<V, E>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<V, E> Debug for DiMulGraph<V, E>

where V: Key + Debug, E: Key + Debug,

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

Formats the value using the given formatter.

impl<V, E> Default for DiMulGraph<V, E>

where V: Key, E: Key,

fn default() -> Self

Returns the “default value” for a type.

impl<'de, V, E> Deserialize<'de> for DiMulGraph<V, E>

where V: Key + Deserialize<'de>, E: Key + Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<V, E> From<DiMulGraph<V, E>> for SlotMap<E, (V, V)>

where V: Key, E: Key,

fn from(value: DiMulGraph<V, E>) -> Self

Converts to this type from the input type.

impl<V, E> From<SlotMap<E, (V, V)>> for DiMulGraph<V, E>

where V: Key, E: Key,

fn from(edges: SlotMap<E, (V, V)>) -> Self

Converts to this type from the input type.

impl<V, E> Serialize for DiMulGraph<V, E>

where V: Key + Serialize, E: Key + Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.