sage icon indicating copy to clipboard operation
sage copied to clipboard
verified publisher icon sagemath

graphs: make init_short_digraph always sort neighbors but without the extra log complexity

Open cyrilbouvier opened this issue 1 year ago • 3 comments

This PR improve the init_short_digraph function that is used to initialize StaticSparseCGraph (used for immutable Graph and DiGraph).

Before, a boolean parameter sort_neighbors was used to specify if we wanted to sort the neighbors or not. It implied an extra log in the complexity (as qsort was called). With this PR, the neighbors are always sorted at no extra cost. It is done by appending to the neighbors list the vertices in the correct order so the call to qsort is not needed anymore.

This PR partly reverts #38198 and mostly reverts #37662

:memo: Checklist

  • [x] The title is concise and informative.
  • [x] The description explains in detail what this PR is about.
  • [ ] I have linked a relevant issue or discussion.
  • [x] I have created tests covering the changes.
  • [ ] I have updated the documentation and checked the documentation preview.

:hourglass: Dependencies

cyrilbouvier avatar Jul 26 '24 14:07 cyrilbouvier

Setting this PR to a draft: the doctests that I added to init_short_digraph requires that the vertices are not sorted before being passed to init_short_digraph as it is currently done in __init__ of StaticSparseBackend. I have a local commit that remove the vertices.sort() in StaticSparseBackend but it breaks one test in connectivity.pyx and I am not able to figure out why.

I have to:

  • either find another way to indirectly test init_short_digraph
  • or fix the doctests in connectivity.pyx when vertices are not sorted in StaticSparseBackend.

Note that the sorting of vertices in StaticSparseBackend probably invalidates most complexity claims of algorithms that rely on building Graph or DiGraph with immutable=True

cyrilbouvier avatar Jul 26 '24 14:07 cyrilbouvier

Documentation preview for this PR (built with commit 8627957dd56890efd4308b2e7ade513d40c7c4dd; changes) is ready! :tada: This preview will update shortly after each push to this PR.

github-actions[bot] avatar Jul 26 '24 15:07 github-actions[bot]

See issue #38527

cyrilbouvier avatar Aug 19 '24 10:08 cyrilbouvier

Failing doctest in graphs/connectivity.pyx will pass once PR #38535 is merged

cyrilbouvier avatar Aug 21 '24 07:08 cyrilbouvier

In 71113cd I start to fix some tests whose output where changed by bd63dd7 (where sort is remove from StaticSparseBackend).

First it is not an easy task as it touches lots of different fields (LieAlgebra, Poset, ...) that I am not familar with. But from what I understand, static graphs are used in these structures (for example the hasse_diagram attribute of Poset is a static digraph) and are the reason for the changes in the output. But maybe people more familiar with these objects should check my changes carefully.

Second, I hate tests whose output depend on internal representation of objects... :angry: (for example when the output is a list where the order does not matter but depends on the internal representation of the classes Graph and DiGraph). When possible I added sorted to avoid this problem. When it was not possible, I just changed the expected line of the doctests.

Special mention for the doctest of the method degree_on_basis in src/sage/algebras/lie_algebras/bgg_dual_module.py that never calls this method (so that is not a test for this method) but calls another method with the same name in src/sage/algebras/lie_algebras/verma_module.py. But I do not know what to do with this information.

cyrilbouvier avatar Aug 22 '24 13:08 cyrilbouvier

I fixed all tests except the two from graphs/connectivity.pyx which are fixed by PR #38535

This PR can now be reviewed.

cyrilbouvier avatar Aug 22 '24 14:08 cyrilbouvier

Changes are done. I also merge the latest develop branch. It should fix doctests in graphs/connectivity.pyx.

cyrilbouvier avatar Sep 04 '24 17:09 cyrilbouvier

On 32-bit I'm getting

**********************************************************************
File "src/sage/algebras/lie_algebras/bgg_dual_module.py", line 204, in sage.algebras.lie_algebras.bgg_dual_module.BGGDualModule.degree_on_basis
Failed example:
    elt = Mc.an_element(); elt
Expected:
    f[-alpha[2]]^2*f[-alpha[5]]^2*f[-alpha[3]]^3*v[Lambda[1]
     + Lambda[4] - 1/3*Lambda[5]]^* + 2*f[-alpha[2]]*v[Lambda[1]
     + Lambda[4] - 1/3*Lambda[5]]^* + 3*f[-alpha[5]]*v[Lambda[1]
     + Lambda[4] - 1/3*Lambda[5]]^* + v[Lambda[1] + Lambda[4]
     - 1/3*Lambda[5]]^*
Got:
    f[-alpha[1]]^2*f[-alpha[3]]^2*f[-alpha[2]]^3*v[Lambda[1] + Lambda[4] - 1/3*Lambda[5]]^* + 2*f[-alpha[1]]*v[Lambda[1] + Lambda[4] - 1/3*Lambda[5]]^* + 3*f[-alpha[3]]*v[Lambda[1] + Lambda[4] - 1/3*Lambda[5]]^* + v[Lambda[1] + Lambda[4] - 1/3*Lambda[5]]^*
**********************************************************************
File "src/sage/algebras/lie_algebras/bgg_dual_module.py", line 210, in sage.algebras.lie_algebras.bgg_dual_module.BGGDualModule.degree_on_basis
Failed example:
    [M.degree_on_basis(m) for m in elt.support()]
Expected:
    [3*Lambda[1] - Lambda[2] - 2*Lambda[3] + 4*Lambda[4] - 4/3*Lambda[5],
     Lambda[1] + Lambda[4] - 1/3*Lambda[5],
     2*Lambda[1] - 2*Lambda[2] + Lambda[3] + Lambda[4] - 1/3*Lambda[5],
     Lambda[1] + Lambda[3] + Lambda[4] - 7/3*Lambda[5]]
Got:
    [-2*Lambda[2] - Lambda[3] + 3*Lambda[4] + 5/3*Lambda[5],
     Lambda[1] + Lambda[4] - 1/3*Lambda[5],
     -Lambda[1] + Lambda[2] + Lambda[4] - 1/3*Lambda[5],
     Lambda[1] + Lambda[2] - 2*Lambda[3] + 2*Lambda[4] + 2/3*Lambda[5]]
**********************************************************************
File "src/sage/algebras/lie_algebras/bgg_dual_module.py", line 612, in sage.algebras.lie_algebras.bgg_dual_module.SimpleModuleIndices.__contains__
Failed example:
    gens = list(I.gens()); gens
Expected:
    [f[-alpha[2]],
     f[-alpha[1]],
     f[-alpha[1] - alpha[2]],
     f[-2*alpha[1] - alpha[2]],
     f[-3*alpha[1] - alpha[2]],
     f[-3*alpha[1] - 2*alpha[2]]]
Got:
    [f[-alpha[1]],
     f[-alpha[2]],
     f[-alpha[1] - alpha[2]],
     f[-2*alpha[1] - alpha[2]],
     f[-3*alpha[1] - alpha[2]],
     f[-3*alpha[1] - 2*alpha[2]]]
**********************************************************************
File "src/sage/algebras/lie_algebras/bgg_dual_module.py", line 619, in sage.algebras.lie_algebras.bgg_dual_module.SimpleModuleIndices.__contains__
Failed example:
    gens[1] in I
Expected:
    True
Got:
    False
**********************************************************************
File "src/sage/algebras/lie_algebras/bgg_dual_module.py", line 900, in sage.algebras.lie_algebras.bgg_dual_module.SimpleModule.lift
Failed example:
    [L.lift(b) for b in L.basis()]  # long time
Expected:
    [v[Lambda[1]]^*,
     f[-alpha[1]]*v[Lambda[1]]^*,
     f[-alpha[2]]*f[-alpha[1]]*v[Lambda[1]]^* - f[-alpha[1] - alpha[2]]*v[Lambda[1]]^*,
     f[-alpha[1]]*f[-alpha[1] - alpha[2]]*v[Lambda[1]]^*
      + f[-2*alpha[1] - alpha[2]]*v[Lambda[1]]^*,
     f[-alpha[1]]^2*f[-alpha[1] - alpha[2]]*v[Lambda[1]]^*
      + f[-alpha[1]]*f[-2*alpha[1] - alpha[2]]*v[Lambda[1]]^*
      + 1/2*f[-3*alpha[1] - alpha[2]]*v[Lambda[1]]^*,
     f[-alpha[2]]*f[-alpha[1]]^2*f[-alpha[1] - alpha[2]]*v[Lambda[1]]^*
      + f[-alpha[2]]*f[-alpha[1]]*f[-2*alpha[1] - alpha[2]]*v[Lambda[1]]^*
      + 1/2*f[-alpha[2]]*f[-3*alpha[1] - alpha[2]]*v[Lambda[1]]^*
      - f[-alpha[1] - alpha[2]]*f[-2*alpha[1] - alpha[2]]*v[Lambda[1]]^*
      + 1/2*f[-3*alpha[1] - 2*alpha[2]]*v[Lambda[1]]^*,
     f[-alpha[1]]*f[-alpha[1] - alpha[2]]*f[-2*alpha[1] - alpha[2]]*v[Lambda[1]]^*
      - 1/2*f[-alpha[1]]*f[-3*alpha[1] - 2*alpha[2]]*v[Lambda[1]]^*
      - 1/2*f[-alpha[1] - alpha[2]]*f[-3*alpha[1] - alpha[2]]*v[Lambda[1]]^*
      + f[-2*alpha[1] - alpha[2]]^2*v[Lambda[1]]^*]
Got:
    [v[Lambda[1]]^*,
     f[-alpha[1]]*v[Lambda[1]]^*,
     f[-alpha[1] - alpha[2]]*v[Lambda[1]]^*,
     f[-alpha[1]]*f[-alpha[1] - alpha[2]]*v[Lambda[1]]^* + f[-2*alpha[1] - alpha[2]]*v[Lambda[1]]^*,
     f[-alpha[1]]^2*f[-alpha[1] - alpha[2]]*v[Lambda[1]]^* + f[-alpha[1]]*f[-2*alpha[1] - alpha[2]]*v[Lambda[1]]^* + 1/2*f[-3*alpha[1] - alpha[2]]*v[Lambda[1]]^*,
     f[-alpha[2]]*f[-3*alpha[1] - alpha[2]]*v[Lambda[1]]^* - 2*f[-alpha[1] - alpha[2]]*f[-2*alpha[1] - alpha[2]]*v[Lambda[1]]^* + f[-3*alpha[1] - 2*alpha[2]]*v[Lambda[1]]^*,
     f[-alpha[1]]*f[-alpha[2]]*f[-3*alpha[1] - alpha[2]]*v[Lambda[1]]^* - 2*f[-alpha[1]]*f[-alpha[1] - alpha[2]]*f[-2*alpha[1] - alpha[2]]*v[Lambda[1]]^* + f[-alpha[1]]*f[-3*alpha[1] - 2*alpha[2]]*v[Lambda[1]]^* + f[-alpha[1] - alpha[2]]*f[-3*alpha[1] - alpha[2]]*v[Lambda[1]]^* - 2*f[-2*alpha[1] - alpha[2]]^2*v[Lambda[1]]^*]
**********************************************************************
3 items had failures:
   2 of   7 in sage.algebras.lie_algebras.bgg_dual_module.BGGDualModule.degree_on_basis
   1 of   5 in sage.algebras.lie_algebras.bgg_dual_module.SimpleModule.lift
   2 of  14 in sage.algebras.lie_algebras.bgg_dual_module.SimpleModuleIndices.__contains__
    [265 tests, 5 failures, 26.58 s]
**********************************************************************
File "src/sage/algebras/lie_algebras/lie_algebra_element.pyx", line 967, in sage.algebras.lie_algebras.lie_algebra_element.UntwistedAffineLieAlgebraElement._repr_generic
Failed example:
    elt._repr_generic(str, str, lambda t: "T^{}".format(t), '.', '(x)')
Expected:
    '(E[alpha[3]] + E[alpha[2]] + E[alpha[1]] + h1 + h2 + h3 + E[-alpha[3]]
     + E[-alpha[2]] + E[-alpha[1]])(x)T^0 + (E[-alpha[1] - 2*alpha[2]
     - 2*alpha[3]])(x)T^1 + (E[alpha[1] + 2*alpha[2] + 2*alpha[3]])(x)T^-1 + c + d'
Got:
    '(E[alpha[1]] + E[alpha[3]] + E[alpha[2]] + h1 + h2 + h3 + E[-alpha[1]] + E[-alpha[3]] + E[-alpha[2]])(x)T^0 + (E[-alpha[1] - 2*alpha[2] - 2*alpha[3]])(x)T^1 + (E[alpha[1] + 2*alpha[2] + 2*alpha[3]])(x)T^-1 + c + d'
**********************************************************************
1 item had failures:
   1 of   4 in sage.algebras.lie_algebras.lie_algebra_element.UntwistedAffineLieAlgebraElement._repr_generic
    [463 tests, 1 failure, 1.23 s]
**********************************************************************
File "src/sage/algebras/lie_algebras/poincare_birkhoff_witt.py", line 545, in sage.algebras.lie_algebras.poincare_birkhoff_witt.PoincareBirkhoffWittBasis.casimir_element
Failed example:
    C = U.casimir_element(); C
Expected:
    1/4*PBW[alpha[2]]*PBW[-alpha[2]] + 1/12*PBW[alpha[1]]*PBW[-alpha[1]]
     + 1/12*PBW[alpha[1] + alpha[2]]*PBW[-alpha[1] - alpha[2]] + 1/12*PBW[2*alpha[1] + alpha[2]]*PBW[-2*alpha[1] - alpha[2]]
     + 1/4*PBW[3*alpha[1] + alpha[2]]*PBW[-3*alpha[1] - alpha[2]]
     + 1/4*PBW[3*alpha[1] + 2*alpha[2]]*PBW[-3*alpha[1] - 2*alpha[2]]
     + 1/12*PBW[alphacheck[1]]^2 + 1/4*PBW[alphacheck[1]]*PBW[alphacheck[2]]
     + 1/4*PBW[alphacheck[2]]^2 - 5/12*PBW[alphacheck[1]] - 3/4*PBW[alphacheck[2]]
Got:
    1/12*PBW[alpha[1]]*PBW[-alpha[1]] + 1/4*PBW[alpha[2]]*PBW[-alpha[2]] + 1/12*PBW[alpha[1] + alpha[2]]*PBW[-alpha[1] - alpha[2]] + 1/12*PBW[2*alpha[1] + alpha[2]]*PBW[-2*alpha[1] - alpha[2]] + 1/4*PBW[3*alpha[1] + alpha[2]]*PBW[-3*alpha[1] - alpha[2]] + 1/4*PBW[3*alpha[1] + 2*alpha[2]]*PBW[-3*alpha[1] - 2*alpha[2]] + 1/12*PBW[alphacheck[1]]^2 + 1/4*PBW[alphacheck[1]]*PBW[alphacheck[2]] + 1/4*PBW[alphacheck[2]]^2 - 5/12*PBW[alphacheck[1]] - 3/4*PBW[alphacheck[2]]
**********************************************************************
1 item had failures:
   1 of   8 in sage.algebras.lie_algebras.poincare_birkhoff_witt.PoincareBirkhoffWittBasis.casimir_element
    [176 tests, 1 failure, 5.25 s]
**********************************************************************
File "src/sage/algebras/lie_algebras/verma_module.py", line 1356, in sage.algebras.lie_algebras.verma_module.VermaModuleHomset.singular_vector
Failed example:
    v = H.singular_vector(); v
Expected:
    f[-alpha[2]]*f[-alpha[1]]^3*v[Lambda[1] - Lambda[3]]
     + 3*f[-alpha[1]]^2*f[-alpha[1] - alpha[2]]*v[Lambda[1] - Lambda[3]]
Got:
    f[-alpha[1]]^3*f[-alpha[2]]*v[Lambda[1] - Lambda[3]]
**********************************************************************
1 item had failures:
   1 of  47 in sage.algebras.lie_algebras.verma_module.VermaModuleHomset.singular_vector
    [422 tests, 1 failure, 3.91 s]
**********************************************************************
File "src/sage/algebras/lie_conformal_algebras/lie_conformal_algebra_element.py", line 170, in sage.algebras.lie_conformal_algebras.lie_conformal_algebra_element.LCAStructureCoefficientsElement._repr_
Failed example:
    R.2.T()+3*R.3
Expected:
    TB[alpha[1]] + 3*B[alpha[2] + alpha[3]]
Got:
    TB[alpha[2]] + 3*B[alpha[1] + alpha[2]]
**********************************************************************
1 item had failures:
   1 of   7 in sage.algebras.lie_conformal_algebras.lie_conformal_algebra_element.LCAStructureCoefficientsElement._repr_
    [31 tests, 1 failure, 0.39 s]
**********************************************************************
File "src/sage/algebras/lie_algebras/classical_lie_algebra.py", line 1999, in sage.algebras.lie_algebras.classical_lie_algebra.LieAlgebraChevalleyBasis.degree_on_basis
Failed example:
    [L.degree_on_basis(m) for m in L.basis().keys()]
Expected:
    [alpha[2], alpha[1], alpha[1] + alpha[2],
     2*alpha[1] + alpha[2], 3*alpha[1] + alpha[2],
     3*alpha[1] + 2*alpha[2],
     0, 0,
     -alpha[2], -alpha[1], -alpha[1] - alpha[2],
     -2*alpha[1] - alpha[2], -3*alpha[1] - alpha[2],
     -3*alpha[1] - 2*alpha[2]]
Got:
    [alpha[1],
     alpha[2],
     alpha[1] + alpha[2],
     2*alpha[1] + alpha[2],
     3*alpha[1] + alpha[2],
     3*alpha[1] + 2*alpha[2],
     0,
     0,
     -alpha[1],
     -alpha[2],
     -alpha[1] - alpha[2],
     -2*alpha[1] - alpha[2],
     -3*alpha[1] - alpha[2],
     -3*alpha[1] - 2*alpha[2]]
**********************************************************************
1 item had failures:
   1 of   3 in sage.algebras.lie_algebras.classical_lie_algebra.LieAlgebraChevalleyBasis.degree_on_basis
    [291 tests, 1 failure, 420.21 s]
**********************************************************************
File "src/sage/categories/regular_crystals.py", line 841, in sage.categories.regular_crystals.RegularCrystals.ElementMethods.dual_equivalence_class
Failed example:
    G.edges(sort=True,sort_vertices=True)
Expected:
    [([[1, 3, 4], [2, 5]], [[1, 3, 5], [2, 4]], 4),
     ([[1, 3, 4], [2, 5]], [[1, 2, 4], [3, 5]], 2),
     ([[1, 2, 5], [3, 4]], [[1, 3, 5], [2, 4]], 2),
     ([[1, 2, 5], [3, 4]], [[1, 3, 5], [2, 4]], 3),
     ([[1, 2, 3], [4, 5]], [[1, 2, 4], [3, 5]], 3),
     ([[1, 2, 3], [4, 5]], [[1, 2, 4], [3, 5]], 4)]
Got:
    [([[1, 3, 5], [2, 4]], [[1, 2, 5], [3, 4]], 2), ([[1, 3, 5], [2, 4]], [[1, 2, 5], [3, 4]], 3), ([[1, 3, 4], [2, 5]], [[1, 3, 5], [2, 4]], 4), ([[1, 3, 4], [2, 5]], [[1, 2, 4], [3, 5]], 2), ([[1, 2, 3], [4, 5]], [[1, 2, 4], [3, 5]], 3), ([[1, 2, 3], [4, 5]], [[1, 2, 4], [3, 5]], 4)]
**********************************************************************
1 item had failures:
   1 of   7 in sage.categories.regular_crystals.RegularCrystals.ElementMethods.dual_equivalence_class
    [127 tests, 1 failure, 0.24 s]
**********************************************************************
File "src/sage/combinat/posets/poset_examples.py", line 1491, in sage.combinat.posets.poset_examples.Posets.YoungsLatticePrincipalOrderIdeal
Failed example:
    P.cover_relations()
Expected:
    [[[], [1]],
     [[1], [1, 1]],
     [[1], [2]],
     [[1, 1], [2, 1]],
     [[2], [2, 1]],
     [[2, 1], [2, 2]]]
Got:
    [[[], [1]],
     [[1], [2]],
     [[1], [1, 1]],
     [[2], [2, 1]],
     [[1, 1], [2, 1]],
     [[2, 1], [2, 2]]]
**********************************************************************
1 item had failures:
   1 of   4 in sage.combinat.posets.poset_examples.Posets.YoungsLatticePrincipalOrderIdeal
    [181 tests, 1 failure, 3.24 s]
----------------------------------------------------------------------
sage -t --long --random-seed=0 src/sage/algebras/lie_algebras/bgg_dual_module.py  # 5 doctests failed
sage -t --long --random-seed=0 src/sage/algebras/lie_algebras/lie_algebra_element.pyx  # 1 doctest failed
sage -t --long --random-seed=0 src/sage/algebras/lie_algebras/poincare_birkhoff_witt.py  # 1 doctest failed
sage -t --long --random-seed=0 src/sage/algebras/lie_algebras/verma_module.py  # 1 doctest failed
sage -t --long --random-seed=0 src/sage/algebras/lie_conformal_algebras/lie_conformal_algebra_element.py  # 1 doctest failed
sage -t --long --random-seed=0 src/sage/algebras/lie_algebras/classical_lie_algebra.py  # 1 doctest failed
sage -t --long --random-seed=0 src/sage/categories/regular_crystals.py  # 1 doctest failed
sage -t --long --random-seed=0 src/sage/combinat/posets/poset_examples.py  # 1 doctest failed
----------------------------------------------------------------------

vbraun avatar Sep 08 '24 08:09 vbraun

@vbraun I really do not know what to do about these tests. Were they passing before the PR ?

For example the first one in your list check the return value of a method an_element() which seems to return a different value on 32 and 64 architectures. I did not write this test, I just modified it because the output was dependent on the internal representation of the Graph class (changed by this PR). But I know nothing about Lie algebras and I do not know how to fix it.

cyrilbouvier avatar Sep 10 '24 11:09 cyrilbouvier

the doctest in src/sage/combinat/posets/poset_examples.py can be fixed with a sort. For the other ones, we can call for help on sage-level.

dcoudert avatar Sep 10 '24 11:09 dcoudert

Test were passing before this PR

If an_element returns different values you can just use the # 64 bit / # 32 bit markers, and then run subsequent test with a particular element.

Together with sorting output this would probably fix most

vbraun avatar Sep 10 '24 20:09 vbraun

the doctest in src/sage/combinat/posets/poset_examples.py can be fixed with a sort. For the other ones, we can call for help on sage-level.

done in 23494ba

For the tests in "src/sage/categories/regular_crystals.py", line 841, I think this is due to a bug in the class EdgesView of graphs: the tests asks for the vertices to be sorted G.edges(sort=True,sort_vertices=True) But the first returned edge is not sorted

u, v, _ = ([[1, 3, 5], [2, 4]], [[1, 2, 5], [3, 4]], 2)
u < v  # should be True
False

Can someone confirm ?

Edit: Something unclear is happening with sort_vertices: it can sort uncomparable items

sage: H = Graph([[1, 'a'],[ (1, 'a')]])
sage: H.edges(sort_vertices=True)
[(1, 'a', None)]

If sorting were really performed, an exception should have been raised. I suspect that the sorting is done based on the indexes of the vertices in the internal representation of the graph.

I am looking into the others.

cyrilbouvier avatar Sep 11 '24 07:09 cyrilbouvier

Commit 8627957 should fix the remaining tests.

I used ... # 32-bit to disabled tests that I could not fix immediatly with a sort. If it is not an accepted way of dealing with these problems and it prevent this PR to be merged, so be it, but I will not spend hours fixing badly written tests* in a part of SageMath I know nothing about and implementing math I do not understand.

(*) the failing tests relies an the fact that an element returned by the an_element method is always the same but the returned element depends in fact of the internal representation of object in a completly different part of SageMath.

For me the remaining problem is the failing doctest in "src/sage/categories/regular_crystals.py". But as I say earlier I suspect a bug in EdgesView. If it is confirm, I can open a ticket for this bug, but I will not try to fix it in this PR.

cyrilbouvier avatar Sep 11 '24 08:09 cyrilbouvier

Edit: Something unclear is happening with sort_vertices: it can sort uncomparable items

sage: H = Graph([[1, 'a'],[ (1, 'a')]])
sage: H.edges(sort_vertices=True)
[(1, 'a', None)]

If sorting were really performed, an exception should have been raised. I suspect that the sorting is done based on the indexes of the vertices in the internal representation of the graph.

I am looking into the others.

in src/sage/graphs/base/sparse_graph.pyx, method _reorganize_edge, there is a try...except that tries to compare vertices and in case of failure silently pass. so we can also get

sage: sage: H = Graph([[0, 1, 2, 'a'],[ ('a', 1)]])
....: sage: H.edges(sort_vertices=True)
[('a', 1, None)]

I don't know what to do here.

dcoudert avatar Sep 11 '24 09:09 dcoudert

I will close this PR and open a new one with less changes to avoid all the breaking doctests. Mainly I will remove commit bd63dd712e916d5dd083a9933e3 which removes 4 lines in StaticSparseBackend code that sort the vertices before creating the graph. I still think this behaviour is a bug (sorting vertices of all immutable graphs should not be the default.), and I will open a ticket to document it but I will not try to fix it myself.

cyrilbouvier avatar Sep 16 '24 13:09 cyrilbouvier

I agree, it's best to have a PR dedicated to the change in StaticSparseBackend and in method _reorganize_edge (which should raise an error when types are incomparable.

dcoudert avatar Sep 16 '24 13:09 dcoudert