summaryrefslogtreecommitdiff
path: root/graph/src/builder.rs
blob: 4a480a5eefe5eacd77bfd9dfc78b88c50959573c (plain)
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//! This file defines the expected behaviours of a builder of graphs.

use crate::{error::Error, Graph};

/// A builder is actually just a graph that can be altered in more
/// ways than an extension graph can.  It should not have any methods
/// from the Graph trait, though, as we shall convert a builder to a
/// normal final graph before using it.
pub trait Builder: Default {
    /// Some graphs are labelled.  This type should be the type of the
    /// labels.
    type Label;

    /// The type of the result graph.
    type Result: Graph;

    /// Construct an empty builder with the capacity to hold a given
    /// number of nodes.
    ///
    /// Implementations may ignore this method, where the default
    /// implementation just calls `Default::default`.
    #[inline]
    fn with_capacity(_size: usize) -> Self {
        Self::default()
    }

    /// Add a vertex without children.
    fn add_vertex(&mut self) -> usize;

    /// Add a number of vertices at the same time.
    fn add_vertices(&mut self, n: usize);

    /// Add an edge from the source to the target.
    fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error>;

    /// Remove an edge from the source to the target.
    ///
    /// Since some graphs are labelled, the users are allowed to pass
    /// a predicate to determine if an edge from the source to the
    /// target should be removed.
    fn remove_edge<F>(&mut self, source: usize, target: usize, predicate: F) -> Result<(), Error>
    where
        F: Fn(Self::Label) -> bool;

    /// Convert the builder into a graph.
    ///
    /// This is the purpose of having a builder.
    fn build(self) -> Self::Result;

    /// Convert the builder into a graph using a reference.
    ///
    /// This is similar to [`build`][Builder::build], but takes an
    /// immutable reference of the builder, so that the builder can
    /// still be used later on.
    fn build_ref(&self) -> Self::Result;
}

/// The type of builders that actually reference the underlying graph
/// instead of owe it.
///
/// To finish the task of the builder, just do not use it anymore.
/// The building happens right when the building methods are called.
pub trait BuilderMut {
    /// Some graphs are labelled.  This type should be the type of the
    /// labels.
    type Label;

    /// The type of the underlying graph.
    type Graph: Graph;

    /// The type of the builder from a borrow.
    type ResultBuilder<'a>: BuilderMut
    where
        Self::Label: 'a;

    /// Borrow a graph to create a builder without copying.
    fn from_graph_mut(graph: &mut Self::Graph) -> Self::ResultBuilder<'_>;

    /// Add a new vertex.
    fn add_vertex(&mut self, label: Self::Label) -> Result<usize, Error>;

    /// Add an edge from the source to the target.
    fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error>;

    /// Remove an edge from the source to the target.
    ///
    /// Since some graphs are labelled, the users are allowed to pass
    /// a predicate to determine if an edge from the source to the
    /// target should be removed.
    fn remove_edge<F>(&mut self, source: usize, target: usize, predicate: F) -> Result<(), Error>
    where
        F: Fn(Self::Label) -> bool;
}