6 * $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
7 ***************************************************************/
10 * \brief A simple embedder algorithm.
12 * \author Thorsten Kerkhof
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 ***************************************************************/
43 #include <ogdf/planarity/SimpleEmbedder.h>
47 void SimpleEmbedder::call(Graph
& G
, adjEntry
& adjExternal
)
49 OGDF_ASSERT(isPlanar(G
));
51 //----------------------------------------------------------
53 // determine embedding of G
56 // We currently compute any embedding and choose the maximal face
59 // if we use FixedEmbeddingInserter, we have to re-use the computed
60 // embedding, otherwise crossing nodes can turn into "touching points"
61 // of edges (alternatively, we could compute a new embedding and
62 // finally "remove" such unnecessary crossings).
64 if(!G
.representsCombEmbedding())
67 if (G
.numberOfEdges() > 0)
69 CombinatorialEmbedding
E(G
);
70 //face fExternal = E.maximalFace();
71 face fExternal
= findBestExternalFace(G
, E
);
72 adjExternal
= fExternal
->firstAdj();
77 face
SimpleEmbedder::findBestExternalFace(
79 const CombinatorialEmbedding
& E
)
81 FaceArray
<int> weight(E
);
85 weight
[f
] = f
->size();
90 if(PG
.typeOf(v
) != Graph::generalizationMerger
)
95 if(adj
->theEdge()->source() == v
)
99 OGDF_ASSERT(adj
->theEdge()->source() == v
);
101 node w
= adj
->theEdge()->target();
105 forall_adj(adj2
, w
) {
106 edge e
= adj2
->theEdge();
107 if(e
->target() != w
&& PG
.typeOf(e
) == Graph::generalization
) {
116 face f1
= E
.leftFace(adj
);
117 face f2
= E
.rightFace(adj
);
119 weight
[f1
] += v
->indeg();
121 weight
[f2
] += v
->indeg();
124 face fBest
= E
.firstFace();
126 if(weight
[f
] > weight
[fBest
])
132 } // end namespace ogdf