Changeset 946:c94ef40a22ce in lemon-0.x for src/lemon/list_graph.h
- Timestamp:
- 10/28/04 00:38:50 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/list_graph.h
r937 r946 1 /* -*- C++ -*- 2 * src/lemon/list_graph.h - Part of LEMON, a generic C++ optimization library 3 * 4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Combinatorial Optimization Research Group, EGRES). 6 * 7 * Permission to use, modify and distribute this software is granted 8 * provided that this copyright notice appears in all copies. For 9 * precise terms see the accompanying LICENSE file. 10 * 11 * This software is provided "AS IS" with no warranty of any kind, 12 * express or implied, and with no claim as to its suitability for any 13 * purpose. 14 * 15 */ 1 // -*- c++ -*- 16 2 17 3 #ifndef LEMON_LIST_GRAPH_H 18 4 #define LEMON_LIST_GRAPH_H 19 5 20 ///\ingroup graphs 21 ///\file 22 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes. 23 24 #include <vector> 25 #include <climits> 26 27 #include <lemon/invalid.h> 28 29 #include <lemon/map_registry.h> 30 #include <lemon/array_map.h> 31 32 #include <lemon/map_defines.h> 6 #include <lemon/erasable_graph_extender.h> 7 #include <lemon/clearable_graph_extender.h> 8 #include <lemon/extendable_graph_extender.h> 9 10 #include <lemon/idmappable_graph_extender.h> 11 12 #include <lemon/iterable_graph_extender.h> 13 14 #include <lemon/alteration_observer_registry.h> 15 16 #include <lemon/default_map.h> 33 17 34 18 35 19 namespace lemon { 36 20 37 /// \addtogroup graphs 38 /// @{ 39 40 ///A list graph class. 41 42 ///This is a simple and fast erasable graph implementation. 43 /// 44 ///It conforms to the 45 ///\ref skeleton::ErasableGraph "ErasableGraph" concept. 46 ///\sa skeleton::ErasableGraph. 47 class ListGraph { 48 49 //Nodes are double linked. 50 //The free nodes are only single linked using the "next" field. 51 struct NodeT 52 { 21 class ListGraphBase { 22 23 struct NodeT { 53 24 int first_in,first_out; 54 25 int prev, next; 55 26 }; 56 //Edges are double linked. 57 //The free edges are only single linked using the "next_in" field. 58 struct EdgeT 59 { 27 28 struct EdgeT { 60 29 int head, tail; 61 30 int prev_in, prev_out; … … 64 33 65 34 std::vector<NodeT> nodes; 66 //The first node 35 67 36 int first_node; 68 //The first free node 37 69 38 int first_free_node; 39 70 40 std::vector<EdgeT> edges; 71 //The first free edge 41 72 42 int first_free_edge; 73 43 74 44 public: 75 45 76 typedef ListGraph Graph; 77 78 class Node; 79 class Edge; 80 81 82 public: 83 84 class NodeIt; 85 class EdgeIt; 86 class OutEdgeIt; 87 class InEdgeIt; 88 89 // Create map registries. 90 CREATE_MAP_REGISTRIES; 91 // Create node and edge maps. 92 CREATE_MAPS(ArrayMap); 93 94 public: 95 96 ListGraph() 46 typedef ListGraphBase Graph; 47 48 class Node { 49 friend class Graph; 50 protected: 51 52 int id; 53 Node(int pid) { id = pid;} 54 55 public: 56 Node() {} 57 Node (Invalid) { id = -1; } 58 bool operator==(const Node& node) const {return id == node.id;} 59 bool operator!=(const Node& node) const {return id != node.id;} 60 bool operator<(const Node& node) const {return id < node.id;} 61 }; 62 63 class Edge { 64 friend class Graph; 65 protected: 66 67 int id; 68 Edge(int pid) { id = pid;} 69 70 public: 71 Edge() {} 72 Edge (Invalid) { id = -1; } 73 bool operator==(const Edge& edge) const {return id == edge.id;} 74 bool operator!=(const Edge& edge) const {return id != edge.id;} 75 bool operator<(const Edge& edge) const {return id < edge.id;} 76 }; 77 78 79 80 ListGraphBase() 97 81 : nodes(), first_node(-1), 98 82 first_free_node(-1), edges(), first_free_edge(-1) {} 99 83 100 ListGraph(const ListGraph &_g) 101 : nodes(_g.nodes), first_node(_g.first_node), 102 first_free_node(_g.first_free_node), edges(_g.edges), 103 first_free_edge(_g.first_free_edge) {} 104 105 /// \bug In the vector can be hole if a node is erased from the graph. 106 ///Number of nodes. 107 int nodeNum() const { return nodes.size(); } 108 ///Number of edges. 109 int edgeNum() const { return edges.size(); } 110 111 ///Set the expected maximum number of edges. 112 113 ///With this function, it is possible to set the expected number of edges. 114 ///The use of this fasten the building of the graph and makes 84 115 85 ///it possible to avoid the superfluous memory allocation. 116 86 void reserveEdge(int n) { edges.reserve(n); }; … … 121 91 ///\sa id(Node) 122 92 int maxNodeId() const { return nodes.size()-1; } 93 123 94 /// Maximum edge ID. 124 95 … … 127 98 int maxEdgeId() const { return edges.size()-1; } 128 99 129 Node tail(Edge e) const { return edges[e.n].tail; } 130 Node head(Edge e) const { return edges[e.n].head; } 131 132 NodeIt& first(NodeIt& v) const { 133 v=NodeIt(*this); return v; } 134 EdgeIt& first(EdgeIt& e) const { 135 e=EdgeIt(*this); return e; } 136 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 137 e=OutEdgeIt(*this,v); return e; } 138 InEdgeIt& first(InEdgeIt& e, const Node v) const { 139 e=InEdgeIt(*this,v); return e; } 140 141 /// Node ID. 142 143 /// The ID of a valid Node is a nonnegative integer not greater than 144 /// \ref maxNodeId(). The range of the ID's is not surely continuous 145 /// and the greatest node ID can be actually less then \ref maxNodeId(). 146 /// 147 /// The ID of the \ref INVALID node is -1. 148 ///\return The ID of the node \c v. 149 static int id(Node v) { return v.n; } 150 /// Edge ID. 151 152 /// The ID of a valid Edge is a nonnegative integer not greater than 153 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 154 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 155 /// 156 /// The ID of the \ref INVALID edge is -1. 157 ///\return The ID of the edge \c e. 158 static int id(Edge e) { return e.n; } 100 Node tail(Edge e) const { return edges[e.id].tail; } 101 Node head(Edge e) const { return edges[e.id].head; } 102 103 104 void first(Node& node) const { 105 node.id = first_node; 106 } 107 108 void next(Node& node) const { 109 node.id = nodes[node.id].next; 110 } 111 112 113 void first(Edge& e) const { 114 int n; 115 for(n = first_node; 116 n!=-1 && nodes[n].first_in == -1; 117 n = nodes[n].next); 118 e.id = (n == -1) ? -1 : nodes[n].first_in; 119 } 120 121 void next(Edge& edge) const { 122 if (edges[edge.id].next_in != -1) { 123 edge.id = edges[edge.id].next_in; 124 } else { 125 int n; 126 for(n = nodes[edges[edge.id].head].next; 127 n!=-1 && nodes[n].first_in == -1; 128 n = nodes[n].next); 129 edge.id = (n == -1) ? -1 : nodes[n].first_in; 130 } 131 } 132 133 void firstOut(Edge &e, const Node& v) const { 134 e.id = nodes[v.id].first_out; 135 } 136 void nextOut(Edge &e) const { 137 e.id=edges[e.id].next_out; 138 } 139 140 void firstIn(Edge &e, const Node& v) const { 141 e.id = nodes[v.id].first_in; 142 } 143 void nextIn(Edge &e) const { 144 e.id=edges[e.id].next_in; 145 } 146 147 148 static int id(Node v) { return v.id; } 149 static int id(Edge e) { return e.id; } 159 150 160 151 /// Adds a new node to the graph. … … 162 153 /// \warning It adds the new node to the front of the list. 163 154 /// (i.e. the lastly added node becomes the first.) 164 Node addNode() { 155 Node addNode() { 165 156 int n; 166 157 167 if(first_free_node==-1) 168 { 169 n = nodes.size(); 170 nodes.push_back(NodeT()); 171 } 172 else { 158 if(first_free_node==-1) { 159 n = nodes.size(); 160 nodes.push_back(NodeT()); 161 } else { 173 162 n = first_free_node; 174 163 first_free_node = nodes[n].next; … … 182 171 nodes[n].first_in = nodes[n].first_out = -1; 183 172 184 Node nn; nn.n=n; 185 186 //Update dynamic maps 187 node_maps.add(nn); 188 189 return nn; 173 return Node(n); 190 174 } 191 175 192 176 Edge addEdge(Node u, Node v) { 193 int n; 194 195 if(first_free_edge==-1) 196 { 197 n = edges.size(); 198 edges.push_back(EdgeT()); 199 } 200 else { 177 int n; 178 179 if (first_free_edge == -1) { 180 n = edges.size(); 181 edges.push_back(EdgeT()); 182 } else { 201 183 n = first_free_edge; 202 184 first_free_edge = edges[n].next_in; 203 185 } 204 186 205 edges[n].tail = u.n; edges[n].head = v.n; 206 207 edges[n].next_out = nodes[u.n].first_out; 208 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n; 209 edges[n].next_in = nodes[v.n].first_in; 210 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n; 187 edges[n].tail = u.id; 188 edges[n].head = v.id; 189 190 edges[n].next_out = nodes[u.id].first_out; 191 if(nodes[u.id].first_out != -1) { 192 edges[nodes[u.id].first_out].prev_out = n; 193 } 194 195 edges[n].next_in = nodes[v.id].first_in; 196 if(nodes[v.id].first_in != -1) { 197 edges[nodes[v.id].first_in].prev_in = n; 198 } 199 211 200 edges[n].prev_in = edges[n].prev_out = -1; 212 201 213 nodes[u.n].first_out = nodes[v.n].first_in = n; 214 215 Edge e; e.n=n; 216 217 //Update dynamic maps 218 edge_maps.add(e); 219 220 return e; 221 } 222 223 /// Finds an edge between two nodes. 224 225 /// Finds an edge from node \c u to node \c v. 226 /// 227 /// If \c prev is \ref INVALID (this is the default value), then 228 /// It finds the first edge from \c u to \c v. Otherwise it looks for 229 /// the next edge from \c u to \c v after \c prev. 230 /// \return The found edge or INVALID if there is no such an edge. 231 Edge findEdge(Node u,Node v, Edge prev = INVALID) 232 { 233 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; 234 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; 235 prev.n=e; 236 return prev; 237 } 238 239 private: 240 void eraseEdge(int n) { 241 242 if(edges[n].next_in!=-1) 202 nodes[u.id].first_out = nodes[v.id].first_in = n; 203 204 return Edge(n); 205 } 206 207 void erase(const Node& node) { 208 int n = node.id; 209 210 if(nodes[n].next != -1) { 211 nodes[nodes[n].next].prev = nodes[n].prev; 212 } 213 214 if(nodes[n].prev != -1) { 215 nodes[nodes[n].prev].next = nodes[n].next; 216 } else { 217 first_node = nodes[n].next; 218 } 219 220 nodes[n].next = first_free_node; 221 first_free_node = n; 222 223 } 224 225 void erase(const Edge& edge) { 226 int n = edge.id; 227 228 if(edges[n].next_in!=-1) { 243 229 edges[edges[n].next_in].prev_in = edges[n].prev_in; 244 if(edges[n].prev_in!=-1) 230 } 231 232 if(edges[n].prev_in!=-1) { 245 233 edges[edges[n].prev_in].next_in = edges[n].next_in; 246 else nodes[edges[n].head].first_in = edges[n].next_in; 247 248 if(edges[n].next_out!=-1) 234 } else { 235 nodes[edges[n].head].first_in = edges[n].next_in; 236 } 237 238 239 if(edges[n].next_out!=-1) { 249 240 edges[edges[n].next_out].prev_out = edges[n].prev_out; 250 if(edges[n].prev_out!=-1) 241 } 242 243 if(edges[n].prev_out!=-1) { 251 244 edges[edges[n].prev_out].next_out = edges[n].next_out; 252 else nodes[edges[n].tail].first_out = edges[n].next_out; 245 } else { 246 nodes[edges[n].tail].first_out = edges[n].next_out; 247 } 253 248 254 249 edges[n].next_in = first_free_edge; 255 250 first_free_edge = n; 256 251 257 //Update dynamic maps 258 Edge e; e.n=n; 259 edge_maps.erase(e); 260 261 } 262 263 public: 264 265 void erase(Node nn) { 266 int n=nn.n; 267 268 int m; 269 while((m=nodes[n].first_in)!=-1) eraseEdge(m); 270 while((m=nodes[n].first_out)!=-1) eraseEdge(m); 271 272 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev; 273 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next; 274 else first_node = nodes[n].next; 275 276 nodes[n].next = first_free_node; 277 first_free_node = n; 278 279 //Update dynamic maps 280 node_maps.erase(nn); 281 282 } 283 284 void erase(Edge e) { eraseEdge(e.n); } 252 } 285 253 286 254 void clear() { 287 edge_maps.clear();288 255 edges.clear(); 289 node_maps.clear();290 256 nodes.clear(); 291 first_node=first_free_node=first_free_edge=-1; 292 } 293 294 class Node { 295 friend class ListGraph; 296 template <typename T> friend class NodeMap; 297 298 friend class Edge; 299 friend class OutEdgeIt; 300 friend class InEdgeIt; 301 friend class SymEdge; 302 303 protected: 304 int n; 305 friend int ListGraph::id(Node v); 306 Node(int nn) {n=nn;} 307 public: 308 Node() {} 309 Node (Invalid) { n=-1; } 310 bool operator==(const Node i) const {return n==i.n;} 311 bool operator!=(const Node i) const {return n!=i.n;} 312 bool operator<(const Node i) const {return n<i.n;} 313 // ///Validity check 314 // operator bool() { return n!=-1; } 315 }; 316 317 class NodeIt : public Node { 318 const ListGraph *G; 319 friend class ListGraph; 320 public: 321 NodeIt() : Node() { } 322 NodeIt(Invalid i) : Node(i) { } 323 NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { } 324 NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { } 325 NodeIt &operator++() { 326 n=G->nodes[n].next; 327 return *this; 328 } 329 // ///Validity check 330 // operator bool() { return Node::operator bool(); } 331 }; 332 333 class Edge { 334 friend class ListGraph; 335 template <typename T> friend class EdgeMap; 336 337 friend class SymListGraph; 338 339 friend class Node; 340 friend class NodeIt; 341 protected: 342 int n; 343 friend int ListGraph::id(Edge e); 344 345 public: 346 /// An Edge with id \c n. 347 348 /// \bug It should be 349 /// obtained by a member function of the Graph. 350 Edge(int nn) {n=nn;} 351 352 Edge() { } 353 Edge (Invalid) { n=-1; } 354 bool operator==(const Edge i) const {return n==i.n;} 355 bool operator!=(const Edge i) const {return n!=i.n;} 356 bool operator<(const Edge i) const {return n<i.n;} 357 // ///Validity check 358 // operator bool() { return n!=-1; } 359 }; 360 361 class EdgeIt : public Edge { 362 const ListGraph *G; 363 friend class ListGraph; 364 public: 365 EdgeIt(const ListGraph& _G) : Edge(), G(&_G) { 366 int m; 367 for(m=_G.first_node; 368 m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next); 369 n = (m==-1)?-1:_G.nodes[m].first_in; 370 } 371 EdgeIt (Invalid i) : Edge(i) { } 372 EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } 373 EdgeIt() : Edge() { } 374 EdgeIt &operator++() { 375 if(G->edges[n].next_in!=-1) n=G->edges[n].next_in; 376 else { 377 int nn; 378 for(nn=G->nodes[G->edges[n].head].next; 379 nn!=-1 && G->nodes[nn].first_in == -1; 380 nn = G->nodes[nn].next) ; 381 n = (nn==-1)?-1:G->nodes[nn].first_in; 382 } 383 return *this; 384 } 385 // ///Validity check 386 // operator bool() { return Edge::operator bool(); } 387 }; 388 389 class OutEdgeIt : public Edge { 390 const ListGraph *G; 391 friend class ListGraph; 392 public: 393 OutEdgeIt() : Edge() { } 394 OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } 395 OutEdgeIt (Invalid i) : Edge(i) { } 396 397 OutEdgeIt(const ListGraph& _G,const Node v) 398 : Edge(_G.nodes[v.n].first_out), G(&_G) {} 399 OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; } 400 // ///Validity check 401 // operator bool() { return Edge::operator bool(); } 402 }; 403 404 class InEdgeIt : public Edge { 405 const ListGraph *G; 406 friend class ListGraph; 407 public: 408 InEdgeIt() : Edge() { } 409 InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } 410 InEdgeIt (Invalid i) : Edge(i) { } 411 InEdgeIt(const ListGraph& _G,Node v) 412 : Edge(_G.nodes[v.n].first_in), G(&_G) { } 413 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } 414 // ///Validity check 415 // operator bool() { return Edge::operator bool(); } 416 }; 257 first_node = first_free_node = first_free_edge = -1; 258 } 259 417 260 }; 418 261 419 ///Graph for bidirectional edges. 420 421 ///The purpose of this graph structure is to handle graphs 422 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair 423 ///of oppositely directed edges. 424 ///There is a new edge map type called 425 ///\ref lemon::SymListGraph::SymEdgeMap "SymEdgeMap" 426 ///that complements this 427 ///feature by 428 ///storing shared values for the edge pairs. The usual 429 ///\ref lemon::skeleton::StaticGraph::EdgeMap "EdgeMap" 430 ///can be used 431 ///as well. 432 /// 433 ///The oppositely directed edge can also be obtained easily 434 ///using \ref lemon::SymListGraph::opposite() "opposite()" member function. 435 /// 436 ///Here erase(Edge) deletes a pair of edges. 437 /// 438 ///\todo this date structure need some reconsiderations. Maybe it 439 ///should be implemented independently from ListGraph. 440 /* 441 class SymListGraph : public ListGraph 442 { 443 public: 444 445 typedef SymListGraph Graph; 446 447 // Create symmetric map registry. 448 CREATE_SYM_EDGE_MAP_REGISTRY; 449 // Create symmetric edge map. 450 CREATE_SYM_EDGE_MAP(ArrayMap); 451 452 SymListGraph() : ListGraph() { } 453 SymListGraph(const ListGraph &_g) : ListGraph(_g) { } 454 ///Adds a pair of oppositely directed edges to the graph. 455 Edge addEdge(Node u, Node v) 456 { 457 Edge e = ListGraph::addEdge(u,v); 458 Edge f = ListGraph::addEdge(v,u); 459 sym_edge_maps.add(e); 460 sym_edge_maps.add(f); 461 462 return e; 463 } 464 465 void erase(Node n) { ListGraph::erase(n);} 466 ///The oppositely directed edge. 467 468 ///Returns the oppositely directed 469 ///pair of the edge \c e. 470 static Edge opposite(Edge e) 471 { 472 Edge f; 473 f.n = e.n - 2*(e.n%2) + 1; 474 return f; 475 } 476 477 ///Removes a pair of oppositely directed edges to the graph. 478 void erase(Edge e) { 479 Edge f = opposite(e); 480 sym_edge_maps.erase(e); 481 sym_edge_maps.erase(f); 482 ListGraph::erase(f); 483 ListGraph::erase(e); 484 } 485 };*/ 486 487 class SymListGraph : public ListGraph { 488 typedef ListGraph Parent; 489 public: 490 491 typedef SymListGraph Graph; 492 493 typedef ListGraph::Node Node; 494 typedef ListGraph::NodeIt NodeIt; 495 496 class SymEdge; 497 class SymEdgeIt; 498 499 class Edge; 500 class EdgeIt; 501 class OutEdgeIt; 502 class InEdgeIt; 503 504 template <typename Value> 505 class NodeMap : public Parent::NodeMap<Value> { 506 public: 507 NodeMap(const SymListGraph& g) 508 : SymListGraph::Parent::NodeMap<Value>(g) {} 509 NodeMap(const SymListGraph& g, Value v) 510 : SymListGraph::Parent::NodeMap<Value>(g, v) {} 511 template<typename TT> 512 NodeMap(const NodeMap<TT>& copy) 513 : SymListGraph::Parent::NodeMap<Value>(copy) { } 514 }; 515 516 template <typename Value> 517 class SymEdgeMap : public Parent::EdgeMap<Value> { 518 public: 519 typedef SymEdge KeyType; 520 521 SymEdgeMap(const SymListGraph& g) 522 : SymListGraph::Parent::EdgeMap<Value>(g) {} 523 SymEdgeMap(const SymListGraph& g, Value v) 524 : SymListGraph::Parent::EdgeMap<Value>(g, v) {} 525 template<typename TT> 526 SymEdgeMap(const SymEdgeMap<TT>& copy) 527 : SymListGraph::Parent::EdgeMap<Value>(copy) { } 528 529 }; 530 531 // Create edge map registry. 532 CREATE_EDGE_MAP_REGISTRY; 533 // Create edge maps. 534 CREATE_EDGE_MAP(ArrayMap); 535 536 class Edge { 537 friend class SymListGraph; 538 friend class SymListGraph::EdgeIt; 539 friend class SymListGraph::OutEdgeIt; 540 friend class SymListGraph::InEdgeIt; 541 542 protected: 543 int id; 544 545 Edge(int pid) { id = pid; } 546 547 public: 548 /// An Edge with id \c n. 549 550 Edge() { } 551 Edge (Invalid) { id = -1; } 552 553 operator SymEdge(){ return SymEdge(id >> 1);} 554 555 bool operator==(const Edge i) const {return id == i.id;} 556 bool operator!=(const Edge i) const {return id != i.id;} 557 bool operator<(const Edge i) const {return id < i.id;} 558 // ///Validity check 559 // operator bool() { return n!=-1; } 560 }; 561 562 class SymEdge : public ListGraph::Edge { 563 friend class SymListGraph; 564 friend class SymListGraph::Edge; 565 typedef ListGraph::Edge Parent; 566 567 protected: 568 SymEdge(int pid) : Parent(pid) {} 569 public: 570 571 SymEdge() { } 572 SymEdge(const ListGraph::Edge& i) : Parent(i) {} 573 SymEdge (Invalid) : Parent(INVALID) {} 574 575 }; 576 577 class OutEdgeIt { 578 Parent::OutEdgeIt out; 579 Parent::InEdgeIt in; 580 public: 581 OutEdgeIt() {} 582 OutEdgeIt(const SymListGraph& g, Edge e) { 583 if ((e.id & 1) == 0) { 584 out = Parent::OutEdgeIt(g, SymEdge(e)); 585 in = Parent::InEdgeIt(g, g.tail(e)); 586 } else { 587 out = Parent::OutEdgeIt(INVALID); 588 in = Parent::InEdgeIt(g, SymEdge(e)); 589 } 590 } 591 OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } 592 593 OutEdgeIt(const SymListGraph& g, const Node v) 594 : out(g, v), in(g, v) {} 595 OutEdgeIt &operator++() { 596 if (out != INVALID) { 597 ++out; 598 } else { 599 ++in; 600 } 601 return *this; 602 } 603 604 operator Edge() const { 605 if (out == INVALID && in == INVALID) return INVALID; 606 return out != INVALID ? forward(out) : backward(in); 607 } 608 609 bool operator==(const Edge i) const {return Edge(*this) == i;} 610 bool operator!=(const Edge i) const {return Edge(*this) != i;} 611 bool operator<(const Edge i) const {return Edge(*this) < i;} 612 }; 613 614 class InEdgeIt { 615 Parent::OutEdgeIt out; 616 Parent::InEdgeIt in; 617 public: 618 InEdgeIt() {} 619 InEdgeIt(const SymListGraph& g, Edge e) { 620 if ((e.id & 1) == 0) { 621 out = Parent::OutEdgeIt(g, SymEdge(e)); 622 in = Parent::InEdgeIt(g, g.tail(e)); 623 } else { 624 out = Parent::OutEdgeIt(INVALID); 625 in = Parent::InEdgeIt(g, SymEdge(e)); 626 } 627 } 628 InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } 629 630 InEdgeIt(const SymListGraph& g, const Node v) 631 : out(g, v), in(g, v) {} 632 633 InEdgeIt &operator++() { 634 if (out != INVALID) { 635 ++out; 636 } else { 637 ++in; 638 } 639 return *this; 640 } 641 642 operator Edge() const { 643 if (out == INVALID && in == INVALID) return INVALID; 644 return out != INVALID ? backward(out) : forward(in); 645 } 646 647 bool operator==(const Edge i) const {return Edge(*this) == i;} 648 bool operator!=(const Edge i) const {return Edge(*this) != i;} 649 bool operator<(const Edge i) const {return Edge(*this) < i;} 650 }; 651 652 class SymEdgeIt : public Parent::EdgeIt { 653 654 public: 655 SymEdgeIt() {} 656 657 SymEdgeIt(const SymListGraph& g) 658 : SymListGraph::Parent::EdgeIt(g) {} 659 660 SymEdgeIt(const SymListGraph& g, SymEdge e) 661 : SymListGraph::Parent::EdgeIt(g, e) {} 662 663 SymEdgeIt(Invalid i) 664 : SymListGraph::Parent::EdgeIt(INVALID) {} 665 666 SymEdgeIt& operator++() { 667 SymListGraph::Parent::EdgeIt::operator++(); 668 return *this; 669 } 670 671 operator SymEdge() const { 672 return SymEdge 673 (static_cast<const SymListGraph::Parent::EdgeIt&>(*this)); 674 } 675 bool operator==(const SymEdge i) const {return SymEdge(*this) == i;} 676 bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;} 677 bool operator<(const SymEdge i) const {return SymEdge(*this) < i;} 678 }; 679 680 class EdgeIt { 681 SymEdgeIt it; 682 bool fw; 683 public: 684 EdgeIt(const SymListGraph& g) : it(g), fw(true) {} 685 EdgeIt (Invalid i) : it(i) { } 686 EdgeIt(const SymListGraph& g, Edge e) 687 : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { } 688 EdgeIt() { } 689 EdgeIt& operator++() { 690 fw = !fw; 691 if (fw) ++it; 692 return *this; 693 } 694 operator Edge() const { 695 if (it == INVALID) return INVALID; 696 return fw ? forward(it) : backward(it); 697 } 698 bool operator==(const Edge i) const {return Edge(*this) == i;} 699 bool operator!=(const Edge i) const {return Edge(*this) != i;} 700 bool operator<(const Edge i) const {return Edge(*this) < i;} 701 702 }; 703 704 ///Number of nodes. 705 int nodeNum() const { return Parent::nodeNum(); } 706 ///Number of edges. 707 int edgeNum() const { return 2*Parent::edgeNum(); } 708 ///Number of symmetric edges. 709 int symEdgeNum() const { return Parent::edgeNum(); } 710 711 ///Set the expected maximum number of edges. 712 713 ///With this function, it is possible to set the expected number of edges. 714 ///The use of this fasten the building of the graph and makes 715 ///it possible to avoid the superfluous memory allocation. 716 void reserveSymEdge(int n) { Parent::reserveEdge(n); }; 717 718 /// Maximum node ID. 719 720 /// Maximum node ID. 721 ///\sa id(Node) 722 int maxNodeId() const { return Parent::maxNodeId(); } 723 /// Maximum edge ID. 724 725 /// Maximum edge ID. 726 ///\sa id(Edge) 727 int maxEdgeId() const { return 2*Parent::maxEdgeId(); } 728 /// Maximum symmetric edge ID. 729 730 /// Maximum symmetric edge ID. 731 ///\sa id(SymEdge) 732 int maxSymEdgeId() const { return Parent::maxEdgeId(); } 733 734 735 Node tail(Edge e) const { 736 return (e.id & 1) == 0 ? 737 Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); 738 } 739 740 Node head(Edge e) const { 741 return (e.id & 1) == 0 ? 742 Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); 743 } 744 745 Node tail(SymEdge e) const { 746 return Parent::tail(e); 747 } 748 749 Node head(SymEdge e) const { 750 return Parent::head(e); 751 } 752 753 NodeIt& first(NodeIt& v) const { 754 v=NodeIt(*this); return v; } 755 EdgeIt& first(EdgeIt& e) const { 756 e=EdgeIt(*this); return e; } 757 SymEdgeIt& first(SymEdgeIt& e) const { 758 e=SymEdgeIt(*this); return e; } 759 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 760 e=OutEdgeIt(*this,v); return e; } 761 InEdgeIt& first(InEdgeIt& e, const Node v) const { 762 e=InEdgeIt(*this,v); return e; } 763 764 /// Node ID. 765 766 /// The ID of a valid Node is a nonnegative integer not greater than 767 /// \ref maxNodeId(). The range of the ID's is not surely continuous 768 /// and the greatest node ID can be actually less then \ref maxNodeId(). 769 /// 770 /// The ID of the \ref INVALID node is -1. 771 ///\return The ID of the node \c v. 772 static int id(Node v) { return Parent::id(v); } 773 /// Edge ID. 774 775 /// The ID of a valid Edge is a nonnegative integer not greater than 776 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 777 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 778 /// 779 /// The ID of the \ref INVALID edge is -1. 780 ///\return The ID of the edge \c e. 781 static int id(Edge e) { return e.id; } 782 783 /// The ID of a valid SymEdge is a nonnegative integer not greater than 784 /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous 785 /// and the greatest edge ID can be actually less then \ref maxSymEdgeId(). 786 /// 787 /// The ID of the \ref INVALID symmetric edge is -1. 788 ///\return The ID of the edge \c e. 789 static int id(SymEdge e) { return Parent::id(e); } 790 791 /// Adds a new node to the graph. 792 793 /// \warning It adds the new node to the front of the list. 794 /// (i.e. the lastly added node becomes the first.) 795 Node addNode() { 796 return Parent::addNode(); 797 } 798 799 SymEdge addEdge(Node u, Node v) { 800 SymEdge se = Parent::addEdge(u, v); 801 edge_maps.add(forward(se)); 802 edge_maps.add(backward(se)); 803 return se; 804 } 805 806 /// Finds an edge between two nodes. 807 808 /// Finds an edge from node \c u to node \c v. 809 /// 810 /// If \c prev is \ref INVALID (this is the default value), then 811 /// It finds the first edge from \c u to \c v. Otherwise it looks for 812 /// the next edge from \c u to \c v after \c prev. 813 /// \return The found edge or INVALID if there is no such an edge. 814 Edge findEdge(Node u, Node v, Edge prev = INVALID) 815 { 816 if (prev == INVALID || id(prev) & 1 == 0) { 817 SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); 818 if (se != INVALID) return forward(se); 819 } else { 820 SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); 821 if (se != INVALID) return backward(se); 822 } 823 return INVALID; 824 } 825 826 // /// Finds an symmetric edge between two nodes. 827 828 // /// Finds an symmetric edge from node \c u to node \c v. 829 // /// 830 // /// If \c prev is \ref INVALID (this is the default value), then 831 // /// It finds the first edge from \c u to \c v. Otherwise it looks for 832 // /// the next edge from \c u to \c v after \c prev. 833 // /// \return The found edge or INVALID if there is no such an edge. 834 835 // SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) 836 // { 837 // if (prev == INVALID || id(prev) & 1 == 0) { 838 // SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); 839 // if (se != INVALID) return se; 840 // } else { 841 // SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); 842 // if (se != INVALID) return se; 843 // } 844 // return INVALID; 845 // } 846 847 public: 848 849 void erase(Node n) { 850 for (OutEdgeIt it(*this, n); it != INVALID; ++it) { 851 edge_maps.erase(it); 852 edge_maps.erase(opposite(it)); 853 } 854 Parent::erase(n); 855 } 856 857 void erase(SymEdge e) { 858 edge_maps.erase(forward(e)); 859 edge_maps.erase(backward(e)); 860 Parent::erase(e); 861 }; 862 863 void clear() { 864 edge_maps.clear(); 865 Parent::clear(); 866 } 867 868 static Edge opposite(Edge e) { 869 return Edge(id(e) ^ 1); 870 } 871 872 static Edge forward(SymEdge e) { 873 return Edge(id(e) << 1); 874 } 875 876 static Edge backward(SymEdge e) { 877 return Edge((id(e) << 1) | 1); 878 } 879 880 }; 881 882 ///A graph class containing only nodes. 883 884 ///This class implements a graph structure without edges. 885 ///The most useful application of this class is to be the node set of an 886 ///\ref EdgeSet class. 887 /// 888 ///It conforms to 889 ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept 890 ///with the exception that you cannot 891 ///add (or delete) edges. The usual edge iterators are exists, but they are 892 ///always \ref INVALID. 893 ///\sa skeleton::ExtendableGraph 894 ///\sa EdgeSet 895 class NodeSet { 896 897 //Nodes are double linked. 898 //The free nodes are only single linked using the "next" field. 899 struct NodeT 900 { 901 int first_in,first_out; 902 int prev, next; 903 // NodeT() {} 904 }; 905 906 std::vector<NodeT> nodes; 907 //The first node 908 int first_node; 909 //The first free node 910 int first_free_node; 911 912 public: 913 914 typedef NodeSet Graph; 915 916 class Node; 917 class Edge; 918 919 public: 920 921 class NodeIt; 922 class EdgeIt; 923 class OutEdgeIt; 924 class InEdgeIt; 925 926 // Create node map registry. 927 CREATE_NODE_MAP_REGISTRY; 928 // Create node maps. 929 CREATE_NODE_MAP(ArrayMap); 930 931 /// Creating empty map structure for edges. 932 template <typename Value> 933 class EdgeMap { 934 public: 935 EdgeMap(const Graph&) {} 936 EdgeMap(const Graph&, const Value&) {} 937 938 EdgeMap(const EdgeMap&) {} 939 template <typename CMap> EdgeMap(const CMap&) {} 940 941 EdgeMap& operator=(const EdgeMap&) {} 942 template <typename CMap> EdgeMap& operator=(const CMap&) {} 943 944 class ConstIterator { 945 public: 946 bool operator==(const ConstIterator&) {return true;} 947 bool operator!=(const ConstIterator&) {return false;} 948 }; 949 950 typedef ConstIterator Iterator; 951 952 Iterator begin() { return Iterator();} 953 Iterator end() { return Iterator();} 954 955 ConstIterator begin() const { return ConstIterator();} 956 ConstIterator end() const { return ConstIterator();} 957 958 }; 959 960 public: 961 962 ///Default constructor 963 NodeSet() 964 : nodes(), first_node(-1), first_free_node(-1) {} 965 ///Copy constructor 966 NodeSet(const NodeSet &_g) 967 : nodes(_g.nodes), first_node(_g.first_node), 968 first_free_node(_g.first_free_node) {} 969 970 ///Number of nodes. 971 int nodeNum() const { return nodes.size(); } 972 ///Number of edges. 973 int edgeNum() const { return 0; } 974 975 /// Maximum node ID. 976 977 /// Maximum node ID. 978 ///\sa id(Node) 979 int maxNodeId() const { return nodes.size()-1; } 980 /// Maximum edge ID. 981 982 /// Maximum edge ID. 983 ///\sa id(Edge) 984 int maxEdgeId() const { return 0; } 985 986 Node tail(Edge e) const { return INVALID; } 987 Node head(Edge e) const { return INVALID; } 988 989 NodeIt& first(NodeIt& v) const { 990 v=NodeIt(*this); return v; } 991 EdgeIt& first(EdgeIt& e) const { 992 e=EdgeIt(*this); return e; } 993 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 994 e=OutEdgeIt(*this,v); return e; } 995 InEdgeIt& first(InEdgeIt& e, const Node v) const { 996 e=InEdgeIt(*this,v); return e; } 997 998 /// Node ID. 999 1000 /// The ID of a valid Node is a nonnegative integer not greater than 1001 /// \ref maxNodeId(). The range of the ID's is not surely continuous 1002 /// and the greatest node ID can be actually less then \ref maxNodeId(). 1003 /// 1004 /// The ID of the \ref INVALID node is -1. 1005 ///\return The ID of the node \c v. 1006 static int id(Node v) { return v.n; } 1007 /// Edge ID. 1008 1009 /// The ID of a valid Edge is a nonnegative integer not greater than 1010 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 1011 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 1012 /// 1013 /// The ID of the \ref INVALID edge is -1. 1014 ///\return The ID of the edge \c e. 1015 static int id(Edge e) { return -1; } 1016 1017 /// Adds a new node to the graph. 1018 1019 /// \warning It adds the new node to the front of the list. 1020 /// (i.e. the lastly added node becomes the first.) 1021 Node addNode() { 1022 int n; 1023 1024 if(first_free_node==-1) 1025 { 1026 n = nodes.size(); 1027 nodes.push_back(NodeT()); 1028 } 1029 else { 1030 n = first_free_node; 1031 first_free_node = nodes[n].next; 1032 } 1033 1034 nodes[n].next = first_node; 1035 if(first_node != -1) nodes[first_node].prev = n; 1036 first_node = n; 1037 nodes[n].prev = -1; 1038 1039 nodes[n].first_in = nodes[n].first_out = -1; 1040 1041 Node nn; nn.n=n; 1042 1043 //Update dynamic maps 1044 node_maps.add(nn); 1045 1046 return nn; 1047 } 1048 1049 void erase(Node nn) { 1050 int n=nn.n; 1051 1052 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev; 1053 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next; 1054 else first_node = nodes[n].next; 1055 1056 nodes[n].next = first_free_node; 1057 first_free_node = n; 1058 1059 //Update dynamic maps 1060 node_maps.erase(nn); 1061 } 1062 1063 1064 Edge findEdge(Node u,Node v, Edge prev = INVALID) 1065 { 1066 return INVALID; 1067 } 1068 1069 void clear() { 1070 node_maps.clear(); 1071 nodes.clear(); 1072 first_node = first_free_node = -1; 1073 } 1074 1075 class Node { 1076 friend class NodeSet; 1077 template <typename T> friend class NodeMap; 1078 1079 friend class Edge; 1080 friend class OutEdgeIt; 1081 friend class InEdgeIt; 1082 1083 protected: 1084 int n; 1085 friend int NodeSet::id(Node v); 1086 Node(int nn) {n=nn;} 1087 public: 1088 Node() {} 1089 Node (Invalid i) { n=-1; } 1090 bool operator==(const Node i) const {return n==i.n;} 1091 bool operator!=(const Node i) const {return n!=i.n;} 1092 bool operator<(const Node i) const {return n<i.n;} 1093 }; 1094 1095 class NodeIt : public Node { 1096 const NodeSet *G; 1097 friend class NodeSet; 1098 public: 1099 NodeIt() : Node() { } 1100 NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { } 1101 NodeIt(Invalid i) : Node(i) { } 1102 NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { } 1103 NodeIt &operator++() { 1104 n=G->nodes[n].next; 1105 return *this; 1106 } 1107 }; 1108 1109 class Edge { 1110 public: 1111 Edge() { } 1112 Edge (Invalid) { } 1113 bool operator==(const Edge i) const {return true;} 1114 bool operator!=(const Edge i) const {return false;} 1115 bool operator<(const Edge i) const {return false;} 1116 }; 1117 1118 class EdgeIt : public Edge { 1119 public: 1120 EdgeIt(const NodeSet& G) : Edge() { } 1121 EdgeIt(const NodeSet&, Edge) : Edge() { } 1122 EdgeIt (Invalid i) : Edge(i) { } 1123 EdgeIt() : Edge() { } 1124 EdgeIt operator++() { return INVALID; } 1125 }; 1126 1127 class OutEdgeIt : public Edge { 1128 friend class NodeSet; 1129 public: 1130 OutEdgeIt() : Edge() { } 1131 OutEdgeIt(const NodeSet&, Edge) : Edge() { } 1132 OutEdgeIt (Invalid i) : Edge(i) { } 1133 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {} 1134 OutEdgeIt operator++() { return INVALID; } 1135 }; 1136 1137 class InEdgeIt : public Edge { 1138 friend class NodeSet; 1139 public: 1140 InEdgeIt() : Edge() { } 1141 InEdgeIt(const NodeSet&, Edge) : Edge() { } 1142 InEdgeIt (Invalid i) : Edge(i) { } 1143 InEdgeIt(const NodeSet& G,Node v) :Edge() {} 1144 InEdgeIt operator++() { return INVALID; } 1145 }; 1146 1147 }; 1148 1149 1150 1151 ///Graph structure using a node set of another graph. 1152 1153 ///This structure can be used to establish another graph over a node set 1154 /// of an existing one. The node iterator will go through the nodes of the 1155 /// original graph, and the NodeMap's of both graphs will convert to 1156 /// each other. 1157 /// 1158 ///\warning Adding or deleting nodes from the graph is not safe if an 1159 ///\ref EdgeSet is currently attached to it! 1160 /// 1161 ///\todo Make it possible to add/delete edges from the base graph 1162 ///(and from \ref EdgeSet, as well) 1163 /// 1164 ///\param GG The type of the graph which shares its node set with this class. 1165 ///Its interface must conform to the 1166 ///\ref skeleton::StaticGraph "StaticGraph" concept. 1167 /// 1168 ///It conforms to the 1169 ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept. 1170 ///\sa skeleton::ExtendableGraph. 1171 ///\sa NodeSet. 1172 template<typename GG> 1173 class EdgeSet { 1174 1175 typedef GG NodeGraphType; 1176 1177 NodeGraphType &G; 1178 1179 public: 1180 1181 class Node; 1182 class Edge; 1183 class OutEdgeIt; 1184 class InEdgeIt; 1185 class SymEdge; 1186 1187 typedef EdgeSet Graph; 1188 1189 int id(Node v) const; 1190 1191 class Node : public NodeGraphType::Node { 1192 friend class EdgeSet; 1193 1194 friend class Edge; 1195 friend class OutEdgeIt; 1196 friend class InEdgeIt; 1197 friend class SymEdge; 1198 1199 public: 1200 friend int EdgeSet::id(Node v) const; 1201 public: 1202 Node() : NodeGraphType::Node() {} 1203 Node (Invalid i) : NodeGraphType::Node(i) {} 1204 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {} 1205 }; 1206 1207 class NodeIt : public NodeGraphType::NodeIt { 1208 friend class EdgeSet; 1209 public: 1210 NodeIt() : NodeGraphType::NodeIt() { } 1211 NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { } 1212 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} 1213 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { } 1214 NodeIt(const typename NodeGraphType::NodeIt &n) 1215 : NodeGraphType::NodeIt(n) {} 1216 1217 operator Node() { return Node(*this);} 1218 NodeIt &operator++() 1219 { this->NodeGraphType::NodeIt::operator++(); return *this;} 1220 }; 1221 1222 private: 1223 //Edges are double linked. 1224 //The free edges are only single linked using the "next_in" field. 1225 struct NodeT 1226 { 1227 int first_in,first_out; 1228 NodeT() : first_in(-1), first_out(-1) { } 1229 }; 1230 1231 struct EdgeT 1232 { 1233 Node head, tail; 1234 int prev_in, prev_out; 1235 int next_in, next_out; 1236 }; 1237 1238 1239 typename NodeGraphType::template NodeMap<NodeT> nodes; 1240 1241 std::vector<EdgeT> edges; 1242 //The first free edge 1243 int first_free_edge; 1244 1245 public: 1246 1247 class Node; 1248 class Edge; 1249 1250 class NodeIt; 1251 class EdgeIt; 1252 class OutEdgeIt; 1253 class InEdgeIt; 1254 1255 1256 // Create edge map registry. 1257 CREATE_EDGE_MAP_REGISTRY; 1258 // Create edge maps. 1259 CREATE_EDGE_MAP(ArrayMap); 1260 1261 // Import node maps from the NodeGraphType. 1262 IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph); 1263 1264 1265 public: 1266 1267 ///Constructor 1268 1269 ///Construates a new graph based on the nodeset of an existing one. 1270 ///\param _G the base graph. 1271 explicit EdgeSet(NodeGraphType &_G) 1272 : G(_G), nodes(_G), edges(), 1273 first_free_edge(-1) {} 1274 ///Copy constructor 1275 1276 ///Makes a copy of an EdgeSet. 1277 ///It will be based on the same graph. 1278 explicit EdgeSet(const EdgeSet &_g) 1279 : G(_g.G), nodes(_g.G), edges(_g.edges), 1280 first_free_edge(_g.first_free_edge) {} 1281 1282 ///Number of nodes. 1283 int nodeNum() const { return G.nodeNum(); } 1284 ///Number of edges. 1285 int edgeNum() const { return edges.size(); } 1286 1287 /// Maximum node ID. 1288 1289 /// Maximum node ID. 1290 ///\sa id(Node) 1291 int maxNodeId() const { return G.maxNodeId(); } 1292 /// Maximum edge ID. 1293 1294 /// Maximum edge ID. 1295 ///\sa id(Edge) 1296 int maxEdgeId() const { return edges.size()-1; } 1297 1298 Node tail(Edge e) const { return edges[e.n].tail; } 1299 Node head(Edge e) const { return edges[e.n].head; } 1300 1301 NodeIt& first(NodeIt& v) const { 1302 v=NodeIt(*this); return v; } 1303 EdgeIt& first(EdgeIt& e) const { 1304 e=EdgeIt(*this); return e; } 1305 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 1306 e=OutEdgeIt(*this,v); return e; } 1307 InEdgeIt& first(InEdgeIt& e, const Node v) const { 1308 e=InEdgeIt(*this,v); return e; } 1309 1310 /// Node ID. 1311 1312 /// The ID of a valid Node is a nonnegative integer not greater than 1313 /// \ref maxNodeId(). The range of the ID's is not surely continuous 1314 /// and the greatest node ID can be actually less then \ref maxNodeId(). 1315 /// 1316 /// The ID of the \ref INVALID node is -1. 1317 ///\return The ID of the node \c v. 1318 int id(Node v) { return G.id(v); } 1319 /// Edge ID. 1320 1321 /// The ID of a valid Edge is a nonnegative integer not greater than 1322 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 1323 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 1324 /// 1325 /// The ID of the \ref INVALID edge is -1. 1326 ///\return The ID of the edge \c e. 1327 static int id(Edge e) { return e.n; } 1328 1329 /// Adds a new node to the graph. 1330 Node addNode() { return G.addNode(); } 1331 1332 Edge addEdge(Node u, Node v) { 1333 int n; 1334 1335 if(first_free_edge==-1) 1336 { 1337 n = edges.size(); 1338 edges.push_back(EdgeT()); 1339 } 1340 else { 1341 n = first_free_edge; 1342 first_free_edge = edges[n].next_in; 1343 } 1344 1345 edges[n].tail = u; edges[n].head = v; 1346 1347 edges[n].next_out = nodes[u].first_out; 1348 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n; 1349 edges[n].next_in = nodes[v].first_in; 1350 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n; 1351 edges[n].prev_in = edges[n].prev_out = -1; 1352 1353 nodes[u].first_out = nodes[v].first_in = n; 1354 1355 Edge e; e.n=n; 1356 1357 //Update dynamic maps 1358 edge_maps.add(e); 1359 1360 return e; 1361 } 1362 1363 /// Finds an edge between two nodes. 1364 1365 /// Finds an edge from node \c u to node \c v. 1366 /// 1367 /// If \c prev is \ref INVALID (this is the default value), then 1368 /// It finds the first edge from \c u to \c v. Otherwise it looks for 1369 /// the next edge from \c u to \c v after \c prev. 1370 /// \return The found edge or INVALID if there is no such an edge. 1371 Edge findEdge(Node u,Node v, Edge prev = INVALID) 1372 { 1373 int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out; 1374 while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out; 1375 prev.n=e; 1376 return prev; 1377 } 1378 1379 private: 1380 void eraseEdge(int n) { 1381 1382 if(edges[n].next_in!=-1) 1383 edges[edges[n].next_in].prev_in = edges[n].prev_in; 1384 if(edges[n].prev_in!=-1) 1385 edges[edges[n].prev_in].next_in = edges[n].next_in; 1386 else nodes[edges[n].head].first_in = edges[n].next_in; 1387 1388 if(edges[n].next_out!=-1) 1389 edges[edges[n].next_out].prev_out = edges[n].prev_out; 1390 if(edges[n].prev_out!=-1) 1391 edges[edges[n].prev_out].next_out = edges[n].next_out; 1392 else nodes[edges[n].tail].first_out = edges[n].next_out; 1393 1394 edges[n].next_in = first_free_edge; 1395 first_free_edge = -1; 1396 1397 //Update dynamic maps 1398 Edge e; e.n = n; 1399 edge_maps.erase(e); 1400 } 1401 1402 public: 1403 1404 void erase(Edge e) { eraseEdge(e.n); } 1405 1406 ///Clear all edges. (Doesn't clear the nodes!) 1407 void clear() { 1408 edge_maps.clear(); 1409 edges.clear(); 1410 first_free_edge=-1; 1411 } 1412 1413 1414 class Edge { 1415 public: 1416 friend class EdgeSet; 1417 template <typename T> friend class EdgeMap; 1418 1419 friend class Node; 1420 friend class NodeIt; 1421 protected: 1422 int n; 1423 friend int EdgeSet::id(Edge e) const; 1424 1425 Edge(int nn) {n=nn;} 1426 public: 1427 Edge() { } 1428 Edge (Invalid) { n=-1; } 1429 bool operator==(const Edge i) const {return n==i.n;} 1430 bool operator!=(const Edge i) const {return n!=i.n;} 1431 bool operator<(const Edge i) const {return n<i.n;} 1432 }; 1433 1434 class EdgeIt : public Edge { 1435 friend class EdgeSet; 1436 template <typename T> friend class EdgeMap; 1437 1438 const EdgeSet *G; 1439 public: 1440 EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) { 1441 NodeIt m; 1442 for(G->first(m); 1443 m!=INVALID && G->nodes[m].first_in == -1; ++m); 1444 ///\bug AJJAJ! This is a non sense!!!!!!! 1445 this->n = m!=INVALID?-1:G->nodes[m].first_in; 1446 } 1447 EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } 1448 EdgeIt (Invalid i) : Edge(i) { } 1449 EdgeIt() : Edge() { } 1450 ///. 1451 1452 ///\bug UNIMPLEMENTED!!!!! 1453 // 1454 EdgeIt &operator++() { 1455 return *this; 1456 } 1457 }; 1458 1459 class OutEdgeIt : public Edge { 1460 const EdgeSet *G; 1461 friend class EdgeSet; 1462 public: 1463 OutEdgeIt() : Edge() { } 1464 OutEdgeIt (Invalid i) : Edge(i) { } 1465 OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } 1466 1467 OutEdgeIt(const EdgeSet& _G,const Node v) : 1468 Edge(_G.nodes[v].first_out), G(&_G) { } 1469 OutEdgeIt &operator++() { 1470 Edge::n = G->edges[Edge::n].next_out; 1471 return *this; 1472 } 1473 }; 1474 1475 class InEdgeIt : public Edge { 1476 const EdgeSet *G; 1477 friend class EdgeSet; 1478 public: 1479 InEdgeIt() : Edge() { } 1480 InEdgeIt (Invalid i) : Edge(i) { } 1481 InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } 1482 InEdgeIt(const EdgeSet& _G,Node v) 1483 : Edge(_G.nodes[v].first_in), G(&_G) { } 1484 InEdgeIt &operator++() { 1485 Edge::n = G->edges[Edge::n].next_in; 1486 return *this; 1487 } 1488 }; 1489 1490 }; 1491 1492 template<typename GG> 1493 inline int EdgeSet<GG>::id(Node v) const { return G.id(v); } 1494 1495 /// @} 1496 1497 } //namespace lemon 1498 1499 #endif //LEMON_LIST_GRAPH_H 262 typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase; 263 typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase; 264 typedef IdMappableGraphExtender<IterableListGraphBase> IdMappableListGraphBase; 265 typedef DefaultMappableGraphExtender<IdMappableListGraphBase> MappableListGraphBase; 266 typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase; 267 typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase; 268 typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase; 269 270 typedef ErasableListGraphBase ListGraph; 271 272 } 273 274 275 276 277 #endif
Note: See TracChangeset
for help on using the changeset viewer.