Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::SubgraphUpwardPlanarizer Class Reference

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< AcyclicSubgraphModulem_acyclicMod
 The acyclic subgraph module. More...
 
std::unique_ptr< UpwardEdgeInserterModulem_inserter
 The edge insertion module. More...
 
int m_runs
 
std::unique_ptr< FUPSModulem_subgraph
 The upward planar subgraph algorithm. More...
 

Private Member Functions

void constructComponentGraphs (BCTree &BC, NodeArray< GraphCopy > &biComps)
 
void dfsMerge (const GraphCopy &GC, BCTree &BC, NodeArray< GraphCopy > &biComps, NodeArray< 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.createEmpty(G);
sup.call(U, 0, 0);

Definition at line 66 of file SubgraphUpwardPlanarizer.h.

Constructor & Destructor Documentation

◆ SubgraphUpwardPlanarizer()

ogdf::SubgraphUpwardPlanarizer::SubgraphUpwardPlanarizer ( )
inline

Creates an instance of subgraph planarizer.

Definition at line 71 of file SubgraphUpwardPlanarizer.h.

Member Function Documentation

◆ constructComponentGraphs()

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

◆ dfsMerge()

void ogdf::SubgraphUpwardPlanarizer::dfsMerge ( const GraphCopy GC,
BCTree BC,
NodeArray< GraphCopy > &  biComps,
NodeArray< 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
UPRrepresents 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!
costpoints to an edge array that gives the cost of each edge. If cost = 0, all edges have cost 1.
forbidpoints 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 95 of file SubgraphUpwardPlanarizer.h.

◆ runs() [2/2]

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

Definition at line 96 of file SubgraphUpwardPlanarizer.h.

◆ setAcyclicSubgraphModule()

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

Sets the module option for acyclic subgraph module.

Definition at line 91 of file SubgraphUpwardPlanarizer.h.

◆ setInserter()

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

Sets the module option for the edge insertion module.

Definition at line 86 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 81 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 106 of file SubgraphUpwardPlanarizer.h.

◆ m_inserter

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

The edge insertion module.

Definition at line 105 of file SubgraphUpwardPlanarizer.h.

◆ m_runs

int ogdf::SubgraphUpwardPlanarizer::m_runs
protected

Definition at line 107 of file SubgraphUpwardPlanarizer.h.

◆ m_subgraph

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

The upward planar subgraph algorithm.

Definition at line 104 of file SubgraphUpwardPlanarizer.h.


The documentation for this class was generated from the following file:
ogdf::SubgraphUpwardPlanarizer::SubgraphUpwardPlanarizer
SubgraphUpwardPlanarizer()
Creates an instance of subgraph planarizer.
Definition: SubgraphUpwardPlanarizer.h:71