spdx_toolkit/
graph.rs

1// SPDX-FileCopyrightText: 2021 HH Partners
2//
3// SPDX-License-Identifier: MIT
4
5use std::collections::HashMap;
6
7use petgraph::{algo::astar, graphmap::DiGraphMap, EdgeDirection};
8
9use spdx_rs::models::{RelationshipType, SPDX};
10
11use crate::error::Error;
12
13pub fn create_graph(spdx: &SPDX) -> DiGraphMap<&str, &RelationshipType> {
14    let mut g = DiGraphMap::<&str, &RelationshipType>::new();
15    let mut nodes: HashMap<&str, &str> = HashMap::new();
16    for relationship in &spdx.relationships {
17        let a = *nodes
18            .entry(&relationship.spdx_element_id)
19            .or_insert_with(|| g.add_node(&relationship.spdx_element_id));
20        let b = *nodes
21            .entry(&relationship.related_spdx_element)
22            .or_insert_with(|| g.add_node(&relationship.related_spdx_element));
23        g.add_edge(a, b, &relationship.relationship_type);
24    }
25    g
26}
27
28pub fn find_path<'a>(
29    graph: &'a DiGraphMap<&'a str, &'a RelationshipType>,
30    start: &'a str,
31    end: &'a str,
32) -> Option<(i32, Vec<&'a str>)> {
33    astar(graph, start, |goal| end == goal, |_| 1, |_| 0)
34}
35
36/// # Errors
37///
38/// - If finding edges fails.
39pub fn path_with_relationships<'a>(
40    graph: &'a DiGraphMap<&'a str, &'a RelationshipType>,
41    path: Vec<&'a str>,
42) -> Result<Vec<&'a str>, Error> {
43    let mut path_with_relationships: Vec<&str> = Vec::new();
44    for spdx_id in path {
45        if !path_with_relationships.is_empty() {
46            let edge = graph
47                .edges_directed(
48                    path_with_relationships
49                        .last()
50                        .ok_or_else(|| Error::Graph("no edge found".to_string()))?,
51                    EdgeDirection::Outgoing,
52                )
53                .find(|edge| edge.1 == spdx_id)
54                .ok_or_else(|| Error::Graph("no edge found".to_string()))?;
55
56            path_with_relationships.push(edge.2.as_ref());
57        }
58        path_with_relationships.push(spdx_id);
59    }
60    Ok(path_with_relationships)
61}
62
63#[cfg(test)]
64mod test {
65    use std::fs::read_to_string;
66
67    use petgraph::dot::Dot;
68
69    use super::*;
70
71    #[test]
72    fn create_graph_succeeds() {
73        let spdx: SPDX =
74            serde_json::from_str(&read_to_string("tests/data/SPDXForGraph.spdx.json").unwrap())
75                .unwrap();
76        let graph = create_graph(&spdx);
77        let dot = Dot::new(&graph);
78        dbg!(dot);
79    }
80
81    #[test]
82    fn create_complex_graph_succeeds() {
83        let spdx: SPDX = serde_json::from_str(
84            &read_to_string("tests/data/SPDXJSONExample-v2.2.spdx.json").unwrap(),
85        )
86        .unwrap();
87        let graph = create_graph(&spdx);
88        let dot = Dot::new(&graph);
89        dbg!(dot);
90    }
91
92    #[test]
93    fn find_path_works() {
94        let spdx: SPDX = serde_json::from_str(
95            &read_to_string("tests/data/SPDXJSONExample-v2.2.spdx.json").unwrap(),
96        )
97        .unwrap();
98        let graph = create_graph(&spdx);
99        let path = find_path(&graph, "SPDXRef-DOCUMENT", "SPDXRef-Saxon").unwrap();
100        dbg!(path);
101    }
102
103    #[test]
104    fn find_complex_path_works() {
105        let spdx: SPDX =
106            serde_json::from_str(&read_to_string("tests/data/SPDXForGraph.spdx.json").unwrap())
107                .unwrap();
108        let graph = create_graph(&spdx);
109        let path = find_path(&graph, "SPDXRef-Package-1", "SPDXRef-File-1").unwrap();
110        dbg!(path);
111    }
112
113    #[test]
114    fn find_path_with_relationships_works() {
115        let spdx: SPDX = serde_json::from_str(
116            &read_to_string("tests/data/SPDXJSONExample-v2.2.spdx.json").unwrap(),
117        )
118        .unwrap();
119        let graph = create_graph(&spdx);
120        let path = find_path(&graph, "SPDXRef-DOCUMENT", "SPDXRef-Saxon").unwrap();
121        let path = path_with_relationships(&graph, path.1).unwrap();
122        dbg!(path);
123    }
124
125    #[test]
126    fn find_complex_path_with_relationships_works() {
127        let spdx: SPDX =
128            serde_json::from_str(&read_to_string("tests/data/SPDXForGraph.spdx.json").unwrap())
129                .unwrap();
130        let graph = create_graph(&spdx);
131        let path = find_path(&graph, "SPDXRef-Package-1", "SPDXRef-File-1").unwrap();
132        let path = path_with_relationships(&graph, path.1).unwrap();
133        dbg!(path);
134    }
135}
spdx_toolkit/graph.rs

spdx_toolkit/
graph.rs
