zrx_graph/graph/
topology.rs

1// Copyright (c) 2025 Zensical and contributors
2
3// SPDX-License-Identifier: MIT
4// Third-party contributions licensed under 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::rc::Rc;
29
30use super::builder::{Builder, Edge};
31
32mod adjacency;
33mod distance;
34
35pub use adjacency::Adjacency;
36pub use distance::Distance;
37
38// ----------------------------------------------------------------------------
39// Structs
40// ----------------------------------------------------------------------------
41
42/// Topology.
43///
44/// This data type represents the topology of a graph, which allows to find the
45/// outgoing and incoming edges for each node in linear time. The topology does
46/// not retain edge weights, since we only need them during graph construction,
47/// as in our case, they're not relevant for traversal. Moreover, it contains
48/// the [`Distance`] matrix that allows to find the shortest path between two
49/// nodes in the graph, or determine whether they're reachable at all.
50///
51/// The graph topology must be considered immutable, as [`Adjacency`] lists
52/// can't be mutated anyway, and represents the conversion of a graph into an
53/// executable form. It's used during [`Traversal`][], so all nodes are visited
54/// in topological order.
55///
56/// Cloning is very cheap, since both incoming and outgoing edges are stored in
57/// [`Rc`] smart pointers, so they can be shared among multiple traversals.
58///
59/// [`Traversal`]: crate::graph::traversal::Traversal
60#[derive(Clone, Debug)]
61pub struct Topology {
62    /// Outgoing edges.
63    outgoing: Rc<Adjacency>,
64    /// Incoming edges.
65    incoming: Rc<Adjacency>,
66    /// Distance matrix.
67    distance: Rc<Distance>,
68}
69
70// ----------------------------------------------------------------------------
71// Implementations
72// ----------------------------------------------------------------------------
73
74impl Topology {
75    /// Creates a topology of the given graph.
76    ///
77    /// This method constructs a topology from a graph builder, one of the key
78    /// components of an executable [`Graph`][]. Thus, it's usually not needed
79    /// to create a topology manually, as it's automatically created when the
80    /// graph is built using the [`Builder::build`] method.
81    ///
82    /// [`Graph`]: crate::graph::Graph
83    ///
84    /// # Examples
85    ///
86    /// ```
87    /// # use std::error::Error;
88    /// # fn main() -> Result<(), Box<dyn Error>> {
89    /// use zrx_graph::{Graph, Topology};
90    ///
91    /// // Create graph builder and add nodes
92    /// let mut builder = Graph::builder();
93    /// let a = builder.add_node("a");
94    /// let b = builder.add_node("b");
95    /// let c = builder.add_node("c");
96    ///
97    /// // Create edges between nodes
98    /// builder.add_edge(a, b, 0)?;
99    /// builder.add_edge(b, c, 0)?;
100    ///
101    /// // Create topology
102    /// let topology = Topology::new(&builder);
103    /// # Ok(())
104    /// # }
105    /// ```
106    #[must_use]
107    pub fn new<T, W>(builder: &Builder<T, W>) -> Self
108    where
109        W: Clone,
110    {
111        Self {
112            outgoing: Rc::new(Adjacency::outgoing(builder)),
113            incoming: Rc::new(Adjacency::incoming(builder)),
114            distance: Rc::new(Distance::new(builder)),
115        }
116    }
117}
118
119#[allow(clippy::must_use_candidate)]
120impl Topology {
121    /// Returns a reference to the outgoing edges.
122    #[inline]
123    pub fn outgoing(&self) -> &Adjacency {
124        &self.outgoing
125    }
126
127    /// Returns a reference to the incoming edges.
128    #[inline]
129    pub fn incoming(&self) -> &Adjacency {
130        &self.incoming
131    }
132
133    /// Returns a reference to the distance matrix.
134    #[inline]
135    pub fn distance(&self) -> &Distance {
136        &self.distance
137    }
138}
zrx_graph/graph/topology.rs

zrx_graph/graph/
topology.rs
