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: FnMut(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) -> 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: FnMut(Self::Label) -> bool;
}
|
