Skip to content

Commit 9d66175

Browse files
authored
Address more clippy lints (#449)
* Add clippy config with MSRV * Allow float comparision with 0 We don't need to use an epsilon as the 0 values are always assigned directly from a constant. * Use &self method receiver where possible The trait_template! macro does not support that, so I added explicit ignores to clippy's warning. * Custom bellman_fords output struct The previous type was overly complex and not too intuitive. * Address type complexity lints In most cases I think the type is Ok as-is, so I added an ignore * Address remaining clippy lints The needless_range_loop in floid_warshall looks more intuitive using the explicit range, hence I ignored the lint.
1 parent ec1b5bc commit 9d66175

13 files changed

Lines changed: 40 additions & 15 deletions

File tree

‎clippy.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
msrv = "1.41.0"

‎src/adj.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -573,7 +573,7 @@ impl<E, Ix: IndexType> EdgeCount for List<E, Ix> {
573573
/// Returns the number of edges in the list
574574
///
575575
/// Computes in **O(|V|)** time.
576-
fn edge_count(self: &Self) -> usize {
576+
fn edge_count(&self) -> usize {
577577
List::edge_count(self)
578578
}
579579
}

‎src/algo/bellman_ford.rs‎

Lines changed: 18 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,12 @@ use crate::visit::{IntoEdges, IntoNodeIdentifiers, NodeCount, NodeIndexable, Vis
66

77
use super::{FloatMeasure, NegativeCycle};
88

9+
#[derive(Debug, Clone)]
10+
pub struct Paths<NodeId, EdgeWeight> {
11+
pub distances: Vec<EdgeWeight>,
12+
pub predecessors: Vec<Option<NodeId>>,
13+
}
14+
915
/// \[Generic\] Compute shortest paths from node `source` to all other.
1016
///
1117
/// Using the [Bellman–Ford algorithm][bf]; negative edge costs are
@@ -51,10 +57,11 @@ use super::{FloatMeasure, NegativeCycle};
5157
/// // \------ e ------/
5258
///
5359
/// let path = bellman_ford(&g, a);
54-
/// assert_eq!(path, Ok((vec![0.0 , 2.0, 3.0, 4.0, 5.0, 6.0],
55-
/// vec![None, Some(a),Some(b),Some(a), Some(d), Some(e)]
56-
/// ))
57-
/// );
60+
/// assert!(path.is_ok());
61+
/// let path = path.unwrap();
62+
/// assert_eq!(path.distances, vec![ 0.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
63+
/// assert_eq!(path.predecessors, vec![None, Some(a),Some(b),Some(a), Some(d), Some(e)]);
64+
///
5865
/// // Node f (indice 5) can be reach from a with a path costing 6.
5966
/// // Predecessor of f is Some(e) which predecessor is Some(d) which predecessor is Some(a).
6067
/// // Thus the path from a to f is a <-> d <-> e <-> f
@@ -74,28 +81,31 @@ use super::{FloatMeasure, NegativeCycle};
7481
pub fn bellman_ford<G>(
7582
g: G,
7683
source: G::NodeId,
77-
) -> Result<(Vec<G::EdgeWeight>, Vec<Option<G::NodeId>>), NegativeCycle>
84+
) -> Result<Paths<G::NodeId, G::EdgeWeight>, NegativeCycle>
7885
where
7986
G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable,
8087
G::EdgeWeight: FloatMeasure,
8188
{
8289
let ix = |i| g.to_index(i);
8390

8491
// Step 1 and Step 2: initialize and relax
85-
let (distance, predecessor) = bellman_ford_initialize_relax(g, source);
92+
let (distances, predecessors) = bellman_ford_initialize_relax(g, source);
8693

8794
// Step 3: check for negative weight cycle
8895
for i in g.node_identifiers() {
8996
for edge in g.edges(i) {
9097
let j = edge.target();
9198
let w = *edge.weight();
92-
if distance[ix(i)] + w < distance[ix(j)] {
99+
if distances[ix(i)] + w < distances[ix(j)] {
93100
return Err(NegativeCycle(()));
94101
}
95102
}
96103
}
97104

98-
Ok((distance, predecessor))
105+
Ok(Paths {
106+
distances,
107+
predecessors,
108+
})
99109
}
100110

101111
/// \[Generic\] Find the path of a negative cycle reachable from node `source`.

‎src/algo/dominators.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -272,10 +272,12 @@ where
272272
.collect()
273273
}
274274

275+
type PredecessorSets<NodeId> = HashMap<NodeId, HashSet<NodeId>>;
276+
275277
fn simple_fast_post_order<G>(
276278
graph: G,
277279
root: G::NodeId,
278-
) -> (Vec<G::NodeId>, HashMap<G::NodeId, HashSet<G::NodeId>>)
280+
) -> (Vec<G::NodeId>, PredecessorSets<G::NodeId>)
279281
where
280282
G: IntoNeighbors + Visitable,
281283
<G as GraphBase>::NodeId: Eq + Hash,

‎src/algo/floyd_warshall.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@ use std::hash::Hash;
55
use crate::algo::{BoundedMeasure, NegativeCycle};
66
use crate::visit::{EdgeRef, IntoEdgeReferences, IntoNodeIdentifiers, NodeCompactIndexable};
77

8+
#[allow(clippy::type_complexity, clippy::needless_range_loop)]
89
/// \[Generic\] [Floyd–Warshall algorithm](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) is an algorithm for all pairs shortest path problem
910
///
1011
/// Compute shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles)

‎src/algo/matching.rs‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -107,7 +107,7 @@ trait WithDummy: NodeIndexable {
107107
fn dummy_idx(&self) -> usize;
108108
fn node_bound_with_dummy(&self) -> usize;
109109
/// Convert `i` to a node index, returns None for the dummy node
110-
fn try_from_index(self: &Self, i: usize) -> Option<Self::NodeId>;
110+
fn try_from_index(&self, i: usize) -> Option<Self::NodeId>;
111111
}
112112

113113
impl<G: NodeIndexable> WithDummy for G {
@@ -122,7 +122,7 @@ impl<G: NodeIndexable> WithDummy for G {
122122
self.node_bound() + 1
123123
}
124124

125-
fn try_from_index(self: &Self, i: usize) -> Option<Self::NodeId> {
125+
fn try_from_index(&self, i: usize) -> Option<Self::NodeId> {
126126
if i != self.dummy_idx() {
127127
Some(self.from_index(i))
128128
} else {
@@ -592,7 +592,6 @@ fn augment_path<G>(
592592
if mate[temp_idx] != Some(outer) {
593593
// We are at the end of the path and so the entire path is completely
594594
// rematched/augmented.
595-
return;
596595
} else if let Label::Vertex(vertex) = label[outer_idx] {
597596
// The outer vertex has a vertex label which refers to another outer
598597
// vertex on the path. So we set this another outer node as the mate for

‎src/algo/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -684,6 +684,7 @@ where
684684
graph: G,
685685
node_ids: Option<G::NodeReferences>,
686686
subgraphs: UnionFind<usize>,
687+
#[allow(clippy::type_complexity)]
687688
sort_edges: BinaryHeap<MinScored<G::EdgeWeight, (G::NodeId, G::NodeId)>>,
688689
node_map: HashMap<usize, usize>,
689690
node_count: usize,

‎src/csr.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -986,8 +986,8 @@ mod tests {
986986
let result = bellman_ford(&m, 0).unwrap();
987987
println!("{:?}", result);
988988
let answer = [0., 0.5, 1.5, 1.5];
989-
assert_eq!(&answer, &result.0[..4]);
990-
assert!(answer[4..].iter().all(|&x| f64::is_infinite(x)));
989+
assert_eq!(&answer, &result.distances[..4]);
990+
assert!(result.distances[4..].iter().all(|&x| f64::is_infinite(x)));
991991
}
992992

993993
#[test]

‎src/data.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@ use crate::Graph;
1111

1212
trait_template! {
1313
/// Access node and edge weights (associated data).
14+
#[allow(clippy::needless_arbitrary_self_type)]
1415
pub trait DataMap : Data {
1516
@section self
1617
fn node_weight(self: &Self, id: Self::NodeId) -> Option<&Self::NodeWeight>;
@@ -30,6 +31,7 @@ DataMap! {delegate_impl [[G], G, Reversed<G>, access0]}
3031

3132
trait_template! {
3233
/// Access node and edge weights mutably.
34+
#[allow(clippy::needless_arbitrary_self_type)]
3335
pub trait DataMapMut : DataMap {
3436
@section self
3537
fn node_weight_mut(self: &mut Self, id: Self::NodeId) -> Option<&mut Self::NodeWeight>;

‎src/graph_impl/frozen.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,7 @@ where
5252
Ty: EdgeType,
5353
Ix: IndexType,
5454
{
55+
#[allow(clippy::type_complexity)]
5556
/// Index the `Graph` by two indices, any combination of
5657
/// node or edge indices is fine.
5758
///

0 commit comments

Comments
 (0)