ogdf::sync_plan::SyncPlan Class Reference

A class for modelling and solving Synchronized Planarity instances. More...

#include <ogdf/cluster/sync_plan/SyncPlan.h>

Classes
class	ResetIndices
class	UndoOperation
	The information needed for undoing the changes a specific operation made to the graph while maintaining its embedding. More...
class	VerifyPipeBijections

Public Types
enum	Result { Result::SUCCESS, Result::NOT_APPLICABLE, Result::INVALID_INSTANCE }
	The result of applying a single operation. More...

Public Member Functions
	SyncPlan (Graph *g, ClusterGraph *cg, std::vector< std::pair< adjEntry, adjEntry >> *augmentation=nullptr, ClusterGraphAttributes *ga=nullptr)
	Create a new Synchronized Planarity instance by applying the reduction from some ClusteredPlanarity instance. More...
	SyncPlan (Graph *g, GraphAttributes *ga=nullptr)
	Create a new Synchronized Planarity instance with a given underlying graph. More...
	SyncPlan (Graph *sefe, Graph *work, EdgeArray< uint8_t > &edge_types)
	Create a new SyncPlan instance using the reduction from a 2-SEFE instance with a connected shared graph. More...
virtual	~SyncPlan ()
Operations used by makeReduced() for removing pipes.
void	makeWheel (node centre, bool update_cuts=true)
void	contractWheel (node centre)
Result	convertSmall (node small)
Result	encapsulate (node g_cut)
Result	contract (node u)
Result	propagatePQ (node u, NodePCRotation *pct, NodePCRotation *pct_v=nullptr)
Result	simplify (node u, const NodePCRotation *pc)
Result	checkPCTree (node u)
	Computes an embedding tree and either applies propagatePQ() or simplify() More...
Result	batchSPQR ()
Methods for solving instances
Recompute biconnected component information after the graph was changed externally.
void	initComponents ()
bool	makeReduced (int check_planarity_every=0)
	Apply operations (in the order defined by the current PipeQueue) until no pipes are left. More...
bool	solveReduced (bool fail_fast=false)
	Solve a reduced instance, creating a combinatorial embedding of the current graph that respects all Q-constraints. More...
void	embed ()
	Undo all operations while maintaining the current embedding to obtain an embedding of the initial graph. More...
Statistics
int	undoOperations () const
	The number of operations that need undoing. More...
int	getLongestSimplifyToroidalCycle () const
	Return the longest cycle length encountered in simplify toroidal. More...
const SyncPlanComponents &	getComponents () const
	The maintained (bi)connected components information. More...
PipeType	getPipeType (const Pipe *p) const
bool	canContract (const Pipe *p) const
	Check whether a Pipe can be removed by applying contract(). More...
Configuration
Config ////////////////////////////////////////////////////////////////////////////////////////////////////////
bool	isAllowContractBBPipe () const
void	setAllowContractBBPipe (bool allowContractBbPipe)
	Configure whether block-block pipes can be contracted. More...
bool	isIntersectTrees () const
void	setIntersectTrees (bool intersectTrees)
	Configure whether the embedding trees of block-block pipes should be intersected before propagating. More...
bool	isBatchSpqr () const
void	setBatchSpqr (bool batchSpqr)
	Configure whether embedding trees should be computed in batch by deriving them from an SPQR-tree. More...

Public Attributes
Graph *const	G
	The underlying graph. More...
PMatching	matchings
	Collection of all matched P-nodes and their pipes. More...
QPartitioning	partitions
	Collection of all Q-nodes and their partitions. More...

Private Member Functions
edge	edgeFromIndex (int idx) const
std::function< std::ostream &(std::ostream &)>	fmtPQNode (node n, bool include_comp=true) const
void	formatNode (node n) const
node	nodeFromIndex (int idx) const
void	pushUndoOperation (UndoOperation *operation)
void	pushUndoOperationAndCheck (UndoOperation *operation)
void	thawPipeBijection (node u, node v, const FrozenPipeBij &in, PipeBij &out) const
bool	verifyPipeBijection (node u, node v, const FrozenPipeBij &bij) const

Private Attributes
bool	allow_contract_bb_pipe = false
	Whether to allow contracting block-vertex to block-vertex pipes instead of propagating. More...
bool	batch_spqr = true
	Whether to apply embedding-tree based operations in batch using SPQR-tree data. More...
SyncPlanComponents	components
	Data structure maintaining (bi)connected components information. More...
SyncPlanConsistency	consistency
	Consistency checking utils. More...
Graph::HiddenEdgeSet	deletedEdges
	Set of all edge objects deleted during the reduction, to be restored when undoing all operations. More...
NodeSet	deletedNodes
	Set of all node objects deleted during the reduction. Will remain as isolated nodes within G. More...
EdgeArray< edge >	edge_reg
	A mapping of edge-index to edge-object used while undoing operations. More...
GraphAttributes *	GA
	If non-null, will be updated with debugging information from applied operations. More...
bool	indices_saved = false
	Whether the constructor already saved the maximum indices present in G before the reduction. More...
bool	intersect_trees = true
	Whether to intersect trees on block-vertex to block-vertex pipes when propagating. More...
NodeArray< bool >	is_wheel
	Labels nodes whether they are already part of a (Q-node-replacement) wheel. More...
Logger	log
	The logger to use. More...
int	longestSimplifyToroidalCycle = 0
	Keeps track of the longest cycle length encountered in simplify toroidal. More...
NodeArray< node >	node_reg
	A mapping of node-index to node-object used while undoing operations. More...
List< UndoOperation * >	undo_stack
	Stack of all operations that should be undone when embedding. More...

Friends
class	EmbeddingTrees
class	internal::UndoSimplify
std::ostream &	operator<< (std::ostream &os, const SyncPlan &pq)
class	SyncPlanConsistency
class	SyncPlanDrawer
class	SyncPlanOptions
class	UndoContract
class	UndoConvertSmall
class	UndoEncapsulate
class	UndoInitCluster
class	UndoMakeWheel
class	UndoPropagate
class	UndoSimplifyToroidal

Detailed Description

A class for modelling and solving Synchronized Planarity instances.

This implements the algorithm described in the following paper:

Remarks

Thomas Bläsius, Simon D. Fink, and Ignaz Rutter. 2023. Synchronized Planarity with Applications to Constrained Planarity Problems. ACM Trans. Algorithms 19, 4, Article 34 (October 2023), 23 pages. https://doi.org/10.1145/3607474

An evaluation of this implementation can be found in the following paper:

Remarks

Simon D. Fink and Ignaz Rutter. 2024. Constrained Planarity in Practice: Engineering the Synchronized Planarity Algorithm. 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) https://doi.org/10.1137/1.9781611977929.1

For more details, see also (open access):

Remarks

Simon D. Fink. 2024. Constrained Planarity Algorithms in Theory and Practice. Doctoral Thesis, University of Passau. https://doi.org/10.15475/cpatp.2024

Definition at line 123 of file SyncPlan.h.

Member Enumeration Documentation

Result

enum ogdf::sync_plan::SyncPlan::Result

strong

The result of applying a single operation.

Enumerator
SUCCESS
NOT_APPLICABLE
INVALID_INSTANCE

Definition at line 194 of file SyncPlan.h.

Constructor & Destructor Documentation

SyncPlan() [1/3]

ogdf::sync_plan::SyncPlan::SyncPlan ( Graph *  g, GraphAttributes *  ga = nullptr  )

explicit

Create a new Synchronized Planarity instance with a given underlying graph.

Usage:

Graph G;
// init your graph here
 
SyncPlan PQ(&G);
// init pipes and partitions here:
PQ.matchings.matchNodes(u, v);
int p = PQ.partitions.makeQVertex(u1);
PQ.partitions.makeQVertex(u2, p);
PQ.partitions.makeQVertex(u3, p);
 
// if you made any changes to edges in G after creating the SyncPlan instance, call
PQ.initComponents(); // to update the BC-tree if connectivity changed
PQ.matchings.rebuildHeap(); // to sort the pipes if their degree changed
 
if (PQ.makeReduced() && PQ.solveReduced()) {
    PQ.embed();
    OGDF_ASSERT(G.representsCombEmbedding());
}

Parameters

g	the underlying graph.
ga	optional GraphAttributes in which to store debugging information of applied operations.

SyncPlan() [2/3]

ogdf::sync_plan::SyncPlan::SyncPlan ( Graph *  g, ClusterGraph *  cg, std::vector< std::pair< adjEntry, adjEntry >> *  augmentation = nullptr, ClusterGraphAttributes *  ga = nullptr  )

explicit

Create a new Synchronized Planarity instance by applying the reduction from some ClusteredPlanarity instance.

Usage:

Graph G;
ClusterGraph CG(G);
// init your graph and clusters here
 
SyncPlan PQ(&G, &CG);
// you shouldn't change G or CG after creating a SyncPlan instance from them
 
if (PQ.makeReduced() && PQ.solveReduced()) {
    PQ.embed();
    OGDF_ASSERT(CG.representsCombEmbedding());
}

Note

After calling (the reduction used within) this constructor, the ClusterGraph and underlying Graph will be invalid until SyncPlan::embed() is called.

Parameters

g	the underlying graph.
cg	the corresponding ClusterGraph.
augmentation	if non-null, will be assigned the edges that need to be inserted to make the graph c-connected c-plane once SyncPlan::embed() was called.
ga	optional GraphAttributes in which to store debugging information of applied operations.

See also

insertAugmentationEdges()

SyncPlan() [3/3]

ogdf::sync_plan::SyncPlan::SyncPlan ( Graph *  sefe, Graph *  work, EdgeArray< uint8_t > &  edge_types  )

explicit

Create a new SyncPlan instance using the reduction from a 2-SEFE instance with a connected shared graph.

Parameters

sefe	the 2-SEFE instance that shall be embedded.
work	an empty graph that is used for the reduction.
edge_types	the types of edges in sefe, 1 or 2 for either of the exclusive graphs, 3 for shared.

~SyncPlan()

virtual ogdf::sync_plan::SyncPlan::~SyncPlan ( )

inlinevirtual

Definition at line 318 of file SyncPlan.h.

Member Function Documentation

batchSPQR()

Result ogdf::sync_plan::SyncPlan::batchSPQR

(

)

canContract()

bool ogdf::sync_plan::SyncPlan::canContract

(

const Pipe *

p

)

const

Check whether a Pipe can be removed by applying contract().

See also

setAllowContractBBPipe()

checkPCTree()

Result ogdf::sync_plan::SyncPlan::checkPCTree

(

node

u

)

Computes an embedding tree and either applies propagatePQ() or simplify()

contract()

Result ogdf::sync_plan::SyncPlan::contract

(

node

u

)

contractWheel()

void ogdf::sync_plan::SyncPlan::contractWheel

(

node

centre

)

convertSmall()

Result ogdf::sync_plan::SyncPlan::convertSmall

(

node

small

)

edgeFromIndex()

edge ogdf::sync_plan::SyncPlan::edgeFromIndex ( int  idx ) const

private

embed()

void ogdf::sync_plan::SyncPlan::embed

(

)

Undo all operations while maintaining the current embedding to obtain an embedding of the initial graph.

encapsulate()

Result ogdf::sync_plan::SyncPlan::encapsulate

(

node

g_cut

)

fmtPQNode()

std::function<std::ostream&(std::ostream&)> ogdf::sync_plan::SyncPlan::fmtPQNode ( node  n, bool  include_comp = true  ) const

private

formatNode()

void ogdf::sync_plan::SyncPlan::formatNode ( node  n ) const

private

getComponents()

const SyncPlanComponents& ogdf::sync_plan::SyncPlan::getComponents ( ) const

inline

The maintained (bi)connected components information.

Definition at line 403 of file SyncPlan.h.

getLongestSimplifyToroidalCycle()

int ogdf::sync_plan::SyncPlan::getLongestSimplifyToroidalCycle ( ) const

inline

Return the longest cycle length encountered in simplify toroidal.

Definition at line 400 of file SyncPlan.h.

getPipeType()

PipeType ogdf::sync_plan::SyncPlan::getPipeType

(

const Pipe *

p

)

const

initComponents()

void ogdf::sync_plan::SyncPlan::initComponents

(

)

isAllowContractBBPipe()

bool ogdf::sync_plan::SyncPlan::isAllowContractBBPipe ( ) const

inline

Definition at line 426 of file SyncPlan.h.

isBatchSpqr()

bool ogdf::sync_plan::SyncPlan::isBatchSpqr ( ) const

inline

Definition at line 438 of file SyncPlan.h.

isIntersectTrees()

bool ogdf::sync_plan::SyncPlan::isIntersectTrees ( ) const

inline

Definition at line 433 of file SyncPlan.h.

makeReduced()

bool ogdf::sync_plan::SyncPlan::makeReduced

(

int

check_planarity_every = 0

)

Apply operations (in the order defined by the current PipeQueue) until no pipes are left.

makeWheel()

void ogdf::sync_plan::SyncPlan::makeWheel	(	node	centre,
		bool	update_cuts = true
	)

nodeFromIndex()

node ogdf::sync_plan::SyncPlan::nodeFromIndex ( int  idx ) const

private

propagatePQ()

Result ogdf::sync_plan::SyncPlan::propagatePQ	(	node	u,
		NodePCRotation *	pct,
		NodePCRotation *	pct_v = nullptr
	)

pushUndoOperation()

void ogdf::sync_plan::SyncPlan::pushUndoOperation ( UndoOperation *  operation )

inlineprivate

Definition at line 348 of file SyncPlan.h.

pushUndoOperationAndCheck()

void ogdf::sync_plan::SyncPlan::pushUndoOperationAndCheck ( UndoOperation *  operation )

inlineprivate

Definition at line 339 of file SyncPlan.h.

setAllowContractBBPipe()

void ogdf::sync_plan::SyncPlan::setAllowContractBBPipe ( bool  allowContractBbPipe )

inline

Configure whether block-block pipes can be contracted.

Definition at line 429 of file SyncPlan.h.

setBatchSpqr()

void ogdf::sync_plan::SyncPlan::setBatchSpqr ( bool  batchSpqr )

inline

Configure whether embedding trees should be computed in batch by deriving them from an SPQR-tree.

Definition at line 441 of file SyncPlan.h.

setIntersectTrees()

void ogdf::sync_plan::SyncPlan::setIntersectTrees ( bool  intersectTrees )

inline

Configure whether the embedding trees of block-block pipes should be intersected before propagating.

Definition at line 436 of file SyncPlan.h.

simplify()

Result ogdf::sync_plan::SyncPlan::simplify	(	node	u,
		const NodePCRotation *	pc
	)

solveReduced()

bool ogdf::sync_plan::SyncPlan::solveReduced

(

bool

fail_fast = false

)

Solve a reduced instance, creating a combinatorial embedding of the current graph that respects all Q-constraints.

thawPipeBijection()

void ogdf::sync_plan::SyncPlan::thawPipeBijection ( node  u, node  v, const FrozenPipeBij &  in, PipeBij &  out  ) const

private

undoOperations()

int ogdf::sync_plan::SyncPlan::undoOperations ( ) const

inline

The number of operations that need undoing.

Definition at line 397 of file SyncPlan.h.

verifyPipeBijection()

bool ogdf::sync_plan::SyncPlan::verifyPipeBijection ( node  u, node  v, const FrozenPipeBij &  bij  ) const

private

Friends And Related Function Documentation

EmbeddingTrees

friend class EmbeddingTrees

friend

Definition at line 148 of file SyncPlan.h.

internal::UndoSimplify

friend class internal::UndoSimplify

friend

Definition at line 142 of file SyncPlan.h.

operator<<

std::ostream& operator<< ( std::ostream &  os, const SyncPlan &  pq  )

friend

SyncPlanConsistency

friend class SyncPlanConsistency

friend

Definition at line 124 of file SyncPlan.h.

SyncPlanDrawer

friend class SyncPlanDrawer

friend

Definition at line 126 of file SyncPlan.h.

SyncPlanOptions

friend class SyncPlanOptions

friend

Definition at line 128 of file SyncPlan.h.

UndoContract

friend class UndoContract

friend

Definition at line 132 of file SyncPlan.h.

UndoConvertSmall

friend class UndoConvertSmall

friend

Definition at line 134 of file SyncPlan.h.

UndoEncapsulate

friend class UndoEncapsulate

friend

Definition at line 136 of file SyncPlan.h.

UndoInitCluster

friend class UndoInitCluster

friend

Definition at line 138 of file SyncPlan.h.

UndoMakeWheel

friend class UndoMakeWheel

friend

Definition at line 146 of file SyncPlan.h.

UndoPropagate

friend class UndoPropagate

friend

Definition at line 140 of file SyncPlan.h.

UndoSimplifyToroidal

friend class UndoSimplifyToroidal

friend

Definition at line 144 of file SyncPlan.h.

Member Data Documentation

allow_contract_bb_pipe

bool ogdf::sync_plan::SyncPlan::allow_contract_bb_pipe = false

private

Whether to allow contracting block-vertex to block-vertex pipes instead of propagating.

Definition at line 237 of file SyncPlan.h.

batch_spqr

bool ogdf::sync_plan::SyncPlan::batch_spqr = true

private

Whether to apply embedding-tree based operations in batch using SPQR-tree data.

Definition at line 241 of file SyncPlan.h.

components

SyncPlanComponents ogdf::sync_plan::SyncPlan::components

private

Data structure maintaining (bi)connected components information.

Definition at line 217 of file SyncPlan.h.

consistency

SyncPlanConsistency ogdf::sync_plan::SyncPlan::consistency

private

Consistency checking utils.

Definition at line 247 of file SyncPlan.h.

deletedEdges

Graph::HiddenEdgeSet ogdf::sync_plan::SyncPlan::deletedEdges

private

Set of all edge objects deleted during the reduction, to be restored when undoing all operations.

Definition at line 219 of file SyncPlan.h.

deletedNodes

NodeSet ogdf::sync_plan::SyncPlan::deletedNodes

private

Set of all node objects deleted during the reduction. Will remain as isolated nodes within G.

Definition at line 222 of file SyncPlan.h.

edge_reg

EdgeArray<edge> ogdf::sync_plan::SyncPlan::edge_reg

private

A mapping of edge-index to edge-object used while undoing operations.

Definition at line 229 of file SyncPlan.h.

G

Graph* const ogdf::sync_plan::SyncPlan::G

The underlying graph.

Definition at line 200 of file SyncPlan.h.

GA

GraphAttributes* ogdf::sync_plan::SyncPlan::GA

private

If non-null, will be updated with debugging information from applied operations.

Definition at line 225 of file SyncPlan.h.

indices_saved

bool ogdf::sync_plan::SyncPlan::indices_saved = false

private

Whether the constructor already saved the maximum indices present in G before the reduction.

Definition at line 235 of file SyncPlan.h.

intersect_trees

bool ogdf::sync_plan::SyncPlan::intersect_trees = true

private

Whether to intersect trees on block-vertex to block-vertex pipes when propagating.

Definition at line 239 of file SyncPlan.h.

is_wheel

NodeArray<bool> ogdf::sync_plan::SyncPlan::is_wheel

private

Labels nodes whether they are already part of a (Q-node-replacement) wheel.

Definition at line 231 of file SyncPlan.h.

log

Logger ogdf::sync_plan::SyncPlan::log

private

The logger to use.

Definition at line 233 of file SyncPlan.h.

longestSimplifyToroidalCycle

int ogdf::sync_plan::SyncPlan::longestSimplifyToroidalCycle = 0

private

Keeps track of the longest cycle length encountered in simplify toroidal.

Definition at line 243 of file SyncPlan.h.

matchings

PMatching ogdf::sync_plan::SyncPlan::matchings

Collection of all matched P-nodes and their pipes.

Definition at line 202 of file SyncPlan.h.

node_reg

NodeArray<node> ogdf::sync_plan::SyncPlan::node_reg

private

A mapping of node-index to node-object used while undoing operations.

Definition at line 227 of file SyncPlan.h.

partitions

QPartitioning ogdf::sync_plan::SyncPlan::partitions

Collection of all Q-nodes and their partitions.

Definition at line 204 of file SyncPlan.h.

undo_stack

List<UndoOperation*> ogdf::sync_plan::SyncPlan::undo_stack

private

Stack of all operations that should be undone when embedding.

Definition at line 215 of file SyncPlan.h.

---

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

• include/ogdf/cluster/sync_plan/SyncPlan.h