Use nauty as the default generator for graphs

[f29946bc-ee7b-48cd-9abc-3445948c551d]

This patch will make plain graphs(n) to use nauty. Otherwise, for example if user uses size option or similar, old behavior is continued.

CC: @slel

Component: graph theory

Author: Jori Mäntysalo

Branch/Commit: d43607d

Reviewer: David Coudert

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

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Branch: u/jmantysalo/default-nauty

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:2

Before the patch it takes about 40 seconds to run sum(1 for g in graphs(8) if g.is_connected()). After the patch it is about half of a second.

---

New commits:

b9dfe35

Nauty as default generator.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Commit: b9dfe35

[slel]

comment:3

Not committing to a full review of this ticket, but just pointing out a typo: hamiltionian -> hamiltonian.

Also not sure about the change to the pre-existing doctest

Use ``graphs(n)`` to iterate through all non-isomorphic graphs of given size::

    sage: for g in graphs(4):
    ....:     print(g.spectrum())

which checked that we get 11 graphs on 4 vertices, and that they are pairwise non-isomorphic (since their spectra are). The proposed replacement doctest does not illustrate that.

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

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

da2e304

Typo.

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

Changed commit from b9dfe35 to da2e304

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:5

Replying to @slel:

Not committing to a full review of this ticket, but just pointing out a typo: hamiltionian -> hamiltonian.

Thanks, corrected.

Also not sure about the change to the pre-existing doctest which checked that we get 11 graphs on 4 vertices, and that they are pairwise non-isomorphic (since their spectra are). The proposed replacement doctest does not illustrate that.

It's too long for that, a user won't easily see if there are duplicates or not. But better example would be nice.

[slel]

comment:6

How about something like the following,

sage: for g in graphs(4):
....:     print((g.num_edges(), [g.degree(v) for v in g]))
....:     
(0, [0, 0, 0, 0])
(1, [1, 1, 0, 0])
(2, [2, 1, 1, 0])
(3, [2, 2, 2, 0])
(3, [3, 1, 1, 1])
(2, [1, 1, 1, 1])
(3, [2, 1, 2, 1])
(4, [2, 2, 3, 1])
(4, [2, 2, 2, 2])
(5, [2, 3, 3, 2])
(6, [3, 3, 3, 3])

inspired by the answers to this math.stackexchange question:

• https://math.stackexchange.com/questions/583870/how-many-four-vertex-graphs-are-there-up-to-isomorphism

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

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

5932c0e

A better example.

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

Changed commit from da2e304 to 5932c0e

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:8

Replying to @slel:

How about something like the following,

sage: for g in graphs(4):
....:     print((g.num_edges(), [g.degree(v) for v in g]))

Good idea, I used that but degree_sequence() instead of manual degree list.

[dcoudert]

comment:9

Why do you need to pass property=lambda _: True when calling graph_gen ? It's the default value of property in graphs, right ?

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:10

Replying to @dcoudert:

Why do you need to pass property=lambda _: True when calling graph_gen ? It's the default value of property in graphs, right ?

It is the way to use "old" generator for testing purposes. Otherwise nauty will be used.

[dcoudert]

comment:11

Ok, understood.

There are some failing doctests in src/sage/graphs/graph.py and other files (see the patchbot).

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

Changed commit from 5932c0e to e562d8b

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

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

e562d8b

Merge branch 'develop' into t/24951/default-nauty

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

Changed commit from e562d8b to d43607d

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

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

d43607d

Correct tests.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:14

Replying to @dcoudert:

There are some failing doctests in src/sage/graphs/graph.py and other files (see the patchbot).

Should work now.

(The same problem again... A vertex has set of neighbors, not a list on neighbors. Sometimes there is no way to make good and clear, but also testable, examples.)

[dcoudert]

comment:15

For me this patch is now good to go.

[fchapoton]

comment:16

missing reviewer's name

[dcoudert]

Reviewer: David Coudert

[vbraun]

Changed branch from u/jmantysalo/default-nauty to d43607d