Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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
32namespace tlp {
33class Graph;
34
35///@cond DOXYGEN_HIDDEN
36struct 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
47struct 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
55private:
56 const tlp::NumericProperty *metric;
57 const Graph *sg;
58};
59
60struct 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
68private:
69 const tlp::NumericProperty *metric;
70 const Graph *sg;
71};
72
73struct 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
84private:
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 **/
93struct 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 **/
114struct SortEdgeIterator : public StableIterator<tlp::edge> {
115
117 bool ascendingOrder = true)
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 **/
136struct SortTargetEdgeIterator : public StableIterator<tlp::edge> {
137
139 const tlp::NumericProperty *metric, bool ascendingOrder = true)
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 **/
158struct SortSourceEdgeIterator : public StableIterator<tlp::edge> {
159
161 const tlp::NumericProperty *metric, bool ascendingOrder = true)
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 **/
180struct SortExtremitiesEdgeIterator : public StableIterator<tlp::edge> {
181
183 const tlp::NumericProperty *metric, bool ascendingOrder = true)
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 **/
210template <typename T, typename CompareFunction>
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 **/
238template <typename T, typename CompareFunction>
239inline 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 **/
259template <typename Container, typename CompareFunction>
260typename 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< typenameContainer::value_type, typenameContainer::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.