Greatly speed up equality check of equal graphs

[novoselt]

The current code goes over all vertex pairs and checks existence of all possible edges, which is extremely inefficient for, say, posets, whose graphs are far from complete. This is a big problem when mixed with unique representation of finite posets.

So let's iterate over edges directly.

CC: @fchapoton @nathanncohen

Component: graph theory

Author: Andrey Novoseltsev

Branch/Commit: 959c85d

Reviewer: Jori Mäntysalo, Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/19077

[novoselt]

Branch: u/novoselt/graph_eq

[novoselt]

comment:2

I've run into this problem while profiling code I am working on (face lattice posets for reflexive polytopes). First run:

 13550671 function calls (13542023 primitive calls) in 73.684 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     4319   10.815    0.003   66.951    0.016 hasse_diagram.py:24(Hasse_diagram_from_incidences)
    21595    7.663    0.000   25.948    0.001 digraph.py:468(__init__)
  1510140    6.001    0.000    7.231    0.000 {method 'add_edge' of 'sage.graphs.base.sparse_graph.SparseGraphBackend' objects}
   148526    4.442    0.000    6.108    0.000 lattice_polytope.py:527(__eq__)
     4319    3.730    0.001   73.397    0.017 lattice_polytope.py:1822(face_lattice)
17276/12957    3.532    0.000   20.710    0.002 generic_graph.py:19289(relabel)
    17276    3.364    0.000   10.626    0.001 generic_graph.py:9865(add_edges)
   946746    2.268    0.000    2.268    0.000 {hash}
  1765714    2.156    0.000    2.156    0.000 toric_lattice.py:922(ambient_module)
  1397396    2.030    0.000    2.030    0.000 {method 'intersection' of 'frozenset' objects}

second run recreating the same posets:

 58955399 function calls in 216.966 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  9250954   46.562    0.000   63.004    0.000 lattice_polytope.py:527(__eq__)
 13056672   43.472    0.000  101.665    0.000 {method 'has_edge' of 'sage.graphs.base.static_sparse_backend.StaticSparseBackend' objects}
 13056672   38.784    0.000  140.449    0.000 generic_graph.py:10290(has_edge)
     4319   23.099    0.005  166.699    0.039 generic_graph.py:392(__eq__)
  9320064   11.157    0.000   11.157    0.000 {isinstance}
     4319   10.888    0.003  210.421    0.049 hasse_diagram.py:24(Hasse_diagram_from_incidences)
  4996396    6.084    0.000    6.084    0.000 toric_lattice.py:922(ambient_module)
     4319    3.726    0.001  216.860    0.050 lattice_polytope.py:1822(face_lattice)
     8638    3.073    0.000   11.644    0.001 digraph.py:468(__init__)
   604056    2.673    0.000    3.296    0.000 {method 'add_edge' of 'sage.graphs.base.sparse_graph.SparseGraphBackend' objects}
     8638    2.391    0.000    6.914    0.001 generic_graph.py:19295(relabel)
   807792    2.049    0.000    2.049    0.000 {hash}
  1397396    2.013    0.000    2.013    0.000 {method 'intersection' of 'frozenset' objects}

after my change the second run becomes

13591197 function calls in 61.236 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     4319   10.819    0.003   54.643    0.013 hasse_diagram.py:24(Hasse_diagram_from_incidences)
   939270    5.871    0.000    8.093    0.000 lattice_polytope.py:527(__eq__)
     4319    3.766    0.001   61.136    0.014 lattice_polytope.py:1822(face_lattice)
     8638    3.065    0.000   11.563    0.001 digraph.py:468(__init__)
   604056    2.653    0.000    3.282    0.000 {method 'add_edge' of 'sage.graphs.base.sparse_graph.SparseGraphBackend' objects}
     8638    2.366    0.000    6.870    0.001 generic_graph.py:19289(relabel)
   807792    2.045    0.000    2.045    0.000 {hash}
  1397396    2.007    0.000    2.007    0.000 {method 'intersection' of 'frozenset' objects}
   302028    1.833    0.000    5.092    0.000 {method 'has_edge' of 'sage.graphs.base.static_sparse_backend.StaticSparseBackend' objects}
  1436908    1.760    0.000    1.760    0.000 toric_lattice.py:922(ambient_module)

so there is actually speed gain due to posets being stored...

---

New commits:

6e83ae0

Speed up equality check of graphs with no multiple edges.

[novoselt]

Commit: 6e83ae0

[novoselt]

Author: Andrey Novoseltsev

[jm58660]

comment:4

I can review this.

Just a side note: why test self.weighted() != other.weighted() is after any(x not in other for x in self)? Seems unlogical exception to rule of having most easy tests first.

[jm58660]

Reviewer: Jori Mäntysalo

[jm58660]

comment:5

Speedup confirmed. After P7 = Posets(7).list() the command P=Posets.ChainPoset(7) took about 635 microseconds, after this patch it takes about 540 microseconds. I ran the test on i5-3470 @ 3.20GHz.

You can mark this as positive_review. Or if you want, check my comment above.

[nathanncohen]

comment:6

Just a note: if you ever want more speed than that for posets, it is possible to get it. Posets are stored internally as 'static sparse graphs', and that can be done in linear time (~m) instead of ~mlog(n) here.

That speedup with be small, however, compared to this one.

Nathann

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

536c481

Further clean up of graph equality.

[sagetrac-git]

Changed commit from 6e83ae0 to 536c481