Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::sync_plan::NodeSSPQRRotation Class Reference

Derive embedding trees from Triconnectivity information. More...

#include <ogdf/cluster/sync_plan/utils/NodeTricRotation.h>

+ Inheritance diagram for ogdf::sync_plan::NodeSSPQRRotation:

Public Member Functions

 NodeSSPQRRotation (const NodeSSPQRRotation &copy)=delete
 
 NodeSSPQRRotation (const SimpleSPQRTree &spqr, node n)
 
 NodeSSPQRRotation (NodeSSPQRRotation &&move)=delete
 
void mapPartnerEdges ()
 
NodeSSPQRRotationoperator= (const NodeSSPQRRotation &copy)=delete
 
NodeSSPQRRotationoperator= (NodeSSPQRRotation &&move)=delete
 
- Public Member Functions inherited from ogdf::pc_tree::NodePCRotation
 NodePCRotation (const Graph &G, node n, bool mapBundleEdges=true)
 Calculate the embedding tree of node n in graph G. More...
 
void generateInnerNodeForGraphNodeMapping (NodeArray< PCNode * > &mapping) const
 
void generateLeafForIncidentEdgeMapping (EdgeArray< PCNode * > &mapping) const
 
void generatePartnerEdgesForIncidentEdge (EdgeArray< const List< edge > * > &mapping) const
 
const GraphgetGraph () 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. More...
 
edge getIncidentEdgeForLeaf (PCNode *n) const
 Returns which incident edge corresponds to which leaf. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
std::function< bool(PCNode *, PCNode *)> uidComparer () const
 
std::function< void(std::ostream &os, PCNode *, int)> uidPrinter () const
 
- Public Member Functions inherited from ogdf::pc_tree::PCTree
 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 ()
 
 operator const PCTreeRegistry & () const
 
PCTreeForestgetForest () 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
 
PCNodegetRootNode () 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 >
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)
 
PCNodenewNode (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...
 
PCNodemergeLeaves (const std::vector< PCNode * > &consecutiveLeaves, bool assumeConsecutive=false)
 Merge multiple leaves into a single one and return it. More...
 
template<typename It >
PCNodemergeLeaves (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...
 
PCNodesetRoot (PCNode *newRoot)
 Overwrite the stored root for this PC-tree. More...
 
PCNodechangeRoot (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...
 
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...
 
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...
 
std::list< Observer * >::const_iterator addObserver (Observer *observer)
 
void removeObserver (std::list< Observer * >::const_iterator it)
 
void removeObserver (Observer *observer)
 

Private Member Functions

void getIncidentRealEdgesInSubtree (adjEntry skel_adj, OverlappingGraphCopy &skel, List< edge > &out)
 
pc_tree::PCNodeprocess (adjEntry skel_adj, OverlappingGraphCopy &skel, pc_tree::PCNode *parent=nullptr)
 

Private Attributes

const SimpleSPQRTreespqr
 

Additional Inherited Members

- Public Types inherited from ogdf::pc_tree::PCTree
using FullLeafIter = std::function< std::function< PCNode *()>()>
 
- Static Public Member Functions inherited from ogdf::pc_tree::NodePCRotation
static node getTrivialPartnerPole (const Graph &G, node n)
 
- Protected Member Functions inherited from ogdf::pc_tree::NodePCRotation
 NodePCRotation ()
 
- Protected Attributes inherited from ogdf::pc_tree::NodePCRotation
PCTreeNodeArray< List< edge > > m_bundleEdgesForLeaf
 
const Graphm_G
 
PCTreeNodeArray< nodem_graphNodeForInnerNode
 
PCTreeNodeArray< edgem_incidentEdgeForLeaf
 
node m_n
 

Detailed Description

Derive embedding trees from Triconnectivity information.

Definition at line 110 of file NodeTricRotation.h.

Constructor & Destructor Documentation

◆ NodeSSPQRRotation() [1/3]

ogdf::sync_plan::NodeSSPQRRotation::NodeSSPQRRotation ( const NodeSSPQRRotation copy)
delete

◆ NodeSSPQRRotation() [2/3]

ogdf::sync_plan::NodeSSPQRRotation::NodeSSPQRRotation ( NodeSSPQRRotation &&  move)
delete

◆ NodeSSPQRRotation() [3/3]

ogdf::sync_plan::NodeSSPQRRotation::NodeSSPQRRotation ( const SimpleSPQRTree spqr,
node  n 
)

Member Function Documentation

◆ getIncidentRealEdgesInSubtree()

void ogdf::sync_plan::NodeSSPQRRotation::getIncidentRealEdgesInSubtree ( adjEntry  skel_adj,
OverlappingGraphCopy skel,
List< edge > &  out 
)
private

◆ mapPartnerEdges()

void ogdf::sync_plan::NodeSSPQRRotation::mapPartnerEdges ( )

◆ operator=() [1/2]

NodeSSPQRRotation& ogdf::sync_plan::NodeSSPQRRotation::operator= ( const NodeSSPQRRotation copy)
delete

◆ operator=() [2/2]

NodeSSPQRRotation& ogdf::sync_plan::NodeSSPQRRotation::operator= ( NodeSSPQRRotation &&  move)
delete

◆ process()

pc_tree::PCNode* ogdf::sync_plan::NodeSSPQRRotation::process ( adjEntry  skel_adj,
OverlappingGraphCopy skel,
pc_tree::PCNode parent = nullptr 
)
private

Member Data Documentation

◆ spqr

const SimpleSPQRTree& ogdf::sync_plan::NodeSSPQRRotation::spqr
private

Definition at line 111 of file NodeTricRotation.h.


The documentation for this class was generated from the following file: