algae_graph/
lib.rs

1/*
2    Appellation: graphs <library>
3    Contrib: FL03 <jo3mccain@icloud.com>
4    Description: This library is dedicated to graphs, explicitly implementing generic directed and undirected data-structures while providing the tools to create new ones.
5*/
6pub use self::{cmp::*, directed::*, errors::*, specs::*, undirected::*};
7
8pub(crate) mod cmp;
9pub(crate) mod directed;
10mod errors;
11mod specs;
12pub(crate) mod undirected;
13
14pub mod graph;
15pub mod search;
16pub mod store;
17
18use errors::GraphError;
19use std::{collections::HashSet, ops::IndexMut};
20use store::AdjacencyTable;
21
22/// [Graph] describes the basic operations of a graph data-structure
23pub trait Graph<N = String, V = i64>:
24    Clone + Contain<N> + Contain<Edge<N, V>> + IndexMut<N, Output = Vec<(N, V)>>
25where
26    N: Node,
27    V: Weight,
28{
29    /// [Graph::add_edge] inserts a new [Edge] into the graph
30    fn add_edge(&mut self, edge: Edge<N, V>) {
31        let pair = edge.pair();
32        self.add_node(pair.0.clone());
33        self.add_node(pair.1.clone());
34
35        self.store_mut().entry(pair.0.clone()).and_modify(|e| {
36            e.push((pair.1, edge.value().clone()));
37        });
38    }
39    /// [Graph::add_edges] insert several edges into the graph
40    fn add_edges(&mut self, iter: impl IntoIterator<Item = Edge<N, V>>) {
41        for i in iter {
42            self.add_edge(i)
43        }
44    }
45    /// [Graph::add_node] if the given [Node] is not already in the [Graph], insert the [Node] and return true; else return false
46    fn add_node(&mut self, node: N) -> bool {
47        match self.store().get(&node) {
48            None => {
49                self.store_mut().insert(node, Vec::new());
50                true
51            }
52            _ => false,
53        }
54    }
55    /// [Graph::add_nodes] insert several nodes into the graph
56    fn add_nodes(&mut self, iter: impl IntoIterator<Item = N>) {
57        for i in iter {
58            self.add_node(i);
59        }
60    }
61    /// [Graph::contains_edge] returns true if the given [Edge] is in the graph
62    fn contains_edge(&self, edge: &Edge<N, V>) -> bool {
63        match self.store().get(&edge.pair().0) {
64            Some(edges) => edges.contains(&(edge.pair().1, edge.value().clone())),
65            None => false,
66        }
67    }
68    /// [Graph::contains_node] returns true if the given [Node] is in the graph
69    fn contains_node(&self, node: &N) -> bool {
70        self.store().contains_key(node)
71    }
72    /// [Graph::degree] returns the degree of the given [Node]
73    fn degree(&self, node: &N) -> Result<usize, GraphError> {
74        match self.store().get(node) {
75            Some(edges) => Ok(edges.len()),
76            None => Err(GraphError::NodeNotInGraph),
77        }
78    }
79    /// [Graph::edges] returns all of the edges persisting within the graph
80    fn edges(&self) -> Vec<Edge<N, V>> {
81        let mut edges = Vec::new();
82        for (from_node, from_node_neighbours) in self.store().clone() {
83            for (to_node, weight) in from_node_neighbours {
84                edges.push((from_node.clone(), to_node, weight).into());
85            }
86        }
87        edges
88    }
89    /// [Graph::edges_from] returns all of the edges originating from the given [Node]
90    fn edges_from(&self, node: &N) -> Result<Vec<Edge<N, V>>, GraphError> {
91        match self.store().get(node) {
92            Some(edges) => Ok(edges
93                .iter()
94                .cloned()
95                .map(|(n, v)| Edge::new(node.clone(), n, v))
96                .collect()),
97            None => Err(GraphError::NodeNotInGraph),
98        }
99    }
100    /// [Graph::edges_to] returns all of the edges terminating at the given [Node]
101    fn edges_to(&self, node: &N) -> Result<Vec<Edge<N, V>>, GraphError> {
102        let mut edges = Vec::new();
103        for (origin, neighbours) in self.store().clone() {
104            for (dest, weight) in neighbours {
105                if &dest == node {
106                    edges.push((origin.clone(), dest, weight).into());
107                }
108            }
109        }
110        Ok(edges)
111    }
112    /// [Graph::is_connected] returns true if the graph is connected
113    fn is_connected(&self) -> bool {
114        let mut visited = HashSet::new();
115        let mut stack = self.nodes().iter().cloned().collect::<Vec<_>>();
116
117        while let Some(node) = stack.pop() {
118            if !visited.contains(&node) {
119                visited.insert(node.clone());
120                stack.extend(
121                    self.neighbors(node)
122                        .unwrap()
123                        .iter()
124                        .map(|(n, _)| n)
125                        .cloned(),
126                );
127            }
128        }
129
130        visited.len() == self.nodes().len()
131    }
132    /// [Graph::store_mut] returns an owned, mutable instance of the [AdjacencyTable]
133    fn store_mut(&mut self) -> &mut AdjacencyTable<N, V>;
134    /// [Graph::store] returns an owned instance of the [AdjacencyTable]
135    fn store(&self) -> &AdjacencyTable<N, V>;
136    /// [Graph::neighbors] attempts to return a [Vec] that contains all of the connected [Node] and their values
137    fn neighbors(&self, node: N) -> Result<&Vec<(N, V)>, GraphError> {
138        if self.nodes().contains(&node) {
139            Ok(&self[node])
140        } else {
141            Err(GraphError::NodeNotInGraph)
142        }
143    }
144    /// [Graph::nodes] returns a cloned [HashSet] of the graph's current [Node]s
145    fn nodes(&self) -> HashSet<N> {
146        self.store().keys().cloned().collect()
147    }
148}
149
150pub trait GraphExt<N = String, V = i64>: Graph<N, V>
151where
152    N: Node,
153    V: Weight,
154{
155}
156
157pub trait Subgraph<N = String, V = i64>: Graph<N, V>
158where
159    N: Node,
160    V: Weight,
161{
162    fn is_subgraph(&self, graph: impl Graph<N, V>) -> bool {
163        self.nodes().is_subset(&graph.nodes())
164    }
165}
algae_graph/lib.rs

algae_graph/
lib.rs
