-
Notifications
You must be signed in to change notification settings - Fork 3
/
abstractnamedgraph.jl
302 lines (249 loc) · 9.89 KB
/
abstractnamedgraph.jl
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
abstract type AbstractNamedGraph{V} <: AbstractGraph{V} end
#
# Required for interface
#
vertices(graph::AbstractNamedGraph) = not_implemented()
parent_graph(graph::AbstractNamedGraph) = not_implemented()
# TODO: Require this for the interface, or implement as:
# typeof(parent_graph(graph))
# ?
parent_graph_type(graph::AbstractNamedGraph) = not_implemented()
vertex_to_parent_vertex(graph::AbstractNamedGraph) = not_implemented()
# TODO: rename `edge_type`?
edgetype(graph::AbstractNamedGraph) = not_implemented()
directed_graph(G::Type{<:AbstractNamedGraph}) = not_implemented()
undirected_graph(G::Type{<:AbstractNamedGraph}) = not_implemented()
# In terms of `parent_graph_type`
# is_directed(::Type{<:AbstractNamedGraph}) = not_implemented()
# TODO: implement as:
#
# graph = set_parent_graph(graph, copy(parent_graph(graph)))
# graph = set_vertices(graph, copy(vertices(graph)))
#
# or:
#
# graph_copy = similar(typeof(graph))(vertices(graph))
# for e in edges(graph)
# add_edge!(graph_copy, e)
# end
copy(graph::AbstractNamedGraph) = not_implemented()
# TODO: Implement using `copyto!`?
function directed_graph(graph::AbstractNamedGraph)
digraph = directed_graph(typeof(graph))(vertices(graph))
for e in edges(graph)
add_edge!(digraph, e)
add_edge!(digraph, reverse(e))
end
return digraph
end
# Default, can overload
eltype(graph::AbstractNamedGraph) = eltype(vertices(graph))
parent_eltype(graph::AbstractNamedGraph) = eltype(parent_graph(graph))
# By default, assume `vertex_to_parent_vertex(graph)`
# returns a data structure that you index into to map
# from a vertex to a parent vertex.
function vertex_to_parent_vertex(graph::AbstractNamedGraph, vertex)
return vertex_to_parent_vertex(graph)[vertex]
end
# Convert parent vertex to vertex.
# Use `vertices`, assumes `vertices` is indexed by a parent vertex (a Vector for linear indexed parent vertices, a dictionary in general).
function parent_vertex_to_vertex(graph::AbstractNamedGraph, parent_vertex)
return vertices(graph)[parent_vertex]
end
# This should be overloaded for multi-dimensional indexing.
# Get the subset of vertices of the graph, for example
# for an input slice `subvertices(graph, "X", :)`.
function subvertices(graph::AbstractNamedGraph, vertices)
return not_implemented()
end
function subvertices(graph::AbstractNamedGraph{V}, vertices::Vector{V}) where {V}
return vertices
end
# This is to handle `NamedDimGraph` where some of the dimensions
# that are not slices get dropped.
function sliced_subvertices(graph::AbstractNamedGraph, vertices)
return subvertices(graph, vertices)
end
function vertices_to_parent_vertices(
graph::AbstractNamedGraph{V}, vertices::Vector{V}
) where {V}
return parent_eltype(graph)[vertex_to_parent_vertex(graph, vertex) for vertex in vertices]
end
parent_vertices(graph::AbstractNamedGraph) = vertices(parent_graph(graph))
parent_edges(graph::AbstractNamedGraph) = edges(parent_graph(graph))
parent_edgetype(graph::AbstractNamedGraph) = edgetype(parent_graph(graph))
function edge_to_parent_edge(graph::AbstractNamedGraph, edge::AbstractEdge)
parent_src = vertex_to_parent_vertex(graph, src(edge))
parent_dst = vertex_to_parent_vertex(graph, dst(edge))
return parent_edgetype(graph)(parent_src, parent_dst)
end
function edge_to_parent_edge(graph::AbstractNamedGraph, edge)
return edge_to_parent_edge(graph, edgetype(graph)(edge))
end
# TODO: This is `O(nv(g))`, use `haskey(vertex_to_parent_vertex(g), v)` instead?
has_vertex(g::AbstractNamedGraph, v) = v in vertices(g)
function edges(graph::AbstractNamedGraph)
vertex(parent_vertex) = vertices(graph)[parent_vertex]
edge(parent_edge) = edgetype(graph)(vertex(src(parent_edge)), vertex(dst(parent_edge)))
return map(edge, parent_edges(graph))
end
# TODO: write in terms of a generic function.
for f in [:outneighbors, :inneighbors, :all_neighbors, :neighbors]
@eval begin
function $f(graph::AbstractNamedGraph, vertex)
parent_vertices = $f(parent_graph(graph), vertex_to_parent_vertex(graph, vertex))
return [
parent_vertex_to_vertex(graph, parent_vertex) for parent_vertex in parent_vertices
]
end
# Ambiguity errors with Graphs.jl
function $f(graph::AbstractNamedGraph, vertex::Integer)
parent_vertices = $f(parent_graph(graph), vertex_to_parent_vertex(graph, vertex))
return [
parent_vertex_to_vertex(graph, parent_vertex) for parent_vertex in parent_vertices
]
end
end
end
function add_edge!(graph::AbstractNamedGraph, edge::AbstractEdge)
add_edge!(parent_graph(graph), edge_to_parent_edge(graph, edge))
return graph
end
# handles single-argument edge constructors such as pairs and tuples
add_edge!(g::AbstractNamedGraph, edge) = add_edge!(g, edgetype(g)(edge))
add_edge!(g::AbstractNamedGraph, src, dst) = add_edge!(g, edgetype(g)(src, dst))
function rem_edge!(graph::AbstractNamedGraph, edge)
rem_edge!(parent_graph(graph), edge_to_parent_edge(graph, edge))
return graph
end
function has_edge(graph::AbstractNamedGraph, edge::AbstractNamedEdge)
return has_edge(parent_graph(graph), edge_to_parent_edge(graph, edge))
end
# handles two-argument edge constructors like src,dst
has_edge(g::AbstractNamedGraph, edge) = has_edge(g, edgetype(g)(edge))
has_edge(g::AbstractNamedGraph, src, dst) = has_edge(g, edgetype(g)(src, dst))
function union(graph1::AbstractNamedGraph, graph2::AbstractNamedGraph)
union_graph = promote_type(typeof(graph1), typeof(graph2))()
union_vertices = union(vertices(graph1), vertices(graph2))
for v in union_vertices
add_vertex!(union_graph, v)
end
for e in edges(graph1)
add_edge!(union_graph, e)
end
for e in edges(graph2)
add_edge!(union_graph, e)
end
return union_graph
end
function add_vertex!(graph::AbstractNamedGraph, vertex)
if vertex ∈ vertices(graph)
throw(ArgumentError("Duplicate vertices are not allowed"))
end
add_vertex!(parent_graph(graph))
# Update the vertex list
push!(vertices(graph), vertex)
# Update the reverse map
insert!(vertex_to_parent_vertex(graph), vertex, last(parent_vertices(graph)))
return graph
end
function rem_vertex!(graph::AbstractNamedGraph, vertex)
parent_vertex = vertex_to_parent_vertex(graph, vertex)
rem_vertex!(parent_graph(graph), parent_vertex)
# Insert the last vertex into the position of the vertex
# that is being deleted, then remove the last vertex.
last_vertex = last(vertices(graph))
vertices(graph)[parent_vertex] = last_vertex
last_vertex = pop!(vertices(graph))
# Insert the last vertex into the position of the vertex
# that is being deleted, then remove the last vertex.
vertex_to_parent_vertex(graph)[last_vertex] = parent_vertex
delete!(vertex_to_parent_vertex(graph), vertex)
return graph
end
function add_vertices!(graph::AbstractNamedGraph, vs::Vector)
for vertex in vs
add_vertex!(graph, vertex)
end
return graph
end
is_directed(G::Type{<:AbstractNamedGraph}) = is_directed(parent_graph_type(G))
is_directed(graph::AbstractNamedGraph) = is_directed(parent_graph(graph))
is_connected(graph::AbstractNamedGraph) = is_connected(parent_graph(graph))
is_cyclic(graph::AbstractNamedGraph) = is_cyclic(parent_graph(graph))
# TODO: Move to namedgraph.jl, or make the output generic?
function blockdiag(graph1::AbstractNamedGraph, graph2::AbstractNamedGraph)
new_parent_graph = blockdiag(parent_graph(graph1), parent_graph(graph2))
new_vertices = vcat(vertices(graph1), vertices(graph2))
@assert allunique(new_vertices)
return GenericNamedGraph(new_parent_graph, new_vertices)
end
# TODO: What `args` are needed?
nv(graph::AbstractNamedGraph, args...) = nv(parent_graph(graph), args...)
# TODO: What `args` are needed?
ne(graph::AbstractNamedGraph, args...) = ne(parent_graph(graph), args...)
# TODO: What `args` are needed?
function adjacency_matrix(graph::AbstractNamedGraph, args...)
return adjacency_matrix(parent_graph(graph), args...)
end
#
# Graph traversals
#
# Overload Graphs.tree. Used for bfs_tree and dfs_tree
# traversal algorithms.
function tree(graph::AbstractNamedGraph, parents::AbstractVector)
n = length(parents)
# TODO: Use `directed_graph` here to make more generic?
t = GenericNamedGraph(DiGraph(n), vertices(graph))
for (parent_v, u) in enumerate(parents)
v = vertices(graph)[parent_v]
if u != v
add_edge!(t, u, v)
end
end
return t
end
bfs_tree(g::AbstractNamedGraph, s; kwargs...) = tree(g, bfs_parents(g, s; kwargs...))
# Disambiguation from Graphs.bfs_tree
bfs_tree(g::AbstractNamedGraph, s::Integer; kwargs...) = bfs_tree(g, tuple(s); kwargs...)
function bfs_parents(graph::AbstractNamedGraph, s; kwargs...)
parent_bfs_parents = bfs_parents(
parent_graph(graph), vertex_to_parent_vertex(graph)[s]; kwargs...
)
return [vertices(graph)[parent_vertex] for parent_vertex in parent_bfs_parents]
end
dfs_tree(g::AbstractNamedGraph, s; kwargs...) = tree(g, dfs_parents(g, s; kwargs...))
# Disambiguation from Graphs.dfs_tree
dfs_tree(g::AbstractNamedGraph, s::Integer; kwargs...) = dfs_tree(g, tuple(s); kwargs...)
function dfs_parents(graph::AbstractNamedGraph, s; kwargs...)
parent_dfs_parents = dfs_parents(
parent_graph(graph), vertex_to_parent_vertex(graph)[s]; kwargs...
)
return [vertices(graph)[parent_vertex] for parent_vertex in parent_dfs_parents]
end
#
# Printing
#
function show(io::IO, mime::MIME"text/plain", graph::AbstractNamedGraph)
println(io, "$(typeof(graph)) with $(nv(graph)) vertices:")
show(io, mime, vertices(graph))
println(io, "\n")
println(io, "and $(ne(graph)) edge(s):")
for e in edges(graph)
show(io, mime, e)
println(io)
end
return nothing
end
show(io::IO, graph::AbstractNamedGraph) = show(io, MIME"text/plain"(), graph)
#
# Convenience functions
#
function Base.:(==)(g1::AbstractNamedGraph, g2::AbstractNamedGraph)
issetequal(vertices(g1), vertices(g2)) || return false
for v in vertices(g1)
issetequal(inneighbors(g1, v), inneighbors(g2, v)) || return false
issetequal(outneighbors(g1, v), outneighbors(g2, v)) || return false
end
return true
end