Opened 6 years ago

Closed 6 years ago

# twographs and Seidel switching

Reported by: Owned by: dimpase major sage-6.9 graph theory ncohen Dima Pasechnik Nathann Cohen N/A 1e8e0b4 1e8e0b4c3168ca179e20377ea6423b0c5385f0bb #18960, #18948, #18988, #18991, #18986, #19018, #19019

### Description

Implement twographs and Seidel switching to realise more entries in Brouwer database

### comment:1 follow-up: ↓ 2 Changed 6 years ago by 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)

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 list n 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:

sage: g = graphs.PetersenGraph()
sage: s = {1,2,3,4}
sage: sc = set(g).difference(s)
sage: b = g.edge_boundary(s)
sage: g.add_edges((x,y) for x in s for y in sc)
sage: g.delete_edges(b)


6) A new method must be added to the index at the top of the file.

Nathann

### comment:2 in reply to: ↑ 1 ; follow-up: ↓ 3 Changed 6 years ago by dimpase

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 list n 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 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.

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 dimpase

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 ncohen

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 dimpase

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 ncohen

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 dimpase

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 ncohen

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 git

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

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

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

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

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

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

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

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

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

TODO: constructing the descent graph directly from a graph should be much faster.

### comment:20 Changed 6 years ago by git

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

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

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 ncohen

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 dimpase

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 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.

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).

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

### comment:25 in reply to: ↑ 24 Changed 6 years ago by dimpase

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 git

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

Branch pushed to git repo; I updated commit sha1. New commits:

 ​758da33 SRG_279_150_85_75 added.

I don't know how to rebuild the database, so that it is available as

sage: graphs.strongly_regular_graph(279, 150, 85, 75)


### comment:28 in reply to: ↑ 24 ; follow-up: ↓ 31 Changed 6 years ago by ncohen

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) vs O(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 git

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

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

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 nor TwoGraph.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) vs O(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.

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) in strongly_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 git

• Commit changed from 449a23ec5b0305fc2f7132bdd38ba0923ec01b89 to a89a02a24b44fd0b2ce1c92ecce22b672bbd9e21

Branch pushed to git repo; I updated commit sha1. New commits:

 ​d959afa trac #18988: Orthogonal Polar graphs in strongly_regular_graph ​a89a02a another unknown graph, instead of the known one

### comment:33 Changed 6 years ago by dimpase

• Dependencies changed from #18960, #18948 to #18960, #18948, #18988

New commits:

 ​d959afa trac #18988: Orthogonal Polar graphs in strongly_regular_graph ​a89a02a another unknown graph, instead of the known one

### comment:34 Changed 6 years ago by dimpase

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

### comment:36 in reply to: ↑ 35 Changed 6 years ago by dimpase

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 git

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

• Dependencies changed from #18960, #18948, #18988 to #18960, #18948, #18988, #18991

New commits:

 ​12753b1 merged

### comment:39 Changed 6 years ago by git

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

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

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 ncohen

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 ncohen

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 ncohen

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 dimpase

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 more O_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 ncohen

it's only because this something might return more than True or False; namely, Unknown. (this is your design, not mine...:-)

Sorry, you cannot blae 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

Version 0, edited 6 years ago by ncohen (next)

### comment:47 in reply to: ↑ 46 ; follow-up: ↓ 48 Changed 6 years ago by dimpase

it's only because this something might return more than True or False; 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 ncohen

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

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

### comment:49 Changed 6 years ago by ncohen

• Status changed from needs_review to needs_work

The branch is in conflict with the latest beta.

### comment:50 Changed 6 years ago by git

• Commit changed from 0a2dae4d4836e37f00bcc2af10dbb1b1d0313c88 to 1b7f6b99019699fdccb4bb9afa86315defc87994

Branch pushed to git repo; I updated commit sha1. New commits:

 ​7d4db20 rebased over beta1 ​1b7f6b9 removed some annoying to reviewer things

### comment:51 Changed 6 years ago by dimpase

• Status changed from needs_work to needs_review

### comment:52 follow-up: ↓ 53 Changed 6 years ago by ncohen

• 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 expect Integer(1) and get float(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 by copy(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 dimpase

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 expect Integer(1) and get float(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 by copy(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 ncohen

• 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) or Graph([V,edges]) or even Graph(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 fed blah 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 by copy(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 dimpase

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

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 fed blah 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 by copy(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 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.

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 ncohen

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 dimpase

• Dependencies changed from #18960, #18948, #18988, #18991 to #18960, #18948, #18988, #18991, #18986

### comment:58 Changed 6 years ago by git

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

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

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

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 git

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

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

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 dimpase

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 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.

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 dimpase

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.

### comment:68 Changed 6 years ago by git

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

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 dimpase

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?

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 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.

Nathann

### comment:72 Changed 6 years ago by git

• Commit changed from 799a2bf3bea99309b02eb11cc5438e428135be0c to 68c0edd21e25d74df2bf41e060e9e55c99ca2fca

Branch pushed to git repo; I updated commit sha1. New commits:

 ​b9fd7af removed spaces and added r's ​68c0edd moved twograph_descendant to twographs.py, and docs improved

### comment:73 in reply to: ↑ 71 Changed 6 years ago by dimpase

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 ncohen

• 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 with complement(), 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 those v0,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 dimpase

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 ncohen

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.

Nathann

### comment:77 in reply to: ↑ 74 Changed 6 years ago by dimpase

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

Right.

### comment:79 follow-up: ↓ 80 Changed 6 years ago by git

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

Branch pushed to git repo; I updated commit sha1. New commits:

 ​6bc5cbd next round of fixes, cf #18972:75

this addresses all the requested changes; regarding the last comment, I keep k0 and k, as k is a variable in the code...

### comment:81 follow-ups: ↓ 82 ↓ 88 Changed 6 years ago by ncohen

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 find PermutationGroup in groups.<tab>, and neither do you find Graph in graphs.<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 of is_regular -- checking that the input is indeed a twograph should be done in TwoGraph.__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 on IncidenceStructure and on TwoGraph. Could you conform to the most general specification?
• T.is_t_design(k=3) -- use is_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 a inplace=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 dimpase

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 on IncidenceStructure and on TwoGraph. 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 a inplace=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 ncohen

• 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() as twograph_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 dimpase

no, for two-graphs it's the way it is. Should I rename this .complement() as twograph_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 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 has complement() 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 it is_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 ncohen

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 dimpase

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.

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. 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 it is_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 dimpase

• T.is_t_design(k=3) -- use is_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 git

• Commit changed from 6bc5cbd678d6d9db6e99ff23489e0e1a720e8569 to 4f7e3c9f19fc3ccfc143beade9bb82c5f742a2cc

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

### comment:90 in reply to: ↑ 89 Changed 6 years ago by dimpase

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 ncohen

Set it to needs_review when it will be ready.

### comment:92 Changed 6 years ago by git

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

• Status changed from needs_work to needs_review

### comment:94 follow-up: ↓ 113 Changed 6 years ago by ncohen

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

• T.is_t_design(k=3) -- use is_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 ncohen

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 ncohen

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 ncohen

Note that the tests do not pass on the patchbot

### comment:99 in reply to: ↑ 95 ; follow-up: ↓ 100 Changed 6 years ago by dimpase

• T.is_t_design(k=3) -- use is_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).

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 ncohen

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 dimpase

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 ncohen

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 git

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

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 ncohen

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?

-_-

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 dimpase

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?

-_-

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 ncohen

Yes we can (for Janko 1, 2, 3 then, not only 2).

Cool !

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).

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 dimpase

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 git

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

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 ncohen

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 dimpase

• T.is_t_design(k=3) -- use is_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).

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 dimpase

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.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_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 git

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

• Status changed from needs_work to needs_review

### comment:116 in reply to: ↑ 112 Changed 6 years ago by ncohen

This is actually just not true. is_regular+is_uniform(k=3) is equivalent to is_t_design(t=1, k=3).

True.

In fact, all I need is_uniform(k=3), which is equivalent to to is_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 ncohen

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 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.

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

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

### comment:119 in reply to: ↑ 118 ; follow-up: ↓ 120 Changed 6 years ago by dimpase

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.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 in group.),

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 or BalancedIncompleteBlockDesign) while orthogonal arrays (which appear in designs.<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 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.HughesPlane # valid
designs.Hypergraph # should not be there
designs.IncidenceStructure # should not be there
designs.ProjectiveGeometryDesign # valid
designs.WittDesign # valid


this is an unfair comparison, for Graph and PermutationGroup 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 dimpase

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.HughesPlane # valid
designs.Hypergraph # should not be there
designs.IncidenceStructure # should not be there
designs.ProjectiveGeometryDesign # valid
designs.WittDesign # valid


this is an unfair comparison, for Graph and PermutationGroup 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 ncohen

May I refer to a precedent of having classes in design catalog to have TwoGraph here?

An error is not a 'precedent'.

Nathann

### comment:123 in reply to: ↑ 122 ; follow-ups: ↓ 124 ↓ 125 Changed 6 years ago by dimpase

May I refer to a precedent of having classes in design catalog to have TwoGraph 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 dimpase

May I refer to a precedent of having classes in design catalog to have TwoGraph 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 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?

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 dimpase

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 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.

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 dimpase

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 ncohen

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 dimpase

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 ncohen

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 git

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

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, and complement.
• I also wonder about TwoGraph.__init__: what is the best behavior for this class which inherits from IncidenceStructure? Should all (existing) arguments of IncidenceStructure.__init__ appear in TwoGraph.__init__, or should we use **kwargs instead? If some argument in IncidenceStructure is added/removed, or if the default value changes, then we will very probably "forget" to update TwoGraph.__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 dimpase

• very long lines in the doc of is_twograph_descendant, twograph, and complement.

what is the guideline? 80 chars, less, more?

• I also wonder about TwoGraph.__init__: what is the best behavior for this class which inherits from IncidenceStructure? Should all (existing) arguments of IncidenceStructure.__init__ appear in TwoGraph.__init__, or should we use **kwargs instead? If some argument in IncidenceStructure is added/removed, or if the default value changes, then we will very probably "forget" to update TwoGraph.__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 ncohen

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 git

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

Branch pushed to git repo; I updated commit sha1. New commits:

 ​1e8e0b4 shortening lines

I will mess with __init__ on #19098, if you don't mind.

### comment:138 in reply to: ↑ 137 Changed 6 years ago by ncohen

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

• Status changed from positive_review to needs_work

### comment:140 Changed 6 years ago by dimpase

• Authors set to Dima Pasechnik
• Status changed from needs_work to positive_review

### comment:141 Changed 6 years ago by vbraun

• Branch changed from u/dimpase/seidelsw to 1e8e0b4c3168ca179e20377ea6423b0c5385f0bb
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.