RDF vertices of a graph are transformed into consecutive integers

[Thierry Monteil]

As reported in the comments of ​this ask answer:

sage: A=Set([RDF.random_element(min=0,max=10) for k in range(10)]) ; A
{6.42320967152, 1.77698693175, 2.95922392964, 9.50745089775, 4.60546838289, 3.67300191731, 5.21254750195, 5.90579400282, 7.55309974188, 0.442799267782}
sage: G = Graph()
sage: G.add_vertices(A)
sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 9]

[Darij Grinberg]

Unfortunately this is not limited to RDF:

sage: A = Set([QQ(0), QQ(1)/QQ(2)])                                                      
sage: A 
{0, 1/2}
sage: G = Graph()
sage: G.add_vertices(A)
sage: G.vertices()
[0]

My attempts at debugging this stop here:

sage: G._backend.add_vertex??  

Type:       instancemethod
String Form:<bound method SparseGraphBackend.add_vertex of <class 'sage.graphs.base.sparse_graph.SparseGraphBackend'>>
Definition: G._backend.add_vertex(self, name)
Source:
    def add_vertex(self, object name):
        """
        Add a vertex to ``self``.

        INPUT:

        - ``name`` -- the vertex to be added (must be hashable). If ``None``,
          a new name is created.

        OUTPUT:

        - If name=None, the new vertex name is returned.
          None otherwise.

        .. SEEALSO::

            - :meth:`add_vertices`
              -- add a bunch of vertices of this graph.

            - :meth:`has_vertex`
              -- returns whether or not this graph has a specific vertex.

        EXAMPLE::

            sage: D = sage.graphs.base.dense_graph.DenseGraphBackend(9)
            sage: D.add_vertex(10)
            sage: D.add_vertex([])
            Traceback (most recent call last):
            ...
            TypeError: unhashable type: 'list'

        ::

            sage: S = sage.graphs.base.sparse_graph.SparseGraphBackend(9)
            sage: S.add_vertex(10)
            sage: S.add_vertex([])
            Traceback (most recent call last):
            ...
            TypeError: unhashable type: 'list'
        """
        retval = None
        if name is None:
            name = 0
            while name in self.vertex_ints or (
                name not in self.vertex_labels and
                bitset_in((<CGraph>self._cg).active_vertices, name)):
                name += 1
            retval = name

        check_vertex(name,
                     self.vertex_ints,
                     self.vertex_labels,
                     self._cg,
                     self._cg_rev,
                     (self._directed and
                      self._cg_rev is not None)) # this will add the vertex

        return retval

What is that mysterious check_vertex method and where can I find it?

EDIT: Oh, I found it. I have been grepping for "def check_vertex" but it is "cdef int check_vertex". Let me see.

[Darij Grinberg]

I suspect the error is in sage/graphs/base/c_graph.pyx:

cdef int get_vertex(object u, dict vertex_ints, dict vertex_labels,
                    CGraph G) except ? -2:
    """
    Returns an int representing the arbitrary hashable vertex u (whether or not
    u is actually in the graph), or -1 if a new association must be made for u
    to be a vertex.

    TESTS:

    We check that the bug described in #8406 is gone::

        sage: G = Graph()
        sage: R.<a> = GF(3**3)
        sage: S.<x> = R[]
        sage: G.add_vertex(a**2)
        sage: G.add_vertex(x)
        sage: G.vertices()
        [a^2, x]

    And that the bug described in #9610 is gone::

        sage: n = 20
        sage: k = 3
        sage: g = DiGraph()
        sage: g.add_edges( (i,Mod(i+j,n)) for i in range(n) for j in range(1,k+1) )
        sage: g.vertices()
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
        sage: g.strongly_connected_components()
        [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]]

    """
    cdef int u_int
    if u in vertex_ints:
        return vertex_ints[u]
    try:
        u_int = u
    except StandardError:
        return -1
    if u_int < 0 or u_int >= G.active_vertices.size or u_int in vertex_labels:
        return -1
    return u_int

This "try/except" has apparently been written in the hope that if u is anything other than an integer, there will be an exception; but that reasoning fails because rationals and reals are silently converted into integers. Am I right? I'm unable to import methods from cython files into the sage console, so I can't test my conjectures...

[Robert Miller]

See also #14967

[Robert Miller]

for patchbot:

Apply trac_14853.patch

[Nathann Cohen]

OKayyyyyyyyyyy... Could you replace the references to the track ticket with :trac:14967 and :trac:14853 ? :-)`

Short of this I think it's good to go :-)

Nathann

[Nathann Cohen]

OOps. :trac:`14967` and :trac:`14853` sorry !

Nathann

[Robert Miller]

Thanks Nathann!

[Nathann Cohen]

Well.. All tests pass :-)

Thaaaaaaaaaaaaaaanks !

Nathann