Loading...
Searching...
No Matches
Edge.hh
Go to the documentation of this file.
1/*
2 * Copyright (C) 2017 Open Source Robotics Foundation
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *
16*/
17#ifndef IGNITION_MATH_GRAPH_EDGE_HH_
18#define IGNITION_MATH_GRAPH_EDGE_HH_
19
20// uint64_t
21#include <cstdint>
22#include <functional>
23#include <iostream>
24#include <map>
25#include <set>
26
27#include <ignition/math/config.hh>
29
30namespace ignition
31{
32namespace math
33{
34inline namespace IGNITION_MATH_VERSION_NAMESPACE
35{
36namespace graph
37{
40 using EdgeId = uint64_t;
41
43 template<typename E>
45 {
50 EdgeInitializer(const VertexId_P &_vertices,
51 const E &_data = E(),
52 const double _weight = 1)
53 : vertices(_vertices),
54 data(_data),
55 weight(_weight)
56 {
57 };
58
61
63 public: E data;
64
66 public: double weight = 1;
67 };
68
72 template<typename E>
73 class Edge
74 {
80 public: explicit Edge(const VertexId_P &_vertices,
81 const E &_data,
82 const double _weight,
83 const EdgeId &_id = kNullId)
84 : id(_id),
85 vertices(_vertices),
86 data(_data),
87 weight(_weight)
88 {
89 }
90
93 public: EdgeId Id() const
94 {
95 return this->id;
96 }
97
100 public: VertexId_P Vertices() const
101 {
102 if (!this->Valid())
103 return {kNullId, kNullId};
104
105 return this->vertices;
106 }
107
110 public: const E &Data() const
111 {
112 return this->data;
113 }
114
117 public: E &Data()
118 {
119 return this->data;
120 }
121
125 public: double Weight() const
126 {
127 return this->weight;
128 }
129
132 public: void SetWeight(const double _newWeight)
133 {
134 this->weight = _newWeight;
135 }
136
151 public: virtual VertexId From(const VertexId &_from) const = 0;
152
167 public: virtual VertexId To(const VertexId &_to) const = 0;
168
171 public: bool Valid() const
172 {
173 return this->id != kNullId;
174 }
175
177 private: EdgeId id = kNullId;
178
180 private: VertexId_P vertices;
181
183 private: E data;
184
187 private: double weight = 1.0;
188 };
189
192 using EdgeId_S = std::set<EdgeId>;
193
197 template<typename EdgeType>
198 using EdgeRef_M = std::map<EdgeId, std::reference_wrapper<const EdgeType>>;
199
203 template<typename E>
204 class UndirectedEdge : public Edge<E>
205 {
208
214 public: explicit UndirectedEdge(const VertexId_P &_vertices,
215 const E &_data,
216 const double _weight,
217 const EdgeId &_id = kNullId)
218 : Edge<E>(_vertices, _data, _weight, _id)
219 {
220 }
221
222 // Documentation inherited.
223 public: VertexId From(const VertexId &_from) const override
224 {
225 if (!this->Valid())
226 return kNullId;
227
228 if (this->Vertices().first != _from && this->Vertices().second != _from)
229 return kNullId;
230
231 if (this->Vertices().first == _from)
232 return this->Vertices().second;
233
234 return this->Vertices().first;
235 }
236
237 // Documentation inherited.
238 public: VertexId To(const VertexId &_to) const override
239 {
240 return this->From(_to);
241 }
242
248 public: friend std::ostream &operator<<(std::ostream &_out,
249 const UndirectedEdge<E> &_e)
250 {
251 auto vertices = _e.Vertices();
252 _out << " " << vertices.first << " -- " << vertices.second
253 << " [label=" << _e.Weight() << "];" << std::endl;
254 return _out;
255 }
256 };
257
259 template<typename E>
260 UndirectedEdge<E> UndirectedEdge<E>::NullEdge(
261 VertexId_P(kNullId, kNullId), E(), 1.0, kNullId);
262
266 template<typename E>
267 class DirectedEdge : public Edge<E>
268 {
270 public: static DirectedEdge<E> NullEdge;
271
277 public: explicit DirectedEdge(const VertexId_P &_vertices,
278 const E &_data,
279 const double _weight,
280 const EdgeId &_id = kNullId)
281 : Edge<E>(_vertices, _data, _weight, _id)
282 {
283 }
284
288 public: VertexId Tail() const
289 {
290 return this->Vertices().first;
291 }
292
296 public: VertexId Head() const
297 {
298 return this->Vertices().second;
299 }
300
301 // Documentation inherited.
302 public: VertexId From(const VertexId &_from) const override
303 {
304 if (_from != this->Tail())
305 return kNullId;
306
307 return this->Head();
308 }
309
310 // Documentation inherited.
311 public: VertexId To(const VertexId &_to) const override
312 {
313 if (_to != this->Head())
314 return kNullId;
315
316 return this->Tail();
317 }
318
324 public: friend std::ostream &operator<<(std::ostream &_out,
325 const DirectedEdge<E> &_e)
326 {
327 _out << " " << _e.Tail() << " -> " << _e.Head()
328 << " [label=" << _e.Weight() << "];" << std::endl;
329 return _out;
330 }
331 };
332
334 template<typename E>
335 DirectedEdge<E> DirectedEdge<E>::NullEdge(
336 VertexId_P(kNullId, kNullId), E(), 1.0, kNullId);
337}
338}
339}
340}
341#endif
A directed edge represents a connection between two vertices.
Definition Edge.hh:268
VertexId From(const VertexId &_from) const override
Get the destination end that is reachable from a source end of an edge.
Definition Edge.hh:302
DirectedEdge(const VertexId_P &_vertices, const E &_data, const double _weight, const EdgeId &_id=kNullId)
Constructor.
Definition Edge.hh:277
VertexId Tail() const
Get the Id of the tail vertex in this edge.
Definition Edge.hh:288
VertexId To(const VertexId &_to) const override
Get the source end that can reach the destination end of an edge.
Definition Edge.hh:311
static DirectedEdge< E > NullEdge
An invalid directed edge.
Definition Edge.hh:270
VertexId Head() const
Get the Id of the head vertex in this edge.
Definition Edge.hh:296
friend std::ostream & operator<<(std::ostream &_out, const DirectedEdge< E > &_e)
Stream insertion operator.
Definition Edge.hh:324
Generic edge class.
Definition Edge.hh:74
virtual VertexId To(const VertexId &_to) const =0
Get the source end that can reach the destination end of an edge.
bool Valid() const
An edge is considered valid when its id is not kNullId.
Definition Edge.hh:171
const E & Data() const
Get a non-mutable reference to the user data stored in the edge.
Definition Edge.hh:110
virtual VertexId From(const VertexId &_from) const =0
Get the destination end that is reachable from a source end of an edge.
Edge(const VertexId_P &_vertices, const E &_data, const double _weight, const EdgeId &_id=kNullId)
Constructor.
Definition Edge.hh:80
VertexId_P Vertices() const
Get the two vertices contained in the edge.
Definition Edge.hh:100
double Weight() const
The cost of traversing the _from end to the other end of the edge.
Definition Edge.hh:125
EdgeId Id() const
Get the edge Id.
Definition Edge.hh:93
void SetWeight(const double _newWeight)
Set the cost of the edge.
Definition Edge.hh:132
E & Data()
Get a mutable reference to the user data stored in the edge.
Definition Edge.hh:117
An undirected edge represents a connection between two vertices.
Definition Edge.hh:205
VertexId To(const VertexId &_to) const override
Get the source end that can reach the destination end of an edge.
Definition Edge.hh:238
VertexId From(const VertexId &_from) const override
Get the destination end that is reachable from a source end of an edge.
Definition Edge.hh:223
friend std::ostream & operator<<(std::ostream &_out, const UndirectedEdge< E > &_e)
Stream insertion operator.
Definition Edge.hh:248
UndirectedEdge(const VertexId_P &_vertices, const E &_data, const double _weight, const EdgeId &_id=kNullId)
Constructor.
Definition Edge.hh:214
static UndirectedEdge< E > NullEdge
An invalid undirected edge.
Definition Edge.hh:207
std::pair< VertexId, VertexId > VertexId_P
Definition Vertex.hh:45
std::map< EdgeId, std::reference_wrapper< const EdgeType > > EdgeRef_M
Definition Edge.hh:198
static const VertexId kNullId
Represents an invalid Id.
Definition Vertex.hh:48
std::set< EdgeId > EdgeId_S
Definition Edge.hh:192
Definition Angle.hh:40
Used in the Graph constructors for uniform initialization.
Definition Edge.hh:45
VertexId_P vertices
IDs of the vertices.
Definition Edge.hh:60
EdgeInitializer(const VertexId_P &_vertices, const E &_data=E(), const double _weight=1)
Constructor.
Definition Edge.hh:50
double weight
The weight (cost) of the edge.
Definition Edge.hh:66