OKlibrary  0.2.1.6
Representations.hpp File Reference

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:
1. First we compute a standardised version T' of the tree T.
2. From T' we compute the representation P as a polar hypergraph via stdg2phg (see "Polar hypergraphs" in ComputerAlgebra/Hypergraphs/Lisp/plans/Basics.hpp).
3. From P we obtain the array d of vertex degrees from T'.
4. Additionally we have an integer array E, where E(v)=1 means that vertex v (of T') has been eliminated (E is 0-initialised).
5. Scanning through d, we compute the set M of monovalent vertices in T'.
6. Now the loop:
1. Using "first_element", we obtain the smallest element x of M.
2. Via P and E we find the current (single) neighbour y of x.
3. y is appended to the code pc (initially the empty list).
4. E(x) : 1, and x is removed from M.
5. 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 data-structure for M, this looks like a natural representation of the natural efficient implementation.
1. 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.
2. 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).
3. 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.