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