Struct DynamicGraph

pub struct DynamicGraph<T: Clone> { /* private fields */ }

Implementations

impl<T: Clone + Copy> DynamicGraph<T>

pub fn check_integrity(&self) -> bool

In time O(V+E) check that the following invariants hold: a) the target node of each non-spare edge is smaller than the number of nodes, and b) the number of non-spare edges add up to the number of edges, and c) the first_edge id at each node is valid d) the number of nodes is consistent with the node array size

pub fn new( node_count: usize, input: Vec<impl Edge<ID = NodeID> + EdgeData<DATA = T> + Ord>, ) -> Self

pub fn new_from_sorted_list( number_of_nodes: usize, input: &[impl Edge<ID = NodeID> + EdgeData<DATA = T> + Ord], ) -> Self

pub fn insert_node(&mut self)

Inserts a node with an empty edge slice into the node array.

pub fn insert_edge(&mut self, source: NodeID, target: NodeID, data: T)

Inserts an edge into the graph by making sure that there’s room one index past the current edge slice. It does so by doing the following: If one past the slice is a spare edge, use it Else, if one before the slice is a spare, move the last element over Else, resize the edge array sufficiently and relocate the slice at the beginning of the newly added extension of the edge array.

pub fn remove_edge(&mut self, source: NodeID, edge_to_delete: EdgeID)

Removes an edge by adjusting counters, moving the edge-to-delete to the end of the edge slice and making it a spare edge

Trait Implementations

impl<T: Clone + Copy> Default for DynamicGraph<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Copy> Graph<T> for DynamicGraph<T>

fn node_range(&self) -> Range<NodeID>

fn edge_range(&self, n: NodeID) -> Range<EdgeID>

fn number_of_nodes(&self) -> usize

fn number_of_edges(&self) -> usize

fn begin_edges(&self, n: NodeID) -> EdgeID

fn end_edges(&self, n: NodeID) -> EdgeID

fn out_degree(&self, n: NodeID) -> usize

fn target(&self, e: EdgeID) -> NodeID

fn data(&self, e: EdgeID) -> &T

fn data_mut(&mut self, e: EdgeID) -> &mut T

fn find_edge(&self, s: NodeID, t: NodeID) -> Option<EdgeID>

fn find_edge_unchecked(&self, s: NodeID, t: NodeID) -> EdgeID