1// Introduction for Multilevelmixer:
2//
3// Multilevel layout computation is an iterative process that can
4// be roughly divided in three phases: coarsening, placement, and
5// single level layout. Starting with the smallest graph, the final
6// layout for the input graph is obtained by successively computing
7// layouts for the graph sequence computed by the coarsening phase.
8// At each level, the additional vertices need to be placed into the
9// layout of the preceding level, optionally after a scaling to provide
10// the necessary space.
11// It helps to overcome some problems of single level energybased graph
12// layouts (such as finding a local optimal solution) and it speeds up
13// the computation.
14//
15// The Modular Multilevel Mixer is an abstract class that can be used
16// to build energybased multilevel layouts. Since it is modular you can
17// easily assemble different layouts by using different coarsening
18// techniques (merger), placer and single level layouts.
19
20#include <ogdf/basic/PreprocessorLayout.h>
21#include <ogdf/energybased/FastMultipoleEmbedder.h>
22#include <ogdf/energybased/multilevel_mixer/BarycenterPlacer.h>
23#include <ogdf/energybased/multilevel_mixer/EdgeCoverMerger.h>
24#include <ogdf/energybased/multilevel_mixer/LocalBiconnectedMerger.h>
25#include <ogdf/energybased/multilevel_mixer/ModularMultilevelMixer.h>
26#include <ogdf/energybased/multilevel_mixer/ScalingLayout.h>
27#include <ogdf/energybased/multilevel_mixer/SolarMerger.h>
28#include <ogdf/energybased/multilevel_mixer/SolarPlacer.h>
29#include <ogdf/fileformats/GraphIO.h>
30#include <ogdf/packing/ComponentSplitterLayout.h>
31#include <ogdf/packing/TileToRowsCCPacker.h>
32
33using namespace ogdf;
34
35template<class T>
36static MultilevelBuilder *getDoubleFactoredZeroAdjustedMerger()
37{
38 T *merger = new T();
39 merger->setFactor(2.0);
40 merger->setEdgeLengthAdjustment(0);
41 return merger;
42}
43
44static InitialPlacer *getBarycenterPlacer()
45{
46 BarycenterPlacer *placer = new BarycenterPlacer();
47 placer->weightedPositionPriority(true);
48 return placer;
49}
50
51static void configureFastLayout(ScalingLayout *sl, MultilevelBuilder *&merger, InitialPlacer *&placer)
52{
53 // The SolarMerger is used for the coarsening phase.
54 merger = new SolarMerger(false, false);
55 // The SolarPlacer is used for the placement.
56 placer = new SolarPlacer();
57
58 // Postprocessing is applied at each level after the single level layout.
59 // It is turned off in this example.
60 sl->setExtraScalingSteps(0);
61 // In this example it is used to scale with fixed factor 2 relative to the graph drawing.
62 sl->setScalingType(ScalingLayout::ScalingType::RelativeToDrawing);
63 sl->setScaling(2.0, 2.0);
64}
65
66static void configureNiceLayout(ScalingLayout *sl, MultilevelBuilder *&merger, InitialPlacer *&placer)
67{
68 // The EdgeCoverMerger is used for the coarsening phase.
69 merger = getDoubleFactoredZeroAdjustedMerger<EdgeCoverMerger>();
70 // The BarycenterPlacer is used for the placement.
71 placer = getBarycenterPlacer();
72
73 // Postprocessing is applied at each level after the single level layout.
74 // In this example a FastMultipoleEmbedder with zero iterations is used for postprocessing.
75 sl->setExtraScalingSteps(0);
76 // No scaling is done. It is fixed to factor 1.
77 sl->setScalingType(ScalingLayout::ScalingType::RelativeToDrawing);
78 sl->setScaling(1.0, 1.0);
79}
80
81static void configureNoTwistLayout(ScalingLayout *sl, MultilevelBuilder *&merger, InitialPlacer *&placer)
82{
83 // The LocalBiconnectedMerger is used for the coarsening phase.
84 // It tries to keep biconnectivity to avoid twisted graph layouts.
85 merger = getDoubleFactoredZeroAdjustedMerger<LocalBiconnectedMerger>();
86 // The BarycenterPlacer is used for the placement.
87 placer = getBarycenterPlacer();
88
89 // Postprocessing is applied at each level after the single level layout.
90 // It is turned off in this example.
91 sl->setExtraScalingSteps(1);
92 // The ScalingLayout is used to scale with a factor between 5 and 10
93 // relative to the edge length.
94 sl->setScalingType(ScalingLayout::ScalingType::RelativeToDesiredLength);
95 sl->setScaling(5.0, 10.0);
96}
97
98int main(int argc, const char *argv[])
99{
100 if (argc != 2) {
101 std::cout << "Usage: " << argv[0] << " (0|1|2)" << std::endl;
102 return 255;
103 }
104
105 // We first declare a Graph G with GraphAttributes GA and load it from
106 // the GML file sierpinski_04.gml.
107 Graph g;
108 GraphAttributes ga(g);
109 if (!GraphIO::read(ga, g, "uk_Pack_Bary_EC_FRENC.gml", GraphIO::readGML)) {
110 std::cerr << "Could not load Graph" << std::endl;
111 return 1;
112 }
113
114 // We assign a width and height of 10.0 to each node.
115 for (node v : g.nodes) {
116 ga.width(v) = ga.height(v) = 10.0;
117 }
118
119 // Then we create a MultilevelGraph from the GraphAttributes.
120 MultilevelGraph mlg(ga);
121
122 // The FastMultipoleEmbedder is used for the single level layout.
123 FastMultipoleEmbedder *fme = new FastMultipoleEmbedder();
124 // It will use 1000 iterations at each level.
125 fme->setNumIterations(1000);
126 fme->setRandomize(false);
127
128 // To minimize dispersion of the graph when more nodes are added, a
129 // ScalingLayout can be used to scale up the graph on each level.
130 ScalingLayout *sl = new ScalingLayout();
131 sl->setLayoutRepeats(1);
132 // The FastMultipoleEmbedder is nested into this ScalingLayout.
133 sl->setSecondaryLayout(fme);
134
135 // Set the merger and placer according to the wanted configuration.
136 MultilevelBuilder *merger;
137 InitialPlacer *placer;
138 switch (argv[1][0]) {
139 case 2:
140 configureFastLayout(sl, merger, placer);
141 break;
142 case 1:
143 configureNiceLayout(sl, merger, placer);
144 break;
145 default:
146 configureNoTwistLayout(sl, merger, placer);
147 break;
148 }
149
150 // Then the ModularMultilevelMixer is created.
151 ModularMultilevelMixer *mmm = new ModularMultilevelMixer;
152 mmm->setLayoutRepeats(1);
153 // The single level layout, the placer and the merger are set.
154 mmm->setLevelLayoutModule(sl);
155 mmm->setInitialPlacer(placer);
156 mmm->setMultilevelBuilder(merger);
157
158 // Since energybased algorithms are not doing well for disconnected
159 // graphs, the ComponentSplitterLayout is used to split the graph and
160 // computation is done separately for each connected component.
161 ComponentSplitterLayout *csl = new ComponentSplitterLayout;
162 // The TileToRowsPacker merges these connected components after computation.
163 TileToRowsCCPacker *ttrccp = new TileToRowsCCPacker;
164 csl->setPacker(ttrccp);
165 csl->setLayoutModule(mmm);
166
167 // At last the PreprocessorLayout removes double edges and loops.
168 PreprocessorLayout ppl;
169 ppl.setLayoutModule(csl);
170 ppl.setRandomizePositions(true);
171
172 ppl.call(mlg);
173
174 // After the computation the MultilevelGraph is exported to the
175 // GraphAttributes and written to disk.
176 mlg.exportAttributes(ga);
177 GraphIO::write(ga, "output-multilevelmixer-.gml", GraphIO::writeGML);
178
179 return 0;
180}
181