This class represents the embedding tree of a single node in a biconnected component.
More...
|
| | NodePCRotation (const Graph &G, node n, bool mapBundleEdges=true) |
| | Calculate the embedding tree of node n in graph G.
|
| |
| void | generateInnerNodeForGraphNodeMapping (NodeArray< PCNode * > &mapping) const |
| |
| void | generateLeafForIncidentEdgeMapping (EdgeArray< PCNode * > &mapping) const |
| |
| void | generatePartnerEdgesForIncidentEdge (EdgeArray< const List< edge > * > &mapping) const |
| |
| const Graph * | getGraph () const |
| |
| node | getGraphNodeForInnerNode (PCNode *n) const |
| | Returns which graph node created a P-node during the run of the planarity test that resulted in this embedding tree.
|
| |
| edge | getIncidentEdgeForLeaf (PCNode *n) const |
| | Returns which incident edge corresponds to which leaf.
|
| |
| node | getNode () const |
| |
| const List< edge > & | getPartnerEdgesForLeaf (PCNode *l) const |
| | If this embedding tree is trivial and getNode() thus has a partner pole, returns the set of edges incident to the pole that correspond to a given leaf l.
|
| |
| node | getTrivialPartnerPole () const |
| | If this embedding tree is trivial (i.e., consists of a single P-node allowing arbitrary rotations), the graphs must contain another node called pole that mirrors the rotation of this node.
|
| |
| bool | isEqual (const NodePCRotation &pc) const |
| | Equality check where to leaves are considered the same if they map to the same edge via getIncidentEdgeForLeaf() in both trees.
|
| |
| bool | knowsPartnerEdges () const |
| |
| void | setIncidentEdgeForLeaf (PCNode *n, edge e) |
| | This is only needed so that SyncPlan::propagatePQ can fix its mapping when propagating into an adjacent cut.
|
| |
| std::function< bool(PCNode *, PCNode *)> | uidComparer () const |
| |
| std::function< void(std::ostream &os, PCNode *, int)> | uidPrinter () const |
| |
| | PCTree () |
| | Constructs a new PCTree.
|
| |
| | PCTree (const PCTree &other, PCTreeNodeArray< PCNode * > &nodeMapping, bool keep_ids=false, PCTreeForest *forest=nullptr) |
| | Copy a PCTree.
|
| |
| | 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().
|
| |
| | 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.
|
| |
| | 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.
|
| |
| virtual | ~PCTree () |
| |
| | operator const PCTreeRegistry & () const |
| |
| PCTreeForest * | getForest () const |
| | The PCTreeForest this PCTree belongs to, or nullptr.
|
| |
| bool | isTrivial () const |
| | Whether this PCTree allows all orders (consists of a single P-node).
|
| |
| 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.
|
| |
| FilteringPCTreeDFS | innerNodes () const |
| | An iterable through all inner (non-leaf) nodes of this PCTree.
|
| |
| template<typename Container > |
| void | currentLeafOrder (Container &container) const |
| | Store the order of leaves currently represented by this tree in container.
|
| |
| std::vector< PCNode * > | currentLeafOrder () const |
| |
| bool | checkValid (bool allow_small_deg=true) const |
| | Validity check for debugging assertions.
|
| |
| bool | isValidOrder (const std::vector< PCNode * > &order) const |
| | Check whether the order order is represented by this tree.
|
| |
| 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.
|
| |
| void | getRestrictions (std::vector< std::vector< PCNode * > > &restrictions, PCNode *fixedLeaf=nullptr) const |
| | Get a list of all cyclic restrictions used to generate this tree.
|
| |
| template<typename R > |
| R | possibleOrders () const |
| | Calculate the number of cyclic orders represented by this tree.
|
| |
| 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.
|
| |
| std::string | uniqueID (const std::function< void(std::ostream &os, PCNode *, int)> &printNode=uid_utils::nodeToID, const std::function< bool(PCNode *, PCNode *)> &compareNodes=uid_utils::compareNodesByID) |
| |
| std::list< Observer * >::const_iterator | addObserver (Observer *observer) |
| |
| void | removeObserver (std::list< Observer * >::const_iterator it) |
| |
| void | removeObserver (Observer *observer) |
| |
| PCNode * | newNode (PCNodeType type, PCNode *parent=nullptr, int id=-1) |
| | Create a new node.
|
| |
| void | destroyNode (PCNode *&node) |
| | Destroy a node.
|
| |
| void | destroyNode (PCNode *const &node) |
| | Destroy a node.
|
| |
| 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.
|
| |
| void | replaceLeaf (int leafCount, PCNode *leaf, std::vector< PCNode * > *added=nullptr) |
| | Convert leaf into a P-node and attach leafCount new leaves to it.
|
| |
| PCNode * | mergeLeaves (const std::vector< PCNode * > &consecutiveLeaves, bool assumeConsecutive=false) |
| | Merge multiple leaves into a single one and return it.
|
| |
| template<typename It > |
| PCNode * | mergeLeaves (It begin, It end, bool assumeConsecutive=false) |
| | Merge multiple leaves into a single one and return it.
|
| |
| void | destroyLeaf (PCNode *leaf) |
| | Remove a leaf and also any newly-introduced inner degree-2 or -1 nodes.
|
| |
| PCNode * | setRoot (PCNode *newRoot) |
| | Overwrite the stored root for this PC-tree.
|
| |
| PCNode * | changeRoot (PCNode *newRoot) |
| | Change the orientation of edges such that newRoot becomes the root of the tree.
|
| |
| PCNodeType | changeNodeType (PCNode *node, PCNodeType newType) |
| | Change the type of a node and update all its registrations.
|
| |
| void | insertTree (PCNode *at, PCTree *tree) |
| | Insert tree tree into this tree at node at.
|
| |
| 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.
|
| |
| void | resetTempData () |
| | Reset all makeConsecutive()-related temporary information, especially which leaves are full (should be made consecutive).
|
| |
| template<typename It > |
| void | markLeavesFull (It begin, It end) |
| | Only marks leaves full, does not update partial/full info of parents.
|
| |
| 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.
|
| |
| bool | makeFullNodesConsecutive () |
| | Updates the tree to make all leaves marked as full consecutive in all represented orders.
|
| |
| 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.
|
| |
This class represents the embedding tree of a single node in a biconnected component.
The embedding tree is a PCTree with one leaf for each incident edge that describes all possible rotations of the incident edges in all planar embeddings of the component. Uses the Booth&Lueker Planarity Test for computing the embedding tree, see https://doi.org/10.15475/cpatp.2024 (Section 9.2).
Definition at line 54 of file NodePCRotation.h.
Inheritance diagram for ogdf::pc_tree::NodePCRotation:
