Skip to content
This repository was archived by the owner on Oct 8, 2021. It is now read-only.

ne fails to count the correct number of self-edges #41

Open
rodrigolece opened this issue Dec 10, 2018 · 3 comments · May be fixed by #73
Open

ne fails to count the correct number of self-edges #41

rodrigolece opened this issue Dec 10, 2018 · 3 comments · May be fixed by #73

Comments

@rodrigolece
Copy link

rodrigolece commented Dec 10, 2018 •
edited
Loading

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
Copy link
Owner

bump - cc @simonschoelly

@simonschoelly
Copy link

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
Copy link
Author

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 :)

@rodrigolece rodrigolece mentioned this issue Oct 10, 2019
Closed
@ghost ghost mentioned this issue Mar 7, 2021
Closed
@yuehhua yuehhua mentioned this issue Aug 25, 2021
Closed
@yuehhua yuehhua linked a pull request Sep 29, 2021 that will close this issue
Open
@gdalle gdalle mentioned this issue Nov 11, 2021
Closed
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix ne for self-loops
3 participants
@sbromberger @simonschoelly @rodrigolece