Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PlanarSubgraphBoyerMyrvold Class Reference

Maximum planar subgraph heuristic based on the Boyer-Myrvold planarity test. More...

#include <ogdf/planarity/PlanarSubgraphBoyerMyrvold.h>

+ Inheritance diagram for ogdf::PlanarSubgraphBoyerMyrvold:

Public Member Functions

 PlanarSubgraphBoyerMyrvold (int runs=1, double randomness=0)
 Creates a new Boyer-Myrvold subgraph module. More...
 
 ~PlanarSubgraphBoyerMyrvold ()
 
virtual PlanarSubgraphBoyerMyrvoldclone () const override
 
void seed (std::minstd_rand rand)
 Seeds the random generator for performing a random DFS. If this method is never called the random generator will be seeded by a value extracted from the global random generator. More...
 
- Public Member Functions inherited from ogdf::PlanarSubgraphModule< int >
 PlanarSubgraphModule ()
 Initializes a planar subgraph module (default constructor). More...
 
ReturnType call (const Graph &G, const EdgeArray< int > &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< int > &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 PlanarSubgraphModuleclone () 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...
 
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 ReturnType doCall (const Graph &graph, const List< edge > &preferedEdges, List< edge > &delEdges, const EdgeArray< int > *pCost, bool preferedImplyPlanar) override
 Constructs a planar subgraph according to the options supplied to the constructor. More...
 
bool isRemoved (const GraphCopy &copy, const edge e)
 Returns true iff this edge could not be embedded. More...
 

Private Attributes

BoothLueker m_planModule
 
std::minstd_rand m_rand
 
double m_randomness
 
int m_runs
 

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

Maximum planar subgraph heuristic based on the Boyer-Myrvold planarity test.

Computes a (possibly non-maximal) planar subgraph using the ogdf::BoyerMyrvold planarity test. Runs in linear time.

Definition at line 50 of file PlanarSubgraphBoyerMyrvold.h.

Constructor & Destructor Documentation

◆ PlanarSubgraphBoyerMyrvold()

ogdf::PlanarSubgraphBoyerMyrvold::PlanarSubgraphBoyerMyrvold ( int  runs = 1,
double  randomness = 0 
)
inlineexplicit

Creates a new Boyer-Myrvold subgraph module.

Parameters
runsThe number of times to start the algorithm, the greatest found subgraph is returned
randomnessIf randomness equals 1, each edge is chosen with the same probability. A randomness of zero chooses each edge according to its cost. Any value between 0 and 1 is allowed and will result in a specific random influence. When performing multiple runs, a randomness greater zero should be chosen.

Definition at line 68 of file PlanarSubgraphBoyerMyrvold.h.

◆ ~PlanarSubgraphBoyerMyrvold()

ogdf::PlanarSubgraphBoyerMyrvold::~PlanarSubgraphBoyerMyrvold ( )
inline

Definition at line 74 of file PlanarSubgraphBoyerMyrvold.h.

Member Function Documentation

◆ clone()

virtual PlanarSubgraphBoyerMyrvold* ogdf::PlanarSubgraphBoyerMyrvold::clone ( ) const
inlineoverridevirtual

Definition at line 76 of file PlanarSubgraphBoyerMyrvold.h.

◆ doCall()

virtual ReturnType ogdf::PlanarSubgraphBoyerMyrvold::doCall ( const Graph graph,
const List< edge > &  preferedEdges,
List< edge > &  delEdges,
const EdgeArray< int > *  pCost,
bool  preferedImplyPlanar 
)
overrideprotectedvirtual

Constructs a planar subgraph according to the options supplied to the constructor.

Parameters
graphthe Graph to be planarized
preferedEdgesignored
delEdgeswill contain the list of edges that can be deleted to achieve planarity
pCostthe costs for removing each edge
preferedImplyPlanarignored

Implements ogdf::PlanarSubgraphModule< int >.

◆ isRemoved()

bool ogdf::PlanarSubgraphBoyerMyrvold::isRemoved ( const GraphCopy copy,
const edge  e 
)
inlineprotected

Returns true iff this edge could not be embedded.

Definition at line 107 of file PlanarSubgraphBoyerMyrvold.h.

◆ seed()

void ogdf::PlanarSubgraphBoyerMyrvold::seed ( std::minstd_rand  rand)
inline

Seeds the random generator for performing a random DFS. If this method is never called the random generator will be seeded by a value extracted from the global random generator.

Definition at line 83 of file PlanarSubgraphBoyerMyrvold.h.

Member Data Documentation

◆ m_planModule

BoothLueker ogdf::PlanarSubgraphBoyerMyrvold::m_planModule
private

Definition at line 55 of file PlanarSubgraphBoyerMyrvold.h.

◆ m_rand

std::minstd_rand ogdf::PlanarSubgraphBoyerMyrvold::m_rand
private

Definition at line 56 of file PlanarSubgraphBoyerMyrvold.h.

◆ m_randomness

double ogdf::PlanarSubgraphBoyerMyrvold::m_randomness
private

Definition at line 54 of file PlanarSubgraphBoyerMyrvold.h.

◆ m_runs

int ogdf::PlanarSubgraphBoyerMyrvold::m_runs
private

Definition at line 53 of file PlanarSubgraphBoyerMyrvold.h.


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