wolf_graph/traits/
visitable_graph.rs

1use std::borrow::Cow;
2
3use anyhow::Result;
4
5use crate::{EdgeID, Edges, Elements, NodeID, Nodes};
6
7pub trait VisitableGraph {
8    type GData;
9    type NData: Clone;
10    type EData: Clone;
11
12    /// Returns a reference to the graph's data.
13    fn data(&self) -> &Self::GData;
14    /// Returns a reference to the node's data.
15    fn node_data(&self, id: impl AsRef<NodeID>) -> Result<Cow<'static, Self::NData>>;
16    /// Returns a reference to the edge's data.
17    fn edge_data(&self, id: impl AsRef<EdgeID>) -> Result<Cow<'static, Self::EData>>;
18
19    /// Returns `true` if the graph is empty.
20    fn is_empty(&self) -> bool;
21    /// Returns the number of nodes in the graph.
22    fn node_count(&self) -> usize;
23    /// Returns the number of edges in the graph.
24    fn edge_count(&self) -> usize;
25
26    /// Returns a set of all nodes in the graph.
27    fn all_nodes(&self) -> Nodes;
28    /// Returns a set of all edges in the graph.
29    fn all_edges(&self) -> Edges;
30
31    /// Returns the set of all elements in the graph.
32    fn elements(&self) -> Elements {
33        Elements::new(self.all_nodes(), self.all_edges())
34    }
35
36    /// Returns `true` if the graph contains the given node.
37    fn has_node(&self, id: impl AsRef<NodeID>) -> bool;
38    /// Returns `true` if the graph contains the given edge.
39    fn has_edge(&self, id: impl AsRef<EdgeID>) -> bool;
40    /// Returns `true` if the graph contains an edge from `source` to `target`.
41    fn has_edge_from_to(&self, source: impl AsRef<NodeID>, target: impl AsRef<NodeID>) -> bool;
42    /// Returns `true` if the graph contains an edge between `a` and `b`,
43    /// regardless of direction.
44    fn has_edge_between(&self, a: impl AsRef<NodeID>, b: impl AsRef<NodeID>) -> bool;
45
46    /// Returns the edges that have the given source and target nodes.
47    ///
48    /// Only returns more than one edge in the case of codirected edges.
49    fn edges_from_to(&self, source: impl AsRef<NodeID>, target: impl AsRef<NodeID>) -> Result<Edges> {
50        Ok(self.out_edges(source)?
51            .into_iter()
52            .filter(|edge| self.target(edge).map(|id| &id == target.as_ref()).unwrap_or(false))
53            .collect())
54    }
55
56    /// Returns the edges that have the given nodes as endpoints.
57    ///
58    /// Only returns more than one edge in the case of parallel edges.
59    fn edges_between(&self, a: impl AsRef<NodeID>, b: impl AsRef<NodeID>) -> Result<Edges> {
60        let a = a.as_ref();
61        let b = b.as_ref();
62        let mut edges = self.edges_from_to(a, b)?;
63        edges.extend(self.edges_from_to(b, a)?);
64        Ok(edges)
65    }
66
67    /// Returns the edges connecting the given source nodes to the given target nodes.
68    fn edges_from_to_nodes(&self, sources: &Nodes, targets: &Nodes) -> Result<Edges> {
69        let mut edges = Edges::new();
70
71        for source in sources.iter() {
72            for target in targets.iter() {
73                edges.extend(self.edges_from_to(source, target)?);
74            }
75        }
76
77        Ok(edges)
78    }
79
80    /// Returns the edges connecting the given sets of nodes.
81    fn edges_between_nodes(&self, a: &Nodes, b: &Nodes) -> Result<Edges> {
82        let mut edges = self.edges_from_to_nodes(a, b)?;
83        edges.extend(self.edges_from_to_nodes(b, a)?);
84        Ok(edges)
85    }
86
87    /// Returns the source node of the edge.
88    fn source(&self, id: impl AsRef<EdgeID>) -> Result<NodeID>;
89    /// Returns the target node of the edge.
90    fn target(&self, id: impl AsRef<EdgeID>) -> Result<NodeID>;
91    /// Returns the endpoints of the edge.
92    fn endpoints(&self, id: impl AsRef<EdgeID>) -> Result<(NodeID, NodeID)>;
93
94    /// Returns the out-edges of the node.
95    fn out_edges(&self, id: impl AsRef<NodeID>) -> Result<Edges>;
96    /// Returns the in-edges of the node.
97    fn in_edges(&self, id: impl AsRef<NodeID>) -> Result<Edges>;
98    /// Returns the incident edges of the node.
99    fn incident_edges(&self, id: impl AsRef<NodeID>) -> Result<Edges>;
100
101    /// Returns the number of out-edges of the node.
102    fn out_degree(&self, id: impl AsRef<NodeID>) -> Result<usize>;
103    /// Returns the number of in-edges of the node.
104    fn in_degree(&self, id: impl AsRef<NodeID>) -> Result<usize>;
105    /// Returns the number of incident edges of the node.
106    fn degree(&self, id: impl AsRef<NodeID>) -> Result<usize>;
107
108    /// Returns the immediate successors of the node.
109    fn successors(&self, id: impl AsRef<NodeID>) -> Result<Nodes>;
110    /// Returns the immediate predecessors of the node.
111    fn predecessors(&self, id: impl AsRef<NodeID>) -> Result<Nodes>;
112    /// Returns the immediate neighbors of the node.
113    fn neighbors(&self, id: impl AsRef<NodeID>) -> Result<Nodes>;
114
115    /// Returns `true` if the node has successors.
116    fn has_successors(&self, id: impl AsRef<NodeID>) -> Result<bool>;
117    /// Returns `true` if the node has predecessors.
118    fn has_predecessors(&self, id: impl AsRef<NodeID>) -> Result<bool>;
119    /// Returns `true` if the node has neighbors.
120    fn has_neighbors(&self, id: impl AsRef<NodeID>) -> Result<bool>;
121
122    /// Returns the immediate successors of all the given nodes.
123    fn nodes_successors(&self, ids: &Nodes) -> Result<Nodes> {
124        let mut result = Nodes::new();
125
126        for id in ids.iter() {
127            let successors = self.successors(id)?;
128            for successor in successors.iter() {
129                result.insert(successor.clone());
130            }
131        }
132
133        Ok(result)
134    }
135
136    /// Returns the immediate predecessors of all the given nodes.
137    fn nodes_predecessors(&self, ids: &Nodes) -> Result<Nodes> {
138        let mut result = Nodes::new();
139
140        for id in ids.iter() {
141            let predecessors = self.predecessors(id)?;
142            for predecessor in predecessors.iter() {
143                result.insert(predecessor.clone());
144            }
145        }
146
147        Ok(result)
148    }
149
150    /// Returns the transitive successors of all the given nodes (i.e., all the
151    /// nodes reachable from the out-edges of the given nodes).
152    ///
153    /// The given nodes will not be included unless they are also reachable from
154    /// the out-edges of other nodes.
155    fn transitive_successors(&self, ids: &Nodes) -> Result<Nodes> {
156        let mut result = Nodes::new();
157
158        let mut ids = ids.clone();
159        while !ids.is_empty() {
160            let next_nodes = self.nodes_successors(&ids)?;
161
162            if next_nodes.is_empty() {
163                break;
164            }
165
166            let mut new_next = false;
167            for node in next_nodes.iter() {
168                if !result.contains(node) {
169                    result.insert(node.clone());
170                    new_next = true;
171                }
172            }
173
174            if !new_next {
175                break;
176            }
177
178            ids = next_nodes;
179        }
180
181        Ok(result)
182    }
183
184    /// Returns the transitive predecessors of all the given nodes (i.e., all
185    /// the nodes reachable from the in-edges of the given nodes).
186    ///
187    /// The given nodes will not be included unless they are also reachable from
188    /// the in-edges of other nodes.
189    fn transitive_predecessors(&self, ids: &Nodes) -> Result<Nodes> {
190        let mut result = Nodes::new();
191
192        let mut ids = ids.clone();
193        while !ids.is_empty() {
194            let next_nodes = self.nodes_predecessors(&ids)?;
195
196            if next_nodes.is_empty() {
197                break;
198            }
199
200            let mut new_next = false;
201            for node in next_nodes.iter() {
202                if !result.contains(node) {
203                    result.insert(node.clone());
204                    new_next = true;
205                }
206            }
207
208            if !new_next {
209                break;
210            }
211
212            ids = next_nodes;
213        }
214
215        Ok(result)
216    }
217
218    /// The set of all "roots" (nodes with no predecessors) in the graph.
219    fn all_roots(&self) -> Nodes;
220    /// The set of all "leaves" (nodes with no successors) in the graph.
221    fn all_leaves(&self) -> Nodes;
222
223    /// The set of all nodes that are not roots (i.e., nodes with at least one predecessor).
224    fn non_roots(&self) -> Nodes;
225    /// The set of all nodes that are not leaves (i.e., nodes with at least one successor).
226    fn non_leaves(&self) -> Nodes;
227
228    /// The set of all nodes that are neither roots nor leaves (i.e., nodes with
229    /// at least one predecessor and at least one successor).
230    fn all_internals(&self) -> Nodes;
231
232    /// Returns `true` if the node is a leaf (i.e., has no successors).
233    fn is_leaf(&self, id: impl AsRef<NodeID>) -> Result<bool>;
234    /// Returns `true` if the node is a root (i.e., has no predecessors).
235    fn is_root(&self, id: impl AsRef<NodeID>) -> Result<bool>;
236    /// Returns `true` if the node is neither a root nor a leaf (i.e., has at
237    /// least one predecessor and at least one successor).
238    fn is_internal(&self, id: impl AsRef<NodeID>) -> Result<bool>;
239}
wolf_graph/traits/visitable_graph.rs

wolf_graph/traits/
visitable_graph.rs
