Opened 5 years ago

Last modified 3 years ago

#22374 needs_work defect

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

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-7.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:

Status badges

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 jdemeyer

  • Branch set to u/jdemeyer/_c_sparse__graph__systematically_turn_integer_like_vertices_into_ints

comment:2 Changed 5 years ago by mmezzarobba

  • Commit set to 61feee1b49d9314f9548a54fe866ba98ba142f1a
  • Status changed from new to needs_review

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

comment:3 in reply to: ↑ description Changed 5 years ago by jdemeyer

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 jdemeyer

  • Status changed from needs_review to needs_info

comment:5 Changed 5 years ago by mmezzarobba

  • Status changed from needs_info to needs_review

comment:6 follow-up: Changed 5 years ago by mmezzarobba

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 jdemeyer

  • 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): 
    2016120161        Relabeling using a dictionary. Note that the dictionary does not define
    2016220162        the new label of vertex `0`::
    2016320163
    20164             sage: G.relabel({1:2,2:1}, inplace=False).am()
     20164            sage: G.relabel({int(1):2,int(2):1}, inplace=False).am()
    2016520165            [0 0 1]
    2016620166            [0 0 1]
    2016720167            [1 1 0]

comment:8 in reply to: ↑ 6 ; follow-up: Changed 5 years ago by 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.

Last edited 5 years ago by jdemeyer (previous) (diff)

comment:9 in reply to: ↑ 8 Changed 5 years ago by mmezzarobba

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 mmezzarobba

  • 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 dcoudert

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

comment:12 Changed 3 years ago by dcoudert

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:

  1. 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.
  2. 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.
  3. 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
  4. 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.

Note: See TracTickets for help on using tickets.