Opened 11 months ago

Last modified 8 days ago

#26640 new task

Meta-ticket: make graphs compatible with Python 3 — at Version 15

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-pending
Component: graph theory Keywords: py3, graph
Cc: tscrim, chapoton, jhpalmieri, gh-jfraymond Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by chapoton)

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

Major issues

  • methods .vertices() and .edges() use sort by default
  • direct comparison of vertex labels (e.g., in method iterator_edges of base/sparse_graph.pyx)
  • all min_spanning_tree methods sort edges before returning the result

Needs work:

  • #26800 py3: bug with canonical_label

Needs review:

Done

  • #26274 avoid comparison of vertex labels in MIP - graph_coloring.py
  • #26282 avoid comparison of vertex labels in MIP - graph.py
  • #26284 avoid comparison of vertex labels in MIP - connectivity.pyx
  • #26285 avoid comparison of vertex labels in MIP - generic_graph.py
  • #26469 avoid sorting vertex labels in graph_plot.py
  • #26484 clean graph_coloring.py and avoid comparison of vertex labels
  • #26528 avoid using .vertices() in comparability, hyperbolicity and distances_all_pairs
  • #26531 avoid using .vertices() in asteroidal_triples
  • #26534 avoid using .vertices() in weakly_chordal.pyx
  • #26554 improve the boost graph interface to avoid using .vertices()
  • #26618 avoid using .vertices() in centrality.pyx
  • #26621 avoid using .vertices() and .edges() in bliss.pyx
  • #26622 avoid using .vertices() in convexity_properties.pyx
  • #26633 clean generic_graph.py (part 4)
  • #26680 clean generic_graph.py (part 14) - visualization
  • #26711 avoid .vertices() in graph_coloring.py
  • #26712 avoid .vertices() in independent_sets.pyx
  • #26757 py3: fixing round in graph_latex.py
  • #26761 py3: fix BlanusaSecondSnarkGraph
  • #26762 py3: fix HortonGraph generator
  • #26763 py3: fix SzekeresSnarkGraph generator
  • #26801 py3: change sorting of neighbors labels in static_sparse_graph.pyx

Change History (15)

comment:1 Changed 11 months ago by dcoudert

  • Description modified (diff)

comment:2 Changed 11 months ago by dcoudert

  • Description modified (diff)

comment:3 Changed 11 months ago by chapoton

  • Component changed from group theory to graph theory

comment:4 Changed 10 months ago by dcoudert

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 ?

comment:5 Changed 10 months ago by chapoton

  • Description modified (diff)

comment:6 Changed 10 months ago by dcoudert

  • Description modified (diff)

comment:7 Changed 10 months ago by dcoudert

  • Description modified (diff)

comment:8 Changed 10 months ago by dcoudert

  • Description modified (diff)

comment:9 Changed 10 months ago by chapoton

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)
Last edited 10 months ago by chapoton (previous) (diff)

comment:10 Changed 10 months ago by dcoudert

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

comment:11 Changed 10 months ago by chapoton

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..

comment:12 Changed 10 months ago by dcoudert

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

comment:13 Changed 10 months ago by chapoton

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

comment:14 Changed 10 months ago by dcoudert

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.

comment:15 Changed 10 months ago by chapoton

  • Description modified (diff)

I made #26846 for graph isomorphism

Note: See TracTickets for help on using tickets.