Opened 10 years ago
Closed 10 years ago
#14477 closed defect (fixed)
Graph database query results should be sorted
| Reported by: | Jeroen Demeyer | Owned by: | William Stein |
|---|---|---|---|
| Priority: | critical | Milestone: | sage-5.10 |
| Component: | packages: huge | Keywords: | |
| Cc: | R. Andrew Ohana, David Roe | Merged in: | sage-5.10.beta1 |
| Authors: | R. Andrew Ohana | Reviewers: | Volker Braun, Jeroen Demeyer |
| Report Upstream: | N/A | Work issues: | |
| Branch: | Commit: | ||
| Dependencies: | Stopgaps: |
Status badges
Description (last modified by )
Currently, the ordering of the query results of the graph database is undefined. In fact, upgrading to Python-2.7.4 (#14423), the following happens on the buildbot machine rosemary (RHEL 5.6 x86_64):
sage -t --long devel/sage/sage/graphs/graph_database.py
**********************************************************************
File "devel/sage/sage/graphs/graph_database.py", line 932, in sage.graphs.graph_database.GraphDatabase.query
Failed example:
q.show()
Expected:
Graph6 Num Vertices Degree Sequence
------------------------------------------------------------
@ 1 [0]
A? 2 [0, 0]
A_ 2 [1, 1]
B? 3 [0, 0, 0]
BG 3 [0, 1, 1]
BW 3 [1, 1, 2]
Bw 3 [2, 2, 2]
C? 4 [0, 0, 0, 0]
C@ 4 [0, 0, 1, 1]
CB 4 [0, 1, 1, 2]
CK 4 [1, 1, 1, 1]
CF 4 [1, 1, 1, 3]
CJ 4 [0, 2, 2, 2]
CL 4 [1, 1, 2, 2]
CN 4 [1, 2, 2, 3]
C] 4 [2, 2, 2, 2]
C^ 4 [2, 2, 3, 3]
D?? 5 [0, 0, 0, 0, 0]
D?C 5 [0, 0, 0, 1, 1]
D?K 5 [0, 0, 1, 1, 2]
D@O 5 [0, 1, 1, 1, 1]
D?[ 5 [0, 1, 1, 1, 3]
D@K 5 [0, 0, 2, 2, 2]
D_K 5 [1, 1, 1, 1, 2]
D@S 5 [0, 1, 1, 2, 2]
D?{ 5 [1, 1, 1, 1, 4]
D@[ 5 [0, 1, 2, 2, 3]
D@s 5 [1, 1, 1, 2, 3]
DBg 5 [1, 1, 2, 2, 2]
DBW 5 [0, 2, 2, 2, 2]
D`K 5 [1, 1, 2, 2, 2]
D@{ 5 [1, 1, 2, 2, 4]
DB[ 5 [0, 2, 2, 3, 3]
DIk 5 [1, 2, 2, 2, 3]
DBk 5 [1, 1, 2, 3, 3]
DK[ 5 [1, 2, 2, 2, 3]
DLo 5 [2, 2, 2, 2, 2]
E??? 6 [0, 0, 0, 0, 0, 0]
E??G 6 [0, 0, 0, 0, 1, 1]
E??W 6 [0, 0, 0, 1, 1, 2]
E?C_ 6 [0, 0, 1, 1, 1, 1]
E??w 6 [0, 0, 1, 1, 1, 3]
E?CW 6 [0, 0, 0, 2, 2, 2]
EG?W 6 [0, 1, 1, 1, 1, 2]
E?Cg 6 [0, 0, 1, 1, 2, 2]
E@Q? 6 [1, 1, 1, 1, 1, 1]
E?@w 6 [0, 1, 1, 1, 1, 4]
E?Cw 6 [0, 0, 1, 2, 2, 3]
E?Dg 6 [0, 1, 1, 1, 2, 3]
E_?w 6 [1, 1, 1, 1, 1, 3]
E?LO 6 [0, 1, 1, 2, 2, 2]
E?N? 6 [1, 1, 1, 1, 2, 2]
E?Ko 6 [0, 0, 2, 2, 2, 2]
EGCW 6 [0, 1, 1, 2, 2, 2]
E_Cg 6 [1, 1, 1, 1, 2, 2]
E?Bw 6 [1, 1, 1, 1, 1, 5]
E?Dw 6 [0, 1, 1, 2, 2, 4]
E?Fg 6 [1, 1, 1, 1, 2, 4]
E?Kw 6 [0, 0, 2, 2, 3, 3]
E@HW 6 [0, 1, 2, 2, 2, 3]
E@FG 6 [1, 1, 1, 2, 2, 3]
E?LW 6 [0, 1, 1, 2, 3, 3]
E?NG 6 [1, 1, 1, 1, 3, 3]
E@N? 6 [1, 1, 2, 2, 2, 2]
E@YO 6 [1, 1, 2, 2, 2, 2]
E@QW 6 [1, 1, 1, 2, 2, 3]
E@Ow 6 [0, 1, 2, 2, 2, 3]
E_Cw 6 [1, 1, 1, 2, 2, 3]
E@T_ 6 [0, 2, 2, 2, 2, 2]
E_Ko 6 [1, 1, 2, 2, 2, 2]
F???? 7 [0, 0, 0, 0, 0, 0, 0]
F???G 7 [0, 0, 0, 0, 0, 1, 1]
F???W 7 [0, 0, 0, 0, 1, 1, 2]
F??G_ 7 [0, 0, 0, 1, 1, 1, 1]
F???w 7 [0, 0, 0, 1, 1, 1, 3]
F??GW 7 [0, 0, 0, 0, 2, 2, 2]
F@??W 7 [0, 0, 1, 1, 1, 1, 2]
F??Gg 7 [0, 0, 0, 1, 1, 2, 2]
F?Ca? 7 [0, 1, 1, 1, 1, 1, 1]
F??@w 7 [0, 0, 1, 1, 1, 1, 4]
F??Gw 7 [0, 0, 0, 1, 2, 2, 3]
F??Hg 7 [0, 0, 1, 1, 1, 2, 3]
FG??w 7 [0, 1, 1, 1, 1, 1, 3]
F??XO 7 [0, 0, 1, 1, 2, 2, 2]
F??Z? 7 [0, 1, 1, 1, 1, 2, 2]
F??Wo 7 [0, 0, 0, 2, 2, 2, 2]
F@?GW 7 [0, 0, 1, 1, 2, 2, 2]
FK??W 7 [1, 1, 1, 1, 1, 1, 2]
FG?Gg 7 [0, 1, 1, 1, 1, 2, 2]
F??Bw 7 [0, 1, 1, 1, 1, 1, 5]
F??Hw 7 [0, 0, 1, 1, 2, 2, 4]
F??Jg 7 [0, 1, 1, 1, 1, 2, 4]
F_?@w 7 [1, 1, 1, 1, 1, 1, 4]
F??Ww 7 [0, 0, 0, 2, 2, 3, 3]
F?CPW 7 [0, 0, 1, 2, 2, 2, 3]
F?CJG 7 [0, 1, 1, 1, 2, 2, 3]
F??^? 7 [1, 1, 1, 1, 1, 2, 3]
F??XW 7 [0, 0, 1, 1, 2, 3, 3]
F??ZG 7 [0, 1, 1, 1, 1, 3, 3]
F?CZ? 7 [0, 1, 1, 2, 2, 2, 2]
F_?Hg 7 [1, 1, 1, 1, 1, 2, 3]
F?CqO 7 [0, 1, 1, 2, 2, 2, 2]
F?CaW 7 [0, 1, 1, 1, 2, 2, 3]
F?LCG 7 [1, 1, 1, 1, 2, 2, 2]
F?C_w 7 [0, 0, 1, 2, 2, 2, 3]
FG?Gw 7 [0, 1, 1, 1, 2, 2, 3]
F?Ch_ 7 [0, 0, 2, 2, 2, 2, 2]
FG?Wo 7 [0, 1, 1, 2, 2, 2, 2]
F_?XO 7 [1, 1, 1, 1, 2, 2, 2]
FK?GW 7 [1, 1, 1, 1, 2, 2, 2]
Got:
Graph6 Num Vertices Degree Sequence
------------------------------------------------------------
@ 1 [0]
A? 2 [0, 0]
B? 3 [0, 0, 0]
C? 4 [0, 0, 0, 0]
D?? 5 [0, 0, 0, 0, 0]
E??? 6 [0, 0, 0, 0, 0, 0]
F???? 7 [0, 0, 0, 0, 0, 0, 0]
A_ 2 [1, 1]
BG 3 [0, 1, 1]
C@ 4 [0, 0, 1, 1]
D?C 5 [0, 0, 0, 1, 1]
E??G 6 [0, 0, 0, 0, 1, 1]
F???G 7 [0, 0, 0, 0, 0, 1, 1]
BW 3 [1, 1, 2]
CB 4 [0, 1, 1, 2]
CK 4 [1, 1, 1, 1]
D?K 5 [0, 0, 1, 1, 2]
D@O 5 [0, 1, 1, 1, 1]
E??W 6 [0, 0, 0, 1, 1, 2]
E?C_ 6 [0, 0, 1, 1, 1, 1]
F???W 7 [0, 0, 0, 0, 1, 1, 2]
F??G_ 7 [0, 0, 0, 1, 1, 1, 1]
Bw 3 [2, 2, 2]
CF 4 [1, 1, 1, 3]
CJ 4 [0, 2, 2, 2]
CL 4 [1, 1, 2, 2]
D?[ 5 [0, 1, 1, 1, 3]
D@K 5 [0, 0, 2, 2, 2]
D_K 5 [1, 1, 1, 1, 2]
D@S 5 [0, 1, 1, 2, 2]
E??w 6 [0, 0, 1, 1, 1, 3]
E?CW 6 [0, 0, 0, 2, 2, 2]
EG?W 6 [0, 1, 1, 1, 1, 2]
E?Cg 6 [0, 0, 1, 1, 2, 2]
E@Q? 6 [1, 1, 1, 1, 1, 1]
F???w 7 [0, 0, 0, 1, 1, 1, 3]
F??GW 7 [0, 0, 0, 0, 2, 2, 2]
F@??W 7 [0, 0, 1, 1, 1, 1, 2]
F??Gg 7 [0, 0, 0, 1, 1, 2, 2]
F?Ca? 7 [0, 1, 1, 1, 1, 1, 1]
CN 4 [1, 2, 2, 3]
C] 4 [2, 2, 2, 2]
D?{ 5 [1, 1, 1, 1, 4]
D@[ 5 [0, 1, 2, 2, 3]
D@s 5 [1, 1, 1, 2, 3]
DBg 5 [1, 1, 2, 2, 2]
DBW 5 [0, 2, 2, 2, 2]
D`K 5 [1, 1, 2, 2, 2]
E?@w 6 [0, 1, 1, 1, 1, 4]
E?Cw 6 [0, 0, 1, 2, 2, 3]
E?Dg 6 [0, 1, 1, 1, 2, 3]
E_?w 6 [1, 1, 1, 1, 1, 3]
E?LO 6 [0, 1, 1, 2, 2, 2]
E?N? 6 [1, 1, 1, 1, 2, 2]
E?Ko 6 [0, 0, 2, 2, 2, 2]
EGCW 6 [0, 1, 1, 2, 2, 2]
E_Cg 6 [1, 1, 1, 1, 2, 2]
F??@w 7 [0, 0, 1, 1, 1, 1, 4]
F??Gw 7 [0, 0, 0, 1, 2, 2, 3]
F??Hg 7 [0, 0, 1, 1, 1, 2, 3]
FG??w 7 [0, 1, 1, 1, 1, 1, 3]
F??XO 7 [0, 0, 1, 1, 2, 2, 2]
F??Z? 7 [0, 1, 1, 1, 1, 2, 2]
F??Wo 7 [0, 0, 0, 2, 2, 2, 2]
F@?GW 7 [0, 0, 1, 1, 2, 2, 2]
FK??W 7 [1, 1, 1, 1, 1, 1, 2]
FG?Gg 7 [0, 1, 1, 1, 1, 2, 2]
C^ 4 [2, 2, 3, 3]
D@{ 5 [1, 1, 2, 2, 4]
DB[ 5 [0, 2, 2, 3, 3]
DIk 5 [1, 2, 2, 2, 3]
DBk 5 [1, 1, 2, 3, 3]
DK[ 5 [1, 2, 2, 2, 3]
DLo 5 [2, 2, 2, 2, 2]
E?Bw 6 [1, 1, 1, 1, 1, 5]
E?Dw 6 [0, 1, 1, 2, 2, 4]
E?Fg 6 [1, 1, 1, 1, 2, 4]
E?Kw 6 [0, 0, 2, 2, 3, 3]
E@HW 6 [0, 1, 2, 2, 2, 3]
E@FG 6 [1, 1, 1, 2, 2, 3]
E?LW 6 [0, 1, 1, 2, 3, 3]
E?NG 6 [1, 1, 1, 1, 3, 3]
E@N? 6 [1, 1, 2, 2, 2, 2]
E@YO 6 [1, 1, 2, 2, 2, 2]
E@QW 6 [1, 1, 1, 2, 2, 3]
E@Ow 6 [0, 1, 2, 2, 2, 3]
E_Cw 6 [1, 1, 1, 2, 2, 3]
E@T_ 6 [0, 2, 2, 2, 2, 2]
E_Ko 6 [1, 1, 2, 2, 2, 2]
F??Bw 7 [0, 1, 1, 1, 1, 1, 5]
F??Hw 7 [0, 0, 1, 1, 2, 2, 4]
F??Jg 7 [0, 1, 1, 1, 1, 2, 4]
F_?@w 7 [1, 1, 1, 1, 1, 1, 4]
F??Ww 7 [0, 0, 0, 2, 2, 3, 3]
F?CPW 7 [0, 0, 1, 2, 2, 2, 3]
F?CJG 7 [0, 1, 1, 1, 2, 2, 3]
F??^? 7 [1, 1, 1, 1, 1, 2, 3]
F??XW 7 [0, 0, 1, 1, 2, 3, 3]
F??ZG 7 [0, 1, 1, 1, 1, 3, 3]
F?CZ? 7 [0, 1, 1, 2, 2, 2, 2]
F_?Hg 7 [1, 1, 1, 1, 1, 2, 3]
F?CqO 7 [0, 1, 1, 2, 2, 2, 2]
F?CaW 7 [0, 1, 1, 1, 2, 2, 3]
F?LCG 7 [1, 1, 1, 1, 2, 2, 2]
F?C_w 7 [0, 0, 1, 2, 2, 2, 3]
FG?Gw 7 [0, 1, 1, 1, 2, 2, 3]
F?Ch_ 7 [0, 0, 2, 2, 2, 2, 2]
FG?Wo 7 [0, 1, 1, 2, 2, 2, 2]
F_?XO 7 [1, 1, 1, 1, 2, 2, 2]
FK?GW 7 [1, 1, 1, 1, 2, 2, 2]
**********************************************************************
Attachments (1)
Change History (17)
comment:1 Changed 10 years ago by
| Description: | modified (diff) |
|---|
comment:2 Changed 10 years ago by
| Cc: | R. Andrew Ohana added |
|---|
comment:3 follow-up: 4 Changed 10 years ago by
| Cc: | David Roe added |
|---|
comment:4 Changed 10 years ago by
Replying to vbraun:
Isn't this a recurring problem that might be fixed by a
# sort linesspecial in the doctesting framework? I.e. just sort the lines (say, alphabetically) before comparing want/got.
That's certainly doable. In this case you would probably want to also have two "header lines."
comment:5 follow-up: 6 Changed 10 years ago by
Maybe something like # sort lines[start:stop]? (So here we would want # sort lines[2:-2].)
comment:6 Changed 10 years ago by
Replying to ohanar:
Maybe something like
# sort lines[start:stop]? (So here we would want# sort lines[2:-1].)
Sounds like a good syntax to me. While we're at it, it may be worth having something like #sort list as well, which sorts based on comma as a separator rather than newlines.
comment:7 follow-up: 8 Changed 10 years ago by
I agree it would be useful to have something like that, but I don't know whether it's the right solution for this ticket (it would be the right solution for doctests returning a set).
The expected output is not in a random order, it's sorted in a particular way. For the user, we should change the code such that the graph database table is always returned in this order.
comment:8 Changed 10 years ago by
Replying to jdemeyer:
I agree it would be useful to have something like that, but I don't know whether it's the right solution for this ticket (it would be the right solution for doctests returning a set).
The expected output is not in a random order, it's sorted in a particular way. For the user, we should change the code such that the graph database table is always returned in this order.
Agreed. It would be nice if the output given to the user were sorted by number of vertices for example (as it is in the expected output).
comment:9 Changed 10 years ago by
| Authors: | → R. Andrew Ohana |
|---|---|
| Status: | new → needs_review |
ok, made it so that when displaying a graph query that has num_vertices as one of its columns, it will sort by the number of vertices (however, if there are multiple graphs in the query with the same number of vertices, it will still still do its own undefined ordering).
Alternatively it appears as if the graph6 column could be used for a well defined ordering (assuming that the column is in the query), but it completely screws up the current doctest.
comment:10 Changed 10 years ago by
If possible we should let the db do the sort (SELECT * FROM table ORDER BY col) instead of creating an in-memory table and then sorting that ourselves.
comment:11 Changed 10 years ago by
ok, new patch has the database do the sort -- choose whichever you prefer.
comment:12 Changed 10 years ago by
I'm in favor of the second approach, but there are a few remaining doctest failures
sage -t devel/sage/sage/graphs/generic_graph.py # 1 doctest failed sage -t devel/sage/sage/databases/sql_db.py # 1 doctest failed sage -t devel/sage/sage/graphs/graph.py # 1 doctest failed
comment:15 Changed 10 years ago by
| Reviewers: | → Volker Braun, Jeroen Demeyer |
|---|---|
| Status: | needs_review → positive_review |
comment:16 Changed 10 years ago by
| Merged in: | → sage-5.10.beta1 |
|---|---|
| Resolution: | → fixed |
| Status: | positive_review → closed |
Isn't this a recurring problem that might be fixed by a
# sort linesspecial in the doctesting framework? I.e. just sort the lines (say, alphabetically) before comparing want/got.