#include <ogdf/planarity/MaximalPlanarSubgraphSimple.h>
Public Member Functions | |
MaximalPlanarSubgraphSimple () | |
Constructor. More... | |
MaximalPlanarSubgraphSimple (PlanarSubgraphModule< TCost > &heuristic, double randomness=0.0, unsigned int runs=1) | |
Constructor. More... | |
virtual | ~MaximalPlanarSubgraphSimple () |
Destructor. More... | |
virtual MaximalPlanarSubgraphSimple * | clone () const override |
Clone method. More... | |
void | setSeed (unsigned seed) |
set seed of std::default_random_engine generator to use when randomness > 0 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... | |
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 Module::ReturnType | doCall (const Graph &graph, 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. More... | |
Private Member Functions | |
TCost | weightOfList (const List< edge > &list, const EdgeArray< TCost > &weights) |
Private Attributes | |
bool | m_deleteHeuristic |
flag to store we have to delete a self created heuristic More... | |
PlanarSubgraphModule< TCost > & | m_heuristic |
user given heuristic More... | |
std::default_random_engine | m_randomGenerator |
random generator to use with std::uniform_real_distribution More... | |
double | m_randomness |
randomness of the process: use 0 to compute everything based on the costs, use 1 for completely randomness More... | |
unsigned int | m_runs |
number of runs when algorithms is randomized 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... | |
Definition at line 135 of file MaximalPlanarSubgraphSimple.h.
|
inline |
Constructor.
Default constructor with PlanarSubgraphEmpty as pre-executed heuristic before the extension to maximality. randomness is set to 0 and runs is set to 1
Definition at line 144 of file MaximalPlanarSubgraphSimple.h.
|
inlineexplicit |
Constructor.
heuristic | user given instance of PlanarSubgraphModule that is executed before extending the solution to maximality. |
randomness | randomness of the process: use 0 to compute everything based on the costs, use 1 for completely randomness |
runs | number of runs when randomness > 0, the best solution is returned by call |
Definition at line 157 of file MaximalPlanarSubgraphSimple.h.
|
inlinevirtual |
Destructor.
Definition at line 168 of file MaximalPlanarSubgraphSimple.h.
|
inlineoverridevirtual |
Clone method.
Implements ogdf::PlanarSubgraphModule< TCost >.
Definition at line 175 of file MaximalPlanarSubgraphSimple.h.
|
inlineoverrideprotectedvirtual |
Computes the set of edges delEdges
which have to be deleted to obtain the planar subgraph.
graph | 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 199 of file MaximalPlanarSubgraphSimple.h.
|
inline |
set seed of std::default_random_engine generator to use when randomness > 0
seed | user given seed value |
Definition at line 186 of file MaximalPlanarSubgraphSimple.h.
|
inlineprivate |
list | list of edges to sum over |
weights | EdgeArray with weights |
weights
over the given list list
Definition at line 298 of file MaximalPlanarSubgraphSimple.h.
|
private |
flag to store we have to delete a self created heuristic
Definition at line 288 of file MaximalPlanarSubgraphSimple.h.
|
private |
user given heuristic
Definition at line 287 of file MaximalPlanarSubgraphSimple.h.
|
private |
random generator to use with std::uniform_real_distribution
Definition at line 290 of file MaximalPlanarSubgraphSimple.h.
|
private |
randomness of the process: use 0 to compute everything based on the costs, use 1 for completely randomness
Definition at line 289 of file MaximalPlanarSubgraphSimple.h.
|
private |
number of runs when algorithms is randomized
Definition at line 291 of file MaximalPlanarSubgraphSimple.h.