Sage: Ticket #14532: Symplectic graphs
https://trac.sagemath.org/ticket/14532
<p>
Brand new pretty graphs <code>:-P</code>
</p>
<p>
Nathann
</p>
<p>
Apply :
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14532/trac_14532.patch" title="Attachment 'trac_14532.patch' in Ticket #14532">trac_14532.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14532/trac_14532.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14532/trac_14532_review-fc.patch" title="Attachment 'trac_14532_review-fc.patch' in Ticket #14532">trac_14532_review-fc.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14532/trac_14532_review-fc.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/14532/trac_14532-rebased.patch" title="Attachment 'trac_14532-rebased.patch' in Ticket #14532">trac_14532-rebased.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/14532/trac_14532-rebased.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/14532
Trac 1.2Nathann CohenSun, 05 May 2013 10:50:03 GMTstatus changed
https://trac.sagemath.org/ticket/14532#comment:1
https://trac.sagemath.org/ticket/14532#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketJernej AzarijaTue, 07 May 2013 11:51:37 GMT
https://trac.sagemath.org/ticket/14532#comment:2
https://trac.sagemath.org/ticket/14532#comment:2
<p>
Hello!
</p>
<p>
Sry for comming back at you so late. I had some other stuff lately!
</p>
<p>
Anways, the code looks fine (read it, run it, and obviously run sage -t) I only have two remarks.
</p>
<ol><li>Maybe we should check if d is even and also nonzero (perhaps >= 2) since that is also a invalid parameter.
</li></ol><ol start="2"><li>I would change the line
<pre class="wiki"> 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
</pre></li></ol>
TicketNathann CohenTue, 07 May 2013 12:12:12 GMT
https://trac.sagemath.org/ticket/14532#comment:3
https://trac.sagemath.org/ticket/14532#comment:3
<p>
Helloooooooooooooo !!
</p>
<blockquote class="citation">
<p>
Sry for comming back at you so late. I had some other stuff lately!
</p>
</blockquote>
<p>
Come on, I am already very thankful that you take the time to review these patches !!!
</p>
<blockquote class="citation">
<ol><li>Maybe we should check if d is even and also nonzero (perhaps >= 2) since that is also a invalid parameter.
</li></ol></blockquote>
<p>
Done
</p>
<blockquote class="citation">
<ol start="2"><li>I would change the line
<pre class="wiki"> 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.
</pre></li></ol></blockquote>
<p>
<code>O_o</code>
</p>
<p>
Here is what I get when I change it :
</p>
<pre class="wiki">sage: graphs.SymplecticGraph(4,4)
...
NetworkXError: Input is not a known data type for conversion.
</pre><p>
But what do you think it should do, and why do you think that it should be 2x faster ? <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketJernej AzarijaTue, 07 May 2013 12:35:58 GMT
https://trac.sagemath.org/ticket/14532#comment:4
https://trac.sagemath.org/ticket/14532#comment:4
<p>
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
</p>
<pre class="wiki">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
</pre><p>
and even faster in this case would be
</p>
<pre class="wiki">sage: %timeit 99
1000000 loops, best of 3: 429 ns per loo
</pre>
TicketNathann CohenTue, 07 May 2013 12:38:45 GMT
https://trac.sagemath.org/ticket/14532#comment:5
https://trac.sagemath.org/ticket/14532#comment:5
<p>
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.
</p>
<p>
Nathann
</p>
TicketJernej AzarijaTue, 07 May 2013 12:42:03 GMT
https://trac.sagemath.org/ticket/14532#comment:6
https://trac.sagemath.org/ticket/14532#comment:6
<p>
Oh FML you see sometimes I do shoot random nonsense!
</p>
<p>
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.
</p>
TicketFrédéric ChapotonTue, 07 May 2013 16:10:47 GMT
https://trac.sagemath.org/ticket/14532#comment:7
https://trac.sagemath.org/ticket/14532#comment:7
<p>
there is a typo in "simplectic" at least twice
</p>
TicketNathann CohenTue, 07 May 2013 16:25:58 GMT
https://trac.sagemath.org/ticket/14532#comment:8
https://trac.sagemath.org/ticket/14532#comment:8
<blockquote class="citation">
<p>
there is a typo in "simplectic" at least twice
</p>
</blockquote>
<p>
Arggggggggg... Fixed <code>:-P</code>
</p>
<p>
Most probably because of that cursed sImplex <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketNathann CohenTue, 07 May 2013 16:26:10 GMTattachment set
https://trac.sagemath.org/ticket/14532
https://trac.sagemath.org/ticket/14532
<ul>
<li><strong>attachment</strong>
set to <em>trac_14532.patch</em>
</li>
</ul>
TicketFrédéric ChapotonThu, 09 May 2013 16:12:06 GMT
https://trac.sagemath.org/ticket/14532#comment:9
https://trac.sagemath.org/ticket/14532#comment:9
<p>
hello,
</p>
<p>
if you are happy with my review patch (just removing unused imports), you can set a positive review on my behalf.
</p>
TicketFrédéric ChapotonThu, 09 May 2013 16:13:19 GMTattachment set
https://trac.sagemath.org/ticket/14532
https://trac.sagemath.org/ticket/14532
<ul>
<li><strong>attachment</strong>
set to <em>trac_14532_review-fc.patch</em>
</li>
</ul>
TicketFrédéric ChapotonThu, 09 May 2013 16:13:52 GMTkeywords, reviewer set
https://trac.sagemath.org/ticket/14532#comment:10
https://trac.sagemath.org/ticket/14532#comment:10
<ul>
<li><strong>keywords</strong>
<em>strongly</em> <em>regular</em> <em>graphs</em> added
</li>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton</em>
</li>
</ul>
TicketNathann CohenThu, 09 May 2013 18:14:23 GMTstatus changed
https://trac.sagemath.org/ticket/14532#comment:11
https://trac.sagemath.org/ticket/14532#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
All tests pass ! Thank you very much for your help <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketJeroen DemeyerMon, 13 May 2013 18:46:49 GMTstatus changed
https://trac.sagemath.org/ticket/14532#comment:12
https://trac.sagemath.org/ticket/14532#comment:12
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<pre class="wiki">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
**********************************************************************
</pre>
TicketJeroen DemeyerTue, 14 May 2013 09:35:08 GMTdependencies set
https://trac.sagemath.org/ticket/14532#comment:13
https://trac.sagemath.org/ticket/14532#comment:13
<ul>
<li><strong>dependencies</strong>
set to <em>#14217</em>
</li>
</ul>
TicketNathann CohenTue, 14 May 2013 09:41:45 GMTattachment set
https://trac.sagemath.org/ticket/14532
https://trac.sagemath.org/ticket/14532
<ul>
<li><strong>attachment</strong>
set to <em>trac_14532-rebased.patch</em>
</li>
</ul>
TicketNathann CohenTue, 14 May 2013 09:42:24 GMTdescription changed
https://trac.sagemath.org/ticket/14532#comment:14
https://trac.sagemath.org/ticket/14532#comment:14
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/14532?action=diff&version=14">diff</a>)
</li>
</ul>
TicketNathann CohenTue, 14 May 2013 09:44:48 GMTstatus changed
https://trac.sagemath.org/ticket/14532#comment:15
https://trac.sagemath.org/ticket/14532#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Rebased !
</p>
<p>
Nathann
</p>
TicketJeroen DemeyerFri, 17 May 2013 06:32:53 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/14532#comment:16
https://trac.sagemath.org/ticket/14532#comment:16
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.10.beta4</em>
</li>
</ul>
TicketDima PasechnikTue, 21 May 2013 00:22:04 GMT
https://trac.sagemath.org/ticket/14532#comment:17
https://trac.sagemath.org/ticket/14532#comment:17
<p>
maybe Sage should have "polar space" graphs in general, not, only symplectic ones?
</p>
TicketNathann CohenTue, 21 May 2013 07:43:34 GMT
https://trac.sagemath.org/ticket/14532#comment:18
https://trac.sagemath.org/ticket/14532#comment:18
<p>
Helloooooooo !
</p>
<blockquote class="citation">
<p>
maybe Sage should have "polar space" graphs in general, not, only symplectic ones?
</p>
</blockquote>
<p>
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.
</p>
<p>
<a class="ext-link" href="http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html"><span class="icon"></span>http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html</a>
</p>
<p>
I believe I created what he calls a <code>VO^-</code> graph (<code>graphs.BrouwerHaemersGraph</code>), 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.
</p>
<p>
If you know how to make it work, I would be glad to see it in Sage too <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketDima PasechnikTue, 21 May 2013 08:15:49 GMT
https://trac.sagemath.org/ticket/14532#comment:19
https://trac.sagemath.org/ticket/14532#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14532#comment:18" title="Comment 18">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Helloooooooo !
</p>
<blockquote class="citation">
<p>
maybe Sage should have "polar space" graphs in general, not, only symplectic ones?
</p>
</blockquote>
<p>
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.
</p>
<p>
<a class="ext-link" href="http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html"><span class="icon"></span>http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html</a>
</p>
<p>
I believe I created what he calls a <code>VO^-</code> graph (<code>graphs.BrouwerHaemersGraph</code>), 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.
</p>
</blockquote>
<p>
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 <a class="ext-link" href="http://www.maths.qmul.ac.uk/~pjc/pps/pps6.pdf"><span class="icon"></span>http://www.maths.qmul.ac.uk/~pjc/pps/pps6.pdf</a>
</p>
<p>
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.
</p>
<pre class="wiki">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>
</pre><p>
etc...
</p>
TicketDima PasechnikTue, 21 May 2013 08:28:04 GMT
https://trac.sagemath.org/ticket/14532#comment:20
https://trac.sagemath.org/ticket/14532#comment:20
<p>
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.
</p>
TicketNathann CohenTue, 21 May 2013 08:31:49 GMT
https://trac.sagemath.org/ticket/14532#comment:21
https://trac.sagemath.org/ticket/14532#comment:21
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Ahahah. Well, why not ? But I really know next to nothing about those, and what people use them for <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketDima PasechnikTue, 21 May 2013 08:54:24 GMT
https://trac.sagemath.org/ticket/14532#comment:22
https://trac.sagemath.org/ticket/14532#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14532#comment:21" title="Comment 21">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Ahahah. Well, why not ? But I really know next to nothing about those, and what people use them for <code>:-)</code>
</p>
</blockquote>
<p>
it's useful to
</p>
<ul><li>store the graphs more compactly
</li><li>compute their properties faster
</li></ul><p>
Isn't it obvious? All these graphs you construct lately have huge automorphism groups, often arc-transitive and/or distance-transitive.
</p>
TicketNathann CohenTue, 21 May 2013 09:01:53 GMT
https://trac.sagemath.org/ticket/14532#comment:23
https://trac.sagemath.org/ticket/14532#comment:23
<blockquote class="citation">
<p>
Isn't it obvious?
</p>
</blockquote>
<p>
What do you use them for ? What do you want to compute ? Graphs have a lot of method, you know.. <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketNathann CohenTue, 21 May 2013 09:08:46 GMT
https://trac.sagemath.org/ticket/14532#comment:24
https://trac.sagemath.org/ticket/14532#comment:24
<p>
By the way, and because these graphs are usually immutable (and dense), I wrote a couple of C functions (<a class="closed ticket" href="https://trac.sagemath.org/ticket/14589" title="#14589: enhancement: binary matrices, dense graphs, and faster is_strongly_regular (closed: fixed)">#14589</a>) 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.
</p>
<p>
Nathann
</p>
TicketDima PasechnikTue, 21 May 2013 09:53:02 GMT
https://trac.sagemath.org/ticket/14532#comment:25
https://trac.sagemath.org/ticket/14532#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14532#comment:23" title="Comment 23">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Isn't it obvious?
</p>
</blockquote>
<p>
What do you use them for ? What do you want to compute ? Graphs have a lot of method, you know.. <code>:-P</code>
</p>
</blockquote>
<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...
</p>
TicketNathann CohenTue, 21 May 2013 10:21:57 GMT
https://trac.sagemath.org/ticket/14532#comment:26
https://trac.sagemath.org/ticket/14532#comment:26
<blockquote class="citation">
<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...
</p>
</blockquote>
<p>
Hmmm... Looks like you will have an awful amount of code to write <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketDima PasechnikTue, 21 May 2013 10:24:08 GMT
https://trac.sagemath.org/ticket/14532#comment:27
https://trac.sagemath.org/ticket/14532#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/14532#comment:26" title="Comment 26">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<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...
</p>
</blockquote>
<p>
Hmmm... Looks like you will have an awful amount of code to write <code>:-P</code>
</p>
</blockquote>
<p>
I wouldn't classify calls to GAP as "awful amount of code" :)
</p>
TicketNathann CohenTue, 21 May 2013 10:25:41 GMT
https://trac.sagemath.org/ticket/14532#comment:28
https://trac.sagemath.org/ticket/14532#comment:28
<p>
Oh ! Well, if it's all in there already, then.... <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketNathann CohenThu, 23 May 2013 08:45:21 GMT
https://trac.sagemath.org/ticket/14532#comment:29
https://trac.sagemath.org/ticket/14532#comment:29
<blockquote class="citation">
<p>
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!
</p>
</blockquote>
<p>
This is now <a class="closed ticket" href="https://trac.sagemath.org/ticket/14631" title="#14631: enhancement: Affine Polar Graphs (closed: fixed)">#14631</a> !
</p>
<p>
Nathann
</p>
Ticket