unobtanium-graph-algorithms 0.1.0

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

use iddqd::BiHashMap;

use core::hash::Hash;

mod branded;
mod pagerank;
pub mod ranked_nodes;

use crate::node::Node;
use crate::node::NodeId;

pub use branded::BrandedNodeId;
pub use branded::MutableGraph;

/// Datastructure to run graph algorithms on.
pub struct Graph<T: Eq + Hash + Clone> {
	/// Maps each node to its incoming edges with weights
	/// `to ("node"), (from, score) ("edge")`
	graph: Vec<Vec<(NodeId, f32)>>,

	/// Maps each node to the sum of its outgoing edge weights
	outgoing_weight_sums: Vec<f32>,

	/// Maps between actual node content and node ids
	nodes: BiHashMap<Node<T>>,

	/// Number of nodes and
	/// the next node id to be assigned.
	nodes_length: usize,
}

impl<T: Eq + Hash + Clone> Default for Graph<T> {
	fn default() -> Self {
		Self {
			graph: Default::default(),
			outgoing_weight_sums: Default::default(),
			nodes: BiHashMap::new(),
			nodes_length: 0,
		}
	}
}

impl<T: Eq + Hash + Clone> Graph<T> {
	/// Construct a new, empty graph
	pub fn new() -> Self {
		Default::default()
	}

	fn get_node_data_for_id(&self, id: NodeId) -> Option<&T> {
		Some(&self.nodes.get1(&id)?.data)
	}

	fn fetch_id_for_data(&mut self, data: &T) -> NodeId {
		if let Some(node) = self.nodes.get2(&data) {
			return node.id;
		}
		let new_id = self.nodes_length;
		self.nodes_length += 1;
		self.outgoing_weight_sums.push(0.0);
		self.graph.push(Vec::with_capacity(4));
		self.nodes.insert_overwrite(Node {
			id: NodeId(new_id),
			data: data.clone(),
		});
		NodeId(new_id)
	}

	#[inline(always)]
	fn add_edge_weighted(&mut self, from: NodeId, to: NodeId, weight: f32) {
		let incoming_edges = self.graph
			.get_mut(to.0)
			.unwrap();
		let mut found = false;
		for (id, e) in &mut *incoming_edges {
			if *id == from {
				*e += weight;
				found = true;
				break;
			}
		}
		if !found {
			incoming_edges.push((from, weight))
		}
		*self.outgoing_weight_sums.get_mut(from.0).unwrap() += weight;
	}

	/// Constructs a modifiable versions of this graph and passes it to `callback`.
	///
	/// This construct is to ensure that node ids aren't mixed up between graphs.
	#[inline(always)]
	pub fn modify<F, R>(&mut self, callback: F) -> R
	where
		for<'new_id> F: FnOnce(MutableGraph<'new_id, T>) -> R,
	{
		MutableGraph::new(self, callback)
	}
}