1/** \file
2 * \brief MMM is a Multilevel Graph drawing Algorithm that can use different modules.
3 *
4 * \author Gereon Bartel
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#pragma once
33
34#include <memory>
35#include <ogdf/module/LayoutModule.h>
36#include <ogdf/energybased/multilevel_mixer/MultilevelGraph.h>
37#include <ogdf/energybased/multilevel_mixer/MultilevelBuilder.h>
38#include <ogdf/energybased/multilevel_mixer/InitialPlacer.h>
39
40
41namespace ogdf {
42
43//! Modular multilevel graph layout.
44/**
45 * @ingroup gd-multi
46 *
47 * <H3>%Module options</H3>
48 * The various phases of the algorithm can be exchanged by setting
49 * module options allowing flexible customization. The algorithm provides
50 * the following module options:
51 *
52 * <table>
53 * <tr>
54 * <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
55 * </tr><tr>
56 * <td><i>multilevelBuilder</i><td>MultilevelBuilder<td>SolarMerger
57 * <td>The multilevel builder module that computes the multilevel graph hierarchy.
58 * </tr><tr>
59 * <td><i>initialPlacer</i><td>InitialPlacer<td>BarycenterPlacer
60 * <td>The initial placer module that computes the initial positions for nodes inserted into the previous level.
61 * </tr><tr>
62 * <td><i>levelLayout</i><td>LayoutModule<td>FastMultipoleEmbedder
63 * <td>The layout module applied on each level.
64 * </tr><tr>
65 * <td><i>finalLayout</i><td>LayoutModule<td>none
66 * <td>The layout module applied on the last level.
67 * </tr><tr>
68 * <td><i>postLayout</i><td>LayoutModule<td>none
69 * <td>The layout module applied to the final drawing for additional beautification.
70 * </tr>
71 * </table>
72 */
73class OGDF_EXPORT ModularMultilevelMixer : public LayoutModule
74{
75private:
76
77 //! The layout algorithm applied on each level.
78 /**
79 * The one-level layout module should not completely discard the initial Layout
80 * but do incremental beautification.
81 * Usually a simple force-directed / energy-based Layout should be chosen.
82 */
83 std::unique_ptr<LayoutModule> m_oneLevelLayoutModule;
84
85 //! The layout algorithm applied on the last level (i.e., the largest graph in the multilevel hierarchy).
86 /**
87 * The final layout module can be set to speed up the computation if the
88 * one-level layout ist relatively slow. If not set, the one-level layout
89 * is also used on the last level.
90 */
91 std::unique_ptr<LayoutModule> m_finalLayoutModule;
92
93 //! The multilevel builder module computes the multilevel hierarchy.
94 std::unique_ptr<MultilevelBuilder> m_multilevelBuilder;
95
96 //! The initial placer module computes the initial positions for nodes inserted into the previous level.
97 std::unique_ptr<InitialPlacer> m_initialPlacement;
98
99 //! The one-level layout will be called #m_times to improve quality.
100 int m_times;
101
102 //! If set to a value > 0, all edge weights will be set to this value.
103 double m_fixedEdgeLength;
104
105 //! If set to a value > 0, all node sizes will be set to this value.
106 double m_fixedNodeSize;
107
108 double m_coarseningRatio; //!< Ratio between sizes of previous (p) and current (c) level graphs: c/p
109
110 bool m_levelBound; //!< Determines if computation is stopped when number of levels is too high.
111 bool m_randomize; //!< Determines if initial random layout is computed.
112
113public:
114
115 //! Error codes for calls.
116 enum class erc {
117 None, //!< no error
118 LevelBound //!< level bound exceeded by merger step
119 };
120
121 ModularMultilevelMixer();
122
123 //! Sets the one-level layout module to \p levelLayout.
124 void setLevelLayoutModule(LayoutModule *levelLayout) {
125 m_oneLevelLayoutModule.reset(levelLayout);
126 }
127
128 //! Sets the final layout module to \p finalLayout.
129 void setFinalLayoutModule(LayoutModule *finalLayout) {
130 m_finalLayoutModule.reset(finalLayout);
131 }
132
133 //! Sets the multilevel builder module to \p levelBuilder.
134 void setMultilevelBuilder(MultilevelBuilder *levelBuilder) {
135 m_multilevelBuilder.reset(levelBuilder);
136 }
137
138 //! Sets the initial placer module to \p placement.
139 void setInitialPlacer(InitialPlacer *placement) {
140 m_initialPlacement.reset(placement);
141 }
142
143 //! Determines how many times the one-level layout will be called.
144 void setLayoutRepeats(int times = 1) { m_times = times; }
145
146 //! If \p len > 0, all edge weights will be set to \p len.
147 void setAllEdgeLengths(double len) { m_fixedEdgeLength = len; }
148
149 //! If \p size > 0, all node sizes will be set to \p size.
150 void setAllNodeSizes(double size) { m_fixedNodeSize = size; }
151
152 //! Determines if an initial random layout is computed.
153 void setRandomize(bool b) { m_randomize = b; }
154
155 //! Determines if computation is stopped when number of levels is too high.
156 void setLevelBound(bool b) { m_levelBound = b; }
157
158 //! Calls the multilevel layout algorithm for graph attributes \p GA.
159 void call(GraphAttributes &GA) override;
160
161 /**
162 * \brief Calls the multilevel layout algorithm for multilevel graph \a MLG.
163 *
164 * This method allows the mixer to modify the Graph, saving some memory
165 * compared to a normal call(GA) in our implementation.
166 * (because the Graph is already given in the MultiLevelGraph Format
167 * (or can be converted without creating a copy) AND the layout would need a copy otherwise).
168 * All Incremental Layouts (especially energy based) CAN be called by ModularMultilevelMixer.
169 * @param MLG is the input graph and will also be assigned the layout information.
170 */
171#if 0
172 virtual void call(MultilevelGraph &MLG) {
173 GraphAttributes GA(MLG.getGraph());
174 MLG.exportAttributesSimple(GA);
175 call(GA);
176 MLG.importAttributesSimple(GA);
177 };
178#else
179 virtual void call(MultilevelGraph &MLG);
180#endif
181
182 //! Returns the error code of last call.
183 erc errorCode() { return m_errorCode; }
184
185 //! Returns the ratio c/p between sizes of previous (p) and current (c) level graphs.
186 double coarseningRatio() { return m_coarseningRatio; }
187
188private:
189 erc m_errorCode; //!< The error code of the last call.
190};
191
192}
193