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 Jeroen Demeyer)

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)

trac14477.2.patch (20.2 KB) - added by R. Andrew Ohana 10 years ago.
apply to sage library

Download all attachments as: .zip

Change History (17)

comment:1 Changed 10 years ago by Jeroen Demeyer

Description: modified (diff)

comment:2 Changed 10 years ago by R. Andrew Ohana

Cc: R. Andrew Ohana added

comment:3 Changed 10 years ago by Volker Braun

Cc: David Roe added

Isn't this a recurring problem that might be fixed by a # sort lines special in the doctesting framework? I.e. just sort the lines (say, alphabetically) before comparing want/got.

comment:4 in reply to:  3 Changed 10 years ago by David Roe

Replying to vbraun:

Isn't this a recurring problem that might be fixed by a # sort lines special 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 Changed 10 years ago by R. Andrew Ohana

Maybe something like # sort lines[start:stop]? (So here we would want # sort lines[2:-1].)

Last edited 10 years ago by R. Andrew Ohana (previous) (diff)

comment:6 in reply to:  5 Changed 10 years ago by David Roe

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 Changed 10 years ago by Jeroen Demeyer

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 10 years ago by David Roe

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 R. Andrew Ohana

Authors: R. Andrew Ohana
Status: newneeds_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 Volker Braun

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 R. Andrew Ohana

ok, new patch has the database do the sort -- choose whichever you prefer.

comment:12 Changed 10 years ago by Volker Braun

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 10 years ago by Nathann Cohen

(cc me)

Changed 10 years ago by R. Andrew Ohana

Attachment: trac14477.2.patch added

apply to sage library

comment:14 Changed 10 years ago by R. Andrew Ohana

ok, new patch resolves those doctests

comment:15 Changed 10 years ago by Jeroen Demeyer

Reviewers: Volker Braun, Jeroen Demeyer
Status: needs_reviewpositive_review

comment:16 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.10.beta1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.