Opened 6 years ago

Closed 6 years ago

Last modified 6 years ago

#14532 closed enhancement (fixed)

Symplectic graphs

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.10
Component: graph theory Keywords: strongly regular graphs
Cc: azi Merged in: sage-5.10.beta4
Authors: Nathann Cohen Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14217 Stopgaps:

Attachments (3)

trac_14532.patch (3.0 KB) - added by ncohen 6 years ago.
trac_14532_review-fc.patch (1.3 KB) - added by chapoton 6 years ago.
trac_14532-rebased.patch (808 bytes) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (32)

comment:1 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

comment:2 follow-up: Changed 6 years ago by azi

Hello!

Sry for comming back at you so late. I had some other stuff lately!

Anways, the code looks fine (read it, run it, and obviously run sage -t) I only have two remarks.

  1. Maybe we should check if d is even and also nonzero (perhaps >= 2) since that is also a invalid parameter.
  1. I would change the line
     Graph([map(tuple,PV), lambda x,y:V(x)*(M*V(y)) == 0], loops = False) 
    }}} to
    
    {{{
    {{{
     Graph((map(tuple,PV), lambda x,y:V(x)*(M*V(y)) == 0), loops = False) 
    }}} 
    }}}
    
    which should be 2x faster.
    
    Best,
    
    Jernej
    
Last edited 6 years ago by azi (previous) (diff)

comment:3 in reply to: ↑ 2 Changed 6 years ago by ncohen

Helloooooooooooooo !!

Sry for comming back at you so late. I had some other stuff lately!

Come on, I am already very thankful that you take the time to review these patches !!!

  1. Maybe we should check if d is even and also nonzero (perhaps >= 2) since that is also a invalid parameter.

Done

  1. I would change the line
     Graph([map(tuple,PV), lambda x,y:V(x)*(M*V(y)) == 0], loops = False) 
    }}} to
    
    {{{
    {{{
     Graph((map(tuple,PV), lambda x,y:V(x)*(M*V(y)) == 0), loops = False) 
    }}} 
    }}}
    
    which should be 2x faster.
    

O_o

Here is what I get when I change it :

sage: graphs.SymplecticGraph(4,4)         
...
NetworkXError: Input is not a known data type for conversion.

But what do you think it should do, and why do you think that it should be 2x faster ? O_o

Nathann

comment:4 Changed 6 years ago by azi

I may be shooting random nonsense of course but in general it is much better to not create lists [] but iterators (). Since in the former case a list has to first be created (1 for loop) and then iterated over (2 for loop). Example

sage: %timeit max((i for i in xrange(100)))
100000 loops, best of 3: 14.5 us per loop
sage: %timeit max([i for i in xrange(100)])
10000 loops, best of 3: 30 us per loop

and even faster in this case would be

sage: %timeit 99
1000000 loops, best of 3: 429 ns per loo

comment:5 Changed 6 years ago by ncohen

Yepyep but no list is created in this case. A list of size 2 is given to the Graph constructor : the first element is a list of vertices, the second element is a function that gives adjacent pairs.

Nathann

comment:6 Changed 6 years ago by azi

Oh FML you see sometimes I do shoot random nonsense!

In this case the patch is ofc OK. If I were to do this I would make the additional test check (since we're already doing them) but its fine as is as well.

comment:7 follow-up: Changed 6 years ago by chapoton

there is a typo in "simplectic" at least twice

comment:8 in reply to: ↑ 7 Changed 6 years ago by ncohen

there is a typo in "simplectic" at least twice

Arggggggggg... Fixed :-P

Most probably because of that cursed sImplex :-P

Nathann

Changed 6 years ago by ncohen

comment:9 Changed 6 years ago by chapoton

hello,

if you are happy with my review patch (just removing unused imports), you can set a positive review on my behalf.

Changed 6 years ago by chapoton

comment:10 Changed 6 years ago by chapoton

  • Keywords strongly regular graphs added
  • Reviewers set to Frédéric Chapoton

comment:11 Changed 6 years ago by ncohen

  • Status changed from needs_review to positive_review

All tests pass ! Thank you very much for your help :-)

Nathann

comment:12 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work
sage -t devel/sage/sage/graphs/generators/families.py
**********************************************************************
File "devel/sage/sage/graphs/generators/families.py", line 1992, in sage.graphs.generators.families.SymplecticGraph
Failed example:
    g = graphs.SymplecticGraph(6,2)
Exception raised:
    Traceback (most recent call last):
      File "/mazur/release/merger/sage-5.10.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 466, in _run
        self.execute(example, compiled, test.globs)
      File "/mazur/release/merger/sage-5.10.beta3/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 825, in execute
        exec compiled in globs
      File "<doctest sage.graphs.generators.families.SymplecticGraph[0]>", line 1, in <module>
        g = graphs.SymplecticGraph(Integer(6),Integer(2))
      File "/mazur/release/merger/sage-5.10.beta3/local/lib/python2.7/site-packages/sage/graphs/generators/families.py", line 2000, in SymplecticGraph
        from sage.schemes.generic.projective_space import ProjectiveSpace
    ImportError: No module named projective_space
**********************************************************************

comment:13 Changed 6 years ago by jdemeyer

  • Dependencies set to #14217

Changed 6 years ago by ncohen

comment:14 Changed 6 years ago by ncohen

  • Description modified (diff)

comment:15 Changed 6 years ago by ncohen

  • Status changed from needs_work to positive_review

Rebased !

Nathann

comment:16 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.10.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:17 follow-up: Changed 6 years ago by dimpase

maybe Sage should have "polar space" graphs in general, not, only symplectic ones?

comment:18 in reply to: ↑ 17 ; follow-up: Changed 6 years ago by ncohen

Helloooooooo !

maybe Sage should have "polar space" graphs in general, not, only symplectic ones?

Well, yes it would be nice indeed, but I do not know how to build them. I guess that it only takes 5~6 lines, like for the symplectic ones, but I don't know which ones. Actually, I have no idea on earth what these graphs are, except what I could read (and understand, which is even less) from Brouwer's website.

http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html

I believe I created what he calls a VO^- graph (graphs.BrouwerHaemersGraph), and the same code worked for different parameters but I was not able to make it work in characteristic two, and so I did not write this more general patch.

If you know how to make it work, I would be glad to see it in Sage too :-P

Nathann

comment:19 in reply to: ↑ 18 ; follow-up: Changed 6 years ago by dimpase

Replying to ncohen:

Helloooooooo !

maybe Sage should have "polar space" graphs in general, not, only symplectic ones?

Well, yes it would be nice indeed, but I do not know how to build them. I guess that it only takes 5~6 lines, like for the symplectic ones, but I don't know which ones. Actually, I have no idea on earth what these graphs are, except what I could read (and understand, which is even less) from Brouwer's website.

http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html

I believe I created what he calls a VO^- graph (graphs.BrouwerHaemersGraph), and the same code worked for different parameters but I was not able to make it work in characteristic two, and so I did not write this more general patch.

no, these are different species. I mean classical polar spaces as introduced by J.Tits (or even long before him). See e.g. Sect 6.5 of http://www.maths.qmul.ac.uk/~pjc/pps/pps6.pdf

To construct these, you need to be able to create the corresponding forms, which are well-studied by group theory, as they lead to finite classical groups. GAP has code to create these forms; it's not completely trivial in characteristic two. You can actually just call GAP! E.g.

gap> Display(InvariantQuadraticForm(GO(1,6,2)).matrix);
 . 1 . . . .
 . . . . . .
 . . . 1 . .
 . . . . . .
 . . . . . 1
 . . . . . .
gap> Display(InvariantQuadraticForm(GO(-1,6,2)).matrix);
 . 1 . . . .
 . . . . . .
 . . 1 1 . .
 . . . 1 . .
 . . . . . 1
 . . . . . .
gap> Display(InvariantSesquilinearForm(GU(6,2)).matrix);
 . . . . . 1
 . . . . 1 .
 . . . 1 . .
 . . 1 . . .
 . 1 . . . .
 1 . . . . .
gap> Display(InvariantBilinearForm(Sp(6,3)).matrix);
 . . . . . 1
 . . . . 1 .
 . . . 1 . .
 . . 2 . . .
 . 2 . . . .
 2 . . . . .
gap> 

etc...

Last edited 6 years ago by dimpase (previous) (diff)

comment:20 follow-up: Changed 6 years ago by dimpase

The more one goes down this road, the more the lack of a proper backend for graphs with big automorphism groups shows. Perhaps we can try implement something next month in Paris.

comment:21 in reply to: ↑ 20 ; follow-up: Changed 6 years ago by ncohen

The more one goes down this road, the more the lack of a proper backend for graphs with big automorphism groups shows. Perhaps we can try implement something next month in Paris.

Ahahah. Well, why not ? But I really know next to nothing about those, and what people use them for :-)

Nathann

comment:22 in reply to: ↑ 21 ; follow-up: Changed 6 years ago by dimpase

Replying to ncohen:

The more one goes down this road, the more the lack of a proper backend for graphs with big automorphism groups shows. Perhaps we can try implement something next month in Paris.

Ahahah. Well, why not ? But I really know next to nothing about those, and what people use them for :-)

it's useful to

  • store the graphs more compactly
  • compute their properties faster

Isn't it obvious? All these graphs you construct lately have huge automorphism groups, often arc-transitive and/or distance-transitive.

Last edited 6 years ago by dimpase (previous) (diff)

comment:23 in reply to: ↑ 22 ; follow-up: Changed 6 years ago by ncohen

Isn't it obvious?

What do you use them for ? What do you want to compute ? Graphs have a lot of method, you know.. :-P

Nathann

comment:24 Changed 6 years ago by ncohen

By the way, and because these graphs are usually immutable (and dense), I wrote a couple of C functions (#14589) to store very compactly an adjacency matrix. Of course it cannot compare with an encoding by generators of the automorphism group, but a graph on 30 000 vertices can be stored on 128MB.

Nathann

comment:25 in reply to: ↑ 23 ; follow-up: Changed 6 years ago by dimpase

Replying to ncohen:

Isn't it obvious?

What do you use them for ? What do you want to compute ? Graphs have a lot of method, you know.. :-P

Obviously, regularity properties - and this is very fast with such data. Then, e.g., e.g. maximum cliques, or an optimal colouring. It's downright hopeless to do without taking symmetries into account. Or Lovasz theta number...

comment:26 in reply to: ↑ 25 ; follow-up: Changed 6 years ago by ncohen

Obviously, regularity properties - and this is very fast with such data. Then, e.g., e.g. maximum cliques, or an optimal colouring. It's downright hopeless to do without taking symmetries into account. Or Lovasz theta number...

Hmmm... Looks like you will have an awful amount of code to write :-P

Nathann

comment:27 in reply to: ↑ 26 Changed 6 years ago by dimpase

Replying to ncohen:

Obviously, regularity properties - and this is very fast with such data. Then, e.g., e.g. maximum cliques, or an optimal colouring. It's downright hopeless to do without taking symmetries into account. Or Lovasz theta number...

Hmmm... Looks like you will have an awful amount of code to write :-P

I wouldn't classify calls to GAP as "awful amount of code" :)

comment:28 Changed 6 years ago by ncohen

Oh ! Well, if it's all in there already, then.... :-)

Nathann

comment:29 in reply to: ↑ 19 Changed 6 years ago by ncohen

To construct these, you need to be able to create the corresponding forms, which are well-studied by group theory, as they lead to finite classical groups. GAP has code to create these forms; it's not completely trivial in characteristic two. You can actually just call GAP!

This is now #14631 !

Nathann

Note: See TracTickets for help on using tickets.