Changes between Version 2 and Version 3 of Ticket #6637, comment 4
 Timestamp:
 04/09/14 07:44:20 (6 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #6637, comment 4
v2 v3 7 7 Now 8 8 9  Let {{{ gens}}} be a subset of X.9  Let {{{seeds}}} be a subset of X. 10 10  Let {{{succ}}} be a callable python object {{{X > 2^X}}} such that xRy if and only if y is in `succ(x)`. 11 11 12 We are interested in the subset S of X that can be generated from the {{{ gens}}} using the {{{succ}}} recursively. More precisely in the set12 We are interested in the subset S of X that can be generated from the {{{seeds}}} using the {{{succ}}} recursively. More precisely in the set 13 13 14 S = {y : x = x1 R x2 R x3 R ... R xn = y and x in {{{ gens}}}}.14 S = {y : x = x1 R x2 R x3 R ... R xn = y and x in {{{seeds}}}}. 15 15 16 16 Moreover, we are interested in the enumeration of S itself and we consider depthfirst and breadthfirst as different and both usefull. … … 22 22 '''1. We do not know anything more about the relation.''' We need to save in memory all the {{{known}}} objects to avoid duplicates. This is what is currently done in {{{TransitiveIdeal}}} (depthfirst search) and (curiously) in {{{TransitiveIdealGraded}}} (breadthfirst search) also. 23 23 24 '''2. The directed graph S is a forest with given {{{ gens}}}.''' Equivalently, one may say that S do not contain cycle (oriented or not). This is what is currently done in {{{SearchForest}}}.24 '''2. The directed graph S is a forest with given {{{seeds}}}.''' Equivalently, one may say that S do not contain cycle (oriented or not). This is what is currently done in {{{SearchForest}}}. 25 25 26 '''3. The relation is graded.''' By graded here I mean what I thought {{{TransitiveIdealGraded}}} was doing until I look more carefully at the doc and the code. More seriously, by graded I mean the following : for all (x1 in gens) and (y1 in gens),26 '''3. The relation is graded.''' By graded here I mean what I thought {{{TransitiveIdealGraded}}} was doing until I look more carefully at the doc and the code. More seriously, by graded I mean the following : for all (x1 in seeds) and (y1 in seeds), 27 27 28 28 if (x1 R x2 R ... R xn) and (y1 R y2 R ... R ym) and (xn=ym), then (n=m).