Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PlanarSubgraphTriangles< TCost > Class Template Reference

Maximum planar subgraph approximation algorithms by Chalermsook/Schmid and Calinescu et al. More...

#include <ogdf/planarity/PlanarSubgraphTriangles.h>

+ Inheritance diagram for ogdf::PlanarSubgraphTriangles< TCost >:

Public Member Functions

 PlanarSubgraphTriangles (bool onlyTriangles=false)
 Creates a planarization module based on triangle or diamond matching. More...
 
virtual PlanarSubgraphTrianglesclone () const override
 Returns a new instance of the planarization module with the same settings. 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 > &, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferredImplyPlanar=false) override
 Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph. More...
 

Private Member Functions

void findTriangle (GraphCopy &copy, edge currentEdge, const EdgeArray< TCost > *pCost, DisjointSets<> &components, NodeArray< int > &set, std::function< bool(node, edge, edge)> callback)
 Finds all triangles from a given edge and calls a callback function on them. More...
 
edge searchEdge (node target, node source, internal::GraphIterator< adjEntry > connectionIterator)
 Finds an edge, starting at a given iterator. More...
 

Private Attributes

bool m_onlyTriangles
 Whether we want to only check for triangles. 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::PlanarSubgraphTriangles< TCost >

Maximum planar subgraph approximation algorithms by Chalermsook/Schmid and Calinescu et al.

This planarity module supports two algorithms.

  • A greedy one by Calinescu et all with an approximation factor of 7/18
  • A greedy one by Chalermsook and Schmid with an approximation factor of 13/33

The default selection is Chalermsook and Schmid.

Setting preferred edges is not supported. Weighted edges are heuristically respected but there is no approximation guarantee in the weighted case.

Definition at line 54 of file PlanarSubgraphTriangles.h.

Constructor & Destructor Documentation

◆ PlanarSubgraphTriangles()

template<typename TCost >
ogdf::PlanarSubgraphTriangles< TCost >::PlanarSubgraphTriangles ( bool  onlyTriangles = false)
inline

Creates a planarization module based on triangle or diamond matching.

Parameters
onlyTrianglesIf true, only search for triangles. If false (default), search for diamonds first and then match triangles.

Definition at line 63 of file PlanarSubgraphTriangles.h.

Member Function Documentation

◆ clone()

template<typename TCost >
virtual PlanarSubgraphTriangles* ogdf::PlanarSubgraphTriangles< TCost >::clone ( ) const
inlineoverridevirtual

Returns a new instance of the planarization module with the same settings.

Implements ogdf::PlanarSubgraphModule< TCost >.

Reimplemented in ogdf::PlanarSubgraphCactus< TCost >.

Definition at line 66 of file PlanarSubgraphTriangles.h.

◆ doCall()

template<typename TCost >
virtual Module::ReturnType ogdf::PlanarSubgraphTriangles< TCost >::doCall ( const Graph G,
const List< edge > &  preferredEdges,
List< edge > &  delEdges,
const EdgeArray< TCost > *  pCost,
bool  preferredImplyPlanar = false 
)
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.

Parameters
Gis 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 71 of file PlanarSubgraphTriangles.h.

◆ findTriangle()

template<typename TCost >
void ogdf::PlanarSubgraphTriangles< TCost >::findTriangle ( GraphCopy copy,
edge  currentEdge,
const EdgeArray< TCost > *  pCost,
DisjointSets<> &  components,
NodeArray< int > &  set,
std::function< bool(node, edge, edge)>  callback 
)
inlineprivate

Finds all triangles from a given edge and calls a callback function on them.

Private implementation function. Takes an edge and attempts to find a node that is adjacent to the edge's incident nodes.

Parameters
copya copy of the graph to look in
currentEdgethe edge to start the search with
pCostfor every edge in copy, a weight that influences how likely an edge is chosen, with higher cost being more likely.
componentsa set of components in the graph. Triangles cannot have two nodes in the same component to keep planarity promises.
seta mapping of nodes to components
callbacka function that takes a node and two of its incident edges, creating a triangle with currentEdge. The calls to this function are roughly ordered by weight as defined by pCost. If the callback returns true, stop the search, otherwise a new triangle will be searched for.

Definition at line 231 of file PlanarSubgraphTriangles.h.

◆ searchEdge()

template<typename TCost >
edge ogdf::PlanarSubgraphTriangles< TCost >::searchEdge ( node  target,
node  source,
internal::GraphIterator< adjEntry connectionIterator 
)
inlineprivate

Finds an edge, starting at a given iterator.

Takes a node and its adjacency list iterator and, from the iterator's current position, tries to find an edge that leads to a target.

Parameters
targetthe node to connect to
sourcethe node to connect from
connectionIteratoran adjacency list iterator of source
Returns
edge between target and source if found, nullptr otherwise

Definition at line 204 of file PlanarSubgraphTriangles.h.

Member Data Documentation

◆ m_onlyTriangles

template<typename TCost >
bool ogdf::PlanarSubgraphTriangles< TCost >::m_onlyTriangles
private

Whether we want to only check for triangles.

Definition at line 193 of file PlanarSubgraphTriangles.h.


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