unobtanium_graph_algorithms/graph/
ranked_nodes.rs

1// SPDX-FileCopyrightText: 2025 Slatian 2025
2//
3// SPDX-License-Identifier: LGPL-3.0-only
4
5use core::hash::Hash;
6use std::collections::HashMap;
7use std::iter::FusedIterator;
8
9use crate::graph::Graph;
10use crate::node::NodeId;
11
12/// Holds the result of a ranking algorithm that was run on a [Graph].
13pub struct RankedNodes<'a, T: Eq + Hash + Clone> {
14	pub(crate) graph: &'a Graph<T>,
15	pub(crate) scores: Vec<f32>,
16}
17
18/// Unsorted iterator over the [RankedNodes] structure.
19pub struct UnsortedRankedNodesIter<'a, T: Eq + Hash + Clone> {
20	inner: &'a RankedNodes<'a, T>,
21	index: usize,
22}
23
24/// Iterator sorted by best score first over the elements in a [RankedNodes] structure.
25pub struct SortedRankedNodesIter<'a, T: Eq + Hash + Clone> {
26	inner: &'a RankedNodes<'a, T>,
27	sorted_node_ids: Vec<(NodeId, f32)>,
28	index: usize,
29}
30
31impl<'a, T: Eq + Hash + Clone> RankedNodes<'a, T> {
32	/// Returns a hash map that maps node data to the resulting score
33	pub fn hash_map(&self) -> HashMap<T, f32> {
34		self.unsorted_iter()
35			.map(|(data, score)| (data.clone(), score))
36			.collect()
37	}
38
39	/// Returns an unsorted iterator over all nodes and their scores `(&data, score)`.
40	///
41	/// This is useful for building maps and filtering by data aspects before sorting.
42	pub fn unsorted_iter(&'a self) -> UnsortedRankedNodesIter<'a, T> {
43		UnsortedRankedNodesIter {
44			inner: self,
45			index: 0,
46		}
47	}
48
49	/// Returns a sorted iterator over all nodes and their scores `(&data, score)`.
50	///
51	/// The highest scores are sorted first.
52	///
53	/// This is useful for getting the top *n* results of the ranking.
54	pub fn sorted_iter(&'a self) -> SortedRankedNodesIter<'a, T> {
55		let mut sorted_list: Vec<(NodeId, f32)> = self
56			.scores
57			.iter()
58			.enumerate()
59			.filter(|(_, score)| !score.is_nan())
60			.map(|(n, score)| (NodeId(n), *score))
61			.collect();
62		sorted_list.sort_by(|(_, a), (_, b)| b.partial_cmp(a).unwrap());
63		SortedRankedNodesIter {
64			inner: self,
65			sorted_node_ids: sorted_list,
66			index: 0,
67		}
68	}
69
70	/// Convenience function to look the score of a single data point
71	///
72	/// This is useful if one only needs the scores for a few specific data points.
73	pub fn get_score_for(&self, data: &T) -> Option<f32> {
74		let node = self.graph.nodes.get2(data)?;
75		self.scores.get(node.id.0).copied()
76	}
77
78	/// Returns the number of scores in this result set.
79	///
80	/// This is usually the number of nodes in the graph.
81	pub fn len(&self) -> usize {
82		self.scores.len()
83	}
84
85	/// Wheter the result set is empty.
86	pub fn is_empty(&self) -> bool {
87		self.scores.is_empty()
88	}
89}
90
91impl<'a, T: Eq + Hash + Clone> Iterator for UnsortedRankedNodesIter<'a, T> {
92	type Item = (&'a T, f32);
93
94	fn next(&mut self) -> Option<Self::Item> {
95		self.inner.scores.get(self.index).map(|score| {
96			let data = &self
97				.inner
98				.graph
99				.nodes
100				.get1(&NodeId(self.index))
101				.unwrap()
102				.data;
103			self.index += 1;
104			(data, *score)
105		})
106	}
107}
108
109impl<T: Eq + Hash + Clone> FusedIterator for UnsortedRankedNodesIter<'_, T> {}
110
111impl<'a, T: Eq + Hash + Clone> Iterator for SortedRankedNodesIter<'a, T> {
112	type Item = (&'a T, f32);
113
114	fn next(&mut self) -> Option<Self::Item> {
115		self.sorted_node_ids
116			.get(self.index)
117			.map(|(node_id, score)| {
118				let data = &self.inner.graph.nodes.get1(node_id).unwrap().data;
119				self.index += 1;
120				(data, *score)
121			})
122	}
123}
124
125impl<T: Eq + Hash + Clone> FusedIterator for SortedRankedNodesIter<'_, T> {}
unobtanium_graph_algorithms/graph/ranked_nodes.rs

unobtanium_graph_algorithms/graph/
ranked_nodes.rs
