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: |
Description
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 :
try: 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) else: 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
- Cc ncohen added
comment:2 Changed 8 years ago by
See also #14853.
comment:3 Changed 8 years ago by
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 else: 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
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
- 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.
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?