Changeset 397:b4d7b19b6740 in lemon0.x for src/work/alpar
 Timestamp:
 04/25/04 18:53:38 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@528
 Location:
 src/work/alpar
 Files:

 1 added
 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/list_graph.h
r396 r397 5 5 6 6 ///\file 7 ///\brief SmartGraph and SymSmartGraph classes.7 ///\brief ListGraph and SymListGraph classes. 8 8 9 9 #include <vector> … … 14 14 namespace hugo { 15 15 16 class Sym SmartGraph;16 class SymListGraph; 17 17 18 18 ///A smart graph class. 19 19 20 ///This is a simple and fast graph implementation. 21 ///It is also quite memory efficient, but at the price 22 ///that <b> it does not support node and edge deletion</b>. 20 ///This is a simple and fast erasable graph implementation. 21 /// 23 22 ///It conforms to the graph interface documented under 24 23 ///the description of \ref GraphSkeleton. 25 24 ///\sa \ref GraphSkeleton. 26 class SmartGraph { 27 25 class ListGraph { 26 27 //Nodes are double linked. 28 //The free nodes are only single linked using the "next" field. 28 29 struct NodeT 29 30 { 30 int first_in,first_out; 31 NodeT() : first_in(1), first_out(1) {} 32 }; 31 int first_in,first_out; 32 int prev, next; 33 // NodeT() {} 34 }; 35 //Edges are double linked. 36 //The free edges are only single linked using the "next_in" field. 33 37 struct EdgeT 34 38 { 35 int head, tail, next_in, next_out; 39 int head, tail; 40 int prev_in, prev_out; 41 int next_in, next_out; 36 42 //FIXME: is this necessary? 37 EdgeT() : next_in(1), next_out(1) {}43 // EdgeT() : next_in(1), next_out(1) prev_in(1), prev_out(1) {} 38 44 }; 39 45 40 46 std::vector<NodeT> nodes; 41 47 //The first node 48 int first_node; 49 //The first free node 50 int first_free_node; 42 51 std::vector<EdgeT> edges; 43 52 //The first free edge 53 int first_free_edge; 54 55 protected: 56 57 template <typename Key> class DynMapBase 58 { 44 59 protected: 45 46 template <typename Key> class DynMapBase 47 { 48 protected: 49 const SmartGraph* G; 60 const ListGraph* G; 50 61 public: 51 62 virtual void add(const Key k) = NULL; 52 63 virtual void erase(const Key k) = NULL; 53 DynMapBase(const SmartGraph &_G) : G(&_G) {}64 DynMapBase(const ListGraph &_G) : G(&_G) {} 54 65 virtual ~DynMapBase() {} 55 friend class SmartGraph;66 friend class ListGraph; 56 67 }; 57 68 … … 59 70 template <typename T> class EdgeMap; 60 71 template <typename T> class EdgeMap; 61 72 62 73 class Node; 63 74 class Edge; … … 85 96 public: 86 97 87 SmartGraph() : nodes(), edges() { } 88 SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { } 89 90 ~SmartGraph() 98 ListGraph() : nodes(), first_node(1), 99 first_free_node(1), edges(), first_free_edge(1) {} 100 ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node), 101 first_free_node(_g.first_free_node), 102 edges(_g.edges), 103 first_free_edge(_g.first_free_edge) {} 104 105 ~ListGraph() 91 106 { 92 107 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); … … 140 155 141 156 NodeIt& next(NodeIt& it) const { 142 it.n= (it.n+2)%(nodes.size()+1)1;157 it.n=nodes[it.n].next; 143 158 return it; 144 159 } … … 147 162 InEdgeIt& next(InEdgeIt& it) const 148 163 { it.n=edges[it.n].next_in; return it; } 149 EdgeIt& next(EdgeIt& it) const { it.n; return it; } 164 EdgeIt& next(EdgeIt& it) const { 165 if(edges[it.n].next_in!=1) { 166 it.n=edges[it.n].next_in; 167 } 168 else { 169 int n; 170 for(n=nodes[edges[it.n].head].next; 171 n!=1 && nodes[n].first_in == 1; 172 n = nodes[n].next) ; 173 it.n = (n==1)?1:nodes[n].first_in; 174 } 175 return it; 176 } 150 177 151 178 int id(Node v) const { return v.n; } 152 179 int id(Edge e) const { return e.n; } 153 180 181 /// Adds a new node to the graph. 182 183 /// \todo It adds the nodes in a reversed order. 184 /// (i.e. the lastly added node becomes the first.) 154 185 Node addNode() { 155 Node n; n.n=nodes.size(); 156 nodes.push_back(NodeT()); //FIXME: Hmmm... 157 186 int n; 187 188 if(first_free_node==1) 189 { 190 n = nodes.size(); 191 nodes.push_back(NodeT()); 192 } 193 else { 194 n = first_free_node; 195 first_free_node = nodes[n].next; 196 } 197 198 nodes[n].next = first_node; 199 if(first_node != 1) nodes[first_node].prev = n; 200 first_node = n; 201 nodes[n].prev = 1; 202 203 nodes[n].first_in = nodes[n].first_out = 1; 204 205 Node nn; nn.n=n; 206 207 //Update dynamic maps 158 208 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 159 i!=dyn_node_maps.end(); ++i) (**i).add(n .n);160 161 return n ;209 i!=dyn_node_maps.end(); ++i) (**i).add(nn); 210 211 return nn; 162 212 } 163 213 164 214 Edge addEdge(Node u, Node v) { 165 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... 166 edges[e.n].tail=u.n; edges[e.n].head=v.n; 167 edges[e.n].next_out=nodes[u.n].first_out; 168 edges[e.n].next_in=nodes[v.n].first_in; 169 nodes[u.n].first_out=nodes[v.n].first_in=e.n; 170 215 int n; 216 217 if(first_free_edge==1) 218 { 219 n = edges.size(); 220 edges.push_back(EdgeT()); 221 } 222 else { 223 n = first_free_edge; 224 first_free_edge = edges[n].next_in; 225 } 226 227 edges[n].tail = u.n; edges[n].head = v.n; 228 229 edges[n].next_out = nodes[u.n].first_out; 230 if(nodes[u.n].first_out != 1) edges[nodes[u.n].first_out].prev_out = n; 231 edges[n].next_in = nodes[v.n].first_in; 232 if(nodes[v.n].first_in != 1) edges[nodes[v.n].first_in].prev_in = n; 233 edges[n].prev_in = edges[n].prev_out = 1; 234 235 nodes[u.n].first_out = nodes[v.n].first_in = n; 236 237 Edge e; e.n=n; 238 239 //Update dynamic maps 171 240 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 172 241 i!=dyn_edge_maps.end(); ++i) (**i).add(e); … … 175 244 } 176 245 177 void clear() {nodes.clear();edges.clear();} 246 private: 247 void eraseEdge(int n) { 248 249 if(edges[n].next_in!=1) 250 edges[edges[n].next_in].prev_in = edges[n].prev_in; 251 if(edges[n].prev_in!=1) 252 edges[edges[n].prev_in].next_in = edges[n].next_in; 253 else nodes[edges[n].head].first_in = edges[n].next_in; 254 255 if(edges[n].next_out!=1) 256 edges[edges[n].next_out].prev_out = edges[n].prev_out; 257 if(edges[n].prev_out!=1) 258 edges[edges[n].prev_out].next_out = edges[n].next_out; 259 else nodes[edges[n].tail].first_out = edges[n].next_out; 260 261 edges[n].next_in = first_free_edge; 262 first_free_edge = 1; 263 264 //Update dynamic maps 265 Edge e; e.n=n; 266 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 267 i!=dyn_edge_maps.end(); ++i) (**i).erase(e); 268 } 269 270 public: 271 272 void erase(Node nn) { 273 int n=nn.n; 274 275 int m; 276 while((m=nodes[n].first_in)!=1) eraseEdge(m); 277 while((m=nodes[n].first_out)!=1) eraseEdge(m); 278 279 if(nodes[n].next != 1) nodes[nodes[n].next].prev = nodes[n].prev; 280 if(nodes[n].prev != 1) nodes[nodes[n].prev].next = nodes[n].next; 281 else first_node = nodes[n].next; 282 283 nodes[n].next = first_free_node; 284 first_free_node = n; 285 286 //Update dynamic maps 287 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 288 i!=dyn_node_maps.end(); ++i) (**i).erase(nn); 289 } 290 291 void erase(Edge e) { eraseEdge(e.n); } 292 293 ///\bug Dynamic maps must be updated! 294 /// 295 void clear() { 296 nodes.clear();edges.clear(); 297 first_node=first_free_node=first_free_edge=1; 298 } 178 299 179 300 class Node { 180 friend class SmartGraph;301 friend class ListGraph; 181 302 template <typename T> friend class NodeMap; 182 303 … … 188 309 protected: 189 310 int n; 190 friend int SmartGraph::id(Node v) const;311 friend int ListGraph::id(Node v) const; 191 312 Node(int nn) {n=nn;} 192 313 public: … … 199 320 200 321 class NodeIt : public Node { 201 friend class SmartGraph;322 friend class ListGraph; 202 323 public: 203 NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:1) { }324 NodeIt(const ListGraph& G) : Node(G.first_node) { } 204 325 NodeIt() : Node() { } 205 326 }; 206 327 207 328 class Edge { 208 friend class SmartGraph;329 friend class ListGraph; 209 330 template <typename T> friend class EdgeMap; 210 331 211 //template <typename T> friend class Sym SmartGraph::SymEdgeMap;212 //friend Edge Sym SmartGraph::opposite(Edge) const;332 //template <typename T> friend class SymListGraph::SymEdgeMap; 333 //friend Edge SymListGraph::opposite(Edge) const; 213 334 214 335 friend class Node; … … 216 337 protected: 217 338 int n; 218 friend int SmartGraph::id(Edge e) const;339 friend int ListGraph::id(Edge e) const; 219 340 220 341 Edge(int nn) {n=nn;} … … 226 347 bool operator<(const Edge i) const {return n<i.n;} 227 348 ///\bug This is a workaround until somebody tells me how to 228 ///make class \c Sym SmartGraph::SymEdgeMap friend of Edge349 ///make class \c SymListGraph::SymEdgeMap friend of Edge 229 350 int &idref() {return n;} 230 351 const int &idref() const {return n;} … … 232 353 233 354 class EdgeIt : public Edge { 234 friend class SmartGraph;355 friend class ListGraph; 235 356 public: 236 EdgeIt(const SmartGraph& G) : Edge(G.edges.size()1) { } 357 EdgeIt(const ListGraph& G) : Edge() { 358 int m; 359 for(m=G.first_node; 360 m!=1 && G.nodes[m].first_in == 1; m = G.nodes[m].next); 361 n = (m==1)?1:G.nodes[m].first_in; 362 } 237 363 EdgeIt (Invalid i) : Edge(i) { } 238 364 EdgeIt() : Edge() { } 239 365 ///\bug This is a workaround until somebody tells me how to 240 ///make class \c Sym SmartGraph::SymEdgeMap friend of Edge366 ///make class \c SymListGraph::SymEdgeMap friend of Edge 241 367 int &idref() {return n;} 242 368 }; 243 369 244 370 class OutEdgeIt : public Edge { 245 friend class SmartGraph;371 friend class ListGraph; 246 372 public: 247 373 OutEdgeIt() : Edge() { } 248 374 OutEdgeIt (Invalid i) : Edge(i) { } 249 375 250 OutEdgeIt(const SmartGraph& G,const Node v)376 OutEdgeIt(const ListGraph& G,const Node v) 251 377 : Edge(G.nodes[v.n].first_out) {} 252 378 }; 253 379 254 380 class InEdgeIt : public Edge { 255 friend class SmartGraph;381 friend class ListGraph; 256 382 public: 257 383 InEdgeIt() : Edge() { } 258 384 InEdgeIt (Invalid i) : Edge(i) { } 259 InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}385 InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){} 260 386 }; 261 387 … … 268 394 typedef Node KeyType; 269 395 270 NodeMap(const SmartGraph &_G) :396 NodeMap(const ListGraph &_G) : 271 397 DynMapBase<Node>(_G), container(_G.maxNodeId()) 272 398 { 273 399 G>dyn_node_maps.push_back(this); 274 400 } 275 NodeMap(const SmartGraph &_G,const T &t) :401 NodeMap(const ListGraph &_G,const T &t) : 276 402 DynMapBase<Node>(_G), container(_G.maxNodeId(),t) 277 403 { … … 358 484 typedef Edge KeyType; 359 485 360 EdgeMap(const SmartGraph &_G) :486 EdgeMap(const ListGraph &_G) : 361 487 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) 362 488 { … … 365 491 G>dyn_edge_maps.push_back(this); 366 492 } 367 EdgeMap(const SmartGraph &_G,const T &t) :493 EdgeMap(const ListGraph &_G,const T &t) : 368 494 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) 369 495 { … … 447 573 ///of oppositely directed edges. 448 574 ///There is a new edge map type called 449 ///\ref Sym SmartGraph::SymEdgeMap "SymEdgeMap"575 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap" 450 576 ///that complements this 451 577 ///feature by … … 457 583 ///The oppositely directed edge can also be obtained easily 458 584 ///using \ref opposite. 459 ///\warning It shares the similarity with \ref SmartGraph that 460 ///it is not possible to delete edges or nodes from the graph. 461 //\sa \ref SmartGraph. 462 463 class SymSmartGraph : public SmartGraph 585 /// 586 ///Here erase(Edge) deletes a pair of edges. 587 /// 588 ///\todo this date structure need some reconsiderations. Maybe it 589 ///should be implemented independently from ListGraph. 590 591 class SymListGraph : public ListGraph 464 592 { 465 593 public: … … 467 595 template<typename T> friend class SymEdgeMap; 468 596 469 SymSmartGraph() : SmartGraph() { } 470 SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { } 597 SymListGraph() : ListGraph() { } 598 SymListGraph(const ListGraph &_g) : ListGraph(_g) { } 599 ///Adds a pair of oppositely directed edges to the graph. 471 600 Edge addEdge(Node u, Node v) 472 601 { 473 Edge e = SmartGraph::addEdge(u,v);474 SmartGraph::addEdge(v,u);602 Edge e = ListGraph::addEdge(u,v); 603 ListGraph::addEdge(v,u); 475 604 return e; 476 605 } 477 606 607 void erase(Node n) { ListGraph::erase(n); } 478 608 ///The oppositely directed edge. 479 609 … … 487 617 } 488 618 619 ///Removes a pair of oppositely directed edges to the graph. 620 void erase(Edge e) { 621 ListGraph::erase(opposite(e)); 622 ListGraph::erase(e); 623 } 624 489 625 ///Common data storage for the edge pairs. 490 626 … … 499 635 typedef Edge KeyType; 500 636 501 SymEdgeMap(const Sym SmartGraph &_G) :637 SymEdgeMap(const SymListGraph &_G) : 502 638 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2) 503 639 { 504 static_cast<const Sym SmartGraph*>(G)>dyn_edge_maps.push_back(this);505 } 506 SymEdgeMap(const Sym SmartGraph &_G,const T &t) :640 static_cast<const SymListGraph*>(G)>dyn_edge_maps.push_back(this); 641 } 642 SymEdgeMap(const SymListGraph &_G,const T &t) : 507 643 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t) 508 644 { … … 536 672 if(G) { 537 673 std::vector<DynMapBase<Edge>* >::iterator i; 538 for(i=static_cast<const Sym SmartGraph*>(G)>dyn_edge_maps.begin();539 i!=static_cast<const Sym SmartGraph*>(G)>dyn_edge_maps.end()674 for(i=static_cast<const SymListGraph*>(G)>dyn_edge_maps.begin(); 675 i!=static_cast<const SymListGraph*>(G)>dyn_edge_maps.end() 540 676 && *i!=this; ++i) ; 541 677 //if(*i==this) G>dyn_edge_maps.erase(i); //Way too slow... 542 678 //A better way to do that: (Is this really important?) 543 679 if(*i==this) { 544 *i=static_cast<const Sym SmartGraph*>(G)>dyn_edge_maps.back();545 static_cast<const Sym SmartGraph*>(G)>dyn_edge_maps.pop_back();680 *i=static_cast<const SymListGraph*>(G)>dyn_edge_maps.back(); 681 static_cast<const SymListGraph*>(G)>dyn_edge_maps.pop_back(); 546 682 } 547 683 }
Note: See TracChangeset
for help on using the changeset viewer.