Meta-ticket: make graphs compatible with Python 3

[dcoudert]

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 - #26940 is attempt to stop sorting returned list of edges

Needs work:

• #26800 py3: bug with canonical_label

Needs review:

• #26520 Meta-ticket for methods in src/sage/graphs/graph_decomposition/ - #26827, #26828, #26829, #26830, #26831, #26832, #26833, #26834
• #26678 clean generic_graph.py (part 12) - meta-ticket for methods related to clustering, centrality and distances. Tickets are #26803, #26813, #26814, #26815, #26819, #26820, #26821, #26822, #26823, #26824, #26825, #26826
• #26679 clean generic_graph.py (part 13) - searches and constructors
• #27059 py3: improve doctests in spanning_tree.pyx
• #27123 bliss automorphism_group() shouldn't sort vertices
• #27125 py3: fix some doctests in graph.py
• #27127 py3: avoid .vertices() in method ear_decomposition

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
• #26478 clean graph_plot_js.py, graph_list.py and graph_input.py
• #26480 clean graph_latex.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
• #26624 clean generic_graph.py (part 1)
• #26627 clean generic_graph.py (part 2)
• #26630 clean generic_graph.py (part 3)
• #26633 clean generic_graph.py (part 4)
• #26634 clean generic_graph.py (part 5)
• #26637 clean generic_graph.py (part 6)
• #26658 clean generic_graph.py (part 7) - planarity
• #26663 clean generic_graph.py (part 8) - connectivity
• #26666 clean generic_graph.py (part 9) - edge and vertex handlers
• #26672 clean generic_graph.py (part 10) - degree
• #26675 clean generic_graph.py (part 11) - substructures
• #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
• #26779 py3: fix graph_input.py and hypergraph_generators.py
• #26801 py3: change sorting of neighbors labels in static_sparse_graph.pyx
• #26812 py3: fix doctest in graph_generators.py
• #26846 for graph isomorphism
• #26851 py3: avoid .vertices() and .edges() in union of graphs
• #26869 py3: improve is_aperiodic to fix doctests (due to deprecation warning in networkx)
• #26870 py3: fix error with map in strongly_regular_db.pyx
• #26871 py3: fix doctests in digraph_generators.py
• #26940 stop sorting returned list of edges in spanning tree methods
• #26971 py3: some minor fix for traveling salesman
• #26973 py3: avoid .vertices() in graph_plot.py
• #27007 py3: avoid .vertices() in planarity.pyx
• #27008 py3: avoid .vertices() in method apex_vertices
• #27009 py3: avoid sorting vertices and edges in method treewidth
• #27010 py3: avoid .vertices() in methods _ford_fulkerson, edge_cut, bounded_outdegree_orientation and gomory_hu_tree

[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 ?

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

[dcoudert]

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

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

[dcoudert]

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

[chapoton]

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

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

[chapoton]

I made #26846 for graph isomorphism

[chapoton]

Salut !

• we should probably add #26971 somewhere

• where are the plot methods handled ?

[dcoudert]

See #26469, #26478, #26480, #26484.

I will check #26971 soon.

[chapoton]

Concerning plot, there are still problems in py3 when plotting posets. This point to the remaining

File "/home/u1/chapoton/sage3/local/lib/python3.6/site-packages/sage/graphs/graph_plot.py", line 255, in __init__
        self._nodelist = graph.vertices()

[dcoudert]

With #27008, #27009 and #27010, all remaining doctest errors in graph.py concern the order in which solutions are displayed (not always the same in py2 and py3).

[embray]

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.

[jhpalmieri]

I would like to ask some questions about how to deal with simplicial complexes.

• The is_isomorphic method for simplicial complexes translates each complex to a graph and then asks whether they are isomorphic, preserving edge labels. Some edges are labeled and some are not: the edge labels look like

  sage: g.edge_labels()
  [None,
   None,
   'special_edge',
   'special_edge']
  

  This fails in Python 3 because it tries to sort edges, and it can't sort str and NoneType. It is easy enough to provide labels in this case, but should the graph is_isomorphic method deal well with graphs where some edges have labels and some don't? (I don't have an opinion and I will fix the simplicial complex code separately.)

• Again with the is_isomorphic method for simplicial complexes: it defines a graph with vertices labeled by the vertices of the complex and its facets, and it adds an edge between a vertex v and a facet f if v is in f. The graph code tries to sort the vertices, and since the vertices in a simplicial complex can be integers, strings, whatever, the sorting goes badly. Again, I think I can handle this for simplicial complexes by translating everything to something sortable, then sorting, and then translating back at the end, but should the graph is_isomorphic method handle these sorts of cases better?

• Consider this:

  sage: S1 = simplicial_complexes.Sphere(1)
  sage: g = S1.wedge(S1).graph()
  sage: g
  Graph on 5 vertices
  sage: g.vertices()
  [0, 'L1', 'L2', 'R1', 'R2']
  

  In Python 3, the last line instead raises an error:

  ---------------------------------------------------------------------------
  TypeError                                 Traceback (most recent call last)
  <ipython-input-4-b2087dfc7b91> in <module>()
  ----> 1 g.vertices()
  
  /Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.6.rc1/local/lib/python3.6/site-packages/sage/graphs/generic_graph.py in vertices(self, sort, key)
    10053             raise ValueError('sort keyword is False, yet a key function is given')
    10054         if sort:
  > 10055             return sorted(list(self.vertex_iterator()), key=key)
    10056         return list(self.vertex_iterator())
    10057 
  
  TypeError: '<' not supported between instances of 'int' and 'str'
  sage: g.min_spanning_tree()
  ---------------------------------------------------------------------------
  TypeError                                 Traceback (most recent call last)
  <ipython-input-5-8a025bbcbd58> in <module>()
  ----> 1 g.min_spanning_tree()
  
  /Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.6.rc1/local/lib/python3.6/site-packages/sage/graphs/generic_graph.py in min_spanning_tree(self, weight_function, algorithm, starting_vertex, check)
     4231                 return min_spanning_tree(g,
     4232                                          weight_function=wfunction_float,
  -> 4233                                          algorithm=algorithm.split("_")[0])
     4234 
     4235         if algorithm == "Prim_fringe":
  
  /Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.6.rc1/local/lib/python3.6/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.min_spanning_tree (build/cythonized/sage/graphs/base/boost_graph.cpp:9345)()
      604 
      605 
  --> 606 cpdef min_spanning_tree(g,
      607                         weight_function=None,
      608                         algorithm='Kruskal'):
  
  /Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.6.rc1/local/lib/python3.6/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.min_spanning_tree (build/cythonized/sage/graphs/base/boost_graph.cpp:9100)()
      719     else:
      720         edges = [(int_to_vertex[<int> result[2*i]], int_to_vertex[<int> result[2*i+1]]) for i in range(n-1)]
  --> 721         return [(min(e[0],e[1]), max(e[0],e[1]), g.edge_label(e[0], e[1])) for e in edges]
      722 
      723 
  
  TypeError: '<' not supported between instances of 'int' and 'str'
  

  In Python 2, g.min_spanning_tree() works, while in Python 3, it raises a similar TypeError:

  sage: g.min_spanning_tree()
  ---------------------------------------------------------------------------
  TypeError                                 Traceback (most recent call last)
  <ipython-input-5-8a025bbcbd58> in <module>()
  ----> 1 g.min_spanning_tree()
  
  /Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.6.rc1/local/lib/python3.6/site-packages/sage/graphs/generic_graph.py in min_spanning_tree(self, weight_function, algorithm, starting_vertex, check)
     4231                 return min_spanning_tree(g,
     4232                                          weight_function=wfunction_float,
  -> 4233                                          algorithm=algorithm.split("_")[0])
     4234 
     4235         if algorithm == "Prim_fringe":
  
  /Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.6.rc1/local/lib/python3.6/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.min_spanning_tree (build/cythonized/sage/graphs/base/boost_graph.cpp:9345)()
      604 
      605 
  --> 606 cpdef min_spanning_tree(g,
      607                         weight_function=None,
      608                         algorithm='Kruskal'):
  
  /Users/jpalmier/Desktop/Sage/sage_builds/PYTHON3/sage-8.6.rc1/local/lib/python3.6/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.min_spanning_tree (build/cythonized/sage/graphs/base/boost_graph.cpp:9100)()
      719     else:
      720         edges = [(int_to_vertex[<int> result[2*i]], int_to_vertex[<int> result[2*i+1]]) for i in range(n-1)]
  --> 721         return [(min(e[0],e[1]), max(e[0],e[1]), g.edge_label(e[0], e[1])) for e in edges]
      722 
      723 
  
  TypeError: '<' not supported between instances of 'int' and 'str'
  

  Once again, I could probably get around this by translating all of the vertices to something sortable and then translating back, but I do think that the graph theory code should be able to handle graphs whose vertices are a combination of int and str and anything else. I would like to put in a request for fixing this particular problem.

[jhpalmieri]

Maybe one of these (the second one, I think) was taken care of by #27027.

[jhpalmieri]

See #27067 for simplicial complexes fixes for the first two items.

[dcoudert]

I fully agree that the graph theory code should be able to handle vertices of different types. We have done significant progresses recently, and many methods are no longer sorting vertices. But a lot remains to be done since a huge part of the code uses vertex ids instead of internal int labels. We have to find solutions for instance for listing edges as end points are currently sorted...

Note that I'm not able to try your example with py3 as this S1.wedge(S1).graph() already raises an error.

[jhpalmieri]

First, you have all done great work with graphs, and you've made a tremendous amount of progress. Partly my questions were because I don't know whether some of these things have been done in tickets which have not yet been merged, but I think that's not the case.

Speaking of things which have not yet been merged, you need #26966 to be able to do S1.wedge(S1).graph(). Sorry, I hadn't realized that when I posted my example.

[jhpalmieri]

Also, as I hope was clear in my questions, the first two are not critiques but honest questions: I don't know how Sage should handle those situations. The fact that things happen to work in Python 2 does not mean that they should automatically work in Python 3. For example, if you explicitly ask for isomorphisms preserving edge labels, an argument could be made that you should actually label all of the edges. The last item on my list was an explicit request, which it sounds like you agree with but also sounds like it take some work.