[BUG] Intermittently-failing tests in Parallel.Closeness

[mattwigway]

Description of bug I saw several Parallel.Closeness tests fail with a message like the one below, but cannot reproduce now. I think it has to do with an uninitialized value in an array (see below). I have only seen it on the branch where I was development #1554, but I think it is unrelated.

Parallel.Closeness: Test Failed at /Users/matthewc/git/LightGraphs.jl/test/parallel/centrality/closeness.jl:9
  Expression: ty ≈ [0.75, 0.6666666666666666, 1.0, 0.0]
   Evaluated: [0.75, 0.6666666666666666, 1.0, NaN] ≈ [0.75, 0.6666666666666666, 1.0, 0.0]

How to reproduce I cannot reproduce the behavior reliably.

Expected behavior Test should reliably pass.

Actual behavior Test occasionally fails.

Version information

• output from versioninfo() surrounded by backticks (``)
• output from ] status LightGraphs surrounded by backticks (``)

Additional context I think what is happening is that there is this code starting at line 40 of closeness.jl:

        if degree(g, u) == 0     # no need to do Dijkstra here
            closeness[u] = 0.0
        else
            d = LightGraphs.dijkstra_shortest_paths(g, u, distmx).dists
            δ = filter(x -> x != typemax(x), d)
            σ = sum(δ)
            l = length(δ) - 1
            if σ > 0
                closeness[u] = l / σ
                if normalize
                    n = l * 1.0 / (n_v - 1)
                    closeness[u] *= n
                end
            end
        end

If the edge has zero degree, then closeness short-circuits and sets closeness to 0.0. If it has non-zero degree, it performs a shortest path search and counts the number of nodes reached. Otherwise, if >= 1 node was reached then it computes the centrality. However, if degree > 0 and number of nodes reached == 0, then the closeness will not be set, and that element of the array will remain undef. This is exactly the situation we have with vertex 4 (which is the vertex causing the test failure), because the graph used in the test looks like this:

1 -> 2 -> 3 -> 4
|         ^
+---------+

Vertex 4 has degree 1 but outdegree 0, so nothing is reached in the path search. I think that degree on line 40 should be replaced with outdegree, and/or there should be an else clause for when a path search was performed but nothing was reached.

In my testing, undef seems to usually be pretty close to zero, which is probably why the test usually works.

[sbromberger]

Great catch. I think we can fix this by adding an else branch to the if \sigma > 0 condition:

else
    closeness[u] = 0

[mattwigway]

That should work and may also handle a case where there is an edge but it's weight is so high that nothing is reachable.

On Fri, Apr 2, 2021, 5:38 PM Seth Bromberger @.***> wrote:

Great catch. I think we can fix this by adding an else branch to the if \sigma > 0 condition:

else closeness[u] = 0

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/JuliaGraphs/LightGraphs.jl/issues/1555#issuecomment-812726521, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAEKNLQQ4U3UFL2RGQYOAMTTGY2OHANCNFSM42JOLSLQ .