|
|||
|
|
|
|||
|
|
Computes planar separators using the Dual of the graph. More...
#include <ogdf/graphalg/SeparatorDual.h>
Inheritance diagram for ogdf::SeparatorDual:Public Member Functions | |
| SeparatorDual (bool useTriangulatingBFS=false, unsigned int treeHeightIt=0) | |
| Constructor. | |
| virtual double | getMaxSeparatorSize (int n) const override |
| 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. | |
| virtual std::string | getSpecificName () const override |
| Returns the unique name of the core algorithm, to be combined with postprocessors later. | |
| Public Member Functions inherited from ogdf::SeparatorLiptonTarjan | |
| SeparatorLiptonTarjan (bool useTriangulatingBFS=false, unsigned int treeHeightIt=0) | |
| Constructor. | |
| 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. | |
| void | clearPostProcessors () |
| Deletes all appended postprocessors from this separator. | |
| std::string | getExitPoint () const |
| Returns the exitPoint, i.e. | |
| virtual std::string | getName () const |
| Returns the full name of this algorithm. | |
| virtual bool | separate (const Graph &G, List< node > &separator, List< node > &first, List< node > &second, bool checkPreconditions=true) final |
| Separates a planar graph. | |
| virtual bool | separate (const Graph &G, NodeArray< short > &assignments, bool checkPreconditions=true) final |
| Separates a planar graph. | |
| 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. | |
| virtual void | makeTree () override |
| Creates the BFS tree used by the algorithm. | |
| Protected Member Functions inherited from ogdf::SeparatorLiptonTarjan | |
| edge | chooseEdge () const |
| Chooses the initial edge for the very first cycle. | |
| void | fillLists (List< node > &separator, List< node > &first, List< node > &second) const |
| Fills the lists with the cycle / inside / outside once the cycle is ready. | |
| 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. | |
| node | getStartNode (const Graph &G) const |
| Selects the starting node for the BFS. | |
| bool | postProcess (const Graph &G, List< node > &separator, List< node > &first, List< node > &second) |
| Apply all postprocessors. | |
| virtual void | reset () |
| Reset everything to enable reuse of the module. | |
| 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. | |
| 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. | |
Protected Attributes | |
| unsigned int | treeHeightIterations |
| bool | useTriBFS |
| Protected Attributes inherited from ogdf::SeparatorLiptonTarjan | |
| std::shared_ptr< BFSTreeClassical > | tree |
| unsigned int | treeHeightIterations |
| bool | useTriBFS |
| Protected Attributes inherited from ogdf::PlanarSeparatorModule | |
| std::string | exitPoint |
| std::shared_ptr< GraphCopy > | graph |
| std::vector< Postprocessor * > | postProcessors |
| int | startNodeIndex = -1 |
Computes planar separators using the Dual of the graph.
Computes planar separators using the dual of the graph as presented in the textbook "The Design and Analysis of Algorithms" by D. Kozen, Springer, 1992.
Definition at line 51 of file SeparatorDual.h.
|
inline |
Constructor.
| useTriangulatingBFS | whether to use triangulating BFS for the second phase or not |
| treeHeightIt | how many iterations of tree height maximization to perform in the first phase |
Definition at line 59 of file SeparatorDual.h.
|
overrideprotectedvirtual |
Core of the specific separation algorithm - override this in inheriting classes.
| G | the graph to be separated |
| separator | the separator nodes |
| first | the first component |
| second | the second component |
Reimplemented from ogdf::SeparatorLiptonTarjan.
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.
| n | the number of nodes of the graph |
Reimplemented from ogdf::SeparatorLiptonTarjan.
Definition at line 74 of file SeparatorDual.h.
|
inlineoverridevirtual |
Returns the unique name of the core algorithm, to be combined with postprocessors later.
Override this in inheriting methods.
Reimplemented from ogdf::SeparatorLiptonTarjan.
Definition at line 62 of file SeparatorDual.h.
Creates the BFS tree used by the algorithm.
Reimplemented from ogdf::SeparatorLiptonTarjan.
Definition at line 83 of file SeparatorDual.h.
|
protected |
Definition at line 82 of file SeparatorDual.h.
