Tulip  5.2.0
Large graphs analysis and drawing
minmaxproperty.cxx
1 /*
2  *
3  * This file is part of Tulip (http://tulip.labri.fr)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 #include <tulip/Graph.h>
20 #include <tulip/Coord.h>
21 
22 template <typename nodeType, typename edgeType, typename propType>
24  tlp::Graph *graph, const std::string &name, typename nodeType::RealType NodeMin,
25  typename nodeType::RealType NodeMax, typename edgeType::RealType EdgeMin,
26  typename edgeType::RealType EdgeMax)
27  : AbstractProperty<nodeType, edgeType, propType>(graph, name), _nodeMin(NodeMin),
28  _nodeMax(NodeMax), _edgeMin(EdgeMin), _edgeMax(EdgeMax), needGraphListener(false) {}
29 
30 template <typename nodeType, typename edgeType, typename propType>
31 typename nodeType::RealType
33  if (!graph) {
34  graph = this->propType::graph;
35  }
36 
37  unsigned int graphID = graph->getId();
38  auto it = minMaxNode.find(graphID);
39 
40  if (it == minMaxNode.end())
41  return computeMinMaxNode(graph).first;
42 
43  return it->second.first;
44 }
45 
46 template <typename nodeType, typename edgeType, typename propType>
47 typename nodeType::RealType
49  if (!graph) {
50  graph = this->propType::graph;
51  }
52 
53  unsigned int graphID = graph->getId();
54  auto it = minMaxNode.find(graphID);
55 
56  if (it == minMaxNode.end())
57  return computeMinMaxNode(graph).second;
58 
59  return it->second.second;
60 }
61 
62 template <typename nodeType, typename edgeType, typename propType>
63 typename edgeType::RealType
65  if (!graph) {
66  graph = this->propType::graph;
67  }
68 
69  unsigned int graphID = graph->getId();
70  auto it = minMaxEdge.find(graphID);
71 
72  if (it == minMaxEdge.end())
73  return computeMinMaxEdge(graph).first;
74 
75  return it->second.first;
76 }
77 
78 template <typename nodeType, typename edgeType, typename propType>
79 typename edgeType::RealType
81  if (!graph) {
82  graph = this->propType::graph;
83  }
84 
85  unsigned int graphID = graph->getId();
86  auto it = minMaxEdge.find(graphID);
87 
88  if (it == minMaxEdge.end())
89  return computeMinMaxEdge(graph).second;
90 
91  return it->second.second;
92 }
93 
94 template <typename nodeType, typename edgeType, typename propType>
95 MINMAX_PAIR(nodeType)
97  if (!graph) {
98  graph = this->propType::graph;
99  }
100 
101  typename nodeType::RealType maxN2 = _nodeMin, minN2 = _nodeMax;
102 
104  for (auto n : graph->nodes()) {
105  typename nodeType::RealType tmp = this->getNodeValue(n);
106 
107  if (tmp > maxN2) {
108  maxN2 = tmp;
109  }
110 
111  if (tmp < minN2) {
112  minN2 = tmp;
113  }
114  }
115  }
116 
117  if (maxN2 < minN2)
119 
120  unsigned int sgi = graph->getId();
121 
122  // graph observation is now delayed
123  // until we need to do some minmax computation
124  // this will minimize the graph loading
125  if (minMaxNode.find(sgi) == minMaxNode.end() && minMaxEdge.find(sgi) == minMaxEdge.end()) {
126  // launch graph hierarchy observation
127  graph->addListener(this);
128  }
129 
130  MINMAX_PAIR(nodeType) minmax(minN2, maxN2);
131  return minMaxNode[sgi] = minmax;
132 }
133 
134 template <typename nodeType, typename edgeType, typename propType>
135 MINMAX_PAIR(edgeType)
137  typename edgeType::RealType maxE2 = _edgeMin, minE2 = _edgeMax;
138 
140  for (auto ite : graph->edges()) {
141  typename edgeType::RealType tmp = this->getEdgeValue(ite);
142 
143  if (tmp > maxE2)
144  maxE2 = tmp;
145 
146  if (tmp < minE2)
147  minE2 = tmp;
148  }
149  }
150 
151  if (maxE2 < minE2)
153 
154  unsigned int sgi = graph->getId();
155 
156  // graph observation is now delayed
157  // until we need to do some minmax computation
158  // this will minimize the graph loading time
159  if (minMaxNode.find(sgi) == minMaxNode.end() && minMaxEdge.find(sgi) == minMaxEdge.end()) {
160  // launch graph hierarchy observation
161  graph->addListener(this);
162  }
163 
164  MINMAX_PAIR(edgeType) minmax(minE2, maxE2);
165  return minMaxEdge[sgi] = minmax;
166 }
167 
168 template <typename nodeType, typename edgeType, typename propType>
170  // we need to clear one of our map
171  // this will invalidate some minmax computations
172  // so the graphs corresponding to these cleared minmax computations
173  // may not have to be longer observed if they have no validated
174  // minmax computation in the other map
175 
176  // loop to remove unneeded graph observation
177  // it is the case if minmax computation
178  //
179  auto it = minMaxNode.begin();
180  auto ite = minMaxNode.end();
181 
182  for (; it != ite; ++it) {
183  unsigned int gi = it->first;
184  auto itg = minMaxEdge.find(gi);
185 
186  if (itg == minMaxEdge.end()) {
187  // no computation in the other map
188  // we can stop observing the current graph
189  Graph *g = (propType::graph->getId() == gi) ? (needGraphListener ? nullptr : propType::graph)
190  : propType::graph->getDescendantGraph(gi);
191 
192  if (g)
193  g->removeListener(this);
194  }
195  }
196 
197  // finally clear the map
198  minMaxNode.clear();
199 }
200 
201 template <typename nodeType, typename edgeType, typename propType>
203  // we need to clear one of our map
204  // this will invalidate some minmax computations
205  // so the graphs corresponding to these cleared minmax computations
206  // may not have to be longer observed if they have no validated
207  // minmax computation in the other map
208 
209  // loop to remove unneeded graph observation
210  // it is the case if minmax computation
211  //
212  auto it = minMaxEdge.begin();
213  auto ite = minMaxEdge.end();
214 
215  for (; it != ite; ++it) {
216  unsigned int gi = it->first;
217  auto itg = minMaxNode.find(gi);
218 
219  if (itg == minMaxNode.end()) {
220  // no computation in the other map
221  // we can stop observing the current graph
222  Graph *g = (propType::graph->getId() == gi) ? (needGraphListener ? nullptr : propType::graph)
223  : propType::graph->getDescendantGraph(gi);
224 
225  if (g)
226  g->removeListener(this);
227  }
228  }
229 
230  // finally clear the map
231  minMaxEdge.clear();
232 }
233 
234 template <typename nodeType, typename edgeType, typename propType>
236  tlp::node n, typename nodeType::RealType newValue) {
237  auto it = minMaxNode.begin();
238 
239  if (it != minMaxNode.end()) {
240  typename nodeType::RealType oldV = this->getNodeValue(n);
241 
242  if (newValue != oldV) {
243  // loop on subgraph min/max
244  for (; it != minMaxNode.end(); ++it) {
245  // if min/max is ok for the current subgraph
246  // check if min or max has to be updated
247  typename nodeType::RealType minV = it->second.first;
248  typename nodeType::RealType maxV = it->second.second;
249 
250  // check if min or max has to be updated
251  if ((newValue < minV) || (newValue > maxV) || (oldV == minV) || (oldV == maxV)) {
252  removeListenersAndClearNodeMap();
253  break;
254  }
255  }
256  }
257  }
258 }
259 
260 template <typename nodeType, typename edgeType, typename propType>
262  tlp::edge e, typename edgeType::RealType newValue) {
263  auto it = minMaxEdge.begin();
264 
265  if (it != minMaxEdge.end()) {
266  typename edgeType::RealType oldV = this->getEdgeValue(e);
267 
268  if (newValue != oldV) {
269  // loop on subgraph min/max
270  for (; it != minMaxEdge.end(); ++it) {
271  // if min/max is ok for the current subgraph
272  // check if min or max has to be updated
273  typename edgeType::RealType minV = it->second.first;
274  typename edgeType::RealType maxV = it->second.second;
275 
276  // check if min or max has to be updated
277  if ((newValue < minV) || (newValue > maxV) || (oldV == minV) || (oldV == maxV)) {
278  removeListenersAndClearEdgeMap();
279  break;
280  }
281  }
282  }
283  }
284 }
285 
286 template <typename nodeType, typename edgeType, typename propType>
288  typename nodeType::RealType newValue) {
289  auto it = minMaxNode.begin();
290  // loop on subgraph min/max
291  MINMAX_PAIR(nodeType) minmax(newValue, newValue);
292 
293  for (; it != minMaxNode.end(); ++it) {
294  unsigned int gid = it->first;
295  minMaxNode[gid] = minmax;
296  }
297 }
298 
299 template <typename nodeType, typename edgeType, typename propType>
301  typename edgeType::RealType newValue) {
302  auto it = minMaxEdge.begin();
303  // loop on subgraph min/max
304  MINMAX_PAIR(edgeType) minmax(newValue, newValue);
305 
306  for (; it != minMaxEdge.end(); ++it) {
307  unsigned int gid = it->first;
308  minMaxEdge[gid] = minmax;
309  }
310 }
311 
312 template <typename nodeType, typename edgeType, typename propType>
314  const GraphEvent *graphEvent = dynamic_cast<const tlp::GraphEvent *>(&ev);
315 
316  if (graphEvent) {
317  tlp::Graph *graph = graphEvent->getGraph();
318 
319  switch (graphEvent->getType()) {
320  case GraphEvent::TLP_ADD_NODE:
321  removeListenersAndClearNodeMap();
322  break;
323 
324  case GraphEvent::TLP_DEL_NODE: {
325  unsigned int sgi = graph->getId();
326  auto it = minMaxNode.find(sgi);
327 
328  if (it != minMaxNode.end()) {
329  typename nodeType::RealType oldV = this->getNodeValue(graphEvent->getNode());
330 
331  // check if min or max has to be updated
332  if ((oldV == it->second.first) || (oldV == it->second.second)) {
333  minMaxNode.erase(it);
334 
335  if ((minMaxEdge.find(sgi) == minMaxEdge.end()) &&
336  (!needGraphListener || (graph != propType::graph)))
337  // graph observation is no longer needed
338  graph->removeListener(this);
339  }
340  }
341 
342  break;
343  }
344 
345  case GraphEvent::TLP_ADD_EDGE:
346  removeListenersAndClearEdgeMap();
347  break;
348 
349  case GraphEvent::TLP_DEL_EDGE: {
350  unsigned int sgi = graph->getId();
351  auto it = minMaxEdge.find(sgi);
352 
353  if (it != minMaxEdge.end()) {
354  typename edgeType::RealType oldV = this->getEdgeValue(graphEvent->getEdge());
355 
356  // check if min or max has to be updated
357  if ((oldV == it->second.first) || (oldV == it->second.second)) {
358  minMaxEdge.erase(it);
359 
360  if ((minMaxNode.find(sgi) == minMaxNode.end()) &&
361  (!needGraphListener || (graph != propType::graph)))
362  // graph observation is no longer needed
363  graph->removeListener(this);
364  }
365  }
366 
367  break;
368  }
369 
370  default:
371  // we don't care about the rest
372  break;
373  }
374  }
375 }
This class extends upon PropertyInterface, and adds type-safe methods to get and set the node and edg...
Abstracts the computation of minimal and maximal values on node and edge values of properties...
tlp::StoredType< typename nodeType::RealType >::ReturnedConstValue getNodeValue(const node n) const
Returns the value associated with the node n in this property. If there is no value, it returns the default node value.
void updateAllNodesValues(typename nodeType::RealType newValue)
Updates the value of all nodes, setting the maximum and minimum values to this. Should be called by s...
MinMaxProperty(tlp::Graph *graph, const std::string &name, typename nodeType::RealType NodeMin, typename nodeType::RealType NodeMax, typename edgeType::RealType EdgeMin, typename edgeType::RealType EdgeMax)
Constructs a MinMaxProperty.
virtual Graph * getDescendantGraph(unsigned int id) const =0
Returns a pointer on the descendant with the corresponding id or nullptr if there is no descendant wi...
edgeType::RealType getEdgeMax(const Graph *graph=nullptr)
Computes the maximum value on the edges. It is only computed if it has never been retrieved before...
virtual const std::vector< edge > & edges() const =0
Return a const reference on the vector of edges of the graph It is the fastest way to access to edges...
virtual const std::vector< node > & nodes() const =0
Return a const reference on the vector of nodes of the graph It is the fastest way to access to nodes...
nodeType::RealType getNodeMin(const Graph *graph=nullptr)
Gets the minimum value on the nodes. It is only computed if it has never been retrieved before...
void addListener(Observable *const listener) const
Adds a Listener to this object.
The edge struct represents an edge in a Graph object.
Definition: Edge.h:40
The node struct represents a node in a Graph object.
Definition: Node.h:40
nodeType::RealType getNodeMax(const Graph *graph=nullptr)
Computes the maximum value on the nodes. It is only computed if it has never been retrieved before...
edgeType::RealType getEdgeMin(const Graph *graph=nullptr)
Computes the minimum value on the edges. It is only computed if it has never been retrieved before...
Event is the base class for all events used in the Observation mechanism.
Definition: Observable.h:51
void removeListener(Observable *const listener) const
Removes a listener from this object.
tlp::StoredType< typename edgeType::RealType >::ReturnedConstValue getEdgeValue(const edge e) const
Returns the value associated to the edge e in this property. If there is no value, it returns the default edge value.
void updateAllEdgesValues(typename edgeType::RealType newValue)
Updates the value of all edges, setting the maximum and minimum values to this. Should be called by s...
void updateEdgeValue(tlp::edge e, typename edgeType::RealType newValue)
Updates the value on an edge, and updates the minimal/maximal cached values if necessary. Should be called by subclasses in order to keep the cache up to date.
unsigned int getId() const
Gets the unique identifier of the graph.
Definition: Graph.h:1073
void updateNodeValue(tlp::node n, typename nodeType::RealType newValue)
Updates the value on a node, and updates the minimal/maximal cached values if necessary. Should be called by subclasses in order to keep the cache up to date.