38 class NodeMap { |
38 class NodeMap { |
39 const ListGraph& G; |
39 const ListGraph& G; |
40 std::vector<ValueType> container; |
40 std::vector<ValueType> container; |
41 public: |
41 public: |
42 NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { } |
42 NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { } |
43 NodeMap(const ListGraph& _G, const ValueType a) : |
43 NodeMap(const ListGraph& _G, ValueType a) : |
44 G(_G), container(_G.node_id, a) { } |
44 G(_G), container(_G.node_id, a) { } |
45 void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; } |
45 void set(NodeIt nit, ValueType a) { container[G.id(nit)]=a; } |
46 ValueType get(const NodeIt nit) const { return container[G.id(nit)]; } |
46 ValueType get(NodeIt nit) const { return container[G.id(nit)]; } |
47 }; |
47 }; |
48 |
48 |
49 template <typename ValueType> |
49 template <typename ValueType> |
50 class EdgeMap { |
50 class EdgeMap { |
51 const ListGraph& G; |
51 const ListGraph& G; |
52 std::vector<ValueType> container; |
52 std::vector<ValueType> container; |
53 public: |
53 public: |
54 EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { } |
54 EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { } |
55 EdgeMap(const ListGraph& _G, const ValueType a) : |
55 EdgeMap(const ListGraph& _G, ValueType a) : |
56 G(_G), container(_G.edge_id, a) { } |
56 G(_G), container(_G.edge_id, a) { } |
57 void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; } |
57 void set(EdgeIt eit, ValueType a) { container[G.id(eit)]=a; } |
58 ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; } |
58 ValueType get(EdgeIt eit) const { return container[G.id(eit)]; } |
59 }; |
59 }; |
60 |
60 |
61 int node_id; |
61 int node_id; |
62 int edge_id; |
62 int edge_id; |
63 int _node_num; |
63 int _node_num; |
224 //EachEdgeIt firstEdge() const { return EachEdgeIt(*this); } |
224 //EachEdgeIt firstEdge() const { return EachEdgeIt(*this); } |
225 |
225 |
226 //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); } |
226 //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); } |
227 //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); } |
227 //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); } |
228 //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); } |
228 //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); } |
229 NodeIt tail(const EdgeIt e) const { return e.tailNode(); } |
229 NodeIt tail(EdgeIt e) const { return e.tailNode(); } |
230 NodeIt head(const EdgeIt e) const { return e.headNode(); } |
230 NodeIt head(EdgeIt e) const { return e.headNode(); } |
231 |
231 |
232 NodeIt aNode(const OutEdgeIt& e) const { return e.aNode(); } |
232 NodeIt aNode(const OutEdgeIt& e) const { return e.aNode(); } |
233 NodeIt aNode(const InEdgeIt& e) const { return e.aNode(); } |
233 NodeIt aNode(const InEdgeIt& e) const { return e.aNode(); } |
234 NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); } |
234 NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); } |
235 |
235 |
246 /* same methods in other style */ |
246 /* same methods in other style */ |
247 /* for experimental purpose */ |
247 /* for experimental purpose */ |
248 |
248 |
249 void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); } |
249 void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); } |
250 void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); } |
250 void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); } |
251 void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); } |
251 void getFirst(OutEdgeIt& e, NodeIt v) const { e=OutEdgeIt(v); } |
252 void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); } |
252 void getFirst(InEdgeIt& e, NodeIt v) const { e=InEdgeIt(v); } |
253 void getFirst(SymEdgeIt& e, const NodeIt& v) const { e=SymEdgeIt(v); } |
253 void getFirst(SymEdgeIt& e, NodeIt v) const { e=SymEdgeIt(v); } |
254 void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); } |
254 //void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); } |
255 void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); } |
255 //void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); } |
256 |
256 |
257 void getANode(NodeIt& n, const OutEdgeIt& e) const { n=e.aNode(); } |
257 //void getANode(NodeIt& n, const OutEdgeIt& e) const { n=e.aNode(); } |
258 void getANode(NodeIt& n, const InEdgeIt& e) const { n=e.aNode(); } |
258 //void getANode(NodeIt& n, const InEdgeIt& e) const { n=e.aNode(); } |
259 void getANode(NodeIt& n, const SymEdgeIt& e) const { n=e.aNode(); } |
259 //void getANode(NodeIt& n, const SymEdgeIt& e) const { n=e.aNode(); } |
260 void getBNode(NodeIt& n, const OutEdgeIt& e) const { n=e.bNode(); } |
260 //void getBNode(NodeIt& n, const OutEdgeIt& e) const { n=e.bNode(); } |
261 void getBNode(NodeIt& n, const InEdgeIt& e) const { n=e.bNode(); } |
261 //void getBNode(NodeIt& n, const InEdgeIt& e) const { n=e.bNode(); } |
262 void getBNode(NodeIt& n, const SymEdgeIt& e) const { n=e.bNode(); } |
262 //void getBNode(NodeIt& n, const SymEdgeIt& e) const { n=e.bNode(); } |
263 //void get_invalid(NodeIt& n) { n=NodeIt(); } |
263 //void get_invalid(NodeIt& n) { n=NodeIt(); } |
264 //void get_invalid(EdgeIt& e) { e=EdgeIt(); } |
264 //void get_invalid(EdgeIt& e) { e=EdgeIt(); } |
265 //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); } |
265 //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); } |
266 //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); } |
266 //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); } |
267 //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); } |
267 //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); } |
272 getFirst(e); |
272 getFirst(e); |
273 return e; |
273 return e; |
274 } |
274 } |
275 |
275 |
276 template< typename It > |
276 template< typename It > |
277 It first(const NodeIt v) const { |
277 It first(NodeIt v) const { |
278 It e; |
278 It e; |
279 getFirst(e, v); |
279 getFirst(e, v); |
280 return e; |
280 return e; |
281 } |
281 } |
282 |
282 |
283 /* for getting id's of graph objects */ |
283 /* for getting id's of graph objects */ |
284 /* these are important for the implementation of property vectors */ |
284 /* these are important for the implementation of property vectors */ |
285 |
285 |
286 int id(const NodeIt v) const { return v.node->id; } |
286 int id(NodeIt v) const { return v.node->id; } |
287 int id(const EdgeIt e) const { return e.edge->id; } |
287 int id(EdgeIt e) const { return e.edge->id; } |
288 |
288 |
289 /* adding nodes and edges */ |
289 /* adding nodes and edges */ |
290 |
290 |
291 NodeIt addNode() { return NodeIt(_add_node()); } |
291 NodeIt addNode() { return NodeIt(_add_node()); } |
292 EdgeIt addEdge(const NodeIt u, const NodeIt v) { |
292 EdgeIt addEdge(NodeIt u, NodeIt v) { |
293 return EdgeIt(_add_edge(u.node, v.node)); |
293 return EdgeIt(_add_edge(u.node, v.node)); |
294 } |
294 } |
295 |
295 |
296 void deleteNode(const NodeIt i) { |
296 void deleteNode(NodeIt i) { |
297 while (first<OutEdgeIt>(i).valid()) deleteEdge(first<OutEdgeIt>(i)); |
297 while (first<OutEdgeIt>(i).valid()) deleteEdge(first<OutEdgeIt>(i)); |
298 while (first<InEdgeIt>(i).valid()) deleteEdge(first<InEdgeIt>(i)); |
298 while (first<InEdgeIt>(i).valid()) deleteEdge(first<InEdgeIt>(i)); |
299 _delete_node(i.node); |
299 _delete_node(i.node); |
300 } |
300 } |
301 |
301 |
302 void deleteEdge(const EdgeIt e) { _delete_edge(e.edge); } |
302 void deleteEdge(EdgeIt e) { _delete_edge(e.edge); } |
303 |
303 |
304 void setTail(const EdgeIt e, const NodeIt tail) { |
304 void setTail(EdgeIt e, NodeIt tail) { |
305 _set_tail(e.edge, tail.node); |
305 _set_tail(e.edge, tail.node); |
306 } |
306 } |
307 |
307 |
308 void setHead(const EdgeIt e, const NodeIt head) { |
308 void setHead(EdgeIt e, NodeIt head) { |
309 _set_head(e.edge, head.node); |
309 _set_head(e.edge, head.node); |
310 } |
310 } |
311 |
311 |
312 /* stream operations, for testing purpose */ |
312 /* stream operations, for testing purpose */ |
313 |
313 |
326 friend class OutEdgeIt; |
326 friend class OutEdgeIt; |
327 friend class InEdgeIt; |
327 friend class InEdgeIt; |
328 friend class SymEdgeIt; |
328 friend class SymEdgeIt; |
329 protected: |
329 protected: |
330 node_item* node; |
330 node_item* node; |
331 friend int ListGraph::id(const NodeIt v) const; |
331 friend int ListGraph::id(NodeIt v) const; |
332 public: |
332 public: |
333 NodeIt() : node(0) { } |
333 NodeIt() : node(0) { } |
334 NodeIt(node_item* _node) : node(_node) { } |
334 NodeIt(node_item* _node) : node(_node) { } |
335 bool valid() const { return (node!=0); } |
335 bool valid() const { return (node!=0); } |
336 //void makeInvalid() { node=0; } |
336 //void makeInvalid() { node=0; } |
404 node_item* v; |
404 node_item* v; |
405 protected: |
405 protected: |
406 OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; } |
406 OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; } |
407 public: |
407 public: |
408 OutEdgeIt() : EdgeIt(), v(0) { } |
408 OutEdgeIt() : EdgeIt(), v(0) { } |
409 OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; } |
409 OutEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; } |
410 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } |
410 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } |
411 protected: |
411 protected: |
412 NodeIt aNode() const { return NodeIt(v); } |
412 NodeIt aNode() const { return NodeIt(v); } |
413 NodeIt bNode() const { |
413 NodeIt bNode() const { |
414 return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); } |
414 return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); } |
419 node_item* v; |
419 node_item* v; |
420 protected: |
420 protected: |
421 InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; } |
421 InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; } |
422 public: |
422 public: |
423 InEdgeIt() : EdgeIt(), v(0) { } |
423 InEdgeIt() : EdgeIt(), v(0) { } |
424 InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; } |
424 InEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; } |
425 InEdgeIt& operator++() { edge=edge->_next_in; return *this; } |
425 InEdgeIt& operator++() { edge=edge->_next_in; return *this; } |
426 protected: |
426 protected: |
427 NodeIt aNode() const { return NodeIt(v); } |
427 NodeIt aNode() const { return NodeIt(v); } |
428 NodeIt bNode() const { |
428 NodeIt bNode() const { |
429 return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); } |
429 return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); } |
439 edge=v->_first_out_edge; |
439 edge=v->_first_out_edge; |
440 if (!edge) { edge=v->_first_in_edge; out_or_in=0; } |
440 if (!edge) { edge=v->_first_in_edge; out_or_in=0; } |
441 } |
441 } |
442 public: |
442 public: |
443 SymEdgeIt() : EdgeIt(), v(0) { } |
443 SymEdgeIt() : EdgeIt(), v(0) { } |
444 SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { |
444 SymEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { |
445 out_or_in=1; |
445 out_or_in=1; |
446 edge=v->_first_out_edge; |
446 edge=v->_first_out_edge; |
447 if (!edge) { edge=v->_first_in_edge; out_or_in=0; } |
447 if (!edge) { edge=v->_first_in_edge; out_or_in=0; } |
448 } |
448 } |
449 SymEdgeIt& operator++() { |
449 SymEdgeIt& operator++() { |