ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 12 May 2016 11:18:04 -0500Using a lambda expression in digraphs fails for len(G.sinks())?http://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/I'm gathering digraphs that have exactly one sink.
This list comprehension works fine to find the 6 such digraphs of order 3 & put them in a list:
[G for G in digraphs(3) if len(G.sinks()) == 1]
However, I need this to work in a lambda expression to make it part of a larger calculation. However,
digraphs(3,lambda G: len(G.sinks()) == 1)
creates an iterator that returns no entries.
Creating a lamba expression creates the same unexpected zero-length iterator in digraphs, but that same iterator correctly finds the 6 single-sink digraphs if used in a for expression:
sage: property = lambda G: len(G.sinks()) == 1
sage: T = digraphs(3, property)
sage: print(list(T))
[]
sage: for H in digraphs(3):
....: print property(H)
....:
False
False
False
True
False
False
False
False
True
True
True
True
False
True
False
False
So, what's the right way to generate the one-sink digraphs of order N directly in the digraphs() generator?
Thu, 12 May 2016 10:05:40 -0500http://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/Answer by tmonteil for <p>I'm gathering digraphs that have exactly one sink.
This list comprehension works fine to find the 6 such digraphs of order 3 & put them in a list:</p>
<pre><code>[G for G in digraphs(3) if len(G.sinks()) == 1]
</code></pre>
<p>However, I need this to work in a lambda expression to make it part of a larger calculation. However,</p>
<pre><code>digraphs(3,lambda G: len(G.sinks()) == 1)
</code></pre>
<p>creates an iterator that returns no entries.
Creating a lamba expression creates the same unexpected zero-length iterator in digraphs, but that same iterator correctly finds the 6 single-sink digraphs if used in a for expression:</p>
<pre><code>sage: property = lambda G: len(G.sinks()) == 1
sage: T = digraphs(3, property)
sage: print(list(T))
[]
sage: for H in digraphs(3):
....: print property(H)
....:
False
False
False
True
False
False
False
False
True
True
True
True
False
True
False
False
</code></pre>
<p>So, what's the right way to generate the one-sink digraphs of order N directly in the digraphs() generator? </p>
http://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/?answer=33386#post-id-33386If you look at the documentation of the `digraph` function by typing `digraph?`, you sill see that there is a `augment` parameter, which is `'edges'` by default, which says:
* "'edges'" - augments a fixed number of vertices by adding one
edge In this case, all digraphs 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 digraphs with that property. If this does not
hold, then all the digraphs generated will satisfy the property,
but there will be some missing.
This means that the graphs are constructed recursively by adding edges as long as the property is satisfied, so, if you want this construction to work, your property must be hereditary (i.e. it must stay valid when you remove edges), which is not the case for the propoerty "having exactly one sink".
You can see more explanation in the (answer of the) following question http://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?answer=24201#post-id-24201
As for that case, the construction `[G for G in digraphs(3) if len(G.sinks()) == 1]` is inefficient since all graphs are created and then filtered, whils with the hereditary construction, there are many graphs that are not even considered since they come from a subgraph that do not have the property. This is very important in terms of efficiency.
Not everything is lost, while `G.sinks()) == 1` is not a edge-hereditary property, `G.sinks()) >= 1` is edge-hereditary since adding an edge can only kill sinks, not create some. So, instead of filtering `G.sinks()) == 1` on all digraphs, you can filter `G.sinks()) == 1` among recursively constructed digraphs with `G.sinks()) >= 1`. You can check that there is indeed some benefit, especially when the number of vertices increases:
sage: n = 3
sage: %time len([G for G in digraphs(n) if len(G.sinks()) == 1])
CPU times: user 40 ms, sys: 0 ns, total: 40 ms
Wall time: 46.2 ms
6
sage: %time len([H for H in digraphs(n,lambda G: len(G.sinks()) >= 1) if len(H.sinks()) == 1])
CPU times: user 36 ms, sys: 0 ns, total: 36 ms
Wall time: 31.4 ms
6
sage: n = 4
sage: %time len([G for G in digraphs(n) if len(G.sinks()) == 1])
CPU times: user 1.23 s, sys: 28 ms, total: 1.26 s
Wall time: 1.22 s
70
sage: %time len([H for H in digraphs(n,lambda G: len(G.sinks()) >= 1) if len(H.sinks()) == 1])
CPU times: user 732 ms, sys: 28 ms, total: 760 ms
Wall time: 690 ms
70
sage: n = 5
sage: %time len([G for G in digraphs(n) if len(G.sinks()) == 1])
CPU times: user 1min 38s, sys: 52 ms, total: 1min 38s
Wall time: 1min 38s
2340
sage: %time len([H for H in digraphs(n,lambda G: len(G.sinks()) >= 1) if len(H.sinks()) == 1])
CPU times: user 24 s, sys: 68 ms, total: 24.1 s
Wall time: 24 s
2340
Thu, 12 May 2016 10:56:56 -0500http://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/?answer=33386#post-id-33386Comment by jim_snydergrant for <div class="snippet"><p>If you look at the documentation of the <code>digraph</code> function by typing <code>digraph?</code>, you sill see that there is a <code>augment</code> parameter, which is <code>'edges'</code> by default, which says:</p>
<pre><code>* "'edges'" - augments a fixed number of vertices by adding one
edge In this case, all digraphs 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 digraphs with that property. If this does not
hold, then all the digraphs generated will satisfy the property,
but there will be some missing.
</code></pre>
<p>This means that the graphs are constructed recursively by adding edges as long as the property is satisfied, so, if you want this construction to work, your property must be hereditary (i.e. it must stay valid when you remove edges), which is not the case for the propoerty "having exactly one sink".</p>
<p>You can see more explanation in the (answer of the) following question <a href="http://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/?answer=24201#post-id-24201">http://ask.sagemath.org/question/2419...</a></p>
<p>As for that case, the construction <code>[G for G in digraphs(3) if len(G.sinks()) == 1]</code> is inefficient since all graphs are created and then filtered, whils with the hereditary construction, there are many graphs that are not even considered since they come from a subgraph that do not have the property. This is very important in terms of efficiency.</p>
<p>Not everything is lost, while <code>G.sinks()) == 1</code> is not a edge-hereditary property, <code>G.sinks()) >= 1</code> is edge-hereditary since adding an edge can only kill sinks, not create some. So, instead of filtering <code>G.sinks()) == 1</code> on all digraphs, you can filter <code>G.sinks()) == 1</code> among recursively constructed digraphs with <code>G.sinks()) >= 1</code>. You can check that there is indeed some benefit, especially when the number of vertices increases:</p>
<pre><code>sage: n = 3
sage: %time len([G for G in digraphs(n) if len(G.sinks()) == 1])
CPU times: user 40 ms, sys: 0 ns, total: 40 ms
Wall time: 46.2 ms
6
sage: %time len([H for H in digraphs(n,lambda G: len(G.sinks()) >= 1) if len(H.sinks()) == 1])
CPU times: user 36 ms, sys: 0 ns, total: 36 ms
Wall time: 31.4 ms
6
sage: n = 4
sage: %time len([G for G in digraphs(n) if len(G.sinks()) == 1])
CPU times: user 1.23 s, sys: 28 ms, total: 1.26 s
Wall time: 1.22 s
70
sage: %time len([H for H in digraphs(n,lambda G: len(G.sinks()) >= 1) if len(H.sinks()) == 1])
CPU times: user 732 ms, sys: 28 ms, total: 760 ms
Wall time: 690 ms
70
sage: n = 5
sage: %time len([G for G in digraphs(n) if len(G.sinks()) == 1])
CPU times: user 1min 38s, sys: 52 ms, total: 1min 38s
Wall time: 1min 38s
2340
sage: %time len([H for H in digraphs(n,lambda G: len(G.sinks()) >= 1 ...</code></pre><span class="expander"> <a>(more)</a></span></div>http://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/?comment=33388#post-id-33388Thanks for the clear explanation & the helpful link. Back to the algorithm drawing board.Thu, 12 May 2016 11:18:04 -0500http://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/?comment=33388#post-id-33388