#6637: standardize the interface to TransitiveIdeal and friends
-----------------------------------------------------------------+----------
Reporter: nthiery |
Owner: mhansen
Type: enhancement |
Status: new
Priority: major |
Milestone: sage-5.7
Component: combinatorics |
Resolution:
Keywords: backtrack, enumerated set, transitive closure | Work
issues:
Report Upstream: N/A |
Reviewers:
Authors: | Merged
in:
Dependencies: |
Stopgaps:
-----------------------------------------------------------------+----------
Comment (by slabbe):
In a tentative to find good choices for name and so on, here is how I see
this.
- Let X be a set.
- Let R be a binary relation on X, that is R is a subset of the cartesian
product of X times X.
- Denote by xRy if x is R-related to y.
Now
- Let {{{roots}}} be a subset of X.
- Let {{{relation}}} be a callable python object {{{X -> 2^X}}} such that
xRy if and only if y is in relation(x).
We are interested in the subset S of X that can be generated from the
{{{roots}}} using the {{{relation}}} recursively. More precisely in the
set
S = {y : x = x1 R x2 R x3 R ... R xn = y and x in {{{roots}}}}.
Moreover, we are interested in the enumeration of S itself and we consider
depth-first and breadth-first as different and both usefull.
Such a relation G = (X,R) can be seen as a directed graph. I think this
remark is useful as it may provide some vocabulary. Indeed the set S is
the connected components of the roots in the digraph G.
I see some different cases :
'''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
{{{TransitiveIdealGraded}}} (breadth-first search).
'''2. The directed graph S is a forest with given {{{roots}}}.'''
Equivalently, one may say that S do not contain cycle (oriented or not).
This is what is currently done in {{{SearchForest}}}.
'''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 roots) and (y1 in roots),
if (x1 R x2 R ... R xn) and (y1 R y2 R ... R ym) and (xn=ym), then (n=m).
The relation is graded if all path from the origin to an element have the
same length. In this case, we only need to save in memory the current
level.
'''4. The relation is symmetric.''' If the relation is symmetric, we only
need to keep in memory the last two level of depth. This is what I needed
and coded this week. And this is why I started to look more carefully at
the code in {{{sage/combinat/backtrack.py}}}...
That is it for now!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6637#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
