Tulip  5.0.0
Large graphs analysis and drawing
minmaxproperty.cxx
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
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>
23 tlp::MinMaxProperty<nodeType, edgeType, propType>::MinMaxProperty(tlp::Graph* graph, const std::string& name, typename nodeType::RealType NodeMin,
24  typename nodeType::RealType NodeMax, typename edgeType::RealType EdgeMin, typename edgeType::RealType EdgeMax)
25  : AbstractProperty<nodeType, edgeType, propType>(graph, name), _nodeMin(NodeMin), _nodeMax(NodeMax), _edgeMin(EdgeMin), _edgeMax(EdgeMax), needGraphListener(false) {
26 }
27 
28 template<typename nodeType, typename edgeType, typename propType>
30  if(!graph) {
31  graph = this->propType::graph;
32  }
33 
34  unsigned int graphID = graph->getId();
35  MINMAX_MAP(nodeType)::const_iterator it = minMaxNode.find(graphID);
36 
37  if (it == minMaxNode.end())
38  return computeMinMaxNode(graph).first;
39 
40  return it->second.first;
41 }
42 
43 template<typename nodeType, typename edgeType, typename propType>
45  if(!graph) {
46  graph = this->propType::graph;
47  }
48 
49  unsigned int graphID = graph->getId();
50  MINMAX_MAP(nodeType)::const_iterator it = minMaxNode.find(graphID);
51 
52  if (it == minMaxNode.end())
53  return computeMinMaxNode(graph).second;
54 
55  return it->second.second;
56 }
57 
58 template<typename nodeType, typename edgeType, typename propType>
60  if(!graph) {
61  graph = this->propType::graph;
62  }
63 
64  unsigned int graphID = graph->getId();
65  MINMAX_MAP(edgeType)::const_iterator it = minMaxEdge.find(graphID);
66 
67  if (it == minMaxEdge.end())
68  return computeMinMaxEdge(graph).first;
69 
70  return it->second.first;
71 }
72 
73 template<typename nodeType, typename edgeType, typename propType>
75  if(!graph) {
76  graph = this->propType::graph;
77  }
78 
79  unsigned int graphID = graph->getId();
80  MINMAX_MAP(edgeType)::const_iterator it = minMaxEdge.find(graphID);
81 
82  if (it == minMaxEdge.end())
83  return computeMinMaxEdge(graph).second;
84 
85  return it->second.second;
86 }
87 
88 template<typename nodeType, typename edgeType, typename propType>
90  if(!graph) {
91  graph = this->propType::graph;
92  }
93 
94  typename nodeType::RealType maxN2 = _nodeMin, minN2 = _nodeMax;
95 
98  else {
99  Iterator<node>* nodeIterator = graph->getNodes();
100 
101  while (nodeIterator->hasNext()) {
102  node n=nodeIterator->next();
103  typename nodeType::RealType tmp = this->getNodeValue(n);
104 
105  if (tmp > maxN2) {
106  maxN2 = tmp;
107  }
108 
109  if (tmp < minN2) {
110  minN2 = tmp;
111  }
112  }
113 
114  delete nodeIterator;
115 
116  // be careful to empty graph
117  if (maxN2 < minN2)
118  minN2 = maxN2;
119  }
120 
121  unsigned int sgi = graph->getId();
122 
123  // graph observation is now delayed
124  // until we need to do some minmax computation
125  // this will minimize the graph loading
126  if (minMaxNode.find(sgi) == minMaxNode.end() &&
127  minMaxEdge.find(sgi) == minMaxEdge.end()) {
128  // launch graph hierarchy observation
129  graph->addListener(this);
130  }
131 
132  MINMAX_PAIR(nodeType) minmax(minN2, maxN2);
133  return minMaxNode[sgi] = minmax;
134 }
135 
136 template<typename nodeType, typename edgeType, typename propType>
138  typename edgeType::RealType maxE2 = _edgeMin, minE2 = _edgeMax;
139 
142  else {
143  Iterator<edge>* edgeIterator = graph->getEdges();
144 
145  while (edgeIterator->hasNext()) {
146  edge ite=edgeIterator->next();
147  typename edgeType::RealType tmp = this->getEdgeValue(ite);
148 
149  if (tmp>maxE2)
150  maxE2 = tmp;
151 
152  if (tmp<minE2)
153  minE2 = tmp;
154  }
155 
156  delete edgeIterator;
157 
158  // be careful to no edges graph
159  if (maxE2 < minE2)
160  minE2 = maxE2;
161  }
162 
163  unsigned int sgi = graph->getId();
164 
165  // graph observation is now delayed
166  // until we need to do some minmax computation
167  // this will minimize the graph loading time
168  if (minMaxNode.find(sgi) == minMaxNode.end() &&
169  minMaxEdge.find(sgi) == minMaxEdge.end()) {
170  // launch graph hierarchy observation
171  graph->addListener(this);
172  }
173 
174  MINMAX_PAIR(edgeType) minmax(minE2, maxE2);
175  return minMaxEdge[sgi] = minmax;
176 }
177 
178 template<typename nodeType, typename edgeType, typename propType>
180  // we need to clear one of our map
181  // this will invalidate some minmax computations
182  // so the graphs corresponding to these cleared minmax computations
183  // may not have to be longer observed if they have no validated
184  // minmax computation in the other map
185 
186  // loop to remove unneeded graph observation
187  // it is the case if minmax computation
188  //
189  MINMAX_MAP(nodeType)::const_iterator it = minMaxNode.begin();
190  MINMAX_MAP(nodeType)::const_iterator ite = minMaxNode.end();
191 
192  for(; it != ite; ++it) {
193  unsigned int gi = it->first;
194  MINMAX_MAP(edgeType)::const_iterator itg = minMaxEdge.find(gi);
195 
196  if (itg == minMaxEdge.end()) {
197  // no computation in the other map
198  // we can stop observing the current graph
199  Graph* g =
200  (propType::graph->getId() == gi) ?
201  (needGraphListener ? NULL : propType::graph) :
202  propType::graph->getDescendantGraph(gi);
203 
204  if (g)
205  g->removeListener(this);
206  }
207  }
208 
209  // finally clear the map
210  minMaxNode.clear();
211 }
212 
213 template<typename nodeType, typename edgeType, typename propType>
215  // we need to clear one of our map
216  // this will invalidate some minmax computations
217  // so the graphs corresponding to these cleared minmax computations
218  // may not have to be longer observed if they have no validated
219  // minmax computation in the other map
220 
221  // loop to remove unneeded graph observation
222  // it is the case if minmax computation
223  //
224  MINMAX_MAP(edgeType)::const_iterator it = minMaxEdge.begin();
225  MINMAX_MAP(edgeType)::const_iterator ite = minMaxEdge.end();
226 
227  for(; it != ite; ++it) {
228  unsigned int gi = it->first;
229  MINMAX_MAP(nodeType)::const_iterator itg = minMaxNode.find(gi);
230 
231  if (itg == minMaxNode.end()) {
232  // no computation in the other map
233  // we can stop observing the current graph
234  Graph* g =
235  (propType::graph->getId() == gi) ?
236  (needGraphListener ? NULL : propType::graph) :
237  propType::graph->getDescendantGraph(gi);
238 
239  if (g)
240  g->removeListener(this);
241  }
242  }
243 
244  // finally clear the map
245  minMaxEdge.clear();
246 }
247 
248 template<typename nodeType, typename edgeType, typename propType>
250  MINMAX_MAP(nodeType)::const_iterator it = minMaxNode.begin();
251 
252  if (it != minMaxNode.end()) {
253  typename nodeType::RealType oldV = this->getNodeValue(n);
254 
255  if (newValue != oldV) {
256  // loop on subgraph min/max
257  for(; it != minMaxNode.end(); ++it) {
258  // if min/max is ok for the current subgraph
259  // check if min or max has to be updated
260  typename nodeType::RealType minV = it->second.first;
261  typename nodeType::RealType maxV = it->second.second;
262 
263  // check if min or max has to be updated
264  if ((newValue < minV) || (newValue > maxV) || (oldV == minV) || (oldV == maxV)) {
265  removeListenersAndClearNodeMap();
266  break;
267  }
268  }
269  }
270  }
271 }
272 
273 template<typename nodeType, typename edgeType, typename propType>
275  MINMAX_MAP(edgeType)::const_iterator it = minMaxEdge.begin();
276 
277  if (it != minMaxEdge.end()) {
278  typename edgeType::RealType oldV = this->getEdgeValue(e);
279 
280  if (newValue != oldV) {
281  // loop on subgraph min/max
282  for(; it != minMaxEdge.end(); ++it) {
283  // if min/max is ok for the current subgraph
284  // check if min or max has to be updated
285  typename edgeType::RealType minV = it->second.first;
286  typename edgeType::RealType maxV = it->second.second;
287 
288  // check if min or max has to be updated
289  if ((newValue < minV) || (newValue > maxV) || (oldV == minV) || (oldV == maxV)) {
290  removeListenersAndClearEdgeMap();
291  break;
292  }
293  }
294  }
295  }
296 }
297 
298 template<typename nodeType, typename edgeType, typename propType>
300  MINMAX_MAP(nodeType)::const_iterator it = minMaxNode.begin();
301  // loop on subgraph min/max
302  MINMAX_PAIR(nodeType) minmax(newValue, newValue);
303 
304  for(; it != minMaxNode.end(); ++it) {
305  unsigned int gid = it->first;
306  minMaxNode[gid] = minmax;
307  }
308 }
309 
310 template<typename nodeType, typename edgeType, typename propType>
312  MINMAX_MAP(edgeType)::const_iterator it = minMaxEdge.begin();
313  // loop on subgraph min/max
314  MINMAX_PAIR(edgeType) minmax(newValue, newValue);
315 
316  for(; it != minMaxEdge.end(); ++it) {
317  unsigned int gid = it->first;
318  minMaxEdge[gid] = minmax;
319  }
320 }
321 
322 template<typename nodeType, typename edgeType, typename propType>
324  const GraphEvent* graphEvent = dynamic_cast<const tlp::GraphEvent*>(&ev);
325 
326  if (graphEvent) {
327  tlp::Graph* graph = graphEvent->getGraph();
328 
329  switch(graphEvent->getType()) {
330  case GraphEvent::TLP_ADD_NODE:
331  removeListenersAndClearNodeMap();
332  break;
333 
334  case GraphEvent::TLP_DEL_NODE: {
335  unsigned int sgi = graph->getId();
336  MINMAX_MAP(nodeType)::iterator it = minMaxNode.find(sgi);
337 
338  if (it != minMaxNode.end()) {
339  typename nodeType::RealType oldV =
340  this->getNodeValue(graphEvent->getNode());
341 
342  // check if min or max has to be updated
343  if ((oldV == it->second.first) || (oldV == it->second.second)) {
344  minMaxNode.erase(it);
345 
346  if ((minMaxEdge.find(sgi) == minMaxEdge.end()) &&
347  (!needGraphListener || (graph != propType::graph)))
348  // graph observation is no longer needed
349  graph->removeListener(this);
350  }
351  }
352 
353  break;
354  }
355 
356  case GraphEvent::TLP_ADD_EDGE:
357  removeListenersAndClearEdgeMap();
358  break;
359 
360  case GraphEvent::TLP_DEL_EDGE: {
361  unsigned int sgi = graph->getId();
362  MINMAX_MAP(edgeType)::iterator it = minMaxEdge.find(sgi);
363 
364  if (it != minMaxEdge.end()) {
365  typename edgeType::RealType oldV =
366  this->getEdgeValue(graphEvent->getEdge());
367 
368  // check if min or max has to be updated
369  if ((oldV == it->second.first) || (oldV == it->second.second)) {
370  minMaxEdge.erase(it);
371 
372  if ((minMaxNode.find(sgi) == minMaxNode.end()) &&
373  (!needGraphListener || (graph != propType::graph)))
374  // graph observation is no longer needed
375  graph->removeListener(this);
376  }
377  }
378 
379  break;
380  }
381 
382  default:
383  // we don't care about the rest
384  break;
385  }
386  }
387 }
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 Iterator< edge > * getEdges() const =0
Get an iterator over all the graph&#39;s edges.
virtual Graph * getDescendantGraph(unsigned int id) const =0
Returns a pointer on the descendant with the corresponding id or NULL if there is no descendant with ...
nodeType::RealType getNodeMin(const Graph *graph=NULL)
Gets the minimum value on the nodes. It is only computed if it has never been retrieved before...
nodeType::RealType getNodeMax(const Graph *graph=NULL)
Computes the maximum 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:39
The node struct represents a node in a Graph object.
Definition: Node.h:39
virtual Iterator< node > * getNodes() const =0
Gets an iterator over this graph&#39;s nodes.
Event is the base class for all events used in the Observation mechanism.
Definition: Observable.h:47
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:1012
edgeType::RealType getEdgeMin(const Graph *graph=NULL)
Computes the minimum value on the edges. It is only computed if it has never been retrieved before...
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.
edgeType::RealType getEdgeMax(const Graph *graph=NULL)
Computes the maximum value on the edges. It is only computed if it has never been retrieved before...