zrx_graph/graph/
topology.rs

1// Copyright (c) 2025-2026 Zensical and contributors
2
3// SPDX-License-Identifier: MIT
4// All contributions are certified under the DCO
5
6// Permission is hereby granted, free of charge, to any person obtaining a copy
7// of this software and associated documentation files (the "Software"), to
8// deal in the Software without restriction, including without limitation the
9// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10// sell copies of the Software, and to permit persons to whom the Software is
11// furnished to do so, subject to the following conditions:
12
13// The above copyright notice and this permission notice shall be included in
14// all copies or substantial portions of the Software.
15
16// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18// FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE
19// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22// IN THE SOFTWARE.
23
24// ----------------------------------------------------------------------------
25
26//! Topology.
27
28use std::cell::OnceCell;
29use std::rc::Rc;
30
31use super::builder::Edge;
32
33mod adjacency;
34mod distance;
35
36pub use adjacency::Adjacency;
37pub use distance::Distance;
38
39// ----------------------------------------------------------------------------
40// Structs
41// ----------------------------------------------------------------------------
42
43/// Topology.
44///
45/// This data type represents the topology of a graph, which allows to find the
46/// outgoing and incoming edges for each node in linear time by using efficient
47/// adjacency lists. Note that our implementation does not support edge weights,
48/// as they're not necessary for scheduling purposes, and they would only add
49/// unnecessary complexity and overhead. The topology also contains the lazily
50/// computed [`Distance`] matrix that allows to find the shortest path between
51/// two nodes in the graph, or determine whether they're reachable at all.
52///
53/// The graph topology must be considered immutable, as [`Adjacency`] lists
54/// can't be mutated anyway, and represents the conversion of a graph into an
55/// executable form. In order to modify the graph, convert it back into a
56/// builder using the [`Graph::into_builder`][] method.
57///
58/// The [`Topology`] data type is just a wrapper around [`TopologyInner`] with
59/// an [`Rc`], so it can be shared between the [`Graph`][] and [`Traversal`][]
60/// structures without the need for lifetime annotations, which would render
61/// incremental and asynchronous traversals of graphs more complex.
62///
63/// [`Graph`]: crate::graph::Graph
64/// [`Graph::into_builder`]: crate::graph::Graph::into_builder
65/// [`Traversal`]: crate::graph::traversal::Traversal
66#[derive(Clone, Debug)]
67pub struct Topology(Rc<TopologyInner>);
68
69// ----------------------------------------------------------------------------
70
71/// Topology inner state.
72#[derive(Debug)]
73struct TopologyInner {
74    /// Outgoing edges.
75    outgoing: Adjacency,
76    /// Incoming edges.
77    incoming: Adjacency,
78    /// Distance matrix (computed on first access).
79    distance: OnceCell<Distance>,
80}
81
82// ----------------------------------------------------------------------------
83// Implementations
84// ----------------------------------------------------------------------------
85
86impl Topology {
87    /// Creates a topology of the given graph.
88    ///
89    /// This method constructs a topology from a graph builder, one of the key
90    /// components of an executable [`Graph`][]. Thus, it's usually not needed
91    /// to create a topology manually, as it's automatically created when the
92    /// graph is built using the [`Builder::build`] method.
93    ///
94    /// [`Graph`]: crate::graph::Graph
95    ///
96    /// # Examples
97    ///
98    /// ```
99    /// # use std::error::Error;
100    /// # fn main() -> Result<(), Box<dyn Error>> {
101    /// use zrx_graph::{Graph, Topology};
102    ///
103    /// // Create graph builder and add nodes
104    /// let mut builder = Graph::builder();
105    /// let a = builder.add_node("a");
106    /// let b = builder.add_node("b");
107    /// let c = builder.add_node("c");
108    ///
109    /// // Create edges between nodes
110    /// builder.add_edge(a, b)?;
111    /// builder.add_edge(b, c)?;
112    ///
113    /// // Create topology
114    /// let topology = Topology::new(builder.len(), builder.edges());
115    /// # Ok(())
116    /// # }
117    /// ```
118    #[must_use]
119    pub fn new(nodes: usize, edges: &[Edge]) -> Self {
120        Self(Rc::new(TopologyInner {
121            outgoing: Adjacency::outgoing(nodes, edges),
122            incoming: Adjacency::incoming(nodes, edges),
123            distance: OnceCell::new(),
124        }))
125    }
126}
127
128#[allow(clippy::must_use_candidate)]
129impl Topology {
130    /// Returns a reference to the outgoing edges.
131    #[inline]
132    pub fn outgoing(&self) -> &Adjacency {
133        &self.0.outgoing
134    }
135
136    /// Returns a reference to the incoming edges.
137    #[inline]
138    pub fn incoming(&self) -> &Adjacency {
139        &self.0.incoming
140    }
141
142    /// Returns a reference to the distance matrix.
143    #[inline]
144    pub fn distance(&self) -> &Distance {
145        self.0.distance.get_or_init(|| {
146            // Compute distance matrix on first access, since this incurs cost
147            // of O(n³) because of the usage of the Floyd-Warshall algorithm.
148            Distance::new(&self.0.outgoing)
149        })
150    }
151}
zrx_graph/graph/topology.rs

zrx_graph/graph/
topology.rs
