Graph Drawing

 v. 2023.09 (Elderberry)

No Matches
Go to the documentation of this file.
1// Introduction for Multilevelmixer:
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.
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.
33using namespace ogdf;
35template<class T>
38 T *merger = new T();
39 merger->setFactor(2.0);
40 merger->setEdgeLengthAdjustment(0);
41 return merger;
46 BarycenterPlacer *placer = new BarycenterPlacer();
47 placer->weightedPositionPriority(true);
48 return placer;
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();
58 // Postprocessing is applied at each level after the single level layout.
59 // It is turned off in this example.
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);
68 // The EdgeCoverMerger is used for the coarsening phase.
70 // The BarycenterPlacer is used for the placement.
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);
83 // The LocalBiconnectedMerger is used for the coarsening phase.
84 // It tries to keep biconnectivity to avoid twisted graph layouts.
86 // The BarycenterPlacer is used for the placement.
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);
98int main(int argc, const char *argv[])
100 if (argc != 2) {
101 std::cout << "Usage: " << argv[0] << " (0|1|2)" << std::endl;
102 return 255;
103 }
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 }
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 }
119 // Then we create a MultilevelGraph from the GraphAttributes.
122 // The FastMultipoleEmbedder is used for the single level layout.
124 // It will use 1000 iterations at each level.
125 fme->setNumIterations(1000);
126 fme->setRandomize(false);
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.
131 sl->setLayoutRepeats(1);
132 // The FastMultipoleEmbedder is nested into this ScalingLayout.
133 sl->setSecondaryLayout(fme);
135 // Set the merger and placer according to the wanted configuration.
138 switch (argv[1][0]) {
139 case 2:
141 break;
142 case 1:
144 break;
145 default:
147 break;
148 }
150 // Then the ModularMultilevelMixer is created.
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);
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.
162 // The TileToRowsPacker merges these connected components after computation.
164 csl->setPacker(ttrccp);
165 csl->setLayoutModule(mmm);
167 // At last the PreprocessorLayout removes double edges and loops.
169 ppl.setLayoutModule(csl);
170 ppl.setRandomizePositions(true);
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-" + std::string(argv[1]) + ".gml", GraphIO::writeGML);
178 GraphIO::write(ga, "output-multilevelmixer-" + std::string(argv[1]) + ".svg", GraphIO::drawSVG);
180 return 0;
Places nodes at the barycenter of his neighbors.
Splits and packs the components of a Graph.
Merges nodes with neighbour to get a Multilevel Graph.
Declaration of Fast-Multipole-Embedder layout algorithm.
Declares class GraphIO which provides access to all graph read and write functionality.
Merges nodes with neighbour to get a Multilevel Graph.
MMM is a Multilevel Graph drawing Algorithm that can use different modules.
Preprocessor Layout simplifies Graphs for use in other Algorithms.
ScalingLayout scales and calls a secondary layout.
Merges nodes with solar system rules.
Places Nodes with solar system rules.
Declaration of class TileToRowsCCPacker.
The barycenter placer for multilevel layout.
void weightedPositionPriority(bool on)
The fast multipole embedder approach for force-directed layout.
Stores additional attributes of a graph (like layout information).
double height(node v) const
Returns the height of the bounding box of node v.
double width(node v) const
Returns the width of the bounding box of node v.
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition Graph_d.h:589
static bool write(const Graph &G, const string &filename, WriterFunc writer=nullptr)
Writes graph G to a file with name filename and infers the format to use from the file's extension.
static bool writeGML(const Graph &G, std::ostream &os)
Writes graph G in GML format to output stream os.
static bool drawSVG(const GraphAttributes &A, std::ostream &os, const SVGSettings &settings)
static bool readGML(Graph &G, std::istream &is)
Reads graph G in GML format from input stream is.
static bool read(Graph &G, const string &filename, ReaderFunc reader=nullptr)
Reads graph G from a file with name filename and infers the used format from the file's extension.
Base class for placer modules.
Modular multilevel graph layout.
Base class for merger modules.
Class for the representation of nodes.
Definition Graph_d.h:177
The PreprocessorLayout removes multi-edges and self-loops.
Scales a graph layout and calls a secondary layout algorithm.
void setScaling(double min, double max)
Sets the minimum and the maximum scaling factor.
void setExtraScalingSteps(unsigned int steps)
Sets how often the scaling should be repeated.
void setScalingType(ScalingType type)
Sets a ScalingType wich sets the relative scale for the Graph.
The solar merger for multilevel layout.
Definition SolarMerger.h:42
The solar placer for multilevel layout.
Definition SolarPlacer.h:42
The tile-to-rows algorithm for packing drawings of connected components.
int main()
static void configureFastLayout(ScalingLayout *sl, MultilevelBuilder *&merger, InitialPlacer *&placer)
static void configureNiceLayout(ScalingLayout *sl, MultilevelBuilder *&merger, InitialPlacer *&placer)
static void configureNoTwistLayout(ScalingLayout *sl, MultilevelBuilder *&merger, InitialPlacer *&placer)
static InitialPlacer * getBarycenterPlacer()
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.