GraphLayoutAlgorithm.h
Go to the documentation of this file.
1 /*
2  * GraphLayoutAlgorithm.h
3  *
4  * Created on: Apr 19, 2016
5  * Author: Michael Wegner
6  */
7
8 #ifndef NETWORKIT_CPP_VIZ_GRAPHLAYOUTALGORITHM_H_
9 #define NETWORKIT_CPP_VIZ_GRAPHLAYOUTALGORITHM_H_
10
11 #include "Point.h"
12 #include "../graph/Graph.h"
13 #include "../auxiliary/Enforce.h"
14
15 #include <vector>
16 #include <fstream>
17
18 namespace NetworKit {
19
25 template<typename T>
27 public:
28  GraphLayoutAlgorithm(const Graph& G, count dim) : G(G), vertexCoordinates(std::vector<Point<T>>(G.upperNodeIdBound(), Point<T>(dim))) {}
29  virtual ~GraphLayoutAlgorithm() = default;
30
31  virtual void run() = 0;
32
33  virtual std::vector<Point<T>> getCoordinates() const {
34  return vertexCoordinates;
35  }
36
37  virtual count numEdgeCrossings() const {
38  if (vertexCoordinates[0].getDimensions() == 2) {
39  count numCrossings = 0;
40  G.forEdges([&](node u, node v, edgeweight) {
41  G.forEdges([&](node p, node q, edgeweight) {
42  if ((p == u && q == v) || (p == v && q == u)) return;
43  double m1 = (vertexCoordinates[v][1] - vertexCoordinates[u][1]) / (vertexCoordinates[v][0] - vertexCoordinates[u][0]);
44  double m2 = (vertexCoordinates[q][1] - vertexCoordinates[p][1]) / (vertexCoordinates[q][0] - vertexCoordinates[p][0]);
45
46  double b1 = vertexCoordinates[u][1] - m1 * vertexCoordinates[u][0];
47  double b2 = vertexCoordinates[p][1] - m1 * vertexCoordinates[p][0];
48  if (m1 != m2) {
49  double xIntersect = (b2 - b1) / (m1 - m2);
50  double minXE1 = std::min(vertexCoordinates[u][0], vertexCoordinates[v][0]);
51  double minXE2 = std::min(vertexCoordinates[p][0], vertexCoordinates[q][0]);
52  double maxXE1 = std::max(vertexCoordinates[u][0], vertexCoordinates[v][0]);
53  double maxXE2 = std::max(vertexCoordinates[p][0], vertexCoordinates[q][0]);
54
55  if (minXE1 <= xIntersect && minXE2 <= xIntersect && xIntersect <= maxXE1 && xIntersect <= maxXE2) {
56  numCrossings++;
57  }
58  } else if (b1 == b2) {
59  numCrossings++;
60  }
61  });
62  });
63
64  numCrossings /= 2;
65  return numCrossings;
66  }
67
68  return 0;
69  }
70
71  virtual bool writeGraphToGML(const std::string& filePath) {
72  if (vertexCoordinates.size() == 0 || vertexCoordinates[0].getDimensions() < 2 || vertexCoordinates[0].getDimensions() > 3) return false;
73  count dim = vertexCoordinates[0].getDimensions();
74  std::ofstream file(filePath);
75  Aux::enforceOpened(file);
76
77  file << "graph [\n";
78  if (G.isDirected()) {
79  file << " directed 1\n";
80  }
81
82  G.forNodes([&](node u) {
83  file << " node [\n";
84  file << " id " << u << "\n";
85  file << " graphics\n";
86  file << " [ x " << 50*vertexCoordinates[u][0] << "\n";
87  file << " y " << 50*vertexCoordinates[u][1] << "\n";
88  if (dim == 3) {
89  file << " z " << vertexCoordinates[u][2] << "\n";
90  }
91  file << " ]\n";
92  file << " ]\n";
93  });
94
95  G.forEdges([&](node u, node v) {
96  file << " edge [\n";
97  file << " source "<< u << "\n";
98  file << " target "<< v << "\n";
99  file << " ]\n";
100  });
101  file << "]\n";
102
103  file.close();
104
105  return true;
106  }
107
108  virtual bool writeKinemage(const std::string& filePath) {
109  if (vertexCoordinates.size() == 0 || vertexCoordinates[0].getDimensions() != 3) return false;
110  std::string fileName = filePath.substr(filePath.find_last_of("/"));
111  std::ofstream file(filePath);
112  Aux::enforceOpened(file);
113
114  file << "@whitebackground" << std::endl;
115  file << "@zoom 1.0" << std::endl;
116  file << "@zslab 240" << std::endl;
117  file << "@center 0 0 0" << std::endl;
118  file << "@master{points}" << std::endl;
119  file << "@group{" << fileName << "}" << std::endl;
120  file << "@balllist {a} color= blue master={points} radius= 0.05" << std::endl;
121
122  G.forNodes([&](node u) {
123  file << "{a}" << vertexCoordinates[u][0] << " " << vertexCoordinates[u][1] << " " << vertexCoordinates[u][2] << std::endl;
124  });
125
126  // edges
127  file << std::endl;
128  file << "@subgroup {edges} dominant" << std::endl;
129  file << "@vectorlist {edges} color= white" << std::endl;
130  G.forEdges([&](node u, node v) {
131  //if (u <= v) { // draw graph undirected
132  file << "P " << vertexCoordinates[u][0] << " " << vertexCoordinates[u][1] << " " << vertexCoordinates[u][2] << std::endl;
133  file << vertexCoordinates[v][0] << " " << vertexCoordinates[v][1] << " " << vertexCoordinates[v][2] << std::endl;
134  //}
135  });
136
137  file << std::endl;
138
139  file.close();
140  return true;
141  }
142
143 protected:
144  const Graph& G;
145  std::vector<Point<T>> vertexCoordinates;
146 };
147
148 } /* namespace NetworKit */
149
150 #endif /* NETWORKIT_CPP_VIZ_GRAPHLAYOUTALGORITHM_H_ */
void forNodes(L handle) const
Iterate over all nodes of the graph and call handle (lambda closure).
Definition: Graph.h:1097
bool isDirected() const
Return true if this graph supports directed edges.
Definition: Graph.h:694
const Graph & G
Definition: GraphLayoutAlgorithm.h:144
void enforceOpened(const Stream &stream)
Checks that the provided fstream is opened and throws an exception otherwise.
Definition: Enforce.h:37
void forEdges(L handle) const
Iterate over all edges of the const graph and call handle (lambda closure).
Definition: Graph.h:1299
Formerly marked as deprecated: To take advantage of automatic mapping between C++ and Python data str...
Definition: Point.h:39
std::vector< Point< T > > vertexCoordinates
Definition: GraphLayoutAlgorithm.h:145
Abstract base class for algorithms that compute a layout of the Graph vertices in d-dimensional space...
Definition: GraphLayoutAlgorithm.h:26
virtual count numEdgeCrossings() const
Definition: GraphLayoutAlgorithm.h:37
virtual std::vector< Point< T > > getCoordinates() const
Definition: GraphLayoutAlgorithm.h:33
uint64_t count
Definition: Globals.h:21
index node
Definition: Globals.h:23
virtual ~GraphLayoutAlgorithm()=default
virtual bool writeGraphToGML(const std::string &filePath)
Definition: GraphLayoutAlgorithm.h:71
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
virtual bool writeKinemage(const std::string &filePath)
Definition: GraphLayoutAlgorithm.h:108
GraphLayoutAlgorithm(const Graph &G, count dim)
Definition: GraphLayoutAlgorithm.h:28
double edgeweight
Definition: Globals.h:24