Revision history [back]
 | 1 | initial version |
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".
| | 2 | No.2 Revision |
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/24199/why-the-function-graphs-cant-generate-graphs/?answer=24201#post-id-24201
| | 3 | No.3 Revision |
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 (answer of the 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
