6 * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of the FastPlanarSubgraph.
12 * \author Hoi-Ming Wong
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_FUPS_SIMPLE_H
49 #define OGDF_FUPS_SIMPLE_H
52 #include <ogdf/module/FUPSModule.h>
58 class OGDF_EXPORT FUPSSimple
: public FUPSModule
{
61 //! Creates an instance of feasible subgraph algorithm.
62 FUPSSimple() : m_nRuns(0) { }
70 //! Sets the number of randomized runs to \a nRuns.
71 void runs (int nRuns
) {
75 //! Returns the current number of randomized runs.
81 //! return a adjEntry of node v which right face is f. Be Carefully! The adjEntry is not always unique.
82 adjEntry
getAdjEntry(const CombinatorialEmbedding
&Gamma
, node v
, face f
)
86 if (Gamma
.rightFace(adj
) == f
)
90 OGDF_ASSERT(Gamma
.rightFace(adj
) == f
);
98 * \brief Computes a feasible upward planar subgraph of the input graph.
100 * @param UPR represents the feasible upward planar subgraph after the call. \a UPR has to be initialzed as a
101 * UpwardPlanRep of the input connected graph G and is modified to obtain the upward planar subgraph.
102 * The subgraph is represented as an upward planar representation.
103 * @param delEdges is the deleted edges in order to obtain the subgraph. The edges are edges of the original graph G.
104 * \return the status of the result.
106 virtual Module::ReturnType
doCall(UpwardPlanRep
&UPR
,
107 List
<edge
> &delEdges
);
112 int m_nRuns
; //!< The number of runs for randomization.
114 void computeFUPS(UpwardPlanRep
&UPR
,
115 List
<edge
> &delEdges
);
117 //! Compute a (random) span tree of the input sT-Graph.
119 * @param GC The Copy of the input graph G.
120 * @param &delEdges The deleted edges (edges of G).
121 * @param random compute a random span tree
122 * @multisource true, if the original graph got multisources. In this case, the incident edges of
123 * the source are allways included in the span tree
125 void getSpanTree(GraphCopy
&GC
, List
<edge
> &delEdges
, bool random
);
128 * Function use by geSpannTree to compute the spannig tree.
130 void dfs_visit(const Graph
&G
, edge e
, NodeArray
<bool> &visited
, EdgeArray
<bool> &treeEdges
, bool random
);
132 // construct a merge graph with repsect to gamma and its test acyclicity
133 bool constructMergeGraph(GraphCopy
&M
, // copy of the original graph, muss be embedded
134 adjEntry adj_orig
, // the adjEntry of the original graph, which right face is the ext. Face and adj->theNode() is the source
135 const List
<edge
> &del_orig
); // deleted edges