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
//! Submodule providing the traits for a generic graph that has weighted edges.
use super::{
Edges, TransposedEdges, TransposedMonoplexGraph, WeightedEdges, WeightedMonoplexGraph,
};
use crate::traits::{SparseValuedMatrix2D, ValuedSizedSparseBiMatrix2D};
/// Trait defining an edge data structure that has weighted edges.
pub trait TransposedWeightedEdges:
TransposedEdges<BiMatrix = <Self as TransposedWeightedEdges>::WeightedBiMatrix>
+ WeightedEdges<WeightedMatrix = <Self as TransposedWeightedEdges>::WeightedBiMatrix>
{
/// The type of the underlying matrix.
type WeightedBiMatrix: ValuedSizedSparseBiMatrix2D<
Value = <Self as WeightedEdges>::Weight,
RowIndex = Self::SourceNodeId,
ColumnIndex = Self::DestinationNodeId,
SparseIndex = Self::EdgeId,
>;
/// Returns the weights of the predecessors of a node.
///
/// # Arguments
///
/// * `destination_node_id`: The node identifier.
///
/// # Returns
///
/// The weights of the predecessors of the node.
#[inline]
fn predecessor_weights(
&self,
destination_node_id: Self::DestinationNodeId,
) -> <<Self::WeightedBiMatrix as ValuedSizedSparseBiMatrix2D>::ValuedSparseTransposedMatrix as SparseValuedMatrix2D>::SparseRowValues<'_>{
self.matrix().sparse_column_values(destination_node_id)
}
/// Returns the largest weight of the predecessors of a node.
///
/// # Arguments
///
/// * `destination_node_id`: The node identifier.
///
/// # Returns
///
/// The largest weight of the predecessors of the node, if any.
#[inline]
fn max_predecessor_weight(
&self,
destination_node_id: Self::DestinationNodeId,
) -> Option<Self::Weight>
where
Self::Weight: crate::traits::total_ord::TotalOrd,
{
self.matrix().sparse_column_max_value(destination_node_id)
}
/// Returns the smallest weight of the predecessors of a node.
///
/// # Arguments
///
/// * `destination_node_id`: The node identifier.
///
/// # Returns
///
/// The smallest weight of the predecessors of the node, if any.
#[inline]
fn min_predecessor_weight(
&self,
destination_node_id: Self::DestinationNodeId,
) -> Option<Self::Weight>
where
Self::Weight: crate::traits::total_ord::TotalOrd,
{
self.matrix().sparse_column_min_value(destination_node_id)
}
}
impl<E> TransposedWeightedEdges for E
where
E: WeightedEdges,
E::WeightedMatrix: ValuedSizedSparseBiMatrix2D<
RowIndex = E::SourceNodeId,
ColumnIndex = E::DestinationNodeId,
SparseIndex = E::EdgeId,
Value = E::Weight,
>,
{
type WeightedBiMatrix = E::WeightedMatrix;
}
/// Trait defining a graph that has weighted edges with transposed access.
///
/// This trait combines `TransposedMonoplexGraph` and `WeightedMonoplexGraph`,
/// requiring that the edges support both transposed access and weighted values.
pub trait TransposedWeightedMonoplexGraph:
TransposedMonoplexGraph<TransposedEdges = Self::TransposedWeightedEdges>
+ WeightedMonoplexGraph<WeightedEdges = Self::TransposedWeightedEdges>
{
/// The type of the weighted edges with transposed access.
type TransposedWeightedEdges: TransposedWeightedEdges<
Weight = <Self as WeightedMonoplexGraph>::Weight,
>;
/// Returns the weights of the predecessors of a node.
///
/// # Arguments
///
/// * `destination_node_id`: The node identifier.
///
/// # Returns
///
/// The weights of the predecessors of the node.
#[inline]
fn predecessor_weights(
&self,
destination_node_id: <Self::TransposedWeightedEdges as Edges>::DestinationNodeId,
) -> <<<Self::TransposedWeightedEdges as TransposedWeightedEdges>::WeightedBiMatrix as ValuedSizedSparseBiMatrix2D>::ValuedSparseTransposedMatrix as SparseValuedMatrix2D>::SparseRowValues<'_>{
self.edges().predecessor_weights(destination_node_id)
}
/// Returns the largest weight of the predecessors of a node.
///
/// # Arguments
///
/// * `destination_node_id`: The node identifier.
///
/// # Returns
///
/// The largest weight of the predecessors of the node, if any.
#[inline]
fn max_predecessor_weight(
&self,
destination_node_id: <Self::TransposedWeightedEdges as Edges>::DestinationNodeId,
) -> Option<Self::Weight>
where
Self::Weight: crate::traits::total_ord::TotalOrd,
{
self.edges().max_predecessor_weight(destination_node_id)
}
/// Returns the smallest weight of the predecessors of a node.
///
/// # Arguments
///
/// * `destination_node_id`: The node identifier.
///
/// # Returns
///
/// The smallest weight of the predecessors of the node, if any.
#[inline]
fn min_predecessor_weight(
&self,
destination_node_id: <Self::TransposedWeightedEdges as Edges>::DestinationNodeId,
) -> Option<Self::Weight>
where
Self::Weight: crate::traits::total_ord::TotalOrd,
{
self.edges().min_predecessor_weight(destination_node_id)
}
}
impl<G> TransposedWeightedMonoplexGraph for G
where
G: TransposedMonoplexGraph<TransposedEdges = <G as WeightedMonoplexGraph>::WeightedEdges>
+ WeightedMonoplexGraph,
G::WeightedEdges: TransposedWeightedEdges,
{
type TransposedWeightedEdges = G::WeightedEdges;
}