//==========================================================================
//
// pq_node.h
//
//==========================================================================
// $Id: pq_node.h,v 1.11 2000/01/05 16:32:39 raitner Exp $
#ifndef PQ_NODE_H
#define PQ_NODE_H
#include <GTL/GTL.h>
#include <GTL/symlist.h>
#include <GTL/graph.h>
#include <list>
#include <iostream>
__GTL_BEGIN_NAMESPACE
class pq_tree;
class p_node;
class q_node;
class pq_leaf;
class direction_indicator;
/**
* @internal
*/
class GTL_EXTERN pq_node
{
protected:
typedef symlist<pq_node*>::iterator iterator;
enum PQ_KIND {P_NODE, Q_NODE, LEAF, DIR};
enum PQ_MARK {UNMARKED, QUEUED, BLOCKED, UNBLOCKED};
pq_node (node n_, int id_) :
pert_children (0), pert_leaves (0), mark (UNMARKED),
n (n_), id (id_) { }
virtual ~pq_node ();
// Used to identify nodes
virtual PQ_KIND kind () const = 0;
// called whenever a son is known to be partial during reduction phase
virtual void partial (iterator) { };
// called whenever a son is known to be full during reduction phase
virtual void full (iterator) { };
// Used to write a description of this node into a GML file.
virtual void write (ostream&, int) = 0;
// reset node for next reduction
virtual void clear ()
{ mark = UNMARKED; pert_leaves = 0; pert_children = 0; }
// type-casts
virtual p_node* P() = 0;
virtual q_node* Q() = 0;
virtual direction_indicator* D() = 0;
virtual pq_leaf* L() = 0;
//
// Data used in reductions
//
// number of pertinent children; is calculated during bubble-up phase
// and gets decreased whenever a pertinent child is matched in reduction
// phase, such that it can be assured that this node is matched _after_ all
// its pertinent children were correctly matched.
int pert_children;
// number of pertinent leaves in the subtree rooted at this node; is
// calculated in the reduction phase and is used to determine the root
// of the pertinent subtree, i.e. the last node for template matchings.
int pert_leaves;
// For Q-nodes it is not acceptable to maintain father pointers for
// _all_ sons (cf. Booth, Luecker); fortunatly this isn't neccessary and
// the father pointer is only valid if is_endmost is true. For the sons of a
// Q-node is_endmost is only true for the first and the last son. For the
// sons of P-nodes ths flag is always true.
bool is_endmost;
// The main operations on PQ-trees are performed bottom up so each node should
// know its father; Because of complexity issuses this isn't always possible and
// thus father is valid iff is_endmost is true.
pq_node* father;
// Describes the role this node plays in the reduction at the moment; four states
// are possible:
//
// (1) UNMARKED: node wasn't touched so far.
// (2) BLOCKED: during bubble-up phase this node got queued, but as yet it
// was not possible to get a valid father pointer.
// (3) UNBLOCKED: node was touched during bubble-up and it either had a valid
// father pointer or one could be borrowed from one of its siblings.
// (4) QUEUED: node has been put into the queue.
PQ_MARK mark;
// list of sons.
symlist<pq_node*> sons;
// position in the list of sons of node's father.
iterator pos;
// position in the list of nodes to be cleared in reset. Each node touched in
// bubble-up phase is stored in the list of nodes to be cleared. As they get
// matched in the reduction phase they are cleared and deleted from this list.
// But even if the reduction is successful not all nodes touched in the first
// phase really get matched.
list<pq_node*>::iterator lpos;
//
// Application specific data (should become template parameter)
//
node n;
int id;
node up;
int up_id;
//
// Friends
//
friend class q_node;
friend class p_node;
friend class pq_tree;
friend class planarity;
GTL_EXTERN friend ostream& operator<< (ostream&, const pq_tree&);
};
/**
* @internal
*/
class GTL_EXTERN p_node : public pq_node
{
private:
p_node (node, int);
p_node (node, int, symlist<pq_node*>&);
//
// pq_node interface
//
void partial (iterator);
void full (iterator);
PQ_KIND kind () const
{ return P_NODE; }
void write (ostream&, int);
void clear ();
// type-casts
p_node* P()
{ return this; }
q_node* Q()
{ assert (false); return 0; }
direction_indicator* D()
{ assert (false); return 0; }
pq_leaf* L()
{ assert (false); return 0; }
//
// Additional
//
// whenever a child is known to be full, it is moved from the list of
// sons to this list.
symlist<pq_node*> full_sons;
// whenever a child is known to be partial, it is moved from the list of
// sons to this list.
symlist<pq_node*> partial_sons;
// number of children
int child_count;
// number of partial children
int partial_count;
// number of full children
int full_count;
//
// Friends
//
friend class planarity;
friend class pq_tree;
};
/**
* @internal
*/
class GTL_EXTERN q_node : public pq_node
{
private:
q_node (node, int);
//
// pq_node interface
//
void partial (iterator);
void full (iterator);
PQ_KIND kind () const
{ return Q_NODE; }
void write (ostream&, int);
void clear ();
// type-casts
p_node* P()
{ assert (false); return 0; }
q_node* Q()
{ return this; }
direction_indicator* D()
{ assert (false); return 0; }
pq_leaf* L()
{ assert (false); return 0; }
//
// Additional
//
// determines pert_begin and pert_end the first time a full or partial
// child is found.
void pertinent (iterator);
// in Q2 and Q3 matchings the sons of partial children have to be merged
// into the list of sons of this node at the partial node's position
q_node* merge (iterator);
// deprecated !!
void turn ();
// first son full or partial viewed from the beginning of the list of sons
iterator pert_begin;
// last son full or partial; usually this is the last son.
iterator pert_end;
// positions of the partial nodes among the sons. Normally only two partial
// sons are allowed, but the third one is needed in planarity testing.
iterator partial_pos[3];
// true when all the pertinent children are consecutive; íf false pert_begin
// lies in one block of pertinent children and pert_end in another, such that
// --pert_end is empty and between the two blocks.
bool pert_cons;
// number of partial children
int partial_count;
// number of full children
int full_count;
//
// Friends
//
friend class planarity;
friend class pq_tree;
};
/**
* @internal
*/
class GTL_EXTERN pq_leaf : public pq_node
{
public:
pq_leaf (int, int, edge, node);
private:
PQ_KIND kind () const
{ return LEAF; }
void write (ostream&, int);
// type-casts
p_node* P()
{ assert (false); return 0; }
q_node* Q()
{ assert (false); return 0; }
direction_indicator* D()
{ assert (false); return 0; }
pq_leaf* L()
{ return this; }
//
// Additional
//
int other_id;
edge e;
//
// Friends
//
friend class planarity;
friend class pq_tree;
};
/**
* @internal
*/
class direction_indicator : public pq_node
{
private:
direction_indicator (node n_, int id_) : pq_node (n_, id_) { };
//
// pq_node interface
//
PQ_KIND kind () const
{ return DIR; }
void write (ostream& os, int);
// type-casts
p_node* P()
{ assert (false); return 0; }
q_node* Q()
{ assert (false); return 0; }
direction_indicator* D()
{ return this; }
pq_leaf* L()
{ assert (false); return 0; }
//
// Additional
//
bool direction;
//
// Friends
//
friend class planarity;
friend class pq_tree;
};
__GTL_END_NAMESPACE
#endif
//--------------------------------------------------------------------------
// end of file
//--------------------------------------------------------------------------
Documentation generated by raitner@hyperion on Tue Mar 7 09:40:04 CET 2000
|
Kdoc |