Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::FastPlanarSubgraph Class Reference

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

#include <ogdf/planarity/FastPlanarSubgraph.h>

+ Inheritance diagram for ogdf::FastPlanarSubgraph:

Public Member Functions

 FastPlanarSubgraph ()
 Creates an instance of the fast planar subgraph algorithm with default settings. More...
 
 FastPlanarSubgraph (const FastPlanarSubgraph &fps)
 Creates an instance of the fast planar subgraph algorithm with the same settings as fps. More...
 
 ~FastPlanarSubgraph ()
 Destructor. More...
 
virtual PlanarSubgraphModuleclone () const
 Returns a new instance of fast planar subgraph with the same option settings. More...
 
FastPlanarSubgraphoperator= (const FastPlanarSubgraph &fps)
 Assignment operator. Copies option settings only. More...
 
void runs (int nRuns)
 Sets the number of randomized runs to nRuns. More...
 
int runs () const
 Returns the current number of randomized runs. More...
 
- Public Member Functions inherited from ogdf::PlanarSubgraphModule
 PlanarSubgraphModule ()
 Initializes a planar subgraph module (default constructor). More...
 
 PlanarSubgraphModule (const PlanarSubgraphModule &psm)
 Initializes a planar subgraph module (copy constructor). More...
 
virtual ~PlanarSubgraphModule ()
 
ReturnType call (const Graph &G, const EdgeArray< int > &cost, const List< edge > &preferedEdges, List< edge > &delEdges, bool preferedImplyPlanar=false)
 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 > &preferedEdges, List< edge > &delEdges, bool preferedImplyPlanar=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< int > &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, 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 > &preferedEdges, List< edge > &delOrigEdges, bool preferedImplyPlanar=false)
 Makes G planar by deleting edges. More...
 
ReturnType callAndDelete (GraphCopy &GC, List< edge > &delOrigEdges)
 Makes G planar by deleting edges. More...
 
int maxThreads () const
 Returns the maximal number of used threads. More...
 
void maxThreads (int n)
 Sets the maximal number of used threads to n. More...
 
ReturnType operator() (const Graph &G, const List< edge > &preferedEdges, List< edge > &delEdges, bool preferedImplyPlanar=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 (double t)
 timeout is set to the given value (seconds) More...
 
 Timeouter (bool t)
 timeout is turned off (false) or on (true) (with 0 second) More...
 
 Timeouter (const Timeouter &t)
 
 ~Timeouter ()
 
bool isTimeLimit () const
 returns whether any time limit is set or not More...
 
Timeouteroperator= (const Timeouter &t)
 
void timeLimit (double t)
 sets the time limit for the call (in seconds); <0 means no limit. More...
 
void timeLimit (bool t)
 shorthand to turn timelimit off or on (with 0 seconds) More...
 
double timeLimit () const
 returns the current time limit for the call More...
 

Protected Member Functions

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

Private Types

typedef std::pair< Graph *, EdgeArray< edge > * > BlockType
 

Private Member Functions

void parCall (const Array< BlockType > &block, const EdgeArray< int > *pCost, int nRuns, int nThreads, List< edge > &delEdges)
 Realizes the parallel implementation. More...
 
void seqCall (const Array< BlockType > &block, const EdgeArray< int > *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 pf 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 { retFeasible, retOptimal, retNoFeasibleSolution, retTimeoutFeasible, retTimeoutInfeasible, retError }
 The return type of a module. More...
 
- Static Public Member Functions inherited from ogdf::Module
static bool isSolution (ReturnType ret)
 Returns true iff retVal 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

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 79 of file FastPlanarSubgraph.h.

Member Typedef Documentation

Definition at line 82 of file FastPlanarSubgraph.h.

Constructor & Destructor Documentation

ogdf::FastPlanarSubgraph::FastPlanarSubgraph ( )

Creates an instance of the fast planar subgraph algorithm with default settings.

ogdf::FastPlanarSubgraph::FastPlanarSubgraph ( const FastPlanarSubgraph fps)

Creates an instance of the fast planar subgraph algorithm with the same settings as fps.

ogdf::FastPlanarSubgraph::~FastPlanarSubgraph ( )
inline

Destructor.

Definition at line 93 of file FastPlanarSubgraph.h.

Member Function Documentation

virtual PlanarSubgraphModule* ogdf::FastPlanarSubgraph::clone ( ) const
virtual

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

Implements ogdf::PlanarSubgraphModule.

ReturnType ogdf::FastPlanarSubgraph::doCall ( const Graph G,
const List< edge > &  preferedEdges,
List< edge > &  delEdges,
const EdgeArray< int > *  pCost,
bool  preferedImplyPlanar 
)
protectedvirtual

Returns true, if G is planar, false otherwise.

Implements ogdf::PlanarSubgraphModule.

static void ogdf::FastPlanarSubgraph::doWorkHelper ( ThreadMaster &  master)
staticprivate
FastPlanarSubgraph& ogdf::FastPlanarSubgraph::operator= ( const FastPlanarSubgraph fps)

Assignment operator. Copies option settings only.

void ogdf::FastPlanarSubgraph::parCall ( const Array< BlockType > &  block,
const EdgeArray< int > *  pCost,
int  nRuns,
int  nThreads,
List< edge > &  delEdges 
)
private

Realizes the parallel implementation.

static void ogdf::FastPlanarSubgraph::planarize ( const Graph G,
NodeArray< int > &  numbering,
List< edge > &  delEdges 
)
staticprivate

Performs a planarization on a biconnected component pf G.

The numbering contains an st-numbering of the component.

void ogdf::FastPlanarSubgraph::runs ( int  nRuns)
inline

Sets the number of randomized runs to nRuns.

Definition at line 105 of file FastPlanarSubgraph.h.

int ogdf::FastPlanarSubgraph::runs ( ) const
inline

Returns the current number of randomized runs.

Definition at line 110 of file FastPlanarSubgraph.h.

void ogdf::FastPlanarSubgraph::seqCall ( const Array< BlockType > &  block,
const EdgeArray< int > *  pCost,
int  nRuns,
bool  randomize,
List< edge > &  delEdges 
)
private

Realizes the sequential implementation.

Member Data Documentation

int ogdf::FastPlanarSubgraph::m_nRuns
private

The number of runs for randomization.

Definition at line 128 of file FastPlanarSubgraph.h.


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