|
|||
|
|
|
|||
|
|
A PC-tree represents a set of cyclic orders of its leaves by labeling its inner nodes as either P- or C-node and allowing arbitrary permutations of the neighbors of P-nodes while only allowing flips of C-nodes. More...
#include <ogdf/basic/pctree/PCTree.h>
Inheritance diagram for ogdf::pc_tree::PCTree:Classes | |
| struct | LoggingObserver |
| struct | NextFullLeaf |
| struct | Observer |
| Interface for Observers that can be notified of all changes made to the tree during an update. More... | |
Public Member Functions | |
| PCTree () | |
| Constructs a new PCTree. More... | |
| PCTree (const PCTree &other, PCTreeNodeArray< PCNode * > &nodeMapping, bool keep_ids=false, PCTreeForest *forest=nullptr) | |
| Copy a PCTree. More... | |
| PCTree (const std::string &str, bool keep_ids=false, PCTreeForest *forest=nullptr) | |
Deserialize a PCTree from a string str as generated by operator<<(std::ostream&, const PCTree*) or PCTree::uniqueID(). More... | |
| PCTree (int leafNum, std::vector< PCNode * > *added=nullptr, PCTreeForest *forest=nullptr) | |
Convenience method generating a PCTree consisting of a single P-node with leafNum leaves, which are all copied to the optional list added. More... | |
| PCTree (PCTreeForest *forest) | |
Constructs a new PCTree that is part of forest and can thus be merged with any other PCTree of the same forest. More... | |
| virtual | ~PCTree () |
Getters | |
| operator const PCTreeRegistry & () const | |
| PCTreeForest * | getForest () const |
| The PCTreeForest this PCTree belongs to, or nullptr. More... | |
| bool | isTrivial () const |
| Whether this PCTree allows all orders (consists of a single P-node). More... | |
| const IntrusiveList< PCNode > & | getLeaves () const |
| size_t | getLeafCount () const |
| size_t | getPNodeCount () const |
| size_t | getCNodeCount () const |
| PCNode * | getRootNode () const |
| int | getTerminalPathLength () const |
| FilteringPCTreeDFS | allNodes () const |
| An iterable through all nodes of this PCTree. More... | |
| FilteringPCTreeDFS | innerNodes () const |
| An iterable through all inner (non-leaf) nodes of this PCTree. More... | |
| template<typename Container > | |
| void | currentLeafOrder (Container &container) const |
Store the order of leaves currently represented by this tree in container. More... | |
| std::vector< PCNode * > | currentLeafOrder () const |
| bool | checkValid (bool allow_small_deg=true) const |
| Validity check for debugging assertions. More... | |
| bool | isValidOrder (const std::vector< PCNode * > &order) const |
Check whether the order order is represented by this tree. More... | |
| void | getTree (ogdf::Graph &tree, ogdf::GraphAttributes *g_a, PCTreeNodeArray< ogdf::node > &pc_repr, ogdf::NodeArray< PCNode * > *g_repr=nullptr, bool mark_full=false, bool show_sibs=false) const |
| Get a graphical representation of this tree as Graph. More... | |
| void | getRestrictions (std::vector< std::vector< PCNode * >> &restrictions, PCNode *fixedLeaf=nullptr) const |
| Get a list of all cyclic restrictions used to generate this tree. More... | |
| template<typename R > | |
| R | possibleOrders () const |
| Calculate the number of cyclic orders represented by this tree. More... | |
| std::ostream & | uniqueID (std::ostream &os, const std::function< void(std::ostream &os, PCNode *, int)> &printNode=uid_utils::nodeToID, const std::function< bool(PCNode *, PCNode *)> &compareNodes=uid_utils::compareNodesByID) |
Print a deterministic and unique representation of this PCTree to os. More... | |
| std::string | uniqueID (const std::function< void(std::ostream &os, PCNode *, int)> &printNode=uid_utils::nodeToID, [[maybe_unused]] const std::function< bool(PCNode *, PCNode *)> &compareNodes=uid_utils::compareNodesByID) |
Private Attributes | |
| PCNode * | m_apexCandidate = nullptr |
| bool | m_apexCandidateIsFix = false |
| PCNode * | m_apexTPPred2 = nullptr |
| size_t | m_cNodeCount = 0 |
| bool | m_externalForest = true |
| PCNode * | m_firstPartial = nullptr |
| PCTreeForest * | m_forest = nullptr |
| PCNode * | m_lastPartial = nullptr |
| IntrusiveList< PCNode > | m_leaves |
| std::list< Observer * > | m_observers |
| size_t | m_partialCount = 0 |
| size_t | m_pNodeCount = 0 |
| PCNode * | m_rootNode = nullptr |
| size_t | m_terminalPathLength = 0 |
Friends | |
| std::ostream & | operator<<) (std::ostream &, const ogdf::pc_tree::PCNode *) |
| std::ostream & | operator<<) (std::ostream &, const ogdf::pc_tree::PCTree *) |
| class | PCNode |
| class | PCTreeForest |
| class | PCTreeRegistry |
Node creation / destruction | |
| PCNode * | newNode (PCNodeType type, PCNode *parent=nullptr, int id=-1) |
| Create a new node. More... | |
| void | destroyNode (PCNode *&node) |
| Destroy a node. More... | |
| void | destroyNode (PCNode *const &node) |
| Destroy a node. More... | |
| void | insertLeaves (int count, PCNode *parent, std::vector< PCNode * > *added=nullptr) |
Attach count leaves to P- or C-node parent and optionally store the new leaves in a vector added. More... | |
| void | replaceLeaf (int leafCount, PCNode *leaf, std::vector< PCNode * > *added=nullptr) |
Convert leaf into a P-node and attach leafCount new leaves to it. More... | |
| PCNode * | mergeLeaves (const std::vector< PCNode * > &consecutiveLeaves, bool assumeConsecutive=false) |
| Merge multiple leaves into a single one and return it. More... | |
| template<typename It > | |
| PCNode * | mergeLeaves (It begin, It end, bool assumeConsecutive=false) |
| Merge multiple leaves into a single one and return it. More... | |
| void | destroyLeaf (PCNode *leaf) |
| Remove a leaf and also any newly-introduced inner degree-2 or -1 nodes. More... | |
| PCNode * | setRoot (PCNode *newRoot) |
| Overwrite the stored root for this PC-tree. More... | |
| PCNode * | changeRoot (PCNode *newRoot) |
Change the orientation of edges such that newRoot becomes the root of the tree. More... | |
| PCNodeType | changeNodeType (PCNode *node, PCNodeType newType) |
| Change the type of a node and update all its registrations. More... | |
| void | insertTree (PCNode *at, PCTree *tree) |
Insert tree tree into this tree at node at. More... | |
| void | unregisterNode (PCNode *node) |
| void | registerNode (PCNode *node) |
Restrictions | |
| bool | isTrivialRestriction (int size) const |
| bool | makeConsecutive (std::initializer_list< PCNode * > consecutiveLeaves) |
| bool | makeConsecutive (const std::vector< PCNode * > &consecutiveLeaves) |
| template<typename It > | |
| bool | makeConsecutive (It begin, It end) |
Make the leaves contained in the range denoted by iterators begin (inclusive) to end (exclusive) consecutive in all represented orders. More... | |
| void | resetTempData () |
| Reset all makeConsecutive()-related temporary information, especially which leaves are full (should be made consecutive). More... | |
| template<typename It > | |
| void | markLeavesFull (It begin, It end) |
| Only marks leaves full, does not update partial/full info of parents. More... | |
| template<typename It > | |
| void | markFull (It begin, It end, std::vector< PCNode * > *fullNodeOrder=nullptr) |
Marks the leaves contained in the range denoted by iterators begin (inclusive) to end (exclusive) full, that is marked for being made consecutive in all represented orders. More... | |
| bool | makeFullNodesConsecutive () |
| Updates the tree to make all leaves marked as full consecutive in all represented orders. More... | |
| PCNode * | markFull (PCNode *full_node, std::vector< PCNode * > *fullNodeOrder=nullptr) |
| bool | findTerminalPath () |
| void | updateSingletonTerminalPath () |
| PCNode * | createCentralNode () |
| int | updateTerminalPath (PCNode *central, PCNode *tpNeigh) |
| void | addPartialNode (PCNode *partial) |
| void | removePartialNode (PCNode *partial) |
| bool | checkTPPartialCNode (PCNode *node) |
| size_t | findEndOfFullBlock (PCNode *node, PCNode *pred, PCNode *curr, PCNode *&fullEnd, PCNode *&emptyEnd) const |
| bool | setApexCandidate (PCNode *ac, bool fix=false) |
| void | replaceTPNeigh (PCNode *central, PCNode *oldTPNeigh, PCNode *newTPNeigh, PCNode *newFullNeigh, PCNode *otherEndOfFullBlock) |
| PCNode * | splitOffFullPNode (PCNode *node, bool skip_parent) |
Intersect | |
| bool | intersect (PCTree &other, PCTreeNodeArray< PCNode * > &mapping) |
Intersect the restrictions represented by this tree with those represented by other, given a bijection mapping from the leaves of other to this trees' leaves. More... | |
| bool | findNodeRestrictions (PCTree &applyTo, PCTreeNodeArray< PCNode * > &mapping, PCTreeNodeArray< std::vector< PCNode * >> &blockNodes, PCTreeNodeArray< std::vector< PCNode * >> &subtreeNodes, PCTreeNodeArray< PCNode * > &leafPartner, PCTreeNodeArray< bool > &isFront) |
| void | restoreSubtrees (PCTreeNodeArray< std::vector< PCNode * >> &blockNodes, PCTreeNodeArray< std::vector< PCNode * >> &subtreeNodes, PCTreeNodeArray< PCNode * > &leafPartner, PCTreeNodeArray< bool > &isFront) |
Observers | |
| using | FullLeafIter = std::function< std::function< PCNode *()>()> |
| std::list< Observer * >::const_iterator | addObserver (Observer *observer) |
| void | removeObserver (std::list< Observer * >::const_iterator it) |
| void | removeObserver (Observer *observer) |
A PC-tree represents a set of cyclic orders of its leaves by labeling its inner nodes as either P- or C-node and allowing arbitrary permutations of the neighbors of P-nodes while only allowing flips of C-nodes.
The operation PCTree::makeConsecutive() updates the tree such that a set of leaves is consecutive in all represented cyclic orders.
If you are using this implementation, please cite the following work:
For more details, see also (open access):
| using ogdf::pc_tree::PCTree::FullLeafIter = std::function<std::function<PCNode*()>()> |
|
inlineexplicit |
|
inlineexplicit |
|
explicit |
Convenience method generating a PCTree consisting of a single P-node with leafNum leaves, which are all copied to the optional list added.
Automatically creates and manages a forest if forest is null.
|
explicit |
Copy a PCTree.
| other | The PCTree to copy. |
| nodeMapping | Will be assigned a mapping from the nodes of other to the newly created nodes in this tree. |
| keep_ids | Set to true to use the same node IDs as in other, otherwise consecutive IDs will be generated. |
| forest | Automatically create and manages a forest if forest is null. |
|
explicit |
Deserialize a PCTree from a string str as generated by operator<<(std::ostream&, const PCTree*) or PCTree::uniqueID().
Automatically creates and manages a forest if forest is null.
|
virtual |
|
private |
|
inline |
| PCNodeType ogdf::pc_tree::PCTree::changeNodeType | ( | PCNode * | node, |
| PCNodeType | newType | ||
| ) |
Change the type of a node and update all its registrations.
Change the orientation of edges such that newRoot becomes the root of the tree.
|
private |
| bool ogdf::pc_tree::PCTree::checkValid | ( | bool | allow_small_deg = true | ) | const |
Validity check for debugging assertions.
|
private |
|
inline |
|
inline |
| void ogdf::pc_tree::PCTree::destroyLeaf | ( | PCNode * | leaf | ) |
Remove a leaf and also any newly-introduced inner degree-2 or -1 nodes.
Unlike destroyNode(), the leaf leaf must still be attached (so that its parent's degree can be checked)
|
inline |
| void ogdf::pc_tree::PCTree::destroyNode | ( | PCNode *const & | node | ) |
Destroy a node.
The node must be detached and may not be the root of this tree.
|
private |
|
private |
|
private |
|
inline |
|
inline |
The PCTreeForest this PCTree belongs to, or nullptr.
|
inline |
|
inline |
|
inline |
| void ogdf::pc_tree::PCTree::getRestrictions | ( | std::vector< std::vector< PCNode * >> & | restrictions, |
| PCNode * | fixedLeaf = nullptr |
||
| ) | const |
Get a list of all cyclic restrictions used to generate this tree.
If a fixedLeaf was given, the restrictions will linear with none of them containing fixedLeaf.
|
inline |
|
inline |
| void ogdf::pc_tree::PCTree::getTree | ( | ogdf::Graph & | tree, |
| ogdf::GraphAttributes * | g_a, | ||
| PCTreeNodeArray< ogdf::node > & | pc_repr, | ||
| ogdf::NodeArray< PCNode * > * | g_repr = nullptr, |
||
| bool | mark_full = false, |
||
| bool | show_sibs = false |
||
| ) | const |
Get a graphical representation of this tree as Graph.
|
inline |
| void ogdf::pc_tree::PCTree::insertLeaves | ( | int | count, |
| PCNode * | parent, | ||
| std::vector< PCNode * > * | added = nullptr |
||
| ) |
Attach count leaves to P- or C-node parent and optionally store the new leaves in a vector added.
Insert tree tree into this tree at node at.
Both trees need to be part of the same forest. All observers of tree will be moved to this tree. If at is a leaf, it will be replaced by tree, otherwise tree will be appended as child of at.
| bool ogdf::pc_tree::PCTree::intersect | ( | PCTree & | other, |
| PCTreeNodeArray< PCNode * > & | mapping | ||
| ) |
Intersect the restrictions represented by this tree with those represented by other, given a bijection mapping from the leaves of other to this trees' leaves.
true if the intersection is non-empty and this now represented by this tree. Otherwise, the intersection is empty and the state of this tree is undefined. | bool ogdf::pc_tree::PCTree::isTrivial | ( | ) | const |
Whether this PCTree allows all orders (consists of a single P-node).
| bool ogdf::pc_tree::PCTree::isTrivialRestriction | ( | int | size | ) | const |
true if calling makeConsecutive() with size leaves never requires changes to the tree. This is the case for size values 0, 1, getLeafCount() - 1, and getLeafCount(). | bool ogdf::pc_tree::PCTree::isValidOrder | ( | const std::vector< PCNode * > & | order | ) | const |
Check whether the order order is represented by this tree.
|
inline |
|
inline |
Make the leaves contained in the range denoted by iterators begin (inclusive) to end (exclusive) consecutive in all represented orders.
This is equivalent to calling resetTempData() and markFull(It, It, std::vector<PCNode*>*) followd by makeFullNodesConsecutive().
true if the update was successful, false if the leaves cannot be made consecutive and the tree was left unchanged.
|
inline |
| bool ogdf::pc_tree::PCTree::makeFullNodesConsecutive | ( | ) |
Updates the tree to make all leaves marked as full consecutive in all represented orders.
Requires labels of parents to be correctly set by markFull(It, It, std::vector<PCNode*>*).
true if the update was successful, false if the leaves cannot be made consecutive and the tree was left unchanged.
|
inline |
Marks the leaves contained in the range denoted by iterators begin (inclusive) to end (exclusive) full, that is marked for being made consecutive in all represented orders.
Also propagates the markings to parents, which is required for makeFullNodesConsecutive().
|
private |
|
inline |
Only marks leaves full, does not update partial/full info of parents.
Use markFull(It, It, std::vector<PCNode*>*) to also update parents for use with makeFullNodesConsecutive().
|
inline |
Merge multiple leaves into a single one and return it.
| consecutiveLeaves | The leaves that shall be merged. |
| assumeConsecutive | Set to true if you already called makeConsecutive() on the leaves. |
consecutiveLeaves into which all other leaves got merged.
|
inline |
Merge multiple leaves into a single one and return it.
| begin,end | Iterator range spanning the leaves that shall be merged. |
| assumeConsecutive | Set to true if you already called makeConsecutive() on the leaves. |
consecutiveLeaves into which all other leaves got merged. | PCNode* ogdf::pc_tree::PCTree::newNode | ( | PCNodeType | type, |
| PCNode * | parent = nullptr, |
||
| int | id = -1 |
||
| ) |
Create a new node.
| type | The type of the node. |
| parent | Parent to attach this node to, may only be null if this tree is empty and thus has no root. |
| id | ID for the new node, or -1 to automatically use the next free one. |
|
inline |
|
inline |
|
private |
|
inline |
|
inline |
|
private |
| void ogdf::pc_tree::PCTree::replaceLeaf | ( | int | leafCount, |
| PCNode * | leaf, | ||
| std::vector< PCNode * > * | added = nullptr |
||
| ) |
Convert leaf into a P-node and attach leafCount new leaves to it.
|
private |
|
inline |
Reset all makeConsecutive()-related temporary information, especially which leaves are full (should be made consecutive).
|
private |
|
private |
Overwrite the stored root for this PC-tree.
Note that the passed newRoot needs to be valid as root for this tree.
|
inline |
| std::ostream& ogdf::pc_tree::PCTree::uniqueID | ( | std::ostream & | os, |
| const std::function< void(std::ostream &os, PCNode *, int)> & | printNode = uid_utils::nodeToID, |
||
| const std::function< bool(PCNode *, PCNode *)> & | compareNodes = uid_utils::compareNodesByID |
||
| ) |
Print a deterministic and unique representation of this PCTree to os.
Unique node IDs and a deterministic order of nodes' children is generated using printNode and compareNodes, respectively.
|
private |
|
private |
|
friend |
|
friend |
|
friend |
|
friend |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |