Re: [sage-devel] On (di)graph generation
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
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
(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
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
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
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
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
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