//==========================================================================
//
// pq_tree.h
//
//==========================================================================
// $Id: pq_tree.h,v 1.12 2000/01/05 16:32:40 raitner Exp $
#ifndef PQ_TREE_H
#define PQ_TREE_H
#include <GTL/GTL.h>
#include <GTL/pq_node.h>
#include <GTL/embedding.h>
#include <GTL/debug.h>
#include <list>
#include <iostream>
__GTL_BEGIN_NAMESPACE
/**
* @short PQ-Trees.
*/
class GTL_EXTERN pq_tree
{
public:
/**
* @internal
*/
typedef symlist<pq_node*> sons_list;
/**
* @internal
*/
typedef symlist<pq_node*>::iterator sons_iterator;
/**
* Creates empty pq_tree
*/
pq_tree () : root (0) { };
/**
* Creates PQ-tree consiting of a single P-node whose children are the leaves
* given in list <code>le</code>.
*
* @param <code>id</code> st-number of <code>n</code>
* @param <code>n</code> node in the graph to which the P-node refers
* @param <code>le</code> list of children
*/
pq_tree (int id, node n, const list<pq_leaf*>& le);
/**
* Deletes PQ-tree.
*/
~pq_tree ();
/**
* Applies so called template matchings to the tree until either all leaves
* labeled with <code>id</code> are consecutive in all equivalent trees or until
* it is recognized that this can't be achieved.
* <p>
* 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 <code>id</code>.
*
* @param <code>leaves</code> list of full leaves
* @return true iff tree was successfully reduced
*/
bool reduce (list<pq_leaf*>& leaves);
/**
* Replaces all the pertinent parts of the pq_tree after a (successful)
* reduction by a new P-node, whose children are given in <code>le</code>.
* The edges (in the graph), represented by the leaves are stored in left
* to right order in <code>em[n]</code>; 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 <code>dirs</code>.
*
* @param <code>id</code> st-number of <code>n</code>
* @param <code>n</code> node in the graph to which the new P-node refers
* @param <code>le</code> list of children
* @param <code>em</code> planar embedding
* @param <code>dirs</code> direction indicators in pertinent subtree
*/
void replace_pert (
int id,
node n,
const list<pq_leaf*>& le,
planar_embedding* em = 0,
list<direction_indicator>* dirs = 0);
/**
* Scans whole tree from left to right and stores edges (in the graph)
* represented by the leaves in <code>em</code>. All direction indicators
* in the tree are stored in <code>dirs</code>. 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.
*
* @param <code>em</code> planar embedding
* @param <code>dirs</code> direction indicators in tree
*/
void get_frontier (planar_embedding& em, list<direction_indicator>& dirs);
/**
* After a (successful) reduction <code>reset</code> has to be called in
* order to prepare the tree for the next reduction.
*/
void reset ();
/**
* Returns the (PQ-) node to which none of the template matchings were
* applicable.
*
* @return (PQ-) node at which the reduction failed
*/
pq_node* get_fail ()
{ return fail; }
/**
* Returns true iff fail is the root of the pertinent subtree.
*
* @return true iff reduction failed at the root of the pertinent subtree.
*/
bool is_fail_root ()
{ return failed_at_root; }
/**
* Checks the structure of the tree. <em>Note:</em> use this only for debugging
* since it scans the whole tree, which isn't acceptable in terms of performance
* in most cases.
*
* @return true iff tree passes checks
*/
bool integrity_check () const;
// p_node* insert_P (pq_node*, sons_list&);
// q_node* insert_Q (pq_node*, sons_list&);
// pq_leaf* insert_leaf (pq_node*);
// void insert (pq_node*, pq_node*);
private:
/**
* Tries to give all the nodes in the pertinent subtree the right father
* pointer. If either all nodes in the pertinent subtree recieved a valid
* father pointer or there was excactly one block of inner nodes just below
* the root of the pertinent subtree, the result is true. If
* <code>bubble_up</code> returns false a reduction isn't possible.
*
* @param <code>leaves</code> list of full leaves
* @return true iff bubble-up succeeded.
*/
bool bubble_up (list<pq_leaf*>& leaves);
/**
* Scans the subtree rooted at <code>p</code> and stores edges (in the graph)
* represented by the leaves in <code>em</code>. All direction indicators
* in the subtree are stored in <code>dirs</code>
*
* @param <code>p</code> root of subtree
* @param <code>em</code> planar embedding
* @param <code>dirs</code> direction indicators in subtree
*/
void dfs (pq_node* p, planar_embedding& em, list<direction_indicator>& dirs);
/**
* Test whether one of the predecessors of <code>le</code> has mark BLOCKED.
* Used when bubble-up failed to determine a minimum subtree, whose root has
* inner pertinent children. Minimum in this regard means that no
* descendant of the subtree's root has BLOCKED children.
*
* @param <code>le</code> (PQ-) node
* @return BLOCKED node or 0
*/
pq_node* leads_to_blocked (pq_node* le);
/**
* Tests wheter <code>le</code> leads to <code>other</code>, i.e. if
* <code>other</code> is a predecessor of <code>le</code>. Used to limit the
* leaves for reduction in case that bubble-up failed to the leaves in the
* minimum subtree, whose root has inner pertinent children.
*
* @param <code>le</code> node to be tested
* @param <code>other</code> root of subtree
* @return true iff <code>le</code> is in subtree rooted at <code>other</code>
* @see
*/
bool leads_to (pq_node* le, pq_node* other);
/**
* In case bubble-up failed a (PQ-) node has to be found which has inner
* children pertinent such that no node in its subtree has inner children
* pertinet. Template matchings then are only performed in this subtree.
*
* @param <code>leaves</code> list of full leaves.
* @return root of the minimum subtree
*/
pq_node* where_bubble_up_failed (list<pq_leaf*>& leaves);
/**
* Tests whether some descendants of <code>n</code> are BLOCKED.
*
* @param <code>n</code> root for subtree to be checked
* @return (PQ-) BLOCKED node or 0
*/
pq_node* blocked_in_subtree (pq_node* n);
//
// Template Matchings
//
//----------------------------------------------------------- P-Templates
bool P1 (p_node* x, bool);
bool P2 (p_node* x);
bool P3 (p_node* x);
bool P4 (p_node* x);
bool P5 (p_node* x);
bool P6 (p_node* x);
//----------------------------------------------------------- Q-Templates
bool Q1 (q_node* x, bool);
bool Q2 (q_node* x, bool);
bool Q3 (q_node* x);
//
// Data
//
// list of (PQ-) nodes to be cleared if the reduction stopped now
list<pq_node*> clear_me;
// root of tree
pq_node* root;
// root of pertinent subtree; defined after succesful reduction
pq_node* pert_root;
// in some cases the root of the pertinent subtree might not be known,
// because it is a Q-node and all its pertinent children are inner. In this
// case for the time of reduction an pseudo node is created as root of the
// pertinent subtree, which gets only the pertinent children as sons
q_node* pseudo;
// (PQ-) node for which the reduction failed.
pq_node* fail;
// true iff reduction failed at the root of the pertinent subtree
bool failed_at_root;
// number of pertinent leaves for the current reduction; defined after bubble-up.
int pert_leaves_count;
//
// Friends
//
GTL_EXTERN friend ostream& operator<< (ostream&, const pq_tree&);
};
__GTL_END_NAMESPACE
#endif
//--------------------------------------------------------------------------
// end of file
//--------------------------------------------------------------------------
Documentation generated by raitner@hyperion on Tue Mar 7 09:40:04 CET 2000
|
Kdoc |