Opened 13 years ago

Closed 13 years ago

Last modified 7 years ago

#7634 closed enhancement (fixed)

switch default Sage graphs over to c_graph, and split up graph.py and graph_generators.py

Reported by: Robert Miller Owned by: Robert Miller
Priority: major Milestone: sage-4.3.1
Component: graph theory Keywords:
Cc: Nathann Cohen, Minh Van Nguyen, William Stein, Robert Bradshaw, Jason Grout Merged in: sage-4.3.1.alpha2
Authors: Robert Miller Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Frédéric Chapoton)

This is currently under discussion here:

http://groups.google.com/group/sage-devel/browse_thread/thread/8edd29e9bddc67e5

I realized that it's probably actually time to switch over, since there are a few other developers working on Sage graphs besides just me now. That way if anything slows down, we are likely to find it out pretty quickly, and get it fixed. And, with the new defaults, things already feel more speedy:

BEFORE:

sage -t  "devel/sage-main/sage/graphs/graph.py"             
 [113.1 s]

AFTER:

sage -t  "devel/sage-main/sage/graphs/graph.py"             
 [78.5 s]

Attachments (3)

trac_7634-switchover.patch (15.7 KB) - added by Robert Miller 13 years ago.
depends on 4.3.1.alpha1
trac_7634-refactor.patch (1017.4 KB) - added by Robert Miller 13 years ago.
depends on trac_7634-switchover.patch
trac_7634-fix-pickle.patch (608 bytes) - added by Robert Miller 13 years ago.
based on trac_7634-refactor.patch

Download all attachments as: .zip

Change History (23)

comment:1 Changed 13 years ago by Minh Van Nguyen

Description: modified (diff)

comment:2 Changed 13 years ago by Nathann Cohen

Status: newneeds_info

Hmmm... When applying your patch here is what I get :

~/sage/sage-A/sage/graphs$ sage -t graph.py 
sage -t  "devel/sage-A/sage/graphs/graph.py"                
*** *** Error: TIMED OUT! PROCESS KILLED! *** ***
*** *** Error: TIMED OUT! *** ***
A mysterious error (perhaps a memory error?) occurred, which may have crashed doctest.
         [360.5 s]
exit code: 768
 
----------------------------------------------------------------------
The following tests failed:


        sage -t  "devel/sage-A/sage/graphs/graph.py"
Total time for all tests: 360.5 seconds

I know that this could not give you much information, but I do not know of any way to make -t more verbose... any idea ?

Nathann

comment:3 Changed 13 years ago by Nathann Cohen

Hmmm, it seems to come from the docstring

G = graphs.CubeGraph(8)
H = G.distance_graph([1,3,5,7])

Which is *very* long !

comment:4 in reply to:  2 Changed 13 years ago by Alex Ghitza

Replying to ncohen:


The following tests failed:

sage -t "devel/sage-A/sage/graphs/graph.py"

Total time for all tests: 360.5 seconds }}} I know that this could not give you much information, but I do not know of any way to make -t more verbose... any idea ?

I would try this :)

sage -t -verbose graph.py

comment:5 Changed 13 years ago by Nathann Cohen

Status: needs_infoneeds_work

Yes, I found it... So stupid of not having checked :-)

By the way, the problem indeed comes from this distance_graph doctest !

Nathann

comment:6 Changed 13 years ago by Robert Miller

This is because distance_graph ultimately relies on shortest_path, which uses the networkx graphs. In other words, for each pair of vertices distance_graphs calls shortest_path, which creates a copy of the graph, calls a NetworkX distance function on it, and discards it. I have created a separate ticket for this issue at #7640.

comment:7 Changed 13 years ago by Jason Grout

Cc: Jason Grout added

comment:8 Changed 13 years ago by Robert Miller

Cc: Jason Grout removed

I guess it should be somewhere on the ticket that #7651 should be taken care of first, also.

comment:9 Changed 13 years ago by Nathann Cohen

With the patch from #7640, it gives :

BEFORE:

G = graphs.CubeGraph(8)
sage: time a=G.distance_graph([1,3,5,7])
CPU times: user 8.15 s, sys: 0.03 s, total: 8.17 s
Wall time: 8.18 s

AFTER:

G = graphs.CubeGraph(8)
sage: time a=G.distance_graph([1,3,5,7])
CPU times: user 6.51 s, sys: 0.03 s, total: 6.55 s
Wall time: 6.56 s

comment:10 Changed 13 years ago by Robert Miller

Also need to be closed first: #7671 and #7672

comment:11 Changed 13 years ago by Robert Miller

Add #7673 to the list.

comment:12 Changed 13 years ago by Robert Miller

Cc: Jason Grout added

sorry, jason, i accidentally removed you from the cc block (not sure what happened there)

comment:13 Changed 13 years ago by Robert Miller

Summary: switch default Sage graphs over to c_graph[not ready] switch default Sage graphs over to c_graph

comment:14 Changed 13 years ago by Robert Miller

Summary: [not ready] switch default Sage graphs over to c_graph[not ready] switch default Sage graphs over to c_graph, and split up graph.py

The current patch does not split up graph.py, but the final version will...

Changed 13 years ago by Robert Miller

Attachment: trac_7634-switchover.patch added

depends on 4.3.1.alpha1

Changed 13 years ago by Robert Miller

Attachment: trac_7634-refactor.patch added

depends on trac_7634-switchover.patch

comment:15 Changed 13 years ago by Robert Miller

Status: needs_workneeds_review
Summary: [not ready] switch default Sage graphs over to c_graph, and split up graph.pyswitch default Sage graphs over to c_graph, and split up graph.py and graph_generators.py

comment:16 Changed 13 years ago by Jason Grout

Oh boy. I spent some time yesterday and today adding a few functions and cleaning up some documentation to graph.py. Well, you beat me to being ready, so I guess I'll rebase my patch on top of this one, hoping it gets into 4.3.1 so my patch on top of it can get in too.

comment:17 Changed 13 years ago by Nathann Cohen

Status: needs_reviewpositive_review

Well, this one does its jobs, and *finally* splits the graph.py file. c_graphs are now the default ones in Sage, and this patch renames what has to be.

Positive review/Good work/Excellent news !

Nathann

Changed 13 years ago by Robert Miller

Attachment: trac_7634-fix-pickle.patch added

based on trac_7634-refactor.patch

comment:18 Changed 13 years ago by Robert Miller

Merged in: 4.3.1.alpha2
Resolution: fixed
Reviewers: Nathann Cohen
Status: positive_reviewclosed

comment:19 Changed 13 years ago by Minh Van Nguyen

Merged in: 4.3.1.alpha2sage-4.3.1.alpha2

comment:20 Changed 7 years ago by Frédéric Chapoton

Description: modified (diff)
Note: See TracTickets for help on using tickets.