trustchain_core/
graph.rs

1//! Graph API for constructing networks from `DIDChain`.
2use crate::chain::{Chain, DIDChain};
3use crate::display::PrettyDID;
4use petgraph::dot::{Config, Dot};
5use petgraph::graph::DiGraph;
6use std::collections::HashMap;
7use std::fmt::Display;
8use thiserror::Error;
9
10/// An error relating to Trustchain graphs.
11#[derive(Error, Debug, PartialEq, Eq, PartialOrd, Ord)]
12pub enum GraphError {
13    /// Constructed graph contains a cycle.
14    #[error("Graph contains a cycle.")]
15    ContainsCycle,
16}
17
18/// Wrapper struct for a petgraph DiGraph of documents.
19#[derive(Debug)]
20pub struct TrustchainGraph {
21    graph: DiGraph<String, String>,
22}
23
24/// Read chains from a vector and return a DiGraph, a subtype of a petgraph [Graph](https://docs.rs/petgraph/latest/petgraph/graph/struct.Graph.html).
25fn read_chains(chains: &Vec<DIDChain>, label_width: usize) -> DiGraph<String, String> {
26    let mut nodes = HashMap::<String, petgraph::prelude::NodeIndex>::new();
27    let mut graph = DiGraph::<String, String>::new();
28    for chain in chains {
29        let mut did = chain.root().to_owned();
30        let mut level = 0;
31        // Add source
32        match nodes.get(&did) {
33            Some(_) => (),
34            None => {
35                let pretty_did = PrettyDID::new(&chain.data(&did).unwrap().0, level, label_width)
36                    .to_node_string();
37                let ns = graph.add_node(pretty_did);
38                nodes.insert(did.to_owned(), ns);
39            }
40        }
41        while let Some(ddid) = chain.downstream(&did) {
42            // Get source node
43            let ns = match nodes.get(&did) {
44                Some(&v) => v,
45                None => panic!(),
46            };
47            // Add or retrieve target
48            let nt = match nodes.get(ddid) {
49                Some(&v) => v,
50                None => {
51                    let pretty_ddid =
52                        PrettyDID::new(&chain.data(ddid).unwrap().0, level + 1, label_width)
53                            .to_node_string();
54                    let nt = graph.add_node(pretty_ddid);
55                    nodes.insert(ddid.to_owned(), nt);
56                    nt
57                }
58            };
59            // Add edge if not in graph
60            if !graph.contains_edge(ns, nt) {
61                graph.extend_with_edges([(ns, nt, "".to_string())]);
62            }
63
64            // Update did
65            ddid.clone_into(&mut did);
66            level += 1;
67        }
68    }
69    graph
70}
71
72impl TrustchainGraph {
73    /// Makes a new TrustchainGraph instance.
74    pub fn new(chains: &Vec<DIDChain>, label_width: usize) -> Result<Self, GraphError> {
75        let graph = read_chains(chains, label_width);
76        if !petgraph::algo::is_cyclic_directed(&graph) {
77            Ok(Self { graph })
78        } else {
79            Err(GraphError::ContainsCycle)
80        }
81    }
82
83    /// Outputs graph to graphviz format.
84    pub fn to_dot(&self) -> String {
85        // Output the tree to `graphviz` `DOT` format
86        format!("{}", Dot::with_config(&self.graph, &[Config::EdgeNoLabel]))
87    }
88}
89
90impl Display for TrustchainGraph {
91    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
92        writeln!(f, "{}", self.to_dot())?;
93        Ok(())
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100    use crate::data::{TEST_DID_CHAIN, TEST_DID_CHAIN_REVERSED};
101
102    const DEFAULT_LABEL_WIDTH: usize = 30;
103
104    fn test_chain() -> DIDChain {
105        serde_json::from_str(TEST_DID_CHAIN).unwrap()
106    }
107    fn test_chain_reversed() -> DIDChain {
108        serde_json::from_str(TEST_DID_CHAIN_REVERSED).unwrap()
109    }
110
111    #[test]
112    fn test_read_chains() -> Result<(), GraphError> {
113        let chains = vec![test_chain(), test_chain()];
114        let graph = TrustchainGraph::new(&chains, DEFAULT_LABEL_WIDTH);
115        assert!(graph.is_ok());
116        if let Ok(graph) = graph {
117            assert_eq!(graph.graph.node_count(), 3);
118            assert_eq!(graph.graph.edge_count(), 2);
119        }
120        Ok(())
121    }
122    #[test]
123    fn test_read_chains_with_cycle() {
124        let chains = vec![test_chain(), test_chain_reversed()];
125        let graph = TrustchainGraph::new(&chains, DEFAULT_LABEL_WIDTH);
126        assert!(matches!(graph, Err(GraphError::ContainsCycle)));
127    }
128    #[test]
129    fn test_to_dot() -> Result<(), GraphError> {
130        let chains = vec![test_chain(), test_chain()];
131        let graph = TrustchainGraph::new(&chains, DEFAULT_LABEL_WIDTH)?;
132        graph.to_dot();
133        Ok(())
134    }
135    #[test]
136    fn test_display() -> Result<(), GraphError> {
137        let chains = vec![test_chain(), test_chain()];
138        let graph = TrustchainGraph::new(&chains, DEFAULT_LABEL_WIDTH)?;
139        let _ = format!("{}", graph);
140        Ok(())
141    }
142}
trustchain_core/graph.rs

trustchain_core/
graph.rs
