On (di)graph generation

[Jori Mäntysalo]

1) list(graphs.nauty_geng(0)) gives empty list, whereas Sage knows a graph
of 0 vertices. Can someone ask McKay to handle this special case too?

2) Is there an example of graph property that holds after deleting any
vertex but not necessarily after deleting an edge? Or the converse?

3) Currently graphs(...) has parameters vertices and augment. With
graphs(n, augment='edges') it generates all n-vertex graphs, whereas
graphs(n, augment='vertices') generates all graphs of 0, 1, ..., n
vertices. Would it be more logical to have parameters max_vertices and
min_vertices?

4) When is augment='edges' usefull? Is

sum(sum(1 for _ in graphs(i, augment='edges')) for i in range(9))

faster in someone's computer than

sum(1 for _ in graphs(8, augment='vertices'))

?

--
Jori Mäntysalo

[David Joyner]

On Oct 11, 2017 1:45 AM, "Jori Mäntysalo" <Jori.Ma...@uta.fi> wrote:

1) list(graphs.nauty_geng(0)) gives empty list, whereas Sage knows a graph of 0 vertices. Can someone ask McKay to handle this special case too?

Wouldn't it be easier to simply catch that case in the nauty_geng method?

2) Is there an example of graph property that holds after deleting any vertex but not necessarily after deleting an edge? Or the converse?

Completeness, if you start with a complete graph, is preserved if you delete a vertex but not if you delete an edge. 

[Jori Mäntysalo]

On Wed, 11 Oct 2017, David Joyner wrote:

>> 1) list(graphs.nauty_geng(0)) gives empty list, whereas Sage knows a
>> graph of 0 vertices. Can someone ask McKay to handle this special case
>> too?

> Wouldn't it be easier to simply catch that case in the nauty_geng method?

Could be done, but needs some string processing, as the argument is given
as a string to nauty. And anyways, isn't this a corner-case bug?

>> 2) Is there an example of graph property that holds after deleting any
>> vertex but not necessarily after deleting an edge? Or the converse?

> Completeness, if you start with a complete graph, is preserved if you
> delete a vertex but not if you delete an edge. 

True. But it is propably not what one will generate orderly...

--
Jori Mäntysalo

[Dima Pasechnik]

On Wednesday, October 11, 2017 at 10:20:02 AM UTC+1, Jori Mäntysalo wrote:

On Wed, 11 Oct 2017, David Joyner wrote:

>> 1) list(graphs.nauty_geng(0)) gives empty list, whereas Sage knows a
>> graph of 0 vertices. Can someone ask McKay to handle this special case
>> too?

> Wouldn't it be easier to simply catch that case in the nauty_geng method?

Could be done, but needs some string processing, as the argument is given
as a string to nauty. And anyways, isn't this a corner-case bug?

it depends upon the definition of an empty graph, I guess...

[Robert Miller]

On Tue, Oct 10, 2017 at 10:45 PM, Jori Mäntysalo <Jori.Ma...@uta.fi> wrote:

4) When is augment='edges' usefull? Is

One reason it is useful:

You can use the argument "property" to restrict to a subclass of graphs. This argument takes a function and filters the output by testing against this property. If this property is preserved under vertex deletion, then using augment='vertices' will give you all graphs satisfying the property. Similarly for edges. If the property is not preserved as described, then you may be missing some.

Also, if you use augment="edges" you get graphs on exactly N vertices, and if you use augment="vertices" you get graphs on ≤ N vertices.

For any particular family of graphs it is likely there are faster ways to do it - for example we have a method of generating iso-classes of trees in constant time per tree. This is meant to be a useful general-purpose generator.

--

Robert L. Miller
http://www.rlmiller.org/

[Jori Mäntysalo]

(There is #24004 with positive_review, so I code changes should be thinked
after next beta.)

On Wed, 11 Oct 2017, Robert Miller wrote:

> 4) When is augment='edges' usefull? Is
>
> One reason it is useful:
>
> You can use the argument "property" to restrict to a subclass of graphs. This argument takes a function and
> filters the output by testing against this property. If this property is preserved under vertex deletion, then
> using augment='vertices' will give you all graphs satisfying the property. Similarly for edges. If the property
> is not preserved as described, then you may be missing some.

Yes, that's why I asked about properties like that.

But I already found an example where augment='edges' could be used:
property=lambda g: g.size() < n, where n is small number; it will work
with augment='vertices', but is slower.

> Also, if you use augment="edges" you get graphs on exactly N vertices,
> and if you use augment="vertices" you get graphs on ≤ N vertices.

Yes, just as I wrote in message starting this thread. And it seems quite
unlogical.

> For any particular family of graphs it is likely there are faster ways
> to do it - for example we have a method of generating iso-classes of
> trees in constant time per tree. This is meant to be a useful
> general-purpose generator.

True.

--
Jori Mäntysalo

[David Coudert]

Le mercredi 11 octobre 2017 16:36:07 UTC+2, Dima Pasechnik a écrit :

On Wednesday, October 11, 2017 at 10:20:02 AM UTC+1, Jori Mäntysalo wrote:

On Wed, 11 Oct 2017, David Joyner wrote:

>> 1) list(graphs.nauty_geng(0)) gives empty list, whereas Sage knows a
>> graph of 0 vertices. Can someone ask McKay to handle this special case
>> too?

> Wouldn't it be easier to simply catch that case in the nauty_geng method?

Could be done, but needs some string processing, as the argument is given
as a string to nauty. And anyways, isn't this a corner-case bug?

it depends upon the definition of an empty graph, I guess...

Many authors avoid the empty graph (see e.g., the excellent book "Graph Theory with Applications" by Bondy and Murty) as there are no consensus on its properties. Should it be considered connected ? biconnected ? hamiltonian ? minor-free ? transitively reduced ?

 

[Jori Mäntysalo]

On Thu, 12 Oct 2017, David Coudert wrote:

> Many authors avoid the empty graph (see e.g., the excellent book "Graph
> Theory with Applications" by Bondy and Murty) as there are no consensus
> on its properties. Should it be considered connected ? biconnected ?
> hamiltonian ? minor-free ? transitively reduced ?

True, and there has been a discussion about is_tree in this list.

Anyways, different parts of Sage should use same definitions.

--
Jori Mäntysalo