1 #ifndef MARCI_LIST_GRAPH_HH |
1 #ifndef LIST_GRAPH_HH |
2 #define MARCI_LIST_GRAPH_HH |
2 #define LIST_GRAPH_HH |
3 |
3 |
4 #include <iostream> |
4 #include <iostream> |
5 |
5 |
6 namespace marci { |
6 namespace marci { |
7 |
|
8 template <typename It> |
|
9 int number_of(It _it) { |
|
10 int i=0; |
|
11 for( ; _it.valid(); ++_it) { ++i; } |
|
12 return i; |
|
13 } |
|
14 |
7 |
15 template <typename It> |
8 template <typename It> |
16 int count(It it) { |
9 int count(It it) { |
17 int i=0; |
10 int i=0; |
18 for( ; it.valid(); ++it) { ++i; } |
11 for( ; it.valid(); ++it) { ++i; } |
19 return i; |
12 return i; |
20 } |
13 } |
21 |
14 |
22 class ListGraph { |
15 class ListGraph { |
|
16 |
23 class node_item; |
17 class node_item; |
24 class edge_item; |
18 class edge_item; |
|
19 |
25 public: |
20 public: |
|
21 |
26 class NodeIt; |
22 class NodeIt; |
27 class EachNodeIt; |
23 class EachNodeIt; |
28 class EdgeIt; |
24 class EdgeIt; |
29 class EachEdgeIt; |
25 class EachEdgeIt; |
30 class OutEdgeIt; |
26 class OutEdgeIt; |
31 class InEdgeIt; |
27 class InEdgeIt; |
32 class SymEdgeIt; |
28 class SymEdgeIt; |
33 |
29 template <typename ValueType> class NodeMap; |
34 template <typename T> |
30 template <typename ValueType> class EdgeMap; |
|
31 |
|
32 private: |
|
33 |
|
34 template <typename ValueType> friend class NodeMap; |
|
35 template <typename ValueType> friend class EdgeMap; |
|
36 |
|
37 template <typename ValueType> |
35 class NodeMap { |
38 class NodeMap { |
36 //typedef typename Graph::NodeIt NodeIt; |
|
37 //typedef typename Graph::EachNodeIt EachNodeIt; |
|
38 const ListGraph& G; |
39 const ListGraph& G; |
39 std::vector<T> container; |
40 std::vector<ValueType> container; |
40 public: |
41 public: |
41 NodeMap(const ListGraph& _G) : G(_G) { |
42 NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { } |
42 int i=0; |
43 NodeMap(const ListGraph& _G, const ValueType a) : |
43 for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) ++i; |
44 G(_G), container(_G.node_id, a) { } |
44 container.resize(i); |
45 void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; } |
45 } |
46 ValueType get(const NodeIt nit) const { return container[G.id(nit)]; } |
46 NodeMap(const ListGraph& _G, const T a) : G(_G) { |
47 }; |
47 for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) { |
48 |
48 container.push_back(a); |
49 template <typename ValueType> |
49 } |
|
50 } |
|
51 void set(const NodeIt nit, const T a) { container[G.id(nit)]=a; } |
|
52 T get(const NodeIt nit) const { return container[G.id(nit)]; } |
|
53 }; |
|
54 |
|
55 template <typename T> |
|
56 class EdgeMap { |
50 class EdgeMap { |
57 //typedef typename Graph::EdgeIt EdgeIt; |
|
58 //typedef typename Graph::EachEdgeIt EachEdgeIt; |
|
59 const ListGraph& G; |
51 const ListGraph& G; |
60 std::vector<T> container; |
52 std::vector<ValueType> container; |
61 public: |
53 public: |
62 EdgeMap(const ListGraph& _G) : G(_G) { |
54 EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { } |
63 int i=0; |
55 EdgeMap(const ListGraph& _G, const ValueType a) : |
64 for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) ++i; |
56 G(_G), container(_G.edge_id, a) { } |
65 container.resize(i); |
57 void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; } |
66 } |
58 ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; } |
67 EdgeMap(const ListGraph& _G, const T a) : G(_G) { |
59 }; |
68 for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) { |
60 |
69 container.push_back(a); |
|
70 } |
|
71 } |
|
72 void set(const EdgeIt eit, const T a) { container[G.id(eit)]=a; } |
|
73 T get(const EdgeIt eit) const { return container[G.id(eit)]; } |
|
74 }; |
|
75 |
|
76 //typedef template<typename T> NodePropertyVector<ListGraph, T> NodeMap; |
|
77 //template <typename T> |
|
78 //typedef NodePropertyVector<ListGraph, T> NodeMap; |
|
79 //template <typename T> |
|
80 //typedef typename NodePropertyVector<ListGraph, T> NodeMap; |
|
81 //template <typename T> |
|
82 //typedef NodePropertyVector<typename ListGraph, T> NodeMap; |
|
83 //template <typename T> |
|
84 //typedef typename NodePropertyVector<typename ListGraph, T> NodeMap; |
|
85 //template <typename T> |
|
86 //typedef template NodePropertyVector<ListGraph, T> NodeMap; |
|
87 //template <typename T> |
|
88 //typedef template typename NodePropertyVector<ListGraph, T> NodeMap; |
|
89 //template <typename T> |
|
90 //typedef template NodePropertyVector<typename ListGraph, T> NodeMap; |
|
91 //template <typename T> |
|
92 //typedef template typename NodePropertyVector<typename ListGraph, T> NodeMap; |
|
93 //template <typename T> |
|
94 //typedef EdgePropertyVector<ListGraph, T> EdgeMap; |
|
95 |
|
96 private: |
|
97 int node_id; |
61 int node_id; |
98 int edge_id; |
62 int edge_id; |
99 int _node_num; |
63 int _node_num; |
100 int _edge_num; |
64 int _edge_num; |
101 |
65 |
111 friend class OutEdgeIt; |
75 friend class OutEdgeIt; |
112 friend class InEdgeIt; |
76 friend class InEdgeIt; |
113 friend class SymEdgeIt; |
77 friend class SymEdgeIt; |
114 friend std::ostream& operator<<(std::ostream& os, const NodeIt& i); |
78 friend std::ostream& operator<<(std::ostream& os, const NodeIt& i); |
115 friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i); |
79 friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i); |
116 ListGraph* G; |
80 //ListGraph* G; |
117 int id; |
81 int id; |
118 edge_item* _first_out_edge; |
82 edge_item* _first_out_edge; |
119 edge_item* _last_out_edge; |
83 edge_item* _last_out_edge; |
120 edge_item* _first_in_edge; |
84 edge_item* _first_in_edge; |
121 edge_item* _last_in_edge; |
85 edge_item* _last_in_edge; |
254 int nodeNum() const { return _node_num; } |
218 int nodeNum() const { return _node_num; } |
255 int edgeNum() const { return _edge_num; } |
219 int edgeNum() const { return _edge_num; } |
256 |
220 |
257 /* functions to construct iterators from the graph, or from each other */ |
221 /* functions to construct iterators from the graph, or from each other */ |
258 |
222 |
259 EachNodeIt firstNode() const { return EachNodeIt(_first_node); } |
223 //EachNodeIt firstNode() const { return EachNodeIt(*this); } |
260 EachEdgeIt firstEdge() const { |
224 //EachEdgeIt firstEdge() const { return EachEdgeIt(*this); } |
261 node_item* v=_first_node; |
|
262 edge_item* edge=v->_first_out_edge; |
|
263 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } |
|
264 return EachEdgeIt(v, edge); |
|
265 } |
|
266 |
225 |
267 //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); } |
226 //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); } |
268 InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); } |
227 //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); } |
269 SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); } |
228 //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); } |
270 NodeIt tail(const EdgeIt e) const { return e.tailNode(); } |
229 NodeIt tail(const EdgeIt e) const { return e.tailNode(); } |
271 NodeIt head(const EdgeIt e) const { return e.headNode(); } |
230 NodeIt head(const EdgeIt e) const { return e.headNode(); } |
272 |
231 |
273 NodeIt aNode(const OutEdgeIt& e) const { return e.aNode(); } |
232 NodeIt aNode(const OutEdgeIt& e) const { return e.aNode(); } |
274 NodeIt aNode(const InEdgeIt& e) const { return e.aNode(); } |
233 NodeIt aNode(const InEdgeIt& e) const { return e.aNode(); } |
285 //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); } |
244 //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); } |
286 |
245 |
287 /* same methods in other style */ |
246 /* same methods in other style */ |
288 /* for experimental purpose */ |
247 /* for experimental purpose */ |
289 |
248 |
290 void getFirst(EachNodeIt& v) const { v=EachNodeIt(_first_node); } |
249 void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); } |
291 void getFirst(EachEdgeIt& e) const { e=firstEdge(); } |
250 void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); } |
292 void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); } |
251 void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); } |
293 void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); } |
252 void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); } |
294 void getFirst(SymEdgeIt& e, const NodeIt& v) const { e=SymEdgeIt(v); } |
253 void getFirst(SymEdgeIt& e, const NodeIt& v) const { e=SymEdgeIt(v); } |
295 void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); } |
254 void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); } |
296 void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); } |
255 void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); } |
384 friend std::ostream& operator<<(std::ostream& os, const NodeIt& i); |
343 friend std::ostream& operator<<(std::ostream& os, const NodeIt& i); |
385 }; |
344 }; |
386 |
345 |
387 class EachNodeIt : public NodeIt { |
346 class EachNodeIt : public NodeIt { |
388 friend class ListGraph; |
347 friend class ListGraph; |
|
348 protected: |
|
349 EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { } |
389 public: |
350 public: |
390 EachNodeIt() : NodeIt() { } |
351 EachNodeIt() : NodeIt() { } |
391 EachNodeIt(node_item* v) : NodeIt(v) { } |
352 EachNodeIt(node_item* v) : NodeIt(v) { } |
392 EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { } |
|
393 EachNodeIt& operator++() { node=node->_next_node; return *this; } |
353 EachNodeIt& operator++() { node=node->_next_node; return *this; } |
394 }; |
354 }; |
395 |
355 |
396 class EdgeIt { |
356 class EdgeIt { |
397 friend class ListGraph; |
357 friend class ListGraph; |
420 friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i); |
380 friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i); |
421 }; |
381 }; |
422 |
382 |
423 class EachEdgeIt : public EdgeIt { |
383 class EachEdgeIt : public EdgeIt { |
424 friend class ListGraph; |
384 friend class ListGraph; |
425 node_item* v; |
385 protected: |
426 public: |
|
427 EachEdgeIt() : EdgeIt(), v(0) { } |
|
428 EachEdgeIt(node_item* _v, edge_item* _e) : EdgeIt(_e), v(_v) { } |
|
429 EachEdgeIt(const ListGraph& G) { |
386 EachEdgeIt(const ListGraph& G) { |
430 v=G._first_node; |
387 node_item* v=G._first_node; |
431 edge=v->_first_out_edge; |
388 if (v) edge=v->_first_out_edge; else edge=0; |
432 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } |
389 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } |
433 } |
390 } |
|
391 public: |
|
392 EachEdgeIt() : EdgeIt() { } |
|
393 EachEdgeIt(edge_item* _e) : EdgeIt(_e) { } |
434 EachEdgeIt& operator++() { |
394 EachEdgeIt& operator++() { |
|
395 node_item* v=edge->_tail; |
435 edge=edge->_next_out; |
396 edge=edge->_next_out; |
436 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } |
397 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } |
437 return *this; |
398 return *this; |
438 } |
399 } |
439 }; |
400 }; |
440 |
401 |
441 class OutEdgeIt : public EdgeIt { |
402 class OutEdgeIt : public EdgeIt { |
442 friend class ListGraph; |
403 friend class ListGraph; |
443 node_item* v; |
404 node_item* v; |
|
405 protected: |
|
406 OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; } |
444 public: |
407 public: |
445 OutEdgeIt() : EdgeIt(), v(0) { } |
408 OutEdgeIt() : EdgeIt(), v(0) { } |
446 protected: |
|
447 OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; } |
|
448 public: |
|
449 OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; } |
409 OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; } |
450 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } |
410 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } |
451 protected: |
411 protected: |
452 NodeIt aNode() const { return NodeIt(v); } |
412 NodeIt aNode() const { return NodeIt(v); } |
453 NodeIt bNode() const { |
413 NodeIt bNode() const { |
455 }; |
415 }; |
456 |
416 |
457 class InEdgeIt : public EdgeIt { |
417 class InEdgeIt : public EdgeIt { |
458 friend class ListGraph; |
418 friend class ListGraph; |
459 node_item* v; |
419 node_item* v; |
|
420 protected: |
|
421 InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; } |
460 public: |
422 public: |
461 InEdgeIt() : EdgeIt(), v(0) { } |
423 InEdgeIt() : EdgeIt(), v(0) { } |
462 protected: |
|
463 InEdgeIt(const NodeIt& _v) : v(_v.node) { |
|
464 edge=v->_first_in_edge; |
|
465 } |
|
466 public: |
|
467 InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; } |
424 InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; } |
468 InEdgeIt& operator++() { edge=edge->_next_in; return *this; } |
425 InEdgeIt& operator++() { edge=edge->_next_in; return *this; } |
469 protected: |
426 protected: |
470 NodeIt aNode() const { return NodeIt(v); } |
427 NodeIt aNode() const { return NodeIt(v); } |
471 NodeIt bNode() const { |
428 NodeIt bNode() const { |
474 |
431 |
475 class SymEdgeIt : public EdgeIt { |
432 class SymEdgeIt : public EdgeIt { |
476 friend class ListGraph; |
433 friend class ListGraph; |
477 bool out_or_in; //1 iff out, 0 iff in |
434 bool out_or_in; //1 iff out, 0 iff in |
478 node_item* v; |
435 node_item* v; |
479 public: |
|
480 SymEdgeIt() : EdgeIt(), v(0) { } |
|
481 protected: |
436 protected: |
482 SymEdgeIt(const NodeIt& _v) : v(_v.node) { |
437 SymEdgeIt(const NodeIt& _v) : v(_v.node) { |
483 out_or_in=1; |
438 out_or_in=1; |
484 edge=v->_first_out_edge; |
439 edge=v->_first_out_edge; |
485 if (!edge) { edge=v->_first_in_edge; out_or_in=0; } |
440 if (!edge) { edge=v->_first_in_edge; out_or_in=0; } |
486 } |
441 } |
487 public: |
442 public: |
|
443 SymEdgeIt() : EdgeIt(), v(0) { } |
488 SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { |
444 SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { |
489 out_or_in=1; |
445 out_or_in=1; |
490 edge=v->_first_out_edge; |
446 edge=v->_first_out_edge; |
491 if (!edge) { edge=v->_first_in_edge; out_or_in=0; } |
447 if (!edge) { edge=v->_first_in_edge; out_or_in=0; } |
492 } |
448 } |