Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Meta-ticket: make graphs compatible with Python 3 #26640

Closed
dcoudert opened this issue Nov 5, 2018 · 92 comments
Closed

Meta-ticket: make graphs compatible with Python 3 #26640

dcoudert opened this issue Nov 5, 2018 · 92 comments
Labels
c: graph theory c: python3 r: worksforme

Comments

@dcoudert
Copy link
Contributor

dcoudert commented Nov 5, 2018

This ticket is used to keep track of the progress towards python3 in graphs.

Major issues

  • Deprecate sorting of Graph vertices and edges by default #22349 Deprecate sorting of methods .vertices() and .edges()
  • direct comparison of vertex labels (e.g., in method iterator_edges of base/sparse_graph.pyx)
  • methods using matrices: adjacency_matrix, distance_matrix, etc. For all these methods, we can now give as input an ordering of the vertices (and edges) that will be used to order rows and columns. Currently, we use .vertices() and .edges() by default. If we switch to list(G) by default, we have to check that it's not breaking algorithms using these matrices.

Needs work:

Needs review:

Done

Optional packages:

With #27628, #27811, #27948, #28108 and #28371 all failing doctests of the optional packages used in the graph module are fixed: benzene, bliss, buckygen, csdp, dot2tex and graphviz, gap_packages, igraph and python_igraph, mcqd, plantri, tdlib

CC: @tscrim @fchapoton @jhpalmieri @jfraymond

Component: graph theory

Author: David Coudert

Reviewer: John Palmieri

Issue created by migration from https://trac.sagemath.org/ticket/26640
@dcoudert dcoudert added this to the sage-8.5 milestone Nov 5, 2018
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert
Copy link
Contributor Author

comment:4

I'm answering here the question of #26567#comment:9 about how to make iterator_edges of sparse_graph.pyx py3 compatible, and if something similar to #26567 for dense_graph.pyx can be done for sparse_graph.pyx.

So far, I don't know what's the best option.

  • just stop ordering end vertices of edges as well as vertices in general, but it shall break many algorithms
  • change the way we use graphs to ensure that internally vertices are all integers, and then use method get_vertex_label (that we already have but rarely use) only when the user wants to display lists of vertices/edges. I think networkx is now doing something like that.
  • try to mimic the py2 sorting using try... except statements, but this might induce some slowdown.
  • maintain an ordering of the vertices and a mapping from vertices to integers used when sorting list of vertices and the end vertices of edges. This ordering could be updated at vertex insertion/deletion time.

All these options have pros and cons, and each of them will require a significant amount of work to fix doctests and algorithms.

In the last months, we did significant progresses on reducing the dependency on ordering, but this is not enough and this central issue is very complex to fix. Which is the best option in the short/long term ?

@fchapoton

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@fchapoton
Copy link
Contributor

comment:9

May I ask in which ticket, if any, you do touch the "is_isomorphic" method ?

I would really like this to work with python 3:

sage: G = Graph()
sage: G.add_edge((1,'a'))
sage: G
Graph on 2 vertices
sage: G.is_isomorphic(G)

@dcoudert
Copy link
Contributor Author

dcoudert commented Dec 6, 2018

comment:10

I have not touched any method related to isomorphism. I have only opened a ticket to show a bug with canonical_label #26800.

@fchapoton
Copy link
Contributor

comment:11

ok.. Then either we wait for all these tickets to be closed (and this may take a lot of time) or we can try to fix this isomorphism problem now..

@dcoudert
Copy link
Contributor Author

dcoudert commented Dec 6, 2018

comment:12

We can start working on it. In the worst case, I will have to fix some merge conflicts.

@fchapoton
Copy link
Contributor

comment:13

I have made a first tentative at u/chapoton/graphe_iso

@dcoudert
Copy link
Contributor Author

dcoudert commented Dec 6, 2018

comment:14

I'm not good enough with git to know what you have changed, except the first 2 calls to .vertices(). It seems ok. Note that the function has 2 more calls to .vertices() that are clearly useless. I think the proposed change fix some doctests, so you should open a ticket.

@fchapoton
Copy link
Contributor

comment:15

I made #26846 for graph isomorphism

@fchapoton

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@fchapoton
Copy link
Contributor

comment:24

Salut !

@tscrim
Copy link
Collaborator

tscrim commented Mar 10, 2019

comment:68

Replying to @dcoudert:

An alternative is to (optionally) make spanning tree methods return a Graph, in which case there is no need to sort end vertices.

My gut reaction was that seems heavy handed. It would make sense, but I suspect the reason we don't is because it would be too expensive (relatively) to return a (Di)Graph. I haven't looked into this (it is too late for me to do so tonight), but just a thought.

@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert
Copy link
Contributor Author

comment:70

Some doctests are failing with bliss (not related to #27571)

sage -t src/sage/graphs/generators/families.py
**********************************************************************
File "src/sage/graphs/generators/families.py", line 3191, in sage.graphs.generators.families.MathonPseudocyclicStronglyRegularGraph
Failed example:
    G3x3.automorphism_group(algorithm="bliss").order() # optional - bliss
Expected:
    27
Got:
    3
**********************************************************************
File "src/sage/graphs/generators/families.py", line 3196, in sage.graphs.generators.families.MathonPseudocyclicStronglyRegularGraph
Failed example:
    G9.automorphism_group(algorithm="bliss").order() # optional - bliss
Expected:
    9
Got:
    3

@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert
Copy link
Contributor Author

comment:75

We are almost done. We have currently 3 open tickets for the remaining failing doctests.

Needs work (contributors are more than welcome):

Needs review / help / comment:

@dcoudert

This comment has been minimized.

Sign in to view
@jhpalmieri
Copy link
Member

comment:76

Replying to @dcoudert:

We are almost done. We have currently 3 open tickets for the remaining failing doctests.

Needs work (contributors are more than welcome):

For this one, I would be tempted to label it # py2 since it seems to rely on the legacy Sage notebook. I can open a ticket if that sounds like a valid approach.

@dcoudert
Copy link
Contributor Author

comment:77

For this one, I would be tempted to label it # py2 since it seems to rely on the legacy Sage notebook. I can open a ticket if that sounds like a valid approach.

It is related to sage notebook, but doctests are failing only with py3... So I don't know which is the best approach. Should we try to make a little change to sagenb to make #27435 fixing the issue, although sagenb will be removed in the future (but when?) ?

@jhpalmieri
Copy link
Member

comment:78

I apologize, my comments really belong on #27435. I'll continue the discussion there.

@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert
Copy link
Contributor Author

comment:79

All doctests in the standard graphs module are now fixed ! Thanks to all of you for your great help.

We can now check all optional packages. For instance, plantri has 2 failing doctests (#28108).

@dcoudert
Copy link
Contributor Author

comment:80

The last failing doctests of the optional packages (benzene, bliss, buckygen, csdp, dot2tex and graphviz, gap_packages, igraph and python_igraph, mcqd, plantri, tdlib) are fixed with #27948, #28108 and #28371.

@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert

This comment has been minimized.

Sign in to view
@dcoudert
Copy link
Contributor Author

comment:82

it's time to close this ticket.

@dcoudert
Copy link
Contributor Author

Author: David Coudert

@jhpalmieri
Copy link
Member

comment:83

Yes, I agree.

@jhpalmieri
Copy link
Member

Reviewer: John Palmieri

@fchapoton fchapoton removed the pending label Apr 20, 2020
@fchapoton fchapoton mentioned this issue Jan 1, 2020
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: graph theory c: python3 r: worksforme
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@embray @tscrim @jhpalmieri @fchapoton @dcoudert