6 * $Date: 2012-07-12 23:31:45 +0200 (Do, 12. Jul 2012) $
7 ***************************************************************/
10 * \brief Computes an embedding of a graph with minimum depth and
11 * maximum external face.
13 * \author Thorsten Kerkhof
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 ***************************************************************/
48 #ifndef OGDF_EMBEDDER_MIN_DEPTH_MAX_FACE_H
49 #define OGDF_EMBEDDER_MIN_DEPTH_MAX_FACE_H
51 #include <ogdf/module/EmbedderModule.h>
52 #include <ogdf/decomposition/BCTree.h>
53 #include <ogdf/internal/planarity/MDMFLengthAttribute.h>
57 //! Planar graph embedding with minimum block-nesting depth and maximum external face.
59 * See the paper "Graph Embedding with Minimum Depth and Maximum External Face"
60 * by C. Gutwenger and P. Mutzel (2004) for details.
62 class OGDF_EXPORT EmbedderMinDepthMaxFace
: public EmbedderModule
66 EmbedderMinDepthMaxFace() { }
69 * \brief Call embedder algorithm.
70 * \param G is the original graph. Its adjacency list has to be changed by the embedder.
71 * \param adjExternal is an adjacency entry on the external face and has to be set by the embedder.
73 void call(Graph
& G
, adjEntry
& adjExternal
);
77 * \brief Bottom-up-traversal of bcTree computing the values \a m_{cT, bT}
78 * for all edges \a (cT, bT) in the BC-tree. The length of each vertex
79 * \f$v \neq c in \a bT\f$ is set to 1 if \f$v \in M_{bT}\f$ and to 0 otherwise.
81 * \param bT is a block vertex in the BC-tree.
82 * \param cH is a vertex in the original graph \a G.
83 * \return Minimum depth of an embedding of \a bT with \a cH on the external
86 int md_bottomUpTraversal(const node
& bT
, const node
& cH
);
89 * \brief Top-down-traversal of BC-tree. The minimum depth of the BC-tree-node
90 * bT is calculated and before calling the function recursively for all
91 * children of bT in the BC-tree, the nodeLength of the cut-vertex which bT
92 * and the child have in common is computed. The length of each node is set to
93 * 1 if it is in M_B and 0 otherwise, except for |M_B| = 1, than it is set to
94 * 1 if it is in M2 with m2 = \f$\max_{v \in V_B, v != c} m_B(v)\f$ and
95 * M2 = \f${c \in V_B \ {v} | m_B(c) = m2}\f$.
97 * \param bT is a block vertex in the BC-tree.
99 void md_topDownTraversal(const node
& bT
);
102 * \brief Bottom up traversal of BC-tree.
104 * \param bT is the BC-tree node treated in this function call.
105 * \param cH is the block node which is related to the cut vertex which is
106 * parent of bT in BC-tree.
108 int mf_constraintMaxFace(const node
& bT
, const node
& cH
);
111 * \brief Top down traversal of BC-tree.
113 * \param bT is the tree node treated in this function call.
114 * \param bT_opt is assigned a block node in BC-tree which contains a face which
115 * cann be expanded to a maximum face.
116 * \param ell_opt is the size of a maximum face.
118 void mf_maximumFaceRec(const node
& bT
, node
& bT_opt
, int& ell_opt
);
121 * \brief Computes the adjacency list for all nodes in a block and calls
122 * recursively the function for all blocks incident to nodes in bT.
124 * \param bT is the tree node treated in this function call.
126 void embedBlock(const node
& bT
);
129 * \brief Computes the adjacency list for all nodes in a block and calls
130 * recursively the function for all blocks incident to nodes in bT.
132 * \param bT is the tree node treated in this function call.
133 * \param cT is the parent cut vertex node of bT in the BC-tree. cT is 0 if bT
135 * \param after is the adjacency entry of the cut vertex, after which bT has to
138 void embedBlock(const node
& bT
, const node
& cT
, ListIterator
<adjEntry
>& after
);
141 /** the BC-tree of G */
144 /** an adjacency entry on the external face */
145 adjEntry
* pAdjExternal
;
147 /** saving for each node in the block graph its length */
148 NodeArray
<int> md_nodeLength
;
150 /** an array containing the minimum depth of each block */
151 NodeArray
<int> md_minDepth
;
153 /** an array saving the length for each edge in the BC-tree */
154 EdgeArray
<int> md_m_cB
;
156 /** M_B = \f${cH \in B | m_B(cH) = m_B}\f$ with m_B = \f$\max_{c \in B} m_B(c)\f$
157 * and m_B(c) = \f$\max {0} \cup {m_{c, B'} | c \in B', B' \neq B}\f$. */
158 NodeArray
< List
<node
> > md_M_B
;
160 /** M2 is empty, if |M_B| != 1, otherwise M_B = {cH}
161 * M2 = \f${cH' \in V_B \ {v} | m_B(cH') = m2}\f$ with
162 * m2 = \f$\max_{vH \in V_B, vH != cH} m_B(vH)\f$. */
163 NodeArray
< List
<node
> > md_M2
;
165 /** is saving for each node of the block graph its length */
166 NodeArray
<int> mf_nodeLength
;
168 /** is saving for each node of the block graph its cstrLength */
169 NodeArray
<int> mf_cstrLength
;
171 /** an array containing the maximum face size of each block */
172 NodeArray
<int> mf_maxFaceSize
;
174 /** is saving for each node of the block graph its length */
175 NodeArray
<MDMFLengthAttribute
> mdmf_nodeLength
;
177 /** is saving for each edge of the block graph its length */
178 EdgeArray
<MDMFLengthAttribute
> mdmf_edgeLength
;
180 /** saves for every node of G the new adjacency list */
181 NodeArray
< List
<adjEntry
> > newOrder
;
183 /** treeNodeTreated saves for all block nodes in the
184 * BC-tree if it has already been treated or not. */
185 NodeArray
<bool> treeNodeTreated
;
188 } // end namespace ogdf