search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.38k stars 469 forks source link

Hall-Janko Graph #13058

Closed 6bdad4c1-1e26-4f2f-a442-a01a2292c181 closed 12 years ago

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago

And heeeeeeeeeere is the Hall-Janko Graph !!

Thank you very much Dima for giving me its recipe :-)

Nathann

Apply:

Depends on #12942 Depends on #12945 Depends on #12952 Depends on #12971 Depends on #12980 Depends on #12981 Depends on #12982 Depends on #12989 Depends on #13038

CC: @wdjoyner @kini @dimpase

Component: graph theory

Author: Nathann Cohen, Dima Pasechnik

Reviewer: Keshav Kini, Dima Pasechnik

Merged: sage-5.2.beta1

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

kini commented 12 years ago

Attachment: trac_13058.patch.gz

apply to $SAGE_ROOT/devel/sage

kini commented 12 years ago
comment:2

Attachment: trac_13058.reviewer.patch.gz

Thanks! Here's a reviewer patch.

For future reference, if you have a long string literal which you want to split into pieces, you can do it by just placing the strings next to each other separated by whitespace:

>>> "a" "b" == "ab"
True

This is actually more efficient than writing "a" + "b", because it is parsed directly as "ab", whereas with "a" + "b", Python first creates two string objects "a" and "b", and then concatenates them together into a new string object "ab", which essentially causes two useless objects to be created.

I decreased the indentation of some lines in the doctest by two spaces because later, once David Roe's work at #12415 fixes #10458, the ... can be replaced with ....: (two characters more) without making the indent excessively wide.

kini commented 12 years ago

Reviewer: Keshav Kini

kini commented 12 years ago
comment:4

patchbot: apply trac_13058.patch trac_13058.reviewer.patch

dimpase commented 12 years ago
comment:5

Hi Nathann, hi Keshav, could you please acknowledge the source of the permutations used (they are from http://brauer.maths.qmul.ac.uk/Atlas/v3/permrep/J2G1-p100B0)

kini commented 12 years ago

Attachment: trac_13058.attribution.patch.gz

apply to $SAGE_ROOT/devel/sage

kini commented 12 years ago
comment:6

Here is a patch which does that.

patchbot: apply trac_13058.patch trac_13058.reviewer.patch trac_13058.attribution.patch

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago
comment:7

Hellooooooooo Keshav !! Could you take a look at that ? Dima though that it would be better to make both constructors available, just to check for correction :-)

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago

Description changed:

--- 
+++ 
@@ -3,3 +3,10 @@
 Thank you very much Dima for giving me its recipe `:-)`

 Nathann
+
+Apply:
+
+* [attachment: trac_13058.patch](https://github.com/sagemath/sage-prod/files/10655680/trac_13058.patch.gz)
+* [attachment: trac_13058.reviewer.patch](https://github.com/sagemath/sage-prod/files/10655681/trac_13058.reviewer.patch.gz)
+* [attachment: trac_13058.attribution.patch](https://github.com/sagemath/sage-prod/files/10655682/trac_13058.attribution.patch.gz)
+* [attachment: trac_13058-fromstring.patch](https://github.com/sagemath/sage-prod/files/10655683/trac_13058-fromstring.patch.gz)
6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago
comment:9

Attachment: trac_13058-fromstring.patch.gz

kini commented 12 years ago
comment:10
sage: timeit("graphs.HallJankoGraph()")
25 loops, best of 3: 25.1 ms per loop
sage: timeit("graphs.HallJankoGraph(from_string=False)")
5 loops, best of 3: 10.8 s per loop

I added "# long time" to the doctests for from_string=False.

kini commented 12 years ago

apply to $SAGE_ROOT/devel/sage

kini commented 12 years ago
comment:11

Attachment: trac_13058-fromstring.reviewer.patch.gz

kini commented 12 years ago

Changed reviewer from Keshav Kini to Keshav Kini, Dima Pasechnik

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago
comment:12

Thaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaanks !! :-)

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago

Description changed:

--- 
+++ 
@@ -10,3 +10,4 @@
 * [attachment: trac_13058.reviewer.patch](https://github.com/sagemath/sage-prod/files/10655681/trac_13058.reviewer.patch.gz)
 * [attachment: trac_13058.attribution.patch](https://github.com/sagemath/sage-prod/files/10655682/trac_13058.attribution.patch.gz)
 * [attachment: trac_13058-fromstring.patch](https://github.com/sagemath/sage-prod/files/10655683/trac_13058-fromstring.patch.gz)
+* [attachment: trac_13058-fromstring.reviewer.patch](https://github.com/sagemath/sage-prod/files/10655684/trac_13058-fromstring.reviewer.patch.gz)
dimpase commented 12 years ago
comment:14

By the way, why

edge_list = [] 
for u, v in edges: 
   edge_list.append((int(u),int(v))) 

   g = graph.Graph(edge_list, pos={})

and not 

   g = graph.Graph([(int(u),int(v)) for u,v in edges], pos={})

The latter is not only shorter and more readable, but faster, too...

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago
comment:15

Oh, right.. Well, it's just because this piece of code did other things before... Well it does not matter much and this patch has been changed many times already -- I will fix that discretely later on in a totally unrelated patch :-)

Nathann

kini commented 12 years ago
comment:16

Well, actually it is currently

edge_list = [] 
for u, v in edges: 
   edge_list.append((int(u),int(v))) 

g = graph.Graph(edge_list, pos={})

If the last line had been indented like Dima said it would be much, much worse :P

An even faster way is probably the following:

g = graph.Graph(((int(u), int(v)) for u,v in edges), pos={})

And we shouldn't need pos={} in order to use _circle_embedding() and _line_embedding() either.

Good catch, Dima - not sure why I missed that...

kini commented 12 years ago
comment:17

Actually it seems that this makes little difference to the efficiency of the constructor, for some reason. Still, it is easier to read, as Dima said. And actually, building a list is probably better than a generator expression after all, since we don't really have enough edges that we have to worry about memory usage. Sorry, Nathann, but I'm going to attach another patch... :P

kini commented 12 years ago

Attachment: trac_13058-no-pos.patch.gz

apply to $SAGE_ROOT/devel/sage

kini commented 12 years ago

Description changed:

--- 
+++ 
@@ -11,3 +11,4 @@
 * [attachment: trac_13058.attribution.patch](https://github.com/sagemath/sage-prod/files/10655682/trac_13058.attribution.patch.gz)
 * [attachment: trac_13058-fromstring.patch](https://github.com/sagemath/sage-prod/files/10655683/trac_13058-fromstring.patch.gz)
 * [attachment: trac_13058-fromstring.reviewer.patch](https://github.com/sagemath/sage-prod/files/10655684/trac_13058-fromstring.reviewer.patch.gz)
+* [attachment: trac_13058-no-pos.patch](https://github.com/sagemath/sage-prod/files/10655685/trac_13058-no-pos.patch.gz)
kini commented 12 years ago
comment:19

patchbot: apply trac_13058.patch trac_13058.reviewer.patch trac_13058.attribution.patch trac_13058-fromstring.patch trac_13058-fromstring.reviewer.patch trac_13058-no-pos.patch

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago
comment:20

Hmmm... Unless you type g.set_pos(d) somewhere, doesn't it build an embedding for nothing ?

Nathann

kini commented 12 years ago
comment:21

g.set_pos(d) is still in the function, where you originally put it. It is not shown in the context lines in the patch because it is too far away from where I made changes.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago
comment:22

Oh right. I wrote this for nothing then. Sorry, I will check the patch right now then :-)

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago
comment:23

Ok, positive review again ! :-)

Nathann

jdemeyer commented 12 years ago
comment:25

I get doctest errors:

sage -t  --long -force_lib devel/sage/sage/graphs/graph_generators.py
**********************************************************************
File "/release/merger/sage-5.2.beta1/devel/sage-main/sage/graphs/graph_generators.py", line 1570:
    sage: gg = graphs.HallJankoGraph(from_string=False) # long time
Exception raised:
    Traceback (most recent call last):
      File "/release/merger/sage-5.2.beta1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/release/merger/sage-5.2.beta1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/release/merger/sage-5.2.beta1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_15[10]>", line 1, in <module>
        gg = graphs.HallJankoGraph(from_string=False) # long time###line 1570:
    sage: gg = graphs.HallJankoGraph(from_string=False) # long time
      File "/release/merger/sage-5.2.beta1/local/lib/python/site-packages/sage/graphs/graph_generators.py", line 1646, in HallJankoGraph
        g = graph([(int(u), int(v)) for u, v in edges])
    TypeError: 'module' object is not callable
**********************************************************************
File "/release/merger/sage-5.2.beta1/devel/sage-main/sage/graphs/graph_generators.py", line 1571:
    sage: g == gg # long time
Exception raised:
    Traceback (most recent call last):
      File "/release/merger/sage-5.2.beta1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/release/merger/sage-5.2.beta1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/release/merger/sage-5.2.beta1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_15[11]>", line 1, in <module>
        g == gg # long time###line 1571:
    sage: g == gg # long time
    NameError: name 'gg' is not defined
**********************************************************************
6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago

Description changed:

--- 
+++ 
@@ -12,3 +12,4 @@
 * [attachment: trac_13058-fromstring.patch](https://github.com/sagemath/sage-prod/files/10655683/trac_13058-fromstring.patch.gz)
 * [attachment: trac_13058-fromstring.reviewer.patch](https://github.com/sagemath/sage-prod/files/10655684/trac_13058-fromstring.reviewer.patch.gz)
 * [attachment: trac_13058-no-pos.patch](https://github.com/sagemath/sage-prod/files/10655685/trac_13058-no-pos.patch.gz)
+* [attachment: trac_13058-bugfix_and_speedup.patch](https://github.com/sagemath/sage-prod/files/10655687/trac_13058-bugfix_and_speedup.patch.gz)
6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago
comment:26

Sorryyyyyyyyyyyy.... graph should have been replaced by Graph. On the bright side I rewrote a line using the .sage() method I discovered in the meantime, and it makes a big difference in speed :-)

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago

Description changed:

--- 
+++ 
@@ -6,10 +6,4 @@

 Apply:

-* [attachment: trac_13058.patch](https://github.com/sagemath/sage-prod/files/10655680/trac_13058.patch.gz)
-* [attachment: trac_13058.reviewer.patch](https://github.com/sagemath/sage-prod/files/10655681/trac_13058.reviewer.patch.gz)
-* [attachment: trac_13058.attribution.patch](https://github.com/sagemath/sage-prod/files/10655682/trac_13058.attribution.patch.gz)
-* [attachment: trac_13058-fromstring.patch](https://github.com/sagemath/sage-prod/files/10655683/trac_13058-fromstring.patch.gz)
-* [attachment: trac_13058-fromstring.reviewer.patch](https://github.com/sagemath/sage-prod/files/10655684/trac_13058-fromstring.reviewer.patch.gz)
-* [attachment: trac_13058-no-pos.patch](https://github.com/sagemath/sage-prod/files/10655685/trac_13058-no-pos.patch.gz)
-* [attachment: trac_13058-bugfix_and_speedup.patch](https://github.com/sagemath/sage-prod/files/10655687/trac_13058-bugfix_and_speedup.patch.gz)
+* [attachment: trac_13058-all.patch](https://github.com/sagemath/sage-prod/files/10655686/trac_13058-all.patch.gz)
6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago
comment:27

New patch to replace them all :-P

is now equivalent to :

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 12 years ago

Attachment: trac_13058-all.patch.gz

Attachment: trac_13058-bugfix_and_speedup.patch.gz

jdemeyer commented 12 years ago

Merged: sage-5.2.beta1