Opened 8 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 ncohen)

And heeeeeeeeeere is the Hall-Janko Graph !!

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

Nathann

Apply:

Attachments (8)

trac_13058.patch (7.1 KB) - added by ncohen 8 years ago.
trac_13058.reviewer.patch (11.6 KB) - added by kini 8 years ago.
apply to $SAGE_ROOT/devel/sage
trac_13058.attribution.patch (1.5 KB) - added by kini 8 years ago.
apply to $SAGE_ROOT/devel/sage
trac_13058-fromstring.patch (5.2 KB) - added by ncohen 8 years ago.
trac_13058-fromstring.reviewer.patch (2.4 KB) - added by kini 8 years ago.
apply to $SAGE_ROOT/devel/sage
trac_13058-no-pos.patch (1.5 KB) - added by kini 8 years ago.
apply to $SAGE_ROOT/devel/sage
trac_13058-all.patch (8.2 KB) - added by ncohen 7 years ago.
trac_13058-bugfix_and_speedup.patch (1.1 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (36)

comment:1 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

Changed 8 years ago by ncohen

Changed 8 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:2 Changed 8 years ago by kini

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.

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

comment:3 Changed 8 years ago by kini

  • Reviewers set to Keshav Kini
  • Status changed from needs_review to positive_review

comment:4 Changed 8 years ago by kini

patchbot: apply trac_13058.patch trac_13058.reviewer.patch

comment:5 Changed 8 years ago by dimpase

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)

Changed 8 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:6 Changed 8 years ago by kini

Here is a patch which does that.

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

comment:7 Changed 8 years ago by ncohen

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

  • Status changed from needs_work to needs_review

Changed 8 years ago by ncohen

comment:9 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:10 Changed 8 years ago by kini

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.

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

Changed 8 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:11 Changed 8 years ago by kini

  • Reviewers changed from Keshav Kini to Keshav Kini, Dima Pasechnik
  • Status changed from needs_review to positive_review

comment:12 Changed 8 years ago by ncohen

Thaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaanks !! :-)

Nathann

comment:13 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:14 Changed 8 years ago by dimpase

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 8 years ago by ncohen

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 8 years ago by kini

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 8 years ago by kini

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

Changed 8 years ago by kini

apply to $SAGE_ROOT/devel/sage

comment:18 Changed 8 years ago by kini

  • Description modified (diff)

comment:19 Changed 8 years ago by kini

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 8 years ago by ncohen

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

Nathann

comment:21 Changed 8 years ago by kini

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 8 years ago by ncohen

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

Nathann

comment:23 Changed 8 years ago by ncohen

Ok, positive review again ! :-)

Nathann

comment:24 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.1 to sage-5.2

comment:25 Changed 7 years ago by jdemeyer

  • 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 ncohen

  • 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

Changed 7 years ago by ncohen

Changed 7 years ago by ncohen

comment:28 Changed 7 years ago by jdemeyer

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