Opened 8 years ago
Closed 8 years ago
#14477 closed defect (fixed)
Graph database query results should be sorted
| Reported by: | jdemeyer | Owned by: | was |
|---|---|---|---|
| Priority: | critical | Milestone: | sage-5.10 |
| Component: | packages: huge | Keywords: | |
| Cc: | ohanar, roed | 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: |
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 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Cc ohanar added
comment:3 follow-up: ↓ 4 Changed 8 years ago by
- Cc roed added
comment:4 in reply to: ↑ 3 Changed 8 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 8 years ago by
Maybe something like # sort lines[start:stop]? (So here we would want # sort lines[2:-1].)
comment:6 in reply to: ↑ 5 Changed 8 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 8 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 in reply to: ↑ 7 Changed 8 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 8 years ago by
- Status changed from new to 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 8 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 8 years ago by
ok, new patch has the database do the sort -- choose whichever you prefer.
comment:12 Changed 8 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:13 Changed 8 years ago by
(cc me)
comment:14 Changed 8 years ago by
ok, new patch resolves those doctests
comment:15 Changed 8 years ago by
- Reviewers set to Volker Braun, Jeroen Demeyer
- Status changed from needs_review to positive_review
comment:16 Changed 8 years ago by
- Merged in set to sage-5.10.beta1
- Resolution set to fixed
- Status changed from positive_review to 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.