`ne` fails to count the correct number of self-edges

[rodrigolece]

Hi! This is my first ever contribution to someone else's package on GiiHub so please bear with me :)

I've noticed the following:

julia> test = SimpleWeightedGraph(CompleteGraph(3))
{3, 3} undirected simple Int64 graph with Float64 weights

julia> ne(test)
3

julia> add_edge!(test, 1, 1, 10)
true

julia> ne(t)
3

The reason is simply the definition here is not meant to be used with self loops; it only works because non-self loops are double counted. I propose that

ne(g::SimpleWeightedGraph) = nnz(g.weights) ÷ 2

be changed to

ne(g::SimpleWeightedGraph) = nnz(triu(g.weights))

However, such a change breaks 3 of the test (I don't really understand why). When I run julia runtests.jl the output is

[ Info: Ignore warnings relating to adding and removing vertices and edges
┌ Warning: Note: adding edges with a zero weight to this graph type has no effect.
└ @ SimpleWeightedGraphs ~/.julia/packages/SimpleWeightedGraphs/yUFrc/src/simpleweightedgraph.jl:103
┌ Warning: Note: adding edges with a zero weight to this graph type has no effect.
└ @ SimpleWeightedGraphs ~/.julia/packages/SimpleWeightedGraphs/yUFrc/src/simpleweighteddigraph.jl:88
Overrides: Test Failed at /home/user/Documents/SimpleWeightedGraphs.jl/test/overrides.jl:21
  Expression: (weights(cartesian_product(g3, gz)))[11, 12] == (weights(gz))[3, 4]
   Evaluated: 1.0 == 87.0
Stacktrace:
 [1] macro expansion at /home/user/Documents/SimpleWeightedGraphs.jl/test/overrides.jl:21 [inlined]
 [2] macro expansion at /home/user/Documents/julia/usr/share/julia/stdlib/v1.0/Test/src/Test.jl:1083 [inlined]
 [3] top-level scope at /home/user/Documents/SimpleWeightedGraphs.jl/test/overrides.jl:2
Overrides: Test Failed at /home/user/Documents/SimpleWeightedGraphs.jl/test/overrides.jl:21
  Expression: (weights(cartesian_product(g3, gz)))[11, 12] == (weights(gz))[3, 4]
   Evaluated: 1.0 == 87.0
Stacktrace:
 [1] macro expansion at /home/user/Documents/SimpleWeightedGraphs.jl/test/overrides.jl:21 [inlined]
 [2] macro expansion at /home/user/Documents/julia/usr/share/julia/stdlib/v1.0/Test/src/Test.jl:1083 [inlined]
 [3] top-level scope at /home/user/Documents/SimpleWeightedGraphs.jl/test/overrides.jl:2
Overrides: Test Failed at /home/user/Documents/SimpleWeightedGraphs.jl/test/overrides.jl:21
  Expression: (weights(cartesian_product(g3, gz)))[11, 12] == (weights(gz))[3, 4]
   Evaluated: 1.0 == 87.0
Stacktrace:
 [1] macro expansion at /home/user/Documents/SimpleWeightedGraphs.jl/test/overrides.jl:21 [inlined]
 [2] macro expansion at /home/user/Documents/julia/usr/share/julia/stdlib/v1.0/Test/src/Test.jl:1083 [inlined]
 [3] top-level scope at /home/user/Documents/SimpleWeightedGraphs.jl/test/overrides.jl:2
┌ Warning: Saving compressed graphs is no longer supported in LightGraphs. Use `LGCompressedFormat()` from the `GraphIO.jl` package instead. Saving uncompressed.
│   caller = ip:0x0
└ @ Core :-1
┌ Warning: Saving compressed graphs is no longer supported in LightGraphs. Use `LGCompressedFormat()` from the `GraphIO.jl` package instead. Saving uncompressed.
│   caller = savegraph(::String, ::SimpleWeightedGraph{Int64,Float64}) at overrides.jl:56
└ @ SimpleWeightedGraphs ~/.julia/packages/SimpleWeightedGraphs/yUFrc/src/overrides.jl:56
Test Summary:          | Pass  Fail  Total
SimpleWeightedGraphs   |  349     3    352
  SimpleWeightedEdge   |   27           27
  SimpleWeightedGraphs |  251          251
  Overrides            |   48     3     51
  Persistence          |   14           14
  Connectivity         |    9            9
ERROR: LoadError: Some tests did not pass: 349 passed, 3 failed, 0 errored, 0 broken.
in expression starting at /home/user/Documents/SimpleWeightedGraphs.jl/test/runtests.jl:21

Ideas?

[sbromberger]

bump - cc @simonschoelly

[simonschoelly]

I haven't looked into why this bug happens yet, but I doubt that triu is the optional solution, as it allocates a new sparse matrix.

Possible solutions for this problem:

• Manually count the self-loops every time one calls nnz. Will use time O(n log n).
• Keep track of the number of self-loops - should be O(1) but has a small overhead for every mutation
• Keep track of the number of edges, as we do for SimpleGraph. Same as above
• Decide to ignore self-loops. Not sure if I like this.

[rodrigolece]

I would definitely be against ignoring self-edges. In many ways self-loops are just like any other edge (if dealt with carefully, for example following the convention that the adjacency matrix should have twice the weight of edges along the diagonal) and I'm almost sure that it will lead to unexpected behaviours.

I am in favour of one of the other options :)