Plans regarding the creation and usage of tree representations.
More...
Go to the source code of this file.
Detailed Description
Plans regarding the creation and usage of tree representations.
 Todo:
 tree2pruefercode_og

This function is very slow.

We need also a more efficient version. The basic ideas are as follows:

First we compute a standardised version T' of the tree T.

From T' we compute the representation P as a polar hypergraph via stdg2phg (see "Polar hypergraphs" in ComputerAlgebra/Hypergraphs/Lisp/plans/Basics.hpp).

From P we obtain the array d of vertex degrees from T'.

Additionally we have an integer array E, where E(v)=1 means that vertex v (of T') has been eliminated (E is 0initialised).

Scanning through d, we compute the set M of monovalent vertices in T'.

Now the loop:

Using "first_element", we obtain the smallest element x of M.

Via P and E we find the current (single) neighbour y of x.

y is appended to the code pc (initially the empty list).

E(x) : 1, and x is removed from M.

The degree of y in d is reduced by one, and if the degree of y becomes 1, then y is added to M.


Except of not using a dedicated datastructure for M, this looks like a natural representation of the natural efficient implementation.

The main imported datastructure (and "point of view") is given by P; d is naturally connected to it, and it doesn't seem worth the effort to have some special function for computing d from P.

The use of a priority queue for M is indicated by using "first_element" (which is also needed, since "first" is not guaranteed to work, and should not be used).

There is no need to update P, but instead we use E: This just performs the minimal work (nothing is repeated in this way).

Later we might implement it also using Boost::Graphs.

Then perhaps the old version is renamed to "tree2pruefercode_bydef_og".
Definition in file Representations.hpp.