Changeset 105:a3c73e9b9b2e in lemon0.x for src/work/alpar/smart_graph.h
 Timestamp:
 02/20/04 22:45:07 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@140
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/smart_graph.h
r104 r105 1 // * mode:C++ * 2 1 3 #ifndef SMART_GRAPH_H 2 4 #define SMART_GRAPH_H … … 5 7 #include <vector> 6 8 7 namespace marci{9 namespace hugo { 8 10 9 11 class SmartGraph { … … 36 38 class InEdgeIt; 37 39 38 // class NodeIt { int n; };39 // class EachNodeIt : public NodeIt { };40 // class EdgeIt { int n; };41 // class EachEdgeIt : public EdgeIt {};42 // class OutEdgeIt : public EdgeIt {};43 // class InEdgeIt : public EdgeIt {};40 // class NodeIt { int n; }; 41 // class EachNodeIt : public NodeIt { }; 42 // class EdgeIt { int n; }; 43 // class EachEdgeIt : public EdgeIt {}; 44 // class OutEdgeIt : public EdgeIt {}; 45 // class InEdgeIt : public EdgeIt {}; 44 46 // class SymEdgeIt; 45 46 template <typename T> class NodeMap;47 48 template <typename T> class NodeMap; 47 49 template <typename T> class EdgeMap; 48 50 49 private: 50 51 template <typename T> friend class NodeMap; 52 template <typename T> friend class EdgeMap; 51 public: 52 53 /* default constructor */ 54 55 SmartGraph() : nodes(), edges() { } 56 57 ~SmartGraph() {} 58 59 int nodeNum() const { return nodes.size(); } //FIXME: What is this? 60 int edgeNum() const { return edges.size(); } //FIXME: What is this? 61 62 NodeIt tail(EdgeIt e) const { return edges[e.n].tail; } 63 NodeIt head(EdgeIt e) const { return edges[e.n].head; } 64 65 NodeIt aNode(const OutEdgeIt& e) const { return tail(e); } 66 NodeIt aNode(const InEdgeIt& e) const { return head(e); } 67 //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); } 68 69 NodeIt bNode(const OutEdgeIt& e) const { return head(e); } 70 NodeIt bNode(const InEdgeIt& e) const { return tail(e); } 71 //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); } 72 73 EachNodeIt& getFirst(EachNodeIt& v) const { 74 v=EachNodeIt(*this); return v; } 75 EachEdgeIt& getFirst(EachEdgeIt& e) const { 76 e=EachEdgeIt(*this); return e; } 77 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const { 78 e=OutEdgeIt(*this,v); return e; } 79 InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const { 80 e=InEdgeIt(*this,v); return e; } 81 82 template< typename It > 83 It first() const { 84 It e; 85 getFirst(e); 86 return e; 87 } 88 89 template< typename It > 90 It first(NodeIt v) const { 91 It e; 92 getFirst(e, v); 93 return e; 94 } 95 96 bool valid(EdgeIt e) const { return e.n!=INVALID; } 97 bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); } 98 bool valid(NodeIt n) const { return n.n<int(nodes.size()); } 99 100 template <typename It> It next(It it) const 101 // { It tmp(it); return goNext(tmp); } 102 { It tmp; tmp.n=it.n+1; return tmp; } 103 104 NodeIt& goNext(NodeIt& it) const { ++it.n; return it; } 105 OutEdgeIt& goNext(OutEdgeIt& it) const 106 { it.n=edges[it.n].next_out; return it; } 107 InEdgeIt& goNext(InEdgeIt& it) const 108 { it.n=edges[it.n].next_in; return it; } 109 EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; } 110 111 int id(NodeIt v) const { return v.n; } 112 int id(EdgeIt e) const { return e.n; } 113 114 NodeIt addNode() { 115 NodeIt n; n.n=nodes.size(); 116 nodes.push_back(NodeT()); //FIXME: Hmmm... 117 return n; 118 } 119 EdgeIt addEdge(NodeIt u, NodeIt v) { 120 EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... 121 edges[e.n].tail=u.n; edges[e.n].head=v.n; 122 edges[e.n].next_out=nodes[u.n].first_out; 123 edges[e.n].next_in=nodes[v.n].first_in; 124 nodes[u.n].first_out=nodes[v.n].first_in=e.n; 125 return e; 126 } 127 128 void clear() {nodes.clear();edges.clear();} 129 130 class NodeIt { 131 friend class SmartGraph; 132 template <typename T> friend class NodeMap; 133 134 friend class EdgeIt; 135 friend class OutEdgeIt; 136 friend class InEdgeIt; 137 friend class SymEdgeIt; 138 139 protected: 140 int n; 141 friend int SmartGraph::id(NodeIt v) const; 142 public: 143 NodeIt() {} 144 NodeIt(int nn) {n=nn;} 145 bool operator==(const NodeIt i) const {return n==i.n;} 146 bool operator!=(const NodeIt i) const {return n!=i.n;} 147 }; 148 149 class EachNodeIt : public NodeIt { 150 friend class SmartGraph; 151 public: 152 EachNodeIt(const SmartGraph& G) : NodeIt(0) { } 153 EachNodeIt() : NodeIt() { } 154 }; 155 156 class EdgeIt { 157 friend class SmartGraph; 158 template <typename T> friend class EdgeMap; 159 160 friend class NodeIt; 161 friend class EachNodeIt; 162 protected: 163 int n; 164 friend int SmartGraph::id(EdgeIt e) const; 165 public: 166 EdgeIt() { } 167 EdgeIt(int nn) {n=nn;} 168 bool operator==(const EdgeIt i) const {return n==i.n;} 169 bool operator!=(const EdgeIt i) const {return n!=i.n;} 170 }; 171 172 class EachEdgeIt : public EdgeIt { 173 friend class SmartGraph; 174 public: 175 EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { } 176 EachEdgeIt() : EdgeIt() { } 177 }; 178 179 class OutEdgeIt : public EdgeIt { 180 friend class SmartGraph; 181 public: 182 OutEdgeIt() : EdgeIt() { } 183 OutEdgeIt(const SmartGraph& G,const NodeIt v) 184 : EdgeIt(G.nodes[v.n].first_out) {} 185 }; 186 187 class InEdgeIt : public EdgeIt { 188 friend class SmartGraph; 189 public: 190 InEdgeIt() : EdgeIt() { } 191 InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){} 192 }; 193 194 // Map types 53 195 54 196 template <typename T> … … 66 208 T& operator[](NodeIt n) { return container[n.n]; } 67 209 const T& operator[](NodeIt n) const { return container[n.n]; } 68 void resize() { container.resize(G.nodeNum()); }69 void resize(T a) { container.resize(G.nodeNum(), a); }210 void update() { container.resize(G.nodeNum()); } 211 void update(T a) { container.resize(G.nodeNum(), a); } 70 212 }; 71 213 … … 84 226 T& operator[](EdgeIt e) { return container[e.n]; } 85 227 const T& operator[](EdgeIt e) const { return container[e.n]; } 86 void resize() { container.resize(G.edgeNum()); } 87 void resize(T a) { container.resize(G.edgeNum(), a); } 88 }; 89 90 public: 91 92 /* default constructor */ 93 94 SmartGraph() : nodes(), edges() { } 95 96 ~SmartGraph() {} 97 98 int nodeNum() const { return nodes.size(); } //FIXME: What is this? 99 int edgeNum() const { return edges.size(); } //FIXME: What is this? 100 101 NodeIt tail(EdgeIt e) const { return edges[e.n].tail; } 102 NodeIt head(EdgeIt e) const { return edges[e.n].head; } 103 104 NodeIt aNode(const OutEdgeIt& e) const { return tail(e); } 105 NodeIt aNode(const InEdgeIt& e) const { return head(e); } 106 //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); } 107 108 NodeIt bNode(const OutEdgeIt& e) const { return head(e); } 109 NodeIt bNode(const InEdgeIt& e) const { return tail(e); } 110 //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); } 111 112 EachNodeIt& getFirst(EachNodeIt& v) const { 113 v=EachNodeIt(*this); return v; } 114 EachEdgeIt& getFirst(EachEdgeIt& e) const { 115 e=EachEdgeIt(*this); return e; } 116 OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const { 117 e=OutEdgeIt(*this,v); return e; } 118 InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const { 119 e=InEdgeIt(*this,v); return e; } 120 121 template< typename It > 122 It first() const { 123 It e; 124 getFirst(e); 125 return e; 126 } 127 128 template< typename It > 129 It first(NodeIt v) const { 130 It e; 131 getFirst(e, v); 132 return e; 133 } 134 135 bool valid(EdgeIt e) const { return e.n!=INVALID; } 136 bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); } 137 bool valid(NodeIt n) const { return n.n<int(nodes.size()); } 138 139 template <typename It> It next(It it) const { 140 It tmp(it); return goNext(it); } 141 142 NodeIt& goNext(NodeIt& it) const { ++it.n; return it; } 143 OutEdgeIt& goNext(OutEdgeIt& it) const 144 { it.n=edges[it.n].next_out; return it; } 145 InEdgeIt& goNext(InEdgeIt& it) const 146 { it.n=edges[it.n].next_in; return it; } 147 EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; } 148 149 int id(NodeIt v) const { return v.n; } 150 int id(EdgeIt e) const { return e.n; } 151 152 NodeIt addNode() { 153 NodeIt n; n.n=nodes.size(); 154 nodes.push_back(NodeT()); //FIXME: Hmmm... 155 return n; 156 } 157 EdgeIt addEdge(NodeIt u, NodeIt v) { 158 EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... 159 edges[e.n].tail=u.n; edges[e.n].head=v.n; 160 edges[e.n].next_out=nodes[u.n].first_out; 161 edges[e.n].next_in=nodes[v.n].first_in; 162 nodes[u.n].first_out=nodes[v.n].first_in=e.n; 163 return e; 164 } 165 166 void clear() {nodes.clear();edges.clear();} 167 168 class NodeIt { 169 friend class SmartGraph; 170 template <typename T> friend class NodeMap; 171 172 friend class EdgeIt; 173 friend class OutEdgeIt; 174 friend class InEdgeIt; 175 friend class SymEdgeIt; 176 177 protected: 178 int n; 179 friend int SmartGraph::id(NodeIt v) const; 180 public: 181 NodeIt() {} 182 NodeIt(int nn) {n=nn;} 183 bool operator==(const NodeIt i) const {return n==i.n;} 184 bool operator!=(const NodeIt i) const {return n!=i.n;} 185 }; 186 187 class EachNodeIt : public NodeIt { 188 friend class SmartGraph; 189 public: 190 EachNodeIt(const SmartGraph& G) : NodeIt(0) { } 191 EachNodeIt() : NodeIt() { } 192 }; 193 194 class EdgeIt { 195 friend class SmartGraph; 196 template <typename T> friend class EdgeMap; 197 198 friend class NodeIt; 199 friend class EachNodeIt; 200 protected: 201 int n; 202 friend int SmartGraph::id(EdgeIt e) const; 203 public: 204 EdgeIt() { } 205 EdgeIt(int nn) {n=nn;} 206 bool operator==(const EdgeIt i) const {return n==i.n;} 207 bool operator!=(const EdgeIt i) const {return n!=i.n;} 208 }; 209 210 class EachEdgeIt : public EdgeIt { 211 friend class SmartGraph; 212 public: 213 EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { } 214 EachEdgeIt() : EdgeIt() { } 215 }; 216 217 class OutEdgeIt : public EdgeIt { 218 friend class SmartGraph; 219 public: 220 OutEdgeIt() : EdgeIt() { } 221 OutEdgeIt(const SmartGraph& G,const NodeIt v) 222 : EdgeIt(G.nodes[v.n].first_out) {} 223 }; 224 225 class InEdgeIt : public EdgeIt { 226 friend class SmartGraph; 227 public: 228 InEdgeIt() : EdgeIt() { } 229 InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){} 230 }; 228 void update() { container.resize(G.edgeNum()); } 229 void update(T a) { container.resize(G.edgeNum(), a); } 230 }; 231 232 233 234 231 235 }; 232 } //namespace marci236 } //namespace hugo 233 237 234 238 #endif //SMART_GRAPH_H
Note: See TracChangeset
for help on using the changeset viewer.