Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ogdf::PlanarSubgraphModule< TCost > Class Template Referenceabstract

Interface for planar subgraph algorithms. More...

#include <ogdf/planarity/PlanarSubgraphModule.h>

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

Public Member Functions

 PlanarSubgraphModule ()
 Initializes a planar subgraph module (default constructor).
 
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.
 
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.
 
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.
 
ReturnType call (const Graph &G, List< edge > &delEdges)
 Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.
 
ReturnType callAndDelete (GraphCopy &GC, const List< edge > &preferredEdges, List< edge > &delOrigEdges, bool preferredImplyPlanar=false)
 Makes GC planar by deleting edges.
 
ReturnType callAndDelete (GraphCopy &GC, List< edge > &delOrigEdges)
 Makes G planar by deleting edges.
 
virtual PlanarSubgraphModuleclone () const =0
 Returns a new instance of the planar subgraph module with the same option settings.
 
unsigned int maxThreads () const
 Returns the maximal number of used threads.
 
void maxThreads (unsigned int n)
 Sets the maximal number of used threads to n.
 
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.
 
ReturnType operator() (const Graph &G, List< edge > &delEdges)
 Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.
 
- 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.
 

Protected Member Functions

virtual ReturnType doCall (const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, const EdgeArray< TCost > *pCost=nullptr, bool preferredImplyPlanar=false)=0
 Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph.
 

Private Attributes

unsigned int m_maxThreads
 The maximal number of used threads.
 

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

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

Interface for planar subgraph algorithms.

See also
PlanarizationLayout, PlanarizationGridLayout

Definition at line 48 of file PlanarSubgraphModule.h.

Constructor & Destructor Documentation

◆ PlanarSubgraphModule()

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

Initializes a planar subgraph module (default constructor).

Definition at line 53 of file PlanarSubgraphModule.h.

Member Function Documentation

◆ call() [1/4]

template<typename TCost >
ReturnType ogdf::PlanarSubgraphModule< TCost >::call ( const Graph G,
const EdgeArray< TCost > &  cost,
const List< edge > &  preferredEdges,
List< edge > &  delEdges,
bool  preferredImplyPlanar = false 
)
inline

Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.

Parameters
Gis the input graph.
costare the costs of edges.
preferredEdgesare edges that should be contained in the planar subgraph.
delEdgesis the set of edges that need to be deleted to obtain the planar subgraph.
preferredImplyPlanarindicates that the edges preferredEdges induce a planar graph.

Definition at line 69 of file PlanarSubgraphModule.h.

◆ call() [2/4]

template<typename TCost >
ReturnType ogdf::PlanarSubgraphModule< TCost >::call ( const Graph G,
const EdgeArray< TCost > &  cost,
List< edge > &  delEdges 
)
inline

Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.

Parameters
Gis the input graph.
costare the costs of edges.
delEdgesis the set of edges that need to be deleted to obtain the planar subgraph.

Definition at line 92 of file PlanarSubgraphModule.h.

◆ call() [3/4]

template<typename TCost >
ReturnType ogdf::PlanarSubgraphModule< TCost >::call ( const Graph G,
const List< edge > &  preferredEdges,
List< edge > &  delEdges,
bool  preferredImplyPlanar = false 
)
inline

Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.

Parameters
Gis the input graph.
preferredEdgesare edges that should be contained in the planar subgraph.
delEdgesis the set of edges that need to be deleted to obtain the planar subgraph.
preferredImplyPlanarindicates that the edges preferredEdges induce a planar graph.

Definition at line 81 of file PlanarSubgraphModule.h.

◆ call() [4/4]

template<typename TCost >
ReturnType ogdf::PlanarSubgraphModule< TCost >::call ( const Graph G,
List< edge > &  delEdges 
)
inline

Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.

Parameters
Gis the input graph.
delEdgesis the set of edges that need to be deleted to obtain the planar subgraph.

Definition at line 102 of file PlanarSubgraphModule.h.

◆ callAndDelete() [1/2]

template<typename TCost >
ReturnType ogdf::PlanarSubgraphModule< TCost >::callAndDelete ( GraphCopy GC,
const List< edge > &  preferredEdges,
List< edge > &  delOrigEdges,
bool  preferredImplyPlanar = false 
)
inline

Makes GC planar by deleting edges.

Parameters
GCis a copy of the input graph.
preferredEdgesare edges in GC that should be contained in the planar subgraph.
delOrigEdgesis the set of original edges whose copy has been deleted in GC.
preferredImplyPlanarindicates that the edges preferredEdges induce a planar graph.

Definition at line 123 of file PlanarSubgraphModule.h.

◆ callAndDelete() [2/2]

template<typename TCost >
ReturnType ogdf::PlanarSubgraphModule< TCost >::callAndDelete ( GraphCopy GC,
List< edge > &  delOrigEdges 
)
inline

Makes G planar by deleting edges.

Parameters
GCis a copy of the input graph.
delOrigEdgesis the set of original edges whose copy has been deleted in GC.

Definition at line 141 of file PlanarSubgraphModule.h.

◆ clone()

◆ doCall()

template<typename TCost >
virtual ReturnType ogdf::PlanarSubgraphModule< TCost >::doCall ( const Graph G,
const List< edge > &  preferredEdges,
List< edge > &  delEdges,
const EdgeArray< TCost > *  pCost = nullptr,
bool  preferredImplyPlanar = false 
)
protectedpure virtual

Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph.

This is the actual algorithm call and needs to be implemented by derived classes.

Parameters
Gis the input graph.
preferredEdgesare edges that should be contained in the planar subgraph.
delEdgesis the set of edges that need to be deleted to obtain the planar subgraph.
pCostis apointer to an edge array containing the edge costs; this pointer can be 0 if no costs are given (all edges have cost 1).
preferredImplyPlanarindicates that the edges preferredEdges induce a planar graph.

Implemented in ogdf::PlanarSubgraphFast< TCost >, ogdf::MaximumPlanarSubgraph< TCost >, ogdf::PlanarSubgraphTriangles< TCost >, ogdf::PlanarSubgraphBoyerMyrvold, ogdf::PlanarSubgraphEmpty< TCost >, ogdf::PlanarSubgraphTree< TCost >, ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >, and ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >.

◆ maxThreads() [1/2]

template<typename TCost >
unsigned int ogdf::PlanarSubgraphModule< TCost >::maxThreads ( ) const
inline

Returns the maximal number of used threads.

Definition at line 150 of file PlanarSubgraphModule.h.

◆ maxThreads() [2/2]

template<typename TCost >
void ogdf::PlanarSubgraphModule< TCost >::maxThreads ( unsigned int  n)
inline

Sets the maximal number of used threads to n.

Definition at line 153 of file PlanarSubgraphModule.h.

◆ operator()() [1/2]

template<typename TCost >
ReturnType ogdf::PlanarSubgraphModule< TCost >::operator() ( const Graph G,
const List< edge > &  preferredEdges,
List< edge > &  delEdges,
bool  preferredImplyPlanar = false 
)
inline

Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.

Definition at line 108 of file PlanarSubgraphModule.h.

◆ operator()() [2/2]

template<typename TCost >
ReturnType ogdf::PlanarSubgraphModule< TCost >::operator() ( const Graph G,
List< edge > &  delEdges 
)
inline

Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph.

Definition at line 114 of file PlanarSubgraphModule.h.

Member Data Documentation

◆ m_maxThreads

template<typename TCost >
unsigned int ogdf::PlanarSubgraphModule< TCost >::m_maxThreads
private

The maximal number of used threads.

Definition at line 49 of file PlanarSubgraphModule.h.


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