unobtanium_graph_algorithms/graph/
mod.rs

1// SPDX-FileCopyrightText: 2025 Slatian 2025
2//
3// SPDX-License-Identifier: LGPL-3.0-only
4
5use iddqd::BiHashMap;
6
7use core::hash::Hash;
8
9mod branded;
10mod pagerank;
11pub mod ranked_nodes;
12
13use crate::node::Node;
14use crate::node::NodeId;
15
16pub use branded::BrandedNodeId;
17pub use branded::MutableGraph;
18
19/// Datastructure to run graph algorithms on.
20pub struct Graph<T: Eq + Hash + Clone> {
21	/// Maps each node to its incoming edges with weights
22	/// `to ("node"), (from, score) ("edge")`
23	graph: Vec<Vec<(NodeId, f32)>>,
24
25	/// Maps each node to the sum of its outgoing edge weights
26	outgoing_weight_sums: Vec<f32>,
27
28	/// Maps between actual node content and node ids
29	nodes: BiHashMap<Node<T>>,
30
31	/// Number of nodes and
32	/// the next node id to be assigned.
33	nodes_length: usize,
34}
35
36impl<T: Eq + Hash + Clone> Default for Graph<T> {
37	fn default() -> Self {
38		Self {
39			graph: Default::default(),
40			outgoing_weight_sums: Default::default(),
41			nodes: BiHashMap::new(),
42			nodes_length: 0,
43		}
44	}
45}
46
47impl<T: Eq + Hash + Clone> Graph<T> {
48	/// Construct a new, empty graph
49	pub fn new() -> Self {
50		Default::default()
51	}
52
53	fn get_node_data_for_id(&self, id: NodeId) -> Option<&T> {
54		Some(&self.nodes.get1(&id)?.data)
55	}
56
57	fn fetch_id_for_data(&mut self, data: &T) -> NodeId {
58		if let Some(node) = self.nodes.get2(&data) {
59			return node.id;
60		}
61		let new_id = self.nodes_length;
62		self.nodes_length += 1;
63		self.outgoing_weight_sums.push(0.0);
64		self.graph.push(Vec::with_capacity(4));
65		self.nodes.insert_overwrite(Node {
66			id: NodeId(new_id),
67			data: data.clone(),
68		});
69		NodeId(new_id)
70	}
71
72	#[inline(always)]
73	fn add_edge_weighted(&mut self, from: NodeId, to: NodeId, weight: f32) {
74		let incoming_edges = self.graph
75			.get_mut(to.0)
76			.unwrap();
77		let mut found = false;
78		for (id, e) in &mut *incoming_edges {
79			if *id == from {
80				*e += weight;
81				found = true;
82				break;
83			}
84		}
85		if !found {
86			incoming_edges.push((from, weight))
87		}
88		*self.outgoing_weight_sums.get_mut(from.0).unwrap() += weight;
89	}
90
91	/// Constructs a modifiable versions of this graph and passes it to `callback`.
92	///
93	/// This construct is to ensure that node ids aren't mixed up between graphs.
94	#[inline(always)]
95	pub fn modify<F, R>(&mut self, callback: F) -> R
96	where
97		for<'new_id> F: FnOnce(MutableGraph<'new_id, T>) -> R,
98	{
99		MutableGraph::new(self, callback)
100	}
101}
unobtanium_graph_algorithms/graph/mod.rs

unobtanium_graph_algorithms/graph/
mod.rs
