|
|||
|
|
|
|||
|
|
Starts with a chordless cycle of the graph and then inserts each original node that is adjacent to already inserted ones via the StarInserter. More...
#include <ogdf/planarity/PlanarizerChordlessCycle.h>
Inheritance diagram for ogdf::PlanarizerChordlessCycle:Public Member Functions | |
| PlanarizerChordlessCycle () | |
| Creates a PlanarizerChordlessCycle with default settings. | |
| PlanarizerChordlessCycle (const PlanarizerChordlessCycle &planarizer) | |
Creates a PlanarizerChordlessCycle with the same settings as planarizer. | |
| virtual CrossingMinimizationModule * | clone () const override |
| Returns a new PlanarizerChordlessCycle with the same option settings. | |
| PlanarizerChordlessCycle & | operator= (const PlanarizerChordlessCycle &planarizer) |
| Assignment operator, copies option settings only. | |
| Public Member Functions inherited from ogdf::CrossingMinimizationModule | |
| CrossingMinimizationModule () | |
| Initializes a crossing minimization module (default constructor). | |
| CrossingMinimizationModule (const CrossingMinimizationModule &cmm) | |
| Initializes an crossing minimization module (copy constructor). | |
| virtual | ~CrossingMinimizationModule () |
| Destructor. | |
| ReturnType | call (PlanRep &pr, int cc, int &crossingNumber, const EdgeArray< int > *pCostOrig=nullptr, const EdgeArray< bool > *pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr) |
| Computes a planarized representation of the input graph. | |
| ReturnType | operator() (PlanRep &pr, int cc, int &crossingNumber, const EdgeArray< int > *pCostOrig=nullptr, const EdgeArray< bool > *pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr) |
| Computes a planarized representation of the input graph. | |
| Public Member Functions inherited from ogdf::Module | |
| Module () | |
| Initializes a module. | |
| virtual | ~Module () |
| Public Member Functions inherited from ogdf::Timeouter | |
| Timeouter () | |
| timeout is turned of by default | |
| Timeouter (bool t) | |
| timeout is turned off (false) or on (true) (with 0 second) | |
| Timeouter (const Timeouter &t) | |
| Timeouter (double t) | |
| timeout is set to the given value (seconds) | |
| ~Timeouter () | |
| bool | isTimeLimit () const |
| returns whether any time limit is set or not | |
| Timeouter & | operator= (const Timeouter &t) |
| double | timeLimit () const |
| returns the current time limit for the call | |
| void | timeLimit (bool t) |
| shorthand to turn timelimit off or on (with 0 seconds) | |
| void | timeLimit (double t) |
| sets the time limit for the call (in seconds); <0 means no limit. | |
Protected Member Functions | |
| virtual ReturnType | doCall (PlanRep &pr, int cc, const EdgeArray< int > *pCostOrig, const EdgeArray< bool > *pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubGraphs, int &crossingNumber) override |
| Implements the algorithm call. | |
Private Member Functions | |
| void | addToGraphCopy (GraphCopy &graphCopy, GraphCopy ©Copy, DynamicDualGraph &dual, node vOrig, const EdgeArray< int > *pCostOrig, EdgeArray< int > *pCostCopy) |
Creates a copy of vOrig in graphCopy and optimally inserts a copy of this copy in the planarization copyCopy. | |
| bool | findChordlessCycle (const Graph &G, List< node > &cycle) |
| void | transferToPlanRep (PlanRep &pr, const GraphCopy &graphCopy, const GraphCopy ©Copy) |
Creates crossings in pr that resemble the crossings in copyCopy. | |
Private Attributes | |
| StarInserter | m_inserter |
| The StarInserter used to insert new nodes into the planarization. | |
Additional Inherited Members | |
| Public Types inherited from ogdf::Module | |
| enum class | ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , Error } |
| The return type of a module. More... | |
| Static Public Member Functions inherited from ogdf::Module | |
| static bool | isSolution (ReturnType ret) |
Returns true iff ret indicates that the module returned a feasible solution. | |
| Static Protected Member Functions inherited from ogdf::CrossingMinimizationModule | |
| static int | computeCrossingNumber (GraphCopy &graphCopy, const EdgeArray< int > *pCost, const EdgeArray< uint32_t > *pEdgeSubGraphs) |
Computes the (weighted) crossing number of the planarization graphCopy. | |
| Protected Attributes inherited from ogdf::Timeouter | |
| double | m_timeLimit |
| Time limit for module calls (< 0 means no limit). | |
Starts with a chordless cycle of the graph and then inserts each original node that is adjacent to already inserted ones via the StarInserter.
See:
K. Clancy, M. Haythorpe, A. Newcombe: An effective crossing minimisation heuristic based on star insertion. J. Graph Algorithms Appl. 23(2): 135-166 (2019)
Definition at line 52 of file PlanarizerChordlessCycle.h.
| ogdf::PlanarizerChordlessCycle::PlanarizerChordlessCycle | ( | ) |
Creates a PlanarizerChordlessCycle with default settings.
| ogdf::PlanarizerChordlessCycle::PlanarizerChordlessCycle | ( | const PlanarizerChordlessCycle & | planarizer | ) |
Creates a PlanarizerChordlessCycle with the same settings as planarizer.
|
private |
Creates a copy of vOrig in graphCopy and optimally inserts a copy of this copy in the planarization copyCopy.
| graphCopy | is the graph copy of the original graph. |
| copyCopy | is the graph copy/planarization of graphCopy. |
| dual | is the dual graph of copyCopy. |
| vOrig | is the node in the original graph for which a copy is created in graphCopy and copyCopy. |
| pCostOrig | are the edge costs in the original graph. |
| pCostCopy | are the edge costs in graphCopy (edge costs for the newly created edges are added). |
|
overridevirtual |
Returns a new PlanarizerChordlessCycle with the same option settings.
Implements ogdf::CrossingMinimizationModule.
|
overrideprotectedvirtual |
Implements the algorithm call.
pr must be simple. Implements ogdf::CrossingMinimizationModule.
|
private |
| G | graph in which a chordless cycle should be found. |
| cycle | is assigned a list of nodes in G which induce a chordless cycle. |
| PlanarizerChordlessCycle & ogdf::PlanarizerChordlessCycle::operator= | ( | const PlanarizerChordlessCycle & | planarizer | ) |
Assignment operator, copies option settings only.
|
private |
Creates crossings in pr that resemble the crossings in copyCopy.
| pr | is assigned the final planarization as it is contained in copyCopy in terms of crossings (but pr must be planarly embedded again afterwards). |
| graphCopy | is a copy of pr's original graph and the original of copyCopy. |
| copyCopy | is a planarization that contains the crossings that should be copied to pr. |
|
private |
The StarInserter used to insert new nodes into the planarization.
Definition at line 114 of file PlanarizerChordlessCycle.h.