Opened 8 years ago

Closed 8 years ago

#14967 closed defect (duplicate)

Bug with DiGraph

Reported by: mercatp Owned by:
Priority: major Milestone: sage-5.11
Component: graph theory Keywords: graph
Cc: ncohen Merged in:
Authors: Paul Mercat Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges


I've found the following bug with DiGraph? :

sage: G=DiGraph({0:{},1/2:{}});G
DiGraph on 1 vertex

I've found where is the error. It's in the file $SAGE_ROOT/sage/graphs/base/c_graph.pyx, in function get_vertex :

    u_int = u
except StandardError:
    return -1

should be replaced by :

from sage.rings.integer_ring import IntegerRing
if u in IntegerRing():
    u_int = int(u)
    return -1

I've tried, and it corrects the problem.

But I'm not sure that it's the right way to correct the problem, because I don't understand exactly how this code works. For me it's very weird (and a source of bugs) to distinguish whether or not u is an integer : it should be any hashable vertex and that's all. Why they wants to have the integer corresponding to u (as an index in the hash table) be equal to u when u is an integer ?

Change History (5)

comment:1 Changed 8 years ago by rlm

  • Cc ncohen added

The reason we did this was to make the most common cases as fast as possible. Since a lot of the graphs in Sage are on the integers [0, 1, ..., n] it is much faster if the underlying representation doesn't have to spend extra time translating between the user-exposed vertices and those of the underlying implementation. The reasoning is to take the cheapest route to integer possible. If the vertex is not an integer, we need to update translation dictionaries and this is more expensive.

When this code was written Cython would not allow you to assign 1/2 to a C integer. We used the fact that try blocks are very cheap to take advantage of this behavior for speed.

I am worried that if u in IntegerRing will take a long time due to coercion. Have you done any profiling to see the difference?

comment:2 Changed 8 years ago by tmonteil

See also #14853.

comment:3 Changed 8 years ago by mercatp

Ok, I understand. So the test if u in IntegerRing() is not a good idea, it would be better to impose u to be of type int for example :

if type(u) == int:
   u_int = u
   return -1

This should be faster. And it's better to impose a strict type for the number, because an 1 in a given number field is not the same that an 1 in an other number field for example (we can imagine a graph with differents vertex 1, although it's weird).

comment:4 Changed 8 years ago by mercatp

The last correction that I proposed doesn't work because u can also be of type Integer or IntMod in many tests (we should write if type(u) == int or if type(u) == Integer or type(u) == IntMod:).

I think that the right way to have fast algorithms with usuals graphs would be to use a different implementation for theses graphs, with vertex labeled by integers 0, 1, 2, ... You will just have to check at the initialization which implementation we should use (and it's not a problem if it's slow here I think), and then it uses the best implementation to manipulate the graph. I think it will not be difficult to do this. Do you think it's a good idea ?

comment:5 Changed 8 years ago by rlm

  • Resolution set to duplicate
  • Status changed from new to closed

I'm resolving this as a duplicate of #14853. There is a patch there which fixes the issue.

Note: See TracTickets for help on using tickets.