Opened 5 years ago
Last modified 3 years ago
#22374 needs_work defect
{c,sparse}_graph: systematically turn integerlike vertices into ints
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  graph theory  Keywords:  
Cc:  dcoudert  Merged in:  
Authors:  Marc Mezzarobba  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/jdemeyer/_c_sparse__graph__systematically_turn_integer_like_vertices_into_ints (Commits, GitHub, GitLab)  Commit:  61feee1b49d9314f9548a54fe866ba98ba142f1a 
Dependencies:  Stopgaps: 
Description
Instead of doing it or not depending on the phase of the moon:
sage: g = DiGraph([[1..12],lambda i,j: i!=j and i.divides(j)]) sage: [type(v) for v in g.vertices()] [<type 'int'>, <type 'int'>, <type 'int'>, <type 'int'>, <type 'int'>, <type 'int'>, <type 'int'>, <type 'int'>, <type 'int'>, <type 'sage.rings.integer.Integer'>, <type 'int'>, <type 'int'>]
Leaving the vertices alone would be a better fix in principle. Unfortunately, it would break compatibility too badly: for example, people clearly expect to be able to create graphs in library code, using Python ints as labels, and then access the vertices using Sage integers.
Change History (12)
comment:1 Changed 5 years ago by
 Branch set to u/jdemeyer/_c_sparse__graph__systematically_turn_integer_like_vertices_into_ints
comment:2 Changed 5 years ago by
 Commit set to 61feee1b49d9314f9548a54fe866ba98ba142f1a
 Status changed from new to needs_review
comment:3 in reply to: ↑ description Changed 5 years ago by
Replying to jdemeyer:
Leaving the vertices alone would be a better fix in principle. Unfortunately, it would break compatibility too badly: for example, people clearly expect to be able to create graphs in library code, using Python ints as labels, and then access the vertices using Sage integers.
I agree that "Leaving the vertices alone would be a better fix".
But I don't understand why you don't just do that. You say that you want to access the vertices using Sage integers, but isn't that possible regardless of whether the vertices are internally stored as int
or Integer
?
comment:4 Changed 5 years ago by
 Status changed from needs_review to needs_info
comment:5 Changed 5 years ago by
 Status changed from needs_info to needs_review
comment:6 followup: ↓ 8 Changed 5 years ago by
If I remember right, generic graphs internally store their vertices as ints, and keep a separate mapping between those ints and the public labels, which can be more or less arbitrary objects. As an (apparently crucial?) optimization, public labels that are (small?) integers are used as internal labels, bypassing this translation layer. Storing Integer vertex labels as Integers would mean using the indirect representation. This would be fine if graph vertices were compared by identity rather than by equality, but while this might have been a saner design, that's clearly not what people expect from the existing code. If however we want to keep the ability to add and access integer vertices indifferently by passing integers of any type, then it seems more reasonable to me to stick to a single representation whenever possible. And in any case, I really don't understand the graphs code well enough to have anything else to suggest.
comment:7 Changed 5 years ago by
 Status changed from needs_review to needs_work
Don't break this doctest:

src/sage/graphs/generic_graph.py
diff git a/src/sage/graphs/generic_graph.py b/src/sage/graphs/generic_graph.py index a3fec74..26b2c83 100644
a b class GenericGraph(GenericGraph_pyx): 20161 20161 Relabeling using a dictionary. Note that the dictionary does not define 20162 20162 the new label of vertex `0`:: 20163 20163 20164 sage: G.relabel({ 1:2,2:1}, inplace=False).am()20164 sage: G.relabel({int(1):2,int(2):1}, inplace=False).am() 20165 20165 [0 0 1] 20166 20166 [0 0 1] 20167 20167 [1 1 0]
comment:8 in reply to: ↑ 6 ; followup: ↓ 9 Changed 5 years ago by
Replying to mmezzarobba:
As an (apparently crucial?) optimization, public labels that are (small?) integers are used as internal labels, bypassing this translation layer.
Do you know where this is implemented? Maybe we can just fix that to support Sage Integers too.
comment:9 in reply to: ↑ 8 Changed 5 years ago by
Replying to jdemeyer:
Replying to mmezzarobba:
As an (apparently crucial?) optimization, public labels that are (small?) integers are used as internal labels, bypassing this translation layer.
Do you know where this is implemented? Maybe we can just fix that to support Sage Integers too.
I think part of it happens in CGraphBackend.get_vertex()
and CGraphBackend.check_labelled_vertex()
. But I really don't know more than what I guessed when working on the comparison stuff that led me to the present issue; I was hoping that someone who understands this code could help.
comment:10 Changed 3 years ago by
 Cc dcoudert added; mmezzarobba removed
Ccing you in case there would be something to salvage from here, since you've apparently be doing lots of related work recently.
comment:11 Changed 3 years ago by
To the best of my understanding (this code is not easy):
c_graph
uses 2 mappings:vertex_ints
that associates the name of a vertex to the integer used in the internal representation, andvertex_labels
that associates the integer from the internal representation to the vertex name. So even is a vertex name is a small int, the integer used for the internal representation might be different.
This said, I don't understand why we have that
sage: g = DiGraph() sage: g.add_vertices([9..12]) sage: [(v, type(v)) for v in g.vertices()] [(9, <type 'int'>), (10, <type 'sage.rings.integer.Integer'>), (11, <type 'sage.rings.integer.Integer'>), (12, <type 'sage.rings.integer.Integer'>)]
Requires more investigation...
comment:12 Changed 3 years ago by
When you create an empty digraph using, DiGraph()
, the SparseGraph
constructor initializes the data structures for 10 vertices (int extra_vertices = 10
). This is the initial size of the bitset active_vertices
. Then, as mentioned above, when adding a vertex u
whose label is an integer:
 if
u
is smaller than the current size ofactive_vertices
, and that no previously added vertexv
has been associated to an integer equals tou
, then vertexu
is marked as active but not added to mappingsvertex_ints
andvertex_labels
.  if
u
is smaller than the current size ofactive_vertices
, but that a previously added vertexv
has been associated to an integer equals tou
, thenu
is associated to the first available integeru_int
in range0..active_vertices1
, marked as active and added to the mappingsvertex_ints
andvertex_labels
.  if
u
is larger than the current size ofactive_vertices
, we map it to the first available integeru_int
in range0..active_vertices1
, marku_int
as active and addu
andu_int
to the mappings  when all slots in
active_vertices
are used, we double it's size before adding a new vertex
Consider the following example:
sage: g = DiGraph() sage: g.add_vertices([9, 10, 0]) sage: [(v, type(v)) for v in g] [(0, <type 'sage.rings.integer.Integer'>), (10, <type 'sage.rings.integer.Integer'>), (9, <type 'int'>)]
When adding vertex 9
, we are in case 1, and so 9
is not added to the mappings. Then, when adding vertex 10
, we are in case 3 so we map it to the first available integer (here 0) and add it to the mappings. Hence, 10 keeps it's type (here sage.rings.integer.Integer
), while 9 is of type int
.
Now, when we add vertex 0
, we are in case 2, and so it will be mapped to 1 and it's type will be sage.rings.integer.Integer
. It will be the same if we now add vertex 1
...
The motivation of this optimization is to save space and few tests when the user creates vertices in the right order. But above example shows how easy it is to loose this optimization.
Shouldn't we should simplify the code and use mappings for all vertices ? It could ease the resolution of issues like in #27037.
See #22029 for the context where this came up. I was trying to fix code that I frankly don't understand, comments or improvements from someone more familiar with
sage.graphs
would be very welcome.New commits:
{c,sparse}_graph: systematically turn integerlike vertices into ints