Computes planar separators by applying the Fundamental Cycle Lemma directly, without trying tree levels first.
More...
#include <ogdf/graphalg/SeparatorDualFC.h>
|
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...
|
|
edge | chooseEdge () const |
| Randomly selects the initial edge for the first cycle. More...
|
|
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...
|
|
Computes planar separators by applying the Fundamental Cycle Lemma directly, without trying tree levels first.
Definition at line 46 of file SeparatorDualFC.h.
◆ SeparatorDualFC()
ogdf::SeparatorDualFC::SeparatorDualFC |
( |
bool |
useTriBFS = false | ) |
|
|
inline |
Constructor.
- Parameters
-
useTriBFS | whether to use triangulating BFS or not |
Definition at line 53 of file SeparatorDualFC.h.
◆ doSeparate()
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
-
G | the graph to be separated |
separator | the separator nodes |
first | the first component |
second | the second component |
- Returns
- true on success
Reimplemented from ogdf::SeparatorLiptonTarjanFC.
◆ findCycle()
Finds a suitable cycle by performing a DFS over the faces of the dual of the graph.
- Parameters
-
separator | the separator nodes |
first | the first component |
second | the second component |
- Returns
- true on success
Reimplemented from ogdf::SeparatorLiptonTarjanFC.
◆ getMaxSeparatorSize()
virtual double ogdf::SeparatorDualFC::getMaxSeparatorSize |
( |
int |
n | ) |
const |
|
inlineoverridevirtual |
◆ 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 |
◆ tree
◆ useTriangulatingBFS
bool ogdf::SeparatorDualFC::useTriangulatingBFS |
|
protected |
The documentation for this class was generated from the following file: