unobtanium_graph_algorithms/graph/
branded.rs

1// SPDX-FileCopyrightText: 2025 Slatian 2025
2//
3// SPDX-License-Identifier: LGPL-3.0-only
4
5use core::hash::Hash;
6use std::marker::PhantomData;
7use std::ops::Deref;
8
9use crate::graph::Graph;
10use crate::node::NodeId;
11
12#[derive(Default, Clone, Copy)]
13struct InvariantLifetime<'id>(PhantomData<*mut &'id ()>);
14
15/// Mutable version of [Graph] which you can use inside the callback given to
16/// [Graph::modify].
17///
18/// This is implemented using the branding mechanism from the [GhostCell Paper](https://plv.mpi-sws.org/rustbelt/ghostcell/).
19pub struct MutableGraph<'id, T: Eq + Hash + Clone> {
20	graph: &'id mut Graph<T>,
21	_marker: InvariantLifetime<'id>,
22}
23
24/// A Node identifier that is strongly coupled to the [MutableGraph] it belongs into.
25///
26/// You can obtain one using [MutableGraph::fetch_id_for_data].
27///
28/// You can use this one to add nodes and edges to the graph.
29///
30/// In case you are using multiple graphs and run into liftime errors
31/// check if you're mixing ids from multiple graphs.
32#[derive(Clone, Copy)]
33pub struct BrandedNodeId<'id> {
34	inner: NodeId,
35	_marker: InvariantLifetime<'id>,
36}
37
38impl PartialEq for BrandedNodeId<'_> {
39	fn eq(&self, other: &Self) -> bool {
40	     self.inner == other.inner
41	}
42}
43
44impl Eq for BrandedNodeId<'_> { /* empty */ }
45
46impl Hash for BrandedNodeId<'_> {
47	fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
48	     self.inner.hash(state);
49	}
50}
51
52impl PartialOrd for BrandedNodeId<'_> {
53	fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
54	     Some(self.cmp(other))
55	}
56}
57
58impl Ord for BrandedNodeId<'_> {
59	fn cmp(&self, other: &Self) -> std::cmp::Ordering {
60	    self.inner.cmp(&other.inner)
61	}
62}
63
64impl<'id, T: Eq + Hash + Clone> MutableGraph<'id, T> {
65
66	/// Creates a new MutableGraph for a given [Graph] that can be used inside the callback.
67	///
68	/// Prefer using the [Graph::modify] method.
69	#[allow(clippy::new_ret_no_self)]
70	pub fn new<F, R>(graph: &'id mut Graph<T>, callback: F) -> R
71	where
72		for<'new_id> F: FnOnce(MutableGraph<'new_id, T>) -> R,
73	{
74		callback(Self {
75			graph,
76			_marker: Default::default(),
77		})
78	}
79
80	/// Fetch an identifier for a given data structure.
81	///
82	/// If this instance of `data` (as determined by the [Hash] and [Eq] traits) already exists in the graph the resulting id will refer to the same node in the graph.
83	///
84	/// If the argument is an instance of `data` that is not already in the graph it will automatically be added.
85	pub fn fetch_id_for_data(&mut self, data: &T) -> BrandedNodeId<'id> {
86		BrandedNodeId {
87			inner: self.graph.fetch_id_for_data(data),
88			_marker: Default::default(),
89		}
90	}
91
92	/// Given a node id this returns a borrow of the data behind that node.
93	pub fn get_node_data_for_id(&self, id: BrandedNodeId<'id>) -> Option<&T> {
94		self.graph.get_node_data_for_id(id.inner)
95	}
96
97	/// Add a directional vertex (connection) between two nodes with a weight of `1.0`.
98	#[inline(always)]
99	pub fn add_edge(&mut self, from: BrandedNodeId<'id>, to: BrandedNodeId<'id>) {
100		self.add_edge_weighted(from, to, 1.0);
101	}
102
103	/// Add a directional vertex (connection) between two nodes with a custom weight.
104	#[inline(always)]
105	pub fn add_edge_weighted(
106		&mut self,
107		from: BrandedNodeId<'id>,
108		to: BrandedNodeId<'id>,
109		weight: f32,
110	) {
111		self.graph.add_edge_weighted(from.inner, to.inner, weight);
112	}
113}
114
115impl<'id, T: Eq + Hash + Clone> Deref for MutableGraph<'id, T> {
116	type Target = Graph<T>;
117
118	fn deref(&self) -> &Self::Target {
119		self.graph
120	}
121}
unobtanium_graph_algorithms/graph/branded.rs

unobtanium_graph_algorithms/graph/
branded.rs
