ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 12 May 2016 18:19:08 +0200Why the function graphs() can't generate graphs?https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/ sage: L = list(graphs(5, lambda G: max(G.degree()) >= 2))
sage: len(L)
0
sage: L = list(graphs(5, lambda G: max(G.degree()) < 2))
sage: len(L)
3
sage: L = list(graphs(5))
sage: len(L)
34
Fri, 19 Sep 2014 01:34:45 +0200https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/Answer by tmonteil for <pre><code>sage: L = list(graphs(5, lambda G: max(G.degree()) >= 2))
sage: len(L)
0
sage: L = list(graphs(5, lambda G: max(G.degree()) < 2))
sage: len(L)
3
sage: L = list(graphs(5))
sage: len(L)
34
</code></pre>
https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?answer=24201#post-id-24201The graphs with a given property (provided by the lambda function) are constructed by recurrence (see the ``augment`` parameter in the doc). The problem you are facing is that having maximal degree at least two is not preserved by removing an edge. In particular, the graph on 5 vertices with no edges does not have this property, hence no larger graph can be constructed from this one, which explains why you do not get any graph in your first construction.
A possible workaround is to actually filter among all graphs of size 5:
sage: L = [G for G in graphs(5) if max(G.degree()) >= 2]
sage: len(L)
31
Of course, it is not speed-efficient in general since you have to look at all graphs. In your case it is not a problem since almost all graphs have your property.
Another workaround is to notice that the condition ``max(H.degree()) >= 2`` for ``H=G`` is equivalent to the condition ``min(H.degree()) <= 2`` for ``H=G.complement()``, and this latter condition is hereditary:
sage: M = [G.complement() for G in graphs(5, lambda G: min(G.degree()) <= 2)]
sage: len(M)
31
Of course, you will not see much speed difference in this case, but it can matter for classes of graphs with smaller density among all graphs:
sage: %timeit L = [G for G in graphs(7) if max(G.degree()) >= 5]
1 loops, best of 3: 11.7 s per loop
sage: %timeit M = [G.complement() for G in graphs(7, lambda G: min(G.degree()) <= 1)]
1 loops, best of 3: 5.84 s per loop
Fri, 19 Sep 2014 04:48:13 +0200https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?answer=24201#post-id-24201Comment by danny for <p>The graphs with a given property (provided by the lambda function) are constructed by recurrence (see the <code>augment</code> parameter in the doc). The problem you are facing is that having maximal degree at least two is not preserved by removing an edge. In particular, the graph on 5 vertices with no edges does not have this property, hence no larger graph can be constructed from this one, which explains why you do not get any graph in your first construction.</p>
<p>A possible workaround is to actually filter among all graphs of size 5:</p>
<pre><code>sage: L = [G for G in graphs(5) if max(G.degree()) >= 2]
sage: len(L)
31
</code></pre>
<p>Of course, it is not speed-efficient in general since you have to look at all graphs. In your case it is not a problem since almost all graphs have your property.</p>
<p>Another workaround is to notice that the condition <code>max(H.degree()) >= 2</code> for <code>H=G</code> is equivalent to the condition <code>min(H.degree()) <= 2</code> for <code>H=G.complement()</code>, and this latter condition is hereditary:</p>
<pre><code>sage: M = [G.complement() for G in graphs(5, lambda G: min(G.degree()) <= 2)]
sage: len(M)
31
</code></pre>
<p>Of course, you will not see much speed difference in this case, but it can matter for classes of graphs with smaller density among all graphs:</p>
<pre><code>sage: %timeit L = [G for G in graphs(7) if max(G.degree()) >= 5]
1 loops, best of 3: 11.7 s per loop
sage: %timeit M = [G.complement() for G in graphs(7, lambda G: min(G.degree()) <= 1)]
1 loops, best of 3: 5.84 s per loop
</code></pre>
https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?comment=24212#post-id-24212Thanks for your excellent answer, tmonteil.
Another question, whether for the same reason, the function graphs.nauty_geng() also cannot generate graphs with maximum degree at least k and n vertices?Fri, 19 Sep 2014 17:26:54 +0200https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?comment=24212#post-id-24212Comment by tmonteil for <p>The graphs with a given property (provided by the lambda function) are constructed by recurrence (see the <code>augment</code> parameter in the doc). The problem you are facing is that having maximal degree at least two is not preserved by removing an edge. In particular, the graph on 5 vertices with no edges does not have this property, hence no larger graph can be constructed from this one, which explains why you do not get any graph in your first construction.</p>
<p>A possible workaround is to actually filter among all graphs of size 5:</p>
<pre><code>sage: L = [G for G in graphs(5) if max(G.degree()) >= 2]
sage: len(L)
31
</code></pre>
<p>Of course, it is not speed-efficient in general since you have to look at all graphs. In your case it is not a problem since almost all graphs have your property.</p>
<p>Another workaround is to notice that the condition <code>max(H.degree()) >= 2</code> for <code>H=G</code> is equivalent to the condition <code>min(H.degree()) <= 2</code> for <code>H=G.complement()</code>, and this latter condition is hereditary:</p>
<pre><code>sage: M = [G.complement() for G in graphs(5, lambda G: min(G.degree()) <= 2)]
sage: len(M)
31
</code></pre>
<p>Of course, you will not see much speed difference in this case, but it can matter for classes of graphs with smaller density among all graphs:</p>
<pre><code>sage: %timeit L = [G for G in graphs(7) if max(G.degree()) >= 5]
1 loops, best of 3: 11.7 s per loop
sage: %timeit M = [G.complement() for G in graphs(7, lambda G: min(G.degree()) <= 1)]
1 loops, best of 3: 5.84 s per loop
</code></pre>
https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?comment=33389#post-id-33389See also the following question http://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/?answer=33386#post-id-33386Thu, 12 May 2016 18:19:08 +0200https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?comment=33389#post-id-33389Comment by kcrisman for <p>The graphs with a given property (provided by the lambda function) are constructed by recurrence (see the <code>augment</code> parameter in the doc). The problem you are facing is that having maximal degree at least two is not preserved by removing an edge. In particular, the graph on 5 vertices with no edges does not have this property, hence no larger graph can be constructed from this one, which explains why you do not get any graph in your first construction.</p>
<p>A possible workaround is to actually filter among all graphs of size 5:</p>
<pre><code>sage: L = [G for G in graphs(5) if max(G.degree()) >= 2]
sage: len(L)
31
</code></pre>
<p>Of course, it is not speed-efficient in general since you have to look at all graphs. In your case it is not a problem since almost all graphs have your property.</p>
<p>Another workaround is to notice that the condition <code>max(H.degree()) >= 2</code> for <code>H=G</code> is equivalent to the condition <code>min(H.degree()) <= 2</code> for <code>H=G.complement()</code>, and this latter condition is hereditary:</p>
<pre><code>sage: M = [G.complement() for G in graphs(5, lambda G: min(G.degree()) <= 2)]
sage: len(M)
31
</code></pre>
<p>Of course, you will not see much speed difference in this case, but it can matter for classes of graphs with smaller density among all graphs:</p>
<pre><code>sage: %timeit L = [G for G in graphs(7) if max(G.degree()) >= 5]
1 loops, best of 3: 11.7 s per loop
sage: %timeit M = [G.complement() for G in graphs(7, lambda G: min(G.degree()) <= 1)]
1 loops, best of 3: 5.84 s per loop
</code></pre>
https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?comment=24206#post-id-24206Great explanation - I figured it was something along these lines but was too lazy to go more in depth.Fri, 19 Sep 2014 14:38:22 +0200https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?comment=24206#post-id-24206Answer by kcrisman for <pre><code>sage: L = list(graphs(5, lambda G: max(G.degree()) >= 2))
sage: len(L)
0
sage: L = list(graphs(5, lambda G: max(G.degree()) < 2))
sage: len(L)
3
sage: L = list(graphs(5))
sage: len(L)
34
</code></pre>
https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?answer=24200#post-id-24200I think you need to give that function the `property` keyword... but also look at the documentation.
- ``property`` -- (default: ``lambda x: True``) any property to be
tested on graphs before generation, but note that in general the
graphs produced are not the same as those produced by using the
property function to filter a list of graphs produced by using
the ``lambda x: True`` default. The generation process assumes
the property has certain characteristics set by the ``augment``
argument, and only in the case of inherited properties such that
all subgraphs of the relevant kind (for ``augment='edges'`` or
``augment='vertices'``) of a graph with the property also
possess the property will there be no missing graphs. (The
``property`` argument is ignored if ``degree_sequence`` is
specified.)
That's a large caveat as to what sort of functions can be put in there, so perhaps this is also part of the problem.Fri, 19 Sep 2014 04:10:47 +0200https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?answer=24200#post-id-24200