6 * $Date: 2012-07-07 23:10:08 +0200 (Sa, 07. Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of the FastPlanarSubgraph.
12 * \author Sebastian Leipert
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
48 #ifndef OGDF_FAST_PLANAR_SUBGRAPH_H
49 #define OGDF_FAST_PLANAR_SUBGRAPH_H
53 #include <ogdf/module/PlanarSubgraphModule.h>
59 * \brief Computation of a planar subgraph using PQ-trees.
61 * Literature: Jayakumar, Thulasiraman, Swamy 1989
63 * <h3>Optional Parameters</h3>
67 * <th>Option</th><th>Type</th><th>Default</th><th>Description</th>
69 * <td><i>runs</i></td><td>int</td><td>0</td>
70 * <td>the number of randomized runs performed by the algorithm; the best
71 * solution is picked among all the runs. If runs is 0, one
72 * deterministic run is performed.</td>
76 * Observe that this algorithm by theory does not compute a maximal
77 * planar subgraph. It is however the fastest known good heuristic.
79 class OGDF_EXPORT FastPlanarSubgraph
: public PlanarSubgraphModule
{
82 //! Creates an instance of the fast planar subgraph algorithm.
83 FastPlanarSubgraph() : PlanarSubgraphModule() {
88 ~FastPlanarSubgraph() { }
93 //! Sets the number of randomized runs to \a nRuns.
94 void runs (int nRuns
) {
98 //! Returns the current number of randomized runs.
105 //! Returns true, if G is planar, false otherwise.
107 * \todo Add timeout support (limit number of runs when timeout is reached).
109 ReturnType
doCall(const Graph
&G
,
110 const List
<edge
> &preferedEdges
,
111 List
<edge
> &delEdges
,
112 const EdgeArray
<int> *pCost
,
113 bool preferedImplyPlanar
);
117 int m_nRuns
; //!< The number of runs for randomization.
120 //! Computes the list of edges to be deleted in \a G.
121 /** Also performs randomization of the planarization algorithm.
123 void computeDelEdges(const Graph
&G
,
124 const EdgeArray
<int> *pCost
,
125 const EdgeArray
<edge
> *backTableEdges
,
126 List
<edge
> &delEdges
);
128 //! Performs a planarization on a biconnected component pf \a G.
129 /** The numbering contains an st-numbering of the component.
133 NodeArray
<int> &numbering
,
134 List
<edge
> &delEdges
);