33 class EdgeIt; |
35 class EdgeIt; |
34 class EachEdgeIt; |
36 class EachEdgeIt; |
35 class OutEdgeIt; |
37 class OutEdgeIt; |
36 class InEdgeIt; |
38 class InEdgeIt; |
37 |
39 |
38 // class NodeIt { int n; }; |
40 // class NodeIt { int n; }; |
39 // class EachNodeIt : public NodeIt { }; |
41 // class EachNodeIt : public NodeIt { }; |
40 // class EdgeIt { int n; }; |
42 // class EdgeIt { int n; }; |
41 // class EachEdgeIt : public EdgeIt {}; |
43 // class EachEdgeIt : public EdgeIt {}; |
42 // class OutEdgeIt : public EdgeIt {}; |
44 // class OutEdgeIt : public EdgeIt {}; |
43 // class InEdgeIt : public EdgeIt {}; |
45 // class InEdgeIt : public EdgeIt {}; |
44 // class SymEdgeIt; |
46 // class SymEdgeIt; |
45 |
47 |
46 template <typename T> class NodeMap; |
48 template <typename T> class NodeMap; |
47 template <typename T> class EdgeMap; |
49 template <typename T> class EdgeMap; |
48 |
50 |
49 private: |
51 public: |
50 |
52 |
51 template <typename T> friend class NodeMap; |
53 /* default constructor */ |
52 template <typename T> friend class EdgeMap; |
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 template <typename T> |
196 template <typename T> |
55 class NodeMap { |
197 class NodeMap { |
56 const SmartGraph& G; |
198 const SmartGraph& G; |
57 std::vector<T> container; |
199 std::vector<T> container; |
81 G(_G), container(G.edgeNum(), a) { } |
223 G(_G), container(G.edgeNum(), a) { } |
82 void set(EdgeIt e, T a) { container[e.n]=a; } |
224 void set(EdgeIt e, T a) { container[e.n]=a; } |
83 T get(EdgeIt e) const { return container[e.n]; } |
225 T get(EdgeIt e) const { return container[e.n]; } |
84 T& operator[](EdgeIt e) { return container[e.n]; } |
226 T& operator[](EdgeIt e) { return container[e.n]; } |
85 const T& operator[](EdgeIt e) const { return container[e.n]; } |
227 const T& operator[](EdgeIt e) const { return container[e.n]; } |
86 void resize() { container.resize(G.edgeNum()); } |
228 void update() { container.resize(G.edgeNum()); } |
87 void resize(T a) { container.resize(G.edgeNum(), a); } |
229 void update(T a) { container.resize(G.edgeNum(), a); } |
88 }; |
230 }; |
89 |
231 |
90 public: |
232 |
91 |
233 |
92 /* default constructor */ |
234 |
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 }; |
|
231 }; |
235 }; |
232 } //namespace marci |
236 } //namespace hugo |
233 |
237 |
234 #endif //SMART_GRAPH_H |
238 #endif //SMART_GRAPH_H |