Opened 7 years ago
Closed 7 years ago
#13058 closed enhancement (fixed)
Hall-Janko Graph
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.2 |
Component: | graph theory | Keywords: | |
Cc: | wdj, kini, dimpase | Merged in: | sage-5.2.beta1 |
Authors: | Nathann Cohen, Dima Pasechnik | Reviewers: | Keshav Kini, Dima Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12942, #12945, #12952, #12971, #12980, #12981, #12982, #12989, #13038 | Stopgaps: |
Description (last modified by )
And heeeeeeeeeere is the Hall-Janko Graph !!
Thank you very much Dima for giving me its recipe :-)
Nathann
Apply:
Attachments (8)
Change History (36)
comment:1 Changed 7 years ago by
- Status changed from new to needs_review
Changed 7 years ago by
Changed 7 years ago by
comment:2 Changed 7 years ago by
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.
comment:3 Changed 7 years ago by
- Reviewers set to Keshav Kini
- Status changed from needs_review to positive_review
comment:4 Changed 7 years ago by
patchbot: apply trac_13058.patch trac_13058.reviewer.patch
comment:5 Changed 7 years ago by
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)
comment:6 Changed 7 years ago by
Here is a patch which does that.
patchbot: apply trac_13058.patch trac_13058.reviewer.patch trac_13058.attribution.patch
comment:7 Changed 7 years ago by
- Status changed from positive_review to needs_work
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
comment:8 Changed 7 years ago by
- Status changed from needs_work to needs_review
Changed 7 years ago by
comment:9 Changed 7 years ago by
- Description modified (diff)
comment:10 Changed 7 years ago by
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
.
comment:11 Changed 7 years ago by
- Reviewers changed from Keshav Kini to Keshav Kini, Dima Pasechnik
- Status changed from needs_review to positive_review
comment:12 Changed 7 years ago by
Thaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaanks !! :-)
Nathann
comment:13 Changed 7 years ago by
- Description modified (diff)
comment:14 Changed 7 years ago by
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...
comment:15 Changed 7 years ago by
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
comment:16 Changed 7 years ago by
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...
comment:17 Changed 7 years ago by
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
comment:18 Changed 7 years ago by
- Description modified (diff)
comment:19 Changed 7 years ago by
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
comment:20 Changed 7 years ago by
Hmmm... Unless you type g.set_pos(d) somewhere, doesn't it build an embedding for nothing ?
Nathann
comment:21 Changed 7 years ago by
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.
comment:22 Changed 7 years ago by
Oh right. I wrote this for nothing then. Sorry, I will check the patch right now then :-)
Nathann
comment:23 Changed 7 years ago by
Ok, positive review again ! :-)
Nathann
comment:24 Changed 7 years ago by
- Milestone changed from sage-5.1 to sage-5.2
comment:25 Changed 7 years ago by
- Status changed from positive_review to needs_work
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 **********************************************************************
comment:26 Changed 7 years ago by
- Description modified (diff)
- Status changed from needs_work to positive_review
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
comment:27 Changed 7 years ago by
- Description modified (diff)
New patch to replace them all :-P
- 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
- trac_13058-bugfix_and_speedup.patch
is now equivalent to :
Changed 7 years ago by
Changed 7 years ago by
comment:28 Changed 7 years ago by
- Merged in set to sage-5.2.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
apply to $SAGE_ROOT/devel/sage