|
|||
|
|
|
|||
|
|
Maximum planar subgraph approximation algorithms by Chalermsook/Schmid and Calinescu et al. More...
#include <ogdf/planarity/PlanarSubgraphTriangles.h>
Inheritance diagram for ogdf::PlanarSubgraphTriangles< TCost >:Public Member Functions | |
| PlanarSubgraphTriangles (bool onlyTriangles=false) | |
| Creates a planarization module based on triangle or diamond matching. More... | |
| virtual PlanarSubgraphTriangles * | clone () const override |
| Returns a new instance of the planarization module with the same settings. More... | |
| Public Member Functions inherited from ogdf::PlanarSubgraphModule< TCost > | |
| PlanarSubgraphModule () | |
| Initializes a planar subgraph module (default constructor). More... | |
| ReturnType | call (const Graph &G, const EdgeArray< TCost > &cost, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false) |
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More... | |
| ReturnType | call (const Graph &G, const EdgeArray< TCost > &cost, List< edge > &delEdges) |
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More... | |
| ReturnType | call (const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false) |
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More... | |
| ReturnType | call (const Graph &G, List< edge > &delEdges) |
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More... | |
| ReturnType | callAndDelete (GraphCopy &GC, const List< edge > &preferredEdges, List< edge > &delOrigEdges, bool preferredImplyPlanar=false) |
Makes GC planar by deleting edges. More... | |
| ReturnType | callAndDelete (GraphCopy &GC, List< edge > &delOrigEdges) |
Makes G planar by deleting edges. More... | |
| unsigned int | maxThreads () const |
| Returns the maximal number of used threads. More... | |
| void | maxThreads (unsigned int n) |
Sets the maximal number of used threads to n. More... | |
| ReturnType | operator() (const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, bool preferredImplyPlanar=false) |
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More... | |
| ReturnType | operator() (const Graph &G, List< edge > &delEdges) |
Returns the set of edges delEdges which have to be deleted to obtain the planar subgraph. More... | |
| Public Member Functions inherited from ogdf::Module | |
| Module () | |
| Initializes a module. More... | |
| virtual | ~Module () |
| Public Member Functions inherited from ogdf::Timeouter | |
| Timeouter () | |
| timeout is turned of by default More... | |
| Timeouter (bool t) | |
| timeout is turned off (false) or on (true) (with 0 second) More... | |
| Timeouter (const Timeouter &t) | |
| Timeouter (double t) | |
| timeout is set to the given value (seconds) More... | |
| ~Timeouter () | |
| bool | isTimeLimit () const |
| returns whether any time limit is set or not More... | |
| Timeouter & | operator= (const Timeouter &t) |
| double | timeLimit () const |
| returns the current time limit for the call More... | |
| void | timeLimit (bool t) |
| shorthand to turn timelimit off or on (with 0 seconds) More... | |
| void | timeLimit (double t) |
| sets the time limit for the call (in seconds); <0 means no limit. More... | |
Protected Member Functions | |
| virtual Module::ReturnType | doCall (const Graph &graph, const List< edge > &, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferredImplyPlanar=false) override |
Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph. More... | |
Private Member Functions | |
| void | findTriangle (GraphCopy ©, edge currentEdge, const EdgeArray< TCost > *pCost, DisjointSets<> &components, NodeArray< int > &set, std::function< bool(node, edge, edge)> callback) |
| Finds all triangles from a given edge and calls a callback function on them. More... | |
| edge | searchEdge (node target, node source, internal::GraphIterator< adjEntry > connectionIterator) |
| Finds an edge, starting at a given iterator. More... | |
Private Attributes | |
| bool | m_onlyTriangles |
| Whether we want to only check for triangles. More... | |
Additional Inherited Members | |
| Public Types inherited from ogdf::Module | |
| enum | ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::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. More... | |
| Protected Attributes inherited from ogdf::Timeouter | |
| double | m_timeLimit |
| Time limit for module calls (< 0 means no limit). More... | |
Maximum planar subgraph approximation algorithms by Chalermsook/Schmid and Calinescu et al.
This planarity module supports two algorithms.
The default selection is Chalermsook and Schmid.
Setting preferred edges is not supported. Weighted edges are heuristically respected but there is no approximation guarantee in the weighted case.
Definition at line 63 of file PlanarSubgraphTriangles.h.
|
inline |
Creates a planarization module based on triangle or diamond matching.
| onlyTriangles | If true, only search for triangles. If false (default), search for diamonds first and then match triangles. |
Definition at line 70 of file PlanarSubgraphTriangles.h.
|
inlineoverridevirtual |
Returns a new instance of the planarization module with the same settings.
Implements ogdf::PlanarSubgraphModule< TCost >.
Reimplemented in ogdf::PlanarSubgraphCactus< TCost >.
Definition at line 73 of file PlanarSubgraphTriangles.h.
|
inlineoverrideprotectedvirtual |
Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph.
This is the actual algorithm call and needs to be implemented by derived classes.
| G | is the input graph. |
| preferredEdges | are edges that should be contained in the planar subgraph. |
| delEdges | is the set of edges that need to be deleted to obtain the planar subgraph. |
| pCost | is apointer to an edge array containing the edge costs; this pointer can be 0 if no costs are given (all edges have cost 1). |
| preferredImplyPlanar | indicates that the edges preferredEdges induce a planar graph. |
Implements ogdf::PlanarSubgraphModule< TCost >.
Definition at line 78 of file PlanarSubgraphTriangles.h.
|
inlineprivate |
Finds all triangles from a given edge and calls a callback function on them.
Private implementation function. Takes an edge and attempts to find a node that is adjacent to the edge's incident nodes.
| copy | a copy of the graph to look in |
| currentEdge | the edge to start the search with |
| pCost | for every edge in copy, a weight that influences how likely an edge is chosen, with higher cost being more likely. |
| components | a set of components in the graph. Triangles cannot have two nodes in the same component to keep planarity promises. |
| set | a mapping of nodes to components |
| callback | a function that takes a node and two of its incident edges, creating a triangle with currentEdge. The calls to this function are roughly ordered by weight as defined by pCost. If the callback returns true, stop the search, otherwise a new triangle will be searched for. |
Definition at line 243 of file PlanarSubgraphTriangles.h.
|
inlineprivate |
Finds an edge, starting at a given iterator.
Takes a node and its adjacency list iterator and, from the iterator's current position, tries to find an edge that leads to a target.
| target | the node to connect to |
| source | the node to connect from |
| connectionIterator | an adjacency list iterator of source |
target and source if found, nullptr otherwise Definition at line 216 of file PlanarSubgraphTriangles.h.
|
private |
Whether we want to only check for triangles.
Definition at line 205 of file PlanarSubgraphTriangles.h.