Opened 5 months ago
Last modified 10 days ago
#26640 new task
Meta-ticket: make graphs compatible with Python 3
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 )
This ticket is used to keep track of the progress towards python3 in graphs.
Major issues
- #22349 Deprecate sorting of methods
.vertices()
and.edges()
- direct comparison of vertex labels (e.g., in method
iterator_edges
ofbase/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 that will be used to order rows and columns. Currently, we use.vertices()
by default. If we switch tolist(G)
by default, we have to check that it's not breaking algorithms using these matrices. - sort used in methods for checking isomorphisms w/wo edge labels (see also #27232 and #26800). Sorting of lists of possibly unhashable objects is needed here, or may be a method for checking that there is a permutation from one list to the other could be enough ?
Needs work:
- #22349 Deprecate sorting of Graph vertices and edges by default
- #26800 py3: bug with
canonical_label
- #27435 py3: failing doctest in
graph_database.py
withinteractive_query
Needs review:
- #27135 pep8 in
digraph_generators.py
(part 2) - #27137 pep8 in
digraph_generators.py
(part 4) - #27138 pep8 in
digraph_generators.py
(part 5) - #27232 is_isomorphic broken with keyword edge_labels=True
- #27408 Edge view for graphs -- introduce deprecation warning for
sort=None
as the plan is to setsort=False
by default.
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
andgraph_input.py
- #26480 clean graph_latex.py
- #26484 clean
graph_coloring.py
and avoid comparison of vertex labels - #26520 Meta-ticket for methods in
src/sage/graphs/graph_decomposition/
- #26827, #26828, #26829, #26830, #26831, #26832, #26833, #26834 - #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()
incentrality.pyx
- #26621 avoid using
.vertices()
and.edges()
inbliss.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
- #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
- #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
andhypergraph_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()
inunion
of graphs - #26869 py3: improve
is_aperiodic
to fix doctests (due to deprecation warning in networkx) - #26870 py3: fix error with
map
instrongly_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()
ingraph_plot.py
- #27007 py3: avoid
.vertices()
inplanarity.pyx
- #27008 py3: avoid
.vertices()
in methodapex_vertices
- #27009 py3: avoid sorting vertices and edges in method treewidth
- #27010 py3: avoid
.vertices()
in methods_ford_fulkerson
,edge_cut
,bounded_outdegree_orientation
andgomory_hu_tree
- #27029 Avoid calling
.vertices()
ingraph_isom_equivalent_non_edge_labeled_graph()
- #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 methodear_decomposition
- #27129 py3: fix other doctests in
graph.py
- #27144 py3: fix doctests in
connectivity.pyx
- #27147 py3: fix doctests in
dense_graph.pyx
,sparse_graph.pyx
,static_sparse_graph.pyx
- #27148 py3: fix doctests in
centrality.pyx
- #27149 py3: fix doctests in
comparability.pyx
- #27151 py3: fix doctests in
vertex_separation.pyx
- #27158 py3: fix doctests in
boost_graph.pyx
- #27159 py3: fix doctests in
strongly_regular_db.pyx
- #27160 py3: fix doctests in
hyperbolicity
andgraph_coloring
- #27165 py3: fix doctests in
c_graph.pyx
- #27166 remove deprecated classes
NetworkXGraphDeprecated
andNetworkXDiGraphDeprecated
- #27167 py3: fix doctest in
distances_all_pairs.pyx
- #27170 py3: fix 14 doctests in
digraph.py
- #27176 py3: fix doctest in
generic_graph
(part 1) - #27179 py3: fix doctest in
generic_graph
(part 2) -- cycle_basis - #27180 py3: fix doctest in
generic_graph
(part 3) -- _build_flow_graph - #27181 py3: fix doctest in
generic_graph
(part 4) - #27183 py3: fix doctest in
generic_graph
(part 5) - #27184 py3: fix doctests in
generic_graph
(part 6) --graphviz_string
- #27202 py3: fix doctests in random graphs generators
- #27203 py3: fix 8 doctests in
generators/families.py
- #27242 py3: strengthen a doctest in
vertex_separation.pyx
- #27243 py3: fix doctests in
generic_graph
(part 7) -- relabel - #27244 py3: fix doctests in
generic_graph
(part 8) --coarsest_equitable_refinement
- #27245 py3: fix doctests in
generic_graph
(part 9) --automorphism_group
- #27246 py3: fix doctests in
generic_graph
(part 10) --is_isomorphic
Change History (68)
comment:1 Changed 5 months ago by
- Description modified (diff)
comment:2 Changed 5 months ago by
- Description modified (diff)
comment:3 Changed 4 months ago by
- Component changed from group theory to graph theory
comment:4 Changed 4 months ago by
comment:5 Changed 4 months ago by
- Description modified (diff)
comment:6 Changed 4 months ago by
- Description modified (diff)
comment:7 Changed 4 months ago by
- Description modified (diff)
comment:8 Changed 4 months ago by
- Description modified (diff)
comment:9 Changed 3 months ago by
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)
comment:10 Changed 3 months ago by
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 3 months ago by
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 3 months ago by
We can start working on it. In the worst case, I will have to fix some merge conflicts.
comment:13 Changed 3 months ago by
I have made a first tentative at u/chapoton/graphe_iso
comment:14 Changed 3 months ago by
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:16 Changed 3 months ago by
- Description modified (diff)
comment:17 Changed 3 months ago by
- Description modified (diff)
comment:18 Changed 3 months ago by
- Description modified (diff)
comment:19 Changed 3 months ago by
- Description modified (diff)
comment:20 Changed 3 months ago by
- Description modified (diff)
comment:21 Changed 3 months ago by
- Description modified (diff)
comment:22 Changed 3 months ago by
- Description modified (diff)
comment:23 Changed 3 months ago by
- Description modified (diff)
comment:24 Changed 3 months ago by
comment:25 Changed 3 months ago by
- Description modified (diff)
comment:26 Changed 3 months ago by
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()
comment:27 Changed 3 months ago by
- Description modified (diff)
- Milestone changed from sage-8.5 to sage-8.6
comment:28 Changed 3 months ago by
- Description modified (diff)
comment:29 Changed 3 months ago by
- Description modified (diff)
comment:30 Changed 3 months ago by
- Description modified (diff)
comment:31 Changed 3 months ago by
- Description modified (diff)
comment:32 Changed 3 months ago by
- Description modified (diff)
comment:33 Changed 2 months ago by
- Description modified (diff)
comment:34 Changed 2 months ago by
- Milestone changed from sage-8.6 to sage-8.7
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.
comment:35 Changed 2 months ago by
I would like 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 likesage: g.edge_labels() [None, None, 'special_edge', 'special_edge']
This fails in Python 3 because it tries to sort edges, and it can't sortstr
andNoneType
. It is easy enough to provide labels in this case, but should the graphis_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 vertexv
and a facetf
ifv
is inf
. 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 graphis_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 similarTypeError
: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 ofint
andstr
and anything else. I would like to put in a request for fixing this particular problem.
comment:36 Changed 2 months ago by
Maybe one of these (the second one, I think) was taken care of by #27027.
comment:37 Changed 2 months ago by
See #27067 for simplicial complexes fixes for the first two items.
comment:38 Changed 2 months ago by
- Milestone changed from sage-8.7 to sage-pending
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.
comment:39 Changed 2 months ago by
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.
comment:40 Changed 2 months ago by
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.
comment:41 Changed 8 weeks ago by
- Description modified (diff)
comment:42 Changed 8 weeks ago by
- Description modified (diff)
comment:43 Changed 8 weeks ago by
- Description modified (diff)
comment:44 Changed 7 weeks ago by
- Description modified (diff)
comment:45 Changed 7 weeks ago by
- Description modified (diff)
comment:46 Changed 7 weeks ago by
- Description modified (diff)
comment:47 Changed 7 weeks ago by
- Description modified (diff)
comment:48 Changed 7 weeks ago by
- Description modified (diff)
comment:49 Changed 7 weeks ago by
- Description modified (diff)
comment:50 Changed 7 weeks ago by
- Description modified (diff)
comment:51 Changed 7 weeks ago by
- Description modified (diff)
comment:52 Changed 7 weeks ago by
- Description modified (diff)
comment:53 Changed 6 weeks ago by
- Description modified (diff)
comment:54 Changed 6 weeks ago by
- Description modified (diff)
comment:55 Changed 6 weeks ago by
- Description modified (diff)
comment:56 Changed 6 weeks ago by
- Description modified (diff)
comment:57 Changed 5 weeks ago by
- Description modified (diff)
comment:58 Changed 5 weeks ago by
- Description modified (diff)
comment:59 Changed 4 weeks ago by
- Description modified (diff)
We have now drastically reduced the dependency to .vertices()
and .edges()
in the graph module (except in doctests, but we can specify sort=True/False
).
We must now identify the tasks to do and schedule the work.
Some issues to take care of in the graph module:
- #22349 Deprecate sorting of methods
.vertices()
and.edges()
.- methods using matrices:
adjacency_matrix
,distance_matrix
, etc. For all these methods, we can now give as input an ordering of the vertices that will be used to order rows and columns. Currently, we use.vertices()
by default. If we switch tolist(G)
by default, we have to check that it's not breaking algorithms using these matrices. - methods using
.relabel()
. We must check that changing the default ordering of vertices/edges is safe. Should be ok, but we never know... - methods for isomorphisms were we also have issues with labels (see e.g. #27232 although the case is certainly beyond what we should reasonably do).
- methods using matrices:
- Deprecate sorting of vertex labels in method
iterator_edges
ofbase/sparse_graph.pyx
(so of the vertices of an edge). Deprecating this behavior is certainly a hard task. A first step could be to order the vertices according internal integer value, thus ensuring that(u, v)
will always be ordered the same way.
And of course, changes done here will certainly break many methods in other modules...
comment:60 Changed 3 weeks ago by
- Cc gh-jfraymond added
comment:61 Changed 3 weeks ago by
- Description modified (diff)
comment:62 Changed 2 weeks ago by
- Description modified (diff)
Proposal for an EdgeView
for graphs in #27408.
comment:63 Changed 13 days ago by
- Description modified (diff)
comment:64 Changed 11 days ago by
- Description modified (diff)
comment:65 Changed 10 days ago by
I don't know if this is a good idea or not, but see #27452 for a branch which fixes the last doctest failures in src/homology. This bypasses an issue with graphs, as mentioned above:
sage: S1 = simplicial_complexes.Sphere(1) sage: g = S1.wedge(S1).graph() sage: g Graph on 5 vertices sage: g.vertices() ... TypeError: '<' not supported between instances of 'int' and 'str'
The branch at #27452 relabels the graph of a simplicial complex so that the vertices are sortable, before trying to compute its minimal spanning tree. Is this just sweeping things under the rug, or is it okay?
comment:66 Changed 10 days ago by
I think it is one way forward. It does suffer in large cases because you have to make a full copy of the simplicial complex's graph, but I don't think it is simply sweeping it under the rug. Perhaps for that a user should know better than to have complicated labels for such tests?
comment:67 follow-up: ↓ 68 Changed 10 days ago by
An alternative is to (optionally) make spanning tree methods return a Graph
, in which case there is no need to sort end vertices.
comment:68 in reply to: ↑ 67 Changed 10 days ago by
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.
I'm answering here the question of #26567#comment:9 about how to make
iterator_edges
ofsparse_graph.pyx
py3 compatible, and if something similar to #26567 fordense_graph.pyx
can be done forsparse_graph.pyx
.So far, I don't know what's the best option.
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.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 ?