Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type > Class Template Reference

#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 MaximalPlanarSubgraphSimpleclone () 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...
 
Timeouteroperator= (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...
 

Detailed Description

template<typename TCost>
class ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >

Definition at line 143 of file MaximalPlanarSubgraphSimple.h.

Constructor & Destructor Documentation

◆ MaximalPlanarSubgraphSimple() [1/2]

template<typename TCost >
ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::MaximalPlanarSubgraphSimple ( )
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 152 of file MaximalPlanarSubgraphSimple.h.

◆ MaximalPlanarSubgraphSimple() [2/2]

template<typename TCost >
ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::MaximalPlanarSubgraphSimple ( PlanarSubgraphModule< TCost > &  heuristic,
double  randomness = 0.0,
unsigned int  runs = 1 
)
inlineexplicit

Constructor.

Parameters
heuristicuser given instance of PlanarSubgraphModule that is executed before extending the solution to maximality.
randomnessrandomness of the process: use 0 to compute everything based on the costs, use 1 for completely randomness
runsnumber of runs when randomness > 0, the best solution is returned by call

Definition at line 165 of file MaximalPlanarSubgraphSimple.h.

◆ ~MaximalPlanarSubgraphSimple()

template<typename TCost >
virtual ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::~MaximalPlanarSubgraphSimple ( )
inlinevirtual

Destructor.

Definition at line 176 of file MaximalPlanarSubgraphSimple.h.

Member Function Documentation

◆ clone()

template<typename TCost >
virtual MaximalPlanarSubgraphSimple* ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::clone ( ) const
inlineoverridevirtual

Clone method.

Implements ogdf::PlanarSubgraphModule< TCost >.

Definition at line 183 of file MaximalPlanarSubgraphSimple.h.

◆ doCall()

template<typename TCost >
virtual Module::ReturnType ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::doCall ( const Graph graph,
const List< edge > &  preferredEdges,
List< edge > &  delEdges,
const EdgeArray< TCost > *  pCost,
bool  preferredImplyPlanar 
)
inlineoverrideprotectedvirtual

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

Parameters
graphis 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.

Implements ogdf::PlanarSubgraphModule< TCost >.

Definition at line 210 of file MaximalPlanarSubgraphSimple.h.

◆ setSeed()

template<typename TCost >
void ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::setSeed ( unsigned  seed)
inline

set seed of std::default_random_engine generator to use when randomness > 0

Parameters
seeduser given seed value

Definition at line 193 of file MaximalPlanarSubgraphSimple.h.

◆ weightOfList()

template<typename TCost >
TCost ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::weightOfList ( const List< edge > &  list,
const EdgeArray< TCost > &  weights 
)
inlineprivate
Parameters
listlist of edges to sum over
weightsEdgeArray with weights
Returns
sum the values in weights over the given list list

Definition at line 307 of file MaximalPlanarSubgraphSimple.h.

Member Data Documentation

◆ m_deleteHeuristic

template<typename TCost >
bool ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::m_deleteHeuristic
private

flag to store we have to delete a self created heuristic

Definition at line 297 of file MaximalPlanarSubgraphSimple.h.

◆ m_heuristic

template<typename TCost >
PlanarSubgraphModule<TCost>& ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::m_heuristic
private

user given heuristic

Definition at line 296 of file MaximalPlanarSubgraphSimple.h.

◆ m_randomGenerator

template<typename TCost >
std::default_random_engine ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::m_randomGenerator
private

random generator to use with std::uniform_real_distribution

Definition at line 299 of file MaximalPlanarSubgraphSimple.h.

◆ m_randomness

template<typename TCost >
double ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::m_randomness
private

randomness of the process: use 0 to compute everything based on the costs, use 1 for completely randomness

Definition at line 298 of file MaximalPlanarSubgraphSimple.h.

◆ m_runs

template<typename TCost >
unsigned int ogdf::MaximalPlanarSubgraphSimple< TCost, typename std::enable_if< std::is_floating_point< TCost >::value >::type >::m_runs
private

number of runs when algorithms is randomized

Definition at line 300 of file MaximalPlanarSubgraphSimple.h.


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