Tulip  5.7.4
Large graphs analysis and drawing
SortIterator.h
1 /*
2  *
3  * This file is part of Tulip (https://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 
20 #ifndef TULIP_SORTITERATOR_H
21 #define TULIP_SORTITERATOR_H
22 
23 #include <vector>
24 #include <algorithm>
25 
26 #include <tulip/Iterator.h>
27 #include <tulip/StableIterator.h>
28 #include <tulip/NumericProperty.h>
29 #include <tulip/Graph.h>
30 #include <tulip/Vector.h>
31 
32 namespace tlp {
33 class Graph;
34 
35 ///@cond DOXYGEN_HIDDEN
36 struct LessThan {
37  LessThan(const tlp::NumericProperty *m) : metric(m) {}
38  const tlp::NumericProperty *metric;
39  bool operator()(const node &n1, const node &n2) const {
40  return (metric->getNodeDoubleValue(n1) < metric->getNodeDoubleValue(n2));
41  }
42  bool operator()(const edge &e1, const edge &e2) const {
43  return (metric->getEdgeDoubleValue(e1) < metric->getEdgeDoubleValue(e2));
44  }
45 };
46 
47 struct LessThanEdgeTargetMetric {
48  LessThanEdgeTargetMetric(const Graph *sg, const tlp::NumericProperty *metric)
49  : metric(metric), sg(sg) {}
50  bool operator()(const edge &e1, const edge &e2) const {
51  return (metric->getNodeDoubleValue(sg->target(e1)) <
52  metric->getNodeDoubleValue(sg->target(e2)));
53  }
54 
55 private:
56  const tlp::NumericProperty *metric;
57  const Graph *sg;
58 };
59 
60 struct LessThanEdgeSourceMetric {
61  LessThanEdgeSourceMetric(const Graph *sg, const tlp::NumericProperty *metric)
62  : metric(metric), sg(sg) {}
63  bool operator()(const edge &e1, const edge &e2) const {
64  return (metric->getNodeDoubleValue(sg->source(e1)) <
65  metric->getNodeDoubleValue(sg->source(e2)));
66  }
67 
68 private:
69  const tlp::NumericProperty *metric;
70  const Graph *sg;
71 };
72 
73 struct LessThanEdgeExtremitiesMetric {
74  LessThanEdgeExtremitiesMetric(const Graph *sg, const tlp::NumericProperty *metric)
75  : metric(metric), sg(sg) {}
76  bool operator()(const edge &e1, const edge &e2) const {
77  std::pair<node, node> ends = sg->ends(e1);
78  Vec2d v1(metric->getNodeDoubleValue(ends.first), metric->getNodeDoubleValue(ends.second));
79  ends = sg->ends(e2);
80  Vec2d v2(metric->getNodeDoubleValue(ends.first), metric->getNodeDoubleValue(ends.second));
81  return v1 < v2;
82  }
83 
84 private:
85  const tlp::NumericProperty *metric;
86  const Graph *sg;
87 };
88 ///@endcond
89 
90 /**
91  * @brief This Iterator sorts the nodes in a sequence based on their values in a NumericProperty.
92  **/
93 struct SortNodeIterator : public StableIterator<tlp::node> {
94 
96  bool ascendingOrder = true)
98  LessThan tmp(metric);
99  sort(sequenceCopy.begin(), sequenceCopy.end(), tmp);
100 
101  if (!ascendingOrder) {
102  reverse(sequenceCopy.begin(), sequenceCopy.end());
103  }
104 
105  copyIterator = sequenceCopy.begin();
106  }
107 
108  ~SortNodeIterator() override {}
109 };
110 
111 /**
112  * @brief This Iterator sorts the edges in a sequence based on their values in a NumericProperty.
113  **/
114 struct SortEdgeIterator : public StableIterator<tlp::edge> {
115 
117  bool ascendingOrder = true)
118  : StableIterator<tlp::edge>(itIn) {
119  LessThan tmp(metric);
120  sort(sequenceCopy.begin(), sequenceCopy.end(), tmp);
121 
122  if (!ascendingOrder) {
123  reverse(sequenceCopy.begin(), sequenceCopy.end());
124  }
125 
126  copyIterator = sequenceCopy.begin();
127  }
128 
129  ~SortEdgeIterator() override {}
130 };
131 
132 /**
133  * @brief This Iterator sorts the edges based on the values of their target nodes in a
134  *NumericProperty.
135  **/
136 struct SortTargetEdgeIterator : public StableIterator<tlp::edge> {
137 
139  const tlp::NumericProperty *metric, bool ascendingOrder = true)
140  : StableIterator<tlp::edge>(itIn) {
141  LessThanEdgeTargetMetric tmp(sg, metric);
142  sort(sequenceCopy.begin(), sequenceCopy.end(), tmp);
143 
144  if (!ascendingOrder) {
145  reverse(sequenceCopy.begin(), sequenceCopy.end());
146  }
147 
148  copyIterator = sequenceCopy.begin();
149  }
150 
151  ~SortTargetEdgeIterator() override {}
152 };
153 
154 /**
155  * @brief This Iterator sorts the edges based on the values of their source nodes in a
156  *NumericProperty.
157  **/
158 struct SortSourceEdgeIterator : public StableIterator<tlp::edge> {
159 
161  const tlp::NumericProperty *metric, bool ascendingOrder = true)
162  : StableIterator<tlp::edge>(itIn) {
163  LessThanEdgeSourceMetric tmp(sg, metric);
164  sort(sequenceCopy.begin(), sequenceCopy.end(), tmp);
165 
166  if (!ascendingOrder) {
167  reverse(sequenceCopy.begin(), sequenceCopy.end());
168  }
169 
170  copyIterator = sequenceCopy.begin();
171  }
172 
173  ~SortSourceEdgeIterator() override {}
174 };
175 
176 /**
177  * @brief This Iterator sorts the edges based on the values of their extremities nodes in a
178  *NumericProperty.
179  **/
180 struct SortExtremitiesEdgeIterator : public StableIterator<tlp::edge> {
181 
183  const tlp::NumericProperty *metric, bool ascendingOrder = true)
184  : StableIterator<tlp::edge>(itIn) {
185  LessThanEdgeExtremitiesMetric tmp(sg, metric);
186  sort(sequenceCopy.begin(), sequenceCopy.end(), tmp);
187 
188  if (!ascendingOrder) {
189  reverse(sequenceCopy.begin(), sequenceCopy.end());
190  }
191 
192  copyIterator = sequenceCopy.begin();
193  }
194 
195  ~SortExtremitiesEdgeIterator() override {}
196 };
197 
198 /**
199  * @class SortIterator
200  * @ingroup Iterators
201  * @brief Iterator that wraps an existing one and sorts its iterated elements based on comparison
202  *function.
203  * @since Tulip 5.2
204  * @param it the iterator to sort
205  * @param comp functor or lambda function taking two parameters of type const T& and returning a
206  * Boolean:
207  * true if the first parameter is lesser or equal than the second one, false otherwise
208  *
209  **/
210 template <typename T, typename CompareFunction>
211 struct SortIterator : public tlp::StableIterator<T> {
212 
213  SortIterator(Iterator<T> *itIn, CompareFunction &&compFunc) : StableIterator<T>(itIn) {
214  sort(this->sequenceCopy.begin(), this->sequenceCopy.end(), compFunc);
215  this->copyIterator = this->sequenceCopy.begin();
216  }
217 
218  ~SortIterator() {}
219 };
220 
221 /**
222  * @brief Convenient function for creating a SortIterator.
223  * @ingroup Iterators
224  *
225  * @since Tulip 5.2
226  *
227  * Creates a SortIterator from another Iterator and a comparison function.
228  * The returned Iterator takes ownership of the one provided as parameter.
229  *
230  * @param it a Tulip Iterator
231  * @param compFunc functor or lambda function taking two parameters of type const T& and returning a
232  * Boolean:
233  * true if the first parameter is lesser or equal than the second one, false otherwise
234  *
235  * @return a SortIterator
236  *
237  **/
238 template <typename T, typename CompareFunction>
239 inline SortIterator<T, CompareFunction> *sortIterator(Iterator<T> *it, CompareFunction &&compFunc) {
240  return new SortIterator<T, CompareFunction>(it, compFunc);
241 }
242 
243 /**
244  * @brief Convenient function for creating a SortIterator from a STL container.
245  * @ingroup Iterators
246  *
247  * @since Tulip 5.2
248  *
249  * Creates a SortIterator from another Iterator and a comparison function.
250  *
251  * @param stlContainer any STL container
252  * @param compFunc functor or lambda function taking two parameters of type const T& and returning a
253  * Boolean:
254  * true if the first parameter is lesser or equal than the second one, false otherwise
255  *
256  * @return a SortIterator
257  *
258  **/
259 template <typename Container, typename CompareFunction>
260 typename std::enable_if<has_const_iterator<Container>::value,
261  SortIterator<typename Container::value_type, CompareFunction>
262  *>::type inline sortIterator(const Container &stlContainer,
263  CompareFunction &&compFunc) {
265  stlIterator(stlContainer), compFunc);
266 }
267 } // namespace tlp
268 #endif
Interface all numerical properties. Property values are always returned as double.
virtual double getEdgeDoubleValue(const edge e) const =0
Returns the value associated with the edge e in this property.
virtual double getNodeDoubleValue(const node n) const =0
Returns the value associated with the node n in this property.
std::enable_if< has_const_iterator< Container >::value, StlIterator< typename Container::value_type, typename Container::const_iterator > * >::type stlIterator(const Container &stlContainer)
Convenient function for creating a StlIterator from a stl container.
Definition: StlIterator.h:95
SortIterator< T, CompareFunction > * sortIterator(Iterator< T > *it, CompareFunction &&compFunc)
Convenient function for creating a SortIterator.
Definition: SortIterator.h:239
Interface for Tulip iterators. Allows basic iteration operations only.
Definition: Iterator.h:74
This Iterator sorts the edges in a sequence based on their values in a NumericProperty.
Definition: SortIterator.h:114
This Iterator sorts the edges based on the values of their extremities nodes in a NumericProperty.
Definition: SortIterator.h:180
Iterator that wraps an existing one and sorts its iterated elements based on comparison function.
Definition: SortIterator.h:211
This Iterator sorts the nodes in a sequence based on their values in a NumericProperty.
Definition: SortIterator.h:93
This Iterator sorts the edges based on the values of their source nodes in a NumericProperty.
Definition: SortIterator.h:158
This Iterator sorts the edges based on the values of their target nodes in a NumericProperty.
Definition: SortIterator.h:136
Stores the elements of an iterator and iterates a copy.
std::vector< tlp::node >::const_iterator copyIterator
STL const_iterator on the cloned sequence.
std::vector< tlp::node > sequenceCopy
A copy of the sequence of the elements to iterate.