6 * $Date: 2012-07-07 23:10:08 +0200 (Sa, 07. Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of class FeasibleUpwardPlanarSubgraph which
11 * computes an feasible upward planar subgraph and a feasible upward embedding.
13 * \author Hoi-Ming Wong
16 * This file is part of the Open Graph Drawing Framework (OGDF).
20 * See README.txt in the root directory of the OGDF installation for details.
23 * This program is free software; you can redistribute it and/or
24 * modify it under the terms of the GNU General Public License
25 * Version 2 or 3 as published by the Free Software Foundation;
26 * see the file LICENSE.txt included in the packaging of this file
30 * This program is distributed in the hope that it will be useful,
31 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
33 * GNU General Public License for more details.
36 * You should have received a copy of the GNU General Public
37 * License along with this program; if not, write to the Free
38 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
39 * Boston, MA 02110-1301, USA.
41 * \see http://www.gnu.org/copyleft/gpl.html
42 ***************************************************************/
49 #ifndef OGDF_FEASIBLE_UPWARD_PLANAR_SUBGRAPH_H
50 #define OGDF_FEASIBLE_UPWARD_PLANAR_SUBGRAPH_H
54 #include <ogdf/basic/Module.h>
55 #include <ogdf/basic/GraphCopy.h>
61 class OGDF_EXPORT FeasibleUpwardPlanarSubgraph
: public Module
65 FeasibleUpwardPlanarSubgraph() { }
67 ~FeasibleUpwardPlanarSubgraph() { }
69 // Computes a feasible upward planar subgraph fups with feasible a
72 Graph
&G
, // connected single source graph
73 GraphCopy
&Fups
, // the feasible upward planar subgraph
74 adjEntry
&extFaceHandle
, // the right face of this adjEntry is the ext. face of the embedded fups
75 List
<edge
> &delEdges
, // the list of deleted edges (original edges)
76 bool multisources
, // true, if the original input graph has multi sources
77 // and G is an tranformed single source graph (by introducing a super source)
78 int runs
); // number of runs
80 // Computes a feasible upward planar subgraph fups with feasible a
85 adjEntry
&extFaceHandle
,
89 // construct a merge graph with repsect to gamma and its test acyclicity
90 bool constructMergeGraph(
91 GraphCopy
&M
, // copy of the original graph, muss be embedded
92 adjEntry adj_orig
, // the adjEntry of the original graph, which right face is the ext. Face and adj->theNode() is the source
93 const List
<edge
> &del_orig
); // deleted edges
96 //! return a adjEntry of node v which right face is f. Be Carefully! The adjEntry is not always unique.
97 adjEntry
getAdjEntry(const CombinatorialEmbedding
&Gamma
, node v
, face f
)
101 if (Gamma
.rightFace(adj
) == f
)
105 OGDF_ASSERT(Gamma
.rightFace(adj
) == f
);
112 //! Compute a (random) span tree of the input sT-Graph.
114 * @param GC The input graph.
115 * @param &delEdges The deleted edges (original edges).
116 * @param random compute a random span tree
117 * @multisource true, if the original graph got multisources. In this case, the incident edges of
118 * the source are allways included in the span tree
120 void getSpanTree(GraphCopy
&GC
, List
<edge
> &delEdges
, bool random
, bool multisources
);
123 * Function use by geSpannTree to compute the spannig tree.
125 void dfs_visit(const Graph
&G
, edge e
, NodeArray
<bool> &visited
, EdgeArray
<bool> &treeEdges
, bool random
);
133 } // end namespace ogdf