Opened 7 months ago
Last modified 2 weeks ago
#26640 new task
Meta-ticket: make graphs compatible with Python 3 — at Version 17
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
- methods
.vertices()
and.edges()
use sort by default - direct comparison of vertex labels (e.g., in method
iterator_edges
ofbase/sparse_graph.pyx
) - all
min_spanning_tree
methods sort edges before returning the result
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 - #26634 clean generic_graph.py (part 5)
- #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
- #26779 py3: fix
graph_input.py
andhypergraph_generators.py
- #26846 for graph isomorphism
- #26851 py3: avoid
.vertices()
and.edges()
inunion
of graphs
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()
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)
- #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
- #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
- #26812 py3: fix doctest in
graph_generators.py
Change History (17)
comment:1 Changed 7 months ago by
- Description modified (diff)
comment:2 Changed 7 months ago by
- Description modified (diff)
comment:3 Changed 7 months ago by
- Component changed from group theory to graph theory
comment:4 Changed 6 months ago by
comment:5 Changed 6 months ago by
- Description modified (diff)
comment:6 Changed 6 months ago by
- Description modified (diff)
comment:7 Changed 6 months ago by
- Description modified (diff)
comment:8 Changed 6 months ago by
- Description modified (diff)
comment:9 Changed 6 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 6 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 6 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 6 months ago by
We can start working on it. In the worst case, I will have to fix some merge conflicts.
comment:13 Changed 6 months ago by
I have made a first tentative at u/chapoton/graphe_iso
comment:14 Changed 6 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 6 months ago by
- Description modified (diff)
comment:17 Changed 6 months ago by
- Description modified (diff)
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 ?