55template<
typename TCost>
76 if (G.numberOfEdges() < 9) {
102 for (
edge e : G.edges) {
103 if (!e->isSelfLoop()) {
104 blockEdges[componentID[e]].pushFront(e);
111 for (i = 0; i < bcCount; i++) {
112 for (
edge e : blockEdges[i]) {
113 if (!mark[e->source()]) {
114 blockNodes[i].pushBack(e->source());
115 mark[e->source()] =
true;
117 if (!mark[e->target()]) {
118 blockNodes[i].pushBack(e->target());
119 mark[e->target()] =
true;
122 for (
node v : blockNodes[i]) {
133 for (i = 0; i < bcCount; i++) {
136 for (
node v : blockNodes[i]) {
143 for (
edge e : blockEdges[i]) {
144 edge f = C.
newEdge(tableNodes[e->source()], tableNodes[e->target()]);
146 if (pCost !=
nullptr) {
147 cost[tableEdges[e]] = (*pCost)[e];
156 for (
edge e : blockEdges[i]) {
157 backTableEdges[tableEdges[e]] = e;
164 mr = mc.
call(CG, pCost ==
nullptr ?
nullptr : &cost, delEdgesOfBC);
173 while (!delEdgesOfBC.
empty()) {
185 template<
typename U = TCost>
188 if (pCost ==
nullptr) {
192 for (
auto it = pCost->begin(); it != pCost->end(); ++it) {
193 dCost[it.key()] = it.value();
202 return mc.
call(CG, pCost, delEdges);
Declaration and implementation of Array class and Array algorithms.
Derived class of GraphObserver providing additional functionality to handle clustered graphs.
Includes declaration of graph class.
Decralation of GraphElement and GraphList classes.
Declaration of doubly linked lists and iterators.
Declaration of an exact c-planar subgraph algorithm, i.e., a maximum c-planar subgraph is computed us...
Declares base class for all module types.
Declaration of interface for planar subgraph algorithms.
Declaration of singly linked lists and iterators.
Basic declarations, included by all source files.
The parameterized class Array implements dynamic arrays of type E.
ReturnType call(const ClusterGraph &G, List< edge > &delEdges)
Computes set of edges delEdges, which have to be deleted in order to get a c-planar subgraph.
Representation of clustered graphs.
Class for the representation of edges.
Data type for general directed graphs (adjacency list representation).
node newNode(int index=-1)
Creates a new node and returns it.
edge newEdge(node v, node w, int index=-1)
Creates a new edge (v,w) and returns it.
Doubly linked lists (maintaining the length of the list).
void clear()
Removes all elements from the list.
iterator pushBack(const E &x)
Adds element x at the end of the list.
E popFrontRet()
Removes the first element from the list and returns it.
bool empty() const
Returns true iff the list is empty.
Exact computation of a maximum c-planar subgraph.
Exact computation of a maximum planar subgraph.
virtual MaximumPlanarSubgraph * clone() const override
Returns a new instance of the planar subgraph module with the same option settings.
virtual Module::ReturnType doCall(const Graph &G, const List< edge > &preferredEdges, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferredImplyPlanar) override
Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph.
Module::ReturnType callWithDouble(MaximumCPlanarSubgraph &mc, const Graph &G, const EdgeArray< U > *pCost, List< edge > &delEdges)
virtual ~MaximumPlanarSubgraph()
Module::ReturnType callWithDouble(MaximumCPlanarSubgraph &mc, const Graph &G, const EdgeArray< double > *pCost, List< edge > &delEdges)
ReturnType
The return type of a module.
@ Optimal
The solution is optimal.
Class for the representation of nodes.
Interface for planar subgraph algorithms.
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.
RegisteredArray for nodes, edges and adjEntries of a graph.
Declaration of extended graph algorithms.
int biconnectedComponents(const Graph &G, EdgeArray< int > &component, int &nonEmptyComponents)
Computes the biconnected components of G.
bool isPlanar(const Graph &G)
Returns true, if G is planar, false otherwise.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
The namespace for all OGDF objects.
Declaration of simple graph algorithms.