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:

Status badges

Description (last modified by jdemeyer)

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 ohanar 8 years ago.
apply to sage library

Download all attachments as: .zip

Change History (17)

comment:1 Changed 8 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 8 years ago by ohanar

  • Cc ohanar added

comment:3 follow-up: Changed 8 years ago by vbraun

  • Cc roed 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 8 years ago by roed

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 follow-up: Changed 8 years ago by ohanar

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

Last edited 8 years ago by ohanar (previous) (diff)

comment:6 in reply to: ↑ 5 Changed 8 years ago by roed

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: Changed 8 years ago by 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.

comment:8 in reply to: ↑ 7 Changed 8 years ago by roed

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 ohanar

  • Authors set to R. Andrew Ohana
  • 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 vbraun

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 ohanar

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

comment:12 Changed 8 years ago by vbraun

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 ncohen

(cc me)

Changed 8 years ago by ohanar

apply to sage library

comment:14 Changed 8 years ago by ohanar

ok, new patch resolves those doctests

comment:15 Changed 8 years ago by jdemeyer

  • Reviewers set to Volker Braun, Jeroen Demeyer
  • Status changed from needs_review to positive_review

comment:16 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.10.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.