Changeset 164:970b265696b0 in lemon-0.x for src/work/alpar
- Timestamp:
- 03/10/04 18:47:54 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@231
- Location:
- src/work/alpar
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/alpar/smart_graph.h
r157 r164 7 7 #include <limits.h> 8 8 9 struct _Invalid {} Invalid; 9 #include <invalid.h> 10 10 11 11 namespace hugo { … … 47 47 template <typename T> class DynEdgeMap; 48 48 49 class Node; 50 class Edge; 51 52 protected: 53 mutable std::vector<DynMapBase<Node> * > dyn_node_maps; 54 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; 55 56 public: 57 49 58 class NodeIt; 50 59 class EdgeIt; 51 52 protected:53 mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps;54 mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;55 56 public:57 58 class EachNodeIt;59 class EachEdgeIt;60 60 class OutEdgeIt; 61 61 class InEdgeIt; 62 62 63 // class Node It{ int n; };64 // class EachNodeIt : public NodeIt{ };65 // class Edge It{ int n; };66 // class E achEdgeIt : public EdgeIt{};67 // class OutEdgeIt : public Edge It{};68 // class InEdgeIt : public Edge It{};69 // class SymEdge It;63 // class Node { int n; }; 64 // class NodeIt : public Node { }; 65 // class Edge { int n; }; 66 // class EdgeIt : public Edge {}; 67 // class OutEdgeIt : public Edge {}; 68 // class InEdgeIt : public Edge {}; 69 // class SymEdge; 70 70 71 71 template <typename T> class NodeMap; … … 81 81 ~SmartGraph() 82 82 { 83 for(std::vector<DynMapBase<Node It> * >::iterator i=dyn_node_maps.begin();83 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 84 84 i!=dyn_node_maps.end(); ++i) (**i).G=NULL; 85 for(std::vector<DynMapBase<Edge It> * >::iterator i=dyn_edge_maps.begin();85 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 86 86 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; 87 87 } … … 94 94 95 95 96 Node It tail(EdgeIte) const { return edges[e.n].tail; }97 Node It head(EdgeIte) const { return edges[e.n].head; }98 99 // Node ItaNode(const OutEdgeIt& e) const { return tail(e); }100 // Node ItaNode(const InEdgeIt& e) const { return head(e); }101 // //Node It aNode(const SymEdgeIt& e) const { return e.aNode(); }102 103 // Node ItbNode(const OutEdgeIt& e) const { return head(e); }104 // Node ItbNode(const InEdgeIt& e) const { return tail(e); }105 // //Node It bNode(const SymEdgeIt& e) const { return e.bNode(); }106 107 EachNodeIt& getFirst(EachNodeIt& v) const {108 v= EachNodeIt(*this); return v; }109 E achEdgeIt& getFirst(EachEdgeIt& e) const {110 e=E achEdgeIt(*this); return e; }111 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeItv) const {96 Node tail(Edge e) const { return edges[e.n].tail; } 97 Node head(Edge e) const { return edges[e.n].head; } 98 99 // Node aNode(const OutEdgeIt& e) const { return tail(e); } 100 // Node aNode(const InEdgeIt& e) const { return head(e); } 101 // //Node aNode(const SymEdge& e) const { return e.aNode(); } 102 103 // Node bNode(const OutEdgeIt& e) const { return head(e); } 104 // Node bNode(const InEdgeIt& e) const { return tail(e); } 105 // //Node bNode(const SymEdge& e) const { return e.bNode(); } 106 107 NodeIt& first(NodeIt& v) const { 108 v=NodeIt(*this); return v; } 109 EdgeIt& first(EdgeIt& e) const { 110 e=EdgeIt(*this); return e; } 111 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 112 112 e=OutEdgeIt(*this,v); return e; } 113 InEdgeIt& getFirst(InEdgeIt& e, const NodeItv) const {113 InEdgeIt& first(InEdgeIt& e, const Node v) const { 114 114 e=InEdgeIt(*this,v); return e; } 115 115 … … 122 122 123 123 template< typename It > 124 It first(Node Itv) const {124 It first(Node v) const { 125 125 It e; 126 126 getFirst(e, v); … … 128 128 } 129 129 130 bool valid(Edge Ite) const { return e.n!=-1; }131 // bool valid(E achEdgeIt e) const { return e.n<int(edges.size()); }132 bool valid(Node Itn) const { return n.n!=-1; }133 134 void setInvalid(Edge It&e) { e.n=-1; }135 void setInvalid(Node It&n) { n.n=-1; }130 bool valid(Edge e) const { return e.n!=-1; } 131 // bool valid(EdgeIt e) const { return e.n<int(edges.size()); } 132 bool valid(Node n) const { return n.n!=-1; } 133 134 void setInvalid(Edge &e) { e.n=-1; } 135 void setInvalid(Node &n) { n.n=-1; } 136 136 137 137 template <typename It> It getNext(It it) const … … 139 139 //{ It tmp; tmp.n=it.n+1; return tmp; } 140 140 141 Node It& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }141 Node& next(Node& it) const { it.n=(it.n+2)%nodes.size()-1; return it; } 142 142 OutEdgeIt& next(OutEdgeIt& it) const 143 143 { it.n=edges[it.n].next_out; return it; } 144 144 InEdgeIt& next(InEdgeIt& it) const 145 145 { it.n=edges[it.n].next_in; return it; } 146 E achEdgeIt& next(EachEdgeIt& it) const { --it.n; return it; }147 148 int id(Node Itv) const { return v.n; }149 int id(Edge Ite) const { return e.n; }150 151 Node ItaddNode() {152 Node Itn; n.n=nodes.size();146 EdgeIt& next(EdgeIt& it) const { --it.n; return it; } 147 148 int id(Node v) const { return v.n; } 149 int id(Edge e) const { return e.n; } 150 151 Node addNode() { 152 Node n; n.n=nodes.size(); 153 153 nodes.push_back(NodeT()); //FIXME: Hmmm... 154 154 155 for(std::vector<DynMapBase<Node It> * >::iterator i=dyn_node_maps.begin();155 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 156 156 i!=dyn_node_maps.end(); ++i) (**i).add(n.n); 157 157 … … 159 159 } 160 160 161 Edge It addEdge(NodeIt u, NodeItv) {162 Edge Ite; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...161 Edge addEdge(Node u, Node v) { 162 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... 163 163 edges[e.n].tail=u.n; edges[e.n].head=v.n; 164 164 edges[e.n].next_out=nodes[u.n].first_out; … … 166 166 nodes[u.n].first_out=nodes[v.n].first_in=e.n; 167 167 168 for(std::vector<DynMapBase<Edge It> * >::iterator i=dyn_edge_maps.begin();168 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 169 169 i!=dyn_edge_maps.end(); ++i) (**i).add(e); 170 170 … … 174 174 void clear() {nodes.clear();edges.clear();} 175 175 176 class Node It{176 class Node { 177 177 friend class SmartGraph; 178 178 template <typename T> friend class NodeMap; 179 179 template <typename T> friend class DynNodeMap; 180 180 181 friend class Edge It;181 friend class Edge; 182 182 friend class OutEdgeIt; 183 183 friend class InEdgeIt; 184 friend class SymEdge It;184 friend class SymEdge; 185 185 186 186 protected: 187 187 int n; 188 friend int SmartGraph::id(Node Itv) const;189 Node It(int nn) {n=nn;}190 public: 191 Node It() {}192 Node It (_Invalid i) { n=-1; }193 bool operator==(const Node Iti) const {return n==i.n;}194 bool operator!=(const Node Iti) const {return n!=i.n;}195 bool operator<(const Node Iti) const {return n<i.n;}196 }; 197 198 class EachNodeIt : public NodeIt{199 friend class SmartGraph; 200 public: 201 EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }202 EachNodeIt() : NodeIt() { }203 }; 204 205 class Edge It{188 friend int SmartGraph::id(Node v) const; 189 Node(int nn) {n=nn;} 190 public: 191 Node() {} 192 Node (Invalid i) { n=-1; } 193 bool operator==(const Node i) const {return n==i.n;} 194 bool operator!=(const Node i) const {return n!=i.n;} 195 bool operator<(const Node i) const {return n<i.n;} 196 }; 197 198 class NodeIt : public Node { 199 friend class SmartGraph; 200 public: 201 NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { } 202 NodeIt() : Node() { } 203 }; 204 205 class Edge { 206 206 friend class SmartGraph; 207 207 template <typename T> friend class EdgeMap; 208 208 template <typename T> friend class DynEdgeMap; 209 209 210 friend class Node; 210 211 friend class NodeIt; 211 friend class EachNodeIt;212 212 protected: 213 213 int n; 214 friend int SmartGraph::id(Edge Ite) const;215 216 Edge It(int nn) {n=nn;}217 public: 218 Edge It() { }219 Edge It (_Invalid i) { n=-1; }220 bool operator==(const Edge Iti) const {return n==i.n;}221 bool operator!=(const Edge Iti) const {return n!=i.n;}222 bool operator<(const Edge Iti) const {return n<i.n;}223 }; 224 225 class E achEdgeIt : public EdgeIt{226 friend class SmartGraph; 227 public: 228 E achEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }229 E achEdgeIt (_Invalid i) : EdgeIt(i) { }230 E achEdgeIt() : EdgeIt() { }231 }; 232 233 class OutEdgeIt : public Edge It{214 friend int SmartGraph::id(Edge e) const; 215 216 Edge(int nn) {n=nn;} 217 public: 218 Edge() { } 219 Edge (Invalid i) { n=-1; } 220 bool operator==(const Edge i) const {return n==i.n;} 221 bool operator!=(const Edge i) const {return n!=i.n;} 222 bool operator<(const Edge i) const {return n<i.n;} 223 }; 224 225 class EdgeIt : public Edge { 226 friend class SmartGraph; 227 public: 228 EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { } 229 EdgeIt (Invalid i) : Edge(i) { } 230 EdgeIt() : Edge() { } 231 }; 232 233 class OutEdgeIt : public Edge { 234 234 friend class SmartGraph; 235 235 public: 236 OutEdgeIt() : Edge It() { }237 OutEdgeIt ( _Invalid i) : EdgeIt(i) { }238 239 OutEdgeIt(const SmartGraph& G,const Node Itv)240 : Edge It(G.nodes[v.n].first_out) {}241 }; 242 243 class InEdgeIt : public Edge It{236 OutEdgeIt() : Edge() { } 237 OutEdgeIt (Invalid i) : Edge(i) { } 238 239 OutEdgeIt(const SmartGraph& G,const Node v) 240 : Edge(G.nodes[v.n].first_out) {} 241 }; 242 243 class InEdgeIt : public Edge { 244 244 friend class SmartGraph; 245 245 public: 246 InEdgeIt() : Edge It() { }247 InEdgeIt ( _Invalid i) : EdgeIt(i) { }248 InEdgeIt(const SmartGraph& G,Node It v) :EdgeIt(G.nodes[v.n].first_in){}246 InEdgeIt() : Edge() { } 247 InEdgeIt (Invalid i) : Edge(i) { } 248 InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){} 249 249 }; 250 250 … … 257 257 public: 258 258 typedef T ValueType; 259 typedef Node ItKeyType;259 typedef Node KeyType; 260 260 NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { } 261 261 NodeMap(const SmartGraph& _G, T a) : 262 262 G(_G), container(G.maxNodeId(), a) { } 263 void set(Node Itn, T a) { container[n.n]=a; }264 T get(Node Itn) const { return container[n.n]; }265 T& operator[](Node Itn) { return container[n.n]; }266 const T& operator[](Node Itn) const { return container[n.n]; }263 void set(Node n, T a) { container[n.n]=a; } 264 T get(Node n) const { return container[n.n]; } 265 T& operator[](Node n) { return container[n.n]; } 266 const T& operator[](Node n) const { return container[n.n]; } 267 267 void update() { container.resize(G.maxNodeId()); } 268 268 void update(T a) { container.resize(G.maxNodeId(), a); } … … 275 275 public: 276 276 typedef T ValueType; 277 typedef Edge ItKeyType;277 typedef Edge KeyType; 278 278 EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { } 279 279 EdgeMap(const SmartGraph& _G, T a) : 280 280 G(_G), container(G.maxEdgeId(), a) { } 281 void set(Edge Ite, T a) { container[e.n]=a; }282 T get(Edge Ite) const { return container[e.n]; }283 T& operator[](Edge Ite) { return container[e.n]; }284 const T& operator[](Edge Ite) const { return container[e.n]; }281 void set(Edge e, T a) { container[e.n]=a; } 282 T get(Edge e) const { return container[e.n]; } 283 T& operator[](Edge e) { return container[e.n]; } 284 const T& operator[](Edge e) const { return container[e.n]; } 285 285 void update() { container.resize(G.maxEdgeId()); } 286 286 void update(T a) { container.resize(G.maxEdgeId(), a); } 287 287 }; 288 288 289 template <typename T> class DynNodeMap : public DynMapBase<Node It>289 template <typename T> class DynNodeMap : public DynMapBase<Node> 290 290 { 291 291 std::vector<T> container; … … 293 293 public: 294 294 typedef T ValueType; 295 typedef Node ItKeyType;295 typedef Node KeyType; 296 296 297 297 DynNodeMap(const SmartGraph &_G) : 298 DynMapBase<Node It>(_G), container(_G.maxNodeId())298 DynMapBase<Node>(_G), container(_G.maxNodeId()) 299 299 { 300 300 //FIXME: What if there are empty Id's? … … 305 305 { 306 306 if(G) { 307 std::vector<DynMapBase<Node It>* >::iterator i;307 std::vector<DynMapBase<Node>* >::iterator i; 308 308 for(i=G->dyn_node_maps.begin(); 309 309 i!=G->dyn_node_maps.end() && *i!=this; ++i) ; … … 317 317 } 318 318 319 void add(const Node Itk)319 void add(const Node k) 320 320 { 321 321 if(k.n>=container.size()) container.resize(k.n+1); 322 322 } 323 // void erase(const Node Itk)323 // void erase(const Node k) 324 324 // { 325 325 // //FIXME: Please implement me. 326 326 // } 327 // void erase(const Edge Itk)327 // void erase(const Edge k) 328 328 // { 329 329 // //FIXME: Please implement me. 330 330 // } 331 331 332 void set(Node Itn, T a) { container[n.n]=a; }333 T get(Node Itn) const { return container[n.n]; }334 T& operator[](Node Itn) { return container[n.n]; }335 const T& operator[](Node Itn) const { return container[n.n]; }332 void set(Node n, T a) { container[n.n]=a; } 333 T get(Node n) const { return container[n.n]; } 334 T& operator[](Node n) { return container[n.n]; } 335 const T& operator[](Node n) const { return container[n.n]; } 336 336 337 337 void update() {} //Useless for DynMaps … … 339 339 }; 340 340 341 template <typename T> class DynEdgeMap : public DynMapBase<Edge It>341 template <typename T> class DynEdgeMap : public DynMapBase<Edge> 342 342 { 343 343 std::vector<T> container; … … 345 345 public: 346 346 typedef T ValueType; 347 typedef Edge ItKeyType;347 typedef Edge KeyType; 348 348 349 349 DynEdgeMap(const SmartGraph &_G) : 350 DynMapBase<Edge It>(_G), container(_G.maxEdgeId())350 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) 351 351 { 352 352 //FIXME: What if there are empty Id's? … … 357 357 { 358 358 if(G) { 359 std::vector<DynMapBase<Edge It>* >::iterator i;359 std::vector<DynMapBase<Edge>* >::iterator i; 360 360 for(i=G->dyn_edge_maps.begin(); 361 361 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; … … 369 369 } 370 370 371 void add(const Edge Itk)371 void add(const Edge k) 372 372 { 373 373 if(k.n>=int(container.size())) container.resize(k.n+1); 374 374 } 375 void erase(const Edge Itk)375 void erase(const Edge k) 376 376 { 377 377 //FIXME: Please implement me. 378 378 } 379 379 380 void set(Edge Itn, T a) { container[n.n]=a; }381 T get(Edge Itn) const { return container[n.n]; }382 T& operator[](Edge Itn) { return container[n.n]; }383 const T& operator[](Edge Itn) const { return container[n.n]; }380 void set(Edge n, T a) { container[n.n]=a; } 381 T get(Edge n) const { return container[n.n]; } 382 T& operator[](Edge n) { return container[n.n]; } 383 const T& operator[](Edge n) const { return container[n.n]; } 384 384 385 385 void update() {} //Useless for DynMaps -
src/work/alpar/smart_graph_demo.cc
r157 r164 1 1 #include<smart_graph.h> 2 #include<emptygraph.h> 2 3 3 4 #include <iostream> 5 #include <vector> 4 6 5 7 using namespace hugo; 6 8 7 SmartGraph::OutEdgeIt safeFirstOut(const SmartGraph &G, SmartGraph::NodeIt n) 9 //typedef SmartGraph Graph; 10 typedef EmptyGraph Graph; 11 12 13 Graph::OutEdgeIt safeFirstOut(const Graph &G, Graph::Node n) 8 14 { 9 return G.valid(n) ? SmartGraph::OutEdgeIt(G,n):Invalid;15 return G.valid(n) ? Graph::OutEdgeIt(G,n):INVALID; 10 16 } 11 17 … … 13 19 { 14 20 15 typedef SmartGraph::EdgeIt EdgeIt;16 typedef SmartGraph::InEdgeIt InEdgeIt;17 typedef SmartGraph::OutEdgeIt OutEdgeIt;18 typedef SmartGraph::EachEdgeIt EachEdgeIt;19 typedef SmartGraph::NodeIt NodeIt;20 typedef SmartGraph::EachNodeIt EachNodeIt;21 typedef Graph::Edge Edge; 22 typedef Graph::InEdgeIt InEdgeIt; 23 typedef Graph::OutEdgeIt OutEdgeIt; 24 typedef Graph::EdgeIt EdgeIt; 25 typedef Graph::Node Node; 26 typedef Graph::NodeIt NodeIt; 21 27 22 SmartGraph G;23 EachNodeIt n;28 Graph G; 29 NodeIt n; 24 30 25 31 26 // std::cout.form("%s: %d\n","Sztring",15);27 28 32 for(int i=0;i<10;i++) G.addNode(); 29 for(G. getFirst(n);G.valid(n);G.next(n))30 for( EachNodeIt m(G);m!=Invalid;G.next(m))33 for(G.first(n);G.valid(n);G.next(n)) 34 for(NodeIt m(G);m!=INVALID;G.next(m)) 31 35 if(n!=m) G.addEdge(n,m); 32 36 33 37 OutEdgeIt e = safeFirstOut(G,n); 34 OutEdgeIt f = safeFirstOut(G,EachNodeIt(G)); 38 OutEdgeIt f = safeFirstOut(G,NodeIt(G)); 39 40 41 InEdgeIt i(INVALID), j; 42 InEdgeIt ii(i); 43 ii=G.first(i,n); 44 ii=G.next(i); 45 46 OutEdgeIt o(INVALID), oo; 47 OutEdgeIt ooo(oo); 48 oo=G.first(o,n); 49 oo=G.next(o); 50 51 EdgeIt ei(INVALID), eie; 52 EdgeIt eiee(ei); 53 eie=G.first(ei); 54 eie=G.next(ei); 55 56 Edge eee(i); 57 eee=o; 58 eee=eie; 59 60 61 bool tm; 62 tm = G.valid(n) && G.valid(i) && G.valid(o) && G.valid(ei); 63 64 std::vector<InEdgeIt> v(10); 65 std::vector<InEdgeIt> w(10,INVALID); 35 66 36 67 }
Note: See TracChangeset
for help on using the changeset viewer.