{c,sparse}_graph: systematically turn integer-like vertices into ints

jdemeyer commented 7 years ago

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.

CC: @dcoudert

Component: graph theory

Author: Marc Mezzarobba

Branch/Commit: u/jdemeyer/_c_sparsegraphsystematically_turn_integer_like_vertices_into_ints @ 61feee1

Issue created by migration from https://trac.sagemath.org/ticket/22374

jdemeyer commented 7 years ago

Branch: u/jdemeyer/_c_sparsegraphsystematically_turn_integer_like_vertices_into_ints

mezzarobba commented 7 years ago

comment:2

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:

61feee1 {c,sparse}_graph: systematically turn integer-like vertices into ints

mezzarobba commented 7 years ago

Commit: 61feee1

jdemeyer commented 7 years ago

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?

mezzarobba commented 7 years ago

comment:6

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.

jdemeyer commented 7 years ago

comment:7

Don't break this doctest:

diff --git a/src/sage/graphs/generic_graph.py b/src/sage/graphs/generic_graph.py
index a3fec74..26b2c83 100644
--- a/src/sage/graphs/generic_graph.py
+++ b/src/sage/graphs/generic_graph.py
@@ -20161,7 +20161,7 @@ class GenericGraph(GenericGraph_pyx):
         Relabeling using a dictionary. Note that the dictionary does not define
         the new label of vertex `0`::

-            sage: G.relabel({1:2,2:1}, inplace=False).am()
+            sage: G.relabel({int(1):2,int(2):1}, inplace=False).am()
             [0 0 1]
             [0 0 1]
             [1 1 0]

jdemeyer commented 7 years ago

comment:8

Replying to @mezzarobba:

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.

mezzarobba commented 7 years ago

comment:9

Replying to @jdemeyer:

Replying to @mezzarobba:

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.

mezzarobba commented 5 years ago

comment:10

Ccing you in case there would be something to salvage from here, since you've apparently be doing lots of related work recently.

dcoudert commented 5 years ago

comment:11

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, and vertex_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...

dcoudert commented 5 years ago

comment:12

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 of active_vertices, and that no previously added vertex v has been associated to an integer equals to u, then vertex u is marked as active but not added to mappings vertex_ints and vertex_labels.
if u is smaller than the current size of active_vertices, but that a previously added vertex v has been associated to an integer equals to u, then u is associated to the first available integer u_int in range 0..|active_vertices|-1, marked as active and added to the mappings vertex_ints and vertex_labels.
if u is larger than the current size of active_vertices, we map it to the first available integer u_int in range 0..|active_vertices|-1, mark u_int as active and add u and u_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.

sagemath / sage

{c,sparse}_graph: systematically turn integer-like vertices into ints #22374