Changeset 774:4297098d9677 in lemon-0.x for src/hugo/list_graph.h
- Timestamp:
- 08/30/04 14:01:47 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1066
- File:
-
- 1 edited
-
src/hugo/list_graph.h (modified) (24 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/list_graph.h
r722 r774 132 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 134 NodeIt& first(NodeIt& v) const { 141 135 v=NodeIt(*this); return v; } … … 147 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) const169 { it.n=edges[it.n].next_out; return it; }170 InEdgeIt& next(InEdgeIt& it) const171 { 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 143 static int id(Node v) { return v.n; } 187 144 static int id(Edge e) { return e.n; } … … 251 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 227 private: 255 228 void eraseEdge(int n) { … … 325 298 bool operator!=(const Node i) const {return n!=i.n;} 326 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 304 class NodeIt : public Node { 305 const ListGraph *G; 330 306 friend class ListGraph; 331 307 public: 332 308 NodeIt() : Node() { } 333 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 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 … … 365 347 ///make class \c SymListGraph::SymEdgeMap friend of Edge 366 348 int &idref() {return n;} 367 const int &idref() const {return n;} 368 }; 349 const int &idref() const {return n;} 350 // ///Validity check 351 // operator bool() { return n!=-1; } 352 }; 369 353 370 354 class EdgeIt : public Edge { 355 const ListGraph *G; 371 356 friend class ListGraph; 372 357 public: 373 EdgeIt(const ListGraph& G) : Edge() {358 EdgeIt(const ListGraph& _G) : Edge(), G(&_G) { 374 359 int m; 375 for(m= G.first_node;376 m!=-1 && G.nodes[m].first_in == -1; m =G.nodes[m].next);377 n = (m==-1)?-1: G.nodes[m].first_in;360 for(m=_G.first_node; 361 m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next); 362 n = (m==-1)?-1:_G.nodes[m].first_in; 378 363 } 379 364 EdgeIt (Invalid i) : Edge(i) { } 365 EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } 380 366 EdgeIt() : Edge() { } 381 367 ///\bug This is a workaround until somebody tells me how to 382 368 ///make class \c SymListGraph::SymEdgeMap friend of Edge 383 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 385 class OutEdgeIt : public Edge { 386 const ListGraph *G; 387 387 friend class ListGraph; 388 388 public: 389 389 OutEdgeIt() : Edge() { } 390 OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } 390 391 OutEdgeIt (Invalid i) : Edge(i) { } 391 392 392 OutEdgeIt(const ListGraph& G,const Node v) 393 : Edge(G.nodes[v.n].first_out) {} 393 OutEdgeIt(const ListGraph& _G,const Node v) 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 400 class InEdgeIt : public Edge { 401 const ListGraph *G; 397 402 friend class ListGraph; 398 403 public: 399 404 InEdgeIt() : Edge() { } 405 InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } 400 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 … … 839 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 851 NodeIt& first(NodeIt& v) const { 848 852 v=NodeIt(*this); return v; } … … 854 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) const869 { 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 860 int id(Node v) const { return v.n; } 880 861 int id(Edge e) const { return -1; } … … 928 909 } 929 910 911 912 Edge findEdge(Node u,Node v, Edge prev = INVALID) 913 { 914 return INVALID; 915 } 916 930 917 ///\bug Dynamic maps must be updated! 931 918 /// … … 956 943 957 944 class NodeIt : public Node { 945 const NodeSet *G; 958 946 friend class NodeSet; 959 947 public: 960 948 NodeIt() : Node() { } 949 NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { } 961 950 NodeIt(Invalid i) : Node(i) { } 962 NodeIt(const NodeSet& G) : Node(G.first_node) { } 963 ///\todo Undocumented conversion Node -\> NodeIt. 964 NodeIt(const NodeSet& G, const Node &n) : Node(n) { } 965 951 NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { } 952 NodeIt &operator++() { 953 n=G->nodes[n].next; 954 return *this; 955 } 966 956 }; 967 957 … … 994 984 public: 995 985 EdgeIt(const NodeSet& G) : Edge() { } 986 EdgeIt(const NodeSet&, Edge) : Edge() { } 996 987 EdgeIt (Invalid i) : Edge(i) { } 997 988 EdgeIt() : Edge() { } … … 999 990 ///make class \c SymNodeSet::SymEdgeMap friend of Edge 1000 991 // int idref() {return -1;} 992 EdgeIt operator++() { return INVALID; } 1001 993 }; 1002 994 … … 1005 997 public: 1006 998 OutEdgeIt() : Edge() { } 999 OutEdgeIt(const NodeSet&, Edge) : Edge() { } 1007 1000 OutEdgeIt (Invalid i) : Edge(i) { } 1008 1001 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {} 1002 OutEdgeIt operator++() { return INVALID; } 1009 1003 }; 1010 1004 … … 1013 1007 public: 1014 1008 InEdgeIt() : Edge() { } 1009 InEdgeIt(const NodeSet&, Edge) : Edge() { } 1015 1010 InEdgeIt (Invalid i) : Edge(i) { } 1016 1011 InEdgeIt(const NodeSet& G,Node v) :Edge() {} 1012 InEdgeIt operator++() { return INVALID; } 1017 1013 }; 1018 1014 … … 1200 1196 public: 1201 1197 NodeIt() : NodeGraphType::NodeIt() { } 1198 NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { } 1202 1199 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} 1203 1200 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { } 1204 1201 NodeIt(const typename NodeGraphType::NodeIt &n) 1205 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 1204 operator Node() { return Node(*this);} 1205 NodeIt &operator++() 1206 { this->NodeGraphType::NodeIt::operator++(); return *this;} 1211 1207 }; 1212 1208 … … 1311 1307 Node tail(Edge e) const { return edges[e.n].tail; } 1312 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 1310 NodeIt& first(NodeIt& v) const { … … 1327 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) const1342 { It tmp(it); return next(tmp); }1343 1344 NodeIt& next(NodeIt& it) const { G.next(it); return it; }1345 OutEdgeIt& next(OutEdgeIt& it) const1346 { it.n=edges[it.n].next_out; return it; }1347 InEdgeIt& next(InEdgeIt& it) const1348 { 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 1319 int id(Edge e) const { return e.n; } 1364 1320 … … 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 1373 private: 1402 1374 void eraseEdge(int n) { … … 1461 1433 friend class NodeIt; 1462 1434 public: 1463 ///\bug It shou d be at least protected1435 ///\bug It should be at least protected 1464 1436 /// 1465 1437 int n; … … 1484 1456 template <typename T> friend class EdgeMap; 1485 1457 1486 1487 public: 1488 EdgeIt(const EdgeSet& G) : Edge() {1458 const EdgeSet *G; 1459 public: 1460 EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) { 1489 1461 // typename NodeGraphType::Node m; 1490 1462 NodeIt m; 1491 for(G.first(m); 1492 G.valid(m) && G.nodes[m].first_in == -1; G.next(m)); 1493 //AJJAJ! This is a non sense!!!!!!! 1494 this->n = G.valid(m)?-1:G.nodes[m].first_in; 1495 } 1463 for(G->first(m); 1464 m!=INVALID && G->nodes[m].first_in == -1; ++m); 1465 ///\bug AJJAJ! This is a non sense!!!!!!! 1466 this->n = m!=INVALID?-1:G->nodes[m].first_in; 1467 } 1468 EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } 1496 1469 EdgeIt (Invalid i) : Edge(i) { } 1497 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 1479 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge 1500 1480 int &idref() {return this->n;} … … 1502 1482 1503 1483 class OutEdgeIt : public Edge { 1484 const EdgeSet *G; 1504 1485 friend class EdgeSet; 1505 1486 public: 1506 1487 OutEdgeIt() : Edge() { } 1507 1488 OutEdgeIt (Invalid i) : Edge(i) { } 1508 1509 OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { } 1489 OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } 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 1496 class InEdgeIt : public Edge { 1497 const EdgeSet *G; 1513 1498 friend class EdgeSet; 1514 1499 public: 1515 1500 InEdgeIt() : Edge() { } 1516 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 … … 1555 1543 //FIXME: What if there are empty Id's? 1556 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 1547 EdgeMap(const EdgeSet &_G,const T &t) : 1560 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 1552 EdgeMap(const EdgeMap<T> &m) : 1565 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 … … 1573 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 1564 typename std::vector<TT>::const_iterator i; 1577 1565 for(typename std::vector<TT>::const_iterator i=m.container.begin(); … … 1582 1570 ~EdgeMap() 1583 1571 { 1584 if( G) {1572 if(this->G) { 1585 1573 typename std::vector<DynMapBase<Edge>* >::iterator i; 1586 for(i= G->dyn_edge_maps.begin();1587 i!= G->dyn_edge_maps.end() && *i!=this; ++i) ;1574 for(i=this->G->dyn_edge_maps.begin(); 1575 i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ; 1588 1576 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... 1589 1577 //A better way to do that: (Is this really important?) 1590 1578 if(*i==this) { 1591 *i= G->dyn_edge_maps.back();1592 G->dyn_edge_maps.pop_back();1579 *i=this->G->dyn_edge_maps.back(); 1580 this->G->dyn_edge_maps.pop_back(); 1593 1581 } 1594 1582 } … … 1603 1591 ///\bug This doesn't work. Why? 1604 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 1594 //T get(Edge n) const { return container[n.n]; } 1607 1595 typename std::vector<T>::reference 1608 1596 ///\bug This doesn't work. Why? 1609 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 1599 typename std::vector<T>::const_reference 1612 1600 ///\bug This doesn't work. Why? 1613 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 1604 ///\warning There is no safety check at all!
Note: See TracChangeset
for help on using the changeset viewer.
