Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MultilevelGraph.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Graph.h>
36
37#include <map>
38#include <vector>
39
40namespace ogdf {
41
42//Stores info on merging for a refinement level
43struct NodeMerge {
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
52 // optional information <target, distance>.
53 // mergedNode will be placed at average of relative distances to target.
54 std::vector<std::pair<int, double>> m_position;
55
56 std::vector<int> m_changedNodes; // there may be placement strategies that use more than one reference-node.
57 std::map<int, double> m_radius; // for changed nodes and the merged node
58
60
61 explicit NodeMerge(int level) : m_mergedNode(-1), m_level(level) { }
62
64};
65
67private:
68 bool m_createdGraph; //used in destructor, TODO: check if it is needed
70 GraphAttributes* m_GA; //<! Keeps layout info in replacement of information below (todo: remove them)
71 std::vector<NodeMerge*> m_changes;
73 double m_avgRadius; //stores average node radius for scaling and random layout purposes
74
76
77 // Associations to index only as the node/edge may be nonexistent
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
89
92
93public:
96 explicit MultilevelGraph(Graph& G);
98 // if the Graph is available without const, no copy needs to be created.
100
101 // creates MultilevelGraph directly from GML file.
102 explicit MultilevelGraph(std::istream& is);
103 explicit MultilevelGraph(const char* filename);
104
105 NodeArray<double>& getRArray() { return m_radius; }
106
107 EdgeArray<double>& getWArray() { return m_weight; }
108
109 edge getEdge(unsigned int index);
110 node getNode(unsigned int index);
111
112 double radius(node v) { return m_radius[v]; }
113
114 void radius(node v, double r) { m_radius[v] = r; }
115
116 double averageRadius() const { return m_avgRadius; }
117
118 double x(node v) { return m_GA->x(v); }
119
120 double y(node v) { return m_GA->y(v); }
121
122 void x(node v, double x) { m_GA->x(v) = x; }
123
124 void y(node v, double y) { m_GA->y(v) = y; }
125
126 void weight(edge e, double weight) { m_weight[e] = weight; }
127
128 double weight(edge e) { return m_weight[e]; }
129
130 //returns the merge weight, i.e. the number of nodes represented by v on the current level
131 int mergeWeight(node v) { return m_reverseNodeMergeWeight[v->index()]; }
132
134
135 int getLevel();
136
137 Graph& getGraph() { return *m_G; }
138
140 GraphAttributes& getGraphAttributes() const { return *m_GA; }
141
147 void reInsertAll(std::vector<MultilevelGraph*>& components);
148 void copyNodeTo(node v, MultilevelGraph& MLG, std::map<node, node>& tempNodeAssociations,
149 bool associate, int index = -1);
150 void copyEdgeTo(edge e, MultilevelGraph& MLG, std::map<node, node>& tempNodeAssociations,
151 bool associate, int index = -1);
152 void writeGML(std::ostream& os);
153 void writeGML(const char* fileName);
154
155 // the original graph will be cleared to save Memory
156 OGDF_DEPRECATED("Use ComponentSplitterLayout instead.")
157 std::vector<MultilevelGraph*> splitIntoComponents();
158
159 bool postMerge(NodeMerge* NM, node merged);
160 //\a merged is the node now represented by \a theNode
161 bool changeNode(NodeMerge* NM, node theNode, double newRadius, node merged);
162 bool changeEdge(NodeMerge* NM, edge theEdge, double newWeight, node newSource, node newTarget);
163 bool deleteEdge(NodeMerge* NM, edge theEdge);
164 std::vector<edge> moveEdgesToParent(NodeMerge* NM, node theNode, node parent,
166 NodeMerge* getLastMerge();
167 node undoLastMerge();
168
169 void updateReverseIndizes();
170 //sets the merge weights back to initial values
171 void updateMergeWeights();
172};
173
174}
Includes declaration of graph class.
Declaration of class GraphAttributes which extends a Graph by additional attributes.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Stores additional attributes of a graph (like layout information).
double y(node v) const
Returns the y-coordinate of node v.
double x(node v) const
Returns the x-coordinate of node v.
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
void writeGML(const char *fileName)
MultilevelGraph(const char *filename)
NodeArray< int > m_nodeAssociations
void reInsertGraph(MultilevelGraph &MLG)
double averageRadius() const
MultilevelGraph * removeOneCC(std::vector< node > &componentSubArray)
void weight(edge e, double weight)
std::vector< node > m_reverseNodeIndex
GraphAttributes * m_GA
std::vector< int > m_reverseNodeMergeWeight
std::vector< NodeMerge * > m_changes
void importAttributes(const GraphAttributes &GA)
void copyNodeTo(node v, MultilevelGraph &MLG, std::map< node, node > &tempNodeAssociations, bool associate, int index=-1)
void reInsertAll(std::vector< MultilevelGraph * > &components)
void y(node v, double y)
void exportAttributes(GraphAttributes &GA) const
EdgeArray< int > m_edgeAssociations
MultilevelGraph(GraphAttributes &GA)
NodeArray< double > m_radius
void x(node v, double x)
void radius(node v, double r)
MultilevelGraph(GraphAttributes &GA, Graph &G)
node getNode(unsigned int index)
MultilevelGraph(std::istream &is)
EdgeArray< double > & getWArray()
NodeArray< double > & getRArray()
EdgeArray< double > m_weight
GraphAttributes & getGraphAttributes() const
Returns attributes of current level graph as GraphAttributes.
void exportAttributesSimple(GraphAttributes &GA) const
void copyEdgeTo(edge e, MultilevelGraph &MLG, std::map< node, node > &tempNodeAssociations, bool associate, int index=-1)
edge getEdge(unsigned int index)
void copyFromGraph(const Graph &G, NodeArray< int > &nodeAssociations, EdgeArray< int > &edgeAssociations)
std::vector< edge > m_reverseEdgeIndex
void writeGML(std::ostream &os)
void importAttributesSimple(const GraphAttributes &GA)
void prepareGraphAttributes(GraphAttributes &GA) const
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
int index() const
Returns the (unique) node index.
Definition Graph_d.h:211
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_DEPRECATED(reason)
Mark a class / member / function as deprecated.
Definition config.h:120
int r[]
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Definition GML.h:110
std::vector< int > m_changedEdges
std::map< int, double > m_radius
std::map< int, int > m_target
std::vector< int > m_changedNodes
std::vector< int > m_deletedEdges
std::vector< std::pair< int, double > > m_position
std::map< int, double > m_doubleWeight
std::map< int, int > m_source
NodeMerge(int level)