rs_graph/
builder.rs

1/*
2 * Copyright (c) 2017-2022 Frank Fischer <frank-fischer@shadow-soft.de>
3 *
4 * This program is free software: you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation, either version 3 of the
7 * License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
16 */
17
18//! Traits for constructing graphs.
19
20/// A trait to construct graphs.
21///
22/// In general graphs are static objects. In order to build a graph,
23/// one should use a graph builder and, once the construction is
24/// complete, convert it into a graph.
25///
26/// This 2-level approach is used because some graph implementations
27/// be unstable if the graph is modified (e.g., the node numbers might
28/// change). The builder approach allows to separate construction and
29/// use of a graph.
30pub trait Builder
31where
32    Self: Sized,
33{
34    /// The graph type produced by this builder.
35    type Graph;
36
37    /// The type of a nodes.
38    type Node: Copy + Eq;
39
40    /// The type of an edge.
41    type Edge: Copy + Eq;
42
43    /// Create a new, empty builder.
44    fn new() -> Self {
45        Self::with_capacities(0, 0)
46    }
47
48    /// Create a new, empty builder.
49    ///
50    /// The builder might be passed a guess of the number of nodes and
51    /// edges. This might be used to reserve the appropriate internal
52    /// memory, but is no strict requirement for the number of nodes
53    /// and edges to be added to the graph.
54    fn with_capacities(nnodes: usize, nedges: usize) -> Self;
55
56    /// Reserve memory for a certain number of nodes and edges.
57    fn reserve(&mut self, nnodes: usize, nedges: usize);
58
59    /// Return the current number of nodes.
60    fn num_nodes(&self) -> usize;
61
62    /// Return the current number of nodes.
63    fn num_edges(&self) -> usize;
64
65    /// Add a new node.
66    fn add_node(&mut self) -> Self::Node;
67
68    /// Add `n` new nodes.
69    fn add_nodes(&mut self, n: usize) -> Vec<Self::Node> {
70        (0..n).map(|_| self.add_node()).collect()
71    }
72
73    /// Add a new edge.
74    fn add_edge(&mut self, u: Self::Node, v: Self::Node) -> Self::Edge;
75
76    /// Return a unique id of a node.
77    fn node2id(&self, u: Self::Node) -> usize;
78
79    /// Return a unique id of an edge.
80    fn edge2id(&self, e: Self::Edge) -> usize;
81
82    /// Return the node with a certain id.
83    fn id2node(&self, uid: usize) -> Self::Node;
84
85    /// Return the edge with a certain id.
86    fn id2edge(&self, eid: usize) -> Self::Edge;
87
88    /// Turn the builder into a graph.
89    fn into_graph(self) -> Self::Graph;
90}
91
92/// A graph with a default builder.
93pub trait Buildable
94where
95    Self: Sized,
96{
97    type Builder: Builder<Graph = Self>;
98
99    /// Create a new builder for this graph type.
100    fn new_builder() -> Self::Builder {
101        Self::Builder::new()
102    }
103
104    /// Create a new graph by passing the builder to the callback `f`.
105    ///
106    /// # Example
107    ///
108    /// ```
109    /// use rs_graph::{Buildable, Builder, LinkedListGraph};
110    /// use rs_graph::traits::FiniteGraph;
111    ///
112    /// let g = LinkedListGraph::<usize>::new_with(|b| {
113    ///     let u = b.add_node();
114    ///     let v = b.add_node();
115    ///     b.add_edge(u, v);
116    /// });
117    ///
118    /// assert_eq!(g.num_nodes(), 2);
119    /// assert_eq!(g.num_edges(), 1);
120    /// ```
121    fn new_with<F>(f: F) -> Self
122    where
123        F: FnOnce(&mut Self::Builder),
124    {
125        let mut b = Self::new_builder();
126        f(&mut b);
127        b.into_graph()
128    }
129}
rs_graph/builder.rs

rs_graph/
builder.rs
