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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b76c9a0 to a48e9e2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a48e9e2

modifications suggested by Nathann in comment 1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a48e9e2 to 46bdc55

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

46bdc55

switching construction for the Chang graphs

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e5144c1

initial version of twograph functionality

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 46bdc55 to e5144c1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e5144c1 to 21b01bc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

21b01bc

no need for explicit .eps in LaTeX

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 21b01bc to 0aafa88

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0aafa88 to 3eeca75

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3eeca75

introducing class TwoGraph

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3eeca75 to 7331311

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7331311 to f72b84e

[dimpase]

comment:19

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f72b84e to 5115728

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5115728

make descendant computation faster

[dimpase]

comment:21

Should we add individual graphs to the database here?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:22

Well, unless you expect the code to be long/complicated, I'd say yes.

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:23

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

[dimpase]

comment:24

Replying to @nathanncohen:

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

[dimpase]

comment:25

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

758da33

SRG_279_150_85_75 added.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5115728 to 758da33

[dimpase]

comment:27

Replying to @sagetrac-git:

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)

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:28

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 [comment: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 [comment: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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c4269ae

doc and srg DB fixes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 758da33 to c4269ae

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

449a23e

improving seidel_switching()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c4269ae to 449a23e

[dimpase]

comment:31

Replying to @nathanncohen:

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 [comment: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 [comment: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()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 449a23e to a89a02a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[dimpase]

New commits:

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

[dimpase]

Changed dependencies from #18960, #18948 to #18960, #18948, #18988

[dimpase]

comment:34

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:35

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?