Interface for planar subgraph algorithms. More...
#include <ogdf/planarity/PlanarSubgraphModule.h>
Public Member Functions | |
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... | |
virtual PlanarSubgraphModule * | clone () const =0 |
Returns a new instance of the planar subgraph module with the same option settings. 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... | |
Timeouter & | operator= (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 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. More... | |
Private Attributes | |
unsigned int | m_maxThreads |
The maximal number of used threads. 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... | |
Interface for planar subgraph algorithms.
Definition at line 48 of file PlanarSubgraphModule.h.
|
inline |
Initializes a planar subgraph module (default constructor).
Definition at line 53 of file PlanarSubgraphModule.h.
|
inline |
Returns the set of edges delEdges
which have to be deleted to obtain the planar subgraph.
G | is the input graph. |
cost | are the costs of edges. |
preferredEdges | are edges that should be contained in the planar subgraph. |
delEdges | is the set of edges that need to be deleted to obtain the planar subgraph. |
preferredImplyPlanar | indicates that the edges preferredEdges induce a planar graph. |
Definition at line 69 of file PlanarSubgraphModule.h.
|
inline |
Returns the set of edges delEdges
which have to be deleted to obtain the planar subgraph.
G | is the input graph. |
cost | are the costs of edges. |
delEdges | is the set of edges that need to be deleted to obtain the planar subgraph. |
Definition at line 92 of file PlanarSubgraphModule.h.
|
inline |
Returns the set of edges delEdges
which have to be deleted to obtain the planar subgraph.
G | is the input graph. |
preferredEdges | are edges that should be contained in the planar subgraph. |
delEdges | is the set of edges that need to be deleted to obtain the planar subgraph. |
preferredImplyPlanar | indicates that the edges preferredEdges induce a planar graph. |
Definition at line 81 of file PlanarSubgraphModule.h.
|
inline |
Returns the set of edges delEdges
which have to be deleted to obtain the planar subgraph.
G | is the input graph. |
delEdges | is the set of edges that need to be deleted to obtain the planar subgraph. |
Definition at line 102 of file PlanarSubgraphModule.h.
|
inline |
Makes GC
planar by deleting edges.
GC | is a copy of the input graph. |
preferredEdges | are edges in GC that should be contained in the planar subgraph. |
delOrigEdges | is the set of original edges whose copy has been deleted in GC . |
preferredImplyPlanar | indicates that the edges preferredEdges induce a planar graph. |
Definition at line 123 of file PlanarSubgraphModule.h.
|
inline |
Makes G
planar by deleting edges.
GC | is a copy of the input graph. |
delOrigEdges | is the set of original edges whose copy has been deleted in GC . |
Definition at line 141 of file PlanarSubgraphModule.h.
|
pure virtual |
Returns a new instance of the planar subgraph module with the same option settings.
Implemented in ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >, ogdf::PlanarSubgraphFast< TCost >, ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >, ogdf::PlanarSubgraphTriangles< TCost >, ogdf::MaximumPlanarSubgraph< TCost >, ogdf::PlanarSubgraphCactus< TCost >, ogdf::PlanarSubgraphTree< TCost >, and ogdf::PlanarSubgraphEmpty< TCost >.
|
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.
G | is the input graph. |
preferredEdges | are edges that should be contained in the planar subgraph. |
delEdges | is the set of edges that need to be deleted to obtain the planar subgraph. |
pCost | is apointer to an edge array containing the edge costs; this pointer can be 0 if no costs are given (all edges have cost 1). |
preferredImplyPlanar | indicates that the edges preferredEdges induce a planar graph. |
Implemented in ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >, ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_integral< TCost >::value >::type >, ogdf::PlanarSubgraphTree< TCost >, ogdf::PlanarSubgraphEmpty< TCost >, ogdf::PlanarSubgraphBoyerMyrvold, ogdf::PlanarSubgraphTriangles< TCost >, ogdf::MaximumPlanarSubgraph< TCost >, and ogdf::PlanarSubgraphFast< TCost >.
|
inline |
Returns the maximal number of used threads.
Definition at line 150 of file PlanarSubgraphModule.h.
|
inline |
Sets the maximal number of used threads to n
.
Definition at line 153 of file PlanarSubgraphModule.h.
|
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.
|
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.
|
private |
The maximal number of used threads.
Definition at line 49 of file PlanarSubgraphModule.h.