twographs and Seidel switching

[dimpase]

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

Depends on #18960
Depends on #18948
Depends on #18988
Depends on #18991
Depends on #18986
Depends on #19018
Depends on #19019

CC: @nathanncohen

Component: graph theory

Author: Dima Pasechnik

Branch/Commit: 1e8e0b4

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/18972

[nathanncohen]

comment:1

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

[dimpase]

comment:2

Replying to @nathanncohen:

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

[nathanncohen]

comment:3

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

[dimpase]

comment:4

Replying to @nathanncohen:

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

[nathanncohen]

comment:5

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

[dimpase]

comment:6

Replying to @nathanncohen:

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.

[nathanncohen]

comment:7

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

[dimpase]

comment:8

Replying to @nathanncohen:

There are many papers and book chapters written about Seidel adjacency matrix and Seidel switching.

I had never heard of it before today.

Really? #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 ;-)

[nathanncohen]

comment:9

I had never heard of it before today.

Really? #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

[sagetrac-git]

Changed commit from b76c9a0 to a48e9e2

[sagetrac-git]

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

a48e9e2

modifications suggested by Nathann in comment 1

[sagetrac-git]

Changed commit from a48e9e2 to 46bdc55

[sagetrac-git]

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

46bdc55

switching construction for the Chang graphs

[sagetrac-git]

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

e5144c1

initial version of twograph functionality

[sagetrac-git]

Changed commit from 46bdc55 to e5144c1

[sagetrac-git]

Changed commit from e5144c1 to 21b01bc

[sagetrac-git]

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

21b01bc

no need for explicit .eps in LaTeX

[sagetrac-git]

Changed commit from 21b01bc to 0aafa88

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 0aafa88 to 3eeca75

[sagetrac-git]

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

3eeca75

introducing class TwoGraph

[sagetrac-git]

Changed commit from 3eeca75 to 7331311

[sagetrac-git]

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

7331311

minor typos etc

[dimpase]

Dependencies: #18960, #18948

[dimpase]

comment:17

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)

[sagetrac-git]

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

[nathanncohen]

comment:125

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

[dimpase]

comment:126

Replying to @nathanncohen:

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.

[nathanncohen]

comment:127

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

[dimpase]

comment:128

Replying to @nathanncohen:

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.

[nathanncohen]

comment:129

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

[dimpase]

comment:130

Replying to @nathanncohen:

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.

[nathanncohen]

comment:131

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

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 25eec1b to a729b27

[nathanncohen]

comment:133

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

[dimpase]

comment:134

Replying to @nathanncohen:

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

[nathanncohen]

comment:135

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

[sagetrac-git]

Changed commit from a729b27 to 1e8e0b4

[sagetrac-git]

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

1e8e0b4

shortening lines

[dimpase]

comment:137

Replying to @sagetrac-git:

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.

[nathanncohen]

comment:138

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

[dimpase]

Author: Dima Pasechnik

[vbraun]

Changed branch from u/dimpase/seidelsw to 1e8e0b4