Changeset 157:ee17030e5f47 in lemon0.x for src/work/alpar/smart_graph.h
 Timestamp:
 03/07/04 20:33:34 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@219
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/smart_graph.h
r136 r157 4 4 #define SMART_GRAPH_H 5 5 6 #include <iostream>7 6 #include <vector> 8 7 #include <limits.h> 9 8 9 struct _Invalid {} Invalid; 10 10 11 namespace hugo { 11 12 12 13 class SmartGraph { 13 14 14 static const int INVALID_EDGE=1;15 static const int INVALID_NODE=INT_MAX;15 // static const int INVALID=1; 16 // static const int INVALID_NODE=INT_MAX; 16 17 17 18 struct NodeT 18 19 { 19 20 int first_in,first_out; 20 NodeT() : first_in( INVALID_EDGE), first_out(INVALID_EDGE) {}21 NodeT() : first_in(1), first_out(1) {} 21 22 }; 22 23 struct EdgeT … … 24 25 int head, tail, next_in, next_out; 25 26 //FIXME: is this necessary? 26 EdgeT() : next_in( INVALID_EDGE), next_out(INVALID_EDGE) {}27 EdgeT() : next_in(1), next_out(1) {} 27 28 }; 28 29 … … 38 39 virtual void add(const Key k) = NULL; 39 40 virtual void erase(const Key k) = NULL; 40 DynMapBase( SmartGraph &_G) : G(&_G) {}41 DynMapBase(const SmartGraph &_G) : G(&_G) {} 41 42 virtual ~DynMapBase() {} 42 43 friend class SmartGraph; 43 44 }; 44 45 45 public: 46 46 template <typename T> class DynEdgeMap; … … 51 51 52 52 protected: 53 std::vector<DynMapBase<NodeIt> * > dyn_node_maps;54 std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;53 mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps; 54 mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps; 55 55 56 56 public: … … 61 61 class InEdgeIt; 62 62 63 // 63 // class NodeIt { int n; }; 64 64 // class EachNodeIt : public NodeIt { }; 65 65 // class EdgeIt { int n; }; … … 67 67 // class OutEdgeIt : public EdgeIt {}; 68 68 // class InEdgeIt : public EdgeIt {}; 69 // class SymEdgeIt;69 // class SymEdgeIt; 70 70 71 71 template <typename T> class NodeMap; … … 97 97 NodeIt head(EdgeIt e) const { return edges[e.n].head; } 98 98 99 NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }100 NodeIt aNode(const InEdgeIt& e) const { return head(e); }101 //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }102 103 NodeIt bNode(const OutEdgeIt& e) const { return head(e); }104 NodeIt bNode(const InEdgeIt& e) const { return tail(e); }105 //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }99 // NodeIt aNode(const OutEdgeIt& e) const { return tail(e); } 100 // NodeIt aNode(const InEdgeIt& e) const { return head(e); } 101 // //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); } 102 103 // NodeIt bNode(const OutEdgeIt& e) const { return head(e); } 104 // NodeIt bNode(const InEdgeIt& e) const { return tail(e); } 105 // //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); } 106 106 107 107 EachNodeIt& getFirst(EachNodeIt& v) const { … … 128 128 } 129 129 130 bool valid(EdgeIt e) const { return e.n!= INVALID_EDGE; }131 bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }132 bool valid(NodeIt n) const { return n.n <int(nodes.size()); }133 134 void setInvalid(EdgeIt &e) { e.n= INVALID_EDGE; }135 void setInvalid(NodeIt &n) { n.n= INVALID_NODE; }136 137 template <typename It> It next(It it) const138 // { It tmp(it); return goNext(tmp); }139 { It tmp; tmp.n=it.n+1; return tmp; }140 141 NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }142 OutEdgeIt& goNext(OutEdgeIt& it) const130 bool valid(EdgeIt e) const { return e.n!=1; } 131 // bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); } 132 bool valid(NodeIt n) const { return n.n!=1; } 133 134 void setInvalid(EdgeIt &e) { e.n=1; } 135 void setInvalid(NodeIt &n) { n.n=1; } 136 137 template <typename It> It getNext(It it) const 138 { It tmp(it); return next(tmp); } 139 //{ It tmp; tmp.n=it.n+1; return tmp; } 140 141 NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()1; return it; } 142 OutEdgeIt& next(OutEdgeIt& it) const 143 143 { it.n=edges[it.n].next_out; return it; } 144 InEdgeIt& goNext(InEdgeIt& it) const144 InEdgeIt& next(InEdgeIt& it) const 145 145 { it.n=edges[it.n].next_in; return it; } 146 EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }146 EachEdgeIt& next(EachEdgeIt& it) const { it.n; return it; } 147 147 148 148 int id(NodeIt v) const { return v.n; } … … 167 167 168 168 for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin(); 169 i!=dyn_edge_maps.end(); ++i) (**i).add(e .n);169 i!=dyn_edge_maps.end(); ++i) (**i).add(e); 170 170 171 171 return e; … … 187 187 int n; 188 188 friend int SmartGraph::id(NodeIt v) const; 189 NodeIt(int nn) {n=nn;} 189 190 public: 190 191 NodeIt() {} 191 NodeIt (int nn) {n=nn;}192 NodeIt (_Invalid i) { n=1; } 192 193 bool operator==(const NodeIt i) const {return n==i.n;} 193 194 bool operator!=(const NodeIt i) const {return n!=i.n;} 195 bool operator<(const NodeIt i) const {return n<i.n;} 194 196 }; 195 197 … … 197 199 friend class SmartGraph; 198 200 public: 199 EachNodeIt(const SmartGraph& G) : NodeIt( 0) { }201 EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:1) { } 200 202 EachNodeIt() : NodeIt() { } 201 203 }; … … 211 213 int n; 212 214 friend int SmartGraph::id(EdgeIt e) const; 215 216 EdgeIt(int nn) {n=nn;} 213 217 public: 214 218 EdgeIt() { } 215 EdgeIt (int nn) {n=nn;}219 EdgeIt (_Invalid i) { n=1; } 216 220 bool operator==(const EdgeIt i) const {return n==i.n;} 217 221 bool operator!=(const EdgeIt i) const {return n!=i.n;} 222 bool operator<(const EdgeIt i) const {return n<i.n;} 218 223 }; 219 224 … … 221 226 friend class SmartGraph; 222 227 public: 223 EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { } 228 EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()1) { } 229 EachEdgeIt (_Invalid i) : EdgeIt(i) { } 224 230 EachEdgeIt() : EdgeIt() { } 225 231 }; … … 229 235 public: 230 236 OutEdgeIt() : EdgeIt() { } 237 OutEdgeIt (_Invalid i) : EdgeIt(i) { } 238 231 239 OutEdgeIt(const SmartGraph& G,const NodeIt v) 232 240 : EdgeIt(G.nodes[v.n].first_out) {} … … 237 245 public: 238 246 InEdgeIt() : EdgeIt() { } 247 InEdgeIt (_Invalid i) : EdgeIt(i) { } 239 248 InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){} 240 249 }; … … 286 295 typedef NodeIt KeyType; 287 296 288 DynNodeMap( SmartGraph &_G) :297 DynNodeMap(const SmartGraph &_G) : 289 298 DynMapBase<NodeIt>(_G), container(_G.maxNodeId()) 290 299 { … … 312 321 if(k.n>=container.size()) container.resize(k.n+1); 313 322 } 314 void erase(const NodeIt k) 315 { 316 //FIXME: Please implement me. 317 } 323 // void erase(const NodeIt k) 324 // { 325 // //FIXME: Please implement me. 326 // } 327 // void erase(const EdgeIt k) 328 // { 329 // //FIXME: Please implement me. 330 // } 318 331 319 332 void set(NodeIt n, T a) { container[n.n]=a; } … … 334 347 typedef EdgeIt KeyType; 335 348 336 DynEdgeMap( SmartGraph &_G) :349 DynEdgeMap(const SmartGraph &_G) : 337 350 DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId()) 338 351 { … … 377 390 } //namespace hugo 378 391 392 393 394 379 395 #endif //SMART_GRAPH_H
Note: See TracChangeset
for help on using the changeset viewer.