Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::SeparatorDualFC Class Reference

Computes planar separators by applying the Fundamental Cycle Lemma directly, without trying tree levels first. More...

#include <ogdf/graphalg/SeparatorDualFC.h>

+ Inheritance diagram for ogdf::SeparatorDualFC:

Public Member Functions

 SeparatorDualFC (bool useTriBFS=false)
 Constructor. More...
 
virtual double getMaxSeparatorSize (int n) const override
 Maximum separator size depends on diameter of graph, so returns -1. More...
 
- Public Member Functions inherited from ogdf::SeparatorLiptonTarjanFC
 SeparatorLiptonTarjanFC (bool useTriBFS=false)
 Constructor. More...
 
- Public Member Functions inherited from ogdf::PlanarSeparatorModule
 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 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

virtual bool doSeparate (const Graph &G, List< node > &separator, List< node > &first, List< node > &second) override
 Core of the specific separation algorithm - override this in inheriting classes. More...
 
virtual bool findCycle (List< node > &separator, List< node > &first, List< node > &second) override
 Finds a suitable cycle by performing a DFS over the faces of the dual of the graph. More...
 
virtual std::string getSpecificName () const override
 Returns the unique name of the core algorithm, to be combined with postprocessors later. More...
 
void makeTree ()
 Builds the BFS tree. More...
 
- Protected Member Functions inherited from ogdf::SeparatorLiptonTarjanFC
edge chooseEdge () const
 Randomly selects the initial edge for the first cycle. More...
 
- Protected Member Functions inherited from ogdf::PlanarSeparatorModule
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...
 
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::shared_ptr< ArrayBFSTreetree
 
bool useTriangulatingBFS
 
- Protected Attributes inherited from ogdf::SeparatorLiptonTarjanFC
std::shared_ptr< ArrayBFSTreetree
 
bool useTriangulatingBFS
 
- Protected Attributes inherited from ogdf::PlanarSeparatorModule
std::string exitPoint
 
std::shared_ptr< GraphCopygraph
 
std::vector< Postprocessor * > postProcessors
 
int startNodeIndex = -1
 

Detailed Description

Computes planar separators by applying the Fundamental Cycle Lemma directly, without trying tree levels first.

Definition at line 46 of file SeparatorDualFC.h.

Constructor & Destructor Documentation

◆ SeparatorDualFC()

ogdf::SeparatorDualFC::SeparatorDualFC ( bool  useTriBFS = false)
inline

Constructor.

Parameters
useTriBFSwhether to use triangulating BFS or not

Definition at line 53 of file SeparatorDualFC.h.

Member Function Documentation

◆ doSeparate()

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

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

Reimplemented from ogdf::SeparatorLiptonTarjanFC.

◆ findCycle()

virtual bool ogdf::SeparatorDualFC::findCycle ( List< node > &  separator,
List< node > &  first,
List< node > &  second 
)
overrideprotectedvirtual

Finds a suitable cycle by performing a DFS over the faces of the dual of the graph.

Parameters
separatorthe separator nodes
firstthe first component
secondthe second component
Returns
true on success

Reimplemented from ogdf::SeparatorLiptonTarjanFC.

◆ getMaxSeparatorSize()

virtual double ogdf::SeparatorDualFC::getMaxSeparatorSize ( int  n) const
inlineoverridevirtual

Maximum separator size depends on diameter of graph, so returns -1.

Reimplemented from ogdf::SeparatorLiptonTarjanFC.

Definition at line 56 of file SeparatorDualFC.h.

◆ getSpecificName()

virtual std::string ogdf::SeparatorDualFC::getSpecificName ( ) const
inlineoverrideprotectedvirtual

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

Reimplemented from ogdf::SeparatorLiptonTarjanFC.

Definition at line 80 of file SeparatorDualFC.h.

◆ makeTree()

void ogdf::SeparatorDualFC::makeTree ( )
protected

Builds the BFS tree.

Member Data Documentation

◆ tree

std::shared_ptr<ArrayBFSTree> ogdf::SeparatorDualFC::tree
protected

Definition at line 60 of file SeparatorDualFC.h.

◆ useTriangulatingBFS

bool ogdf::SeparatorDualFC::useTriangulatingBFS
protected

Definition at line 59 of file SeparatorDualFC.h.


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