| blob | d271675e230828a563b20901f92ab2d1d7852d60 |
1 /*
2 * $Revision: 2583 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012) $
7 ***************************************************************/
9 /** \file
10 * \brief Declaration and implementation of the class PQTree.
11 *
12 * \author Sebastian Leipert
13 *
14 * \par License:
15 * This file is part of the Open Graph Drawing Framework (OGDF).
16 *
17 * \par
18 * Copyright (C)<br>
19 * See README.txt in the root directory of the OGDF installation for details.
20 *
21 * \par
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
26 * for details.
27 *
28 * \par
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
33 *
34 * \par
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
39 *
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
44 #ifdef _MSC_VER
45 #pragma once
46 #endif
49 #ifndef OGDF_PQ_TREE_H
50 #define OGDF_PQ_TREE_H
53 #include <string.h>
55 #include <ogdf/basic/Stack.h>
56 #include <ogdf/basic/Queue.h>
57 #include <ogdf/basic/Array.h>
59 #include <ogdf/internal/planarity/PQNode.h>
60 #include <ogdf/internal/planarity/PQInternalNode.h>
61 #include <ogdf/internal/planarity/PQLeaf.h>
62 #include <ogdf/internal/planarity/PQLeafKey.h>
63 #include <ogdf/internal/planarity/PQInternalKey.h>
64 #include <ogdf/internal/planarity/PQNodeKey.h>
72 class PQTree
73 {
78 /**
79 * The function shown here is the destructor of the class template PQTree.
80 * In order to free allocated memory, all nodes of the
81 * tree have to be deleted, hence their destructors have to be called.
82 * This is done in the function Cleanup().
83 * Furthermore all other initialized memory has to be freed which is
84 * done as well in the function Cleanup().
85 */
102 /**
103 * If the user wishes to use different flags in a derived class of PQTree
104 * that are not available in this implementation, he can overload the function
105 * clientDefinedEmptyNode() in order to make a valid cleanup of the nodes.
106 * It will be called per default by the function emptyAllPertinentNodes().
107 */
110 }
118 /**
119 * The function root() returns a pointer of the root node of the PQTree.
120 */
123 }
132 //! is a pointer to the root of the $PQ$-tree.
135 //! is a pointer to the root of the pertinent subtree.
138 //! is a pointer to the virtual root of the pertinent subtree, in case that the pertinent root cannot be detected.
141 //! Stores the total number of nodes that have been allocated.
142 /**
143 * Gives every node that has been used once in the
144 * PQ-tree a unique identification number.
145 */
148 //! Stores the number of leaves.
151 /**
152 * Stores all nodes that have been marked \b FULL or
153 * \b PARTIAL during a reduction. After the reduction has been
154 * finished succesfully, all pertinent nodes are reinitialized and
155 * prepared for the next reduction. This list also contains pertinent
156 * nodes that have been removed during a reduction. When detected in
157 * the stack, their memory is freed.
158 */
202 /**
203 * The function destroyNode() marks a node as TO_BE_DELETED. This
204 * enables the function emptyAllPertinentNodes()
205 * to remove the node and free its memory.
206 */
209 }
228 }
233 }
237 }
241 }
246 }
250 }
254 }
285 };
289 /************************************************************************
290 addNewLeavesToTree
291 ************************************************************************/
293 /**
294 * The function addNewLeavesToTree() adds a set of elements to the already
295 * existing set of elements of a PQ-tree.
296 * These elements have to be of type PQLeafKey
297 * and are handed to the function in an array leafKeys.
298 * The father of the new elements that has to be an existing P- or Q-node,
299 * has to be specified and is not allowed to have children.
300 *
301 * The above mentioned facts
302 * are checked by the function addNodeToNewParent() and the process
303 * of adding a child to parent is interrupted with an error message
304 * returning 0 as soon none of the facts is fullfilled.
305 * The function addNewLeavesToTree() returns 1 if it
306 * succeeded in adding the leaves to parent.
307 */
313 {
315 {
317 // Father has children. Brothers expected
319 /// Enter the first element as PQLeaf to the [[parent]].
323 PQNode<T,X,Y>* aktualSon = OGDF_NEW PQLeaf<T,X,Y>(m_identificationNumber++,PQNodeRoot::EMPTY,newKey);
330 /// Enter all other elements as leaves to [[parent]].
332 {
342 }
344 /// Set the reference pointers if [[parent]] is a $P$-node.
345 {
350 }
352 /// Set the endmost children if [[parent is a $Q$-node.
353 {
356 }
358 }
361 }
365 /************************************************************************
366 addNodeToNewParent
367 ************************************************************************/
369 /**
370 * The function addNodeToNewParent() adds a node \a child as a child
371 * to another node specified in \a parent.
372 * The \a parent of the new node has to be an existing P- or Q-node and
373 * is \b not allowed to have children.
374 * In the case, that \a parent has children, addNewNodeToParent()
375 * returns 0 printing an error-message.
376 * In this case, use the function addNodeToParent() while specifying the future
377 * siblings of \a child. See addNodeToNewParent2() for more
378 * details.
379 *
380 * After successfully inserting \a child to \a parent the function
381 * addNewNodeToParent() returns 1. Otherwise it returns
382 * 0.
383 */
389 {
391 //parent type not valid.
394 {
396 //when adding new nodes: Brothers expected.
401 /*
402 Set the reference pointers in case that [[parent]] is a $P$-node.
403 If [[parent]] is a $Q$-node, this chunk sets the endmost children
404 of [[parent]]. Since [[child]] is the only child of [[parent]]
405 both endmost pointers are set to [[child]].
406 */
408 {
413 }
415 {
418 }
421 }
424 }
427 /************************************************************************
428 addNodeToNewParent
429 ************************************************************************/
431 /**
432 * The function addNodeToNewParent() adds a node \a child to the children
433 * of another node specified in \a parent.
434 * The \a parent of the new node has to be an existing P- or Q-node and
435 * is allowed to have children. In case that \a parent has children,
436 * the siblings of the new introduced child <b> must be specified</b>.
437 * If no siblings are specified, the function addNodeToNewParent(PQNode<T,X,Y>*,PQNode<T,X,Y>*)
438 * is called by default.
439 * If the \a parent is not specified, the function assumes that
440 * \a child is added as interior child to a Q-node.
441 *
442 * The client of this function should observe the following facts:
443 * - If \a parent is a P-node, than only one sibling is needed in order
444 * to enter the \a child. If the client specifies two siblings in \a leftBrother
445 * and \a rightBrother, then an arbitrary one is choosen to be a sibling.
446 * - If \a parent is a Q-node, two siblings <b>must be specified</b> if
447 * \a child has to become an interior child of the Q-node. If just
448 * one sibling is specified, this implies that \a child is about to become
449 * a new endmost child of \a parent. So either \a leftBrother or
450 * \a rightBrother must store an existing endmost child of \a parent.
451 * - If \a parent is a zero pointer, addNodeToNewParents() assumes
452 * that \a child is added as interior child to a Q-node. In this
453 * case \b both siblings of \a child <b>have to be specified</b>. Observe
454 * however, that it is also legal to specify the parent in this case.
455 *
456 * The above mentioned facts
457 * are checked by the function addNodeToNewParent() and the process
458 * of adding a child to \a parent is interrupted with an error message
459 * returning 0 as soon
460 * none of the facts is fullfilled.
461 * The function addNodeToNewParent() returns 1 if it
462 * succeeded in adding the \a child to \a parent.
463 */
471 {
474 {
476 //parent type not valid
480 {
486 {
487 /*
488 The parent is a $P$-node with children.
489 Either [[leftBrother]] or [[rightBrother]] stores
490 a pointer to an existing child of [[parent]] and [[parent]]
491 is a $P$-node. In case that two brothers are stored, an
492 arbitrary one is choosen to be the next sibling of [[child]].
493 This brother is stored in [[brother]]. The pointer [[sister]]
494 denotes a pointer to an arbitrary sibling of [[brother]].
495 */
503 }
506 {
507 /*
508 The parent is a $Q$-node with children.
509 The [[leftBrother]] is a [[0]]-pointer while the
510 [[rightBrother]] denotes an existing child of [[parent]].
511 The node [[rightBrother]] {\bf must be} one of the two endmost
512 children of [[parent]]. If this is not the case, the chunk
513 detects this, halts the procedure [[addNewLeavesToTree]]
514 printing an error message and returning [[0]].
515 If [[rightBrother]] is endmost child of [[parent]], then
516 this chunk adds [[child]] at the one end where
517 [[rightBrother]] hides. The node [[child]] is then made the
518 new endmost child of [[parent]] on the corresponding side.
519 */
521 {
526 }
528 // missing second brother?
534 }
537 {
538 /*
539 The parent is a $Q$-node with children.
540 The [[rightBrother]] is a [[0]]-pointer while the
541 [[leftBrother]] denotes an existing child of [[parent]]. The
542 node [[leftBrother]] {\bf must be} one of the two endmost
543 children of [[parent]]. If this is not the case, the chunk
544 detects this, halts the procedure [[addNodeToNewParent]]
545 printing an error message and returning [[0]].
546 If [[leftBrother]] is endmost child of [[parent]], then this
547 chunk adds [[child]] at the one end where [[leftBrother]]
548 hides. The node [[child]] is then made new endmost child of
549 [[parent]] on the corresponding side.
550 */
552 {
557 }
559 // missing second brother?
565 }
567 else
568 {
569 /*
570 The parent is a $Q$-node with children.
571 Both the [[rightBrother]] and the [[leftBrother]] denote
572 existing children of [[parent]]. In this case, [[leftBrother]]
573 and [[rightBrother]] must be immideate siblings. If this is
574 not the case, this will be detected during the function call
575 [[changeSiblings]] of the class [[PQNode.h]] (see
576 \ref{PQNode.changeSiblings}) in the first two lines of this
577 chunk. If the chunk recognizes the failure of
578 [[changeSiblings]] it halts the procedure
579 [[addNewLeavesToTree]], printing an error message and
580 returning [[0]].
581 If the two brothers are immediate siblings, this chunk
582 adds [[child]] between the two brothers as interior child of
583 the $Q$-node [[parent]].
584 */
585 #ifdef OGDF_DEBUG
587 #endif
588 rightBrother->changeSiblings(leftBrother,child) && leftBrother->changeSiblings(rightBrother,child);
590 // brothers are not siblings?
594 {
597 }
598 else
599 {
602 }
604 }
605 }
606 else
608 }
610 {
611 /*
612 The parent is a $Q$-node with children.
613 Both the [[rightBrother]] and the [[leftBrother]] denote
614 existing children of [[parent]]. In this case, [[leftBrother]]
615 and [[rightBrother]] must be immideate siblings. If this is
616 not the case, this will be detected during the function call
617 [[changeSiblings]] of the class [[PQNode.h]] (see
618 \ref{PQNode.changeSiblings}) in the first two lines of this
619 chunk. If the chunk recognizes the failure of
620 [[changeSiblings]] it halts the procedure
621 [[addNewLeavesToTree]], printing an error message and
622 returning [[0]].
623 If the two brothers are immediate siblings, this chunk
624 adds [[child]] between the two brothers as interior child of
625 the $Q$-node [[parent]].
626 */
627 #ifdef OGDF_DEBUG
629 #endif
630 rightBrother->changeSiblings(leftBrother,child) && leftBrother->changeSiblings(rightBrother,child);
632 // brothers are not siblings?
636 {
639 }
640 else
641 {
644 }
646 }
649 }
653 /************************************************************************
654 Bubble
655 ************************************************************************/
657 /**
658 * The function Bubble() realizes a function described in [Booth].
659 * It <em>bubbles</em> up from the pertinent leaves to the pertinent root
660 * in order to make sure that every pertinent node in the pertinent subtree
661 * has a valid pointer to its parent. If Bubble() does not succed in doing so,
662 * then the set of elements, stored in the \a leafKeys cannot form
663 * a consecutive sequence.
664 *
665 * The function Bubble() uses a wide variaty of variables, explained
666 * in detail below.
667 * - \a blockcount is the number of blocks of blocked nodes during
668 * the bubbling up phase.
669 * - \a numBlocked is the number of blocked nodes during the
670 * bubbling up phase.
671 * - \a blockedSiblings counts the number of blocked siblings that
672 * are adjacent to \a checkNode. A node has 0, 1 or 2 blocked siblings.
673 * A child of a P-node has no blocked siblings. Endmost children of
674 * Q-nodes have at most 1 blocked sibling. The interior children of
675 * a Q-Node have at most 2 blocked siblings.
676 * - \a checkLeaf is a pointer used for finding the pertinent leaves.
677 * - \a checkNode is a pointer to the actual node.
678 * - \a checkSib is a pointer used to examin the siblings of [[checkNode]].
679 * - \a offTheTop is a variable which is either 0 (that is its
680 * initial value) or 1 in case that the root of the tree has been
681 * process during the first phase.
682 * - \a parent is a pointer to the parent of \a checkNode, if \a checkNode
683 * has a valid parent pointer.
684 * - \a processNodes is a first-in first-out list that is used for
685 * sequencing the order in which the nodes are processed.
686 * - \a blockedNodes is a stack storing all nodes that have been
687 * once blocked. In case that the [[m_pseudoRoot]] has to be
688 * introduced, the stack contains the blocked nodes.
689 */
693 {
696 /*
697 Enter the [[Full]] leaves into the queue [[processNodes]].
698 In a first step the pertinent leaves have to be identified in the tree
699 and entered on to the queue [[processNodes]]. The identification of
700 the leaves can be done with the help of a pointer stored in every
701 [[PQLeafKey]] (see \ref{PQLeafKey}) in constant time for every element.
702 */
705 {
710 }
720 {
722 /*
723 No consecutive sequence possible.
724 The queue [[processNodes]] does not contain any nodes for
725 processing and the sum of [[blockCount]] and [[offTheTop]] is
726 greater than 1. If the queue is empty, the root of the pertinent
727 subtree was already processed. Nevertheless, there are blocked
728 nodes since [[offTheTop]] is either be [[0]] or [[1]], hence
729 [[blockCount]] must be at least [[1]]. Such blocked nodes cannot
730 form a consecutive sequence with all nodes in the set
731 [[leafKeys]]. Observe that this chunk finishes the function
732 [[Bubble]]. Hence every memory allocated by the function [[Bubble]]
733 has to be deleted here as well.
734 */
736 /*
737 If there are still nodes to be processed in which case the queue
738 [[processNodes]] is not empty, we get the next node from the queue.
739 By default this node has to be marked as blocked.
740 */
746 /*
747 Check if node is adjacent to an unblocked node.
748 After getting the node [[checkNode]] from the queue, its siblings are
749 checked, whether they are unblocked. If they are, then they have a
750 valid pointer to their parent and the parent pointer of [[checkNode]]
751 is updated.
752 */
754 // checkNode is son of a QNode.
755 // Check if it is blocked.
756 {
758 // checkNode is endmost child of
759 // a QNode. It has a valid pointer
760 // to its parent.
761 {
765 blockedSiblings++;
766 }
769 // checkNode is endmost child of
770 // a QNode. It has a valid pointer
771 // to its parent.
772 {
776 blockedSiblings++;
777 }
780 else
781 // checkNode is not endmost child of
782 // a QNode. It has not a valid
783 // pointer to its parent.
784 {
786 // checkNode is adjacent to an
787 // unblocked node. Take its parent.
788 {
791 }
793 blockedSiblings++;
796 // checkNode is adjacent to an
797 // unblocked node. Take its parent.
798 {
801 }
803 blockedSiblings++;
804 }
805 }
807 else
808 // checkNode is son of a PNode
809 // and children of P_NODEs
810 // cannot be blocked.
814 {
817 /*
818 Get maximal consecutive set of blocked siblings.
819 This chunk belongs to the procedure [[bubble]].
820 The node [[checkNode]] is [[UNBLOCKED]].
821 If the parent of [[checkNode]] is a $Q$-Node, then we check the
822 siblings [[checkSib]] of [[checkNode]] whether they are
823 [[BLOCKED]]. If they are blocked, they have to be marked
824 [[UNBLOCKED]] since they are adjacent to the [[UNBLOCKED]] node
825 [[checkNode]]. We then have to proceed with the siblings of
826 [[checkSib]] in order to find [[BLOCKED]] nodes
827 adjacent to [[checkSib]]. This is repeated until no [[BLOCKED]]
828 nodes are found any more.
830 Observe that while running through the children of the $Q$-Node
831 (referred by the pointer [[parent]]), their parent pointers,
832 as well as the [[pertChildCount]] of [[parent]] are updated.
833 Furthermore we reduce simultaneously the count [[numBlocked]].
834 */
836 {
838 {
842 {
845 numBlocked--;
850 //Blocked node as endmost child of a QNode.
851 }
852 }
855 {
859 {
862 numBlocked--;
867 //Blocked node as endmost child of a QNode.
868 }
869 }
873 /*
874 Process parent of [[checkNode]]
875 After processing the siblings of the [[UNBLOCKED]] [[checkNode]]
876 the parent has to be processed. If [[checkNode]] is the root
877 of the tree we do nothing except setting the flag [[offTheTop]].
878 If it is not the root and [[parent]] has not been placed onto the
879 queue [[processNodes]], the [[parent]] is placed on to
880 [[processNodes]].
882 Observe that the number [[blockCount]] is updated. Since
883 [[checkNode]] was [[UNBLOCKED]] all perinent nodes adjacent
884 to that node became [[UNBLOCKED]] as well. Therefore the number
885 of blocks is reduced by the number of [[BLOCKED]] siblings of
886 [[checkNode]].
887 */
889 // checkNode is root of the tree.
891 else
892 // checkNode is not the root.
893 {
896 {
900 }
901 }
908 else
909 {
910 /*
911 Process blocked [[checkNode]]
912 Since [[checkNode]] is [[BLOCKED]], we cannot continue
913 processing at this point in the Tree. We have to wait until
914 this node becomes unblocked. So only the variables
915 [[blockCount]] and [[numBlocked]] are updated.
916 */
918 numBlocked++;
919 }
924 {
925 /*
926 If [[blockCount]] $= 1$ enter [[m_pseudoRoot]] to the tree
927 In case that the root of the pertinent subtree is a $Q$-node
928 with empty children on both sides and the pertinent children
929 in the middle, it is possible that the $PQ$-tree is reducible.
930 But since the sequence of pertinent children of the $Q$-node is
931 blocked, the procedure is not able to find the parent of its
932 pertinent children. This is due to the fact that the interior
933 children of a $Q$-node do not have a valid parent pointer.
935 So the root of the pertinent subtree is not known, hence cannot be
936 entered into the processing queue used in the function call [[Reduce]]
937 (see \ref{Reduce}). To solve this problem a special node only designed
938 for this cases is used: [[m_pseudoRoot]]. It simulates the root of the
939 pertinent subtree. This works out well, since for this node the only
940 possible template maching is [[templateQ3]] (see \ref{templateQ3}),
941 where no pointers to the endmost children of a $Q$-node are used.
942 */
944 {
947 {
952 //Blocked node as endmost child of a QNode.
953 }
954 }
955 }
958 }
961 /************************************************************************
962 checkChain
963 ************************************************************************/
965 /**
966 * The function checkChain() is used by the function templateQ2()
967 * and templateQ3().
968 * It checks whether all full children of a Q-node
969 * \a nodePtr form a consecutive sequence. If the full nodes do so,
970 * the procedure returns 1 as a result, otherwise 0.
971 *
972 * The pointer \a firstFull denotes just an arbirtary full child. Starting
973 * from this position, checkChain sweeps through the consecutive
974 * sequence, halting as soon as a nonfull child is detected.
975 * The two pointers \a seqStart and \a seqEnd are set within the
976 * function \a checkChain. They denote the first and last node of the consecutive
977 * sequence.
978 *
979 * The client should observe that it is not possible to avoid the use
980 * of such a function. According to the procedure Bubble() children of
981 * Q-nodes get unblocked as soon as they are adjacent to any pertinent
982 * sibling. This includes that chains of more than two partial children
983 * are regarded as unblocked as well.
984 * Such chains are of course not reducible and therefore
985 * have to be detected by the function checkChain().
986 *
987 * Following we give an overview of the variables used in
988 * checkChain().
989 * - \a fullCount counts the number of children that are
990 * discovered by the function checkChain(). This is necessary, since
991 * checkChain() is used by two template matching functions
992 * templateQ2() and templateQ3() where in the latter case the
993 * pointer \a firstFull may point to any full child in the front of the Q-node
994 * \a nodePtr.
995 * - \a notFull is set 1 when an empty child is encountered.
996 * - \a checkNode is the actual node that is examined.
997 * - \a leftNext is the next node that has to be examined on the
998 * left side of \a firstFull.
999 * - \a leftOld is the node that has been examined right before
1000 * \a checkNode on the left side of \a firstFull.
1001 * - \a rightNext is the next node that has to be examined on the
1002 * right side of \a firstFull. Not needed when checkChain() was
1003 * called by templateQ2().
1004 * - \a rightOld is the node that has been examined right before
1005 * \a checkNode on the right side of \a firstFull.
1006 * Not needed when checkChain() was called by templateQ2().
1007 */
1015 {
1020 /*
1021 Start at the [[firstFull]] child sweeping through the full children on
1022 the left side of [[firstfull]]. It stops as soon as a nonfull child is
1023 detected. The last found full child is stored in [[seqEnd]].
1024 */
1028 {
1030 fullCount--;
1036 // There are still full children to be
1037 // counted, and no empty child has been
1038 // encountered on this side.
1039 {
1042 fullCount--;
1043 else
1047 }
1053 //searching consecutive sequence in Q2 or Q3.
1056 }
1060 }
1061 }
1063 /*
1064 Start at the [[firstFull]] child sweeping through the full children on
1065 the right side of [[firstfull]]. It stops as soon as a nonfull child is
1066 detected.
1067 */
1072 {
1074 fullCount--;
1080 // There are still full children to be
1081 // counted, and no empty child has been
1082 // encountered on this side.
1083 {
1086 fullCount--;
1087 else
1091 }
1098 //searching consecutive seqeuence in Q2 or Q3.
1099 }
1103 }
1104 }
1109 {
1113 }
1116 // All full children occupy a consecutive
1117 // sequence.
1119 else
1121 }
1124 /************************************************************************
1125 checkIfOnlyChild
1126 ************************************************************************/
1128 /**
1129 * The function checkIfOnlyChild() checks if \a child is the only
1130 * child of \a parent. If so, \a child is connected to its
1131 * grandparent, as long as parent is not the root of the tree. In case
1132 * that \a parent is the root of the tree and \a child is its only
1133 * child, the node \a child becomes the new root of the tree. The parent then
1134 * is completely removed from the tree and destroyd. The return value of
1135 * the method checkIfOnlyChild() is 1, if \a child was the only
1136 * child of parent. Otherwise the return value is 0.
1137 * Before applying the function exchangeNodes(), the function removeChildFromSiblings()
1138 * is applied. This is usefull in case
1139 * the node \a parent has some ignored children and has to be reused
1140 * within some extra algorithmic context.
1141 */
1148 {
1152 {
1157 else
1158 {
1161 }
1164 }
1165 else
1167 }
1170 /************************************************************************
1171 Cleanup
1172 ************************************************************************/
1174 /**
1175 * The function Cleanup() removes the entire PQ-tree, stored in the
1176 * class template PQTree. The function Cleanup() is called by the
1177 * destructor of the class template PQTree.
1178 * It scans all nodes of the tree and frees the
1179 * memory used by the tree. Cleanup() includes the removal of the memory
1180 * allocated by the following datastructures:
1181 * - \a m_root,
1182 * - \a m_pseudoRoot,
1183 * - \a m_pertinentNodes.
1184 * The function Cleanup() enables the client to reuse the function
1185 * Initialize().
1186 *
1187 * In order to free the allocated memory, all nodes of the
1188 * tree have to be deleted, hence there destructors are called.
1189 * In order to achieve this, we start at the root of the tree and go down the
1190 * tree to the leaves for reaching every node. When a node is processed,
1191 * (besides the \a m_root, this will always be the node \a checkNode)
1192 * the pointers of all its children are stored in a queue \a helpqueue and
1193 * then the processed node is deleted.
1194 *
1195 * The use of a queue \a helpqueue is a must, since the nodes do not
1196 * have pointers to all of their children, as the children mostly do
1197 * not have a pointer to their parent.
1198 *
1199 * It might look weird at the first glance that the function Cleanup()
1200 * calls the function emptyAllPertinentNodes(), but if some nodes were removed
1201 * during a reduction, they were stored in the stack \a m_pertinentNodes.
1202 * These nodes have to be deleted as well
1203 * which is provided by the function emptyAllPertinentNodes().
1204 */
1208 {
1216 {
1219 /*
1220 Process the [[m_root]] of the [[PQTree]]. Before deleting [[m_root]],
1221 pointers to all its children are stored in the queue [[helpqueue]].
1222 */
1224 {
1226 {
1233 {
1236 }
1237 }
1238 }
1240 {
1250 {
1255 }
1256 }
1263 {
1266 /*
1267 Process an arbitrary node [[checkNode]] of the [[PQTree]].
1268 Before deleting [[checkNode]],
1269 pointers to all its children are stored in the queue [[helpqueue]].
1270 */
1272 {
1274 {
1281 {
1284 }
1285 }
1286 }
1288 {
1300 {
1305 }
1306 }
1310 }
1311 }
1325 }
1328 /************************************************************************
1329 clientPrintNodeCategorie
1330 ************************************************************************/
1332 /**
1333 * If the user wishes to use different flags in a derived class of PQTree
1334 * that are not available in this implementation, he can overload the function
1335 * clientPrintNodeCategorie(). This function is called per default by the functions
1336 * printOutCurrentTree() and printNode().
1337 * With the help of this function it is possible to influence the layout of the nodes
1338 * by using new, different lables depicting node categories
1339 * in the <em>Tree Interface</em>.
1340 */
1344 {
1346 // 1 is the standard node categrie in the Tree Interface.
1347 }
1350 /************************************************************************
1351 clientPrintStatus
1352 ************************************************************************/
1354 /**
1355 * If the user wishes to use different status in a derived class of PQTree
1356 * that are not available in this implementation, he can overload the function
1357 * clientPrintStatus(). This function is called per default by the functions
1358 * printOutCurrentTree() and printNode().
1359 * With the help of this function it is possible to influence the information stored
1360 * at nodes in the <em>Tree Interface</em> that concern the
1361 * status of a node.
1362 */
1366 {
1368 }
1371 /************************************************************************
1372 clientPrintType
1373 ************************************************************************/
1375 /**
1376 * If the user wishes to use different types in a derived class of PQTree
1377 * that are not available in this implementation, he can overload the function
1378 * clientPrintType(). This function is called per default by the functions
1379 * printOutCurrentTree() and printNode().
1380 * With the help of this function it is possible to influence the information stored
1381 * at nodes in the <em>Tree Interface</em> that concern the
1382 * type of a node.
1383 */
1387 {
1389 }
1392 /************************************************************************
1393 Constructor
1394 ************************************************************************/
1398 {
1407 }
1411 /************************************************************************
1412 copyFullChildrenToPartial
1413 ************************************************************************/
1415 /**
1416 * The function copyFullChildrenToPartial()
1417 * copies all full children of \a nodePtr to a new P-node
1418 * The node \a nodePtr has to be a P-node. The new P-node
1419 * is added to \a partialChild as an endmost child of \a partialChild.
1420 * The node \a partialChild has to be a Q-node and the new P-node is added
1421 * to the side of \a partialChild where the pertinent children are.
1422 *
1423 * The new P-node is allocated by this function and referenced by the
1424 * variable \a newNode.
1425 *
1426 * The function copyFullChildrenToPartial() is used by the functions
1427 * templateP4(), templateP5(), and templateP6().
1428 */
1434 {
1436 // There are some full children to
1437 // be copied.
1438 {
1444 // Introduce newNode as endmost
1445 // child of the partial Q-node.
1450 {
1455 }
1457 // ERROR: Endmostchild not found?
1463 }
1467 }
1468 }
1471 /************************************************************************
1472 createNodeAndCopyFullChildren
1473 ************************************************************************/
1475 /**
1476 * The function createNodeAndCopyFullChildren() copies the full children of a
1477 * P-node that are stored in the stack \a fullNodes to a new P-node.
1478 * This new P-node
1479 * is created by the function and stored in \a newNode if there is more than one full child.
1480 * If there is just one full child, it is not necessary to construct a new
1481 * P-node and the full child is stored in \a newNode.
1482 * The \a newNode is the return value of the procedure.
1483 *
1484 * The function createNodeAndCopyFullChildren() is used by
1485 * templateP2() templateP3() and the function copyFullChildrenToPartial().
1486 * The function createNodeAndCopyFullChildren() uses the following
1487 * variables.
1488 * - \a newNode stores the adress of the new allocated P-node or
1489 * the adress of the only full child.
1490 * - \a oldSon is a variable used for adding the full nodes as
1491 * children to the new P-node.
1492 * - \a firstSon stores the adress of the first detected full
1493 * child. It is needed for adding the full nodes as
1494 * children to the new P-node.
1495 * - \a checkSon is a variable used for adding the full nodes as
1496 * children to the new P-node.
1497 * - \a newPQnode is used for proper allocation of the new P-node.
1498 */
1503 {
1507 {
1508 /*
1509 There is just one full child. So no new $P$-node is created. The
1510 full child is copied as child to the [[partialChild]].
1511 */
1514 }
1516 else
1517 {
1518 /*
1519 This chunk belongs to the function [[createNodeAndCopyFullChildren]].
1520 There is more than one full child, so a new $P$-node is created.
1521 This chunk first allocates the memory for the new $P$-node that will
1522 be stored in [[newNode]]. Then it pops the nodes out of the stack
1523 [[fullNodes]] and introduces them as sons of [[newNode]].
1524 Popping the nodes out of the stack implies at the same time
1525 that they are removed from the [[fullChildren]] stack of the
1526 $P$-node of their parent.
1527 */
1528 newNode = OGDF_NEW PQInternalNode<T,X,Y>(m_identificationNumber++,PQNodeRoot::PNode,PQNodeRoot::FULL);
1533 /*
1534 The first node is copied separately, since we need the pointer to it
1535 for setting the pointers to the siblings of the next full nodes.
1536 */
1545 /*
1546 All remaining nodes that are stored in the stack [[fullNodes]] are
1547 introduced as children of the new $P$-node [[newNode]]. Observe
1548 that the children of a $P$-node must form a doubly linked list.
1549 Hence the last node and the [[firstSon]] must be linked via their
1550 siblings pointers.
1551 */
1553 {
1562 }
1567 }
1570 }
1573 /************************************************************************
1574 emptyAllPertinetNodes
1575 ************************************************************************/
1577 /**
1578 * The function emptyAllPertinentNodes() has to be called after a reduction
1579 * has been processed. In cleans up all flags that have been set in the
1580 * pertinent nodes during the reduction process. All pertinent nodes have been
1581 * stored in the private member stack \a m_pertinentNodes of the class template
1582 * PQTree during the Bubble()-phase
1583 * or when processing one of the templates (see templateL1() to templateQ3()).
1584 */
1588 {
1592 {
1595 {
1600 //if (nodePtr)
1615 }
1616 }
1623 }
1626 /************************************************************************
1627 emptyNode
1628 ************************************************************************/
1630 /**
1631 * The funtion emptyNode() cleans up all stacks, flags and pointers of a
1632 * pertinent node that has been visited during the reduction process.
1633 */
1637 {
1644 }
1647 /************************************************************************
1648 exchangeNodes
1649 ************************************************************************/
1651 /**
1652 * The function exchangeNodes() replaces the \a oldNode by the \a newNode
1653 * in the tree. This is a function used very often in the template matchings,
1654 * normally in combination with the construction of a new node which has to
1655 * conquer the place of an existing node in the tree.
1656 *
1657 * This function can be used in all cases, so the parent of \a oldNode
1658 * is allowed to be either a Q-node or a P-node and \a oldNode may be
1659 * any child of its parent.
1660 *
1661 * The client should observe, that this function does \b not reset
1662 * the pointer \a m_root. If necessary, this has to be done explicitly by
1663 * the client himself.
1664 */
1670 {
1672 {
1673 /*
1674 The node [[oldNode]] is connected to its parent
1675 via the reference pointer of the doubly linked list. The [[newNode]]
1676 will be the new reference child and is linked via the reference
1677 pointers to the $P$-node.
1678 */
1682 }
1685 {
1686 /*
1687 The [[oldNode]] is endmost child of a Q-node. So its parent
1688 contains an extra pointer to [[oldNode]]. Link the parent of
1689 [[oldNode]] to [[newNode]] via this pointer and make [[newNode]]
1690 endmost child of its new parent.
1691 */
1696 }
1699 {
1700 /*
1701 Two possible cases are occured.
1702 \begin{enumerate}
1703 \item [[oldNode]] is the only child of a $P$-node. In order to
1704 implement the doubly linked list of children of the $P$-node, the sibling
1705 pointers of [[newNode]] are set to [[newNode]].
1706 \item [[oldNode]] is the [[m_root]] of the $PQ$-tree. Since
1707 by our definition of the $PQ$-tree the sibling pointers of the
1708 [[m_root]] point to the root itself, (i.e. to make sure that
1709 checking for the endmost child property is also valid for the root)
1710 the sibling pointers of [[newNode]] are set to [[newNode]] as well.
1711 \end{enumerate}
1712 */
1716 {
1719 }
1720 else
1721 {
1724 }
1725 }
1726 else
1727 {
1729 //sibling pointers of old node are not compatible
1731 //sibling pointers of old node are not compatible.
1732 }
1733 /*
1734 Manage the exchange of [[oldNode]] and [[newNode]] according to
1735 [[oldNode]]'s siblings. The chunk checks both siblings of
1736 [[oldNode]] and resets the sibling pointers of [[oldNode]]'s siblings
1737 as well as the sibling pointers of [[newNode]].
1738 */
1740 {
1744 // Sibling was not connected to child?
1747 }
1750 }
1753 {
1757 // Sibling was not connected to child?
1760 }
1763 }
1767 }
1770 /************************************************************************
1771 front
1772 ************************************************************************/
1774 /**
1775 * The function front()
1776 * returns the keys stored in the leaves of the front of
1777 * \a nodePtr. A specified node \a nodePtr of the PQ-tree is
1778 * handed to the function and front() detects the leaves in the front
1779 * of this node returning the elements represented by the leaves. These
1780 * elements are
1781 * stored in an array of keys named \a leafKeys.
1782 * The return value is the numbers of leaves that have been detected.
1783 * Observe that front() uses \a leafKeys[0] to store the
1784 * first key.
1785 */
1791 {
1796 {
1801 else
1802 {
1809 {
1812 }
1814 {
1817 }
1822 {
1827 }
1828 }
1829 }
1830 }
1833 /************************************************************************
1834 Initialize
1835 ************************************************************************/
1837 /**
1838 * The function Initialize() initializes the PQ-tree with a set of elements.
1839 * These elements have to be template classes of the class template PQLeafKey
1840 * and are handed to the function in an array \a leafKeys.
1841 * The function constructs the universal PQ-tree. If the
1842 * \a numberOfElements > 1, the universal PQ-tree consists of one P-node
1843 * as root (stored in \a m_root) and all leaves gathered underneath the P-node,
1844 * symbolizing all kinds of permutations. If \a numberOfElements = 1,
1845 * the universal PQ-tree consists of a single PQLeaf, being the root of
1846 * the tree.
1847 *
1848 * Observe that the first element has to be stored in
1849 * \a leafKeys[0] and the last one in
1850 * \a leafKeys[\a numberOfElements-1].
1851 * The function Initialize() returns 1, if the initialization of
1852 * the PQ-tree was successful.
1853 */
1857 {
1861 {
1862 PQInternalNode<T,X,Y> *newNode2 = OGDF_NEW PQInternalNode<T,X,Y>(-1,PQNodeRoot::QNode,PQNodeRoot::PARTIAL);
1866 {
1867 PQInternalNode<T,X,Y> *newNode = OGDF_NEW PQInternalNode<T,X,Y>(m_identificationNumber++,PQNodeRoot::PNode,PQNodeRoot::EMPTY);
1872 }
1873 PQLeaf<T,X,Y> *newLeaf = OGDF_NEW PQLeaf<T,X,Y>(m_identificationNumber++,PQNodeRoot::EMPTY,*leafKeys.begin());
1878 }
1881 }
1884 /************************************************************************
1885 linkChildrenOfQnode
1886 ************************************************************************/
1888 /**
1889 * The function linkChildrenOfQnode() links the two endmost children
1890 * of two \b different Q-nodes via their sibling pointers together.
1891 * The purpose of doing this is to combine the children of two Q-nodes
1892 * as children of only one Q-node. This function does not reset the
1893 * pointers to the endmost children of the Q-node. This has to be done
1894 * by the client of the function.
1895 */
1901 {
1903 {
1905 {
1909 else
1911 }
1913 // endmost child with 2 siblings encountered?
1919 else
1921 }
1922 }
1923 }
1927 /************************************************************************
1928 writeGML
1929 ************************************************************************/
1931 /**
1932 * The function writeGML() prints the PQ-tree in the GML
1933 * fileformat. The filename is ended by a ".gml" and can be read
1934 * eg. by the <em>AGD</em>.
1935 */
1939 {
1942 }
1946 {
1971 {
1983 {
1990 }
1992 {
1999 }
2001 {
2008 }
2010 {
2017 }
2023 {
2025 {
2032 {
2035 }
2036 }
2037 }
2039 {
2048 {
2053 {
2058 }
2059 }
2060 }
2062 {
2066 }
2067 else
2069 }
2075 {
2078 {
2080 {
2090 {
2096 }
2097 }
2098 }
2100 {
2112 {
2121 {
2129 }
2130 }
2131 }
2132 }
2134 }
2138 /************************************************************************
2139 Reduce
2140 ************************************************************************/
2142 /**
2143 * The function Reduce() does the reduction of the pertinent leaves
2144 * with the help of the template matchings, designed by Booth and Lueker.
2145 * The reader should observe that this function can only be called after
2146 * every pertinent node in the pertinent subtree has gotten a valid parent
2147 * pointer. If this is not the case, the programm will be interrupted
2148 * by run-time errors such as seqmentation faults. The pertinent nodes
2149 * can get valid parent pointers by using the function Bubble().
2150 * If the function Bubble() returns 1, then it was succesful in
2151 * giving each pertinent node in the pertinent subtree a valid parent pointer.
2152 * If the function returns 0, then some nodes do not have a valid
2153 * parent pointer and the pertinent leaves are not reducable.
2154 *
2155 * The function Reduce() starts with the pertinent leaves and stores
2156 * them in
2157 * a queue \a processNodes. Every time a node is processed, its parent is
2158 * checked whether all its pertinent children are already processed.
2159 * If this is the case, the parent is allowed to be processed as well
2160 * and stored in the queue.
2161 *
2162 * Processing a node means that the function Reduce() tries to apply
2163 * one of the template matchings. In case that one template matching was
2164 * successful, the node was reduced and Reduce() tries to reduce the
2165 * next node.
2166 * In case that no template matching was successfully applied, the tree is
2167 * is irreducible. This causes the reduction process to be halted
2168 * returning 0.
2169 *
2170 * The folllowing variables are used by the function Reduce().
2171 * - \a checkLeaf is a pointer to a various PQLeaf of the set of
2172 * elements that has to be reduced.
2173 * - \a checkNode is a pointer to a various node of the pertinent
2174 * subtree.
2175 * - \a pertLeafCount counts the number of pertinent leaves in the
2176 * PQ-tree. Since Reduce() takes care that every node knows the
2177 * number of pertinent leaves in its frontier, the root of the
2178 * pertinent subtree can be identified with the help of \a pertLeafCount.
2179 * - \a processNodes is a queue storing nodes of the pertinent
2180 * subtree that are considered to be reduced next. A node may be
2181 * reduced (and therefore is pushed on to \a processNodes) as soon as
2182 * all its pertinent children have been reduced.
2183 */
2187 {
2191 /*
2192 In a first step the pertinent leaves have to be identified in the tree
2193 and are entered on to the queue [[processNodes]]. The identification of
2194 the leaves can be done with the help of a pointer stored in every
2195 [[PQLeafKey]] in constant time for every element.
2196 */
2199 {
2204 pertLeafCount++;
2205 }
2209 {
2213 {
2214 /*
2215 Application of the template matchings to a pointer [[checkNode]]
2216 storing the adress of a node that is {\bf not the root} of the
2217 pertinent subtree. Before applying the template matchings to
2218 [[checkNode]], some values of the parent of [[checkNode]] are
2219 updated. The number of the parents pertinent children stored in
2220 [[pertChildCount]] is count down by one. In case that
2221 [[checkNode->m_parent->m_pertChildCount == 0]], we know that all
2222 pertinent children of the parent have been processed. Since the
2223 parent then is allowed to be processed as well,
2224 [[checkNode->m_parent]] is stored in the queue [[processNodes]].
2225 */
2240 }
2241 else
2242 {
2243 /*
2244 application of the template matchings to a pointer [[checkNode]]
2245 that stores the adress of a node that {\bf is the root} of the
2246 pertinent subtree. In a case that a template matching was
2247 successfully applied, the pointer [[checkNode]] stores after the
2248 application the adress of the root of pertinent subtree. This
2249 includes nodes that have been newly introduced as root of the
2250 perinent subtree during the application. If no template matching
2251 was successfully applied [[checkNode]] is a [[0]] pointer.
2252 */
2262 }
2263 }
2267 }
2271 /************************************************************************
2272 Reduction
2273 ************************************************************************/
2275 /**
2276 * The function Reduction() tests whether permissible permutations of the
2277 * elements of U exist such that the elements of a subset S of U,
2278 * stored in \a leafKeys, form a consecutive sequence. If there exists
2279 * such a permutation, the PQ-tree is reduced and Reduction()
2280 * returns 1.
2281 *
2282 * The function Reduction() gets a list \a leafKeys
2283 * of pointers to elements of type PQLeafKey,
2284 * representing all elements of S.
2285 *
2286 * Reduction() calls the procedure Bubble() and if Bubble() was
2287 * successful, Reduction() calls the function Reduce().
2288 */
2292 {
2297 else
2300 }
2303 /************************************************************************
2304 removeBlock
2305 ************************************************************************/
2307 /**
2308 * This chunk contains the procedure removeBlock. It is used by the functions
2309 * templateQ2() and templateQ3(). The node \a nodePtr is expected to be a
2310 * Q-node with no, one or at most two partial children, such that
2311 * the partial and full children of \a nodePtr form a legal consecutive
2312 * sequence, hence can be reduced.
2313 *
2314 * The function removeBlock() does the
2315 * following: Of every partial node that is found in the sequence of children of
2316 * \a nodePtr, all children are removed from that partial node and included
2317 * as children of \a nodePtr, occupying the place of the partial node in
2318 * the sequence of children of \a nodePtr. Thereby, removeBlock() takes
2319 * care, that the newly included full children of \a nodePtr form
2320 * a consecutive sequence with the already existing pertinent children of
2321 * \a nodePtr. The partial node itself is deleted afterwards.
2322 */
2327 {
2328 /*
2329 For every
2330 partial child we keep a set of pointers. Since there are at most
2331 two partial children, we initialize two sets. Every set contains
2332 besides a pointer to the partial child four pointers to its endmost
2333 children, sorted according to their full or empty labels and pointers
2334 to the immediate siblings of the partial child, also sorted according
2335 to their full or empty labels.
2336 */
2337 ///Pointer to the first partial child
2340 /*
2341 Pointer to the full endmost child (more
2342 precisely: to the endmost child appearing on the full side) of
2343 [[partial_1]]. In case that ignored nodes are used, this [[endfull_1]]
2344 may store the adress of an ignored node.
2345 */
2348 /*
2349 Pointer to the empty endmost child (more
2350 precisely: to the endmost child appearing on the empty side) of
2351 [[partial_1]]. In case that ignored nodes are used, this [[endempty_1]]
2352 may store the adress of an ignored node.
2353 */
2356 /*
2357 Pointer to the first {\it non ignored} node
2358 with full status. [[realfull_1]] is identical to [[endfull_1]] if no
2359 ignored nodes appear at the full end of the first partial child.
2360 */
2363 /*
2364 Pointer to the first {\it non ignored} node
2365 with empty status. [[realempty_1]] is identical to [[endempty_1]] if no
2366 ignored nodes appear at the empty end of the first partial child.
2367 */
2370 // Pointer to the second partial child.
2373 /*
2374 Pointer to the full endmost child (more
2375 precisely: to the endmost child appearing on the full side) of
2376 [[partial_2]]. In case that ignored nodes are used, this [[endfull_2]]
2377 may store the adress of an ignored node.
2378 */
2381 /*
2382 Pointer to the empty endmost child (more
2383 precisely: to the endmost child appearing on the empty side) of
2384 [[partial_2]]. In case that ignored nodes are used, this [[endempty_2]]
2385 may store the adress of an ignored node.
2386 */
2389 /*
2390 Pointer to the first {\it non ignored} node
2391 with empty status. [[realempty_2]] is identical to [[endempty_2]] if no
2392 ignored nodes appear at the empty end of the first partial child.
2393 */
2396 /*
2397 Pointer to a full sibling of
2398 [[partial_1]], if it exists. In case that ignored nodes are used
2399 this [[sibfull_1]] stores the direct sibling of [[partial_1]]
2400 on the side where the full siblings are. Hence [[sibfull_1]] may
2401 store an ignored node.
2402 */
2405 /*
2406 Pointer to a partial sibling of
2407 [[partial_1]], if it exists. In case that ignored nodes are used
2408 this [[sibpartial_1]] stores the direct sibling of [[partial_1]]
2409 on the side where a partial sibling is. Hence [[sibpartial_1]] may
2410 store an ignored node.
2411 */
2414 /*
2415 Pointer to an empty sibling of
2416 [[parial_1]], if it exists. In case that ignored nodes are used
2417 this [[sibempty_1]] stores the direct sibling of [[partial_1]]
2418 on the side where the empty siblings are. Hence [[sibempty_1]] may
2419 store an ignored node.
2420 */
2423 /*
2424 Pointer only used in case that [[partial_1]] has
2425 no non-ignored siblings on one side. [[partial_1]] then is endmost child
2426 of [[nodePtr]], but ignored children may appear between [[partial_1]]
2427 and the end of sequence of children of [[nodePtr]]. The
2428 [[nonstatussib_1]] then stores the adress of the endmost ignored child.
2429 Observe that it is not valid for a $Q$-node to have only one
2430 non-ignored child and several ignored children. Hence this situation
2431 is only allowed to appear {\bf once} on one side of [[partial_1]].
2432 Every other situation results in an error message.
2433 */
2436 /*
2437 Pointer to a full sibling of
2438 [[partial_2]], if it exists. In case that ignored nodes are used
2439 this [[sibfull_2]] stores the direct sibling of [[partial_2]]
2440 on the side where the full siblings are. Hence [[sibfull_2]] may
2441 store an ignored node.
2442 */
2445 /*
2446 Pointer to a partial sibling of
2447 [[partial_2]], if it exists. In case that ignored nodes are used
2448 this [[sibpartial_2]] stores the direct sibling of [[partial_2]]
2449 on the side where a partial sibling is. Hence [[sibpartial_2]] may
2450 store an ignored node.
2451 */
2454 /*
2455 Pointer to an empty sibling of
2456 [[parial_2]], if it exists. In case that ignored nodes are used
2457 this [[sibempty_2]] stores the direct sibling of [[partial_2]]
2458 on the side where the empty siblings are. Hence [[sibempty_2]] may
2459 store an ignored node.
2460 */
2463 /*
2464 Pointer only used in case that [[partial_2]] has
2465 no non-ignored siblings on one side. [[partial_2]] then is endmost child
2466 of [[nodePtr]], but ignored children may appear between [[partial_2]]
2467 and the end of sequence of children of [[nodePtr]]. The
2468 [[nonstatussib_2]] then stores the adress of the endmost ignored child.
2469 Observe that it is not valid for a $Q$-node to have only one
2470 non-ignored child and several ignored children. Hence this situation
2471 is only allowed to appear {\bf once} on one side of [[partial_2]].
2472 Every other situation results in an error message.
2473 */
2482 /*
2483 [[endmostcheck]] is [[1]], if [[partial_1]] is the endmost
2484 child of [[nodePtr]]. Per default, [[endmostcheck]] is [[0]].
2485 */
2494 // Get a partial child.
2495 {
2498 // Get the full and empty
2499 // endmost children of the
2500 // partial child [[partial_1]].
2504 {
2507 }
2509 // partial child with no full endmost child detected?
2514 }
2517 {
2520 }
2522 // partial child with no empty endmost child detected?
2527 }
2529 // Get the immediate
2530 // siblings of the partial
2531 // child [[partial_1]].
2533 {
2540 }
2541 else
2545 {
2552 }
2554 // partial child detected with no siblings of valid status?
2557 }
2558 }
2562 // There is a second partial child.
2563 {
2565 // Get the full and empty endmost
2566 // children of the partial
2567 // child [[partial_2]].
2572 {
2574 }
2576 // partial child with no full endmost child detected?
2580 }
2583 {
2586 }
2588 // partial child with no empty endmost child detected?
2593 }
2594 // Get the immediate siblings
2595 // of the partial child
2596 // [[partial_2]].
2598 {
2605 }
2606 else
2611 {
2618 }
2622 }
2623 }
2628 /*
2629 Connect the endmost
2630 children of the partial children [[partial_1]] and [[partial_2]] correctly
2631 with their new siblings. In doing this, all children of the partial
2632 children become children of [[nodePtr]]. The reader should observe that
2633 the parent pointers of the interior children of [[partial_1]] and
2634 [[partial_2]] are not updated in order to hit the linear time complexity.
2636 When including the children of the partial children to the children
2637 of [[nodePtr]], it is taken care that all full children
2638 form a consecutive sequence afterwards. If neccessary the pointers to the
2639 endmost children of [[nodePtr]] are updated.
2640 */
2641 {
2643 // There are full children between
2644 // the 2 partial nodes.
2645 // Connect the full children
2646 // between the 2 partial children
2647 // with the full endmost children
2648 // of the 2 partial nodes.
2649 {
2654 }
2657 // There are no full children between
2658 // the 2 partial nodes. Connect the
2659 // full endmost children of the
2660 // partial nodes as siblings.
2661 {
2663 // Regular Case.
2664 {
2667 }
2668 // Only ignored children between
2669 // partial_1 and partial_2.
2670 else
2671 {
2676 }
2678 }
2679 // Include the children of the
2680 // partial children with their
2681 // full nodes inbetween into
2682 // the sequence of the children of
2683 // Q-node nodePtr.
2685 // partial_1 is endmost child of
2686 // nodePtr. Make the empty endmost
2687 // child of partial_1 be the new
2688 // endmost child of nodePtr.
2689 {
2691 // Regular case.
2692 {
2694 }
2695 else
2696 // Only ignored children between
2697 // partial_1 and one end of nodePtr.
2698 {
2701 }
2704 }
2706 else
2707 // partial_1 is not endmost child.
2708 {
2711 }
2715 // partial_2 is endmost child of
2716 // nodePtr. Make the empty endmost
2717 // child of partial_2 be the new
2718 // endmost child of nodePtr.
2719 {
2721 // Regular case.
2722 {
2724 }
2725 else
2726 // Only ignored children between
2727 // partial_1 and one end of
2728 // nodePtr.
2729 {
2732 }
2735 }
2737 else
2738 // partial_2 is not endmost child.
2739 {
2742 }
2744 // Copy the full children of
2745 // partial_1 and partial_2 to
2746 // nodePtr.
2748 {
2751 }
2757 {
2760 }
2764 }
2769 /*
2770 Connect the endmost
2771 children of the partial child [[partial_1]] correctly
2772 with their new siblings. In doing this, all children of the partial
2773 child become children of [[nodePtr]]. The reader should observe that
2774 the parent pointers of the interior children of [[partial_1]]
2775 are not updated in order to hit the linear time complexity.
2777 When including the children of [[partial_1]] to the children
2778 of [[nodePtr]], it is taken care that all full children
2779 form a consecutive sequence afterwards. If necessary the pointers to the
2780 endmost children of [[nodePtr]] are updated.
2781 */
2783 {
2786 // partial_1 is endmost child.
2790 // There are full children on one
2791 // side of the partial node.
2792 // Connect the full children with
2793 // the full endmost child of
2794 // partial_1.
2795 {
2798 }
2801 // There are not any full children
2802 // and partial_1 is not endmost.
2803 // So get the 2nd empty sibling
2804 // of partial_1 and connect it
2805 // to the full endmost child
2806 // of partial_1.
2807 {
2810 else
2815 }
2817 else
2818 // partial_1 is endmost child
2819 // and there are no full children.
2820 // Make the full endmost child of
2821 // partial_1 be the endmostchild
2822 // of nodePtr.
2823 {
2826 // Regular case.
2827 {
2829 }
2830 else
2831 // Only ignored children between
2832 // partial_1 and one end of
2833 // nodePtr.
2834 {
2837 }
2841 }
2844 // There are no empty children.
2845 // partial_1 is endmost child of
2846 // nodePtr. Make the empty endmost
2847 // child of partial_1 be the new
2848 // endmost child of nodePtr.
2849 {
2851 // Regular case.
2852 {
2854 }
2855 else
2856 // Only ignored children between
2857 // partial_1 and one end of
2858 // nodePtr.
2859 {
2862 }
2865 }
2867 else
2868 // There are empty children. So
2869 // connect the empty endmost child
2870 // of partial_1 with sibempty_1.
2871 {
2874 }
2877 {
2880 }
2885 }
2886 // else nodePtr does not have partial children. Then nothing is to do.
2887 }
2890 /************************************************************************
2891 removeChildFromSiblings
2892 ************************************************************************/
2894 /**
2895 * The function removeChildFromSiblings() removes the node \a nodePtr from
2896 * the doubly linked list of its parent. In case that \a nodePtr is endmost
2897 * child of an Q-node or child of a P-node equiped with a valid
2898 * reference pointer \a referenceParent to its parent (see PQNode),
2899 * these pointers are considered as
2900 * well and the adjacent siblings of \a nodePtr have to cover
2901 * \a nodePtr's task.
2902 */
2906 {
2908 {
2909 /*
2910 Checksif [[nodePtr]] is connected with its parent via the reference
2911 pointers (see \ref{PQNode}). If so, the next sibling of [[nodePtr]]
2912 will be the the new reference child.
2913 */
2919 }
2921 {
2922 /*
2923 Check if [[nodePtr]] is the endmost child of a $Q$-node.
2924 If so, the next sibling of [[nodePtr]] will be the the new endmost
2925 child of the $Q$-node. Observe that the sibling then gets a valid
2926 pointer to its parent.
2927 */
2935 }
2937 /*
2938 Remove [[nodePtr]] from its immediate siblings and links the
2939 siblings via the [[sibRight]] and [[sibLeft]] pointers.
2940 */
2942 {
2946 // Sibling was not connected to child?
2949 }
2950 }
2952 {
2956 // Sibling was not connected to child?
2959 }
2960 }
2964 }
2967 /************************************************************************
2968 removeNodeFromTree
2969 ************************************************************************/
2971 /**
2972 * The function removeNodeFromTree() has to be handled with great care by
2973 * the user. This function is not used in any of the functions of
2974 * the class template PQTree and can only be accessed by inheritance.
2975 *
2976 * Its objective is to remove a node \a child from the PQ-tree. To do so,
2977 * the \a parent of the node \a child has to be known by the user.
2978 * To indicate this, the parent has to be handed over by her.
2979 *
2980 * <b>This function does not check if \a parent is the parent node of
2981 * \a child</b>. This has to be guaranteed by the user. The reason for
2982 * this riscfull approach lies in the details of the powerful data structure
2983 * PQ-tree. In order to reach linear runtime, the internal children
2984 * of a Q-node normally do not have valid parent pointers. So forcing
2985 * this function to search the parent would cost in worst case
2986 * linear runtime for one call of the function removeNodeFromTree().
2987 * Its up to the user to do better.
2988 *
2989 * Calling removeNodeFromTree() with a 0-pointer for \a parent,
2990 * will always terminate this function with an ERROR-message and returning
2991 * -1 as value.
2992 *
2993 * The return value is an integer value used to indicate how many children
2994 * the \a parent after the removal of \a child still has. The client should
2995 * observe that internal nodes in the PQ-tree which have just one or
2996 * no children at all do not make sense. However, the function
2997 * removeNodeFromTree() <b>does not check if \a parent has less than
2998 * two children after the removal of \< child</b>.
2999 * So in case that \a parent has less than two children, the user has to check
3000 * this by herself and remove the \a parent, probably using the function
3001 * checkIfOnlyChild().
3002 *
3003 * There are two reasons why the function removeNodeFromTree() does
3004 * not check if \a parent has less than two children after the removal
3005 * of \a child:
3006 * -# The user might keep the node in the tree in order to add new nodes
3007 * as children to it.
3008 * -# Again, the parent of \a parent might not be known to \a parent,
3009 * hence removeNodeTree() would have to search, at the cost of linear time
3010 * consumption, for the parent of \a parent first before removing
3011 * \a parent from the tree.
3012 *
3013 * Observe that removeNodeFromTree() does not free the allocated
3014 * memory of \a child. This has to be done by the user \b after calling
3015 * removeNodeFromTree(). It also offers the opportunity to reuse
3016 * deleted nodes. Observe that the identification number of a node
3017 * \a m_identificationNumber (see PQNode) cannot be changed.
3018 */
3022 {
3024 {
3030 }
3031 else
3032 {
3033 //parent is invalid 0-pointer.
3035 }
3036 }
3039 /************************************************************************
3040 sortExceptions
3041 ************************************************************************/
3043 /**
3044 * The function sortExceptions() is only called by the function frontExcept().
3045 * It sorts the exceptions before frontExcept()
3046 * scans the frontier.
3047 */
3051 {
3054 {
3057 {
3059 {
3062 }
3063 }
3064 }
3065 }
3068 /************************************************************************
3069 templateL1
3070 ************************************************************************/
3072 /**
3073 * The function templateL1() implements the template matching for
3074 * leaves.
3075 * The function requires as input any pointer to a node stored in
3076 * \a nodePtr. If the node stored in \a nodePtr is a PQLeaf,
3077 * templateL1() considers itself responsible for the node and will
3078 * apply the template matching for pertinent leaves to \a nodePtr.
3079 * If the flag \a isRoot is set to 1, it signalizes
3080 * templateL1() that \a nodePtr is the root of
3081 * the pertinent subtree. In any other case the flag has to be 0.
3082 *
3083 * If templateL1() was responsible for \a nodePtr and the
3084 * reduction was successful, the return value is 1. Otherwise
3085 * the return value is 0.
3086 *
3087 * The function updates the \a fullChildren stack of its parent, as long as
3088 * \a nodePtr is not the root of the pertinent subtree.
3089 * Observe that \a nodePtr needs a valid pointer to its parent. This
3090 * can be achieved by using the function Bubble() or any other
3091 * appropriate, user defined function.
3092 */
3096 {
3098 {
3102 }
3105 }
3108 /************************************************************************
3109 templateP1
3110 ************************************************************************/
3112 /**
3113 * The function templateP1() implements the template matching for
3114 * P-nodes with only full children.
3115 * The function requires as input any pointer to a node stored in
3116 * \a nodePtr. If the node stored in \a nodePtr is a P-node with
3117 * only full children,
3118 * templateP1() considers itself responsible for the node and will
3119 * apply the template matching for full P-nodes to \a nodePtr.
3120 * If the flag \a isRoot is set to 1, it signalizes
3121 * templateP1() that \a nodePtr is the root of
3122 * the pertinent subtree. In any other case the flag has to be 0.
3123 *
3124 * If templateP1() was responsible for \a nodePtr and the
3125 * reduction was successful, the return value is 1. Otherwise
3126 * the return value is 0.
3127 *
3128 * If the P-node is not the root of the pertinent subtree,
3129 * the \a fullChildren stack of the parent of \a nodePtr is updated.
3130 * If the P-node is the root of the pertinent subtree, nothing has to
3131 * be done.
3132 */
3136 {
3140 else
3141 {
3147 }
3148 }
3151 /************************************************************************
3152 templateP2
3153 ************************************************************************/
3155 /**
3156 * The function templateP2() implements the template matching for a
3157 * P-node with full \b and empty children that is the root of
3158 * the pertinent subtree.
3159 * The function requires as input any pointer to a node stored in
3160 * \ nodePtr. If the node stored in \a nodePtr is a P-node with
3161 * no partial children,
3162 * templateP2() considers itself responsible for the node and will
3163 * apply the template matching \b P2 to \a nodePtr.
3164 * Observe that the user calling this function has to make sure that
3165 * \a nodePtr is partial and is the root of the pertinent subtree.
3166 *
3167 * If templateP2() was responsible for \a nodePtr and the
3168 * reduction was successful, the return value is 1. Otherwise
3169 * the return value is 0.
3170 *
3171 * The function templateP2() creates a new full P-node that
3172 * will be the new root of the pertinent subtree. It then copies all full
3173 * children from \a nodePtr to the new root of the pertinent subtree.
3174 */
3178 {
3185 // Gather all full children of nodePtr
3186 // as children of the new P-node.
3187 // Delete them from nodePtr.
3190 // Correct parent-pointer and
3191 // sibling-pointers of the new P-node.
3199 // The new P-node now is the root of
3200 // the pertinent subtree.
3204 }
3207 /************************************************************************
3208 templateP3
3209 ************************************************************************/
3211 /*
3212 * The function templateP3() implements the template matching for a
3213 * P-node with full \b and empty children that is \b not the root of
3214 * the pertinent subtree.
3215 * The function requires as input any pointer to a node stored in
3216 * \ nodePtr. If the node stored in \a nodePtr is a P-node with
3217 * no partial children,
3218 * templateP3() considers itself responsible for the node and will
3219 * apply the template matching \b P3 to \a nodePtr.
3220 * Observe that the user calling this function has to make sure that
3221 * \a nodePtr is partial and is not the root of the pertinent subtree.
3222 *
3223 * If templateP3() was responsible for \a nodePtr and the
3224 * reduction was successful, the return value is 1. Otherwise
3225 * the return value is 0.
3226 *
3227 * The function templateP3() creates
3228 * a new full P-node, stored in \a newPnode and copies the full children
3229 * of \a nodePtr to \a newPnode. \a nodePtr keeps all empty children
3230 * and will be labeled empty. A new partial Q-node will be created and stored
3231 * in \a newQnode. \a newQnode is placed at the position of \a nodePtr
3232 * in the tree and gets two children: \a nodePtr itself and the newly
3233 * created \a newPnode.
3234 *
3235 * The function templateP3() uses a few variables.
3236 * - \a newPnode is the pointer to the new P-node, or, in case
3237 * that \a nodePtr has only one full child, is the pointer of this child.
3238 * - \a newQnode is the pointer to the new Q-node.
3239 * - \a newNode is used for the proper allocation of the new
3240 * Q-node.
3241 * - \a emptyNode is a pointer to any empty child of nodePtr.
3242 */
3246 {
3250 /*
3251 Create a new partial $Q$-node stored in [[newQnode]].
3252 It replaces [[nodePtr]] by the Q-node [[newQnode]] in the $PQ$-tree
3253 and makes [[nodePtr]] endmost child of [[newQnode]].
3254 This is done by updating parent-pointers and sibling-pointers.
3255 */
3256 PQInternalNode<T,X,Y> *newNode = OGDF_NEW PQInternalNode<T,X,Y>(m_identificationNumber++,PQNodeRoot::QNode,PQNodeRoot::PARTIAL);
3267 /*
3268 Create a new full $P$-node stored in [[newPnode]].
3269 It copies the full children of [[nodePtr]] to [[newPnode]].
3270 The new $P$-node will then be included into the tree as child of
3271 the new $Q$-node [[newQnode]].
3272 */
3274 {
3281 // Update newQnode.
3284 // Update sibling pointers.
3289 }
3291 // Check if nodePtr contains
3292 // only one son. If so, nodePtr
3293 // will be deleted from the tree.
3296 // Update partialchildren stack of
3297 // the parent of the new Q-node.
3301 }
3304 /************************************************************************
3305 templateP4
3306 ************************************************************************/
3308 /**
3309 * The function templateP4() implements the template matching for a
3310 * P-node with full, empty and exactly one partial children. The
3311 * P-node has to be the root of the pertinent subtree.
3312 * The function requires as input any pointer to a node stored in
3313 * \a nodePtr. If the node stored in \a nodePtr is a P-node with
3314 * one partial child,
3315 * templateP4() considers itself responsible for the node and will
3316 * apply the template matching \b P4 to \a nodePtr.
3317 * Observe that the user calling this function has to make sure that
3318 * \a nodePtr is the root of the pertinent subtree.
3319 *
3320 * If templateP4() was responsible for \a nodePtr and the
3321 * reduction was successful, the return value is 1. Otherwise
3322 * the return value is 0.
3323 *
3324 * The function templateP4() creates a new full P-node, if neccessary,
3325 * and copies the full children of \a nodePtr to this P-node.
3326 * The new P-node then is made endmost child of \a partialChild.
3327 * The node \a partialChild is used to store the adress of the partial
3328 * child of \a nodePtr.
3329 * The \a partialChild itself stays child of \a nodePtr.
3330 * Most of the here described action is done in the function
3331 * copyFullChildrenToPartial().
3332 */
3336 {
3343 // If nodePtr does not have any
3344 // empty children, then it has to
3345 // be deleted and the partial node
3346 // is occupying its place in the tree.
3348 // The partial child now is
3349 // root of the pertinent subtree.
3353 }
3356 /************************************************************************
3357 templateP5
3358 ************************************************************************/
3360 /**
3361 * The function templateP5() implements the template matching for a
3362 * P-node with full, empty children and exactly one partial child. The
3363 * P-node is not allowed to be the root of the pertinent subtree.
3364 * The function requires as input any pointer to a node stored in
3365 * \a nodePtr. If the node stored in \a nodePtr is a P-node with
3366 * one partial child,
3367 * templateP5() considers itself responsible for the node and will
3368 * apply the template matching \b P5 to \a nodePtr.
3369 * Observe that the user calling this function has to make sure that
3370 * \a nodePtr is not the root of the pertinent subtree.
3371 *
3372 * If templateP5() was responsible for \a nodePtr and the
3373 * reduction was successful, the return value is 1. Otherwise
3374 * the return value is 0.
3375 *
3376 * The function templateP5() uses a few variables.
3377 * - \a partialChild is a pointer to the partial child of
3378 * \a nodePtr.
3379 * - \a checkNode is a pointer to the endmost empty child of
3380 * \a partialChild.
3381 * - \a emptyNode is a pointer to the empty node that is copied as
3382 * endmost child to \a partialChild.
3383 * - \a emptyChildCount stores the number of empty children of
3384 * \a nodePtr.
3385 *
3386 * If neccessary, the function templateP5() creates a new full P-node
3387 * and copies all full children of \a nodePtr to this new full P-node.
3388 * All empty children of \a nodePtr stay empty children of \a nodePtr.
3389 *
3390 * The new full P-node and \a nodePtr will be the new endmost children of
3391 * \a partialChild. The \a partialChild then occupies the position
3392 * of \a nodePtr in the PQ-tree.
3393 */
3397 {
3402 /*
3403 Remove [[partialChild]] from the children of [[nodePtr]]. The node
3404 [[partialChild]] then occupies the position of [[nodePtr]] in the
3405 $PQ$-tree which is done in the function call [[exchangeNodes]]
3406 (\ref{exchangeNodes}). The chunk then removes all full children from
3407 [[nodePtr]] and adds them as children of a new $P$-node as endmost
3408 child of [[partialChild]]. This is done in the function call
3409 [[copyFullChildrenToPartial]] (\ref{copyFullChildrenToPartial}).
3410 When this chunk has finished, [[nodePtr]] has only empty children.
3411 */
3421 {
3422 /*
3423 Check if [[nodePtr]] has just one empty child. If so, the child
3424 is stored in [[emptyNode]] in order to be added to the empty
3425 side of the partial $Q$-node [[partialChild]]. If [[nodePtr]]
3426 has more than one empty child, [[nodePtr]] is stored in
3427 [[emptyNode]] in order to be added to the empty
3428 side of the partial $Q$-node [[partialChild]].
3429 */
3432 {
3439 }
3441 /*
3442 Check at which side of [[partialChild]]
3443 the empty children hide. [[emptyNode]] stores the empty node
3444 that is added to the empty side of [[partialChild]].
3445 */
3448 {
3451 }
3453 // Endmostchild not found?
3458 }
3464 }
3465 // If nodePtr did not have any empty
3466 // children it has to be deleted.
3471 }
3474 /************************************************************************
3475 templateP6
3476 ************************************************************************/
3478 /**
3479 * The function templateP6() implements the template matching for a
3480 * P-node with full, empty and exactly two partial children. The
3481 * P-node must be the root of the pertinent subtree.
3482 * The function requires as input any pointer to a node stored in
3483 * \a nodePtr. If the node stored in \a nodePtr is a P-node with
3484 * two partial children,
3485 * templateP6() considers itself responsible for the node and will
3486 * apply the template matching \b P6 to \a nodePtr.
3487 * Observe that the user calling this function has to make sure that
3488 * \a nodePtr is the root of the pertinent subtree.
3489 *
3490 * If templateP6() was responsible for \a nodePtr and the
3491 * reduction was successful, the return value is 1. Otherwise
3492 * the return value is 0.
3493 *
3494 * The function templateP6() creates, if neccessary,
3495 * a new full P-node and copies all the full children of \a nodePtr
3496 * to the new full P-node, whereas all empty children stay children of
3497 * \a nodePtr. The new P-node will be copied to one of the partial children
3498 * as endmost child of this partial node. The children of the second
3499 * partial node are copied to the first one, such that the pertinent nodes
3500 * form a consecutive sequence.
3501 *
3502 * The following variables are used in the function templateP6().
3503 * - \a partial_1 is a pointer to the first partial child of
3504 * \a nodePtr.
3505 * - \a partial_2 is a pointer to the second partial child of
3506 * \a nodePtr.
3507 * - \a fullEnd_1 is a pointer to a full endmost child of \a partial_1.
3508 * - \a fullEnd_2 is a pointer to a full endmost child of \a partial_2.
3509 * - \a emptyEnd_2 is a pointer to the empty endmost child (more
3510 * precisely: to the endmost child appearing on the empty side) of
3511 * \a partial_2. In case that <em>ignored nodes</em> are used, this
3512 * \a emptyEnd_2 may store the adress of an ignored node.
3513 * - \a realEmptyEnd_2 is a pointer to the first <em>non ignored</em>
3514 * node with empty status on the empty side of \a partial_2. In case
3515 * that no ignored nodes are used, \a realEmpty_2 is identical to
3516 * \a endEmpty_2.
3517 */
3521 {
3522 //PQNode<T,X,Y> *partial_1 = 0;
3523 //PQNode<T,X,Y> *partial_2 = 0;
3524 //PQNode<T,X,Y> *fullEnd_1 = 0;
3525 //PQNode<T,X,Y> *fullEnd_2 = 0;
3526 //PQNode<T,X,Y> *emptyEnd_2 = 0;
3527 //PQNode<T,X,Y> *realEmptyEnd_2 = 0;
3533 /*
3534 Get the partial children of [[nodePtr]] and removes the second
3535 partial child stored in [[partial_2]] from the children of
3536 [[nodePtr]]. If there are any full children of [[nodePtr]], the
3537 chunk removes them from the children of [[nodePtr]] and copies them
3538 as children to a new $P$-node. This new $P$-node is then made
3539 endmost child of [[partial_1]].
3540 */
3548 /*
3549 Check the endmost children of the two partial children of [[nodePtr]]
3550 and stores them at approriate places, remembering what kind of type
3551 the endmost children are.
3552 */
3557 // partial child with no FULL endmost child detected?
3560 }
3568 // partial child with no FULL or EMPTY endmost child detected?
3573 }
3578 // partial child with no FULL or EMPTY endmost child detected?
3583 }
3586 //partial child with same type of endmost child detected
3588 /*
3589 The children of [[partial_2]] are removed from their parent and
3590 added as children to [[partial_1]]. This is done by resetting the
3591 sibling pointers of the two endmost children of [[partial_1]] and
3592 [[partial_2]] and the endmost child pointers of [[partial_1]].
3593 Observe that the parent pointers are not updated. The node
3594 [[partial_2]] is deleted.
3595 */
3601 else
3616 // If nodePtr does not have any
3617 // empty children, then it has to
3618 // be deleted and the partial node
3619 // is occupying its place in the tree.
3621 // partial_1 is now root of the
3622 // pertinent subtree.
3626 }
3629 /************************************************************************
3630 templateQ1
3631 ************************************************************************/
3633 /**
3634 * The function templateQ1() implements the template matching for
3635 * Q-nodes with only full children.
3636 * The function requires as input any pointer to a node stored in
3637 * \a nodePtr. If the node stored in \a nodePtr is a Q-node with
3638 * only full children,
3639 * templateQ1() considers itself responsible for the node and will
3640 * apply the template matching for full Q-nodes to \a nodePtr.
3641 * If the flag \a isRoot is set to 1, it signalizes
3642 * templateQ1() that \a nodePtr is the root of
3643 * the pertinent subtree. In any other case the flag has to be 0.
3644 *
3645 * If templateQ1() was responsible for \a nodePtr and the
3646 * reduction was successful, the return value is 1. Otherwise
3647 * the return value is 0.
3648 *
3649 * Different to the templateP1() for P-nodes,
3650 * this function is not able to check if Q-node is full by comparing
3651 * the number of children with the number of full children. The reason
3652 * is the application of the \a m_pseudoRoot at certain steps in the
3653 * matching algorithm. This \a m_pseudoRoot is used instead of the real
3654 * root of the pertinent subtree in case that no parent pointer was
3655 * found. But this implies that changing the number of the children of
3656 * the pertinent root is not registered by the pertinent root. Hence we
3657 * are not allowed to use the \a childCount of Q-nodes.
3658 */
3662 {
3667 {
3671 {
3676 }
3677 }
3680 }
3683 /************************************************************************
3684 templateQ2
3685 ************************************************************************/
3687 /**
3688 * The function templateQ2() implements the template matching for
3689 * Q-nodes with a pertinent
3690 * sequence of children on one side of the Q-node.
3691 * The function requires as input any pointer to a node stored in
3692 * \a nodePtr. If the node stored in \a nodePtr is a Q-node with
3693 * a pertinent
3694 * sequence of children on one side of the Q-node,
3695 * templateQ2() considers itself responsible for the node and will
3696 * apply the template matching \b Q2 to \a nodePtr.
3697 * If the flag \a isRoot is set to 1, it signalizes
3698 * templateQ2() that \a nodePtr is the root of
3699 * the pertinent subtree. In any other case the flag has to be 0.
3700 *
3701 * If templateQ2() was responsible for \a nodePtr and the
3702 * reduction was successful, the return value is 1. Otherwise
3703 * the return value is 0.
3704 *
3705 * Below a short description is given of all different cases that
3706 * may occure and that are handled by the function templateQ2(), \b regardless
3707 * whether the Q-node \a nodePtr is root of the pertinent subtree or not.
3708 * The description is somewhat trunkated and should be understood as a
3709 * stenographic description of the labels of the children of \a nodePtr
3710 * when running through the children from one side to the other. Of course
3711 * we leave the mirror-images out.
3712 * - full, empty
3713 * - full, partial, empty
3714 * - full, partial
3715 * - partial, empty.
3716 *
3717 * templateQ2() uses the following variables.
3718 * - \a fullNode is a pointer to the full endmost child of \a nodePtr.
3719 * - \a sequenceBegin is a pointer to the first node of the
3720 * sequence of full children. Identical to the node fullNode and
3721 * mainly needed by the function checkChain().
3722 * - \a sequenceEnd is a pointer to the last node of the sequence
3723 * of full children. Is set by the function checkChain().
3724 * - \a partialChild is a pointer to the partial child of \a nodePtr.
3725 * - \a sequenceCons is 1 if all full children of
3726 * \a nodePtr form a consecutive sequence with one full child beeing
3727 * an endmost child of \a nodePtr \b and the partial child is
3728 * adjacent to the sequence.
3729 *
3730 * templateQ2() first checks if one of the above mentioned cases
3731 * occures and
3732 * then applies the necessary template matching.
3733 * No special action has to be performed for the full nodes. If there exists
3734 * a partial child that will be stored in \a partialChild, its children
3735 * are made children of \a nodePtr. So to say, \a partialChild is lifted
3736 * up to the Q-node \a nodePtr and the occurance of the children
3737 * of \a partialChild is fixed within the children of \a nodePtr.
3738 * (Remember that a partial child is also a Q-node).
3739 */
3743 {
3750 {
3751 /*
3752 Get a full endmost child of
3753 the $Q$-node [[nodePtr]] if there exists one.
3754 */
3757 {
3761 }
3763 {
3767 }
3769 /*
3770 In case that a full endmost child of [[nodePtr]] exists, this
3771 child has been stored in [[fullNode]] and the chunk checks by
3772 calling the function [[checkChain]] (\ref{checkChain}), if all
3773 full children of [[nodePtr]] form a consecutive sequence.
3774 In case that the full children
3775 of [[nodePtr]] form a consecutive sequence the
3776 return value of [[checkChain]] is [[1]]. If a partial child
3777 stored in [[partialChild]] exists, the chunk checks if
3778 [[partialChild]] is adjacent to the sequence of full children.
3779 If the latter case is [[1]], the flag [[sequenceCons]] is
3780 set to [[1]] and the function [[templateQ2]] is allowed to
3781 reduce the pertient children of [[nodePtr]].
3782 */
3789 {
3796 }
3797 }
3798 else
3799 {
3801 {
3802 /*
3803 If the $Q$-node [[nodePtr]] has no full children but one
3804 partial child this chunk checks, if the partial child is
3805 endmost child of the [[nodePtr]]. If this is not the case,
3806 [[nodePtr]] cannot be reduced by the template matching
3807 {\bf Q2}.
3808 */
3809 //nodePtr->partialChildren->startAtBottom();
3810 //partialChild = nodePtr->partialChildren->readNext();
3815 }
3816 }
3822 }
3825 /************************************************************************
3826 templateQ3
3827 ************************************************************************/
3829 /*
3830 * The function templateQ3() implements the template matching for
3831 * Q-nodes with empty and/or partial children at both ends and a sequence
3832 * of full and/or partial children in the middle. The Q-node must be the
3833 * root of the pertinent subtree.
3834 * The function requires as input any pointer to a node stored in
3835 * \a nodePtr. If the node stored in \a nodePtr is a Q-node
3836 * with empty and/or partial children at both ends and a sequence
3837 * full or partial children in the middle,
3838 * templateQ3() considers itself responsible for the node and will
3839 * apply the template matching \b Q3 to \a nodePtr.
3840 * Observe that the user calling this function has to make sure that
3841 * \a nodePtr is the root of the pertinent subtree.
3842 *
3843 * If templateQ3() was responsible for \a nodePtr and the
3844 * reduction was successful, the return value is 1. Otherwise
3845 * the return value is 0.
3846 *
3847 * Below a short description is given of all different cases that
3848 * may occure and are handled by the function templateQ3(), \b regardless
3849 * whether the Q-node \a nodePtr is the root of the pertinent subtree or not.
3850 * The description is somewhat trunkated and should be understood as a
3851 * stenographic description of the labels of the children of \a nodePtr
3852 * when running through the children from one side to the other. Of course
3853 * we leave the mirror-images out.
3854 * - empty, full, empty
3855 * - empty, partial, full, partial, empty
3856 * - empty, partial, full, empty
3857 * - empty, partial, full, partial
3858 * - partial, full, partial
3859 * - empty, partial, partial, empty
3860 * - empty, partial, partial
3861 * - partial, partial
3862 *
3863 * The function templateQ3() uses the following variables.
3864 * - \a fullChild is a pointer to an arbitrary full child of \a nodePtr.
3865 * - \a fullStart is a pointer to the first full child of a
3866 * consecutive sequence of full children.
3867 * - \a fullEnd is a pointer to the last full child of a
3868 * consecutive sequence of full children.
3869 * - \a partial_1 is a pointer to the first partial child of \a nodePtr.
3870 * - \a partial_2 is a pointer to the second partial child of \a nodePtr.
3871 * - \a conssequence is 1 if the pertinent children of
3872 * \a nodePtr form a consecutive sequence with at most one partial
3873 * child at every end of the sequence.
3874 * - \a found is a help variable.
3875 *
3876 * templateQ3() first checks if one of the above mentioned cases
3877 * occures and then applies the neccessary template matching.
3878 * No special action has to be performed for the full nodes. If there exist
3879 * one or two partial children which will be stored in \a partial_1
3880 * or \a partial_2, their children
3881 * are made children of \a nodePtr. So to say, \a partial_1 and
3882 * partial_2 are lifted up to the Q-node \a nodePtr
3883 * and the occurance of their children
3884 * is fixed within the children of \a nodePtr.
3885 */
3889 {
3896 /*
3897 Check ifthe
3898 pertinent children of [[nodePtr]] form a consecutive sequence. We
3899 differ between two cases:
3900 \begin{enumerate}
3901 \item There exist full children of [[nodePtr]]. First check with
3902 the function [[checkChain]] (\ref{checkChain}) if the full children
3903 form a consecutive sequence. In case that the check was
3904 successful, check if each partial child is adjacent to a full child.
3905 If both checks were successful, the pertient children form a
3906 consecutive sequence.
3907 \item There do not exist full children. Check if the partial
3908 children (there are at most two of them) form a consecutive sequence.
3909 If the test was successful, the pertinent children form a
3910 consecutive sequence.
3911 */
3914 {
3915 /*
3916 A consecutive
3917 sequence of full children has been detected, containing all full
3918 children of [[nodePtr]]. The chunk checks if each partial child
3919 of [[nodePtr]] is adjacent to a full child. Observe that the
3920 function [[templateQ3]] only reaches this chunk when [[nodePtr]]
3921 has less than three partial children.
3922 */
3928 {
3931 {
3941 }
3942 }
3943 }
3946 {
3947 /*
3948 In case that the node [[nodePtr]] does not have any full children,
3949 this chunk checks if the partial children are adjacent.
3950 */
3957 }
3963 }
3966 }
3968 #endif