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
//! Trait defining a data structure to handle Edges, such as a simple edge list,
//! or a ragged list or a compressed sparse row matrix.
use num_traits::{AsPrimitive, SaturatingAdd, Zero};
use super::{AttributedEdge, Edge, EdgeType, TypedEdge};
use crate::traits::{
MatrixMut, PositiveInteger, SizedRowsSparseMatrix2D, SizedSparseMatrix, SparseMatrix,
SparseMatrix2D, SparseMatrixMut, TryFromUsize,
};
/// Trait defining a data structure to handle Edges, such as a simple edge list,
/// or a ragged list or a compressed sparse row matrix.
pub trait Edges {
/// The type of the edge.
type Edge: Edge<SourceNodeId = Self::SourceNodeId, DestinationNodeId = Self::DestinationNodeId>;
/// The type of the source node ID.
type SourceNodeId: PositiveInteger + AsPrimitive<usize> + TryFromUsize + SaturatingAdd;
/// The type of the destination node ID.
type DestinationNodeId: PositiveInteger + AsPrimitive<usize> + TryFromUsize + SaturatingAdd;
/// The type of the edge identifier.
type EdgeId: PositiveInteger + AsPrimitive<usize> + TryFromUsize + SaturatingAdd;
/// The underlying matrix type.
type Matrix: SizedRowsSparseMatrix2D<
RowIndex = Self::SourceNodeId,
ColumnIndex = Self::DestinationNodeId,
SparseIndex = Self::EdgeId,
>;
/// Returns a reference to the underlying matrix.
fn matrix(&self) -> &Self::Matrix;
/// Returns the number of edges.
#[inline]
fn number_of_edges(&self) -> Self::EdgeId {
self.matrix().number_of_defined_values()
}
/// Returns whether the graph has any edges.
#[inline]
fn has_edges(&self) -> bool {
!self.matrix().is_empty()
}
/// Returns the successors of the node with the given identifier.
///
/// # Arguments
///
/// * `source` - The identifier of the source node.
#[inline]
fn successors(
&self,
source: Self::SourceNodeId,
) -> <Self::Matrix as SparseMatrix2D>::SparseRow<'_> {
self.matrix().sparse_row(source)
}
/// Returns whether the given source has that successor.
///
/// # Arguments
///
/// * `source` - The identifier of the source node.
/// * `destination` - The identifier of the destination node.
#[inline]
fn has_successor(
&self,
source: Self::SourceNodeId,
destination: Self::DestinationNodeId,
) -> bool {
self.matrix().has_entry(source, destination)
}
/// Returns whether the given source node has successors.
///
/// # Arguments
///
/// * `source` - The identifier of the source node.
#[inline]
fn has_successors(&self, source: Self::SourceNodeId) -> bool {
self.out_degree(source) > Self::DestinationNodeId::zero()
}
/// Returns the outbound degree of the node with the given identifier.
///
/// # Arguments
///
/// * `source` - The identifier of the source node.
#[inline]
fn out_degree(&self, source: Self::SourceNodeId) -> Self::DestinationNodeId {
self.matrix().number_of_defined_values_in_row(source)
}
/// Returns an iterator over the out degrees of the nodes.
#[inline]
fn out_degrees(&self) -> <Self::Matrix as SizedRowsSparseMatrix2D>::SparseRowSizes<'_> {
self.matrix().sparse_row_sizes()
}
/// Returns the iterator of the edges.
#[inline]
fn sparse_coordinates(&self) -> <Self::Matrix as SparseMatrix>::SparseCoordinates<'_> {
self.matrix().sparse_coordinates()
}
}
/// Trait defining a data structure that handles typed edges.
pub trait TypedEdges: Edges
where
Self::Edge: TypedEdge + AttributedEdge,
<Self::Edge as AttributedEdge>::Attribute: EdgeType,
{
}
impl<E> TypedEdges for E
where
E: Edges,
E::Edge: TypedEdge + AttributedEdge,
<E::Edge as AttributedEdge>::Attribute: EdgeType,
{
}
/// Trait defining a data structure to handle edges that can grow dynamically.
pub trait GrowableEdges: Edges<Matrix = <Self as GrowableEdges>::GrowableMatrix> + Default {
/// The type of the growable matrix.
type GrowableMatrix: SparseMatrixMut<Entry = Self::Edge> + SparseMatrix2D;
/// The error that may be returned when adding an edge.
type Error: core::error::Error + From<<Self::GrowableMatrix as MatrixMut>::Error>;
/// Creates a new growable edges representation with the provided graph
/// shape.
///
/// # Arguments
///
/// * `shape` - The shape of the graph.
/// * `number_of_edges` - The number of edges.
fn with_shaped_capacity(
shape: <Self::GrowableMatrix as SparseMatrixMut>::MinimalShape,
number_of_edges: Self::EdgeId,
) -> Self;
/// Creates a new growable edges representation with the provided graph
/// shape.
///
/// # Arguments
///
/// * `shape` - The shape of the graph.
fn with_shape(shape: <Self::GrowableMatrix as SparseMatrixMut>::MinimalShape) -> Self;
/// Creates a new growable edges representation with the provided graph
/// shape.
///
/// # Arguments
///
/// * `number_of_edges` - The number of edges.
fn with_capacity(number_of_edges: Self::EdgeId) -> Self;
/// Returns a mutable reference to the underlying matrix.
fn matrix_mut(&mut self) -> &mut Self::GrowableMatrix;
/// Adds an edge to the graph.
///
/// # Arguments
///
/// * `edge` - The edge to add.
///
/// # Errors
///
/// Returns an error if the entry cannot be added. Possible reasons include:
/// - The entries are not provided in the expected order.
/// - The entry is out of bounds.
/// - The entry is already defined.
#[inline]
fn add(&mut self, edge: Self::Edge) -> Result<(), Self::Error> {
Ok(self.matrix_mut().add(edge)?)
}
}