Tulip  5.5.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)
118  maxN2 = minN2 = AbstractProperty<nodeType, edgeType, propType>::nodeDefaultValue;
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)
152  maxE2 = minE2 = AbstractProperty<nodeType, edgeType, propType>::edgeDefaultValue;
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 }
tlp::AbstractProperty::hasNonDefaultValuatedNodes
bool hasNonDefaultValuatedNodes(const Graph *g=nullptr) const override
Returns whether the property has nodes with a non default value. When given a Graph as parameter,...
Definition: AbstractProperty.cxx:330
tlp::GraphEvent
Definition: Graph.h:1751
tlp::Graph
Definition: Graph.h:234
tlp::MinMaxProperty::treatEvent
void treatEvent(const tlp::Event &ev) override
This function is called when events are sent to the Listeners, and Listeners only.
Definition: minmaxproperty.cxx:313
tlp::Graph::getId
unsigned int getId() const
Gets the unique identifier of the graph.
Definition: Graph.h:1067
tlp::Observable::addListener
void addListener(Observable *const listener) const
Adds a Listener to this object.
tlp::Graph::nodes
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...
tlp::MinMaxProperty::updateEdgeValue
void updateEdgeValue(tlp::edge e, typename edgeType::RealType newValue)
Updates the value on an edge, and updates the minimal/maximal cached values if necessary....
Definition: minmaxproperty.cxx:261
tlp::MinMaxProperty::getNodeMax
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,...
Definition: minmaxproperty.cxx:48
tlp::MinMaxProperty::updateAllEdgesValues
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...
Definition: minmaxproperty.cxx:300
tlp::MinMaxProperty::updateAllNodesValues
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...
Definition: minmaxproperty.cxx:287
tlp::AbstractProperty
This class extends upon PropertyInterface, and adds type-safe methods to get and set the node and edg...
Definition: AbstractProperty.h:55
tlp::Event
Event is the base class for all events used in the Observation mechanism.
Definition: Observable.h:52
tlp::MinMaxProperty::getEdgeMin
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,...
Definition: minmaxproperty.cxx:64
tlp::AbstractProperty::hasNonDefaultValuatedEdges
bool hasNonDefaultValuatedEdges(const Graph *g=nullptr) const override
Returns whether the property has edges with a non default value. When given a Graph as parameter,...
Definition: AbstractProperty.cxx:402
tlp::MinMaxProperty::updateNodeValue
void updateNodeValue(tlp::node n, typename nodeType::RealType newValue)
Updates the value on a node, and updates the minimal/maximal cached values if necessary....
Definition: minmaxproperty.cxx:235
tlp::MinMaxProperty::getNodeMin
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,...
Definition: minmaxproperty.cxx:32
tlp::MinMaxProperty::MinMaxProperty
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.
Definition: minmaxproperty.cxx:23
tlp::MinMaxProperty::getEdgeMax
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,...
Definition: minmaxproperty.cxx:80
tlp::Observable::removeListener
void removeListener(Observable *const listener) const
Removes a listener from this object.
tlp::edge
The edge struct represents an edge in a Graph object.
Definition: Edge.h:40
tlp::node
The node struct represents a node in a Graph object.
Definition: Node.h:40
tlp::MinMaxProperty
Abstracts the computation of minimal and maximal values on node and edge values of properties.
Definition: minmaxproperty.h:41