title
Graph Drawing Toolkit

An object-oriented C++ library for handling and drawing graphs
gdt::PQ_tree

gdt::PQ_tree< T > Class Template Reference

#include <rm3_PQ_tree.h>

Collaboration diagram for gdt::PQ_tree< T >:

Collaboration graph
[legend]

List of all members.

Public Member Functions

 PQ_tree ()
 PQ_tree (gdtlist< T > &input_leaves)
 ~PQ_tree ()
PQ_tree< T > & operator= (const PQ_tree< T > &t)
PQ_node get_root ()
int get_max_id ()
int get_number_of_nodes ()
void set_leaves (gdt::gdtlist< gdt::PQ_node_struct< T > * > list_leaves)
gdtlist< PQ_node > get_leaves ()
PQ_node find_leaf (T value)
void reset_tree ()
bool is_root (PQ_node node)
bool pnode_sorting (PQ_node node)
bool qnode_reversing (PQ_node node)
bool assign_parent_to_draw_graph (PQ_node node, int count)
void add_leaf (T value)
bool bubble (gdtlist< T > &S)
bool template_L1 (PQ_node node)
bool template_P1 (PQ_node node)
bool template_P2 (PQ_node node)
bool template_P3 (PQ_node node)
bool template_P4 (PQ_node node)
bool template_P5 (PQ_node node)
bool template_P6 (PQ_node node)
bool template_Q1 (PQ_node node)
bool template_Q2 (PQ_node node)
bool template_Q3 (PQ_node node)
bool make_empty ()
bool reduce (gdtlist< T > &S)
void freeze (PQ_tree_freezed< T > &freezed_tree)
undi_graph PQ_tree_into_undi_graph (std::string title)

Protected Member Functions

int generate_id ()

Detailed Description

template<class T>
class gdt::PQ_tree< T >

Global class PQ_tree.
A PQ_tree represents all the admissible permutations of a set of objects. A permutation is admissible if it respects a set of constraints.

Definition at line 220 of file rm3_PQ_tree.h.

Constructor & Destructor Documentation

template<class T>
gdt::PQ_tree< T >::PQ_tree (  )  [inline]

Empty constructor

Definition at line 932 of file rm3_PQ_tree.h.

References NULL.

template<class T>
gdt::PQ_tree< T >::PQ_tree ( gdt::gdtlist< T > &  input_leaves  )  [inline]

Constructor.

Definition at line 947 of file rm3_PQ_tree.h.

References gdt::PQ_node_struct< T >::child_count, forall, gdt::PQ_node_struct< T >::id, LEAF, gdt::PQ_node_struct< T >::parent, PNODE, gdt::PQ_node_struct< T >::type, and gdt::PQ_node_struct< T >::value.

template<class T>
gdt::PQ_tree< T >::~PQ_tree (  )  [inline]

Destructor. It deallocates the memory required by the PQ_tree object.

Definition at line 993 of file rm3_PQ_tree.h.

References NULL.

Member Function Documentation

template<class T>
int gdt::PQ_tree< T >::generate_id (  )  [inline, protected]

Definition at line 1079 of file rm3_PQ_tree.h.

template<class T>
gdt::PQ_tree< T > & gdt::PQ_tree< T >::operator= ( const PQ_tree< T > &  t  )  [inline]

Copy assignment operator. It clears the topology of the current PQ_tree class object, and makes it as a copy of tree "t".

Definition at line 1009 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, forall, gdt::PQ_node_struct< T >::full_children, gdt::PQ_node_struct< T >::id, LEAF, gdt::PQ_node_struct< T >::left_endmost, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, NULL, gdt::PQ_node_struct< T >::parent, gdt::PQ_node_struct< T >::partial_children, gdt::PQ_node_struct< T >::right_endmost, gdt::PQ_node_struct< T >::type, and gdt::PQ_node_struct< T >::value.

Here is the call graph for this function:

template<class T>
gdt::PQ_node_struct< T > * gdt::PQ_tree< T >::get_root (  )  [inline]

Returns the root

Definition at line 1102 of file rm3_PQ_tree.h.

template<class T>
int gdt::PQ_tree< T >::get_max_id (  )  [inline]

Returns the max_id

Definition at line 1112 of file rm3_PQ_tree.h.

template<class T>
int gdt::PQ_tree< T >::get_number_of_nodes (  )  [inline]

Returns the number of nodes

Definition at line 1122 of file rm3_PQ_tree.h.

template<class T>
void gdt::PQ_tree< T >::set_leaves ( gdt::gdtlist< gdt::PQ_node_struct< T > * >  list_leaves  )  [inline]

Sets the list of leaves

Definition at line 1133 of file rm3_PQ_tree.h.

template<class T>
gdt::gdtlist< gdt::PQ_node_struct< T > * > gdt::PQ_tree< T >::get_leaves (  )  [inline]

Returns the list of leaves

Definition at line 1145 of file rm3_PQ_tree.h.

template<class T>
gdt::PQ_node_struct< T > * gdt::PQ_tree< T >::find_leaf ( T  value  )  [inline]

Returns the leaf with the id as input

Definition at line 1155 of file rm3_PQ_tree.h.

template<class T>
void gdt::PQ_tree< T >::reset_tree (  )  [inline]

Resets the values of a tree in the constructor and after bubble.

Definition at line 1089 of file rm3_PQ_tree.h.

template<class T>
bool gdt::PQ_tree< T >::is_root ( PQ_node  node  )  [inline]

Returns true if the node is the root.

Definition at line 1167 of file rm3_PQ_tree.h.

template<class T>
bool gdt::PQ_tree< T >::pnode_sorting ( PQ_node  node  )  [inline]

Sorts the children full and empty of a PNODE.

Definition at line 1179 of file rm3_PQ_tree.h.

References EMPTY, forall, gdt::PQ_node_struct< T >::full_children, gdt::gdtlist< E >::head(), gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, gdt::PQ_node_struct< T >::partial_children, PNODE, gdt::gdtlist< E >::size(), gdt::gdtlist< E >::tail(), and gdt::PQ_node_struct< T >::type.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::qnode_reversing ( PQ_node  node  )  [inline]

Reverses a QNODE.

Definition at line 1265 of file rm3_PQ_tree.h.

References gdt::PQ_node_struct< T >::left_endmost, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, NULL, QNODE, gdt::PQ_node_struct< T >::right_endmost, and gdt::PQ_node_struct< T >::type.

template<class T>
bool gdt::PQ_tree< T >::assign_parent_to_draw_graph ( PQ_node  node,
int  count 
) [inline]

Assignes the true parent to a pseudonode child.

Definition at line 1292 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, forall, FULL, gdt::PQ_node_struct< T >::full_children, gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::link_right_side, NULL, gdt::PQ_node_struct< T >::parent, PARTIAL, and gdt::PQ_node_struct< T >::partial_children.

Here is the call graph for this function:

template<class T>
void gdt::PQ_tree< T >::add_leaf ( T  value  )  [inline]

Adds a given leaf to the tree

Definition at line 1330 of file rm3_PQ_tree.h.

References gdt::PQ_node_struct< T >::child_count, gdt::PQ_node_struct< T >::id, LEAF, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, NULL, gdt::PQ_node_struct< T >::parent, PNODE, gdt::PQ_node_struct< T >::type, and gdt::PQ_node_struct< T >::value.

template<class T>
bool gdt::PQ_tree< T >::bubble ( gdt::gdtlist< T > &  S  )  [inline]

First step for reduction of a PQ_tree. Returns false if a reducution does not exist.

Definition at line 1384 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), BLOCKED, gdt::PQ_node_struct< T >::child_count, gdt::gdtlist< E >::clear(), forall, gdt_error, gdt::PQ_node_struct< T >::id, gdt::PQ_node_struct< T >::is_endmost(), gdt::PQ_node_struct< T >::left_endmost, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, gdt::PQ_node_struct< T >::mark, NULL, gdt::PQ_node_struct< T >::parent, gdt::PQ_node_struct< T >::pertinent_child_count, PNODE, PSEUDONODE, QUEUED, gdt::PQ_node_struct< T >::right_endmost, gdt::gdtlist< E >::size(), gdt::gdtlist< E >::tail(), gdt::PQ_node_struct< T >::type, UNBLOCKED, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::template_L1 ( PQ_node  node  )  [inline]

A template in the reduce pass. Returns false if the template does not exist.

Definition at line 1541 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), FULL, gdt::PQ_node_struct< T >::full_children, gdt::PQ_node_struct< T >::label, LEAF, gdt::PQ_node_struct< T >::mark, gdt::PQ_node_struct< T >::parent, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, gdt::PQ_node_struct< T >::type, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::template_P1 ( PQ_node  node  )  [inline]

A template in the reduce pass. Returns false if the template does not exist.

Definition at line 1565 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, FULL, gdt::PQ_node_struct< T >::full_children, gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::mark, gdt::PQ_node_struct< T >::parent, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, PNODE, gdt::gdtlist< E >::size(), gdt::PQ_node_struct< T >::type, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::template_P2 ( PQ_node  node  )  [inline]

A template in the reduce pass. Returns false if the template doesn't exist.

Definition at line 1591 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, gdt::gdtlist< E >::clear(), forall, FULL, gdt::PQ_node_struct< T >::full_children, gdt::gdtlist< E >::head(), gdt::PQ_node_struct< T >::id, gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, gdt::PQ_node_struct< T >::mark, gdt::PQ_node_struct< T >::parent, gdt::PQ_node_struct< T >::partial_children, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, PNODE, gdt::gdtlist< E >::size(), gdt::gdtlist< E >::tail(), gdt::PQ_node_struct< T >::type, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::template_P3 ( PQ_node  node  )  [inline]

A template in the reduce pass. Returns false if the template does not exist.

Definition at line 1682 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, gdt::gdtlist< E >::clear(), EMPTY, forall, FULL, gdt::PQ_node_struct< T >::full_children, gdt::gdtlist< E >::head(), gdt::PQ_node_struct< T >::id, gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::left_endmost, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, gdt::PQ_node_struct< T >::mark, NULL, gdt::PQ_node_struct< T >::parent, PARTIAL, gdt::PQ_node_struct< T >::partial_children, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, PNODE, QNODE, gdt::PQ_node_struct< T >::right_endmost, gdt::gdtlist< E >::size(), gdt::gdtlist< E >::tail(), gdt::PQ_node_struct< T >::type, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::template_P4 ( PQ_node  node  )  [inline]

A template in the reduce pass. Returns false if the template does not exist.

Definition at line 1806 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, gdt::gdtlist< E >::clear(), forall, FULL, gdt::PQ_node_struct< T >::full_children, gdt::gdtlist< E >::head(), gdt::PQ_node_struct< T >::id, gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::left_endmost, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, gdt::PQ_node_struct< T >::mark, NULL, gdt::PQ_node_struct< T >::parent, gdt::PQ_node_struct< T >::partial_children, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, PNODE, gdt::PQ_node_struct< T >::right_endmost, gdt::gdtlist< E >::size(), gdt::gdtlist< E >::tail(), gdt::PQ_node_struct< T >::type, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::template_P5 ( PQ_node  node  )  [inline]

A template in the reduce pass. Returns false if the template does not exist.

Definition at line 1979 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, EMPTY, forall, FULL, gdt::PQ_node_struct< T >::full_children, gdt::gdtlist< E >::head(), gdt::PQ_node_struct< T >::id, gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::left_endmost, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, gdt::PQ_node_struct< T >::mark, NULL, gdt::PQ_node_struct< T >::parent, gdt::PQ_node_struct< T >::partial_children, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, PNODE, gdt::PQ_node_struct< T >::remove_from_circular_link(), gdt::PQ_node_struct< T >::right_endmost, gdt::gdtlist< E >::size(), gdt::PQ_node_struct< T >::type, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::template_P6 ( PQ_node  node  )  [inline]

A template in the reduce pass. Returns false if the template does not exist.

Definition at line 2206 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, gdt::gdtlist< E >::clear(), EMPTY, forall, FULL, gdt::PQ_node_struct< T >::full_children, gdt::gdtlist< E >::head(), gdt::PQ_node_struct< T >::id, gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::left_endmost, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, gdt::PQ_node_struct< T >::mark, NULL, gdt::PQ_node_struct< T >::parent, PARTIAL, gdt::PQ_node_struct< T >::partial_children, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, PNODE, gdt::gdtlist< E >::pop(), QNODE, gdt::PQ_node_struct< T >::right_endmost, gdt::gdtlist< E >::size(), gdt::gdtlist< E >::tail(), gdt::PQ_node_struct< T >::type, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::template_Q1 ( PQ_node  node  )  [inline]

A template in the reduce pass. Returns false if the template does not exist.

Definition at line 2469 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, FULL, gdt::PQ_node_struct< T >::full_children, gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::mark, gdt::PQ_node_struct< T >::parent, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, QNODE, gdt::gdtlist< E >::size(), gdt::PQ_node_struct< T >::type, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::template_Q2 ( PQ_node  node  )  [inline]

A template in the reduce pass. Returns false if the template does not exist.

Definition at line 2495 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, EMPTY, forall, FULL, gdt::PQ_node_struct< T >::full_children, gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::left_endmost, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, gdt::PQ_node_struct< T >::mark, NULL, gdt::PQ_node_struct< T >::parent, PARTIAL, gdt::PQ_node_struct< T >::partial_children, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, gdt::gdtlist< E >::pop(), QNODE, gdt::PQ_node_struct< T >::right_endmost, gdt::gdtlist< E >::size(), gdt::PQ_node_struct< T >::type, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::template_Q3 ( PQ_node  node  )  [inline]

A template in the reduce pass. Returns false if the template does not exist.

Definition at line 2696 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::append(), gdt::PQ_node_struct< T >::child_count, gdt::gdtlist< E >::clear(), EMPTY, FULL, gdt::PQ_node_struct< T >::full_children, gdt::gdtlist< E >::head(), gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::left_endmost, gdt::PQ_node_struct< T >::link_left_side, gdt::PQ_node_struct< T >::link_right_side, gdt::PQ_node_struct< T >::mark, NULL, gdt::PQ_node_struct< T >::parent, PARTIAL, gdt::PQ_node_struct< T >::partial_children, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, PSEUDONODE, QNODE, gdt::PQ_node_struct< T >::right_endmost, gdt::gdtlist< E >::size(), gdt::gdtlist< E >::tail(), gdt::PQ_node_struct< T >::type, and UNMARKED.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::make_empty (  )  [inline]

Makes empty a pq_tree. Returns false if it fails.

Definition at line 3111 of file rm3_PQ_tree.h.

References gdt::gdtqueue< E >::append(), gdt::PQ_node_struct< T >::child_count, gdt::gdtqueue< E >::empty(), forall, gdt::PQ_node_struct< T >::id, NULL, gdt::PQ_node_struct< T >::parent, gdt::gdtqueue< E >::pop(), PSEUDONODE, and gdt::PQ_node_struct< T >::type.

Here is the call graph for this function:

template<class T>
bool gdt::PQ_tree< T >::reduce ( gdt::gdtlist< T > &  S  )  [inline]

Second step for reduction of a PQ_tree. Returns false if th reduction does not exist.

Definition at line 3154 of file rm3_PQ_tree.h.

References gdt::gdtlist< E >::clear(), EMPTY, forall, gdt::PQ_node_struct< T >::full_children, gdt_error, gdt::PQ_node_struct< T >::label, gdt::PQ_node_struct< T >::mark, NULL, gdt::PQ_node_struct< T >::parent, gdt::PQ_node_struct< T >::partial_children, gdt::PQ_node_struct< T >::pertinent_child_count, gdt::PQ_node_struct< T >::pertinent_leaf_count, gdt::gdtlist< E >::size(), gdt::gdtlist< E >::tail(), and UNMARKED.

Here is the call graph for this function:

template<class T>
void gdt::PQ_tree< T >::freeze ( PQ_tree_freezed< T > &  freezed_tree  )  [inline]

It "freezes" a PQ_tree into a PQ_tree_freezed.

Definition at line 3343 of file rm3_PQ_tree.h.

References gdt::gdtqueue< E >::append(), gdt::PQ_node_struct_freezed< T >::children_list, forall, gdt::PQ_node_struct< T >::id, gdt::PQ_node_struct_freezed< T >::id, gdt::PQ_node_struct< T >::is_endmost(), LEAF, gdt::PQ_node_struct< T >::left_endmost, gdt::PQ_node_struct< T >::link_left_side, NULL, gdt::PQ_tree_freezed< T >::number_of_nodes, gdt::PQ_node_struct< T >::parent, gdt::gdtqueue< E >::pop(), QNODE, gdt::PQ_node_struct< T >::right_endmost, gdt::PQ_tree_freezed< T >::root, gdt::gdtqueue< E >::size(), gdt::PQ_node_struct_freezed< T >::type, gdt::PQ_node_struct< T >::type, gdt::PQ_node_struct< T >::value, and gdt::PQ_node_struct_freezed< T >::value.

Here is the call graph for this function:

template<class T>
undi_graph gdt::PQ_tree< T >::PQ_tree_into_undi_graph ( std::string  title  )  [inline]

Input: PQ_tree. Returns the corresponding graph.

Definition at line 3420 of file rm3_PQ_tree.h.

References gdt::gdtqueue< E >::append(), gdt::PQ_node_struct< T >::child_count, gdt::gdtqueue< E >::empty(), undi_graph::find_node(), forall, forall_nodes, gdt_itoa(), undi_graph::id(), gdt::PQ_node_struct< T >::id, LEAF, undi_graph::new_edge(), undi_graph::new_node(), NULL, gdt::PQ_node_struct< T >::parent, PNODE, gdt::gdtqueue< E >::pop(), draw_undi_graph::set_label(), gdt::PQ_node_struct< T >::type, and draw_undi_graph::write().

Here is the call graph for this function:

The documentation for this class was generated from the following file:
Generated on Thu Jan 10 14:50:34 2008 for GDToolkit GAPI by  doxygen 1.5.3