Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ogdf::EmbedderOptimalFlexDraw Class Reference

The algorithm computes a planar embedding with minimum cost. More...

#include <ogdf/planarity/EmbedderOptimalFlexDraw.h>

+ Inheritance diagram for ogdf::EmbedderOptimalFlexDraw:

Public Member Functions

 EmbedderOptimalFlexDraw ()
 
void cost (EdgeArray< int > *cost)
 Sets bend costs for each edge.
 
virtual void doCall (Graph &G, adjEntry &adjExternal) override
 Calls the embedder algorithm for graph G.
 
void setMinCostFlowComputer (MinCostFlowModule< int > *pMinCostFlowComputer)
 Sets the module option to compute min-cost flow.
 
- Public Member Functions inherited from ogdf::EmbedderModule
 EmbedderModule ()
 Initializes an embedder module.
 
virtual ~EmbedderModule ()
 
void call (Graph &G, adjEntry &adjExternal)
 Calls the embedder algorithm for graph G.
 
void operator() (Graph &G, adjEntry &adjExternal)
 Calls the embedder algorithm for graph G.
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module.
 
virtual ~Module ()
 
- Public Member Functions inherited from ogdf::Timeouter
 Timeouter ()
 timeout is turned of by default
 
 Timeouter (bool t)
 timeout is turned off (false) or on (true) (with 0 second)
 
 Timeouter (const Timeouter &t)
 
 Timeouter (double t)
 timeout is set to the given value (seconds)
 
 ~Timeouter ()
 
bool isTimeLimit () const
 returns whether any time limit is set or not
 
Timeouteroperator= (const Timeouter &t)
 
double timeLimit () const
 returns the current time limit for the call
 
void timeLimit (bool t)
 shorthand to turn timelimit off or on (with 0 seconds)
 
void timeLimit (double t)
 sets the time limit for the call (in seconds); <0 means no limit.
 

Private Member Functions

void computePrincipalSplitComponentCost (StaticPlanarSPQRTree &T, NodeArray< int > cost[], NodeArray< long long > embedding[], node parent, node mu)
 
void createNetwork (node parent, node mu, int bends, NodeArray< int > cost[], Skeleton &skeleton, EdgeArray< node > &edgeNode, Graph &N, EdgeArray< int > &upper, EdgeArray< int > &perUnitCost, NodeArray< int > &supply)
 
void optimizeOverEmbeddings (StaticPlanarSPQRTree &T, node parent, node mu, int bends, NodeArray< int > cost[], NodeArray< long long > embedding[])
 

Private Attributes

EdgeArray< int > * m_cost
 
std::unique_ptr< MinCostFlowModule< int > > m_minCostFlowComputer
 

Additional Inherited Members

- Public Types inherited from ogdf::Module
enum class  ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , 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.
 
- Protected Attributes inherited from ogdf::Timeouter
double m_timeLimit
 Time limit for module calls (< 0 means no limit).
 

Detailed Description

The algorithm computes a planar embedding with minimum cost.

See paper "Optimal Orthogonal Graph Drawing with Convex Bend Costs" by Thomas Blasius, Ignaz Rutter, Dorothea Wagner (2012) for details.

Definition at line 49 of file EmbedderOptimalFlexDraw.h.

Constructor & Destructor Documentation

◆ EmbedderOptimalFlexDraw()

ogdf::EmbedderOptimalFlexDraw::EmbedderOptimalFlexDraw ( )

Member Function Documentation

◆ computePrincipalSplitComponentCost()

void ogdf::EmbedderOptimalFlexDraw::computePrincipalSplitComponentCost ( StaticPlanarSPQRTree T,
NodeArray< int cost[],
NodeArray< long long embedding[],
node  parent,
node  mu 
)
private

◆ cost()

void ogdf::EmbedderOptimalFlexDraw::cost ( EdgeArray< int > *  cost)
inline

Sets bend costs for each edge.

Definition at line 61 of file EmbedderOptimalFlexDraw.h.

◆ createNetwork()

void ogdf::EmbedderOptimalFlexDraw::createNetwork ( node  parent,
node  mu,
int  bends,
NodeArray< int cost[],
Skeleton skeleton,
EdgeArray< node > &  edgeNode,
Graph N,
EdgeArray< int > &  upper,
EdgeArray< int > &  perUnitCost,
NodeArray< int > &  supply 
)
private

◆ doCall()

virtual void ogdf::EmbedderOptimalFlexDraw::doCall ( Graph G,
adjEntry adjExternal 
)
overridevirtual

Calls the embedder algorithm for graph G.

G is guaranteed to be planar. See call .

Implements ogdf::EmbedderModule.

◆ optimizeOverEmbeddings()

void ogdf::EmbedderOptimalFlexDraw::optimizeOverEmbeddings ( StaticPlanarSPQRTree T,
node  parent,
node  mu,
int  bends,
NodeArray< int cost[],
NodeArray< long long embedding[] 
)
private

◆ setMinCostFlowComputer()

void ogdf::EmbedderOptimalFlexDraw::setMinCostFlowComputer ( MinCostFlowModule< int > *  pMinCostFlowComputer)
inline

Sets the module option to compute min-cost flow.

Definition at line 56 of file EmbedderOptimalFlexDraw.h.

Member Data Documentation

◆ m_cost

EdgeArray<int>* ogdf::EmbedderOptimalFlexDraw::m_cost
private

Definition at line 66 of file EmbedderOptimalFlexDraw.h.

◆ m_minCostFlowComputer

std::unique_ptr<MinCostFlowModule<int> > ogdf::EmbedderOptimalFlexDraw::m_minCostFlowComputer
private

Definition at line 64 of file EmbedderOptimalFlexDraw.h.


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