PQ-Trees. More...
#include <GTL/pq_tree.h>
[public]
Creates empty pq_tree
[public]
Creates PQ-tree consiting of a single P-node whose children are the leaves
given in list le
.
le | list of children |
id |
st-number of n |
n | node in the graph to which the P-node refers |
[public]
Deletes PQ-tree.
[public]
Applies so called template matchings to the tree until either all leaves
labeled with id
are consecutive in all equivalent trees or until
it is recognized that this can't be achieved.
This operation is guaranteed to perform in O(PPT), where PPT is the
size of the so called pruned pertinent subtree, which can be
constructed, by cutting away all the parts of the pq_tree, that do
not contain a leaf labeled with id
.
leaves | list of full leaves |
[public]
Replaces all the pertinent parts of the pq_tree after a (successful)
reduction by a new P-node, whose children are given in le
.
The edges (in the graph), represented by the leaves are stored in left
to right order in em[n]
; they form (up to reversion) the
so called upward-embedding. A direction indicator representing the
direction in which the leaves were scanned is added to the sons of the
root of the pertinent subtree (if neccessary). All direction indicators
in the pertinent subtree are stored in dirs
.
le | list of children |
dirs | direction indicators in pertinent subtree |
em | planar embedding |
id |
st-number of n |
n | node in the graph to which the new P-node refers |
[public]
Scans whole tree from left to right and stores edges (in the graph)
represented by the leaves in em
. All direction indicators
in the tree are stored in dirs
. This is used in planarity
test to get the upward embedding of the last node, because no reduction
is needed in this case since all leaves are labeled with the same number.
dirs | direction indicators in tree |
em | planar embedding |
[public]
After a (successful) reduction reset
has to be called in
order to prepare the tree for the next reduction.
[public]
Returns the (PQ-) node to which none of the template matchings were applicable.
[public]
Returns true iff fail is the root of the pertinent subtree.
[public]
Checks the structure of the tree. Note: use this only for debugging since it scans the whole tree, which isn't acceptable in terms of performance in most cases.
Kdoc |