1//! A bijective map between node indices and a `TopologicalPosition`, to store
2//! the total topological order of the graph.
3//!
4//! This data structure is an implementation detail and is not exposed in the
5//! public API.
6use std::{collections::BTreeMap, fmt, ops::RangeBounds};
78use crate::{
9 algo::{toposort, Cycle},
10 visit::{GraphBase, IntoNeighborsDirected, IntoNodeIdentifiers, NodeIndexable, Visitable},
11};
1213/// A position in the topological order of the graph.
14///
15/// This defines a total order over the set of nodes in the graph.
16///
17/// Note that the positions of all nodes in a graph may not form a contiguous
18/// interval.
19#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Default)]
20#[repr(transparent)]
21pub struct TopologicalPosition(pub(super) usize);
2223/// A bijective map between node indices and their position in a topological order.
24///
25/// Note that this map does not check for injectivity or surjectivity, this
26/// must be enforced by the user. Map mutations that invalidate these properties
27/// are allowed to make it easy to perform batch modifications that temporarily
28/// break the invariants.
29#[derive(Clone)]
30pub(super) struct OrderMap<N> {
31/// Map topological position to node index.
32pos_to_node: BTreeMap<TopologicalPosition, N>,
33/// The inverse of `pos_to_node`, i.e. map node indices to their position.
34 ///
35 /// This is a Vec, relying on `N: NodeIndexable` for indexing.
36node_to_pos: Vec<TopologicalPosition>,
37}
3839impl<N> Default for OrderMap<N> {
40fn default() -> Self {
41Self {
42 pos_to_node: Default::default(),
43 node_to_pos: Default::default(),
44 }
45 }
46}
4748impl<N: fmt::Debug> fmt::Debug for OrderMap<N> {
49fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
50 f.debug_struct("OrderMap")
51 .field("order", &self.pos_to_node)
52 .finish()
53 }
54}
5556impl<N: Copy> OrderMap<N> {
57pub(super) fn try_from_graph<G>(graph: G) -> Result<Self, Cycle<G::NodeId>>
58where
59G: NodeIndexable<NodeId = N> + IntoNeighborsDirected + IntoNodeIdentifiers + Visitable,
60 {
61// Compute the topological order.
62let topo_vec = toposort(graph, None)?;
6364// Create the two map directions.
65let mut pos_to_node = BTreeMap::new();
66let mut node_to_pos = vec![TopologicalPosition::default(); graph.node_bound()];
6768// Populate the maps.
69for (i, &id) in topo_vec.iter().enumerate() {
70let pos = TopologicalPosition(i);
71 pos_to_node.insert(pos, id);
72 node_to_pos[graph.to_index(id)] = pos;
73 }
7475Ok(Self {
76 pos_to_node,
77 node_to_pos,
78 })
79 }
8081pub(super) fn with_capacity(nodes: usize) -> Self {
82Self {
83 pos_to_node: BTreeMap::new(),
84 node_to_pos: Vec::with_capacity(nodes),
85 }
86 }
8788/// Map a node to its position in the topological order.
89 ///
90 /// Panics if the node index is out of bounds.
91pub(super) fn get_position(
92&self,
93 id: N,
94 graph: impl NodeIndexable<NodeId = N>,
95 ) -> TopologicalPosition {
96let idx = graph.to_index(id);
97assert!(idx < self.node_to_pos.len());
98self.node_to_pos[idx]
99 }
100101/// Map a position in the topological order to a node, if it exists.
102pub(super) fn at_position(&self, pos: TopologicalPosition) -> Option<N> {
103self.pos_to_node.get(&pos).copied()
104 }
105106/// Get an iterator over the nodes, ordered by their position.
107pub(super) fn nodes_iter(&self) -> impl Iterator<Item = N> + '_ {
108self.pos_to_node.values().copied()
109 }
110111/// Get an iterator over the nodes within the range of positions.
112pub(super) fn range(
113&self,
114 range: impl RangeBounds<TopologicalPosition>,
115 ) -> impl Iterator<Item = N> + '_ {
116self.pos_to_node.range(range).map(|(_, &n)| n)
117 }
118119/// Add a node to the order map and assign it an arbitrary position.
120 ///
121 /// Return the position of the new node.
122pub(super) fn add_node(
123&mut self,
124 id: N,
125 graph: impl NodeIndexable<NodeId = N>,
126 ) -> TopologicalPosition {
127// The position and node index
128let new_pos = self
129.pos_to_node
130 .iter()
131 .next_back()
132 .map(|(TopologicalPosition(idx), _)| TopologicalPosition(idx + 1))
133 .unwrap_or_default();
134let idx = graph.to_index(id);
135136// Make sure the order_inv is large enough.
137if idx >= self.node_to_pos.len() {
138self.node_to_pos
139 .resize(graph.node_bound(), TopologicalPosition::default());
140 }
141142// Insert both map directions.
143self.pos_to_node.insert(new_pos, id);
144self.node_to_pos[idx] = new_pos;
145146 new_pos
147 }
148149/// Remove a node from the order map.
150 ///
151 /// Panics if the node index is out of bounds.
152pub(super) fn remove_node(&mut self, id: N, graph: impl NodeIndexable<NodeId = N>) {
153let idx = graph.to_index(id);
154assert!(idx < self.node_to_pos.len());
155156let pos = self.node_to_pos[idx];
157self.node_to_pos[idx] = TopologicalPosition::default();
158self.pos_to_node.remove(&pos);
159 }
160161/// Set the position of a node.
162 ///
163 /// Panics if the node index is out of bounds.
164pub(super) fn set_position(
165&mut self,
166 id: N,
167 pos: TopologicalPosition,
168 graph: impl NodeIndexable<NodeId = N>,
169 ) {
170let idx = graph.to_index(id);
171assert!(idx < self.node_to_pos.len());
172173self.pos_to_node.insert(pos, id);
174self.node_to_pos[idx] = pos;
175 }
176}
177178impl<G: Visitable> super::Acyclic<G> {
179/// Get the position of a node in the topological sort.
180 ///
181 /// Panics if the node index is out of bounds.
182pub fn get_position<'a>(&'a self, id: G::NodeId) -> TopologicalPosition
183where
184&'a G: NodeIndexable + GraphBase<NodeId = G::NodeId>,
185 {
186self.order_map.get_position(id, &self.graph)
187 }
188189/// Get the node at a given position in the topological sort, if it exists.
190pub fn at_position(&self, pos: TopologicalPosition) -> Option<G::NodeId> {
191self.order_map.at_position(pos)
192 }
193}