find cospectral graphs

[jasongrout]

This patch adds a function to the graphs object that finds cospectral graphs.

CC: @nathanncohen @rlmill

Component: graph theory

Author: Jason Grout

Reviewer: Nathann Cohen

Merged: sage-4.5.2.alpha0

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

[jasongrout]

comment:1

This patch has a doctest which depends on #9140

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

comment:2

Well... I do not work with spectral theory very often (perhaps read about it once or twice...) but I can check this is correct :-)

From the look of it though, there seems to be an interest in the spectra of very small graphs, as enumerating all the graphs is admissible. One question though : what would you think of "graph_set" instead of "test" ? It sounds a bit wide to me otherwise :-)

Today, I was thinking about some future patches (when all these dependencies will have disappeared). They would be methods taking as an argument a list of graphs, and returning, depending on the flags, the set of minimal elements of this list according to subgraph containment, induced subgraph containment, or minor containment.

I was also thinking of a function taking as an argument a graph and a lambda function (lambda representing a property), and returning one smallest (or all the smallests) subgraphs (possibly induced, or minors) of the graphs given as an argument satisfying the property given by lambda. We could then "clean" it with the functions mentionned before. Well, I just thought, considering this function, that this also may be of interest to you !

Nathann

[jasongrout]

comment:3

Replying to @nathanncohen:

From the look of it though, there seems to be an interest in the spectra of very small graphs, as enumerating all the graphs is admissible. One question though : what would you think of "graph_set" instead of "test" ? It sounds a bit wide to me otherwise :-)

Since "test" can be either a function or an iterable object, I don't think graph_set is a good name. I thought "test" could have two meanings: 1. a test function, 2. a set of graphs to test. This covers the two possible inputs.

If you can think of a more natural way to have these sorts of inputs, please let me know!

Today, I was thinking about some future patches (when all these dependencies will have disappeared). They would be methods taking as an argument a list of graphs, and returning, depending on the flags, the set of minimal elements of this list according to subgraph containment, induced subgraph containment, or minor containment.

That sounds fantastic!

I was also thinking of a function taking as an argument a graph and a lambda function (lambda representing a property), and returning one smallest (or all the smallests) subgraphs (possibly induced, or minors) of the graphs given as an argument satisfying the property given by lambda. We could then "clean" it with the functions mentionned before. Well, I just thought, considering this function, that this also may be of interest to you !

Definitely! I've done much of my research in minimal forbidden subgraphs, so these types of functions are definitely of interest!

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

comment:4

Since "test" can be either a function or an iterable object, I don't think graph_set is a good name. I thought "test" could have two meanings: 1. a test function, 2. a set of graphs to test. This covers the two possible inputs.

If you can think of a more natural way to have these sorts of inputs, please let me know!

I was thinking of your lambda function as defining a set... I'll give it another try, though ! What would you think of "domain" ? If you still don't find it fitting, just forget about it ! :-)

Nathann

[jasongrout]

comment:5

Replying to @nathanncohen:

I was thinking of your lambda function as defining a set... I'll give it another try, though ! What would you think of "domain" ? If you still don't find it fitting, just forget about it ! :-)

I still have a problem with "domain", since it still indicates a set rather than a function restricting the set (at least to me). If test=function, then it is a restriction on graphs with "vertices" vertices. If test=iterable, then it is a domain or graph_set. I guess I just don't see either graph_set or domain having the double-meaning that "test" has.

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

comment:6

It's just that for me, your function does not "restricts" the set but defines it ! :-)

Nathann

[jasongrout]

comment:7

I guess I can see what you're saying now. How about "graphs", since it doesn't have to be a set, and that is more descriptive than "domain"?

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

comment:8

Hmmmmm :-/

Because it is already the name of our generator class ? It's not that awful, though... Ok, let's settle on "graphs" :-)

I will now work on this patch and add a patch myself for this change !

Nathann

[jasongrout]

comment:9

Replying to @nathanncohen:

I will now work on this patch and add a patch myself for this change !

Wait. I'm almost done!

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

comment:10

Okok :-)

[jasongrout]

Attachment: trac-9141-cospectral_graphs.patch.gz

[jasongrout]

comment:11

Okay, patch updated.

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

comment:12

Positive review to your patch, and a small modification, as in 9142, for the math formulas :-)

Nathann

[jasongrout]

comment:13

Thanks for the review! If you change "ommitted" to "omitted" (http://www.merriam-webster.com/dictionary/omitted), positive review on your changes.

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

Attachment: trac_9141-smallfixes.patch.gz

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

comment:14

Done ! Sorry for the delay :-)

Nathann

[e14f4152-4982-4ace-8c95-73a0599b109b]

comment:15

I'm about to attach V2 of Jason's patch, which is rebased for the following queue:

[...other, non-graph theory patches to be merged into 4.5.2.alpha0...]
trac_9111.patch
trac_9111-doc-edits.patch
trac_9111-doc_addition.patch
trac_9373.patch
trac_9375-graph-doctests.patch
trac_9485-strongly_connected_componnents_digraph-fix-nt.patch
trac_8953.patch
trac_9532-graphs-randstate.patch
trac-9141-cospectral_graphs.2.patch
trac_9141-smallfixes.patch

Please check and let me know if there are any problems.

[e14f4152-4982-4ace-8c95-73a0599b109b]

Reviewer: Nathann Cohen

[e14f4152-4982-4ace-8c95-73a0599b109b]

Attachment: trac-9141-cospectral_graphs.2.patch.gz

Rebased for queue in comment 15. Replaces previous version.

[e14f4152-4982-4ace-8c95-73a0599b109b]

comment:16

By the way, the reason is that I got

$ hg qpush
applying trac-9141-cospectral_graphs.patch
patching file sage/graphs/graph_generators.py
Hunk #1 FAILED at 152
1 out of 2 hunks FAILED -- saving rejects to file sage/graphs/graph_generators.py.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac-9141-cospectral_graphs.patch

with V1.

[e14f4152-4982-4ace-8c95-73a0599b109b]

Merged: sage-4.5.2.alpha0