Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::PlanarSeparatorModule Class Referenceabstract

Abstract description of all planar separator algorithms. More...

#include <ogdf/graphalg/PlanarSeparatorModule.h>

+ Inheritance diagram for ogdf::PlanarSeparatorModule:

Public Member Functions

 PlanarSeparatorModule ()
 
virtual ~PlanarSeparatorModule ()
 
void addPostProcessor (Postprocessor &post)
 Adds a postprocessor to this separator, which will always be applied. More...
 
void clearPostProcessors ()
 Deletes all appended postprocessors from this separator. More...
 
std::string getExitPoint () const
 Returns the exitPoint, i.e. More...
 
virtual double getMaxSeparatorSize (int n) const =0
 Provides the maximal separator size that this algorithm guarantees as a function of the number of nodes of the graph, or a negative value if the guarantee cannot be expressed through such a function. More...
 
virtual std::string getName () const
 Returns the full name of this algorithm. More...
 
virtual bool separate (const Graph &G, List< node > &separator, List< node > &first, List< node > &second, bool checkPreconditions=true) final
 Separates a planar graph. More...
 
virtual bool separate (const Graph &G, NodeArray< short > &assignments, bool checkPreconditions=true) final
 Separates a planar graph. More...
 
void setStartIndex (int index)
 

Protected Member Functions

bool cleanup (const Graph &G, List< node > &separator, List< node > &first, List< node > &second)
 Performs built-in post-processing: For small instances, it can happen that all nodes are assigned to the separator, while both components are empty, which can be fixed by moving half of the nodes to the first list. More...
 
virtual bool doSeparate (const Graph &G, List< node > &separator, List< node > &first, List< node > &second)=0
 Core of the specific separation algorithm - override this in inheriting classes. More...
 
virtual std::string getSpecificName () const =0
 Returns the unique name of the core algorithm, to be combined with postprocessors later. More...
 
node getStartNode (const Graph &G) const
 Selects the starting node for the BFS. More...
 
bool postProcess (const Graph &G, List< node > &separator, List< node > &first, List< node > &second)
 Apply all postprocessors. More...
 
virtual void reset ()
 Reset everything to enable reuse of the module. More...
 
bool separateComponents (GraphCopy &G, List< node > &separator, List< node > &first, List< node > &second, bool skip=false) const
 Checks if the graph consists of multiple connected components, takes necessary steps for fixing that, returns true if this already solved the graph, false if the core algorithm still needs to run. More...
 
bool setup (const Graph &G, List< node > &separator, List< node > &first, List< node > &second, bool checkPreconditions=true)
 Performs some initial setup to ensure that all preconditions hold and takes trivial steps to separate the graph. More...
 

Protected Attributes

std::string exitPoint
 
std::shared_ptr< GraphCopygraph
 
std::vector< Postprocessor * > postProcessors
 
int startNodeIndex = -1
 

Private Member Functions

int connectedComponents (const Graph &G, NodeArray< int > &component, std::map< int, int > &compSizes) const
 Finds all connected components within the graph. More...
 

Detailed Description

Abstract description of all planar separator algorithms.

Definition at line 916 of file PlanarSeparatorModule.h.

Constructor & Destructor Documentation

◆ PlanarSeparatorModule()

ogdf::PlanarSeparatorModule::PlanarSeparatorModule ( )
inline

Definition at line 918 of file PlanarSeparatorModule.h.

◆ ~PlanarSeparatorModule()

virtual ogdf::PlanarSeparatorModule::~PlanarSeparatorModule ( )
inlinevirtual

Definition at line 920 of file PlanarSeparatorModule.h.

Member Function Documentation

◆ addPostProcessor()

void ogdf::PlanarSeparatorModule::addPostProcessor ( Postprocessor post)
inline

Adds a postprocessor to this separator, which will always be applied.

Parameters
postthe postprocessor

Definition at line 927 of file PlanarSeparatorModule.h.

◆ cleanup()

bool ogdf::PlanarSeparatorModule::cleanup ( const Graph G,
List< node > &  separator,
List< node > &  first,
List< node > &  second 
)
inlineprotected

Performs built-in post-processing: For small instances, it can happen that all nodes are assigned to the separator, while both components are empty, which can be fixed by moving half of the nodes to the first list.

Parameters
Gthe graph
separatorthe separator
firstthe first component
secondthe second component
Returns
whether the cleanup procedure was applied or not

Definition at line 1127 of file PlanarSeparatorModule.h.

◆ clearPostProcessors()

void ogdf::PlanarSeparatorModule::clearPostProcessors ( )
inline

Deletes all appended postprocessors from this separator.

Definition at line 932 of file PlanarSeparatorModule.h.

◆ connectedComponents()

int ogdf::PlanarSeparatorModule::connectedComponents ( const Graph G,
NodeArray< int > &  component,
std::map< int, int > &  compSizes 
) const
private

Finds all connected components within the graph.

Essentially a modified version of ogdf::connectedComponents that also fills a map to maintain component sizes.

Parameters
Gthe graph
componentassigns a component to each node
compSizesmaps component number to its size
Returns
the number of connected components

◆ doSeparate()

virtual bool ogdf::PlanarSeparatorModule::doSeparate ( const Graph G,
List< node > &  separator,
List< node > &  first,
List< node > &  second 
)
protectedpure virtual

Core of the specific separation algorithm - override this in inheriting classes.

Precondition
G is planar, simple-undirected, connected and represents a Combinatorial Embedding = is planarly embedded already.
Parameters
Gthe graph to be separated
separatorthe separator nodes
firstthe first component
secondthe second component
Returns
true on success

Implemented in ogdf::SeparatorHarPeled, ogdf::SeparatorLiptonTarjanFC, ogdf::SeparatorDual, ogdf::SeparatorDualFC, and ogdf::SeparatorLiptonTarjan.

◆ getExitPoint()

std::string ogdf::PlanarSeparatorModule::getExitPoint ( ) const
inline

Returns the exitPoint, i.e.

a string describing the point at which the algorithm returned.

Returns
the exitPoint

Definition at line 1024 of file PlanarSeparatorModule.h.

◆ getMaxSeparatorSize()

virtual double ogdf::PlanarSeparatorModule::getMaxSeparatorSize ( int  n) const
pure virtual

Provides the maximal separator size that this algorithm guarantees as a function of the number of nodes of the graph, or a negative value if the guarantee cannot be expressed through such a function.

See e.g. SeparatorHarPeled or SeparatorDualFC for examples.

Parameters
nthe number of nodes of the graph
Returns
the maximal separator size

Implemented in ogdf::SeparatorHarPeled, ogdf::SeparatorLiptonTarjanFC, ogdf::SeparatorDual, ogdf::SeparatorLiptonTarjan, and ogdf::SeparatorDualFC.

◆ getName()

virtual std::string ogdf::PlanarSeparatorModule::getName ( ) const
inlinevirtual

Returns the full name of this algorithm.

Useful when running experiments. The name consists of the specific name of the algorithm and the names of the postprocessors.

Returns
the full name

Definition at line 1011 of file PlanarSeparatorModule.h.

◆ getSpecificName()

virtual std::string ogdf::PlanarSeparatorModule::getSpecificName ( ) const
protectedpure virtual

Returns the unique name of the core algorithm, to be combined with postprocessors later.

Override this in inheriting methods.

Returns
the specific name as a string

Implemented in ogdf::SeparatorLiptonTarjanFC, ogdf::SeparatorHarPeled, ogdf::SeparatorDualFC, ogdf::SeparatorLiptonTarjan, and ogdf::SeparatorDual.

◆ getStartNode()

node ogdf::PlanarSeparatorModule::getStartNode ( const Graph G) const
inlineprotected

Selects the starting node for the BFS.

Parameters
Gthe graph to be solved
Returns
random node if no desired index was set, node with that index otherwise

Definition at line 1052 of file PlanarSeparatorModule.h.

◆ postProcess()

bool ogdf::PlanarSeparatorModule::postProcess ( const Graph G,
List< node > &  separator,
List< node > &  first,
List< node > &  second 
)
inlineprotected

Apply all postprocessors.

Parameters
Gthe graph to be separated
separatorthe separator nodes
firstthe first component
secondthe second component
Returns
true on success

Definition at line 1160 of file PlanarSeparatorModule.h.

◆ reset()

virtual void ogdf::PlanarSeparatorModule::reset ( )
inlineprotectedvirtual

Reset everything to enable reuse of the module.

Reimplemented in ogdf::SeparatorHarPeled.

Definition at line 1178 of file PlanarSeparatorModule.h.

◆ separate() [1/2]

virtual bool ogdf::PlanarSeparatorModule::separate ( const Graph G,
List< node > &  separator,
List< node > &  first,
List< node > &  second,
bool  checkPreconditions = true 
)
inlinefinalvirtual

Separates a planar graph.

This method takes care of multiple components, makes sure that all preconditions are fulfilled and applies postprocessing, both general postprocessing (only useful for small graphs) and via the added postprocessors.

Precondition
The input graph is planar, simple and undirected. If you know that all conditions hold and the graph is already planarly embedded, you can set checkPreconditions = false for a small speedup.
Parameters
Gthe graph to be separated
separatorthe separator nodes
firstthe first component
secondthe second component
checkPreconditionswhether to ensure that the current embedding is planar and G is simple undirected
Returns
true on success

Definition at line 951 of file PlanarSeparatorModule.h.

◆ separate() [2/2]

virtual bool ogdf::PlanarSeparatorModule::separate ( const Graph G,
NodeArray< short > &  assignments,
bool  checkPreconditions = true 
)
inlinefinalvirtual

Separates a planar graph.

Represents a solution as a NodeArray that assigns the component to each node. 0 = separator node, 1 = first component, 2 = second component

Parameters
Gthe graph to be separated
assignmentsthe NodeArray containing the assignments
checkPreconditionswhether to check if the current embedding is planar and G is simple undirected
Returns
true on success

Definition at line 979 of file PlanarSeparatorModule.h.

◆ separateComponents()

bool ogdf::PlanarSeparatorModule::separateComponents ( GraphCopy G,
List< node > &  separator,
List< node > &  first,
List< node > &  second,
bool  skip = false 
) const
protected

Checks if the graph consists of multiple connected components, takes necessary steps for fixing that, returns true if this already solved the graph, false if the core algorithm still needs to run.

Parameters
Gthe graph to be separated
separatorthe separator nodes
firstthe first component
secondthe second component
skipwhether to skip the connectedness-step
Returns
true if the graph could be separated already

◆ setStartIndex()

void ogdf::PlanarSeparatorModule::setStartIndex ( int  index)
inline

Definition at line 934 of file PlanarSeparatorModule.h.

◆ setup()

bool ogdf::PlanarSeparatorModule::setup ( const Graph G,
List< node > &  separator,
List< node > &  first,
List< node > &  second,
bool  checkPreconditions = true 
)
inlineprotected

Performs some initial setup to ensure that all preconditions hold and takes trivial steps to separate the graph.

Asserts that the graph is planar, simple and undirected.

Parameters
Gthe graph to be separated
separatorthe separator nodes
firstthe first component
secondthe second component
checkPreconditionswhether to check if the graph represents a comb-embedding and is simple and undirected
Returns
whether the graph could already be solved by trivial operations (i.e. if true, we are done)

Definition at line 1084 of file PlanarSeparatorModule.h.

Member Data Documentation

◆ exitPoint

std::string ogdf::PlanarSeparatorModule::exitPoint
protected

Definition at line 1044 of file PlanarSeparatorModule.h.

◆ graph

std::shared_ptr<GraphCopy> ogdf::PlanarSeparatorModule::graph
protected

Definition at line 1039 of file PlanarSeparatorModule.h.

◆ postProcessors

std::vector<Postprocessor*> ogdf::PlanarSeparatorModule::postProcessors
protected

Definition at line 1037 of file PlanarSeparatorModule.h.

◆ startNodeIndex

int ogdf::PlanarSeparatorModule::startNodeIndex = -1
protected

Definition at line 1041 of file PlanarSeparatorModule.h.


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