Changes between Version 2 and Version 3 of Ticket #6637, comment 4


Ignore:
Timestamp:
04/09/14 07:44:20 (7 years ago)
Author:
slabbe
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #6637, comment 4

    v2 v3  
    77Now
    88
    9  - Let {{{gens}}} be a subset of X.
     9 - Let {{{seeds}}} be a subset of X.
    1010 - Let {{{succ}}} be a callable python object {{{X -> 2^X}}} such that xRy if and only if y is in `succ(x)`.
    1111
    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 set
     12We are interested in the subset S of X that can be generated from the {{{seeds}}} using the {{{succ}}} recursively. More precisely in the set
    1313
    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}}}}.
    1515
    1616Moreover, we are interested in the enumeration of S itself and we consider depth-first and breadth-first as different and both usefull.
     
    2222'''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}}} (depth-first search) and (curiously) in {{{TransitiveIdealGraded}}} (breadth-first search) also.
    2323
    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}}}.
    2525
    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),
    2727
    2828 if (x1 R x2 R ... R xn) and (y1 R y2 R ... R ym) and (xn=ym), then (n=m).