I am using LightGraphs.jl to implement a fast SIR algorithm, which I have done. However, I am now trying to improve the timings. In the course of investigating, I find that `neighbors(g, v)`

allocates memory (I used `@time`

to determine this). So I went into the `LightGraphs.jl`

source code.

In method `SimpleGraphsCore//SimpleGraphsCore.jl`

, I find that

```
outneighbors(g::AbstractSimpleGraph, v::Integer) = fadj(g, v)
```

and that the `neighbors`

function is really a call to `outneighbors`

.

So my question: when does the memory allocation occur? The adjacency matrix is obviously preallocated unless `fadj`

is a function. Ok. In the same file, I find that

```
fadj(g::AbstractSimpleGraph) = g.fadjlist
fadj(g::AbstractSimpleGraph, v::Integer) = g.fadjlist[v]
```

It is still not clear to me where the memory allocation occurs. Given the presence of `pop!(g.fadjlist)`

in the same file, it appears that we are dealing with a linked list or similar structure.

In `SimpleGraphsCore/simpledigraph.jl`

, I found functions

```
function SimpleDiGraph{T}(n::Integer=0) where {T<:Integer}
fadjlist = [Vector{T}() for _ = one(T):n]
badjlist = [Vector{T}() for _ = one(T):n]
return SimpleDiGraph(0, fadjlist, badjlist)
end
This routine does not preallocate space for neighbors, but rather prepares a list unfilled vectors "just in case" neighbors are called for.
So when using `push!` On `fadjlist`, I assume allocation is made either for an integer or a reference to a structure. There are two costs: 1) the cost of performing the allocation, and 2) the cost of transferring data to the allocated memory.
I also found the longer routine in `SimpleGraphsCore/simpledigraph.jl`, but I am doubtful it is called when wanting to just give the neighbors of a given vertex:
```

function all_neighbors(g::SimpleDiGraph{T}, u::Integer) where {T}

union_nbrs = Vector{T}()

i, j = 1, 1

in_nbrs, out_nbrs = inneighbors(g, u), outneighbors(g, u)

in_len, out_len = length(in_nbrs), length(out_nbrs)

while i <= in_len && j <= out_len

if in_nbrs[i] < out_nbrs[j]

push!(union_nbrs, in_nbrs[i])

i += 1

elseif in_nbrs[i] > out_nbrs[j]

push!(union_nbrs, out_nbrs[j])

j += 1

else

push!(union_nbrs, in_nbrs[i])

i += 1

j += 1

end

end

while i <= in_len

push!(union_nbrs, in_nbrs[i])

i += 1

end

while j <= out_len

push!(union_nbrs, out_nbrs[j])

j += 1

end

return union_nbrs

end

```
I guess my question is: if the fadjlist is computed regardless of whether I invoke the `neighbors(g,i)` function, where is the memory allocation performed. I am still confused. Thanks.
Gordon
```