1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/*
 * Copyright (c) 2017 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

//! Traits for constructing graphs.

use graph::{Node, Edge};

/// A trait to construct graphs.
///
/// In general graphs are static objects. In order to build a graph,
/// one should use a graph builder and, once the construction is
/// complete, convert it into a graph.
///
/// This 2-level approach is used because some graph implementations
/// be unstable if the graph is modified (e.g., the node numbers might
/// change). The builder approach allows to separate construction and
/// use of a graph.
pub trait Builder
    where Self: Sized
{
    /// The graph type produced by this builder.
    type Graph;

    /// The type of a nodes.
    type Node: Node;

    /// The type of an edge.
    type Edge: Edge;

    /// Create a new, empty builder.
    fn new() -> Self {
        Self::with_capacities(0, 0)
    }

    /// Create a new, empty builder.
    ///
    /// The builder might be passed a guess of the number of nodes and
    /// edges. This might be used to reserve the appropriate internal
    /// memory, but is no strict requirement for the number of nodes
    /// and edges to be added to the graph.
    fn with_capacities(nnodes: usize, nedges: usize) -> Self;

    /// Reserve memory for a certain number of nodes and edges.
    fn reserve(&mut self, nnodes: usize, nedges: usize);

    /// Add a new node.
    fn add_node(&mut self) -> Self::Node;

    /// Add `n` new nodes.
    fn add_nodes(&mut self, n: usize) -> Vec<Self::Node> {
        (0..n).map(|_| self.add_node()).collect()
    }

    /// Add a new edge.
    fn add_edge(&mut self, u: Self::Node, v: Self::Node) -> Self::Edge;

    /// Return a unique id of a node.
    fn node_id(&self, u: Self::Node) -> usize;

    /// Return a unique id of an edge.
    fn edge_id(&self, e: Self::Edge) -> usize;

    /// Turn the builder into a graph.
    fn to_graph(self) -> Self::Graph;
}