Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

MultilevelGraph.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/Graph.h>
36 #include <vector>
37 #include <map>
38 
39 namespace ogdf {
40 
41 //Stores info on merging for a refinement level
42 struct 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 
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 
66 {
67 private:
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 
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 
92 public:
93  ~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.
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; }
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 }
ogdf::MultilevelGraph::m_GA
GraphAttributes * m_GA
Definition: MultilevelGraph.h:70
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::MultilevelGraph::radius
void radius(node v, double r)
Definition: MultilevelGraph.h:111
ogdf::GraphAttributes
Stores additional attributes of a graph (like layout information).
Definition: GraphAttributes.h:67
GraphAttributes.h
Declaration of class GraphAttributes which extends a Graph by additional attributes.
Graph.h
Includes declaration of graph class.
OGDF_DEPRECATED
#define OGDF_DEPRECATED(reason)
Mark a class / member / function as deprecated.
Definition: config.h:118
ogdf::NodeMerge::m_mergedNode
int m_mergedNode
Definition: MultilevelGraph.h:51
ogdf::NodeElement::index
int index() const
Returns the (unique) node index.
Definition: Graph_d.h:203
ogdf::MultilevelGraph::getGraphAttributes
GraphAttributes & getGraphAttributes() const
Returns attributes of current level graph as GraphAttributes.
Definition: MultilevelGraph.h:130
ogdf::MultilevelGraph::getGraph
Graph & getGraph()
Definition: MultilevelGraph.h:128
ogdf::GraphAttributes::x
double x(node v) const
Returns the x-coordinate of node v.
Definition: GraphAttributes.h:261
ogdf::NodeMerge::m_level
int m_level
Definition: MultilevelGraph.h:57
ogdf::MultilevelGraph::averageRadius
double averageRadius() const
Definition: MultilevelGraph.h:112
ogdf::MultilevelGraph
Definition: MultilevelGraph.h:65
ogdf::NodeMerge::m_radius
std::map< int, double > m_radius
Definition: MultilevelGraph.h:55
ogdf::NodeArray< double >
ogdf::EdgeArray< double >
ogdf::MultilevelGraph::m_nodeAssociations
NodeArray< int > m_nodeAssociations
Definition: MultilevelGraph.h:78
ogdf::MultilevelGraph::radius
double radius(node v)
Definition: MultilevelGraph.h:110
ogdf::NodeMerge::m_changedEdges
std::vector< int > m_changedEdges
Definition: MultilevelGraph.h:46
ogdf::GraphAttributes::y
double y(node v) const
Returns the y-coordinate of node v.
Definition: GraphAttributes.h:281
ogdf::NodeMerge::m_doubleWeight
std::map< int, double > m_doubleWeight
Definition: MultilevelGraph.h:47
ogdf::MultilevelGraph::getRArray
NodeArray< double > & getRArray()
Definition: MultilevelGraph.h:104
ogdf::NodeMerge
Definition: MultilevelGraph.h:42
r
int r[]
Definition: hierarchical-ranking.cpp:8
ogdf::MultilevelGraph::m_createdGraph
bool m_createdGraph
Definition: MultilevelGraph.h:68
ogdf::MultilevelGraph::m_reverseNodeIndex
std::vector< node > m_reverseNodeIndex
Definition: MultilevelGraph.h:81
ogdf::MultilevelGraph::m_changes
std::vector< NodeMerge * > m_changes
Definition: MultilevelGraph.h:71
ogdf::MultilevelGraph::m_avgRadius
double m_avgRadius
Definition: MultilevelGraph.h:73
ogdf::NodeMerge::NodeMerge
NodeMerge(int level)
Definition: MultilevelGraph.h:60
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::MultilevelGraph::getWArray
EdgeArray< double > & getWArray()
Definition: MultilevelGraph.h:105
ogdf::MultilevelGraph::m_reverseNodeMergeWeight
std::vector< int > m_reverseNodeMergeWeight
Definition: MultilevelGraph.h:82
ogdf::MultilevelGraph::m_reverseEdgeIndex
std::vector< edge > m_reverseEdgeIndex
Definition: MultilevelGraph.h:83
ogdf::MultilevelGraph::x
void x(node v, double x)
Definition: MultilevelGraph.h:116
ogdf::MultilevelGraph::weight
void weight(edge e, double weight)
Definition: MultilevelGraph.h:119
std
Definition: GML.h:110
ogdf::MultilevelGraph::y
double y(node v)
Definition: MultilevelGraph.h:115
ogdf::NodeMerge::m_position
std::vector< std::pair< int, double > > m_position
Definition: MultilevelGraph.h:52
ogdf::NodeMerge::m_source
std::map< int, int > m_source
Definition: MultilevelGraph.h:48
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::MultilevelGraph::m_radius
NodeArray< double > m_radius
Definition: MultilevelGraph.h:72
ogdf::MultilevelGraph::mergeWeight
int mergeWeight(node v)
Definition: MultilevelGraph.h:123
ogdf::MultilevelGraph::x
double x(node v)
Definition: MultilevelGraph.h:114
ogdf::NodeMerge::~NodeMerge
~NodeMerge()
Definition: MultilevelGraph.h:61
ogdf::MultilevelGraph::weight
double weight(edge e)
Definition: MultilevelGraph.h:120
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::NodeMerge::m_deletedEdges
std::vector< int > m_deletedEdges
Definition: MultilevelGraph.h:45
ogdf::MultilevelGraph::m_edgeAssociations
EdgeArray< int > m_edgeAssociations
Definition: MultilevelGraph.h:79
ogdf::MultilevelGraph::m_weight
EdgeArray< double > m_weight
Definition: MultilevelGraph.h:75
ogdf::MultilevelGraph::y
void y(node v, double y)
Definition: MultilevelGraph.h:117
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::NodeMerge::m_target
std::map< int, int > m_target
Definition: MultilevelGraph.h:49
ogdf::NodeMerge::m_changedNodes
std::vector< int > m_changedNodes
Definition: MultilevelGraph.h:54
ogdf::MultilevelGraph::m_G
Graph * m_G
Definition: MultilevelGraph.h:69