alpar@105
|
1 |
// -*- mode:C++ -*-
|
alpar@105
|
2 |
|
alpar@185
|
3 |
#ifndef HUGO_SMART_GRAPH_H
|
alpar@185
|
4 |
#define HUGO_SMART_GRAPH_H
|
alpar@104
|
5 |
|
alpar@242
|
6 |
///\file
|
alpar@242
|
7 |
///\brief SmartGraph and SymSmartGraph classes.
|
alpar@242
|
8 |
|
alpar@104
|
9 |
#include <vector>
|
alpar@129
|
10 |
#include <limits.h>
|
alpar@104
|
11 |
|
alpar@253
|
12 |
#include "invalid.h"
|
alpar@157
|
13 |
|
alpar@105
|
14 |
namespace hugo {
|
alpar@104
|
15 |
|
alpar@185
|
16 |
class SymSmartGraph;
|
alpar@185
|
17 |
|
alpar@186
|
18 |
///A smart graph class.
|
alpar@186
|
19 |
|
alpar@186
|
20 |
///This is a simple and fast graph implementation.
|
alpar@186
|
21 |
///It is also quite memory efficient, but at the price
|
alpar@186
|
22 |
///that <b> it does not support node and edge deletion</b>.
|
alpar@242
|
23 |
///It conforms to the graph interface documented under
|
alpar@186
|
24 |
///the description of \ref GraphSkeleton.
|
alpar@186
|
25 |
///\sa \ref GraphSkeleton.
|
alpar@104
|
26 |
class SmartGraph {
|
alpar@104
|
27 |
|
alpar@104
|
28 |
struct NodeT
|
alpar@104
|
29 |
{
|
alpar@104
|
30 |
int first_in,first_out;
|
alpar@157
|
31 |
NodeT() : first_in(-1), first_out(-1) {}
|
alpar@104
|
32 |
};
|
alpar@104
|
33 |
struct EdgeT
|
alpar@104
|
34 |
{
|
alpar@104
|
35 |
int head, tail, next_in, next_out;
|
alpar@104
|
36 |
//FIXME: is this necessary?
|
alpar@157
|
37 |
EdgeT() : next_in(-1), next_out(-1) {}
|
alpar@104
|
38 |
};
|
alpar@104
|
39 |
|
alpar@104
|
40 |
std::vector<NodeT> nodes;
|
alpar@129
|
41 |
|
alpar@104
|
42 |
std::vector<EdgeT> edges;
|
alpar@104
|
43 |
|
alpar@185
|
44 |
protected:
|
alpar@185
|
45 |
|
alpar@108
|
46 |
template <typename Key> class DynMapBase
|
alpar@108
|
47 |
{
|
alpar@108
|
48 |
protected:
|
alpar@185
|
49 |
const SmartGraph* G;
|
alpar@108
|
50 |
public:
|
alpar@108
|
51 |
virtual void add(const Key k) = NULL;
|
alpar@108
|
52 |
virtual void erase(const Key k) = NULL;
|
alpar@157
|
53 |
DynMapBase(const SmartGraph &_G) : G(&_G) {}
|
alpar@108
|
54 |
virtual ~DynMapBase() {}
|
alpar@108
|
55 |
friend class SmartGraph;
|
alpar@108
|
56 |
};
|
alpar@185
|
57 |
|
alpar@104
|
58 |
public:
|
alpar@185
|
59 |
template <typename T> class EdgeMap;
|
alpar@185
|
60 |
template <typename T> class EdgeMap;
|
alpar@104
|
61 |
|
alpar@164
|
62 |
class Node;
|
alpar@164
|
63 |
class Edge;
|
alpar@108
|
64 |
|
alpar@185
|
65 |
// protected:
|
alpar@185
|
66 |
// HELPME:
|
alpar@186
|
67 |
protected:
|
alpar@185
|
68 |
///\bug It must be public because of SymEdgeMap.
|
alpar@185
|
69 |
///
|
alpar@164
|
70 |
mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
|
alpar@185
|
71 |
///\bug It must be public because of SymEdgeMap.
|
alpar@185
|
72 |
///
|
alpar@164
|
73 |
mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
|
alpar@108
|
74 |
|
alpar@108
|
75 |
public:
|
alpar@108
|
76 |
|
alpar@164
|
77 |
class NodeIt;
|
alpar@164
|
78 |
class EdgeIt;
|
alpar@104
|
79 |
class OutEdgeIt;
|
alpar@104
|
80 |
class InEdgeIt;
|
alpar@104
|
81 |
|
alpar@105
|
82 |
template <typename T> class NodeMap;
|
alpar@104
|
83 |
template <typename T> class EdgeMap;
|
alpar@104
|
84 |
|
alpar@104
|
85 |
public:
|
alpar@104
|
86 |
|
alpar@104
|
87 |
SmartGraph() : nodes(), edges() { }
|
alpar@136
|
88 |
SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
|
alpar@104
|
89 |
|
alpar@108
|
90 |
~SmartGraph()
|
alpar@108
|
91 |
{
|
alpar@164
|
92 |
for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
|
alpar@108
|
93 |
i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
|
alpar@164
|
94 |
for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
|
alpar@108
|
95 |
i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
|
alpar@108
|
96 |
}
|
alpar@104
|
97 |
|
alpar@104
|
98 |
int nodeNum() const { return nodes.size(); } //FIXME: What is this?
|
alpar@104
|
99 |
int edgeNum() const { return edges.size(); } //FIXME: What is this?
|
alpar@104
|
100 |
|
alpar@186
|
101 |
///\bug This function does something different than
|
alpar@186
|
102 |
///its name would suggests...
|
alpar@108
|
103 |
int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
|
alpar@186
|
104 |
///\bug This function does something different than
|
alpar@186
|
105 |
///its name would suggests...
|
alpar@108
|
106 |
int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
|
alpar@108
|
107 |
|
alpar@164
|
108 |
Node tail(Edge e) const { return edges[e.n].tail; }
|
alpar@164
|
109 |
Node head(Edge e) const { return edges[e.n].head; }
|
alpar@104
|
110 |
|
marci@174
|
111 |
Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
|
marci@174
|
112 |
Node aNode(InEdgeIt e) const { return edges[e.n].head; }
|
alpar@104
|
113 |
|
marci@174
|
114 |
Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
|
marci@174
|
115 |
Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
|
alpar@104
|
116 |
|
alpar@164
|
117 |
NodeIt& first(NodeIt& v) const {
|
alpar@164
|
118 |
v=NodeIt(*this); return v; }
|
alpar@164
|
119 |
EdgeIt& first(EdgeIt& e) const {
|
alpar@164
|
120 |
e=EdgeIt(*this); return e; }
|
alpar@164
|
121 |
OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
|
alpar@104
|
122 |
e=OutEdgeIt(*this,v); return e; }
|
alpar@164
|
123 |
InEdgeIt& first(InEdgeIt& e, const Node v) const {
|
alpar@104
|
124 |
e=InEdgeIt(*this,v); return e; }
|
alpar@104
|
125 |
|
alpar@104
|
126 |
template< typename It >
|
alpar@177
|
127 |
It first() const { It e; first(e); return e; }
|
alpar@104
|
128 |
|
alpar@104
|
129 |
template< typename It >
|
alpar@177
|
130 |
It first(Node v) const { It e; first(e,v); return e; }
|
alpar@104
|
131 |
|
alpar@164
|
132 |
bool valid(Edge e) const { return e.n!=-1; }
|
alpar@164
|
133 |
bool valid(Node n) const { return n.n!=-1; }
|
alpar@104
|
134 |
|
alpar@164
|
135 |
void setInvalid(Edge &e) { e.n=-1; }
|
alpar@164
|
136 |
void setInvalid(Node &n) { n.n=-1; }
|
alpar@129
|
137 |
|
alpar@157
|
138 |
template <typename It> It getNext(It it) const
|
alpar@157
|
139 |
{ It tmp(it); return next(tmp); }
|
alpar@104
|
140 |
|
marci@174
|
141 |
NodeIt& next(NodeIt& it) const {
|
marci@174
|
142 |
it.n=(it.n+2)%(nodes.size()+1)-1;
|
marci@174
|
143 |
return it;
|
marci@174
|
144 |
}
|
alpar@157
|
145 |
OutEdgeIt& next(OutEdgeIt& it) const
|
alpar@104
|
146 |
{ it.n=edges[it.n].next_out; return it; }
|
alpar@157
|
147 |
InEdgeIt& next(InEdgeIt& it) const
|
alpar@104
|
148 |
{ it.n=edges[it.n].next_in; return it; }
|
alpar@164
|
149 |
EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
|
alpar@104
|
150 |
|
alpar@164
|
151 |
int id(Node v) const { return v.n; }
|
alpar@164
|
152 |
int id(Edge e) const { return e.n; }
|
alpar@104
|
153 |
|
alpar@164
|
154 |
Node addNode() {
|
alpar@164
|
155 |
Node n; n.n=nodes.size();
|
alpar@104
|
156 |
nodes.push_back(NodeT()); //FIXME: Hmmm...
|
alpar@108
|
157 |
|
alpar@164
|
158 |
for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
|
alpar@108
|
159 |
i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
|
alpar@108
|
160 |
|
alpar@104
|
161 |
return n;
|
alpar@104
|
162 |
}
|
alpar@108
|
163 |
|
alpar@164
|
164 |
Edge addEdge(Node u, Node v) {
|
alpar@164
|
165 |
Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
|
alpar@104
|
166 |
edges[e.n].tail=u.n; edges[e.n].head=v.n;
|
alpar@104
|
167 |
edges[e.n].next_out=nodes[u.n].first_out;
|
alpar@104
|
168 |
edges[e.n].next_in=nodes[v.n].first_in;
|
alpar@104
|
169 |
nodes[u.n].first_out=nodes[v.n].first_in=e.n;
|
alpar@108
|
170 |
|
alpar@164
|
171 |
for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
|
alpar@157
|
172 |
i!=dyn_edge_maps.end(); ++i) (**i).add(e);
|
alpar@108
|
173 |
|
alpar@104
|
174 |
return e;
|
alpar@104
|
175 |
}
|
alpar@104
|
176 |
|
alpar@104
|
177 |
void clear() {nodes.clear();edges.clear();}
|
alpar@104
|
178 |
|
alpar@164
|
179 |
class Node {
|
alpar@104
|
180 |
friend class SmartGraph;
|
alpar@104
|
181 |
template <typename T> friend class NodeMap;
|
alpar@104
|
182 |
|
alpar@164
|
183 |
friend class Edge;
|
alpar@104
|
184 |
friend class OutEdgeIt;
|
alpar@104
|
185 |
friend class InEdgeIt;
|
alpar@164
|
186 |
friend class SymEdge;
|
alpar@104
|
187 |
|
alpar@104
|
188 |
protected:
|
alpar@104
|
189 |
int n;
|
alpar@164
|
190 |
friend int SmartGraph::id(Node v) const;
|
alpar@164
|
191 |
Node(int nn) {n=nn;}
|
alpar@104
|
192 |
public:
|
alpar@164
|
193 |
Node() {}
|
alpar@164
|
194 |
Node (Invalid i) { n=-1; }
|
alpar@164
|
195 |
bool operator==(const Node i) const {return n==i.n;}
|
alpar@164
|
196 |
bool operator!=(const Node i) const {return n!=i.n;}
|
alpar@164
|
197 |
bool operator<(const Node i) const {return n<i.n;}
|
alpar@104
|
198 |
};
|
alpar@104
|
199 |
|
alpar@164
|
200 |
class NodeIt : public Node {
|
alpar@104
|
201 |
friend class SmartGraph;
|
alpar@104
|
202 |
public:
|
alpar@164
|
203 |
NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
|
alpar@164
|
204 |
NodeIt() : Node() { }
|
alpar@104
|
205 |
};
|
alpar@104
|
206 |
|
alpar@164
|
207 |
class Edge {
|
alpar@104
|
208 |
friend class SmartGraph;
|
alpar@104
|
209 |
template <typename T> friend class EdgeMap;
|
alpar@185
|
210 |
|
alpar@185
|
211 |
//template <typename T> friend class SymSmartGraph::SymEdgeMap;
|
alpar@185
|
212 |
//friend Edge SymSmartGraph::opposite(Edge) const;
|
alpar@104
|
213 |
|
alpar@164
|
214 |
friend class Node;
|
alpar@104
|
215 |
friend class NodeIt;
|
alpar@104
|
216 |
protected:
|
alpar@104
|
217 |
int n;
|
alpar@164
|
218 |
friend int SmartGraph::id(Edge e) const;
|
alpar@157
|
219 |
|
alpar@164
|
220 |
Edge(int nn) {n=nn;}
|
alpar@104
|
221 |
public:
|
alpar@164
|
222 |
Edge() { }
|
marci@174
|
223 |
Edge (Invalid) { n=-1; }
|
alpar@164
|
224 |
bool operator==(const Edge i) const {return n==i.n;}
|
alpar@164
|
225 |
bool operator!=(const Edge i) const {return n!=i.n;}
|
alpar@164
|
226 |
bool operator<(const Edge i) const {return n<i.n;}
|
alpar@185
|
227 |
///\bug This is a workaround until somebody tells me how to
|
alpar@185
|
228 |
///make class \c SymSmartGraph::SymEdgeMap friend of Edge
|
alpar@185
|
229 |
int &idref() {return n;}
|
alpar@185
|
230 |
const int &idref() const {return n;}
|
alpar@104
|
231 |
};
|
alpar@104
|
232 |
|
alpar@164
|
233 |
class EdgeIt : public Edge {
|
alpar@104
|
234 |
friend class SmartGraph;
|
alpar@104
|
235 |
public:
|
alpar@164
|
236 |
EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
|
alpar@164
|
237 |
EdgeIt (Invalid i) : Edge(i) { }
|
alpar@164
|
238 |
EdgeIt() : Edge() { }
|
alpar@185
|
239 |
///\bug This is a workaround until somebody tells me how to
|
alpar@185
|
240 |
///make class \c SymSmartGraph::SymEdgeMap friend of Edge
|
alpar@185
|
241 |
int &idref() {return n;}
|
alpar@104
|
242 |
};
|
alpar@104
|
243 |
|
alpar@164
|
244 |
class OutEdgeIt : public Edge {
|
alpar@104
|
245 |
friend class SmartGraph;
|
alpar@104
|
246 |
public:
|
alpar@164
|
247 |
OutEdgeIt() : Edge() { }
|
alpar@164
|
248 |
OutEdgeIt (Invalid i) : Edge(i) { }
|
alpar@157
|
249 |
|
alpar@164
|
250 |
OutEdgeIt(const SmartGraph& G,const Node v)
|
alpar@164
|
251 |
: Edge(G.nodes[v.n].first_out) {}
|
alpar@104
|
252 |
};
|
alpar@104
|
253 |
|
alpar@164
|
254 |
class InEdgeIt : public Edge {
|
alpar@104
|
255 |
friend class SmartGraph;
|
alpar@104
|
256 |
public:
|
alpar@164
|
257 |
InEdgeIt() : Edge() { }
|
alpar@164
|
258 |
InEdgeIt (Invalid i) : Edge(i) { }
|
alpar@164
|
259 |
InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
|
alpar@104
|
260 |
};
|
alpar@105
|
261 |
|
alpar@185
|
262 |
template <typename T> class NodeMap : public DynMapBase<Node>
|
alpar@108
|
263 |
{
|
alpar@108
|
264 |
std::vector<T> container;
|
alpar@105
|
265 |
|
alpar@108
|
266 |
public:
|
alpar@108
|
267 |
typedef T ValueType;
|
alpar@164
|
268 |
typedef Node KeyType;
|
alpar@105
|
269 |
|
alpar@185
|
270 |
NodeMap(const SmartGraph &_G) :
|
alpar@164
|
271 |
DynMapBase<Node>(_G), container(_G.maxNodeId())
|
alpar@108
|
272 |
{
|
alpar@108
|
273 |
G->dyn_node_maps.push_back(this);
|
alpar@108
|
274 |
}
|
alpar@185
|
275 |
NodeMap(const SmartGraph &_G,const T &t) :
|
alpar@185
|
276 |
DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
|
alpar@185
|
277 |
{
|
alpar@185
|
278 |
G->dyn_node_maps.push_back(this);
|
alpar@185
|
279 |
}
|
alpar@185
|
280 |
|
alpar@185
|
281 |
NodeMap(const NodeMap<T> &m) :
|
alpar@185
|
282 |
DynMapBase<Node>(*m.G), container(m.container)
|
alpar@185
|
283 |
{
|
alpar@185
|
284 |
G->dyn_node_maps.push_back(this);
|
alpar@185
|
285 |
}
|
alpar@185
|
286 |
|
alpar@185
|
287 |
template<typename TT> friend class NodeMap;
|
alpar@185
|
288 |
|
alpar@185
|
289 |
///\todo It can copy between different types.
|
alpar@185
|
290 |
///
|
alpar@185
|
291 |
template<typename TT> NodeMap(const NodeMap<TT> &m) :
|
alpar@185
|
292 |
DynMapBase<Node>(*m.G)
|
alpar@185
|
293 |
{
|
alpar@185
|
294 |
G->dyn_node_maps.push_back(this);
|
alpar@185
|
295 |
typename std::vector<TT>::const_iterator i;
|
alpar@185
|
296 |
for(typename std::vector<TT>::const_iterator i=m.container.begin();
|
alpar@185
|
297 |
i!=m.container.end();
|
alpar@185
|
298 |
i++)
|
alpar@185
|
299 |
container.push_back(*i);
|
alpar@185
|
300 |
}
|
alpar@185
|
301 |
~NodeMap()
|
alpar@108
|
302 |
{
|
alpar@108
|
303 |
if(G) {
|
alpar@164
|
304 |
std::vector<DynMapBase<Node>* >::iterator i;
|
alpar@108
|
305 |
for(i=G->dyn_node_maps.begin();
|
alpar@108
|
306 |
i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
|
alpar@115
|
307 |
//if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
|
alpar@115
|
308 |
//A better way to do that: (Is this really important?)
|
alpar@115
|
309 |
if(*i==this) {
|
alpar@116
|
310 |
*i=G->dyn_node_maps.back();
|
alpar@115
|
311 |
G->dyn_node_maps.pop_back();
|
alpar@115
|
312 |
}
|
alpar@108
|
313 |
}
|
alpar@108
|
314 |
}
|
alpar@105
|
315 |
|
alpar@164
|
316 |
void add(const Node k)
|
alpar@108
|
317 |
{
|
alpar@185
|
318 |
if(k.n>=int(container.size())) container.resize(k.n+1);
|
alpar@108
|
319 |
}
|
alpar@177
|
320 |
|
alpar@215
|
321 |
void erase(const Node) { }
|
alpar@108
|
322 |
|
alpar@164
|
323 |
void set(Node n, T a) { container[n.n]=a; }
|
alpar@285
|
324 |
//'T& operator[](Node n)' would be wrong here
|
alpar@215
|
325 |
typename std::vector<T>::reference
|
alpar@215
|
326 |
operator[](Node n) { return container[n.n]; }
|
alpar@285
|
327 |
//'const T& operator[](Node n)' would be wrong here
|
alpar@215
|
328 |
typename std::vector<T>::const_reference
|
alpar@215
|
329 |
operator[](Node n) const { return container[n.n]; }
|
alpar@108
|
330 |
|
alpar@185
|
331 |
///\warning There is no safety check at all!
|
alpar@185
|
332 |
///Using operator = between maps attached to different graph may
|
alpar@185
|
333 |
///cause serious problem.
|
alpar@185
|
334 |
///\todo Is this really so?
|
alpar@185
|
335 |
///\todo It can copy between different types.
|
alpar@185
|
336 |
const NodeMap<T>& operator=(const NodeMap<T> &m)
|
alpar@185
|
337 |
{
|
alpar@185
|
338 |
container = m.container;
|
alpar@185
|
339 |
return *this;
|
alpar@185
|
340 |
}
|
alpar@185
|
341 |
template<typename TT>
|
alpar@185
|
342 |
const NodeMap<T>& operator=(const NodeMap<TT> &m)
|
alpar@185
|
343 |
{
|
alpar@185
|
344 |
copy(m.container.begin(), m.container.end(), container.begin());
|
alpar@185
|
345 |
return *this;
|
alpar@185
|
346 |
}
|
alpar@185
|
347 |
|
alpar@285
|
348 |
void update() {} //Useless for Dynamic Maps
|
alpar@285
|
349 |
void update(T a) {} //Useless for Dynamic Maps
|
alpar@108
|
350 |
};
|
alpar@108
|
351 |
|
alpar@185
|
352 |
template <typename T> class EdgeMap : public DynMapBase<Edge>
|
alpar@108
|
353 |
{
|
alpar@108
|
354 |
std::vector<T> container;
|
alpar@108
|
355 |
|
alpar@108
|
356 |
public:
|
alpar@108
|
357 |
typedef T ValueType;
|
alpar@164
|
358 |
typedef Edge KeyType;
|
alpar@108
|
359 |
|
alpar@185
|
360 |
EdgeMap(const SmartGraph &_G) :
|
alpar@164
|
361 |
DynMapBase<Edge>(_G), container(_G.maxEdgeId())
|
alpar@108
|
362 |
{
|
alpar@108
|
363 |
//FIXME: What if there are empty Id's?
|
alpar@115
|
364 |
//FIXME: Can I use 'this' in a constructor?
|
alpar@108
|
365 |
G->dyn_edge_maps.push_back(this);
|
alpar@108
|
366 |
}
|
alpar@185
|
367 |
EdgeMap(const SmartGraph &_G,const T &t) :
|
alpar@185
|
368 |
DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
|
alpar@185
|
369 |
{
|
alpar@185
|
370 |
G->dyn_edge_maps.push_back(this);
|
alpar@185
|
371 |
}
|
alpar@185
|
372 |
EdgeMap(const EdgeMap<T> &m) :
|
alpar@185
|
373 |
DynMapBase<Edge>(*m.G), container(m.container)
|
alpar@185
|
374 |
{
|
alpar@185
|
375 |
G->dyn_node_maps.push_back(this);
|
alpar@185
|
376 |
}
|
alpar@185
|
377 |
|
alpar@185
|
378 |
template<typename TT> friend class EdgeMap;
|
alpar@185
|
379 |
|
alpar@185
|
380 |
///\todo It can copy between different types.
|
alpar@185
|
381 |
///
|
alpar@185
|
382 |
template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
|
alpar@185
|
383 |
DynMapBase<Edge>(*m.G)
|
alpar@185
|
384 |
{
|
alpar@185
|
385 |
G->dyn_node_maps.push_back(this);
|
alpar@185
|
386 |
typename std::vector<TT>::const_iterator i;
|
alpar@185
|
387 |
for(typename std::vector<TT>::const_iterator i=m.container.begin();
|
alpar@185
|
388 |
i!=m.container.end();
|
alpar@185
|
389 |
i++)
|
alpar@185
|
390 |
container.push_back(*i);
|
alpar@185
|
391 |
}
|
alpar@185
|
392 |
~EdgeMap()
|
alpar@108
|
393 |
{
|
alpar@108
|
394 |
if(G) {
|
alpar@164
|
395 |
std::vector<DynMapBase<Edge>* >::iterator i;
|
alpar@108
|
396 |
for(i=G->dyn_edge_maps.begin();
|
alpar@108
|
397 |
i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
|
alpar@115
|
398 |
//if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
|
alpar@115
|
399 |
//A better way to do that: (Is this really important?)
|
alpar@115
|
400 |
if(*i==this) {
|
alpar@116
|
401 |
*i=G->dyn_edge_maps.back();
|
alpar@115
|
402 |
G->dyn_edge_maps.pop_back();
|
alpar@115
|
403 |
}
|
alpar@108
|
404 |
}
|
alpar@108
|
405 |
}
|
alpar@115
|
406 |
|
alpar@164
|
407 |
void add(const Edge k)
|
alpar@108
|
408 |
{
|
alpar@108
|
409 |
if(k.n>=int(container.size())) container.resize(k.n+1);
|
alpar@108
|
410 |
}
|
alpar@215
|
411 |
void erase(const Edge) { }
|
alpar@108
|
412 |
|
alpar@164
|
413 |
void set(Edge n, T a) { container[n.n]=a; }
|
alpar@209
|
414 |
//T get(Edge n) const { return container[n.n]; }
|
alpar@215
|
415 |
typename std::vector<T>::reference
|
alpar@215
|
416 |
operator[](Edge n) { return container[n.n]; }
|
alpar@215
|
417 |
typename std::vector<T>::const_reference
|
alpar@215
|
418 |
operator[](Edge n) const { return container[n.n]; }
|
alpar@108
|
419 |
|
alpar@185
|
420 |
///\warning There is no safety check at all!
|
alpar@185
|
421 |
///Using operator = between maps attached to different graph may
|
alpar@185
|
422 |
///cause serious problem.
|
alpar@185
|
423 |
///\todo Is this really so?
|
alpar@185
|
424 |
///\todo It can copy between different types.
|
alpar@185
|
425 |
const EdgeMap<T>& operator=(const EdgeMap<T> &m)
|
alpar@185
|
426 |
{
|
alpar@185
|
427 |
container = m.container;
|
alpar@185
|
428 |
return *this;
|
alpar@185
|
429 |
}
|
alpar@185
|
430 |
template<typename TT>
|
alpar@185
|
431 |
const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
|
alpar@185
|
432 |
{
|
alpar@185
|
433 |
copy(m.container.begin(), m.container.end(), container.begin());
|
alpar@185
|
434 |
return *this;
|
alpar@185
|
435 |
}
|
alpar@185
|
436 |
|
alpar@108
|
437 |
void update() {} //Useless for DynMaps
|
alpar@108
|
438 |
void update(T a) {} //Useless for DynMaps
|
alpar@108
|
439 |
};
|
alpar@185
|
440 |
|
alpar@104
|
441 |
};
|
alpar@185
|
442 |
|
alpar@185
|
443 |
///Graph for bidirectional edges.
|
alpar@185
|
444 |
|
alpar@185
|
445 |
///The purpose of this graph structure is to handle graphs
|
alpar@185
|
446 |
///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
|
alpar@186
|
447 |
///of oppositely directed edges.
|
alpar@186
|
448 |
///There is a new edge map type called
|
alpar@186
|
449 |
///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
|
alpar@186
|
450 |
///that complements this
|
alpar@186
|
451 |
///feature by
|
alpar@186
|
452 |
///storing shared values for the edge pairs. The usual
|
alpar@186
|
453 |
///\ref GraphSkeleton::EdgeMap "EdgeMap"
|
alpar@186
|
454 |
///can be used
|
alpar@185
|
455 |
///as well.
|
alpar@185
|
456 |
///
|
alpar@186
|
457 |
///The oppositely directed edge can also be obtained easily
|
alpar@186
|
458 |
///using \ref opposite.
|
alpar@186
|
459 |
///\warning It shares the similarity with \ref SmartGraph that
|
alpar@186
|
460 |
///it is not possible to delete edges or nodes from the graph.
|
alpar@186
|
461 |
//\sa \ref SmartGraph.
|
alpar@185
|
462 |
|
alpar@185
|
463 |
class SymSmartGraph : public SmartGraph
|
alpar@185
|
464 |
{
|
alpar@185
|
465 |
public:
|
alpar@186
|
466 |
template<typename T> class SymEdgeMap;
|
alpar@186
|
467 |
template<typename T> friend class SymEdgeMap;
|
alpar@186
|
468 |
|
alpar@185
|
469 |
SymSmartGraph() : SmartGraph() { }
|
alpar@185
|
470 |
SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
|
alpar@185
|
471 |
Edge addEdge(Node u, Node v)
|
alpar@185
|
472 |
{
|
alpar@185
|
473 |
Edge e = SmartGraph::addEdge(u,v);
|
alpar@185
|
474 |
SmartGraph::addEdge(v,u);
|
alpar@185
|
475 |
return e;
|
alpar@185
|
476 |
}
|
alpar@185
|
477 |
|
alpar@186
|
478 |
///The oppositely directed edge.
|
alpar@186
|
479 |
|
alpar@186
|
480 |
///Returns the oppositely directed
|
alpar@186
|
481 |
///pair of the edge \c e.
|
alpar@185
|
482 |
Edge opposite(Edge e) const
|
alpar@185
|
483 |
{
|
alpar@185
|
484 |
Edge f;
|
alpar@185
|
485 |
f.idref() = e.idref() - 2*(e.idref()%2) + 1;
|
alpar@185
|
486 |
return f;
|
alpar@185
|
487 |
}
|
alpar@185
|
488 |
|
alpar@186
|
489 |
///Common data storage for the edge pairs.
|
alpar@186
|
490 |
|
alpar@186
|
491 |
///This map makes it possible to store data shared by the oppositely
|
alpar@186
|
492 |
///directed pairs of edges.
|
alpar@185
|
493 |
template <typename T> class SymEdgeMap : public DynMapBase<Edge>
|
alpar@185
|
494 |
{
|
alpar@185
|
495 |
std::vector<T> container;
|
alpar@185
|
496 |
|
alpar@185
|
497 |
public:
|
alpar@185
|
498 |
typedef T ValueType;
|
alpar@185
|
499 |
typedef Edge KeyType;
|
alpar@185
|
500 |
|
alpar@186
|
501 |
SymEdgeMap(const SymSmartGraph &_G) :
|
alpar@185
|
502 |
DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
|
alpar@185
|
503 |
{
|
alpar@186
|
504 |
static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
|
alpar@185
|
505 |
}
|
alpar@186
|
506 |
SymEdgeMap(const SymSmartGraph &_G,const T &t) :
|
alpar@185
|
507 |
DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
|
alpar@185
|
508 |
{
|
alpar@185
|
509 |
G->dyn_edge_maps.push_back(this);
|
alpar@185
|
510 |
}
|
alpar@185
|
511 |
|
alpar@185
|
512 |
SymEdgeMap(const SymEdgeMap<T> &m) :
|
alpar@185
|
513 |
DynMapBase<SymEdge>(*m.G), container(m.container)
|
alpar@185
|
514 |
{
|
alpar@185
|
515 |
G->dyn_node_maps.push_back(this);
|
alpar@185
|
516 |
}
|
alpar@185
|
517 |
|
alpar@185
|
518 |
// template<typename TT> friend class SymEdgeMap;
|
alpar@185
|
519 |
|
alpar@185
|
520 |
///\todo It can copy between different types.
|
alpar@185
|
521 |
///
|
alpar@185
|
522 |
|
alpar@185
|
523 |
template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
|
alpar@185
|
524 |
DynMapBase<SymEdge>(*m.G)
|
alpar@185
|
525 |
{
|
alpar@185
|
526 |
G->dyn_node_maps.push_back(this);
|
alpar@185
|
527 |
typename std::vector<TT>::const_iterator i;
|
alpar@185
|
528 |
for(typename std::vector<TT>::const_iterator i=m.container.begin();
|
alpar@185
|
529 |
i!=m.container.end();
|
alpar@185
|
530 |
i++)
|
alpar@185
|
531 |
container.push_back(*i);
|
alpar@185
|
532 |
}
|
alpar@185
|
533 |
|
alpar@185
|
534 |
~SymEdgeMap()
|
alpar@185
|
535 |
{
|
alpar@185
|
536 |
if(G) {
|
alpar@185
|
537 |
std::vector<DynMapBase<Edge>* >::iterator i;
|
alpar@186
|
538 |
for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
|
alpar@186
|
539 |
i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
|
alpar@186
|
540 |
&& *i!=this; ++i) ;
|
alpar@185
|
541 |
//if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
|
alpar@185
|
542 |
//A better way to do that: (Is this really important?)
|
alpar@185
|
543 |
if(*i==this) {
|
alpar@186
|
544 |
*i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
|
alpar@186
|
545 |
static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
|
alpar@185
|
546 |
}
|
alpar@185
|
547 |
}
|
alpar@185
|
548 |
}
|
alpar@185
|
549 |
|
alpar@185
|
550 |
void add(const Edge k)
|
alpar@185
|
551 |
{
|
alpar@185
|
552 |
if(!k.idref()%2&&k.idref()/2>=int(container.size()))
|
alpar@185
|
553 |
container.resize(k.idref()/2+1);
|
alpar@185
|
554 |
}
|
alpar@185
|
555 |
void erase(const Edge k) { }
|
alpar@185
|
556 |
|
alpar@185
|
557 |
void set(Edge n, T a) { container[n.idref()/2]=a; }
|
alpar@209
|
558 |
//T get(Edge n) const { return container[n.idref()/2]; }
|
alpar@215
|
559 |
typename std::vector<T>::reference
|
alpar@215
|
560 |
operator[](Edge n) { return container[n.idref()/2]; }
|
alpar@215
|
561 |
typename std::vector<T>::const_reference
|
alpar@215
|
562 |
operator[](Edge n) const { return container[n.idref()/2]; }
|
alpar@185
|
563 |
|
alpar@185
|
564 |
///\warning There is no safety check at all!
|
alpar@185
|
565 |
///Using operator = between maps attached to different graph may
|
alpar@185
|
566 |
///cause serious problem.
|
alpar@185
|
567 |
///\todo Is this really so?
|
alpar@185
|
568 |
///\todo It can copy between different types.
|
alpar@185
|
569 |
const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
|
alpar@185
|
570 |
{
|
alpar@185
|
571 |
container = m.container;
|
alpar@185
|
572 |
return *this;
|
alpar@185
|
573 |
}
|
alpar@185
|
574 |
template<typename TT>
|
alpar@185
|
575 |
const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
|
alpar@185
|
576 |
{
|
alpar@185
|
577 |
copy(m.container.begin(), m.container.end(), container.begin());
|
alpar@185
|
578 |
return *this;
|
alpar@185
|
579 |
}
|
alpar@185
|
580 |
|
alpar@185
|
581 |
void update() {} //Useless for DynMaps
|
alpar@185
|
582 |
void update(T a) {} //Useless for DynMaps
|
alpar@185
|
583 |
|
alpar@185
|
584 |
};
|
alpar@185
|
585 |
|
alpar@185
|
586 |
};
|
alpar@185
|
587 |
|
alpar@185
|
588 |
|
alpar@105
|
589 |
} //namespace hugo
|
alpar@104
|
590 |
|
alpar@157
|
591 |
|
alpar@157
|
592 |
|
alpar@157
|
593 |
|
alpar@104
|
594 |
#endif //SMART_GRAPH_H
|