Ask Your Question
1

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

asked 2016-05-12 10:05:40 -0500

jim_snydergrant gravatar image

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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2016-05-12 10:56:56 -0500

tmonteil gravatar image

updated 2016-05-12 11:18:36 -0500

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)
edit flag offensive delete link more

Comments

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

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-05-12 10:05:40 -0500

Seen: 40 times

Last updated: May 12 '16