|
|||
|
|
|
|||
|
|
#include <ogdf/planarity/MaximalPlanarSubgraphSimple.h>
Inheritance diagram for ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >: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 142 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 151 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 164 of file MaximalPlanarSubgraphSimple.h.
|
inlinevirtual |
Destructor.
Definition at line 175 of file MaximalPlanarSubgraphSimple.h.
|
inlineoverridevirtual |
Clone method.
Implements ogdf::PlanarSubgraphModule< TCost >.
Definition at line 182 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 206 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 193 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 305 of file MaximalPlanarSubgraphSimple.h.
|
private |
flag to store we have to delete a self created heuristic
Definition at line 295 of file MaximalPlanarSubgraphSimple.h.
|
private |
user given heuristic
Definition at line 294 of file MaximalPlanarSubgraphSimple.h.
|
private |
random generator to use with std::uniform_real_distribution
Definition at line 297 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 296 of file MaximalPlanarSubgraphSimple.h.
|
private |
number of runs when algorithms is randomized
Definition at line 298 of file MaximalPlanarSubgraphSimple.h.