Abstract description of all planar separator algorithms.
More...
#include <ogdf/graphalg/PlanarSeparatorModule.h>
|
| 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...
|
| |
Abstract description of all planar separator algorithms.
Definition at line 925 of file PlanarSeparatorModule.h.
◆ PlanarSeparatorModule()
| ogdf::PlanarSeparatorModule::PlanarSeparatorModule |
( |
| ) |
|
|
inline |
◆ ~PlanarSeparatorModule()
| virtual ogdf::PlanarSeparatorModule::~PlanarSeparatorModule |
( |
| ) |
|
|
inlinevirtual |
◆ addPostProcessor()
| void ogdf::PlanarSeparatorModule::addPostProcessor |
( |
Postprocessor & |
post | ) |
|
|
inline |
Adds a postprocessor to this separator, which will always be applied.
- Parameters
-
Definition at line 936 of file PlanarSeparatorModule.h.
◆ cleanup()
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
-
| G | the graph |
| separator | the separator |
| first | the first component |
| second | the second component |
- Returns
- whether the cleanup procedure was applied or not
Definition at line 1136 of file PlanarSeparatorModule.h.
◆ clearPostProcessors()
| void ogdf::PlanarSeparatorModule::clearPostProcessors |
( |
| ) |
|
|
inline |
◆ 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
-
| G | the graph |
| component | assigns a component to each node |
| compSizes | maps component number to its size |
- Returns
- the number of connected components
◆ doSeparate()
◆ 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 1033 of file PlanarSeparatorModule.h.
◆ getMaxSeparatorSize()
| virtual double ogdf::PlanarSeparatorModule::getMaxSeparatorSize |
( |
int |
n | ) |
const |
|
pure virtual |
◆ 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 1020 of file PlanarSeparatorModule.h.
◆ getSpecificName()
| virtual std::string ogdf::PlanarSeparatorModule::getSpecificName |
( |
| ) |
const |
|
protectedpure virtual |
◆ getStartNode()
| node ogdf::PlanarSeparatorModule::getStartNode |
( |
const Graph & |
G | ) |
const |
|
inlineprotected |
Selects the starting node for the BFS.
- Parameters
-
- Returns
- random node if no desired index was set, node with that index otherwise
Definition at line 1061 of file PlanarSeparatorModule.h.
◆ postProcess()
Apply all postprocessors.
- Parameters
-
| G | the graph to be separated |
| separator | the separator nodes |
| first | the first component |
| second | the second component |
- Returns
- true on success
Definition at line 1169 of file PlanarSeparatorModule.h.
◆ reset()
| virtual void ogdf::PlanarSeparatorModule::reset |
( |
| ) |
|
|
inlineprotectedvirtual |
◆ 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
-
| G | the graph to be separated |
| separator | the separator nodes |
| first | the first component |
| second | the second component |
| checkPreconditions | whether to ensure that the current embedding is planar and G is simple undirected |
- Returns
- true on success
Definition at line 960 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
-
| G | the graph to be separated |
| assignments | the NodeArray containing the assignments |
| checkPreconditions | whether to check if the current embedding is planar and G is simple undirected |
- Returns
- true on success
Definition at line 988 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
-
| G | the graph to be separated |
| separator | the separator nodes |
| first | the first component |
| second | the second component |
| skip | whether to skip the connectedness-step |
- Returns
- true if the graph could be separated already
◆ setStartIndex()
| void ogdf::PlanarSeparatorModule::setStartIndex |
( |
int |
index | ) |
|
|
inline |
◆ 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
-
| G | the graph to be separated |
| separator | the separator nodes |
| first | the first component |
| second | the second component |
| checkPreconditions | whether 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 1093 of file PlanarSeparatorModule.h.
◆ exitPoint
| std::string ogdf::PlanarSeparatorModule::exitPoint |
|
protected |
◆ graph
| std::shared_ptr<GraphCopy> ogdf::PlanarSeparatorModule::graph |
|
protected |
◆ postProcessors
| std::vector<Postprocessor*> ogdf::PlanarSeparatorModule::postProcessors |
|
protected |
◆ startNodeIndex
| int ogdf::PlanarSeparatorModule::startNodeIndex = -1 |
|
protected |
The documentation for this class was generated from the following file:
Inheritance diagram for ogdf::PlanarSeparatorModule:
