# Using a lambda expression in digraphs fails for len(G.sinks())?

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?

edit retag close merge delete

Sort by » oldest newest most voted

If 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/2419...

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

Thanks for the clear explanation & the helpful link. Back to the algorithm drawing board.

( 2016-05-12 11:18:04 -0500 )edit