/
randomwalks.jl
144 lines (135 loc) · 4.01 KB
/
randomwalks.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
"""
randomwalk(g, s, niter; rng=nothing, seed=nothing)
Perform a random walk on graph `g` starting at vertex `s` and continuing for
a maximum of `niter` steps. Return a vector of vertices visited in order.
"""
function randomwalk(
g::AG,
s::Integer,
niter::Integer;
rng::Union{Nothing,AbstractRNG}=nothing,
seed::Union{Nothing,Integer}=nothing,
) where {AG<:AbstractGraph{T}} where {T}
s in vertices(g) || throw(BoundsError())
rng = rng_from_rng_or_seed(rng, seed)
visited = Vector{T}()
sizehint!(visited, niter)
currs = s
i = 1
while i <= niter
push!(visited, currs)
i += 1
nbrs = outneighbors(g, currs)
length(nbrs) == 0 && break
currs = rand(rng, nbrs)
end
return visited[1:(i - 1)]
end
"""
non_backtracking_randomwalk(g, s, niter; rng=nothing, seed=nothing)
Perform a non-backtracking random walk on directed graph `g` starting at
vertex `s` and continuing for a maximum of `niter` steps. Return a
vector of vertices visited in order.
"""
function non_backtracking_randomwalk end
# see https://github.com/mauro3/SimpleTraits.jl/issues/47#issuecomment-327880153 for syntax
@traitfn function non_backtracking_randomwalk(
g::AG::(!IsDirected),
s::Integer,
niter::Integer;
rng::Union{Nothing,AbstractRNG}=nothing,
seed::Union{Nothing,Integer}=nothing,
) where {T,AG<:AbstractGraph{T}}
s in vertices(g) || throw(BoundsError())
rng = rng_from_rng_or_seed(rng, seed)
visited = Vector{T}()
sizehint!(visited, niter)
currs = s
prev = -1
i = 1
push!(visited, currs)
i += 1
nbrs = outneighbors(g, currs)
length(nbrs) == 0 && return visited[1:(i - 1)]
prev = currs
currs = rand(rng, nbrs)
while i <= niter
push!(visited, currs)
i += 1
nbrs = outneighbors(g, currs)
length(nbrs) == 1 && break
idnext = rand(rng, 1:(length(nbrs) - 1))
next = nbrs[idnext]
if next == prev
next = nbrs[end]
end
prev = currs
currs = next
end
return visited[1:(i - 1)]
end
# see https://github.com/mauro3/SimpleTraits.jl/issues/47#issuecomment-327880153 for syntax
@traitfn function non_backtracking_randomwalk(
g::AG::IsDirected,
s::Integer,
niter::Integer;
rng::Union{Nothing,AbstractRNG}=nothing,
seed::Union{Nothing,Integer}=nothing,
) where {T,AG<:AbstractGraph{T}}
s in vertices(g) || throw(BoundsError())
rng = rng_from_rng_or_seed(rng, seed)
visited = Vector{T}()
sizehint!(visited, niter)
currs = s
prev = -1
i = 1
while i <= niter
push!(visited, currs)
i += 1
nbrs = outneighbors(g, currs)
length(nbrs) == 0 && break
next = rand(rng, nbrs)
if next == prev
length(nbrs) == 1 && break
idnext = rand(rng, 1:(length(nbrs) - 1))
next = nbrs[idnext]
if next == prev
next = nbrs[end]
end
end
prev = currs
currs = next
end
return visited[1:(i - 1)]
end
"""
self_avoiding_walk(g, s, niter; rng=nothing, seed=nothing)
Perform a [self-avoiding walk](https://en.wikipedia.org/wiki/Self-avoiding_walk)
on graph `g` starting at vertex `s` and continuing for a maximum of `niter` steps.
Return a vector of vertices visited in order.
"""
function self_avoiding_walk(
g::AG,
s::Integer,
niter::Integer;
rng::Union{Nothing,AbstractRNG}=nothing,
seed::Union{Nothing,Integer}=nothing,
) where {AG<:AbstractGraph{T}} where {T}
s in vertices(g) || throw(BoundsError())
rng = rng_from_rng_or_seed(rng, seed)
visited = Vector{T}()
svisited = Set{T}()
sizehint!(visited, niter)
sizehint!(svisited, niter)
currs = s
i = 1
while i <= niter
push!(visited, currs)
push!(svisited, currs)
i += 1
nbrs = setdiff(Set(outneighbors(g, currs)), svisited)
length(nbrs) == 0 && break
currs = rand(rng, collect(nbrs))
end
return visited[1:(i - 1)]
end