include/GTL/pq_tree.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   pq_tree.h
0005 //
0006 //==========================================================================
0007 // $Id: pq_tree.h,v 1.20 2008/02/03 18:17:08 chris Exp $
0008
0009 #ifndef PQ_TREE_H
0010 #define PQ_TREE_H
0011
0012 #include <GTL/GTL.h>
0013 #include <GTL/pq_node.h>
0014 #include <GTL/embedding.h>
0015 #include <GTL/debug.h>
0016
0017 #include <list>
0018 #include <iostream>
0019
0020 __GTL_BEGIN_NAMESPACE
0021
0022 /**
0023  * $Date: 2008/02/03 18:17:08 $
0024  * $Revision: 1.20 $
0025  *
0026  * @brief PQ-Trees.
0027  *
0028  */
0029 class GTL_EXTERN pq_tree
0030 {
0031 public:
0032     /**
0033      * @internal
0034      */
0035     typedef symlist<pq_node*> sons_list;
0036
0037     /**
0038      * @internal
0039      */
0040     typedef symlist<pq_node*>::iterator sons_iterator;
0041
0042     /**
0043      * @brief Creates empty pq_tree.
0044      */
0045     pq_tree() : root(0), pert_root(0), pseudo(0), fail(0)
0046     {
0047     }
0048
0049     /**
0050      * @brief Creates a PQ-tree consisting of a single P-node whose
0051      * whose children are the leaves given in list @p le.
0052      *
0053      * @param id st-number of @p n
0054      * @param n node in the %graph to which the P-node refers
0055      * @param le list of children
0056      */
0057     pq_tree(int id, node n, const list<pq_leaf*>& le);
0058
0059     /**
0060      * @brief Deletes PQ-tree.
0061      */
0062     ~pq_tree();
0063
0064     /**
0065      * @brief Applies so called template matchings to the tree until either
0066      * all leaves labeled with @c id are consecutive in all equivalent
0067      * trees or until it is recognized that this can't be achieved.
0068      *
0069      * This operation is guaranteed to perform in O(PPT), where
0070      * PPT is the size of the so called @em pruned @em pertinent
0071      * @em subtree, which can be constructed, by cutting away all
0072      * the parts of the PQ-tree, that do not contain a leaf
0073      * labeled with @c id.
0074      *
0075      * @param leaves list of full leaves
0076      *
0077      * @retval true if tree was successfully reduced
0078      * @retval false if reduction failed
0079      */
0080     bool reduce(list<pq_leaf*>& leaves);
0081
0082     /**
0083      * @brief Replaces all the pertinent parts of the PQ-tree after a
0084      * (successful) reduction by a new P-node, whose children are given in
0085      * @p le.
0086      *
0087      * The edges (in the %graph), represented by the leaves are stored in
0088      * left to right order in @c em[n] They form (up to reversion)
0089      * the so called upward-embedding. A direction indicator representing
0090      * the direction in which the leaves were scanned is added to the sons
0091      * of the root of the pertinent subtree (if neccessary). All direction
0092      * indicators in the pertinent subtree are stored in @p dirs.
0093      *
0094      * @param id st-number of @p n
0095      * @param n node in the %graph to which the new P-node refers
0096      * @param le list of children
0097      * @param em planar embedding
0098      * @param dirs direction indicators in pertinent subtree
0099      */
0100     void replace_pert(int id,
0101               node n,
0102               const list<pq_leaf*>& le,
0103               planar_embedding* em = 0,
0104               list<direction_indicator>* dirs = 0);
0105
0106     /**
0107      * @brief Scans whole tree from left to right and stores edges (in the
0108      * %graph) represented by the leaves in @p em.
0109      *
0110      * All direction indicators in the tree are stored in @p
0111      * dirs. This is used in %planarity test to get the upward
0112      * %embedding of the last node, because no reduction is
0113      * needed in this case since all leaves are labeled with the
0114      * same number.
0115      *
0116      * @param em planar embedding
0117      * @param dirs direction indicators in tree
0118      */
0119     void get_frontier (planar_embedding& em, list<direction_indicator>& dirs);
0120
0121     /**
0122      * @brief After a (successful) reduction @c reset has to be called in
0123      * order to prepare the tree for the next reduction.
0124      */
0125     void reset ();
0126
0127     /**
0128      * @brief Returns the (PQ-) node to which none of the
0129      * template matchings were applicable.
0130      *
0131      * @return PQ-node at which the reduction failed
0132      */
0133     pq_node* get_fail()
0134     {
0135     return fail;
0136     }
0137
0138     /**
0139      * @brief Returns true iff fail is the root of the
0140      * pertinent subtree.
0141      *
0142      * @retval true iff reduction failed at the root of the
0143      *         pertinent subtree.
0144      */
0145     bool is_fail_root()
0146     {
0147     return failed_at_root;
0148     }
0149
0150     /**
0151      * @brief Remove a direction indicator among sons of a Q-node.
0152      * Needed for computation of the obstruction set.
0153      *
0154      * @param q_fail the Q-node on which the reduction failed
0155      * @param the position of the direction indicator among the sons
0156      *
0157      * @retval next valid sons iterator
0158      */
0159     sons_iterator remove_dir_ind(q_node* q_fail, sons_iterator s_it);
0160
0161     /**
0162      * @brief Checks the structure of the tree.
0163      *
0164      * @note Use this only for debugging since it scans the whole tree,
0165      * which isn't acceptable in terms of performance in most cases.
0166      *
0167      * @retval true iff tree passes checks
0168      */
0169     bool integrity_check () const;
0170
0171 //    p_node* insert_P (pq_node*, sons_list&);
0172
0173 //    q_node* insert_Q (pq_node*, sons_list&);
0174
0175 //    pq_leaf* insert_leaf (pq_node*);
0176
0177 //    void insert (pq_node*, pq_node*);
0178 private:
0179     /**
0180      * @internal
0181      * Tries to give all the nodes in the pertinent subtree the right father
0182      * pointer. If either all nodes in the pertinent subtree recieved a
0183      * valid father pointer or there was excactly one block of inner nodes
0184      * just below the root of the pertinent subtree, the result is true. If
0185      * @c bubble_up returns false a reduction isn't possible.
0186      *
0187      * @param leaves list of full leaves
0188      *
0189      * @retval true iff bubble-up succeeded
0190      */
0191     bool bubble_up (list<pq_leaf*>& leaves);
0192
0193     /**
0194      * @internal
0195      * Scans the subtree rooted at @p p and stores edges (in the %graph)
0196      * represented by the leaves in @p em. All direction indicators in the
0197      * subtree are stored in @p dirs.
0198      *
0199      * @param p root of subtree
0200      * @param em planar embedding
0201      * @param dirs direction indicators in subtree
0202      */
0203     void dfs(pq_node* p,
0204          planar_embedding& em,
0205          list<direction_indicator>& dirs);
0206
0207     /**
0208      * @internal
0209      * Test whether one of the predecessors of @p le has mark @c BLOCKED.
0210      * Used when bubble-up failed to determine a minimum subtree, whose root
0211      * has inner pertinent children. Minimum in this regard means that no
0212      * descendant of the subtree's root has @c BLOCKED children.
0213      *
0214      * @param le (PQ-)node
0215      *
0216      * @return @c BLOCKED node or @c 0
0217      */
0218     pq_node* leads_to_blocked(pq_node* le);
0219
0220
0221     /**
0222      * @internal
0223      * Tests wheter @p le leads to @p other, i.e. if  @p other is a
0224      * predecessor of @p le. Used to limit the leaves for reduction in case
0225      * that bubble-up failed to the leaves in the minimum subtree, whose
0226      * root has inner pertinent children.
0227      *
0228      * @param le node to be tested
0229      * @param other root of subtree
0230      *
0231      * @retval true iff @p le is in subtree rooted at @p other
0232      */
0233     bool leads_to(pq_node* le, pq_node* other);
0234
0235
0236     /**
0237      * @internal
0238      * In case bubble-up failed a (PQ-)node has to be found which has inner
0239      * children pertinent such that no node in its subtree has inner
0240      * children pertinet. Template matchings then are only performed in this
0241      * subtree.
0242      *
0243      * @param leaves list of full leaves
0244      *
0245      * @return root of the minimum subtree
0246      */
0247     pq_node* where_bubble_up_failed(list<pq_leaf*>& leaves);
0248
0249
0250     /**
0251      * @internal
0252      * Tests whether some descendants of @p n are @c BLOCKED.
0253      *
0254      * @param n root for subtree to be checked
0255      *
0256      * @return (PQ-) @c BLOCKED node or @c 0
0257      */
0258     pq_node* blocked_in_subtree(pq_node* n);
0259
0260
0261     //
0262     // Template Matchings
0263     //
0264
0265     //---------------------------------------------------------- P-Templates
0266
0267     /**
0268      * @internal
0269      * Template P1.
0270      */
0271     bool P1 (p_node* x, bool);
0272
0273     /**
0274      * @internal
0275      * Template P2.
0276      */
0277     bool P2 (p_node* x);
0278
0279     /**
0280      * @internal
0281      * Template P3.
0282      */
0283     bool P3 (p_node* x);
0284
0285     /**
0286      * @internal
0287      * Template P4.
0288      */
0289     bool P4 (p_node* x);
0290
0291     /**
0292      * @internal
0293      * Template P5.
0294      */
0295     bool P5 (p_node* x);
0296
0297     /**
0298      * @internal
0299      * Template P6.
0300      */
0301     bool P6 (p_node* x);
0302
0303     //---------------------------------------------------------- Q-Templates
0304
0305     /**
0306      * @internal
0307      * Template Q1.
0308      */
0309     bool Q1 (q_node* x, bool);
0310
0311     /**
0312      * @internal
0313      * Template Q2.
0314      */
0315     bool Q2 (q_node* x, bool);
0316
0317     /**
0318      * @internal
0319      * Template Q3.
0320      */
0321     bool Q3 (q_node* x);
0322
0323
0324     //
0325     // Data
0326     //
0327
0328     /**
0329      * @internal
0330      * List of (PQ-) nodes to be cleared if the reduction stopped now.
0331      */
0332     list<pq_node*> clear_me;
0333
0334     /**
0335      * @internal
0336      * Root of tree.
0337      */
0338     pq_node* root;
0339
0340     /**
0341      * @internal
0342      * Root of pertinent subtree; defined after succesful reduction.
0343      */
0344     pq_node* pert_root;
0345
0346     /**
0347      * @internal
0348      * In some cases the root of the pertinent subtree might not be known,
0349      * because it is a Q-node and all its pertinent children are inner. In
0350      * this case for the time of reduction an pseudo node is created as root
0351      * of the pertinent subtree, which gets only the pertinent children as
0352      * sons.
0353      */
0354     q_node* pseudo;
0355
0356     /**
0357      * @internal
0358      * (PQ-) node for which the reduction failed.
0359      */
0360     pq_node* fail;
0361
0362     /**
0363      * @internal
0364      * @c true iff reduction failed at the root of the pertinent subtree.
0365      */
0366     bool failed_at_root;
0367
0368     /**
0369      * @internal
0370      * Number of pertinent leaves for the current reduction; defined after
0371      * bubble-up.
0372      */
0373     int pert_leaves_count;
0374
0375     //
0376     // Friends
0377     //
0378
0379     /**
0380      * @internal
0381      * Allow operator<< private access.
0382      */
0383     GTL_EXTERN friend ostream& operator<< (ostream&, const pq_tree&);
0384 };
0385
0386 __GTL_END_NAMESPACE
0387
0388 #endif
0389
0390 //--------------------------------------------------------------------------
0391 //   end of file
0392 //--------------------------------------------------------------------------