search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.41k stars 475 forks source link

Implement unordered trees #15612

Open darijgr opened 10 years ago

darijgr commented 10 years ago

Of course, the actual implementation will have to wait for #14498 being reviewed (hint, hint), but I guess it won't hurt to bring up the matter now.

I'd really like to see unordered (=non-planar) trees of various varieties (binary/arbitrary, labelled/unlabelled) being implemented in Sage. ("Unordered" means that the children of a vertex form a multiset, not a list.) I'm wondering if it is possible to implement the labelled kind as a finite set with a Maybe-endomorphism (i. e., a partial map from the set to itself) while still satisfying the AbstractLabelledTree interface, because I guess this will be a lot faster than following the recursive paradigm we currently have.

CC: @sagetrac-sage-combinat @nthiery @hivert @sagetrac-elixyre @fchapoton

Component: combinatorics

Keywords: trees

Issue created by migration from https://trac.sagemath.org/ticket/15612

darijgr commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 Of course, the actual implementation will have to wait for #14498 being reviewed (hint, hint), but I guess it won't hurt to bring up the matter now.

-I'd really like to see unordered (=non-planar) trees of various varieties (binary/arbitrary, labelled/unlabelled) being implemented in Sage. ("Unordered" means that the children of a vertex form a multiset, not a list.) I'm wondering if it is possible to implement the labelled kind as a finite set with a Maybe-endomorphism (i. e., a partial map from the set to itself), because I guess this will be a lot faster than following the recursive paradigm we currently have.
+I'd really like to see unordered (=non-planar) trees of various varieties (binary/arbitrary, labelled/unlabelled) being implemented in Sage. ("Unordered" means that the children of a vertex form a multiset, not a list.) I'm wondering if it is possible to implement the labelled kind as a finite set with a Maybe-endomorphism (i. e., a partial map from the set to itself) while still satisfying the AbstractLabelledTree implementation, because I guess this will be a lot faster than following the recursive paradigm we currently have.
darijgr commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 Of course, the actual implementation will have to wait for #14498 being reviewed (hint, hint), but I guess it won't hurt to bring up the matter now.

-I'd really like to see unordered (=non-planar) trees of various varieties (binary/arbitrary, labelled/unlabelled) being implemented in Sage. ("Unordered" means that the children of a vertex form a multiset, not a list.) I'm wondering if it is possible to implement the labelled kind as a finite set with a Maybe-endomorphism (i. e., a partial map from the set to itself) while still satisfying the AbstractLabelledTree implementation, because I guess this will be a lot faster than following the recursive paradigm we currently have.
+I'd really like to see unordered (=non-planar) trees of various varieties (binary/arbitrary, labelled/unlabelled) being implemented in Sage. ("Unordered" means that the children of a vertex form a multiset, not a list.) I'm wondering if it is possible to implement the labelled kind as a finite set with a Maybe-endomorphism (i. e., a partial map from the set to itself) while still satisfying the AbstractLabelledTree interface, because I guess this will be a lot faster than following the recursive paradigm we currently have.
fchapoton commented 10 years ago
comment:5

The way is long and not easy:

First #10963 then #10194 then #11529

It may be possible to bypass #10963 though. As far as I remember, #10194 does not really depend on it, and commuting should be easy.

darijgr commented 10 years ago
comment:6

Oh, I didn't know of #11529. Looks like things are on a good way forward then, at least once the latest memory leak from #10963 is plugged.

fchapoton commented 9 years ago
comment:10

or should it be duplicate ?

darijgr commented 9 years ago
comment:11

There is something that I'm still kind-of missing: The labelled rooted trees on {1, 2, ..., n}. We don't have them, do we? They can be implemented as lists (g(1), g(2), ..., g(n)), where g(i) is the father of i if such a father exists and 0 else. They are a basis for a Hopf algebra, and I still have some ancient code that defines this Hopf algebra (although I'm not sure about the quality of that code). What could be tricky: Can we make them inherit from LabelledRootedTree, or only convert to such?

slel commented 3 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 Of course, the actual implementation will have to wait for #14498 being reviewed (hint, hint), but I guess it won't hurt to bring up the matter now.

-I'd really like to see unordered (=non-planar) trees of various varieties (binary/arbitrary, labelled/unlabelled) being implemented in Sage. ("Unordered" means that the children of a vertex form a multiset, not a list.) I'm wondering if it is possible to implement the labelled kind as a finite set with a Maybe-endomorphism (i. e., a partial map from the set to itself) while still satisfying the AbstractLabelledTree interface, because I guess this will be a lot faster than following the recursive paradigm we currently have.
+I'd really like to see unordered (=non-planar) trees of various varieties (binary/arbitrary, labelled/unlabelled) being implemented in Sage. ("Unordered" means that the children of a vertex form a multiset, not a list.) I'm wondering if it is possible to implement the labelled kind as a finite set with a Maybe-endomorphism (i. e., a partial map from the set to itself) while still satisfying the `AbstractLabelledTree` interface, because I guess this will be a lot faster than following the recursive paradigm we currently have.