Opened 6 years ago
Closed 6 years ago
#18972 closed enhancement (fixed)
twographs and Seidel switching
Reported by: | dimpase | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.9 |
Component: | graph theory | Keywords: | |
Cc: | ncohen | Merged in: | |
Authors: | Dima Pasechnik | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | 1e8e0b4 (Commits, GitHub, GitLab) | Commit: | 1e8e0b4c3168ca179e20377ea6423b0c5385f0bb |
Dependencies: | #18960, #18948, #18988, #18991, #18986, #19018, #19019 | Stopgaps: |
Description
Implement twographs and Seidel switching to realise more entries in Brouwer database
Change History (141)
comment:1 follow-up: ↓ 2 Changed 6 years ago by
comment:2 in reply to: ↑ 1 ; follow-up: ↓ 3 Changed 6 years ago by
Replying to ncohen:
Hellooooooo,
1) The docstring must begin with a one-line sentence (http://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content)
2) small case (e.g.:
Graph.tutte_polynomial
)
why, why... Tutte won't complain from the grave, but, you know, to me this feels like dancing on his tombstone... And I actually happened to know Jaap Seidel; I was a postdoc in Eindhoven, and he (and Jack van Lint, whose name just popped up on your 2-weights code ticket) were still there...
3) If your methods only apply to undirected graphs, they should be in graph.py
ok, I will fix it.
4) Add doctests for your new constructor
5) This line is an insult to computer science:
idx = frozenset([self.vertices().index(v) for v in s])
It builds a listn
times to compute the index of an element with a linear search.
that's what you write as an 1:30am prototype, you know; thanks for pointing this out :-)
And I don't think that you need a
.Seydel_adjacency_matrix
or a new input type for this function.
Seidel adj.mat. has interesting spectral properties, and that's why it is there. (one gets srgs out of it if it has just 2 distinct eigenvalues; as well, it is a means to construct cospectral graphs, by switching---which is matrix conjugation, and this is why you preserve the spectrum...)
So it is very useful on its own right.
6) A new method must be added to the index at the top of the file.
OK; should there also be something done in src/doc ?
Dima
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 6 years ago by
why, why... Tutte won't complain from the grave, but, you know, to me this feels like dancing on his tombstone...
Well, I don't like much that all graphs constructors end with "Graph" but it's like a 'standard' problem. We either change them all, or none of them. And in the case of upper cases for family names, I expect that Sage has many occurrences of that.
Seidel adj.mat. has interesting spectral properties, and that's why it is there. (one gets srgs out of it if it has just 2 distinct eigenvalues; as well, it is a means to construct cospectral graphs, by switching---which is matrix conjugation, and this is why you preserve the spectrum...)
So it is very useful on its own right.
I personally don't see the added value with respect to the adjacency matrix. For sure it is not needed as far as the switching method is concerned.
OK; should there also be something done in src/doc ?
nonono, that's only needed when you create a new file.
Nathann
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 6 years ago by
Replying to ncohen:
why, why... Tutte won't complain from the grave, but, you know, to me this feels like dancing on his tombstone...
Well, I don't like much that all graphs constructors end with "Graph" but it's like a 'standard' problem. We either change them all, or none of them. And in the case of upper cases for family names, I expect that Sage has many occurrences of that.
I just posted a question on sage-devel: perhaps it's only me, and then I'll have to live with this :-)
Seidel adj.mat. has interesting spectral properties, and that's why it is there. (one gets srgs out of it if it has just 2 distinct eigenvalues; as well, it is a means to construct cospectral graphs, by switching---which is matrix conjugation, and this is why you preserve the spectrum...)
So it is very useful on its own right.
I personally don't see the added value with respect to the adjacency matrix. For sure it is not needed as far as the switching method is concerned.
In a similar vein you can say that Laplacian matrix should not be there, as it is a simple variation of the adjacency matrix, too...
It is there because we want to have readable code with readable documentation. It is syntactic sugar, if you wish. Of course you can say that all syntactic sugar is a waste of time and space, but without it you end up with obscure unreadable implementation...
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 6 years ago by
I just posted a question on sage-devel: perhaps it's only me, and then I'll have to live with this :-)
Good idea. I prefer it in small case, but I want it to be somehow consistent.
In a similar vein you can say that Laplacian matrix should not be there, as it is a simple variation of the adjacency matrix, too...
I would not say that, for there are books written about the laplacian matrix is .... well. More confidential.
It is there because we want to have readable code with readable documentation. It is syntactic sugar, if you wish.
The only guy who uses this expression is Nicolas Thierry. If you want me to believe you are just trying to trick me into acting the way you want it, there is no better way.
Of course you can say that all syntactic sugar is a waste of time and space, but without it you end up with obscure unreadable implementation..
Obscure? The 4 lines code?
Nathann
comment:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 6 years ago by
Replying to ncohen:
In a similar vein you can say that Laplacian matrix should not be there, as it is a simple variation of the adjacency matrix, too...
I would not say that, for there are books written about the laplacian matrix is .... well. More confidential.
There are many papers and book chapters written about Seidel adjacency matrix and Seidel switching.
And there are no books written graph6
, yet it is there in full glory.
It is there because we want to have readable code with readable documentation. It is syntactic sugar, if you wish.
The only guy who uses this expression is Nicolas Thierry.
I don't know what you are talking about: go read https://en.wikipedia.org/wiki/Syntactic_sugar Googling "syntactic sugar" gives you over 300,000 hits.
Anyhow, if you are not willing to allow Seidel_adjacency_matrix
into Sage graphs, I'd stop working on this implementation now.
comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 6 years ago by
There are many papers and book chapters written about Seidel adjacency matrix and Seidel switching.
I had never heard of it before today. Hard to miss the laplacian matrix, though.
I don't know what you are talking about: go read https://en.wikipedia.org/wiki/Syntactic_sugar Googling "syntactic sugar" gives you over 300,000 hits.
It was mostly a joke. I did not expect him to have invented the sentence.
Anyhow, if you are not willing to allow
Seidel_adjacency_matrix
into Sage graphs, I'd stop working on this implementation now.
Did you hear me say that I "would not allow it"? For sure I don't like it, but that did not stop me from accepting code that other thought useful. Also, you add long lines of code to an already very very heavy constructor, while you could turn it into an adjacency matrix with a one-liner.. But that would result in possibly misleading error messages.
What I said is that I do not see the added value and it is true. I said that the best way to write seydel_switching was to not use this new function. And also that it should be in small case unless a new standard is decided that applies to all of sage.
Nathann
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 6 years ago by
Replying to ncohen:
There are many papers and book chapters written about Seidel adjacency matrix and Seidel switching.
I had never heard of it before today.
Really? http://trac.sagemath.org/ticket/18785#comment:5 :-) And it is all over the place in the twograph business...
I don't know what you are talking about: go read https://en.wikipedia.org/wiki/Syntactic_sugar Googling "syntactic sugar" gives you over 300,000 hits.
It was mostly a joke. I did not expect him to have invented the sentence.
Anyhow, if you are not willing to allow
Seidel_adjacency_matrix
into Sage graphs, I'd stop working on this implementation now.Did you hear me say that I "would not allow it"? For sure I don't like it, but that did not stop me from accepting code that other thought useful. Also, you add long lines of code to an already very very heavy constructor, while you could turn it into an adjacency matrix with a one-liner.. But that would result in possibly misleading error messages.
OK, OK, I just was learning from your approach to ticket writing/abandoning ;-)
comment:9 in reply to: ↑ 8 Changed 6 years ago by
I had never heard of it before today.
Really? http://trac.sagemath.org/ticket/18785#comment:5 :-) And it is all over the place in the twograph business...
You have a talent for turning any conversation into a pointless word battle. But really, I don't think I heard of "Seydel adjacency matrix" before your ticket. And with good reason, it's almost equal to the adjacency matrix...
OK, OK, I just was learning from your approach to ticket writing/abandoning ;-)
If you feel a bit of responsibility for that, perhaps you could help me get these tikets through instead of letting this code rot because of unsufferable reviewers.
Nathann
comment:10 Changed 6 years ago by
- Commit changed from b76c9a0369a5babc98481d6b96125c9b86f1adc9 to a48e9e2c5ca13c44468a42a1420fac8b70ee9faa
Branch pushed to git repo; I updated commit sha1. New commits:
a48e9e2 | modifications suggested by Nathann in comment 1
|
comment:11 Changed 6 years ago by
- Commit changed from a48e9e2c5ca13c44468a42a1420fac8b70ee9faa to 46bdc550161b3fce56097c8c3f0bf101ea2c5c64
Branch pushed to git repo; I updated commit sha1. New commits:
46bdc55 | switching construction for the Chang graphs
|
comment:12 Changed 6 years ago by
- Commit changed from 46bdc550161b3fce56097c8c3f0bf101ea2c5c64 to e5144c17944ba15810fa6add30e1d9a996559607
Branch pushed to git repo; I updated commit sha1. New commits:
e5144c1 | initial version of twograph functionality
|
comment:13 Changed 6 years ago by
- Commit changed from e5144c17944ba15810fa6add30e1d9a996559607 to 21b01bcc384a0bef91b019dbe6914911a3aad5db
Branch pushed to git repo; I updated commit sha1. New commits:
21b01bc | no need for explicit .eps in LaTeX
|
comment:14 Changed 6 years ago by
- Commit changed from 21b01bcc384a0bef91b019dbe6914911a3aad5db to 0aafa88f085c4bd0962512831ef2fc39911a1f99
Branch pushed to git repo; I updated commit sha1. New commits:
0aafa88 | Merge branch 'u/dimpase/seidelsw' of git://trac.sagemath.org/sage into seidelsw
|
comment:15 Changed 6 years ago by
- Commit changed from 0aafa88f085c4bd0962512831ef2fc39911a1f99 to 3eeca75f420da293a72012fe54eddc28de1495fd
Branch pushed to git repo; I updated commit sha1. New commits:
3eeca75 | introducing class TwoGraph
|
comment:16 Changed 6 years ago by
- Commit changed from 3eeca75f420da293a72012fe54eddc28de1495fd to 7331311b78d59d5e932fd92af3a4cb4a3188a348
Branch pushed to git repo; I updated commit sha1. New commits:
7331311 | minor typos etc
|
comment:17 Changed 6 years ago by
- Dependencies set to #18960, #18948
we now can build not yet known to Sage graphs.strongly_regular_graph(279,150,85)
sage: A=graphs.strongly_regular_graph(280,135,70) sage: gTA=A.twograph().descendant(A.vertices()[0]) #long time sage: gTA.is_strongly_regular(parameters=True) (279, 150, 85, 75)
comment:18 Changed 6 years ago by
- Commit changed from 7331311b78d59d5e932fd92af3a4cb4a3188a348 to f72b84ea89a0f371a53a965620ca7820886f0f82
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
606d15f | trac #18960: Adding nonzero somewhere
|
83ed332 | trac #18960: Again...
|
dc2d326 | trac #18960: Lint -> vLint
|
3b0bd4f | Merge branch 'u/ncohen/18960' of git://trac.sagemath.org/sage into seidelsw
|
8f25493 | trac #18948: Merged with 6.9.beta0
|
a9280c9 | trac #18948: Rephrasing the doc
|
cf8f2da | trac #18948: guess mu
|
4f51703 | trac #18948: DOcstring
|
a75774f | trac #18948: take into account the BIBD from #18934
|
f72b84e | rebase...
|
comment:19 Changed 6 years ago by
TODO: constructing the descent graph directly from a graph should be much faster.
comment:20 Changed 6 years ago by
- Commit changed from f72b84ea89a0f371a53a965620ca7820886f0f82 to 5115728f80aa95f87a272feec999e317ccdffba4
Branch pushed to git repo; I updated commit sha1. New commits:
5115728 | make descendant computation faster
|
comment:21 Changed 6 years ago by
- Status changed from new to needs_review
- Type changed from defect to enhancement
Should we add individual graphs to the database here?
comment:22 Changed 6 years ago by
Well, unless you expect the code to be long/complicated, I'd say yes.
Nathann
comment:23 follow-up: ↓ 24 Changed 6 years ago by
I already made comments on the code of seidel_switching
, and you need to document what a twograph_descendant
is. I am not sure that this function should be in Graph
, though. If it is just a bit faster than using the TwoGraph
class, maybe it is enough to make it appear in a seealso
inside of twograph
and keep it in the two_graph
module.
But really, all in all, I don't see the point of creating a new module, a new class and 6 functions, if all it takes to build the descendant of a graph is 5 lines of code.
Nathann
comment:24 in reply to: ↑ 23 ; follow-ups: ↓ 25 ↓ 28 Changed 6 years ago by
Replying to ncohen:
I already made comments on the code of
seidel_switching
,
You said there that Graph.vertices() is a plain list, and I should make it a set, or something? (I guess a dictionary, as I need to know the original indices)
It's a usual operation, find positions of vertices... E.g. how do you construct subgraphs without essentially doing this?
and you need to document what a
twograph_descendant
is.
it's the composition of two documented functions, isn't it enough?
I am not sure that this function should be in
Graph
, though. If it is just a bit faster than using theTwoGraph
class, maybe it is enough to make it appear in aseealso
inside oftwograph
and keep it in thetwo_graph
module.
It is a hell of lot faster for cases with more than 100 vertices, say. O(n^2)
vs O(n^3)
.
But really, all in all, I don't see the point of creating a new module, a new class and 6 functions, if all it takes to build the descendant of a graph is 5 lines of code.
Did you see the patch for Chang graphs? Do you think it is useless and should be removed? (IMHO, Chang graphs should be constructed this way, not the way it's done at present).
comment:25 in reply to: ↑ 24 Changed 6 years ago by
Replying to dimpase: I'm also playing with constructing an srg of "2-graph" type from one of "2-graph\*"-type, via (integer) linear programming. One needs to find a -1/+1-diagonal matrix corresponding to the switching from "2-graph\*"+K1 to an srg of "2-graph" type. I can do toy cases so far...
comment:26 follow-up: ↓ 27 Changed 6 years ago by
- Commit changed from 5115728f80aa95f87a272feec999e317ccdffba4 to 758da33a4bd616f97e2b9748236c0d866fb8f79d
Branch pushed to git repo; I updated commit sha1. New commits:
758da33 | SRG_279_150_85_75 added.
|
comment:27 in reply to: ↑ 26 Changed 6 years ago by
comment:28 in reply to: ↑ 24 ; follow-up: ↓ 31 Changed 6 years ago by
Hello,
I already made comments on the code of
seidel_switching
,You said there that Graph.vertices() is a plain list, and I should make it a set, or something? (I guess a dictionary, as I need to know the original indices)
It's a usual operation, find positions of vertices... E.g. how do you construct subgraphs without essentially doing this?
I was refering to point 5 of 1. It contains code.
and you need to document what a
twograph_descendant
is.it's the composition of two documented functions, isn't it enough?
Neither twograph_descendant
nor TwoGraph.descendant
define what a descendant is.
It is a hell of lot faster for cases with more than 100 vertices, say.
O(n^2)
vsO(n^3)
.
We have very fast functions in modules, too. For hyperbolicity, for vertex separation, for.. Well, a lot of things. It can be made much faster, however, if you rewrite it to use seidel_switching
and rewrite seidel_switching
with the code of 1.
Did you see the patch for Chang graphs? Do you think it is useless and should be removed?
It is unrelated to my point: this is nice indeed, but it merely uses seidel_switching
, and that's it.
I don't know how to rebuild the database, so that it is available as
Look for (275, 112, 30, 56)
in strongly_regular_db.pyx
.
Nathann
comment:29 Changed 6 years ago by
- Commit changed from 758da33a4bd616f97e2b9748236c0d866fb8f79d to c4269aeae44bbd64afbdee96f04fb120d73f0de1
Branch pushed to git repo; I updated commit sha1. New commits:
c4269ae | doc and srg DB fixes
|
comment:30 Changed 6 years ago by
- Commit changed from c4269aeae44bbd64afbdee96f04fb120d73f0de1 to 449a23ec5b0305fc2f7132bdd38ba0923ec01b89
Branch pushed to git repo; I updated commit sha1. New commits:
449a23e | improving seidel_switching()
|
comment:31 in reply to: ↑ 28 Changed 6 years ago by
Replying to ncohen:
I already made comments on the code of
seidel_switching
,You said there that Graph.vertices() is a plain list, and I should make it a set, or something? (I guess a dictionary, as I need to know the original indices)
It's a usual operation, find positions of vertices... E.g. how do you construct subgraphs without essentially doing this?
I was refering to point 5 of 1. It contains code.
I changed seidel_switching()
in the way you propose. As the function returns a new
graph, I needed to use deepcopy(self)
(copy(self)
is not enough). Perhaps there is a better way...
and you need to document what a
twograph_descendant
is.it's the composition of two documented functions, isn't it enough?
Neither
twograph_descendant
norTwoGraph.descendant
define what a descendant is.
OK, oops, fixed in the next commit.
It is a hell of lot faster for cases with more than 100 vertices, say.
O(n^2)
vsO(n^3)
.We have very fast functions in modules, too. For hyperbolicity, for vertex separation, for.. Well, a lot of things. It can be made much faster, however, if you rewrite it to use
seidel_switching
and rewriteseidel_switching
with the code of 1.Did you see the patch for Chang graphs? Do you think it is useless and should be removed?
It is unrelated to my point: this is nice indeed, but it merely uses
seidel_switching
, and that's it.
OK, perhaps I misunderstood your point.
I don't know how to rebuild the database, so that it is available as
Look for
(275, 112, 30, 56)
instrongly_regular_db.pyx
.
OK, thx, fixed.
New commits:
c4269ae | doc and srg DB fixes
|
449a23e | improving seidel_switching()
|
comment:32 Changed 6 years ago by
- Commit changed from 449a23ec5b0305fc2f7132bdd38ba0923ec01b89 to a89a02a24b44fd0b2ce1c92ecce22b672bbd9e21
comment:33 Changed 6 years ago by
- Dependencies changed from #18960, #18948 to #18960, #18948, #18988
comment:34 Changed 6 years ago by
- Status changed from needs_review to needs_work
SRG_279_150_85_75
is an example of a general construction, obtaining a 2-graph\*
-srg from a 2-graph
-srg. I'll try to add this in strongly_regular_graph
DB.
Further on a followup ticket I'd like to have Taylor 2-graphs for U_3(q)
, and the corresponding 2-graph\*
-srg (note that in this case there is no 2-graph
srg, as far as I understand). They should come from yet to be written more general function, that will also produce U_d(q)
.
comment:35 follow-up: ↓ 36 Changed 6 years ago by
Is there a general way to *guess* how those 2-graph entries are produced? Couldn't we turn this construction into something automatic? Or will those 2-graph construction all have to be added manually to the list?
comment:36 in reply to: ↑ 35 Changed 6 years ago by
Replying to ncohen:
Is there a general way to *guess* how those 2-graph entries are produced? Couldn't we turn this construction into something automatic? Or will those 2-graph construction all have to be added manually to the list?
there is a general way to get 2-graph
(more precisely, regular two-graph) tags; it's a simple computation with parameters. It is all in 10.3 of BH12. I don't know how helpful this is, as it does not tell you how to actually construct the srg (or, equvalently, the underlying two-graph). As far as I can see you don't have any functionality that merely computes such tags.
comment:37 Changed 6 years ago by
- Commit changed from a89a02a24b44fd0b2ce1c92ecce22b672bbd9e21 to 12753b1062f1db1bcada48a3714176c6f45214cc
Branch pushed to git repo; I updated commit sha1. New commits:
12753b1 | merged
|
comment:38 Changed 6 years ago by
- Dependencies changed from #18960, #18948, #18988 to #18960, #18948, #18988, #18991
New commits:
12753b1 | merged
|
comment:39 Changed 6 years ago by
- Commit changed from 12753b1062f1db1bcada48a3714176c6f45214cc to 0a2dae4d4836e37f00bcc2af10dbb1b1d0313c88
Branch pushed to git repo; I updated commit sha1. New commits:
0a2dae4 | construct "2-graph\*" graphs from srg's corr. to 2-graphs
|
comment:40 Changed 6 years ago by
- Status changed from needs_work to needs_review
please have a look at the latest commit in particular.
comment:41 Changed 6 years ago by
You really need to start thinking of what exactly your code does. Plus it is python, not lisp.
return TwoGraph(filter(lambda x: not list(x) in self.blocks(), combinations(self.ground_set(), 3)))
comment:42 follow-up: ↓ 45 Changed 6 years ago by
or if 'something == True'
.
Your last commit sounds cool, though apparently it only adds two new SRG O_o
. Weird, I thought that it would add more O_o
Nathann
comment:43 Changed 6 years ago by
This is ridiculous
for kf in map(lambda s: (s*D+b)/4, [-1,1]):
You build a list, a lambda function, destroy the list, build another list, all this through a function call 'map'.
for kf in [(D+b)/4,(-D+b)/4]:
comment:44 Changed 6 years ago by
Seriously? from sage.misc.functional import is_even
Is it now wrong to write 'x%2==0' ?
Nathann
comment:45 in reply to: ↑ 42 ; follow-up: ↓ 46 Changed 6 years ago by
Replying to ncohen:,
or
if 'something == True'
.
it's only because this something
might return more than True
or False
;
namely, Unknown
.
(this is your design, not mine...:-)
Your last commit sounds cool, though apparently it only adds two new SRG
O_o
. Weird, I thought that it would add moreO_o
It added 4 on my branch, which might be behind yours. 294 vs 298. Actually one more, as I removed an explicit construction for an srg on 279, replacing it by this general function.
It will add more automatically, as we build more graphs on v+1 vertices which are tagged "2-graph".
comment:46 in reply to: ↑ 45 ; follow-up: ↓ 47 Changed 6 years ago by
it's only because this
something
might return more thanTrue
orFalse
; namely,Unknown
. (this is your design, not mine...:-)
Sorry, you cannot blame soembody else for that one. Remove True ==
, and it still works.
It will add more automatically, as we build more graphs on v+1 vertices which are tagged "2-graph".
Any clue how we can build those entries? There is a *LOT* of them :-/
Nathann
comment:47 in reply to: ↑ 46 ; follow-up: ↓ 48 Changed 6 years ago by
Replying to ncohen:
it's only because this
something
might return more thanTrue
orFalse
; namely,Unknown
. (this is your design, not mine...:-)Sorry, you cannot blame soembody else for that one. Remove
True ==
, and it still works.
This not a feature I would like to rely on. Using a non-boolean function as a boolean one smells of a hack.
It will add more automatically, as we build more graphs on v+1 vertices which are tagged "2-graph".
Any clue how we can build those entries? There is a *LOT* of them
:-/
for some of them an explicit construction is referred to, and then it's just a question of work. How many of these are so that "2-graph" is the only clue?
comment:48 in reply to: ↑ 47 Changed 6 years ago by
This not a feature I would like to rely on.
I would say the same about testing equality with True
:
sage: 1 == True True sage: 2 == True False
Regardless of that, and whether you like it or not removing True ==
does the job, and works as intended. It is also in the documentation of the 'Unknown' truth value, and is tested in so many places that it can be trusted to work.
for some of them an explicit construction is referred to, and then it's just a question of work. How many of these are so that "2-graph" is the only clue?
A lot. Run the _check_db
function and you will see how many exactly. For some of them it is not the only thing on the line but it is still the only entry with no '?' flag.
Nathann
comment:49 Changed 6 years ago by
- Status changed from needs_review to needs_work
The branch is in conflict with the latest beta.
comment:50 Changed 6 years ago by
- Commit changed from 0a2dae4d4836e37f00bcc2af10dbb1b1d0313c88 to 1b7f6b99019699fdccb4bb9afa86315defc87994
comment:51 Changed 6 years ago by
- Status changed from needs_work to needs_review
comment:52 follow-up: ↓ 53 Changed 6 years ago by
- Reviewers set to Nathann Cohen
- Status changed from needs_review to needs_work
Helloooooooooooooo,
Here is the review you requested:
TwoGraph
-- Probably should not be in the global namespace.
- Class documentation: there is none. Write one, and redirect toward the module's doc if necessary for the longer explanations.
is_regular
-- clashes with standard hypergraph terminology. Should be renamed (see #18986).
is_regular
-- parameters, role and definition not documented.
- Stop using map and filter. You do not know what it does, i.e. Python is not lisp. You are building in memory lists that you do not need, only to throw them away later. Use list-comprehension instead (also faster).
Graph([V, lambda i, j: frozenset((i,j)) in edges])
THINK ABOUT WHAT IT DOES. This is insulting.
complement
-- Rely on #18986.
- What the hell is this 'functions' in the middle of the file? Does it produce anything in the html doc?
#. A Sage Seidel adjacency matrix
-- link toward the doc of seidel adjacency matrix, in case people might want to read a definition.
M[i,j]=-1 indicating that (i,j) is an edge, otherwise M[i,j]=1.
missing backticks.
data = data.change_ring(ZZ)
-- you don't copy a matrix just because you expectInteger(1)
and getfloat(1)
. Test that the entries belong to a set you like instead.
- Repeated sentence
+ Returns the Seidel adjacency matrix of self. + + Returns the Seidel adjacency matrix of the graph.
- The sentence that follows the repeated sentence is not very clear. Use a list to define the objects, it should make it clearer.
change_ring
-- should be a sphinx link
- Stop using
\
at the end of lines. If you need to span an instruction over several lines, it is more readable to use()
, e.g.a = (1 + 2 + 3 )
seidel_switching
-- repeated sentence, as previously.
- Backticks are missing in the text again.
- Use
g.copy()
(which should be called bycopy(g)
), not deepcopy.
- Really, STOP using lambda functions. You don't know what it does, so stop
that.
+ return Graph([Nv+NonNv, lambda i, j: + (i in NonNv and j in NonNv and i in self.neighbors(j)) or + (i in Nv and j in Nv and i in self.neighbors(j)) or + (i in Nv and j in NonNv and not i in self.neighbors(j)) or + (j in Nv and i in NonNv and not i in self.neighbors(j))])
Build this graph by adding edges to it. It will be incomparably faster. Writing code like this should not be allowed.
is_two_graph_descendant_of_srg
-- could you remove those '0' everywhere in the variables?
is_even
.
Nathann
comment:53 in reply to: ↑ 52 ; follow-up: ↓ 54 Changed 6 years ago by
Replying to ncohen:
Here is the review you requested:
Thanks!
TwoGraph
-- Probably should not be in the global namespace.
- Class documentation: there is none. Write one, and redirect toward the module's doc if necessary for the longer explanations.
is_regular
-- clashes with standard hypergraph terminology. Should be renamed (see #18986).
is_regular
-- parameters, role and definition not documented.
OK, sure.
- Stop using map and filter. You do not know what it does, i.e. Python is not lisp. You are building in memory lists that you do not need, only to throw them away later. Use list-comprehension instead (also faster).
this is an urban myth that the latter is much faster:
sage: ll=range(50000) sage: timeit('[x for x in ll if x%2==0]') 25 loops, best of 3: 19.8 ms per loop sage: timeit('filter(lambda x: x%2==0, ll)') 25 loops, best of 3: 22.2 ms per loop sage: timeit('[x**2 for x in ll]') 25 loops, best of 3: 19.7 ms per loop sage: timeit('map(lambda x: x**2, ll)') 25 loops, best of 3: 23.7 ms per loop
besides, I do find the list comprehension syntax ugly and error-prone. All these
for ah if that or what not
is very hard to parse for me. Yes, I wrote a bit of lisp code in my previous life, and my brain is damaged by parentheses. :-)
Graph([V, lambda i, j: frozenset((i,j)) in edges])
THINK ABOUT WHAT IT DOES. This is insulting.
Indeed, I wish I could write Graph(V,edges)
or Graph([V,edges])
or even Graph(edges)
instead. Why can't I? Why must I instead do something like
blah=Graph(V); blah.add_edges(edges); return blah
? Cause the GC is hungry and must be fed blah
on each return?
complement
-- Rely on #18986.
- What the hell is this 'functions' in the middle of the file? Does it produce anything in the html doc?
#. A Sage Seidel adjacency matrix
-- link toward the doc of seidel adjacency matrix, in case people might want to read a definition.
M[i,j]=-1 indicating that (i,j) is an edge, otherwise M[i,j]=1.
missing backticks.
data = data.change_ring(ZZ)
-- you don't copy a matrix just because you expectInteger(1)
and getfloat(1)
. Test that the entries belong to a set you like instead.
I copied this one from the elif format == 'adjacency_matrix':
block. Should one fix both places?
- Repeated sentence
+ Returns the Seidel adjacency matrix of self. + + Returns the Seidel adjacency matrix of the graph.
- The sentence that follows the repeated sentence is not very clear. Use a list to define the objects, it should make it clearer.
change_ring
-- should be a sphinx link
OK, will do.
- Stop using
\
at the end of lines. If you need to span an instruction over several lines, it is more readable to use()
,
not to me, sorry. I tend to (mis)read a=(1+2)
as a=(1+2,)
.
e.g.
a = (1 + 2 + 3 )
seidel_switching
-- repeated sentence, as previously.
- Backticks are missing in the text again.
- Use
g.copy()
(which should be called bycopy(g)
), not deepcopy.
the docs to g.copy()
say something like "use only if you change the backend..."
Warning: Please use this method only if you need to copy but change the underlying implementation or weightedness. Otherwise simply do "copy(g)" instead of "g.copy()".
Should I ignore this? Should the docs be improved?
- Really, STOP using lambda functions. You don't know what it does, so stop that.
This is a myth that they are slow, see above.
+ return Graph([Nv+NonNv, lambda i, j: + (i in NonNv and j in NonNv and i in self.neighbors(j)) or + (i in Nv and j in Nv and i in self.neighbors(j)) or + (i in Nv and j in NonNv and not i in self.neighbors(j)) or + (j in Nv and i in NonNv and not i in self.neighbors(j))])Build this graph by adding edges to it. It will be incomparably faster. Writing code like this should not be allowed.
in my book using temporary variables is slow; perhaps Python implementations will get fuller use of this fact as its devs and users get wiser...
is_two_graph_descendant_of_srg
-- could you remove those '0' everywhere in the variables?
well, I have v and v0, l and l0 - they are sets of parameters of different graphs... Or I had, and then optimised v, l, mu away, sorry. I'll see what I can do.
is_even
.
I like it better than %
, more readable: one does not need to swap out some other language in the head to recall the meaning. But if you insist...
comment:54 in reply to: ↑ 53 ; follow-up: ↓ 55 Changed 6 years ago by
- Stop using map and filter. You do not know what it does, i.e. Python is not lisp. You are building in memory lists that you do not need, only to throw them away later. Use list-comprehension instead (also faster).
this is an urban myth that the latter is much faster:
I said 'faster', not 'much faster', and this is what your timing proves. It also eats less memory. I also suspect that the resulting Cython code is much better (and so that the timings could differ in that case).
besides, I do find the list comprehension syntax ugly and error-prone.
It is much shorter and easier to read. Get used to it.
Graph([V, lambda i, j: frozenset((i,j)) in edges])
THINK ABOUT WHAT IT DOES. This is insulting.Indeed, I wish I could write
Graph(V,edges)
orGraph([V,edges])
or evenGraph(edges)
instead. Why can't I?
There is no God above forbidding this syntax. If the constructor does not do what you want, then improve it.
In this situation, Graph(edges)
simply works.
Why must I instead do something like
blah=Graph(V); blah.add_edges(edges); return blah
? Cause the GC is hungry and must be fedblah
on each return?
What your code does is this:
"For every pair of points among V, build a frozen set {i,j} then test if this set is contained in a LIST (linear time) of sets". That's ridiculous.
I copied this one from the
elif format == 'adjacency_matrix':
block. Should one fix both places?
Lazy code.... Yeah yeah, please -_-
- Use
g.copy()
(which should be called bycopy(g)
), not deepcopy.the docs to
g.copy()
say something like "use only if you change the backend..."Warning: Please use this method only if you need to copy but change the underlying implementation or weightedness. Otherwise simply do "copy(g)" instead of "g.copy()".Should I ignore this? Should the docs be improved?
All that it says is that "g.copy()" is equivalent to "copy(g)", and that the latter should be preferred. The advantage of g.copy()
is that you can give it additional arguments, e.g. change the backend.
I'd say that we can do without this warning, though.. To me it enforces a personal taste, not something we should ask users (or even developers) to follow. Makes no difference in what gets run.
- Really, STOP using lambda functions. You don't know what it does, so stop that.
This is a myth that they are slow, see above.
I am not saying that it is slow to use lambda function, I say that you have no idea of what you are doing.
+ return Graph([Nv+NonNv, lambda i, j: + (i in NonNv and j in NonNv and i in self.neighbors(j)) or + (i in Nv and j in Nv and i in self.neighbors(j)) or + (i in Nv and j in NonNv and not i in self.neighbors(j)) or + (j in Nv and i in NonNv and not i in self.neighbors(j))])Build this graph by adding edges to it. It will be incomparably faster. Writing code like this should not be allowed.
in my book using temporary variables is slow; perhaps Python implementations will get fuller use of this fact as its devs and users get wiser...
This code call .neighbors()
for around Theta(n^2)
times. Each time it builds a list in memory, and does a linear search in a list of things which may not even be integers. That's madness. THIS IS NOT SYMBOLICS. THIS IS ACTUAL CODE. For every pair of i,j this function is run, and every time all these lists are creates for nothing.
is_even
.I like it better than
%
, more readable: one does not need to swap out some other language in the head to recall the meaning. But if you insist...
Are you telling me that you are having a hard time remembering the meaning of %
? Is that a joke?
Besides, how many CPU instructions do you think it takes to compute a %2
on a C int variable? Now, what happens when you load a function, turn the int into a Python object, compute '%2', then return the result?
Nathann
comment:55 in reply to: ↑ 54 ; follow-up: ↓ 56 Changed 6 years ago by
Replying to ncohen:
Graph([V, lambda i, j: frozenset((i,j)) in edges])
THINK ABOUT WHAT IT DOES. This is insulting.Indeed, I wish I could write
Graph(V,edges)
orGraph([V,edges])
or evenGraph(edges)
instead. Why can't I?There is no God above forbidding this syntax. If the constructor does not do what you want, then improve it.
In this situation,
Graph(edges)
simply works.
Really? This is not documented! No wonder I didn't try this.
Why must I instead do something like
blah=Graph(V); blah.add_edges(edges); return blah
? Cause the GC is hungry and must be fedblah
on each return?What your code does is this:
"For every pair of points among V, build a frozen set {i,j} then test if this set is contained in a LIST (linear time) of sets". That's ridiculous.
I just wanted one function call, you know...
- Use
g.copy()
(which should be called bycopy(g)
), not deepcopy.the docs to
g.copy()
say something like "use only if you change the backend..."Warning: Please use this method only if you need to copy but change the underlying implementation or weightedness. Otherwise simply do "copy(g)" instead of "g.copy()".Should I ignore this? Should the docs be improved?
All that it says is that "g.copy()" is equivalent to "copy(g)", and that the latter should be preferred. The advantage of
g.copy()
is that you can give it additional arguments, e.g. change the backend.
If g.copy()==copy(g)
then it would not work. I tried using copy(g)
in place of deepcopy(g)
and it produced crap. A bug in Graph
? I don't know...
I am not saying that it is slow to use lambda function, I say that you have no idea of what you are doing.
+ return Graph([Nv+NonNv, lambda i, j: + (i in NonNv and j in NonNv and i in self.neighbors(j)) or + (i in Nv and j in Nv and i in self.neighbors(j)) or + (i in Nv and j in NonNv and not i in self.neighbors(j)) or + (j in Nv and i in NonNv and not i in self.neighbors(j))])Build this graph by adding edges to it. It will be incomparably faster. Writing code like this should not be allowed.
in my book using temporary variables is slow; perhaps Python implementations will get fuller use of this fact as its devs and users get wiser...
This code call
.neighbors()
for aroundTheta(n^2)
times. Each time it builds a list in memory, and does a linear search in a list of things which may not even be integers. That's madness. THIS IS NOT SYMBOLICS. THIS IS ACTUAL CODE. For every pair of i,j this function is run, and every time all these lists are creates for nothing.
I don't get it. Somewhere deep inside Graph
there must be a fast way to check if two vertices are adjacent... I took it as self.neighbour(j)
is actually something that takes constant time to invoke. If not, pray tell me how to check that two vertices are adjacent in a reasonably fast way.
is_even
.I like it better than
%
, more readable: one does not need to swap out some other language in the head to recall the meaning. But if you insist...e Are you telling me that you are having a hard time remembering the meaning of
%
? Is that a joke?
No, not at all. I have been programming for over 35 years, you know... Yes, I do need nonzero time to recall the meaning of %
, of //
, etc etc, if I don't touch them for a week...
comment:56 in reply to: ↑ 55 Changed 6 years ago by
I don't get it. Somewhere deep inside
Graph
there must be a fast way to check if two vertices are adjacent...
Graph.has_edge
.
I took it as
self.neighbour(j)
is actually something that takes constant time to invoke.
It returns a list.
If not, pray tell me how to check that two vertices are adjacent in a reasonably fast way.
The right way to write this code is NOT to test for adjacency. Use seidel_switching
, it takes a couple of lines at most.
Nathann
comment:57 Changed 6 years ago by
- Dependencies changed from #18960, #18948, #18988, #18991 to #18960, #18948, #18988, #18991, #18986
comment:58 Changed 6 years ago by
- Commit changed from 1b7f6b99019699fdccb4bb9afa86315defc87994 to 8406d0c80314601988109034ff5fdd891d29ed47
Branch pushed to git repo; I updated commit sha1. New commits:
ab39583 | copy works now... perhaps a bug was elsewhere
|
55f934b | trac #18986: IncidenceStructure.is_uniform, is_regular, and complement
|
0bd9d95 | Merge branch 'u/ncohen/18986' of git://trac.sagemath.org/sage into seidelsw
|
7e0d333 | using complement from #18986
|
10f9df8 | a saner implementation of descendant
|
8406d0c | regularising is_regular...
|
comment:59 Changed 6 years ago by
- Commit changed from 8406d0c80314601988109034ff5fdd891d29ed47 to 86bf5b8fa763ef06ada8e1993a3c75726575b767
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
cb071e2 | trac #19019: Missing space
|
19b40d9 | trac #19019: Sort the list of SRGs
|
778556f | Merge remote-tracking branch 'trac/u/ncohen/19019' into t19019
|
6ed716d | added a doctest
|
cb0b3fb | Merge branch 'reg_symm_hadamard' into t19019
|
2c4a38a | Merge branch '#19019' into seidelsw
|
8601814 | removed duplicate [BH12]
|
6ba4533 | docs for two-graphs class
|
afbf2cb | docs changes; hyperlinks etc
|
86bf5b8 | remove twographs.* from global namespace, added to design_catalog
|
comment:60 Changed 6 years ago by
- Dependencies changed from #18960, #18948, #18988, #18991, #18986 to #18960, #18948, #18988, #18991, #18986, #19018, #19019
- Status changed from needs_work to needs_review
merged with #19019. I have addressed the issues from comment 53, etc.
comment:61 follow-up: ↓ 63 Changed 6 years ago by
You have not fixed the code of twograph_descendant
, whose documentation also contains broken links.
I also find this function to be *very* specific, and I do not think that it should belong to the Graph class. What about moving it to this twograph module that you create?
Nathann
comment:62 Changed 6 years ago by
- Commit changed from 86bf5b8fa763ef06ada8e1993a3c75726575b767 to 2fae2fc7b92d306f1336b6786c67318823f812f4
Branch pushed to git repo; I updated commit sha1. New commits:
2fae2fc | fixed docs for twograph_descendant, adjusted the Graph methods indices
|
comment:63 in reply to: ↑ 61 ; follow-up: ↓ 64 Changed 6 years ago by
Replying to ncohen:
You have not fixed the code of
twograph_descendant
, whose documentation also contains broken links.
done; I also shifted it and the rest of the methods on this ticket to the Leftovers index.
I also find this function to be *very* specific, and I do not think that it should belong to the Graph class. What about moving it to this twograph module that you create?
It is not even a function. It is a method of Graph, and it produces a Graph. There are things in Graph that I also find very specific, yet they belong there by right.
comment:64 in reply to: ↑ 63 ; follow-up: ↓ 65 Changed 6 years ago by
done; I also shifted it and the rest of the methods on this ticket to the Leftovers index.
I see no difference in the code of twograph_descendent
It is not even a function. It is a method of Graph, and it produces a Graph. There are things in Graph that I also find very specific, yet they belong there by right.
I would agree with you if we had fewer methods, but we have a *LOT* of them already. It is true that it takes a graph as input and returns a graph, but it could be advertised properly if it were in the trograph module, and if we added a "SEEALSO" in the documentation of Graph.twograph
. I want it to be found by whoever needs it, but I also know that everything cannot belong to the graph module. Right now you can see David and Michele working on a new hyperbolicity algorithm (#19049) and you wil see that there are *MANY* lines of code in this module which took a lot of effort. Yet even that is not a Graph method (perhaps it should be). And you do not see Graph.pathwidth
nor Graph.grundy_coloring
nor Graph.vertex_separation
, and all of them took a *LOT* of code and effort.
I don't want to hide what you do, I want to organise this smartly. Some things are much less useful than others, and your function is an *optimization* of something that is already available via the twograph object. Would you agree to let it stay in the twograph module? Whoever wants to get the twograph_descendant
of a graph wil definitely look at twograph
. (S)He will then look at the descendant
method, which can *also* link toward your optimization. This thing has its place in the twograph class and will be found there, but having the optimization directly in the Graph
class does not add a new feature by itself, and can really be sufficiently advertised through the TwoGraph
method.
Please, think with me. I'm tired of this endless arguing.
Nathann
comment:65 in reply to: ↑ 64 ; follow-up: ↓ 66 Changed 6 years ago by
Replying to ncohen:
done; I also shifted it and the rest of the methods on this ticket to the Leftovers index.
I see no difference in the code of
twograph_descendent
Well, I am using 'has_edge' there now, which you say is fast. So the bottleneck of creating neighbour lists is gone, no?
It is not even a function. It is a method of Graph, and it produces a Graph. There are things in Graph that I also find very specific, yet they belong there by right.
I would agree with you if we had fewer methods, but we have a *LOT* of them already.
Mind you, you said in comment 1 above that I should move these things to graph.py. And it's not much code being added, compared to complicated algorithms not in Graph that you mention. Anyway, we should open another ticket to reorganise the Graph module. I agree that Graph has a lot of methods, and they should be better organised.
comment:66 in reply to: ↑ 65 ; follow-up: ↓ 67 Changed 6 years ago by
Well, I am using 'has_edge' there now, which you say is fast. So the bottleneck of creating neighbour lists is gone, no?
No, it is not gone. There is a huge loss of time in this function because you want to build it from a lambda function.
Mind you, you said in comment 1 above that I should move these things to graph.py.
What I meant is that DiGraph.twograph()
should not exist. Surely you agree with that?
And it's not much code being added, compared to complicated algorithms not in Graph that you mention. Anyway, we should open another ticket to reorganise the Graph module. I agree that Graph has a lot of methods, and they should be better organised.
Could we please keep it out for the moment? It is not for the code that I advocate this, it is merely for the length of the list of functions that appears to the user.
I don't mind improvng the twograph_descendant
myself if that can ease the deal.
Nathann
comment:67 in reply to: ↑ 66 ; follow-up: ↓ 69 Changed 6 years ago by
Replying to ncohen:
Well, I am using 'has_edge' there now, which you say is fast. So the bottleneck of creating neighbour lists is gone, no?
No, it is not gone. There is a huge loss of time in this function because you want to build it from a lambda function.
We already discussed here a similar issue and found that we talk about 5-10% loss (which can hardly be called huge) no?
Perhaps making Nv
and NoNv
(frozen)sets will be an extra optimisation that I am willing to add, but other than that it's matter of taste, IMHO...
Mind you, you said in comment 1 above that I should move these things to graph.py.
What I meant is that
DiGraph.twograph()
should not exist. Surely you agree with that?
Look, I read what you wrote, and you wrote the following:
3) If your methods only apply to undirected graphs, they should be in graph.py
And I duly put the stuff into graph.py.
And it's not much code being added, compared to complicated algorithms not in Graph that you mention. Anyway, we should open another ticket to reorganise the Graph module. I agree that Graph has a lot of methods, and they should be better organised.
Could we please keep it out for the moment? It is not for the code that I advocate this, it is merely for the length of the list of functions that appears to the user.
No, why should we keep this out now? I hope you don't like the role of the code bouncer you play now... The methods need to be cathegorised better, that's all. Dumping too much stuff directly into g.TAB (for g a Graph) is bound to cause a problem sooner or later.
Presently I find it absurd that we have e.g. kirchhoff_symanzik_polynomial
but we cannot have twograph_descendant
. Certainly there should be g.polynomial.TAB,
g.graph.TAB, g.decomposition.TAB, g.matrix.TAB etc etc.
I don't mind improvng the
twograph_descendant
myself if that can ease the deal.
Sure, please.
comment:68 Changed 6 years ago by
- Commit changed from 2fae2fc7b92d306f1336b6786c67318823f812f4 to 799a2bf3bea99309b02eb11cc5438e428135be0c
Branch pushed to git repo; I updated commit sha1. New commits:
799a2bf | speeding up twograph_descendant
|
comment:69 in reply to: ↑ 67 ; follow-up: ↓ 70 Changed 6 years ago by
No, why should we keep this out now?
Because it is highly specialised and already available by another means, i.e. by G.twograph().descendant(). Having an optimized alias is not necessary, and not a sensible thing to add given the amount of functions already available in that class.
Sure, please.
If you accept the 'deal' about this unnecessary function, I will. You will see that the speedup will not be 5%.
Nathan
comment:70 in reply to: ↑ 69 ; follow-up: ↓ 71 Changed 6 years ago by
Replying to ncohen:
No, why should we keep this out now?
Because it is highly specialised and already available by another means, i.e. by G.twograph().descendant(). Having an optimized alias is not necessary, and not a sensible thing to add given the amount of functions already available in that class.
OK, this is a good argument. Perhaps it's better to move it to strongly_regular_db, where it is used, than to twographs?
Sure, please.
If you accept the 'deal' about this unnecessary function, I will. You will see that the speedup will not be 5%.
IMHO there are more important things than speeding this function up, but do as you like.
comment:71 in reply to: ↑ 70 ; follow-up: ↓ 73 Changed 6 years ago by
OK, this is a good argument. Perhaps it's better to move it to strongly_regular_db, where it is used, than to twographs?
That's up to you. I believe that it makes more sense to define it in the twograph module, cause that's where I would personally look for anything related to twographs. Plus this descendant, unless I make a mistake, is not directly linked to SRGs. But well, that's up to you: move it where you prefer.
IMHO there are more important things than speeding this function up, but do as you like.
I will update that code, it takes two lines at most. I only wish Volker would release another beta, for it is hard to see what is added by that branch and what belongs to its dependencies.
Nathann
comment:72 Changed 6 years ago by
- Commit changed from 799a2bf3bea99309b02eb11cc5438e428135be0c to 68c0edd21e25d74df2bf41e060e9e55c99ca2fca
comment:73 in reply to: ↑ 71 Changed 6 years ago by
Replying to ncohen:
OK, this is a good argument. Perhaps it's better to move it to strongly_regular_db, where it is used, than to twographs?
That's up to you. I believe that it makes more sense to define it in the twograph module, cause that's where I would personally look for anything related to twographs. Plus this descendant, unless I make a mistake, is not directly linked to SRGs. But well, that's up to you: move it where you prefer.
IMHO there are more important things than speeding this function up, but do as you like.
I will update that code, it takes two lines at most. I only wish Volker would release another beta, for it is hard to see what is added by that branch and what belongs to its dependencies.
OK, it's moved and docs updated. You can study diff with trac/public/19019 branch to see the changes on this ticket.
comment:74 follow-ups: ↓ 75 ↓ 77 Changed 6 years ago by
- Status changed from needs_review to needs_work
Helloooo Dima,
Here is a first-pass review:
- Where exactly is the 'twograph' module to be found in the documentation? It does not belong to the main 'design' page.
is_regular_twograph
-- the first sentence of the docstring must be short (one line) and describe what the function does.
- doc of
descendant
: a sentence starts with an upper-case letter. Same withcomplement()
,twograph_descendant()
``self.ground_set()``
-- should be a link.
is_twograph
-- you should rephrase the first sentence of the doc. An INPUT block is missing.
- Construction of chang graphs by switching: define K8 and T8 in the block that does that, not in the previous doc which does not use them.
:meth:`sage.matrix.change_ring`
-- broken link (appears twice)
seidel_matrix
INPUT for Graph: you must add doctests to test that it works, and to test your exceptions.
is_two_graph_descendant_of_srg
- what about thosev0,k0,l0,mu0
we already mentionned?v,k,l,mu
would be easier to read.
Nathann
comment:75 in reply to: ↑ 74 ; follow-up: ↓ 76 Changed 6 years ago by
Replying to ncohen:
Helloooo Dima,
Here is a first-pass review:
Thanks!
- Where exactly is the 'twograph' module to be found in the documentation?
it can be found in "comprehensive module index" of Combinatorics
It does not belong to the main 'design' page.
should it? Do you know where the corresponding index is located?
By the way, Hadamard matrices are in the same situation: they can be found in "comprehensive module index" of Combinatorics, but not elsewhere.
comment:76 in reply to: ↑ 75 Changed 6 years ago by
should it? Do you know where the corresponding index is located?
Yeah yeah they should. The index of combinatorial designs can be found in the __init__.py
file of the design/
folder.
By the way, Hadamard matrices are in the same situation: they can be found in "comprehensive module index" of Combinatorics, but not elsewhere.
That's because Nicolas decided that the documentation of "combinat/" had to be handled in a different way from everything else in the doc. To me we should revert it to something that makes sense, and change everything or nothing at all. But I'm tired of fighting alone against people who protect their friends. Too much bullshit these days.
http://doc.sagemath.org/html/en/developer/sage_manuals.html#adding-a-new-file
Nathann
comment:77 in reply to: ↑ 74 Changed 6 years ago by
Replying to ncohen:
- Construction of chang graphs by switching: define K8 and T8 in the block that does that, not in the previous doc which does not use them.
the previous block does use them after my change, so I don't understand this comment.
comment:78 Changed 6 years ago by
Right.
comment:79 follow-up: ↓ 80 Changed 6 years ago by
- Commit changed from 68c0edd21e25d74df2bf41e060e9e55c99ca2fca to 6bc5cbd678d6d9db6e99ff23489e0e1a720e8569
Branch pushed to git repo; I updated commit sha1. New commits:
6bc5cbd | next round of fixes, cf #18972:75
|
comment:80 in reply to: ↑ 79 Changed 6 years ago by
comment:81 follow-ups: ↓ 82 ↓ 88 Changed 6 years ago by
Helloooooooo Dima,
Here is another review. I also fixed a couple of things in a commit at public/18972
.
- About
designs.is_twograph
-- this has nothing to do in the design catalog.
- About
designs.TwoGraph
-- I believe that it is the same: a class constructor does not have anything to do in the design catalog. You don't findPermutationGroup
ingroups.<tab>
, and neither do you findGraph
ingraphs.<tab>
. Note that there is an 'exception' in this case, i.e.BlockDesign
, which (I believe) should also be removed, and for the same reasons.
- The first letter of the docstrings should be in upper case. I told you that already.
- There are still broken links. If you can't be bothered to read the doc, at
least compile it with
--warn-links
.
- No need of indentation after a 'INPUT' block.
- Backticks are required around
True/False
.
- option
check
ofis_regular
-- checking that the input is indeed a twograph should be done inTwoGraph.__init__
.
- Instead of
Return True if [...]
, it would be better to have `Test whether [...]. Formally, a function that *always* returns
True` satisfies your description (I know, that's a stupid thing to say. Still).
complement
-- the default meaning of.complement()
is different onIncidenceStructure
and onTwoGraph
. Could you conform to the most general specification?
T.is_t_design(k=3)
-- useis_uniform
.
- It feels a bit weird that the default behaviour of
seidel_switching
is not to modify the graph inplace but to return a copy... I would have expected ainplace=False
argument for that.
- Documentation of
seidel_switching
: some mathematical notations need backticks.
- Same function: the OUTPUT section is hardly necessary, given the first two lines of doc.
twograph
-- I am tired of reminding you to write doctests.
- Code of
twograph
-- please rewrite the code of this function decently.
is_two_graph_descendant_of_srg
-- you seem to have prefered 'twograph' everywhere else.
- Please build and read the doc of that function. Also,
lambda
should be\lambda
.
Nathann
comment:82 in reply to: ↑ 81 ; follow-up: ↓ 83 Changed 6 years ago by
Replying to ncohen:
Here is another review. I also fixed a couple of things in a commit at
public/18972
.
Thanks! Here are few clarifications/comments/questions:
- The first letter of the docstrings should be in upper case. I told you that already.
oops, sorry, I misunderstood your comment about this, and was making things lower case...
- There are still broken links. If you can't be bothered to read the doc, at least compile it with
--warn-links
.
I normally build docs with make. Does it mean I better do an explicit -docbuild
?
complement
-- the default meaning of.complement()
is different onIncidenceStructure
and onTwoGraph
. Could you conform to the most general specification?
no, for two-graphs it's the way it is. Should I rename this .complement()
as
twograph_complement()
?
- It feels a bit weird that the default behaviour of
seidel_switching
is not to modify the graph inplace but to return a copy... I would have expected ainplace=False
argument for that.
well, I don't like inplace things. I don't even have an inplace option for this function. I hope it's OK.
I'm going to fix the rest and add a construction of two-graphs (more precisely, certain Seidel adj.matrices, from which the two-graph can be constructed, if needed) from doubly-transitive permutation groups, i.e. Taylor two-graphs.
comment:83 in reply to: ↑ 82 ; follow-up: ↓ 84 Changed 6 years ago by
- There are still broken links. If you can't be bothered to read the doc, at least compile it with
--warn-links
.I normally build docs with make. Does it mean I better do an explicit
-docbuild
?
With make? It must take a lot of time! I compile the doc with sage -b && sage -docbuild reference/combinat html
. You can add a --warn-links
flag to it to get a report of broken links.
no, for two-graphs it's the way it is. Should I rename this
.complement()
astwograph_complement()
?
HMmmmmm :-/
It is true that the "right" notion of "complement" really depends on what you do when it comes to hypergraphs. I made the other one the default because it applies to all hypergraphs, and not only to uniform ones.
I thought for a while of your proposition to make it a new method
, but then why don't you just use .complement(uniform=True)
? If you are ready to leave .complement
as it is and to create a new function, then do you really need that function?
well, I don't like inplace things. I don't even have an inplace option for this function. I hope it's OK.
It's surprising, at least for me. Would you object if I added a commit that makes it an inplace function, with an optional inplace=False
to get a copy?
I'm going to fix the rest and add a construction of two-graphs (more precisely, certain Seidel adj.matrices, from which the two-graph can be constructed, if needed) from doubly-transitive permutation groups, i.e. Taylor two-graphs.
Nice. Could you please do that in another ticket, please? This one is already dozens of commits long.
Nathann
comment:84 in reply to: ↑ 83 ; follow-ups: ↓ 85 ↓ 86 Changed 6 years ago by
Replying to ncohen:
no, for two-graphs it's the way it is. Should I rename this
.complement()
astwograph_complement()
?HMmmmmm
:-/
It is true that the "right" notion of "complement" really depends on what you do when it comes to hypergraphs. I made the other one the default because it applies to all hypergraphs, and not only to uniform ones.
I thought for a while of your proposition to make it a
new method
, but then why don't you just use.complement(uniform=True)
? If you are ready to leave.complement
as it is and to create a new function, then do you really need that function?
Well, the rationale behind the current code is that someone who wants to take the complement of a two-graph should just call .complement()
rather than something more complicated. And indeed, the complement of a two-graph has a well-established meaning. It's more an implementation artefact that the base class already has complement()
defined, and it's not quite the same. The user should not care about this IMHO.
Same was with is_regular()
, but you didn't like this as it clashed with the default, and I made it is_regular_twograph()
.
It looks rather incoherent now; I'd personally prefer to revert to my old is_regular()
, and keep the current complement()
.
well, I don't like inplace things. I don't even have an inplace option for this function. I hope it's OK.
It's surprising, at least for me. Would you object if I added a commit that makes it an inplace function, with an optional
inplace=False
to get a copy?
no problem, go ahead with this.
I'm going to fix the rest and add a construction of two-graphs (more precisely, certain Seidel adj.matrices, from which the two-graph can be constructed, if needed) from doubly-transitive permutation groups, i.e. Taylor two-graphs.
Nice. Could you please do that in another ticket, please? This one is already dozens of commits long.
OK, on another ticket then, no problem.
comment:85 in reply to: ↑ 84 ; follow-up: ↓ 87 Changed 6 years ago by
Well, the rationale behind the current code is that someone who wants to take the complement of a two-graph should just call
.complement()
rather than something more complicated. And indeed, the complement of a two-graph has a well-established meaning. It's more an implementation artefact that the base class already hascomplement()
defined, and it's not quite the same. The user should not care about this IMHO.
I agree with everything you just said, but there is this other definition above that is inherited, and we can't really change that definition either for it would only apply to uniform hypergraphs...
I see only one way out: what would you think of making the *default* of .complement()
to only work for uniform hypergraphs? If we do that, then the problem is solved in a more elegant way. Though complement
would not work for all instances but then, perhaps *that* is less surprising. And we can make the exception "smart" to indicate that a keyword can change this behaviour.
Same was with
is_regular()
, but you didn't like this as it clashed with the default, and I made itis_regular_twograph()
.
I take this a bit differently: surely there is such a thing as a "regular two-graph", but you can't work on hypergraphs and not know the other definition, i.e. of 'regular hypergraph'. So to me, this is less surprising and indeed something like is_twograph_regular
can make sense.
A twograph_complement
looks very odd, as the definition of complement you need has nothing to do with twographs specifically.
Nathann
comment:86 in reply to: ↑ 84 Changed 6 years ago by
It's surprising, at least for me. Would you object if I added a commit that makes it an inplace function, with an optional
inplace=False
to get a copy?no problem, go ahead with this.
I added the commit at the same location as previously.
Nathann
comment:87 in reply to: ↑ 85 Changed 6 years ago by
Replying to ncohen:
Well, the rationale behind the current code is that someone who wants to take the complement of a two-graph should just call
.complement()
rather than something more complicated. And indeed, the complement of a two-graph has a well-established meaning. It's more an implementation artefact that the base class already hascomplement()
defined, and it's not quite the same. The user should not care about this IMHO.I agree with everything you just said, but there is this other definition above that is inherited, and we can't really change that definition either for it would only apply to uniform hypergraphs...
Why? I see no harm in this, as this is merely an implementation detail, provided this is documented, and this I can certainly do.
I see only one way out: what would you think of making the *default* of
.complement()
to only work for uniform hypergraphs? If we do that, then the problem is solved in a more elegant way. Thoughcomplement
would not work for all instances but then, perhaps *that* is less surprising. And we can make the exception "smart" to indicate that a keyword can change this behaviour.Same was with
is_regular()
, but you didn't like this as it clashed with the default, and I made itis_regular_twograph()
.I take this a bit differently: surely there is such a thing as a "regular two-graph", but you can't work on hypergraphs and not know the other definition, i.e. of 'regular hypergraph'. So to me, this is less surprising and indeed something like
is_twograph_regular
can make sense.
Well, I don't recall what regular hypergraph
is.
(I know where to look it up, but I don't remember its meaning)
A
twograph_complement
looks very odd, as the definition of complement you need has nothing to do with twographs specifically.
At least this would be unambigous.
comment:88 in reply to: ↑ 81 ; follow-up: ↓ 95 Changed 6 years ago by
Replying to ncohen:
T.is_t_design(k=3)
-- useis_uniform
.
I cannot, I need to test that it is a 2-design with blocks of size 3.
comment:89 follow-up: ↓ 90 Changed 6 years ago by
- Commit changed from 6bc5cbd678d6d9db6e99ff23489e0e1a720e8569 to 4f7e3c9f19fc3ccfc143beade9bb82c5f742a2cc
comment:90 in reply to: ↑ 89 Changed 6 years ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
d9b098a trac #18972: Reviewer's commit
e7022f3 trac #18972: inplace seidel_switching
f4add31 Merge branch 'develop' into seidelsw
4f7e3c9 1st portion of fixes for #18972:81
merged 6.9.beta3
and public/18972
in. More change described in the commit message of the the last commit.
comment:91 Changed 6 years ago by
Set it to needs_review
when it will be ready.
comment:92 Changed 6 years ago by
- Commit changed from 4f7e3c9f19fc3ccfc143beade9bb82c5f742a2cc to a3362414d8710523b1a7f118a96fb4617be36637
Branch pushed to git repo; I updated commit sha1. New commits:
a336241 | The rest of fixes for #18972:81:
|
comment:93 Changed 6 years ago by
- Status changed from needs_work to needs_review
comment:94 follow-up: ↓ 113 Changed 6 years ago by
- Status changed from needs_review to needs_work
Please address all the comments or tell my why you chose not to. I can still see designs.TwoGraph
.
Dima, you are no children: you can't just address some of the comments without saying anything and let me figure out what exactly you did, and what you left out.
Nathann
comment:95 in reply to: ↑ 88 ; follow-ups: ↓ 99 ↓ 112 Changed 6 years ago by
T.is_t_design(k=3)
-- useis_uniform
.I cannot, I need to test that it is a 2-design with blocks of size 3.
T.is_t_design(k=3)
is *equivalent* to is_regular+is_uniform(k=3)
.
sage: T = IncidenceStructure([[0,1,2],[3,4,5]]) sage: T.is_t_design(k=3) True sage: T.is_t_design(k=3,return_parameters=True) (True, (1, 6, 3, 1))
Nathann
comment:96 Changed 6 years ago by
I added a commit at public/18972
. It speeds is_twograph
up. Before (with the added 't=2'):
sage: from sage.combinat.designs.twographs import is_twograph sage: T = graphs.OrthogonalArrayBlockGraph(3,6).twograph() sage: %timeit is_twograph(T) 1 loops, best of 3: 18.4 s per loop
After
sage: %timeit is_twograph(T) 1 loops, best of 3: 1.62 s per loop
Nathann
comment:97 Changed 6 years ago by
Added another commit at public/18972
to speedup .twograph()
. Before:
sage: g = graphs.CameronGraph() sage: %timeit g.twograph() 1 loops, best of 3: 1.9 s per loop
After
sage: g = graphs.CameronGraph() sage: %timeit g.twograph() 1 loops, best of 3: 1 s per loop
Nathann
comment:98 follow-up: ↓ 104 Changed 6 years ago by
Note that the tests do not pass on the patchbot
comment:99 in reply to: ↑ 95 ; follow-up: ↓ 100 Changed 6 years ago by
Replying to ncohen:
T.is_t_design(k=3)
-- useis_uniform
.I cannot, I need to test that it is a 2-design with blocks of size 3.
T.is_t_design(k=3)
is *equivalent* tois_regular+is_uniform(k=3)
.
I don't call is_t_design()
this way! I also set t=2
. And surely enough, it's a different story:
sage: T = IncidenceStructure([[0,1,2],[3,4,5]]) sage: T.is_t_design(t=2,k=3) False
You might be confused by the terminology difference that I already explained, that regularity of two-graphs and of hypergraphs are different notions.
In fact, this term is hugely overused in maths in general; there are regular maps, regular rings, regular sequences, regular graphs (which in algebraic are totally different animals from regular (hyper)graphs), regular points, etc etc etc...
sage: T = IncidenceStructure([[0,1,2],[3,4,5]]) sage: T.is_t_design(k=3) True sage: T.is_t_design(k=3,return_parameters=True) (True, (1, 6, 3, 1))Nathann
comment:100 in reply to: ↑ 99 ; follow-up: ↓ 101 Changed 6 years ago by
I don't call
is_t_design()
this way!
Line 2 of is_twograph
.
Nathann
comment:101 in reply to: ↑ 100 ; follow-up: ↓ 102 Changed 6 years ago by
Replying to ncohen:
I don't call
is_t_design()
this way!Line 2 of
is_twograph
.
I am talking about line 1 of is_regular_twograph()
...
Besides, what's wrong about the line 2 of is_twograph`? It's certainly not where the bottleneck is (the latter is in lines 3-4).
comment:102 in reply to: ↑ 101 Changed 6 years ago by
Besides, what's wrong about the line 2 of is_twograph`?
Well, it calls T.is_t_design(k=3)
. If you want to do that you should call is_uniform
and is_regular
instead, and if you don't then t=2
should be added.
It's certainly not where the bottleneck is (the latter is in lines 3-4).
True. My commit improves it a bit.
Nathann
comment:103 Changed 6 years ago by
- Commit changed from a3362414d8710523b1a7f118a96fb4617be36637 to 3350efc6229a8a584774cd452d3d33ee4f5f26bc
Branch pushed to git repo; I updated commit sha1. New commits:
3350efc | inplace has arrived here too
|
comment:104 in reply to: ↑ 98 ; follow-up: ↓ 105 Changed 6 years ago by
Replying to ncohen:
Note that the tests do not pass on the patchbot
one of these is fixed by just pushed 3350efc, also pushed to public/18972.
The other is tricky: the problem is that SRG_280_135_70_60()
needs an optional GAP package, as is clear from gap.load_package("AtlasRep")
there.
How do you like this fixed?
comment:105 in reply to: ↑ 104 ; follow-up: ↓ 106 Changed 6 years ago by
The other is tricky: the problem is that
SRG_280_135_70_60()
needs an optional GAP package, as is clear fromgap.load_package("AtlasRep")
there. How do you like this fixed?
-_-
Well, ideally it would be really cool if we could build it from Sage only. Couldn't we take Gap's generators and have them in the JankoGroup
class?
Nathann
comment:106 in reply to: ↑ 105 ; follow-up: ↓ 107 Changed 6 years ago by
Replying to ncohen:
The other is tricky: the problem is that
SRG_280_135_70_60()
needs an optional GAP package, as is clear fromgap.load_package("AtlasRep")
there. How do you like this fixed?
-_-
Well, ideally it would be really cool if we could build it from Sage only. Couldn't we take Gap's generators and have them in the
JankoGroup
class?
Yes we can (for Janko 1, 2, 3 then, not only 2). How about
groups.permutation.Janko(k)
getting an extra parameter, degree
?
Then groups.permutation.Janko(k)
will give what the do now, and
groups.permutation.Janko(k,degree=blah)
will give a permutation representation of Janko(k)
of degree blah (if one is known to Sage).
Actually, there is no need to store permutations on 280 points, we can get by with ones on 100 points, and generate the former on the fly, as an action on sets.
But this begs for another ticket. Should I open one?
comment:107 in reply to: ↑ 106 ; follow-up: ↓ 108 Changed 6 years ago by
Yes we can (for Janko 1, 2, 3 then, not only 2).
Cool !
How about
groups.permutation.Janko(k)
getting an extra parameter,degree
? Thengroups.permutation.Janko(k)
will give what the do now, andgroups.permutation.Janko(k,degree=blah)
will give a permutation representation of Janko(k) of degree blah (if one is known to Sage).
Hmmmm... I am afraid that I don't even know what that notion of degree is O_o
But this begs for another ticket.
Of course.
Should I open one?
Yesyes please. And you can add an #optional
flag if it is a problem in this ticket.
Nathann
comment:108 in reply to: ↑ 107 ; follow-up: ↓ 111 Changed 6 years ago by
Replying to ncohen:
Hmmmm... I am afraid that I don't even know what that notion of degree is
O_o
degree of a transitive permutation group is the size of its natural domain. E.g. the symmetric group S_n has degree n... And of course degree is a greatly overused word in maths...
But this begs for another ticket.
Of course.
Should I open one?
Yesyes please. And you can add an
#optional
flag if it is a problem in this ticket.
see #19080.
comment:109 Changed 6 years ago by
- Commit changed from 3350efc6229a8a584774cd452d3d33ee4f5f26bc to 4e077dbd9d039c9c375227269cda8a0ce4c0d326
Branch pushed to git repo; I updated commit sha1. New commits:
4e077db | making internet and gap_packages tests optional
|
comment:110 Changed 6 years ago by
Can you add my two speedup commits to your branch, or do you have something against them?
Could you also answer my question about designs.TwoGraph
?
Nathann
comment:111 in reply to: ↑ 108 Changed 6 years ago by
degree of a transitive permutation group is the size of its natural domain.
Oh. Okay :-P
see #19080.
Thanks !
Nathann
comment:112 in reply to: ↑ 95 ; follow-up: ↓ 116 Changed 6 years ago by
Replying to ncohen:
T.is_t_design(k=3)
-- useis_uniform
.I cannot, I need to test that it is a 2-design with blocks of size 3.
T.is_t_design(k=3)
is *equivalent* tois_regular+is_uniform(k=3)
.
This is actually just not true. is_regular+is_uniform(k=3)
is equivalent
to is_t_design(t=1, k=3)
.
In fact, all I need is_uniform(k=3)
, which is equivalent to to is_t_design(k=3)
.
comment:113 in reply to: ↑ 94 ; follow-up: ↓ 118 Changed 6 years ago by
Replying to ncohen:
Please address all the comments or tell my why you chose not to. I can still see
designs.TwoGraph
.
well, designs.TAB
gives
designs.AffineGeometryDesign designs.BalancedIncompleteBlockDesign designs.BlockDesign designs.DesarguesianProjectivePlaneDesign designs.Hadamard3Design designs.HadamardDesign designs.HughesPlane designs.Hypergraph designs.IncidenceStructure designs.ProjectiveGeometryDesign designs.TwoGraph designs.WittDesign designs.balanced_incomplete_block_design designs.best_known_covering_design_from_LJCR designs.difference_family designs.difference_matrix designs.group_divisible_design designs.incomplete_orthogonal_array designs.kirkman_triple_system designs.mutually_orthogonal_latin_squares designs.orthogonal_array designs.orthogonal_arrays designs.projective_plane designs.resolvable_balanced_incomplete_block_design designs.steiner_quadruple_system designs.steiner_triple_system designs.transversal_design
Quite a few of them added by you, right? Why do you ask me to make TwoGraph
a second-class citizen then? I don't mind it removed, but then in the same sweep as the rest. So this is not for this ticket...
comment:114 Changed 6 years ago by
- Commit changed from 4e077dbd9d039c9c375227269cda8a0ce4c0d326 to 25eec1b6d18bb021eccd4b04774111097ff8f3b5
Branch pushed to git repo; I updated commit sha1. New commits:
0d20a94 | inplace has arrived here too
|
7d15add | trac #18972: Speedup is_twograph
|
7a690de | trac #18972: speedup Graph.twograph
|
4e3a0ea | Merge branch 'public/18972' of git://trac.sagemath.org/sage into HEAD
|
95fe0f2 | Merge remote-tracking branch 'trac/public/18972' into seidelsw
|
25eec1b | uniformity, but no regularity
|
comment:115 Changed 6 years ago by
- Status changed from needs_work to needs_review
comment:116 in reply to: ↑ 112 Changed 6 years ago by
This is actually just not true.
is_regular+is_uniform(k=3)
is equivalent tois_t_design(t=1, k=3)
.
True.
In fact, all I need
is_uniform(k=3)
, which is equivalent to tois_t_design(k=3)
.
It is equivalent in term of answers but not in terms of running time, though. So please use T.is_uniform
, whose intent is also much clearer.
Nathann
comment:117 Changed 6 years ago by
Arg. You already did. I thought that you were justifying why you wanted to keep it.
comment:118 in reply to: ↑ 113 ; follow-up: ↓ 119 Changed 6 years ago by
well,
designs.TAB
gives<lots of things>Quite a few of them added by you, right?
Yes. I am quite proud of that.
Why do you ask me to make
TwoGraph
a second-class citizen then?
No. I asked you to *not make it appear in the catalog* (which is different). In the same way that you do not see the following classes (that I also created): BalancedIncompleteBlockDesign
, GroupDivisibleDesign
, PairwiseBalancedDesign
.
Catalogs are not meant to hold generic class constructors (you don't see Graph in 'graphs.' or PermutationGroup
in group.
), but only functions meant to return a "famous object". That's what catalogs are for. And 'TwoGraph?', like 'BalancedIncompleteBlockDesign?', is to be instanciated with a list of blocks (like IncidenceStructure
or BalancedIncompleteBlockDesign
) while orthogonal arrays (which appear in designs.<tab>
) are created from a pair of integers only.
I mean. That's what catalogs are supposed to hold. You have matrix.ones
but not matrix.Matrix
.
Nathann
comment:119 in reply to: ↑ 118 ; follow-up: ↓ 120 Changed 6 years ago by
Replying to ncohen:
well,
designs.TAB
gives<lots of things>Quite a few of them added by you, right?
Yes. I am quite proud of that.
Why do you ask me to make
TwoGraph
a second-class citizen then?No. I asked you to *not make it appear in the catalog* (which is different). In the same way that you do not see the following classes (that I also created):
BalancedIncompleteBlockDesign
,GroupDivisibleDesign
,PairwiseBalancedDesign
.
on the other hand there are classes such as
designs.AffineGeometryDesign designs.BalancedIncompleteBlockDesign designs.BlockDesign designs.DesarguesianProjectivePlaneDesign designs.Hadamard3Design designs.HadamardDesign designs.HughesPlane designs.Hypergraph designs.IncidenceStructure designs.ProjectiveGeometryDesign designs.WittDesign
Perhaps some of them are (misnamed?) functions, I didn't check.
Catalogs are not meant to hold generic class constructors (you don't see Graph in 'graphs.' or
PermutationGroup
ingroup.
),
this is an unfair comparison, for Graph
and PermutationGroup
are in global space!
And you told me to remove TwoGraph
from it, which I duly did.
but only functions meant to return a "famous object". That's what catalogs are for. And 'TwoGraph?', like 'BalancedIncompleteBlockDesign?', is to be instanciated with a list of blocks (like
IncidenceStructure
orBalancedIncompleteBlockDesign
) while orthogonal arrays (which appear indesigns.<tab>
) are created from a pair of integers only.
So what? There isn't much difference between a pair of integers, and a list of lists, from user's point of view in particular. It's quite an artificial distinction here, invisible at user level, be it function, or class, or shmass, whatever. It returns an object, to which one can apply methods, this is what counts. A user does not care whether he calls a function, or a class constructor directly.
Catalog are there for users, and it's just an extra needless hoop for a user to jump through, having to import stuff explicitly, if she wants to call a constructor directly.
comment:120 in reply to: ↑ 119 ; follow-up: ↓ 121 Changed 6 years ago by
Hello Dima,
on the other hand there are classes such as
designs.AffineGeometryDesign # valid designs.BalancedIncompleteBlockDesign # deprecated designs.BlockDesign # should not be there designs.DesarguesianProjectivePlaneDesign # valid designs.Hadamard3Design # valid designs.HadamardDesign # valid designs.HughesPlane # valid designs.Hypergraph # should not be there designs.IncidenceStructure # should not be there designs.ProjectiveGeometryDesign # valid designs.WittDesign # validthis is an unfair comparison, for
Graph
andPermutationGroup
are in global space!
I asked the question on sage-devel. It's quite legitimate, actually.
And you told me to remove
TwoGraph
from it, which I duly did.
You did not. I still have designs.TwoGraph
when I load your branch.
So what? There isn't much difference between a pair of integers, and a list of lists, from user's point of view in particular. It's quite an artificial distinction here, invisible at user level, be it function, or class, or shmass, whatever. It returns an object, to which one can apply methods, this is what counts. A user does not care whether he calls a function, or a class constructor directly.
I do not defend a blind distinction between class/function here. It is more relative to "the amount of data you give the constructor", and "what you get". I posted about this on sage-devel to see what others think.
Catalog are there for users, and it's just an extra needless hoop for a user to jump through, having to import stuff explicitly, if she wants to call a constructor directly.
Well, it's not like everybody is waiting to instanciate TwoGraph
in the first place, but of course the question is fair: if we cannot export everything to the global namespace like it was apparently done before, what are we meant to do with the new classes?
Let's hope the thread will clear things up, and not be the usual "I talk but I don't listen" thread.
Nathann
comment:121 in reply to: ↑ 120 ; follow-up: ↓ 122 Changed 6 years ago by
Replying to ncohen:
Hello Dima,
on the other hand there are classes such as
designs.AffineGeometryDesign # valid designs.BalancedIncompleteBlockDesign # deprecated designs.BlockDesign # should not be there designs.DesarguesianProjectivePlaneDesign # valid designs.Hadamard3Design # valid designs.HadamardDesign # valid designs.HughesPlane # valid designs.Hypergraph # should not be there designs.IncidenceStructure # should not be there designs.ProjectiveGeometryDesign # valid designs.WittDesign # validthis is an unfair comparison, for
Graph
andPermutationGroup
are in global space!I asked the question on sage-devel. It's quite legitimate, actually.
And you told me to remove
TwoGraph
from it, which I duly did.You did not. I still have
designs.TwoGraph
when I load your branch.
I have removed it from global
namespace, as you requested earlier.
sage: TwoGraph --------------------------------------------------------------------------- NameError Traceback (most recent call last) <ipython-input-4-d7f5bedb1058> in <module>() ----> 1 TwoGraph NameError: name 'TwoGraph' is not defined
vs
sage: Graph <class 'sage.graphs.graph.Graph'> sage:
So what? There isn't much difference between a pair of integers, and a list of lists, from user's point of view in particular. It's quite an artificial distinction here, invisible at user level, be it function, or class, or shmass, whatever. It returns an object, to which one can apply methods, this is what counts. A user does not care whether he calls a function, or a class constructor directly.
I do not defend a blind distinction between class/function here. It is more relative to "the amount of data you give the constructor", and "what you get". I posted about this on sage-devel to see what others think.
Catalog are there for users, and it's just an extra needless hoop for a user to jump through, having to import stuff explicitly, if she wants to call a constructor directly.
Well, it's not like everybody is waiting to instanciate
TwoGraph
in the first place,
ditto for, say, WittDesign
, right?
May I refer to a precedent of having classes in design
catalog to have TwoGraph
here?
comment:122 in reply to: ↑ 121 ; follow-up: ↓ 123 Changed 6 years ago by
May I refer to a precedent of having classes in
design
catalog to haveTwoGraph
here?
An error is not a 'precedent'.
Nathann
comment:123 in reply to: ↑ 122 ; follow-ups: ↓ 124 ↓ 125 Changed 6 years ago by
Replying to ncohen:
May I refer to a precedent of having classes in
design
catalog to haveTwoGraph
here?An error is not a 'precedent'.
A precedent is a precedent, and reviewers are to act in a fair and objective manner, akin to judges in a legal system, right?
An "error", approved by something or somebody whose authority you recognise, is a precedent. Either you object to this authority, in an acceptable way, e.g. you open a ticket removing that "error", and actually get it reviewed and removed (just shouting about it is not enough, sorry). Or it stays as it is, and then you have no authority to overrule the precedent.
comment:124 in reply to: ↑ 123 Changed 6 years ago by
Replying to dimpase:
Replying to ncohen:
May I refer to a precedent of having classes in
design
catalog to haveTwoGraph
here?An error is not a 'precedent'.
A precedent is a precedent, and reviewers are to act in a fair and objective manner, akin to judges in a legal system, right?
An "error", approved by something or somebody whose authority you recognise, is a precedent. Either you object to this authority, in an acceptable way, e.g. you open a ticket removing that "error", and actually get it reviewed and removed (just shouting about it is not enough, sorry). Or it stays as it is, and then you have no authority to overrule the precedent.
anyhow, if you are still not convinced, I can remove this thing from designs.
.
comment:125 in reply to: ↑ 123 ; follow-up: ↓ 126 Changed 6 years ago by
A precedent is a precedent, and reviewers are to act in a fair and objective manner, akin to judges in a legal system, right?
Come on Dima, don't build up on top of this idea. Do you really need to be convinced that "sometimes, we make mistakes"? Never saw one? Never did one?
In this case it is even easier. I am 100% sure (did not check) that I did this myself Or that I was the one who reviewed it.
An "error", approved by something or somebody whose authority you recognise, is a precedent.
Excellent. Then let us say that I disregard my own authority.
Either you object to this authority
I just did it in my head.
in an acceptable way
I found it acceptable
e.g. you open a ticket removing that "error", and actually get it reviewed and removed (just shouting about it is not enough, sorry). Or it stays as it is, and then you have no authority to overrule the precedent.
Oh, I plan to remove it, no problem there.
anyhow, if you are still not convinced, I can remove this thing from designs..
Please do. And I will remove the others, unless the thread on Sage-devel indicates that we should keep them instead.
Nathann
comment:126 in reply to: ↑ 125 ; follow-up: ↓ 127 Changed 6 years ago by
Replying to ncohen:
A precedent is a precedent, and reviewers are to act in a fair and objective manner, akin to judges in a legal system, right?
Come on Dima, don't build up on top of this idea. Do you really need to be convinced that "sometimes, we make mistakes"? Never saw one? Never did one?
An "error" resulting in an improvement of the situation is not an error. The is the whole point of this discussion. You agree that having useful constructors discoverable by means of TAB is useful, yet keep telling me that this is an error. If there is a real error here, it is in your head. We are building a system that is meant to be user-friendly; forcing the user to import stuff (which is hard to find too) explicitly is not user-friendly.
In this case it is even easier. I am 100% sure (did not check) that I did this myself Or that I was the one who reviewed it.
An "error", approved by something or somebody whose authority you recognise, is a precedent.
Excellent. Then let us say that I disregard my own authority.
Either you object to this authority
I just did it in my head.
in an acceptable way
I found it acceptable
sometimes what you find acceptable pisses many people off, and you are perfectly aware of this :-)
e.g. you open a ticket removing that "error", and actually get it reviewed and removed (just shouting about it is not enough, sorry). Or it stays as it is, and then you have no authority to overrule the precedent.
Oh, I plan to remove it, no problem there.
get it approved; e.g. try asking me to review it ;-)
anyhow, if you are still not convinced, I can remove this thing from designs..
Please do. And I will remove the others, unless the thread on Sage-devel indicates that we should keep them instead.
there is at least one more voice of reason, agreeing with me, and none agreeing with you.
comment:127 in reply to: ↑ 126 ; follow-up: ↓ 128 Changed 6 years ago by
An "error" resulting in an improvement of the situation is not an error.
I did it myself, and I claim that it was an error. I shouldn't have, and I regret it. That makes it an error, at the very least in the intent.
there is at least one more voice of reason, agreeing with me, and none agreeing with you.
True, but I would like to have a solution with respect to these things in the global namespace too. We do need a way to define new classes without exporting them to the global namespace. At least that would give us a way to get rid of the 10 000 combinat things exported in the wild: if catalogs change and are made able to gather all kind of classes and not only 'famous constructions', there will be a lot of deprecation ahead.
Nathann
comment:128 in reply to: ↑ 127 ; follow-up: ↓ 129 Changed 6 years ago by
Replying to ncohen:
An "error" resulting in an improvement of the situation is not an error.
I did it myself, and I claim that it was an error. I shouldn't have, and I regret it. That makes it an error, at the very least in the intent.
You are not alone, for many scientific discoveries were made this way, by mistake...
there is at least one more voice of reason, agreeing with me, and none agreeing with you.
True, but I would like to have a solution with respect to these things in the global namespace too. We do need a way to define new classes without exporting them to the global namespace.
well, you have invented it already, with IncidenceSystem
. True, lots of deprecations ahead --- how else would you manage to clean up the global namespace?
At least that would give us a way to get rid of the 10 000 combinat things exported in the wild: if catalogs change and are made able to gather all kind of classes and not only 'famous constructions', there will be a lot of deprecation ahead.
At the moment on this ticket you pursue the line that the classes must be hidden from the user, and this is totally unreasonable, you admit it yourself.
IMHO either having TwoGraph
out there in the global namespace (with 10000 other things already there), or having it in designs.TAB is reasonable; pick one, and let us move on.
comment:129 in reply to: ↑ 128 ; follow-up: ↓ 130 Changed 6 years ago by
You are not alone, for many scientific discoveries were made this way, by mistake...
Let me sum it up: 1) You tell me that I am forced to accept it because there is a precedent and that somebody thought that it would be better this way. So I should obey his judgement. 2) You learn that I did it myself, and I tell you that it was a mistake. 3) You tell me that I should do it anyway, because many mistakes are valuable.
I just see you bend the truth wherever it can help you.
well, you have invented it already, with
IncidenceSystem
. True, lots of deprecations ahead --- how else would you manage to clean up the global namespace?
That's a design decision for sage-devel.
At the moment on this ticket you pursue the line that the classes must be hidden from the user
I spent weeks writing code that has to be imported manually. Nobody died.
you admit it yourself.
I am the only reference, when it comes to figure out what *I* think.
IMHO either having
TwoGraph
out there in the global namespace (with 10000 other things already there), or having it in designs.TAB is reasonable; pick one, and let us move on.
This is not the choice we have to make. The choice it between:
1) Global namespace (No)
2) Manual import (possible)
3) designs.TwoGraph
-- must be a collective decision to move everything into the catalogs.
So we are not stuck. If you pick 2, we can have this ticket pass right now and discuss 3 on sage-devel while being able to continue the development of this SRG module. You will easily admit that it does not block us for anything.
Nathann
comment:130 in reply to: ↑ 129 ; follow-up: ↓ 131 Changed 6 years ago by
Replying to ncohen:
IMHO either having
TwoGraph
out there in the global namespace (with 10000 other things already there), or having it in designs.TAB is reasonable; pick one, and let us move on.This is not the choice we have to make. The choice it between: 1) Global namespace (No) 2) Manual import (possible) 3)
designs.TwoGraph
-- must be a collective decision to move everything into the catalogs.So we are not stuck. If you pick 2, we can have this ticket pass right now and discuss 3 on sage-devel while being able to continue the development of this SRG module. You will easily admit that it does not block us for anything
You somehow see designs.IncidenceSystem
as (your favourite?) mistake you have made yourself, yet you are not fixing it, and unwilling to let the others repeat it. This is some kind of dictatorial powers you are enjoying here. You are free to guess my feelings about it.
comment:131 in reply to: ↑ 130 Changed 6 years ago by
You somehow see
designs.IncidenceSystem
as (your favourite?) mistake you have made yourself, yet you are not fixing it
I am cooking. Give me thirty minutes and I will add a ticket. If I do, will you review it or block it? Don't make me write it only to complain on the ticket afterwards because you don't want it to be done.
Nathann
comment:132 Changed 6 years ago by
- Commit changed from 25eec1b6d18bb021eccd4b04774111097ff8f3b5 to a729b27245f217f98bde11e4fc13dd03cdce9c96
Branch pushed to git repo; I updated commit sha1. New commits:
a729b27 | the reviwer has cooked and has eaten my brain (removed stuff from designs.*)
|
comment:133 follow-up: ↓ 134 Changed 6 years ago by
Helloooo again Dima,
Thank you for what you just did. I am not even against the idea of moving all class constructors to the catalogs, but so far it is not done this way and I do not want it to be done without collective agreement that it is what should be done. So I'll not even fight against the idea in this debate.
About your branch, I noticed several last things:
- very long lines in the doc of
is_twograph_descendant
,twograph
, andcomplement
.
- I also wonder about
TwoGraph.__init__
: what is the best behavior for this class which inherits fromIncidenceStructure
? Should all (existing) arguments ofIncidenceStructure.__init__
appear inTwoGraph.__init__
, or should we use**kwargs
instead? If some argument inIncidenceStructure
is added/removed, or if the default value changes, then we will very probably "forget" to updateTwoGraph.__init__
as a result.
AAAAnd then we should be done with this ticket, at long long last..
Nathann
comment:134 in reply to: ↑ 133 ; follow-up: ↓ 135 Changed 6 years ago by
Replying to ncohen:
- very long lines in the doc of
is_twograph_descendant
,twograph
, andcomplement
.
what is the guideline? 80 chars, less, more?
- I also wonder about
TwoGraph.__init__
: what is the best behavior for this class which inherits fromIncidenceStructure
? Should all (existing) arguments ofIncidenceStructure.__init__
appear inTwoGraph.__init__
, or should we use**kwargs
instead? If some argument inIncidenceStructure
is added/removed, or if the default value changes, then we will very probably "forget" to updateTwoGraph.__init__
as a result.
Removing will cause a doctest failure, hopefully...
How does one mix **kwargs
and explicit keywords (which have to be used too, as I need
some control over this)?
comment:135 in reply to: ↑ 134 Changed 6 years ago by
what is the guideline? 80 chars, less, more?
The "official" rule, if I remember correctly, is to follow "yet another senseless" PEP. If I make no mistake, it is something like 80 characters for the code and 72 characters for the doc (no joke).
In Sage it seems that we apply 80 characters everywhere, which is already rather boring to enforce.
Removing will cause a doctest failure, hopefully...
Err, right...
How does one mix
**kwargs
and explicit keywords (which have to be used too, as I need some control over this)?
In the natural way:
sage: def a(hey=3,**kwargs): ....: print hey, kwargs ....: sage: a(6) 6 {} sage: a(hey=9,eeee=4) 9 {'eeee': 4}
Nathann
comment:136 follow-up: ↓ 137 Changed 6 years ago by
- Commit changed from a729b27245f217f98bde11e4fc13dd03cdce9c96 to 1e8e0b4c3168ca179e20377ea6423b0c5385f0bb
Branch pushed to git repo; I updated commit sha1. New commits:
1e8e0b4 | shortening lines
|
comment:137 in reply to: ↑ 136 ; follow-up: ↓ 138 Changed 6 years ago by
comment:138 in reply to: ↑ 137 Changed 6 years ago by
- Status changed from needs_review to positive_review
I will mess with
__init__
on #19098, if you don't mind.
No prob, thanks!
Nathann
P.S.: Please fill in your name in the Author field
comment:139 Changed 6 years ago by
- Status changed from positive_review to needs_work
comment:140 Changed 6 years ago by
- Status changed from needs_work to positive_review
comment:141 Changed 6 years ago by
- Branch changed from u/dimpase/seidelsw to 1e8e0b4c3168ca179e20377ea6423b0c5385f0bb
- Resolution set to fixed
- Status changed from positive_review to closed
Hellooooooo,
1) The docstring must begin with a one-line sentence (http://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content)
2) small case (e.g.:
Graph.tutte_polynomial
)3) If your methods only apply to undirected graphs, they should be in graph.py
4) Add doctests for your new constructor
5) This line is an insult to computer science:
idx = frozenset([self.vertices().index(v) for v in s])
It builds a listn
times to compute the index of an element with a linear search. And I don't think that you need a.Seydel_adjacency_matrix
or a new input type for this function. You can do it like that:6) A new method must be added to the index at the top of the file.
Nathann