1/** \file
2 * \brief MLG is the main data structure for ModularMultilevelMixer
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 <ogdf/basic/Graph.h>
35#include <ogdf/basic/GraphAttributes.h>
36#include <vector>
37#include <map>
38
39namespace ogdf {
40
41//Stores info on merging for a refinement level
42struct NodeMerge
43{
44 // Node/Edge IDs instead of pointers as the nodes themselves may be nonexistent.
45 std::vector<int> m_deletedEdges;
46 std::vector<int> m_changedEdges;
47 std::map<int, double> m_doubleWeight; // for changed and deleted edges
48 std::map<int, int> m_source;
49 std::map<int, int> m_target;
50
51 int m_mergedNode;
52 std::vector< std::pair<int, double> > m_position; // optional information <target, distance>. mergedNode will be placed at average of relative distances to target.
53
54 std::vector<int> m_changedNodes; // there may be placement strategies that use more than one reference-node.
55 std::map<int, double> m_radius; // for changed nodes and the merged node
56
57 int m_level;
58
59
60 explicit NodeMerge(int level) : m_mergedNode(-1), m_level(level) { }
61 ~NodeMerge() { }
62};
63
64
65class OGDF_EXPORT MultilevelGraph
66{
67private:
68 bool m_createdGraph; //used in destructor, TODO: check if it is needed
69 Graph * m_G;
70 GraphAttributes * m_GA; //<! Keeps layout info in replacement of information below (todo: remove them)
71 std::vector<NodeMerge *> m_changes;
72 NodeArray<double> m_radius;
73 double m_avgRadius; //stores average node radius for scaling and random layout purposes
74
75 EdgeArray<double> m_weight;
76
77 // Associations to index only as the node/edge may be nonexistent
78 NodeArray<int> m_nodeAssociations;
79 EdgeArray<int> m_edgeAssociations;
80
81 std::vector<node> m_reverseNodeIndex;
82 std::vector<int> m_reverseNodeMergeWeight;//<! Keeps number of vertices represented by vertex with given index
83 std::vector<edge> m_reverseEdgeIndex;
84
85 MultilevelGraph * removeOneCC(std::vector<node> &componentSubArray);
86 void copyFromGraph(const Graph &G, NodeArray<int> &nodeAssociations, EdgeArray<int> &edgeAssociations);
87 void prepareGraphAttributes(GraphAttributes &GA) const;
88
89 void initReverseIndizes();
90 void initInternal();
91
92public:
93 ~MultilevelGraph();
94 MultilevelGraph();
95 explicit MultilevelGraph(Graph &G);
96 explicit MultilevelGraph(GraphAttributes &GA);
97 // if the Graph is available without const, no copy needs to be created.
98 MultilevelGraph(GraphAttributes &GA, Graph &G);
99
100 // creates MultilevelGraph directly from GML file.
101 explicit MultilevelGraph(std::istream &is);
102 explicit MultilevelGraph(const char *filename);
103
104 NodeArray<double> &getRArray() { return m_radius; }
105 EdgeArray<double> &getWArray() { return m_weight; }
106
107 edge getEdge(unsigned int index);
108 node getNode(unsigned int index);
109
110 double radius(node v) { return m_radius[v]; }
111 void radius(node v, double r) { m_radius[v] = r; }
112 double averageRadius() const { return m_avgRadius;}
113
114 double x(node v) { return m_GA->x(v); }
115 double y(node v) { return m_GA->y(v); }
116 void x(node v, double x) { m_GA->x(v) = x;}
117 void y(node v, double y) { m_GA->y(v) = y;}
118
119 void weight(edge e, double weight) { m_weight[e] = weight; }
120 double weight(edge e) { return m_weight[e]; }
121
122 //returns the merge weight, i.e. the number of nodes represented by v on the current level
123 int mergeWeight(node v) {return m_reverseNodeMergeWeight[v->index()];}
124
125 void moveToZero();
126
127 int getLevel();
128 Graph & getGraph() { return *m_G; }
129 //! Returns attributes of current level graph as GraphAttributes
130 GraphAttributes & getGraphAttributes() const { return *m_GA; }
131 void exportAttributes(GraphAttributes &GA) const;
132 void exportAttributesSimple(GraphAttributes &GA) const;
133 void importAttributes(const GraphAttributes &GA);
134 void importAttributesSimple(const GraphAttributes &GA);
135 void reInsertGraph(MultilevelGraph &MLG);
136 void reInsertAll(std::vector<MultilevelGraph *> &components);
137 void copyNodeTo(node v, MultilevelGraph &MLG, std::map<node, node> &tempNodeAssociations, bool associate, int index = -1);
138 void copyEdgeTo(edge e, MultilevelGraph &MLG, std::map<node, node> &tempNodeAssociations, bool associate, int index = -1);
139 void writeGML(std::ostream &os);
140 void writeGML(const char *fileName);
141
142 // the original graph will be cleared to save Memory
143 OGDF_DEPRECATED("Use ComponentSplitterLayout instead.")
144 std::vector<MultilevelGraph *> splitIntoComponents();
145
146 bool postMerge(NodeMerge * NM, node merged);
147 //\a merged is the node now represented by \a theNode
148 bool changeNode(NodeMerge * NM, node theNode, double newRadius, node merged);
149 bool changeEdge(NodeMerge * NM, edge theEdge, double newWeight, node newSource, node newTarget);
150 bool deleteEdge(NodeMerge * NM, edge theEdge);
151 std::vector<edge> moveEdgesToParent(NodeMerge * NM, node theNode, node parent, bool deleteDoubleEndges, int adjustEdgeLengths);
152 NodeMerge * getLastMerge();
153 node undoLastMerge();
154
155 void updateReverseIndizes();
156 //sets the merge weights back to initial values
157 void updateMergeWeights();
158};
159
160}
161