Takes an acyclic connected non-upward-planar graph and planarizes it, i.e., we obtain an upward-planar graph where crossings are represented via dummy vertices. More...

#include <ogdf/upward/SubgraphUpwardPlanarizer.h>

Inheritance diagram for ogdf::SubgraphUpwardPlanarizer:

Public Member Functions
	SubgraphUpwardPlanarizer ()
	Creates an instance of subgraph planarizer. More...

int	runs ()

void	runs (int n)

void	setAcyclicSubgraphModule (AcyclicSubgraphModule *acyclicMod)
	Sets the module option for acyclic subgraph module. More...

void	setInserter (UpwardEdgeInserterModule *pInserter)
	Sets the module option for the edge insertion module. More...

void	setSubgraph (FUPSModule *FUPS)
	Sets the module option for the computation of the feasible upward planar subgraph. More...

Public Member Functions inherited from ogdf::UpwardPlanarizerModule
	UpwardPlanarizerModule ()
	Initializes an upward planarizer module. More...

virtual	~UpwardPlanarizerModule ()

ReturnType	call (UpwardPlanRep &UPR, const EdgeArray< int > cost=nullptr, const EdgeArray< bool > forbid=nullptr)
	Computes a upward planarized representation (UPR) of the input graph G. More...

ReturnType	operator() (UpwardPlanRep &UPR, const EdgeArray< int > cost=nullptr, const EdgeArray< bool > forbid=nullptr)
	Computes a upward planarized representation of the input graph (shorthand for call) More...

bool	useCost () const
	Returns true iff edge costs are given. More...

bool	useForbid () const
	Returns true iff forbidden edges are given. More...

Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module. More...

virtual	~Module ()

Protected Member Functions
virtual ReturnType	doCall (UpwardPlanRep &UPR, const EdgeArray< int > &cost, const EdgeArray< bool > &forbid) override
	Computes an upward planarized representation of the input graph. More...

Protected Attributes
std::unique_ptr< AcyclicSubgraphModule >	m_acyclicMod
	The acyclic subgraph module. More...

std::unique_ptr< UpwardEdgeInserterModule >	m_inserter
	The edge insertion module. More...

int	m_runs

std::unique_ptr< FUPSModule >	m_subgraph
	The upward planar subgraph algorithm. More...

Private Member Functions
void	constructComponentGraphs (BCTree &BC, NodeArrayP< GraphCopy > &biComps)

void	dfsMerge (const GraphCopy &GC, BCTree &BC, NodeArrayP< GraphCopy > &biComps, NodeArrayP< UpwardPlanRep > &uprs, UpwardPlanRep &UPR_res, node parent_BC, node current_BC, NodeArray< bool > &nodesDone)
	traversion the BTree and merge the component to a common graph More...

void	merge (const GraphCopy &GC, UpwardPlanRep &UPR_res, const GraphCopy &block, UpwardPlanRep &UPR)
	add UPR to UPR_res. More...

Additional Inherited Members
Public Types inherited from ogdf::Module
enum	ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::Error }
	The return type of a module. More...

Static Public Member Functions inherited from ogdf::Module
static bool	isSolution (ReturnType ret)
	Returns true iff `ret` indicates that the module returned a feasible solution. More...

Detailed Description

Takes an acyclic connected non-upward-planar graph and planarizes it, i.e., we obtain an upward-planar graph where crossings are represented via dummy vertices.

The code corresponds to the following paper by Hoi-Ming Wong:

M. Chimani, C. Gutwenger, P. Mutzel, H.-M. Wong. Layer-Free Upward Crossing Minimization. ACM Journal of Experimental Algorithmics, Vol. 15, Art.No. 2.2, 27 pages, ACM, 2010.

Note: To call the planarizer, an UpwardPlanRep is required. It needs to have the input graph as its orginal, but is initially empty! After the algorithm, it will hold the representation.

Example for Input "Graph G":

UpwardPlanRep U;
U.setOriginalGraph(G);
SubgraphUpwardPlanarizer sup;
sup.call(U, 0, 0);

Definition at line 70 of file SubgraphUpwardPlanarizer.h.

Constructor & Destructor Documentation

◆ SubgraphUpwardPlanarizer()

ogdf::SubgraphUpwardPlanarizer::SubgraphUpwardPlanarizer ( )

inline

Creates an instance of subgraph planarizer.

Definition at line 73 of file SubgraphUpwardPlanarizer.h.

Member Function Documentation

◆ constructComponentGraphs()

void ogdf::SubgraphUpwardPlanarizer::constructComponentGraphs	(	BCTree &	BC,
		NodeArrayP< GraphCopy > &	biComps
	)

private

◆ dfsMerge()

void ogdf::SubgraphUpwardPlanarizer::dfsMerge	(	const GraphCopy &	GC,
		BCTree &	BC,
		NodeArrayP< GraphCopy > &	biComps,
		NodeArrayP< UpwardPlanRep > &	uprs,
		UpwardPlanRep &	UPR_res,
		node	parent_BC,
		node	current_BC,
		NodeArray< bool > &	nodesDone
	)

private

traversion the BTree and merge the component to a common graph

◆ doCall()

virtual ReturnType ogdf::SubgraphUpwardPlanarizer::doCall	(	UpwardPlanRep &	UPR,
		const EdgeArray< int > &	cost,
		const EdgeArray< bool > &	forbid
	)

overrideprotectedvirtual

Computes an upward planarized representation of the input graph.

Parameters

UPR	represents the input graph as well as the computed upward planarized representation after the call. The original graph of `UPR` has to be the input graph G. Crossings are replaced by dummy vertices. The UPR is finaly augmented to a st-graph. Since this augmentation, crossings dummies may not got an in- and outdegree of 2!
cost	points to an edge array that gives the cost of each edge. If cost = 0, all edges have cost 1.
forbid	points to an edge array indicating which edges are not allowed to be crossed, i.e., (*forbid)[e] = true. If forbid = 0, no edges are forbidden.

Returns: the status of the result.

Implements ogdf::UpwardPlanarizerModule.

◆ merge()

void ogdf::SubgraphUpwardPlanarizer::merge	(	const GraphCopy &	GC,
		UpwardPlanRep &	UPR_res,
		const GraphCopy &	block,
		UpwardPlanRep &	UPR
	)

private

add UPR to UPR_res.

◆ runs() [1/2]

int ogdf::SubgraphUpwardPlanarizer::runs ( )

inline

Definition at line 92 of file SubgraphUpwardPlanarizer.h.

◆ runs() [2/2]

void ogdf::SubgraphUpwardPlanarizer::runs ( int n )

inline

Definition at line 94 of file SubgraphUpwardPlanarizer.h.

◆ setAcyclicSubgraphModule()

void ogdf::SubgraphUpwardPlanarizer::setAcyclicSubgraphModule ( AcyclicSubgraphModule * acyclicMod )

inline

Sets the module option for acyclic subgraph module.

Definition at line 88 of file SubgraphUpwardPlanarizer.h.

◆ setInserter()

void ogdf::SubgraphUpwardPlanarizer::setInserter ( UpwardEdgeInserterModule * pInserter )

inline

Sets the module option for the edge insertion module.

Definition at line 85 of file SubgraphUpwardPlanarizer.h.

◆ setSubgraph()

void ogdf::SubgraphUpwardPlanarizer::setSubgraph ( FUPSModule * FUPS )

inline

Sets the module option for the computation of the feasible upward planar subgraph.

Definition at line 82 of file SubgraphUpwardPlanarizer.h.

Member Data Documentation

◆ m_acyclicMod

std::unique_ptr<AcyclicSubgraphModule> ogdf::SubgraphUpwardPlanarizer::m_acyclicMod

protected

The acyclic subgraph module.

Definition at line 102 of file SubgraphUpwardPlanarizer.h.

◆ m_inserter

std::unique_ptr<UpwardEdgeInserterModule> ogdf::SubgraphUpwardPlanarizer::m_inserter

protected

The edge insertion module.

Definition at line 101 of file SubgraphUpwardPlanarizer.h.

◆ m_runs

int ogdf::SubgraphUpwardPlanarizer::m_runs

protected

Definition at line 103 of file SubgraphUpwardPlanarizer.h.

◆ m_subgraph

std::unique_ptr<FUPSModule> ogdf::SubgraphUpwardPlanarizer::m_subgraph

protected

The upward planar subgraph algorithm.

Definition at line 100 of file SubgraphUpwardPlanarizer.h.

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

include/ogdf/upward/SubgraphUpwardPlanarizer.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ SubgraphUpwardPlanarizer()

Member Function Documentation

◆ constructComponentGraphs()

◆ dfsMerge()

◆ doCall()

◆ merge()

◆ runs() [1/2]

◆ runs() [2/2]

◆ setAcyclicSubgraphModule()

◆ setInserter()

◆ setSubgraph()

Member Data Documentation

◆ m_acyclicMod

◆ m_inserter

◆ m_runs

◆ m_subgraph

Open
Graph Drawing
Framework