Re: [sage-devel] On (di)graph generation

2017-10-12 Thread 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

Re: [sage-devel] On (di)graph generation

2017-10-12 Thread 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 ?

 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] On (di)graph generation

2017-10-12 Thread 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

Re: [sage-devel] On (di)graph generation

2017-10-11 Thread Robert Miller 
On Tue, Oct 10, 2017 at 10:45 PM, Jori Mäntysalo 
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/

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] On (di)graph generation

2017-10-11 Thread 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...
 

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

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] On (di)graph generation

2017-10-11 Thread 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

Re: [sage-devel] On (di)graph generation

2017-10-11 Thread David Joyner 
On Oct 11, 2017 1:45 AM, "Jori Mäntysalo"  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.





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

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] On (di)graph generation

2017-10-10 Thread 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