Probable Bug in Graph Generation

[Fidel]

Hello,

I'm running sage-4.0

Prof. Rafael Villarroel told me about some weird things happening in
sage. Here is a sample session

sage: L = list ( graphs(5, lambda G: G.is_bipartite()) ); len(L)
13
sage: X = list ( graphs(5, lambda G: G.is_connected()) ); len(X)
0
sage: T = list ( graphs(5, lambda G: G.is_tree()) ); len(T)
0
sage: F = list ( graphs(5, lambda G: G.is_forest()) ); len(F)
10
sage: V = list ( graphs(5, property=lambda G: G.is_vertex_transitive
()) ); len(V)
1

In some cases we get no results, and in some others we get partial
results.
If we try first constructing the list and then filtering, it works.
e.g.

sage: X=[g for g in list(graphs(5)) if g.is_connected()];len
(X)
21
sage: V=[g for g in list(graphs(5)) if g.is_vertex_transitive()];len
(V)
3

Is this a bug in the generator? Thanks for your attention.

Greetings,
Fidel

[Jason Grout]

It's not a bug in the generator (probably not), but it is a bug in the
documentation, in my opinion. Well, at least it would help if there was
a pointer in the documentation for "property" that pointed to the
clarifications in the docs for the "augment" parameter.

From the documentation, the augment parameter affects how (and when)
the property argument works:

- ``'vertices'`` - augments by adding a vertex, and
edges incident to that vertex. In this case, all graphs on up to
n=vertices are generated. If for any graph G satisfying the
property, every subgraph, obtained from G by deleting one vertex
and only edges incident to that vertex, satisfies the property,
then this will generate all graphs with that property. If this does
not hold, then all the graphs generated will satisfy the property,
but there will be some missing.

- ``'edges'`` - augments a fixed number of vertices by
adding one edge In this case, all graphs on exactly n=vertices are
generated. If for any graph G satisfying the property, every
subgraph, obtained from G by deleting one edge but not the vertices
incident to that edge, satisfies the property, then this will
generate all graphs with that property. If this does not hold, then
all the graphs generated will satisfy the property, but there will
be some missing.

Basically, the property test is applied to a graph before it is used to
generate more graphs. So if you have a property that is inherited
(i.e., a property such that if a graph has it, then all subgraphs
(induced or edge subgraphs, depending on the augment parameter), things
will work fine. Otherwise, you'll probably be missing graphs.

Thanks,

Jason

--
Jason Grout