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.

  • 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.