1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
/*
* $Revision: 2523 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
***************************************************************/
/** \file
* \brief Declaration of interface for planar subgraph algorithms.
*
* \author Carsten Gutwenger
*
* \par License:
* This file is part of the Open Graph Drawing Framework (OGDF).
*
* \par
* Copyright (C)<br>
* See README.txt in the root directory of the OGDF installation for details.
*
* \par
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* Version 2 or 3 as published by the Free Software Foundation;
* see the file LICENSE.txt included in the packaging of this file
* for details.
*
* \par
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* \par
* You should have received a copy of the GNU General Public
* License along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
* \see http://www.gnu.org/copyleft/gpl.html
***************************************************************/
#ifdef _MSC_VER
#pragma once
#endif
#ifndef OGDF_PLANAR_SUBGRAPH_MODULE_H
#define OGDF_PLANAR_SUBGRAPH_MODULE_H
#include <ogdf/planarity/PlanRepUML.h>
#include <ogdf/basic/Module.h>
#include <ogdf/basic/Logger.h>
#include <ogdf/basic/Timeouter.h>
namespace ogdf {
/**
* \brief Interface for planar subgraph algorithms.
*
* \see PlanarizationLayout, PlanarizationGridLayout
*/
class OGDF_EXPORT PlanarSubgraphModule : public Module, public Timeouter {
public:
//! Initializes a planar subgraph module.
PlanarSubgraphModule() { }
// destruction
virtual ~PlanarSubgraphModule() { }
/**
* \brief Returns the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
* @param G is the input graph.
* @param preferedEdges are edges that should be contained in the planar subgraph.
* @param delEdges is the set of edges that need to be deleted to obtain the planar subgraph.
* @param preferedImplyPlanar indicates that the edges \a preferedEdges induce a planar graph.
*/
ReturnType call(const Graph &G,
const List<edge> &preferedEdges,
List<edge> &delEdges,
bool preferedImplyPlanar = false)
{
return doCall(G,preferedEdges,delEdges,0,preferedImplyPlanar);
}
/**
* \brief Returns the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
* @param G is the input graph.
* @param cost are the costs of edges.
* @param delEdges is the set of edges that need to be deleted to obtain the planar subgraph.
*/
ReturnType call(const Graph &G, const EdgeArray<int> &cost, List<edge> &delEdges) {
List<edge> preferedEdges;
return doCall(G,preferedEdges,delEdges, &cost);
}
/**
* \brief Returns the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
* @param G is the input graph.
* @param delEdges is the set of edges that need to be deleted to obtain the planar subgraph.
*/
ReturnType call(const Graph &G, List<edge> &delEdges) {
List<edge> preferedEdges;
return doCall(G,preferedEdges,delEdges);
}
//! Returns the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
ReturnType operator()(const Graph &G,
const List<edge> &preferedEdges,
List<edge> &delEdges,
bool preferedImplyPlanar = false)
{
return call(G,preferedEdges,delEdges,preferedImplyPlanar);
}
//! Returns the set of edges \a delEdges which have to be deleted to obtain the planar subgraph.
ReturnType operator()(const Graph &G, List<edge> &delEdges) {
return call(G,delEdges);
}
/**
* \brief Makes \a G planar by deleting edges.
* @param GC is a copy of the input graph.
* @param preferedEdges are edges in \a GC that should be contained in the planar subgraph.
* @param delOrigEdges is the set of original edges whose copy has been deleted in \a GC.
* @param preferedImplyPlanar indicates that the edges \a preferedEdges induce a planar graph.
*/
ReturnType callAndDelete(GraphCopy &GC,
const List<edge> &preferedEdges,
List<edge> &delOrigEdges,
bool preferedImplyPlanar = false);
/**
* \brief Makes \a G planar by deleting edges.
* @param GC is a copy of the input graph.
* @param delOrigEdges is the set of original edges whose copy has been deleted in \a GC.
*/
ReturnType callAndDelete(GraphCopy &GC, List<edge> &delOrigEdges) {
List<edge> preferedEdges;
return callAndDelete(GC,preferedEdges,delOrigEdges);
}
protected:
// computes set of edges delEdges, which have to be deleted
// in order to get a planar subgraph; edges in preferedEdges
// should be contained in planar subgraph
// must be implemented by derived classes!
/**
* \brief Computes the set of edges \a 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.
* @param G is the input graph.
* @param preferedEdges are edges that should be contained in the planar subgraph.
* @param delEdges is the set of edges that need to be deleted to obtain the planar subgraph.
* @param 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).
* @param preferedImplyPlanar indicates that the edges \a preferedEdges induce a planar graph.
*/
virtual ReturnType doCall(const Graph &G,
const List<edge> &preferedEdges,
List<edge> &delEdges,
const EdgeArray<int> *pCost = 0,
bool preferedImplyPlanar = false) = 0;
OGDF_MALLOC_NEW_DELETE
};
} // end namespace ogdf
#endif
|
