Opened 9 years ago

Closed 9 years ago

# RDF vertices of a graph are transformed into consecutive integers

Reported by: Owned by: Thierry Monteil jason, ncohen, rlm major sage-5.12 graph theory Nathann Cohen sage-5.12.beta3 Robert Miller Nathann Cohen N/A

### Description

```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.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 9]
```

### comment:1 Changed 9 years ago by 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.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'>>
Source:
"""

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

-- 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)
Traceback (most recent call last):
...
TypeError: unhashable type: 'list'

::

sage: S = sage.graphs.base.sparse_graph.SparseGraphBackend(9)
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.

Last edited 9 years ago by Darij Grinberg (previous) (diff)

### comment:2 Changed 9 years ago by 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.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...

### comment:4 Changed 9 years ago by Robert Miller

Authors: → Robert Miller new → needs_review

### comment:5 Changed 9 years ago by Robert Miller

for patchbot:

Apply trac_14853.patch

### comment:6 Changed 9 years ago by Nathann Cohen

Status: needs_review → needs_work

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

### comment:7 Changed 9 years ago by Nathann Cohen

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

Nathann

### comment:8 Changed 9 years ago by Robert Miller

Status: needs_work → needs_review

Thanks Nathann!

### comment:9 Changed 9 years ago by Nathann Cohen

Reviewers: → Nathann Cohen needs_review → positive_review

Well.. All tests pass `:-)`

Thaaaaaaaaaaaaaaanks !

Nathann

### comment:10 Changed 9 years ago by Jeroen Demeyer

Merged in: → sage-5.12.beta3 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.