/
multigraph.go
202 lines (168 loc) · 5.76 KB
/
multigraph.go
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
// Copyright ©2014 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package graph
// Line is an edge in a multigraph. A Line returns an ID that must
// distinguish Lines sharing Node end points.
type Line interface {
// From returns the from node of the edge.
From() Node
// To returns the to node of the edge.
To() Node
// ReversedLine returns the edge reversal of the receiver
// if a reversal is valid for the data type.
// When a reversal is valid an edge of the same type as
// the receiver with nodes of the receiver swapped should
// be returned, otherwise the receiver should be returned
// unaltered.
ReversedLine() Line
// ID returns the unique ID for the Line.
ID() int64
}
// WeightedLine is a weighted multigraph edge.
type WeightedLine interface {
Line
Weight() float64
}
// Multigraph is a generalized multigraph.
type Multigraph interface {
// Node returns the node with the given ID if it exists
// in the multigraph, and nil otherwise.
Node(id int64) Node
// Nodes returns all the nodes in the multigraph.
//
// Nodes must not return nil.
Nodes() Nodes
// From returns all nodes that can be reached directly
// from the node with the given ID.
//
// From must not return nil.
From(id int64) Nodes
// HasEdgeBetween returns whether an edge exists between
// nodes with IDs xid and yid without considering direction.
HasEdgeBetween(xid, yid int64) bool
// Lines returns the lines from u to v, with IDs uid and
// vid, if any such lines exist and nil otherwise. The
// node v must be directly reachable from u as defined by
// the From method.
//
// Lines must not return nil.
Lines(uid, vid int64) Lines
}
// WeightedMultigraph is a weighted multigraph.
type WeightedMultigraph interface {
Multigraph
// WeightedLines returns the weighted lines from u to v
// with IDs uid and vid if any such lines exist and nil
// otherwise. The node v must be directly reachable
// from u as defined by the From method.
//
// WeightedLines must not return nil.
WeightedLines(uid, vid int64) WeightedLines
}
// UndirectedMultigraph is an undirected multigraph.
type UndirectedMultigraph interface {
Multigraph
// LinesBetween returns the lines between nodes x and y
// with IDs xid and yid.
//
// LinesBetween must not return nil.
LinesBetween(xid, yid int64) Lines
}
// WeightedUndirectedMultigraph is a weighted undirected multigraph.
type WeightedUndirectedMultigraph interface {
WeightedMultigraph
// WeightedLinesBetween returns the lines between nodes
// x and y with IDs xid and yid.
//
// WeightedLinesBetween must not return nil.
WeightedLinesBetween(xid, yid int64) WeightedLines
}
// DirectedMultigraph is a directed multigraph.
type DirectedMultigraph interface {
Multigraph
// HasEdgeFromTo returns whether an edge exists
// in the multigraph from u to v with IDs uid
// and vid.
HasEdgeFromTo(uid, vid int64) bool
// To returns all nodes that can reach directly
// to the node with the given ID.
//
// To must not return nil.
To(id int64) Nodes
}
// WeightedDirectedMultigraph is a weighted directed multigraph.
type WeightedDirectedMultigraph interface {
WeightedMultigraph
// HasEdgeFromTo returns whether an edge exists
// in the multigraph from u to v with IDs uid
// and vid.
HasEdgeFromTo(uid, vid int64) bool
// To returns all nodes that can reach directly
// to the node with the given ID.
//
// To must not return nil.
To(id int64) Nodes
}
// LineAdder is an interface for adding lines to a multigraph.
type LineAdder interface {
// NewLine returns a new Line from the source to the destination node.
NewLine(from, to Node) Line
// SetLine adds a Line from one node to another.
// If the multigraph supports node addition the nodes
// will be added if they do not exist, otherwise
// SetLine will panic.
// Whether l, l.From() and l.To() are stored
// within the graph is implementation dependent.
SetLine(l Line)
}
// WeightedLineAdder is an interface for adding lines to a multigraph.
type WeightedLineAdder interface {
// NewWeightedLine returns a new WeightedLine from
// the source to the destination node.
NewWeightedLine(from, to Node, weight float64) WeightedLine
// SetWeightedLine adds a weighted line from one node
// to another. If the multigraph supports node addition
// the nodes will be added if they do not exist,
// otherwise SetWeightedLine will panic.
// Whether l, l.From() and l.To() are stored
// within the graph is implementation dependent.
SetWeightedLine(l WeightedLine)
}
// LineRemover is an interface for removing lines from a multigraph.
type LineRemover interface {
// RemoveLine removes the line with the given end
// and line IDs, leaving the terminal nodes. If
// the line does not exist it is a no-op.
RemoveLine(fid, tid, id int64)
}
// MultigraphBuilder is a multigraph that can have nodes and lines added.
type MultigraphBuilder interface {
NodeAdder
LineAdder
}
// WeightedMultigraphBuilder is a multigraph that can have nodes and weighted lines added.
type WeightedMultigraphBuilder interface {
NodeAdder
WeightedLineAdder
}
// UndirectedMultgraphBuilder is an undirected multigraph builder.
type UndirectedMultigraphBuilder interface {
UndirectedMultigraph
MultigraphBuilder
}
// UndirectedWeightedMultigraphBuilder is an undirected weighted multigraph builder.
type UndirectedWeightedMultigraphBuilder interface {
UndirectedMultigraph
WeightedMultigraphBuilder
}
// DirectedMultigraphBuilder is a directed multigraph builder.
type DirectedMultigraphBuilder interface {
DirectedMultigraph
MultigraphBuilder
}
// DirectedWeightedMultigraphBuilder is a directed weighted multigraph builder.
type DirectedWeightedMultigraphBuilder interface {
DirectedMultigraph
WeightedMultigraphBuilder
}