129 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
129 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
130 |
130 |
131 Node tail(Edge e) const { return edges[e.n].tail; } |
131 Node tail(Edge e) const { return edges[e.n].tail; } |
132 Node head(Edge e) const { return edges[e.n].head; } |
132 Node head(Edge e) const { return edges[e.n].head; } |
133 |
133 |
134 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } |
|
135 Node aNode(InEdgeIt e) const { return edges[e.n].head; } |
|
136 |
|
137 Node bNode(OutEdgeIt e) const { return edges[e.n].head; } |
|
138 Node bNode(InEdgeIt e) const { return edges[e.n].tail; } |
|
139 |
|
140 NodeIt& first(NodeIt& v) const { |
134 NodeIt& first(NodeIt& v) const { |
141 v=NodeIt(*this); return v; } |
135 v=NodeIt(*this); return v; } |
142 EdgeIt& first(EdgeIt& e) const { |
136 EdgeIt& first(EdgeIt& e) const { |
143 e=EdgeIt(*this); return e; } |
137 e=EdgeIt(*this); return e; } |
144 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
138 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
145 e=OutEdgeIt(*this,v); return e; } |
139 e=OutEdgeIt(*this,v); return e; } |
146 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
140 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
147 e=InEdgeIt(*this,v); return e; } |
141 e=InEdgeIt(*this,v); return e; } |
148 |
142 |
149 // template< typename It > |
|
150 // It first() const { It e; first(e); return e; } |
|
151 |
|
152 // template< typename It > |
|
153 // It first(Node v) const { It e; first(e,v); return e; } |
|
154 |
|
155 static bool valid(Edge e) { return e.n!=-1; } |
|
156 static bool valid(Node n) { return n.n!=-1; } |
|
157 |
|
158 static void setInvalid(Edge &e) { e.n=-1; } |
|
159 static void setInvalid(Node &n) { n.n=-1; } |
|
160 |
|
161 template <typename It> static It getNext(It it) |
|
162 { It tmp(it); return next(tmp); } |
|
163 |
|
164 NodeIt& next(NodeIt& it) const { |
|
165 it.n=nodes[it.n].next; |
|
166 return it; |
|
167 } |
|
168 OutEdgeIt& next(OutEdgeIt& it) const |
|
169 { it.n=edges[it.n].next_out; return it; } |
|
170 InEdgeIt& next(InEdgeIt& it) const |
|
171 { it.n=edges[it.n].next_in; return it; } |
|
172 EdgeIt& next(EdgeIt& it) const { |
|
173 if(edges[it.n].next_in!=-1) { |
|
174 it.n=edges[it.n].next_in; |
|
175 } |
|
176 else { |
|
177 int n; |
|
178 for(n=nodes[edges[it.n].head].next; |
|
179 n!=-1 && nodes[n].first_in == -1; |
|
180 n = nodes[n].next) ; |
|
181 it.n = (n==-1)?-1:nodes[n].first_in; |
|
182 } |
|
183 return it; |
|
184 } |
|
185 |
|
186 static int id(Node v) { return v.n; } |
143 static int id(Node v) { return v.n; } |
187 static int id(Edge e) { return e.n; } |
144 static int id(Edge e) { return e.n; } |
188 |
145 |
189 /// Adds a new node to the graph. |
146 /// Adds a new node to the graph. |
190 |
147 |
248 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); |
205 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); |
249 i!=dyn_edge_maps.end(); ++i) (**i).add(e); |
206 i!=dyn_edge_maps.end(); ++i) (**i).add(e); |
250 |
207 |
251 return e; |
208 return e; |
252 } |
209 } |
253 |
210 |
|
211 /// Finds an edge between two nodes. |
|
212 |
|
213 /// Finds an edge from node \c u to node \c v. |
|
214 /// |
|
215 /// If \c prev is \ref INVALID (this is the default value), then |
|
216 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
217 /// the next edge from \c u to \c v after \c prev. |
|
218 /// \return The found edge or INVALID if there is no such an edge. |
|
219 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
|
220 { |
|
221 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; |
|
222 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; |
|
223 prev.n=e; |
|
224 return prev; |
|
225 } |
|
226 |
254 private: |
227 private: |
255 void eraseEdge(int n) { |
228 void eraseEdge(int n) { |
256 |
229 |
257 if(edges[n].next_in!=-1) |
230 if(edges[n].next_in!=-1) |
258 edges[edges[n].next_in].prev_in = edges[n].prev_in; |
231 edges[edges[n].next_in].prev_in = edges[n].prev_in; |
322 Node() {} |
295 Node() {} |
323 Node (Invalid) { n=-1; } |
296 Node (Invalid) { n=-1; } |
324 bool operator==(const Node i) const {return n==i.n;} |
297 bool operator==(const Node i) const {return n==i.n;} |
325 bool operator!=(const Node i) const {return n!=i.n;} |
298 bool operator!=(const Node i) const {return n!=i.n;} |
326 bool operator<(const Node i) const {return n<i.n;} |
299 bool operator<(const Node i) const {return n<i.n;} |
|
300 // ///Validity check |
|
301 // operator bool() { return n!=-1; } |
327 }; |
302 }; |
328 |
303 |
329 class NodeIt : public Node { |
304 class NodeIt : public Node { |
|
305 const ListGraph *G; |
330 friend class ListGraph; |
306 friend class ListGraph; |
331 public: |
307 public: |
332 NodeIt() : Node() { } |
308 NodeIt() : Node() { } |
333 NodeIt(Invalid i) : Node(i) { } |
309 NodeIt(Invalid i) : Node(i) { } |
334 NodeIt(const ListGraph& G) : Node(G.first_node) { } |
310 NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { } |
335 ///\todo Undocumented conversion Node -\> NodeIt. |
311 ///\todo Undocumented conversion Node -\> NodeIt. |
336 NodeIt(const ListGraph& G, const Node &n) : Node(n) { } |
312 NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { } |
|
313 NodeIt &operator++() { |
|
314 n=G->nodes[n].next; |
|
315 return *this; |
|
316 } |
|
317 // ///Validity check |
|
318 // operator bool() { return Node::operator bool(); } |
337 }; |
319 }; |
338 |
320 |
339 class Edge { |
321 class Edge { |
340 friend class ListGraph; |
322 friend class ListGraph; |
341 template <typename T> friend class EdgeMap; |
323 template <typename T> friend class EdgeMap; |
362 bool operator!=(const Edge i) const {return n!=i.n;} |
344 bool operator!=(const Edge i) const {return n!=i.n;} |
363 bool operator<(const Edge i) const {return n<i.n;} |
345 bool operator<(const Edge i) const {return n<i.n;} |
364 ///\bug This is a workaround until somebody tells me how to |
346 ///\bug This is a workaround until somebody tells me how to |
365 ///make class \c SymListGraph::SymEdgeMap friend of Edge |
347 ///make class \c SymListGraph::SymEdgeMap friend of Edge |
366 int &idref() {return n;} |
348 int &idref() {return n;} |
367 const int &idref() const {return n;} |
349 const int &idref() const {return n;} |
368 }; |
350 // ///Validity check |
|
351 // operator bool() { return n!=-1; } |
|
352 }; |
369 |
353 |
370 class EdgeIt : public Edge { |
354 class EdgeIt : public Edge { |
|
355 const ListGraph *G; |
371 friend class ListGraph; |
356 friend class ListGraph; |
372 public: |
357 public: |
373 EdgeIt(const ListGraph& G) : Edge() { |
358 EdgeIt(const ListGraph& _G) : Edge(), G(&_G) { |
374 int m; |
359 int m; |
375 for(m=G.first_node; |
360 for(m=_G.first_node; |
376 m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next); |
361 m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next); |
377 n = (m==-1)?-1:G.nodes[m].first_in; |
362 n = (m==-1)?-1:_G.nodes[m].first_in; |
378 } |
363 } |
379 EdgeIt (Invalid i) : Edge(i) { } |
364 EdgeIt (Invalid i) : Edge(i) { } |
|
365 EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } |
380 EdgeIt() : Edge() { } |
366 EdgeIt() : Edge() { } |
381 ///\bug This is a workaround until somebody tells me how to |
367 ///\bug This is a workaround until somebody tells me how to |
382 ///make class \c SymListGraph::SymEdgeMap friend of Edge |
368 ///make class \c SymListGraph::SymEdgeMap friend of Edge |
383 int &idref() {return n;} |
369 int &idref() {return n;} |
|
370 EdgeIt &operator++() { |
|
371 if(G->edges[n].next_in!=-1) n=G->edges[n].next_in; |
|
372 else { |
|
373 int nn; |
|
374 for(nn=G->nodes[G->edges[n].head].next; |
|
375 nn!=-1 && G->nodes[nn].first_in == -1; |
|
376 nn = G->nodes[nn].next) ; |
|
377 n = (nn==-1)?-1:G->nodes[nn].first_in; |
|
378 } |
|
379 return *this; |
|
380 } |
|
381 // ///Validity check |
|
382 // operator bool() { return Edge::operator bool(); } |
384 }; |
383 }; |
385 |
384 |
386 class OutEdgeIt : public Edge { |
385 class OutEdgeIt : public Edge { |
|
386 const ListGraph *G; |
387 friend class ListGraph; |
387 friend class ListGraph; |
388 public: |
388 public: |
389 OutEdgeIt() : Edge() { } |
389 OutEdgeIt() : Edge() { } |
|
390 OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } |
390 OutEdgeIt (Invalid i) : Edge(i) { } |
391 OutEdgeIt (Invalid i) : Edge(i) { } |
391 |
392 |
392 OutEdgeIt(const ListGraph& G,const Node v) |
393 OutEdgeIt(const ListGraph& _G,const Node v) |
393 : Edge(G.nodes[v.n].first_out) {} |
394 : Edge(_G.nodes[v.n].first_out), G(&_G) {} |
|
395 OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; } |
|
396 // ///Validity check |
|
397 // operator bool() { return Edge::operator bool(); } |
394 }; |
398 }; |
395 |
399 |
396 class InEdgeIt : public Edge { |
400 class InEdgeIt : public Edge { |
|
401 const ListGraph *G; |
397 friend class ListGraph; |
402 friend class ListGraph; |
398 public: |
403 public: |
399 InEdgeIt() : Edge() { } |
404 InEdgeIt() : Edge() { } |
|
405 InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } |
400 InEdgeIt (Invalid i) : Edge(i) { } |
406 InEdgeIt (Invalid i) : Edge(i) { } |
401 InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {} |
407 InEdgeIt(const ListGraph& _G,Node v) |
|
408 : Edge(_G.nodes[v.n].first_in), G(&_G) { } |
|
409 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } |
|
410 // ///Validity check |
|
411 // operator bool() { return Edge::operator bool(); } |
402 }; |
412 }; |
403 |
413 |
404 template <typename T> class NodeMap : public DynMapBase<Node> |
414 template <typename T> class NodeMap : public DynMapBase<Node> |
405 { |
415 { |
406 std::vector<T> container; |
416 std::vector<T> container; |
836 int maxEdgeId() const { return 0; } //FIXME: What is this? |
846 int maxEdgeId() const { return 0; } //FIXME: What is this? |
837 |
847 |
838 Node tail(Edge e) const { return INVALID; } |
848 Node tail(Edge e) const { return INVALID; } |
839 Node head(Edge e) const { return INVALID; } |
849 Node head(Edge e) const { return INVALID; } |
840 |
850 |
841 Node aNode(OutEdgeIt e) const { return INVALID; } |
|
842 Node aNode(InEdgeIt e) const { return INVALID; } |
|
843 |
|
844 Node bNode(OutEdgeIt e) const { return INVALID; } |
|
845 Node bNode(InEdgeIt e) const { return INVALID; } |
|
846 |
|
847 NodeIt& first(NodeIt& v) const { |
851 NodeIt& first(NodeIt& v) const { |
848 v=NodeIt(*this); return v; } |
852 v=NodeIt(*this); return v; } |
849 EdgeIt& first(EdgeIt& e) const { |
853 EdgeIt& first(EdgeIt& e) const { |
850 e=EdgeIt(*this); return e; } |
854 e=EdgeIt(*this); return e; } |
851 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
855 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
852 e=OutEdgeIt(*this,v); return e; } |
856 e=OutEdgeIt(*this,v); return e; } |
853 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
857 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
854 e=InEdgeIt(*this,v); return e; } |
858 e=InEdgeIt(*this,v); return e; } |
855 |
859 |
856 // template< typename It > |
|
857 // It first() const { It e; first(e); return e; } |
|
858 |
|
859 // template< typename It > |
|
860 // It first(Node v) const { It e; first(e,v); return e; } |
|
861 |
|
862 bool valid(Edge e) const { return false; } |
|
863 bool valid(Node n) const { return n.n!=-1; } |
|
864 |
|
865 void setInvalid(Edge &e) { } |
|
866 void setInvalid(Node &n) { n.n=-1; } |
|
867 |
|
868 template <typename It> It getNext(It it) const |
|
869 { It tmp(it); return next(tmp); } |
|
870 |
|
871 NodeIt& next(NodeIt& it) const { |
|
872 it.n=nodes[it.n].next; |
|
873 return it; |
|
874 } |
|
875 OutEdgeIt& next(OutEdgeIt& it) const { return it; } |
|
876 InEdgeIt& next(InEdgeIt& it) const { return it; } |
|
877 EdgeIt& next(EdgeIt& it) const { return it; } |
|
878 |
|
879 int id(Node v) const { return v.n; } |
860 int id(Node v) const { return v.n; } |
880 int id(Edge e) const { return -1; } |
861 int id(Edge e) const { return -1; } |
881 |
862 |
882 /// Adds a new node to the graph. |
863 /// Adds a new node to the graph. |
883 |
864 |
953 bool operator!=(const Node i) const {return n!=i.n;} |
940 bool operator!=(const Node i) const {return n!=i.n;} |
954 bool operator<(const Node i) const {return n<i.n;} |
941 bool operator<(const Node i) const {return n<i.n;} |
955 }; |
942 }; |
956 |
943 |
957 class NodeIt : public Node { |
944 class NodeIt : public Node { |
|
945 const NodeSet *G; |
958 friend class NodeSet; |
946 friend class NodeSet; |
959 public: |
947 public: |
960 NodeIt() : Node() { } |
948 NodeIt() : Node() { } |
|
949 NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { } |
961 NodeIt(Invalid i) : Node(i) { } |
950 NodeIt(Invalid i) : Node(i) { } |
962 NodeIt(const NodeSet& G) : Node(G.first_node) { } |
951 NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { } |
963 ///\todo Undocumented conversion Node -\> NodeIt. |
952 NodeIt &operator++() { |
964 NodeIt(const NodeSet& G, const Node &n) : Node(n) { } |
953 n=G->nodes[n].next; |
965 |
954 return *this; |
|
955 } |
966 }; |
956 }; |
967 |
957 |
968 class Edge { |
958 class Edge { |
969 //friend class NodeSet; |
959 //friend class NodeSet; |
970 //template <typename T> friend class EdgeMap; |
960 //template <typename T> friend class EdgeMap; |
991 |
981 |
992 class EdgeIt : public Edge { |
982 class EdgeIt : public Edge { |
993 //friend class NodeSet; |
983 //friend class NodeSet; |
994 public: |
984 public: |
995 EdgeIt(const NodeSet& G) : Edge() { } |
985 EdgeIt(const NodeSet& G) : Edge() { } |
|
986 EdgeIt(const NodeSet&, Edge) : Edge() { } |
996 EdgeIt (Invalid i) : Edge(i) { } |
987 EdgeIt (Invalid i) : Edge(i) { } |
997 EdgeIt() : Edge() { } |
988 EdgeIt() : Edge() { } |
998 ///\bug This is a workaround until somebody tells me how to |
989 ///\bug This is a workaround until somebody tells me how to |
999 ///make class \c SymNodeSet::SymEdgeMap friend of Edge |
990 ///make class \c SymNodeSet::SymEdgeMap friend of Edge |
1000 // int idref() {return -1;} |
991 // int idref() {return -1;} |
|
992 EdgeIt operator++() { return INVALID; } |
1001 }; |
993 }; |
1002 |
994 |
1003 class OutEdgeIt : public Edge { |
995 class OutEdgeIt : public Edge { |
1004 friend class NodeSet; |
996 friend class NodeSet; |
1005 public: |
997 public: |
1006 OutEdgeIt() : Edge() { } |
998 OutEdgeIt() : Edge() { } |
|
999 OutEdgeIt(const NodeSet&, Edge) : Edge() { } |
1007 OutEdgeIt (Invalid i) : Edge(i) { } |
1000 OutEdgeIt (Invalid i) : Edge(i) { } |
1008 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {} |
1001 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {} |
|
1002 OutEdgeIt operator++() { return INVALID; } |
1009 }; |
1003 }; |
1010 |
1004 |
1011 class InEdgeIt : public Edge { |
1005 class InEdgeIt : public Edge { |
1012 friend class NodeSet; |
1006 friend class NodeSet; |
1013 public: |
1007 public: |
1014 InEdgeIt() : Edge() { } |
1008 InEdgeIt() : Edge() { } |
|
1009 InEdgeIt(const NodeSet&, Edge) : Edge() { } |
1015 InEdgeIt (Invalid i) : Edge(i) { } |
1010 InEdgeIt (Invalid i) : Edge(i) { } |
1016 InEdgeIt(const NodeSet& G,Node v) :Edge() {} |
1011 InEdgeIt(const NodeSet& G,Node v) :Edge() {} |
|
1012 InEdgeIt operator++() { return INVALID; } |
1017 }; |
1013 }; |
1018 |
1014 |
1019 template <typename T> class NodeMap : public DynMapBase<Node> |
1015 template <typename T> class NodeMap : public DynMapBase<Node> |
1020 { |
1016 { |
1021 std::vector<T> container; |
1017 std::vector<T> container; |
1197 |
1193 |
1198 class NodeIt : public NodeGraphType::NodeIt { |
1194 class NodeIt : public NodeGraphType::NodeIt { |
1199 friend class EdgeSet; |
1195 friend class EdgeSet; |
1200 public: |
1196 public: |
1201 NodeIt() : NodeGraphType::NodeIt() { } |
1197 NodeIt() : NodeGraphType::NodeIt() { } |
|
1198 NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { } |
1202 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} |
1199 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} |
1203 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { } |
1200 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { } |
1204 NodeIt(const typename NodeGraphType::NodeIt &n) |
1201 NodeIt(const typename NodeGraphType::NodeIt &n) |
1205 : NodeGraphType::NodeIt(n) {} |
1202 : NodeGraphType::NodeIt(n) {} |
1206 ///\todo Undocumented conversion Node -\> NodeIt. |
|
1207 NodeIt(const EdgeSet& _G, const Node &n) |
|
1208 : NodeGraphType::NodeIt(_G.G,n) { } |
|
1209 |
1203 |
1210 operator Node() { return Node(*this);} |
1204 operator Node() { return Node(*this);} |
|
1205 NodeIt &operator++() |
|
1206 { this->NodeGraphType::NodeIt::operator++(); return *this;} |
1211 }; |
1207 }; |
1212 |
1208 |
1213 private: |
1209 private: |
1214 //Edges are double linked. |
1210 //Edges are double linked. |
1215 //The free edges are only single linked using the "next_in" field. |
1211 //The free edges are only single linked using the "next_in" field. |
1308 ///its name would suggests... |
1304 ///its name would suggests... |
1309 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
1305 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
1310 |
1306 |
1311 Node tail(Edge e) const { return edges[e.n].tail; } |
1307 Node tail(Edge e) const { return edges[e.n].tail; } |
1312 Node head(Edge e) const { return edges[e.n].head; } |
1308 Node head(Edge e) const { return edges[e.n].head; } |
1313 |
|
1314 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } |
|
1315 Node aNode(InEdgeIt e) const { return edges[e.n].head; } |
|
1316 |
|
1317 Node bNode(OutEdgeIt e) const { return edges[e.n].head; } |
|
1318 Node bNode(InEdgeIt e) const { return edges[e.n].tail; } |
|
1319 |
1309 |
1320 NodeIt& first(NodeIt& v) const { |
1310 NodeIt& first(NodeIt& v) const { |
1321 v=NodeIt(*this); return v; } |
1311 v=NodeIt(*this); return v; } |
1322 EdgeIt& first(EdgeIt& e) const { |
1312 EdgeIt& first(EdgeIt& e) const { |
1323 e=EdgeIt(*this); return e; } |
1313 e=EdgeIt(*this); return e; } |
1324 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
1314 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
1325 e=OutEdgeIt(*this,v); return e; } |
1315 e=OutEdgeIt(*this,v); return e; } |
1326 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
1316 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
1327 e=InEdgeIt(*this,v); return e; } |
1317 e=InEdgeIt(*this,v); return e; } |
1328 |
1318 |
1329 // template< typename It > |
|
1330 // It first() const { It e; first(e); return e; } |
|
1331 |
|
1332 // template< typename It > |
|
1333 // It first(Node v) const { It e; first(e,v); return e; } |
|
1334 |
|
1335 bool valid(Edge e) const { return e.n!=-1; } |
|
1336 bool valid(Node n) const { return G.valid(n); } |
|
1337 |
|
1338 void setInvalid(Edge &e) { e.n=-1; } |
|
1339 void setInvalid(Node &n) { G.setInvalid(n); } |
|
1340 |
|
1341 template <typename It> It getNext(It it) const |
|
1342 { It tmp(it); return next(tmp); } |
|
1343 |
|
1344 NodeIt& next(NodeIt& it) const { G.next(it); return it; } |
|
1345 OutEdgeIt& next(OutEdgeIt& it) const |
|
1346 { it.n=edges[it.n].next_out; return it; } |
|
1347 InEdgeIt& next(InEdgeIt& it) const |
|
1348 { it.n=edges[it.n].next_in; return it; } |
|
1349 EdgeIt& next(EdgeIt& it) const { |
|
1350 if(edges[it.n].next_in!=-1) { |
|
1351 it.n=edges[it.n].next_in; |
|
1352 } |
|
1353 else { |
|
1354 NodeIt n(*this,edges[it.n].head); |
|
1355 for(n=next(n); |
|
1356 valid(n) && nodes[n].first_in == -1; |
|
1357 next(n)) ; |
|
1358 it.n = (valid(n))?-1:nodes[n].first_in; |
|
1359 } |
|
1360 return it; |
|
1361 } |
|
1362 |
|
1363 int id(Edge e) const { return e.n; } |
1319 int id(Edge e) const { return e.n; } |
1364 |
1320 |
1365 /// Adds a new node to the graph. |
1321 /// Adds a new node to the graph. |
1366 Node addNode() { return G.addNode(); } |
1322 Node addNode() { return G.addNode(); } |
1367 |
1323 |
1396 i!=dyn_edge_maps.end(); ++i) (**i).add(e); |
1352 i!=dyn_edge_maps.end(); ++i) (**i).add(e); |
1397 |
1353 |
1398 return e; |
1354 return e; |
1399 } |
1355 } |
1400 |
1356 |
|
1357 /// Finds an edge between two nodes. |
|
1358 |
|
1359 /// Finds an edge from node \c u to node \c v. |
|
1360 /// |
|
1361 /// If \c prev is \ref INVALID (this is the default value), then |
|
1362 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
1363 /// the next edge from \c u to \c v after \c prev. |
|
1364 /// \return The found edge or INVALID if there is no such an edge. |
|
1365 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
|
1366 { |
|
1367 int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out; |
|
1368 while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out; |
|
1369 prev.n=e; |
|
1370 return prev; |
|
1371 } |
|
1372 |
1401 private: |
1373 private: |
1402 void eraseEdge(int n) { |
1374 void eraseEdge(int n) { |
1403 |
1375 |
1404 if(edges[n].next_in!=-1) |
1376 if(edges[n].next_in!=-1) |
1405 edges[edges[n].next_in].prev_in = edges[n].prev_in; |
1377 edges[edges[n].next_in].prev_in = edges[n].prev_in; |
1481 |
1453 |
1482 class EdgeIt : public Edge { |
1454 class EdgeIt : public Edge { |
1483 friend class EdgeSet; |
1455 friend class EdgeSet; |
1484 template <typename T> friend class EdgeMap; |
1456 template <typename T> friend class EdgeMap; |
1485 |
1457 |
1486 |
1458 const EdgeSet *G; |
1487 public: |
1459 public: |
1488 EdgeIt(const EdgeSet& G) : Edge() { |
1460 EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) { |
1489 // typename NodeGraphType::Node m; |
1461 // typename NodeGraphType::Node m; |
1490 NodeIt m; |
1462 NodeIt m; |
1491 for(G.first(m); |
1463 for(G->first(m); |
1492 G.valid(m) && G.nodes[m].first_in == -1; G.next(m)); |
1464 m!=INVALID && G->nodes[m].first_in == -1; ++m); |
1493 //AJJAJ! This is a non sense!!!!!!! |
1465 ///\bug AJJAJ! This is a non sense!!!!!!! |
1494 this->n = G.valid(m)?-1:G.nodes[m].first_in; |
1466 this->n = m!=INVALID?-1:G->nodes[m].first_in; |
1495 } |
1467 } |
|
1468 EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } |
1496 EdgeIt (Invalid i) : Edge(i) { } |
1469 EdgeIt (Invalid i) : Edge(i) { } |
1497 EdgeIt() : Edge() { } |
1470 EdgeIt() : Edge() { } |
1498 ///\bug This is a workaround until somebody tells me how to |
1471 ///. |
|
1472 |
|
1473 ///\bug UNIMPLEMENTED!!!!! |
|
1474 // |
|
1475 EdgeIt &operator++() { |
|
1476 return *this; |
|
1477 } |
|
1478 ///\bug This is a workaround until somebody tells me how to |
1499 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge |
1479 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge |
1500 int &idref() {return this->n;} |
1480 int &idref() {return this->n;} |
1501 }; |
1481 }; |
1502 |
1482 |
1503 class OutEdgeIt : public Edge { |
1483 class OutEdgeIt : public Edge { |
|
1484 const EdgeSet *G; |
1504 friend class EdgeSet; |
1485 friend class EdgeSet; |
1505 public: |
1486 public: |
1506 OutEdgeIt() : Edge() { } |
1487 OutEdgeIt() : Edge() { } |
1507 OutEdgeIt (Invalid i) : Edge(i) { } |
1488 OutEdgeIt (Invalid i) : Edge(i) { } |
1508 |
1489 OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } |
1509 OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { } |
1490 |
|
1491 OutEdgeIt(const EdgeSet& _G,const Node v) : |
|
1492 Edge(_G.nodes[v].first_out), G(&_G) { } |
|
1493 OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; } |
1510 }; |
1494 }; |
1511 |
1495 |
1512 class InEdgeIt : public Edge { |
1496 class InEdgeIt : public Edge { |
|
1497 const EdgeSet *G; |
1513 friend class EdgeSet; |
1498 friend class EdgeSet; |
1514 public: |
1499 public: |
1515 InEdgeIt() : Edge() { } |
1500 InEdgeIt() : Edge() { } |
1516 InEdgeIt (Invalid i) : Edge(i) { } |
1501 InEdgeIt (Invalid i) : Edge(i) { } |
1517 InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { } |
1502 InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } |
|
1503 InEdgeIt(const EdgeSet& _G,Node v) |
|
1504 : Edge(_G.nodes[v].first_in), G(&_G) { } |
|
1505 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } |
1518 }; |
1506 }; |
1519 |
1507 |
1520 template <typename T> class NodeMap : |
1508 template <typename T> class NodeMap : |
1521 public NodeGraphType::template NodeMap<T> |
1509 public NodeGraphType::template NodeMap<T> |
1522 { |
1510 { |
1552 EdgeMap(const EdgeSet &_G) : |
1540 EdgeMap(const EdgeSet &_G) : |
1553 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) |
1541 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) |
1554 { |
1542 { |
1555 //FIXME: What if there are empty Id's? |
1543 //FIXME: What if there are empty Id's? |
1556 //FIXME: Can I use 'this' in a constructor? |
1544 //FIXME: Can I use 'this' in a constructor? |
1557 G->dyn_edge_maps.push_back(this); |
1545 this->G->dyn_edge_maps.push_back(this); |
1558 } |
1546 } |
1559 EdgeMap(const EdgeSet &_G,const T &t) : |
1547 EdgeMap(const EdgeSet &_G,const T &t) : |
1560 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) |
1548 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) |
1561 { |
1549 { |
1562 G->dyn_edge_maps.push_back(this); |
1550 this->G->dyn_edge_maps.push_back(this); |
1563 } |
1551 } |
1564 EdgeMap(const EdgeMap<T> &m) : |
1552 EdgeMap(const EdgeMap<T> &m) : |
1565 DynMapBase<Edge>(*m.G), container(m.container) |
1553 DynMapBase<Edge>(*m.G), container(m.container) |
1566 { |
1554 { |
1567 G->dyn_edge_maps.push_back(this); |
1555 this->G->dyn_edge_maps.push_back(this); |
1568 } |
1556 } |
1569 |
1557 |
1570 ///\todo It can copy between different types. |
1558 ///\todo It can copy between different types. |
1571 /// |
1559 /// |
1572 template<typename TT> EdgeMap(const EdgeMap<TT> &m) : |
1560 template<typename TT> EdgeMap(const EdgeMap<TT> &m) : |
1573 DynMapBase<Edge>(*m.G), container(m.container.size()) |
1561 DynMapBase<Edge>(*m.G), container(m.container.size()) |
1574 { |
1562 { |
1575 G->dyn_edge_maps.push_back(this); |
1563 this->G->dyn_edge_maps.push_back(this); |
1576 typename std::vector<TT>::const_iterator i; |
1564 typename std::vector<TT>::const_iterator i; |
1577 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
1565 for(typename std::vector<TT>::const_iterator i=m.container.begin(); |
1578 i!=m.container.end(); |
1566 i!=m.container.end(); |
1579 i++) |
1567 i++) |
1580 container.push_back(*i); |
1568 container.push_back(*i); |
1581 } |
1569 } |
1582 ~EdgeMap() |
1570 ~EdgeMap() |
1583 { |
1571 { |
1584 if(G) { |
1572 if(this->G) { |
1585 typename std::vector<DynMapBase<Edge>* >::iterator i; |
1573 typename std::vector<DynMapBase<Edge>* >::iterator i; |
1586 for(i=G->dyn_edge_maps.begin(); |
1574 for(i=this->G->dyn_edge_maps.begin(); |
1587 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; |
1575 i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ; |
1588 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... |
1576 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... |
1589 //A better way to do that: (Is this really important?) |
1577 //A better way to do that: (Is this really important?) |
1590 if(*i==this) { |
1578 if(*i==this) { |
1591 *i=G->dyn_edge_maps.back(); |
1579 *i=this->G->dyn_edge_maps.back(); |
1592 G->dyn_edge_maps.pop_back(); |
1580 this->G->dyn_edge_maps.pop_back(); |
1593 } |
1581 } |
1594 } |
1582 } |
1595 } |
1583 } |
1596 |
1584 |
1597 void add(const Edge k) |
1585 void add(const Edge k) |
1600 } |
1588 } |
1601 void erase(const Edge) { } |
1589 void erase(const Edge) { } |
1602 |
1590 |
1603 ///\bug This doesn't work. Why? |
1591 ///\bug This doesn't work. Why? |
1604 /// void set(Edge n, T a) { container[n.n]=a; } |
1592 /// void set(Edge n, T a) { container[n.n]=a; } |
1605 void set(Edge n, T a) { container[G->id(n)]=a; } |
1593 void set(Edge n, T a) { container[this->G->id(n)]=a; } |
1606 //T get(Edge n) const { return container[n.n]; } |
1594 //T get(Edge n) const { return container[n.n]; } |
1607 typename std::vector<T>::reference |
1595 typename std::vector<T>::reference |
1608 ///\bug This doesn't work. Why? |
1596 ///\bug This doesn't work. Why? |
1609 /// operator[](Edge n) { return container[n.n]; } |
1597 /// operator[](Edge n) { return container[n.n]; } |
1610 operator[](Edge n) { return container[G->id(n)]; } |
1598 operator[](Edge n) { return container[this->G->id(n)]; } |
1611 typename std::vector<T>::const_reference |
1599 typename std::vector<T>::const_reference |
1612 ///\bug This doesn't work. Why? |
1600 ///\bug This doesn't work. Why? |
1613 /// operator[](Edge n) const { return container[n.n]; } |
1601 /// operator[](Edge n) const { return container[n.n]; } |
1614 operator[](Edge n) const { return container[G->id(n)]; } |
1602 operator[](Edge n) const { return container[this->G->id(n)]; } |
1615 |
1603 |
1616 ///\warning There is no safety check at all! |
1604 ///\warning There is no safety check at all! |
1617 ///Using operator = between maps attached to different graph may |
1605 ///Using operator = between maps attached to different graph may |
1618 ///cause serious problem. |
1606 ///cause serious problem. |
1619 ///\todo Is this really so? |
1607 ///\todo Is this really so? |