Struct Graph 

pub struct Graph<K, V>(/* private fields */)
where
    K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug,
    V: PartialEq + Clone + Debug;

This struct contains all functionality implemented in this module. It is can be used for building and sorting a graph of causally connected nodes.

Sorting is deterministic with > comparison of contained node data being the deciding factor on which paths to walk first.

Example

use p2panda_rs::graph::{Graph, Reducer};
use p2panda_rs::graph::error::ReducerError;

// First we define a reducer we will use later on.

#[derive(Default)]
struct CharReducer {
    acc: String,
}

impl Reducer<char> for CharReducer {
    type Error = ReducerError;

    fn combine(&mut self, value: &char) -> Result<(), Self::Error> {
        self.acc = format!("{}{}", self.acc, value);
        Ok(())
    }
}

// Instantiate the graph.

let mut graph = Graph::new();

// Add some nodes to the graph.

graph.add_node(&'a', 'A');
graph.add_node(&'b', 'B');
graph.add_node(&'c', 'C');

assert!(graph.get_node(&'a').is_some());
assert!(graph.get_node(&'x').is_none());

// Add some links between the nodes.

graph.add_link(&'a', &'b');
graph.add_link(&'a', &'c');

// The graph looks like this:
//
//  /--[B]
// [A]<--[C]

// We can sort it topologically and pass in our reducer.

let mut reducer = CharReducer::default();
let nodes = graph.reduce(&mut reducer)?;

assert_eq!(nodes.sorted(), vec!['A', 'B', 'C']);
assert_eq!(reducer.acc, "ABC".to_string());

// Add another link which creates a cycle (oh dear!).

graph.add_link(&'b', &'a');

let mut reducer = CharReducer::default();
assert!(graph.reduce(&mut reducer).is_err());

Implementations

impl<'a, K, V> Graph<K, V>

where K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug, V: PartialEq + Clone + Debug,

pub fn new() -> Self

Instantiate a new empty graph.

pub fn add_node(&mut self, key: &K, data: V)

Add a node to the graph. This node will be detached until it is linked to another node.

pub fn add_link(&mut self, from: &K, to: &K) -> bool

Add a link between existing nodes to the graph. Returns true if the link was added. Returns false if the link was unable to be added. This happens if either of the nodes were not present in the graph, or if the link creates a single node loop.

pub fn get_node(&'a self, key: &K) -> Option<&Node<K, V>>

Get node from the graph by key, returns None if it wasn’t found.

pub fn root_node(&self) -> Result<&Node<K, V>, GraphError>

Returns a reference to the root node of this graph.

pub fn root_node_key(&self) -> Result<&K, GraphError>

Returns the root node key.

pub fn trim(&'a mut self, tip_nodes: &[K]) -> Result<Graph<K, V>, GraphError>

Returns a new graph instance which has had all nodes removed which aren’t causally linked to the passed nodes.

Data contained in the returned nodes is unchanged, but the nodes’ next arrays are edited to reflect the new graph connections. The returned graph can be sorted in order to arrive at a linear ordering of nodes.

pub fn walk_from( &'a self, key: &K, reducer: &mut impl Reducer<V>, ) -> Result<GraphData<V>, GraphError>

Sorts the graph topologically and returns the result.

pub fn reduce( &'a self, reducer: &mut impl Reducer<V>, ) -> Result<GraphData<V>, GraphError>

Sort the entire graph, starting from the root node.

Accepts a mutable reducer as an argument. As each node is sorted into topological order its value is passed into the combine method.

Trait Implementations

impl<K, V> Clone for Graph<K, V>

where K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug + Clone, V: PartialEq + Clone + Debug + Clone,

fn clone(&self) -> Graph<K, V>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K, V> Debug for Graph<K, V>

where K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug + Debug, V: PartialEq + Clone + Debug + Debug,

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

Formats the value using the given formatter.

impl<K, V> Default for Graph<K, V>

where K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug, V: PartialEq + Clone + Debug,

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> PartialEq for Graph<K, V>

where K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug + PartialEq, V: PartialEq + Clone + Debug + PartialEq,

fn eq(&self, other: &Graph<K, V>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K, V> Eq for Graph<K, V>

where K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug + Eq, V: PartialEq + Clone + Debug + Eq,

impl<K, V> StructuralPartialEq for Graph<K, V>

where K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug, V: PartialEq + Clone + Debug,