Struct FrozenGraph

pub struct FrozenGraph<N, E, NI, EI, NM, EM>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{ /* private fields */ }

A Graph with immutable structure.

You can not add/remove nodes/edges from a FrozenGraph, but you can still mutate their weights in case you have a mutable reference to the graph.

Graph is effectively a smart pointer into a FrozenGraph so the conversion is free.

Implementations

impl<N, E, NI, EI, NM, EM> FrozenGraph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static, EI: Copy + Eq + Debug + 'static, NM: Map<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,

pub fn node(&self, index: NI) -> Option<&Node<N, EI>>

Returns an immutable reference to a node by its index or None if the index is invalid.

pub fn node_mut(&mut self, index: NI) -> Option<&mut Node<N, EI>>

Returns a mutable reference to a node by its index or None if the index is invalid.

pub fn nodes_count(&self) -> usize

Returns the current amount of nodes in the graph.

pub fn node_weight(&self, index: NI) -> Option<&N>

Returns an immutable reference to the weight of a node by its index or None in case the index is not valid.

Example

let mut graph = SlotMapGraph::<i32, ()>::default();

let node = graph.add_node(1);
assert_eq!(graph.node_weight(node), Some(&1));

pub fn node_weight_mut(&mut self, index: NI) -> Option<&mut N>

Returns a mutable reference to the weight of a node by its index or None in case the index is not valid.

Example

let mut graph = SlotMapGraph::<i32, ()>::default();

let node = graph.add_node(1);
let weight_mut = graph.node_weight_mut(node).unwrap();
assert_eq!(*weight_mut, 1);

*weight_mut = 2;
assert_eq!(graph.node_weight(node), Some(&2));

pub fn edge(&self, index: EI) -> Option<&Edge<E, NI, EI>>

Returns an immutable reference to an edge by its index or None if the index is invalid.

pub fn edge_mut(&mut self, index: EI) -> Option<&mut Edge<E, NI, EI>>

Returns a mutable reference to an edge by its index or None if the index is invalid.

pub fn edges_count(&self) -> usize

Returns the current amount of edges in the graph.

pub fn edge_weight(&self, index: EI) -> Option<&E>

Returns an immutable reference to the weight of a node by its index or None in case the index is not valid.

Example

let mut graph = SlotMapGraph::<i32, i32>::default();

let from = graph.add_node(1234);
let to = graph.add_node(1234);
let edge = graph.add_edge(4567, from, to).unwrap();

assert_eq!(graph.edge_weight(edge), Some(&4567));

Panics

This function will panic if the provided edge index is not valid.

pub fn edge_weight_mut(&mut self, index: EI) -> Option<&mut E>

Returns a mutable reference to the weight of an edge by its index.

Panics

This function will panic if the provided edge index is not valid.

pub fn as_nodes_mut_and_edges( &mut self, ) -> (&mut Nodes<N, EI, NM>, &Edges<E, NI, EI, EM>)

Given a mutable reference to a graph returns a mutable reference to its Nodes and an immutable reference to its Edges.

This is useful for parallel processing of a graph when its necessary to both mutate nodes and walk over edges.

pub fn as_nodes_and_edges_mut( &mut self, ) -> (&Nodes<N, EI, NM>, &mut Edges<E, NI, EI, EM>)

Given a mutable reference to a graph returns an immutable reference to its Nodes and a mutable reference to its Edges.

This is useful for parallel processing of a graph when its necessary to both mutate edges and walk over nodes.

pub fn as_nodes_mut_and_edges_mut( &mut self, ) -> (&mut Nodes<N, EI, NM>, &mut Edges<E, NI, EI, EM>)

Given a mutable reference to a graph returns a mutable reference to its Nodes and a mutable reference to its Edges.

This is useful for parallel processing of a graph when its necessary to mutably process both nodes and edges in parallel somehow.

pub fn find_edge( &self, from: NI, to: NI, ) -> Result<Option<EI>, InvalidEdgeError>

Finds an edge from one node to another and returns its index.

Example

let mut graph = SlotMapGraph::<i32, ()>::default();

let first = graph.add_node(1);
let second = graph.add_node(2);
let edge = graph.add_edge((), first, second).unwrap();

assert_eq!(graph.find_edge(first, second).unwrap(), Some(edge));

Errors

This function will return an InvalidEdgeError error in case either the source or the destination index is not valid which will be indicated by the error’s value.

pub fn find_node<F: FnMut(&N) -> bool>(&self, f: F) -> Option<NI>

Calls the given closure on each node in the index growth order passing the node’s weight as a parameter until the closure returns true. Returns the index of the node for which the closure returned true or None in case there was no such node.

Example

let mut graph = SlotMapGraph::<bool, ()>::default();
let false_idx = graph.add_node(false);
let true_idx = graph.add_node(true);

assert_eq!(graph.find_node(|v| *v), Some(true_idx));
assert_eq!(graph.find_node(|v| !*v), Some(false_idx));

pub fn node_weights(&self) -> NodeWeights<'_, N, NI, EI, NM>

Returns an immutable iterator over the weights of nodes in a graph.

Order of iteration

The order of iteration is specified by the iterator type provided by the node map in its Map implementation as the Map::Iter associated type.

pub fn node_weights_mut(&mut self) -> NodeWeightsMut<'_, N, NI, EI, NM>

Returns a mutable iterator over the weights of nodes in a graph.

Order of iteration

The order of iteration is specified by the iterator type provided by the node map in its Map implementation as the Map::IterMut associated type.

pub fn edge_weights(&self) -> EdgeWeights<'_, E, NI, EI, EM>

Returns an immutable iterator over the weights of edges in a graph.

Order of iteration

The order of iteration is specified by the iterator type provided by the edge map in its Map implementation as the Map::Iter associated type.

pub fn edge_weights_mut(&mut self) -> EdgeWeightsMut<'_, E, NI, EI, EM>

Returns a mutable iterator over the weights of edges in a graph.

Order of iteration

The order of iteration is specified by the iterator type provided by the edge map in its Map implementation as the Map::IterMut associated type.

pub fn outputs(&self, node_index: NI) -> Outputs<'_, E, NI, EI, EM>

Returns an iterator over the outputs of a node.

Example

let mut graph = SlotMapGraph::<i32, i32>::default();

let entry = graph.add_node(1);
let (left, left_ei) = graph.add_connected_node(2, entry, 22).unwrap();
let (right, right_ei) = graph.add_connected_node(3, entry, 33).unwrap();

// make a map for expected edge weights
let mut map = HashMap::new();
map.insert(left_ei, 22);
map.insert(right_ei, 33);

// check that they match what we get from the iterator
for (ei, edge) in graph.outputs(entry) {
    assert_eq!(map.remove(&ei), Some(*edge.weight()));
}

assert!(map.is_empty());

pub fn inputs(&self, node_index: NI) -> Inputs<'_, E, NI, EI, EM>

Returns an iterator over the inputs of a node.

Example

let mut graph = SlotMapGraph::<i32, i32>::default();

let left = graph.add_node(1);
let right = graph.add_node(2);
let exit = graph.add_node(3);
let left_ei = graph.add_edge(11, left, exit).unwrap();
let right_ei = graph.add_edge(22, right, exit).unwrap();

// make a map for expected edge weights
let mut map = HashMap::new();
map.insert(left_ei, 11);
map.insert(right_ei, 22);

// check that they match what we get from the iterator
for (ei, edge) in graph.inputs(exit) {
    assert_eq!(map.remove(&ei), Some(*edge.weight()));
}

assert!(map.is_empty());

pub fn successors(&self, node_index: NI) -> Successors<'_, N, E, NI, EI, NM, EM>

Returns an iterator over successors of a node.

Example

let mut graph = SlotMapGraph::<i32, ()>::default();

let entry = graph.add_node(1);
let (left, left_ei) = graph.add_connected_node(2, entry, ()).unwrap();
let (right, right_ei) = graph.add_connected_node(3, entry, ()).unwrap();

// make a map for expected edge weights
let mut map = HashMap::new();
map.insert(left, 2);
map.insert(right, 3);

// check that they match what we get from the iterator
for (ni, weight) in graph.successors(entry) {
    assert_eq!(map.remove(&ni), Some(*weight));
}

assert!(map.is_empty());

pub fn predecessors( &self, node_index: NI, ) -> Predecessors<'_, N, E, NI, EI, NM, EM>

Returns an iterator over predecessors of a node.

Example

let mut graph = SlotMapGraph::<i32, ()>::default();

let left = graph.add_node(1);
let right = graph.add_node(2);
let exit = graph.add_node(3);
let left_ei = graph.add_edge((), left, exit).unwrap();
let right_ei = graph.add_edge((), right, exit).unwrap();

// make a map for expected edge weights
let mut map = HashMap::new();
map.insert(left, 1);
map.insert(right, 2);

// check that they match what we get from the iterator
for (ni, weight) in graph.predecessors(exit) {
    assert_eq!(map.remove(&ni), Some(*weight));
}

assert!(map.is_empty());

pub fn walk_successors(&self, node_index: NI) -> WalkSuccessors<EI>

Returns a walker over the successors of a node.

pub fn walk_predecessors(&self, node_index: NI) -> WalkPredecessors<EI>

Returns a walker over the predecessors of a node.

pub fn walk_inputs(&self, node_index: NI) -> WalkInputs<EI>

Returns a walker over the inputs of a node.

pub fn walk_outputs(&self, node_index: NI) -> WalkOutputs<EI>

Returns a walker over the outputs of a node.

pub fn unfreeze(self) -> Graph<N, E, NI, EI, NM, EM>

Converts a FrozenGraph into a Graph.

impl<N, E, NI, EI, NM, EM> FrozenGraph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Ord + Debug + 'static, EI: Copy + Eq + Debug + 'static, NM: OrderedKeyMap<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,

pub fn nodes_range<R: RangeBounds<NI>>( &self, range: R, ) -> impl DoubleEndedIterator<Item = (NI, &N)>

Returns an immutable iterator over nodes with indices that fall into the specified range.

Order of iteration

The order the nodes are returned in depends on the range iterator type provided by the node map in its OrderedKeyMap implementation as the OrderedKeyMap::Range associated type.

pub fn nodes_range_mut<R: RangeBounds<NI>>( &mut self, range: R, ) -> impl DoubleEndedIterator<Item = (NI, &mut N)>

Returns a mutable iterator over nodes with indices that fall into the specified range.

Example

let mut graph = BTreeSlotMapGraph::<i32, (), i32>::default();

graph.try_add_node_at_index(1, 111).unwrap();
graph.try_add_node_at_index(2, 222).unwrap();
graph.try_add_node_at_index(3, 333).unwrap();

let mut iter = graph.nodes_range_mut(2..=3);

let (index, value) = iter.next().unwrap();
assert_eq!(index, 2);
assert_eq!(mem::replace(value, 223), 222);

let (index, value) = iter.next().unwrap();
assert_eq!(index, 3);
assert_eq!(mem::replace(value, 334), 333);

assert!(iter.next().is_none());

drop(iter);

assert_eq!(*graph.node_weight(1).unwrap(), 111);
assert_eq!(*graph.node_weight(2).unwrap(), 223);
assert_eq!(*graph.node_weight(3).unwrap(), 334);

Order of iteration

The order the nodes are returned in depends on the range iterator type provided by the node map in its OrderedKeyMap implementation as the OrderedKeyMap::RangeMut associated type.

pub fn first_node(&self) -> Option<(NI, &N)>

Returns the index and an immutable reference to the weight of the first node in the graph.

Order of nodes

What node is first is defined by the underlying node map by its implementation of the OrderedKeyMap::first method.

pub fn first_node_mut(&mut self) -> Option<(NI, &mut N)>

Returns the index and a mutable reference to the weight of the first node in the graph.

Order of nodes

What node is first is defined by the underlying node map by its implementation of the OrderedKeyMap::first_mut method.

pub fn last_node(&self) -> Option<(NI, &N)>

Returns the index and an immutable reference to the weight of the first node in the graph.

Order of nodes

What node is last is defined by the underlying node map by its implementation of the OrderedKeyMap::last method.

pub fn last_node_mut(&mut self) -> Option<(NI, &mut N)>

Returns the index and a mutable reference to the weight of the first node in the graph.

Order of nodes

What node is last is defined by the underlying node map by its implementation of the OrderedKeyMap::last_mut method.

impl<N, E, NI, EI, NM, EM> FrozenGraph<N, E, NI, EI, NM, EM>

where N: Send + Sync, NI: Copy + Eq + Ord + Send + Sync + Debug + 'static, EI: Copy + Eq + Debug + 'static, NM: ParIterMap<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,

pub fn par_iter_nodes(&self) -> NM::ParIter<'_>

Available on crate feature rayon only.

Returns an immutable parallel iterator over the graph’s nodes.

pub fn par_iter_nodes_mut(&mut self) -> NM::ParIterMut<'_>

Available on crate feature rayon only.

Returns a mutable parallel iterator over the graph’s nodes.

pub fn par_iter_node_weights( &self, ) -> Map<NM::ParIter<'_>, for<'a> fn((NI, &'a Node<N, EI>)) -> (NI, &'a N)>

Available on crate feature rayon only.

Returns an immutable parallel iterator over the graph’s nodes’ weights.

pub fn par_iter_node_weights_mut( &mut self, ) -> Map<NM::ParIterMut<'_>, for<'a> fn((NI, &'a mut Node<N, EI>)) -> (NI, &'a mut N)>

Available on crate feature rayon only.

Returns a mutable parallel iterator over the graph’s nodes’ weights.

impl<N, E, NI, EI, NM, EM> FrozenGraph<N, E, NI, EI, NM, EM>

where E: Send + Sync, NI: Copy + Eq + Ord + Send + Sync + Debug + 'static, EI: Copy + Eq + Send + Sync + Debug + 'static, NM: Map<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + ParIterMap<Edge<E, NI, EI>, Key = EI>,

pub fn par_iter_edges(&self) -> EM::ParIter<'_>

Available on crate feature rayon only.

Returns an immutable parallel iterator over the graph’s edges.

pub fn par_iter_edges_mut(&mut self) -> EM::ParIterMut<'_>

Available on crate feature rayon only.

Returns a mutable parallel iterator over the graph’s edges.

pub fn par_iter_edge_weights( &self, ) -> ParMap<EM::ParIter<'_>, for<'a> fn((EI, &'a Edge<E, NI, EI>)) -> (EI, &'a E)>

Available on crate feature rayon only.

Returns an immutable parallel iterator over the graph’s edges’ weights.

pub fn par_iter_edge_weights_mut( &mut self, ) -> ParMap<EM::ParIterMut<'_>, for<'a> fn((EI, &'a mut Edge<E, NI, EI>)) -> (EI, &'a mut E)>

Available on crate feature rayon only.

Returns a mutable parallel iterator over the graph’s edges’ weights.

Trait Implementations

impl<N, E, NI, EI, NM, EM> AsMut<FrozenGraph<N, E, NI, EI, NM, EM>> for Graph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static, EI: Copy + Eq + Debug + 'static, NM: Map<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,

fn as_mut(&mut self) -> &mut FrozenGraph<N, E, NI, EI, NM, EM>

Converts this type into a mutable reference of the (usually inferred) input type.

impl<N, E, NI, EI, NM, EM> AsRef<FrozenGraph<N, E, NI, EI, NM, EM>> for Graph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static, EI: Copy + Eq + Debug + 'static, NM: Map<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,

fn as_ref(&self) -> &FrozenGraph<N, E, NI, EI, NM, EM>

Converts this type into a shared reference of the (usually inferred) input type.

impl<N, E, NI, EI, NM, EM> Borrow<FrozenGraph<N, E, NI, EI, NM, EM>> for Graph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static, EI: Copy + Eq + Debug + 'static, NM: Map<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,

fn borrow(&self) -> &FrozenGraph<N, E, NI, EI, NM, EM>

Immutably borrows from an owned value.

impl<N, E, NI, EI, NM, EM> BorrowMut<FrozenGraph<N, E, NI, EI, NM, EM>> for Graph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static, EI: Copy + Eq + Debug + 'static, NM: Map<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,

fn borrow_mut(&mut self) -> &mut FrozenGraph<N, E, NI, EI, NM, EM>

Mutably borrows from an owned value.

impl<N: Clone, E: Clone, NI, EI, NM, EM> Clone for FrozenGraph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static + Clone, EI: Copy + Eq + Debug + 'static + Clone, NM: Map<Node<N, EI>, Key = NI> + Clone, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + Clone,

fn clone(&self) -> FrozenGraph<N, E, NI, EI, NM, EM>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<N: Debug, E: Debug, NI, EI, NM, EM> Debug for FrozenGraph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static + Debug, EI: Copy + Eq + Debug + 'static + Debug, NM: Map<Node<N, EI>, Key = NI> + Debug, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + Debug,

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

Formats the value using the given formatter.

impl<N, E, NI, EI, NM, EM> Default for FrozenGraph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static, EI: Copy + Eq + Debug + 'static, NM: Map<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,

fn default() -> Self

Returns the “default value” for a type.

impl<'de, N, E, NI, EI, NM, EM> Deserialize<'de> for FrozenGraph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static + Deserialize<'de>, EI: Copy + Eq + Debug + 'static + Deserialize<'de>, NM: Map<Node<N, EI>, Key = NI> + Deserialize<'de>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + Deserialize<'de>, N: Deserialize<'de>, E: Deserialize<'de>,

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<N, E, NI, EI, NM, EM> From<FrozenGraph<N, E, NI, EI, NM, EM>> for Graph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static, EI: Copy + Eq + Debug + 'static, NM: Map<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,

fn from(value: FrozenGraph<N, E, NI, EI, NM, EM>) -> Self

Converts to this type from the input type.

impl<N, E, NI, EI, NM, EM> From<Graph<N, E, NI, EI, NM, EM>> for FrozenGraph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static, EI: Copy + Eq + Debug + 'static, NM: Map<Node<N, EI>, Key = NI>, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,

fn from(value: Graph<N, E, NI, EI, NM, EM>) -> Self

Converts to this type from the input type.

impl<N, E, NI, EI, NM, EM> Serialize for FrozenGraph<N, E, NI, EI, NM, EM>

where NI: Copy + Eq + Debug + 'static + Serialize, EI: Copy + Eq + Debug + 'static + Serialize, NM: Map<Node<N, EI>, Key = NI> + Serialize, EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + Serialize, N: Serialize, E: Serialize,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.