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

[rlmill]

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]

CC: @nathanncohen @sagetrac-mvngu @williamstein @robertwb @jasongrout

Component: graph theory

Author: Robert Miller

Reviewer: Nathann Cohen

Merged: sage-4.3.1.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/7634

[nathanncohen]

comment:2

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

[nathanncohen]

comment:3

Hmmm, it seems to come from the docstring

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

Which is very long !

[aghitza]

comment:4

Replying to @nathanncohen:

---

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

[nathanncohen]

comment:5

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

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

Nathann

[rlmill]

comment:6

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.

[rlmill]

comment:8

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

[nathanncohen]

comment:9

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

[rlmill]

comment:10

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

[rlmill]

comment:11

Add #7673 to the list.

[rlmill]

comment:12

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

[rlmill]

comment:14

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

[rlmill]

Attachment: trac_7634-switchover.patch.gz

depends on 4.3.1.alpha1

[rlmill]

depends on trac_7634-switchover.patch

[rlmill]

comment:15

Attachment: trac_7634-refactor.patch.gz

[jasongrout]

comment:16

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.

[nathanncohen]

comment:17

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

[rlmill]

based on trac_7634-refactor.patch

[rlmill]

comment:18

Attachment: trac_7634-fix-pickle.patch.gz

[rlmill]

Reviewer: Nathann Cohen

[rlmill]

Merged: 4.3.1.alpha2

[sagetrac-mvngu]

Changed merged from 4.3.1.alpha2 to sage-4.3.1.alpha2