Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PlanarSubgraphFast< TCost > Class Template Reference

Computation of a planar subgraph using PQ-trees. More...

#include <ogdf/planarity/PlanarSubgraphFast.h>

+ Inheritance diagram for ogdf::PlanarSubgraphFast< TCost >:

Classes

class  ThreadMaster
 
class  Worker
 

Public Member Functions

 PlanarSubgraphFast ()
 Creates an instance of the fast planar subgraph algorithm with default settings (runs = 10). More...
 
virtual PlanarSubgraphFastclone () const override
 Returns a new instance of fast planar subgraph with the same option settings. More...
 
int runs () const
 Returns the current number of randomized runs. More...
 
void runs (int nRuns)
 Sets the number of randomized runs to nRuns. More...
 
- Public Member Functions inherited from ogdf::PlanarSubgraphModule< TCost >
 PlanarSubgraphModule ()
 Initializes a planar subgraph module (default constructor). More...
 
ReturnType call (const Graph &G, const EdgeArray< TCost > &cost, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false)
 Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More...
 
ReturnType call (const Graph &G, const EdgeArray< TCost > &cost, List< edge > &delEdges)
 Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More...
 
ReturnType call (const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false)
 Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More...
 
ReturnType call (const Graph &G, List< edge > &delEdges)
 Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More...
 
ReturnType callAndDelete (GraphCopy &GC, const List< edge > &preferredEdges, List< edge > &delOrigEdges, bool preferredImplyPlanar=false)
 Makes GC planar by deleting edges. More...
 
ReturnType callAndDelete (GraphCopy &GC, List< edge > &delOrigEdges)
 Makes G planar by deleting edges. More...
 
unsigned int maxThreads () const
 Returns the maximal number of used threads. More...
 
void maxThreads (unsigned int n)
 Sets the maximal number of used threads to n. More...
 
ReturnType operator() (const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false)
 Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More...
 
ReturnType operator() (const Graph &G, List< edge > &delEdges)
 Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More...
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module. More...
 
virtual ~Module ()
 
- Public Member Functions inherited from ogdf::Timeouter
 Timeouter ()
 timeout is turned of by default More...
 
 Timeouter (bool t)
 timeout is turned off (false) or on (true) (with 0 second) More...
 
 Timeouter (const Timeouter &t)
 
 Timeouter (double t)
 timeout is set to the given value (seconds) More...
 
 ~Timeouter ()
 
bool isTimeLimit () const
 returns whether any time limit is set or not More...
 
Timeouteroperator= (const Timeouter &t)
 
double timeLimit () const
 returns the current time limit for the call More...
 
void timeLimit (bool t)
 shorthand to turn timelimit off or on (with 0 seconds) More...
 
void timeLimit (double t)
 sets the time limit for the call (in seconds); <0 means no limit. More...
 

Protected Member Functions

virtual Module::ReturnType doCall (const Graph &G, const List< edge > &preferedEdges, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferedImplyPlanar) override
 Returns true, if G is planar, false otherwise. More...
 

Private Types

using BlockType = std::pair< Graph *, EdgeArray< edge > * >
 

Private Member Functions

void parCall (const Array< BlockType > &block, const EdgeArray< TCost > *pCost, int nRuns, unsigned int nThreads, List< edge > &delEdges)
 Realizes the parallel implementation. More...
 
void seqCall (const Array< BlockType > &block, const EdgeArray< TCost > *pCost, int nRuns, bool randomize, List< edge > &delEdges)
 Realizes the sequential implementation. More...
 

Static Private Member Functions

static void doWorkHelper (ThreadMaster &master)
 
static void planarize (const Graph &G, NodeArray< int > &numbering, List< edge > &delEdges)
 Performs a planarization on a biconnected component of G. More...
 

Private Attributes

int m_nRuns
 The number of runs for randomization. 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...
 
- Protected Attributes inherited from ogdf::Timeouter
double m_timeLimit
 Time limit for module calls (< 0 means no limit). More...
 

Detailed Description

template<typename TCost>
class ogdf::PlanarSubgraphFast< TCost >

Computation of a planar subgraph using PQ-trees.

Literature: Jayakumar, Thulasiraman, Swamy 1989

Optional Parameters

OptionTypeDefaultDescription
runsint0 the number of randomized runs performed by the algorithm; the best solution is picked among all the runs. If runs is 0, one deterministic run is performed.

Observe that this algorithm by theory does not compute a maximal planar subgraph. It is however the fastest known good heuristic.

Definition at line 68 of file PlanarSubgraphFast.h.

Member Typedef Documentation

◆ BlockType

template<typename TCost >
using ogdf::PlanarSubgraphFast< TCost >::BlockType = std::pair<Graph*,EdgeArray<edge>*>
private

Definition at line 70 of file PlanarSubgraphFast.h.

Constructor & Destructor Documentation

◆ PlanarSubgraphFast()

template<typename TCost >
ogdf::PlanarSubgraphFast< TCost >::PlanarSubgraphFast ( )
inline

Creates an instance of the fast planar subgraph algorithm with default settings (runs = 10).

Definition at line 164 of file PlanarSubgraphFast.h.

Member Function Documentation

◆ clone()

template<typename TCost >
virtual PlanarSubgraphFast* ogdf::PlanarSubgraphFast< TCost >::clone ( ) const
inlineoverridevirtual

Returns a new instance of fast planar subgraph with the same option settings.

Implements ogdf::PlanarSubgraphModule< TCost >.

Definition at line 169 of file PlanarSubgraphFast.h.

◆ doCall()

template<typename TCost >
virtual Module::ReturnType ogdf::PlanarSubgraphFast< TCost >::doCall ( const Graph G,
const List< edge > &  preferedEdges,
List< edge > &  delEdges,
const EdgeArray< TCost > *  pCost,
bool  preferedImplyPlanar 
)
inlineoverrideprotectedvirtual

Returns true, if G is planar, false otherwise.

Implements ogdf::PlanarSubgraphModule< TCost >.

Definition at line 191 of file PlanarSubgraphFast.h.

◆ doWorkHelper()

template<typename TCost >
static void ogdf::PlanarSubgraphFast< TCost >::doWorkHelper ( ThreadMaster master)
inlinestaticprivate

Definition at line 410 of file PlanarSubgraphFast.h.

◆ parCall()

template<typename TCost >
void ogdf::PlanarSubgraphFast< TCost >::parCall ( const Array< BlockType > &  block,
const EdgeArray< TCost > *  pCost,
int  nRuns,
unsigned int  nThreads,
List< edge > &  delEdges 
)
inlineprivate

Realizes the parallel implementation.

Definition at line 329 of file PlanarSubgraphFast.h.

◆ planarize()

template<typename TCost >
static void ogdf::PlanarSubgraphFast< TCost >::planarize ( const Graph G,
NodeArray< int > &  numbering,
List< edge > &  delEdges 
)
inlinestaticprivate

Performs a planarization on a biconnected component of G.

The numbering contains an st-numbering of the component.

Definition at line 357 of file PlanarSubgraphFast.h.

◆ runs() [1/2]

template<typename TCost >
int ogdf::PlanarSubgraphFast< TCost >::runs ( ) const
inline

Returns the current number of randomized runs.

Definition at line 181 of file PlanarSubgraphFast.h.

◆ runs() [2/2]

template<typename TCost >
void ogdf::PlanarSubgraphFast< TCost >::runs ( int  nRuns)
inline

Sets the number of randomized runs to nRuns.

Definition at line 176 of file PlanarSubgraphFast.h.

◆ seqCall()

template<typename TCost >
void ogdf::PlanarSubgraphFast< TCost >::seqCall ( const Array< BlockType > &  block,
const EdgeArray< TCost > *  pCost,
int  nRuns,
bool  randomize,
List< edge > &  delEdges 
)
inlineprivate

Realizes the sequential implementation.

Definition at line 269 of file PlanarSubgraphFast.h.

Member Data Documentation

◆ m_nRuns

template<typename TCost >
int ogdf::PlanarSubgraphFast< TCost >::m_nRuns
private

The number of runs for randomization.

Definition at line 266 of file PlanarSubgraphFast.h.


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