-
Notifications
You must be signed in to change notification settings - Fork 0
/
simplelazygraph.jl
146 lines (124 loc) · 4.4 KB
/
simplelazygraph.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
"""
SimpleLazyGraph{T}
A type representing a graph that computes its vertices and edges as needed.
"""
mutable struct SimpleLazyGraph{T<:Integer} <: AbstractSimpleLazyGraph{T}
ne::Int
fadjlist::Vector{Vector{T}} # [src]: (dst, dst, dst)
# boolean vectors to keep track of created neighbors
created_inneighbors::Vector{Bool}
created_outneighbors::Vector{Bool}
# function to compute the in/outneighbors of a vertex
inneighbors_lazy::Function
outneighbors_lazy::Function
function SimpleLazyGraph{T}(
ne::Int,
fadjlist::Vector{Vector{T}},
inneighbors_lazy::Function,
outneighbors_lazy::Function,
) where {T}
throw_if_invalid_eltype(T)
created_inneighbors = Vector{Bool}()
created_outneighbors = Vector{Bool}()
return new(
ne,
fadjlist,
created_inneighbors,
created_outneighbors,
inneighbors_lazy,
outneighbors_lazy,
)
end
end
# Create simplelazygraphs based on specified inneighbor/outneighbor function or just a single neighbor function
function SimpleLazyGraph(
ne::Int,
fadjlist::Vector{Vector{T}},
inneighbors_lazy::Function,
outneighbors_lazy::Function,
) where {T}
return SimpleLazyGraph{T}(ne, fadjlist, inneighbors_lazy, outneighbors_lazy)
end
function SimpleLazyGraph(
ne::Int,
fadjlist::Vector{Vector{T}},
neighbors_lazy::Function, # function to compute the neighbors of a vertex
) where {T}
return SimpleLazyGraph{T}(ne, fadjlist, neighbors_lazy, neighbors_lazy)
end
function SimpleLazyGraph(inneighbors_lazy::Function, outneighbors_lazy::Function)
ne = 0
fadjlist = Vector{Vector{Int}}()
return SimpleLazyGraph{Int}(ne, fadjlist, inneighbors_lazy, outneighbors_lazy)
end
function SimpleLazyGraph(
neighbors_lazy::Function, # function to compute the neighbors of a vertex
)
ne = 0
fadjlist = Vector{Vector{Int}}()
return SimpleLazyGraph{Int}(ne, fadjlist, neighbors_lazy, neighbors_lazy)
end
function inneighbors(g::AbstractSimpleLazyGraph, v::Integer)
if v ∉ g.created_inneighbors
new_inneighors = g.inneighbors_lazy(v)
for new_inneighbor in new_inneighors
add_vertex!(g)
add_edge!(g, new_inneighbor, v)
end
push!(g.created_inneighbors, true)
end
# return Base.@invoke inneighbors(g::AbstractSimpleGraph, v::Integer)
return g.fadjlist[v]
end
function outneighbors(g::AbstractSimpleLazyGraph, v::Integer)
if v ∉ g.created_outneighbors
new_outneighbors = g.outneighbors_lazy(v)
for new_outneighbor in new_outneighbors
add_vertex!(g)
add_edge!(g, v, new_outneighbor)
end
push!(g.created_outneighbors, true)
end
# return Base.@invoke outneighbors(g::AbstractSimpleGraph, v::Integer)
return g.fadjlist[v]
end
## Copy pasted methods with different input types from SimpleGraph:
# https://github.com/JuliaGraphs/Graphs.jl/blob/master/src/SimpleGraphs/simplegraph.jl
function add_vertex!(g::AbstractSimpleGraph{T}) where {T}
(nv(g) + one(T) <= nv(g)) && return false # test for overflow
push!(g.fadjlist, Vector{T}())
push!(g.created_inneighbors, false)
push!(g.created_outneighbors, false)
return true
end
function add_edge!(g::AbstractSimpleGraph{T}, s, d) where {T}
verts = vertices(g)
(s in verts && d in verts) || return false # edge out of bounds
@inbounds list = g.fadjlist[s]
index = searchsortedfirst(list, d)
@inbounds (index <= length(list) && list[index] == d) && return false # edge already in graph
insert!(list, index, d)
g.ne += 1
s == d && return true # selfloop
@inbounds list = g.fadjlist[d]
index = searchsortedfirst(list, s)
insert!(list, index, s)
return true # edge successfully added
end
is_directed(::Type{<:SimpleLazyGraph}) = false
edgetype(::SimpleLazyGraph{T}) where {T<:Integer} = SimpleGraphEdge{T}
function has_edge(g::SimpleLazyGraph{T}, s, d) where {T}
verts = vertices(g)
(s in verts && d in verts) || return false # edge out of bounds
@inbounds list_s = g.fadjlist[s]
@inbounds list_d = g.fadjlist[d]
if length(list_s) > length(list_d)
d = s
list_s = list_d
end
return insorted(d, list_s)
end
function has_edge(g::SimpleLazyGraph{T}, e::SimpleGraphEdge{T}) where {T}
s, d = T.(Tuple(e))
return has_edge(g, s, d)
end