unobtanium-graph-algorithms 0.1.0

// SPDX-FileCopyrightText: 2025 Slatian 2025
//
// SPDX-License-Identifier: LGPL-3.0-only

use crate::PageRankConfiguration;
use crate::graph::Graph;
use crate::graph::ranked_nodes::RankedNodes;
use crate::node::NodeId;

use core::hash::Hash;

// Based on the textrank algorithm of the keyword_extraction crate:
// https://github.com/tugascript/keyword-extraction-rs/blob/master/src/text_rank/text_rank_logic.rs

/// PageRank and TextRank related graph functionality
impl<T: Eq + Hash + Clone> Graph<T> {
	/// Add tokens to graph, use a window in which all tokens will be connected with each other using bidirectional connections. Use this if you want to use textrank for keyword extraction.
	///
	/// Since textrank is just pagerank you can use the `run_pagerank()` function to get the results.
	pub fn populate_for_textrank(&mut self, tokens: &[T], window_size: usize) {
		let edges = tokens.iter().enumerate().flat_map(|(i, from)| {
			tokens[i + 1..]
				.iter()
				.take(window_size)
				.filter(move |to| &from != to)
				.map(move |to| (from, to))
		});
		self.modify(|mut graph| {
			for (from, to) in edges {
				let from_id = graph.fetch_id_for_data(from);
				let to_id = graph.fetch_id_for_data(to);
				graph.add_edge(from_id, to_id);
				graph.add_edge(to_id, from_id);
			}
		});
	}

	/// Runs the textrank algorithm on the graph and returns a HashMap mapping node values to the resulting scores.
	pub fn run_pagerank(&self, config: &PageRankConfiguration) -> RankedNodes<'_, T> {
		//TODO: Add a max_iterations value here to prevent too long loops.
		//      This is likely processing untrusted data.

		// TODO: Add the "bored surfer" part to mitigate score sinks.

		let mut scores = vec![1.0_f32; self.nodes_length];

		loop {
			let prev_scores = scores.to_owned();
			let max_diff;
			(scores, max_diff) = self.iterate_pagerank_once(&prev_scores, config.damping);

			if max_diff < config.tolerance {
				break;
			}
		}

		RankedNodes {
			graph: self,
			scores,
		}
	}

	/// Perform one pagerank/textrank iteration
	fn iterate_pagerank_once(&self, prev_scores: &[f32], damping: f32) -> (Vec<f32>, f32) {
		let mut new_scores = Vec::with_capacity(prev_scores.len());
		let mut max_diff = 0.0_f32;
		for (i, incoming_edges) in self.graph.iter().enumerate() {
			let new_score = self.pagerank_score_node(incoming_edges, prev_scores, damping);
			let diff = (prev_scores[i] - new_score).abs();
			if diff > max_diff {
				max_diff = diff;
			}
			new_scores.push(new_score);
		}
		(new_scores, max_diff)
	}

	/// computes the new score for one node by **pulling in** the values from its edges.
	fn pagerank_score_node(
		&self,
		incoming_edges: &[(NodeId, f32)],
		prev_scores: &[f32],
		damping: f32,
	) -> f32 {
		let new_score = incoming_edges
			.iter()
			.map(|(from, weight)| {
				let from_outgoing_sum = self.outgoing_weight_sums[from.0];
				// The `R(v) / N_v` part of the original pagerank equation, times weight
				(prev_scores[from.0] / from_outgoing_sum) * weight
			})
			.sum::<f32>();

		(1.0 - damping) + damping * new_score
	}
}