|
|||
|
|
|
|||
|
|
Exact computation of a maximum planar subgraph. More...
#include <ogdf/planarity/MaximumPlanarSubgraph.h>
Inheritance diagram for ogdf::MaximumPlanarSubgraph< TCost >:Public Member Functions | |
| MaximumPlanarSubgraph () | |
| virtual | ~MaximumPlanarSubgraph () |
| virtual MaximumPlanarSubgraph * | clone () const override |
| Returns a new instance of the planar subgraph module with the same option settings. | |
| Public Member Functions inherited from ogdf::PlanarSubgraphModule< TCost > | |
| 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. | |
| 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 | |
| Timeouter & | operator= (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 Module::ReturnType | doCall (const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferredImplyPlanar) override |
Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph. | |
Private Member Functions | |
| Module::ReturnType | callWithDouble (MaximumCPlanarSubgraph &mc, const Graph &G, const EdgeArray< double > *pCost, List< edge > &delEdges) |
| template<typename U = TCost> | |
| Module::ReturnType | callWithDouble (MaximumCPlanarSubgraph &mc, const Graph &G, const EdgeArray< U > *pCost, List< edge > &delEdges) |
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). | |
Exact computation of a maximum planar subgraph.
Definition at line 50 of file MaximumPlanarSubgraph.h.
|
inline |
Definition at line 53 of file MaximumPlanarSubgraph.h.
|
inlinevirtual |
Definition at line 56 of file MaximumPlanarSubgraph.h.
|
inlineprivate |
Definition at line 193 of file MaximumPlanarSubgraph.h.
|
inlineprivate |
Definition at line 180 of file MaximumPlanarSubgraph.h.
|
inlineoverridevirtual |
Returns a new instance of the planar subgraph module with the same option settings.
Implements ogdf::PlanarSubgraphModule< TCost >.
Definition at line 58 of file MaximumPlanarSubgraph.h.
|
inlineoverrideprotectedvirtual |
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. |
Implements ogdf::PlanarSubgraphModule< TCost >.
Definition at line 68 of file MaximumPlanarSubgraph.h.
