1 #include <iostream> |
1 #include <iostream> |
2 #include <vector> |
2 #include <vector> |
3 #include <smart_graph.h> |
3 #include <lemon/smart_graph.h> |
|
4 #include <limits> |
4 |
5 |
5 using namespace lemon; |
6 using namespace lemon; |
6 |
7 |
7 ///\todo This is only a static map! |
8 ///\todo This is only a static map! |
8 /// |
9 ///\param BaseMap is an interger map. |
9 template<class GG> |
10 template<class BaseMap> |
10 class BoolIterEdgeMap |
11 class BoolIterMap |
11 { |
12 { |
12 public: |
13 public: |
13 typedef GG Graph; |
|
14 typedef typename GG::Edge Edge; |
|
15 |
14 |
16 typedef Edge Key; |
15 typedef typename BaseMap::Key Key; |
17 typedef bool Value; |
16 typedef bool Value; |
18 |
17 |
19 friend class RefType; |
18 friend class RefType; |
20 friend class FalseIterator; |
19 friend class FalseIt; |
21 friend class TrueIterator; |
20 friend class TrueIt; |
22 |
21 |
23 private: |
22 private: |
24 Graph &G; |
23 BaseMap &cref; |
25 typename Graph::EdgeMap<int> cref; |
24 std::vector<Key> vals; |
26 std::vector<Edge> vals; |
|
27 int sep; //map[e] is true <=> cref[e]>=sep |
25 int sep; //map[e] is true <=> cref[e]>=sep |
28 |
26 |
29 bool isTrue(Edge e) {return cref[e]>=sep;} |
27 bool isTrue(Key k) {return cref[k]>=sep;} |
30 void swap(Edge e, int s) |
28 void swap(Key k, int s) |
31 { |
29 { |
32 int ti=cref[e]; |
30 int ti=cref[k]; |
33 Edge te=vals[s]; |
31 Key tk=vals[s]; |
34 cref[e]=s; vals[s]=e; |
32 cref[k]=s; vals[s]=k; |
35 cref[te]=ti; vals[ti]=te; |
33 cref[tk]=ti; vals[ti]=tk; |
36 } |
34 } |
37 |
35 |
38 void setTrue(Edge e) { if(cref[e]<sep) { sep--; swap(e,sep); } } |
36 void setTrue(Key k) { if(cref[k]<sep) { sep--; swap(k,sep); } } |
39 void setFalse(Edge e) { if(cref[e]>=sep) { swap(e,sep); sep++; } } |
37 void setFalse(Key k) { if(cref[k]>=sep) { swap(k,sep); sep++; } } |
40 |
38 |
41 public: |
39 public: |
42 class FalseIterator |
40 ///\e |
|
41 void set(Key k,Value v) { if(v) setTrue(k); else setFalse(k);} |
|
42 |
|
43 ///\e |
|
44 class FalseIt |
43 { |
45 { |
44 BoolIterEdgeMap &M; |
46 const BoolIterMap &M; |
45 int i; |
47 int i; |
46 public: |
48 public: |
47 FalseIterator(BoolIterEdgeMap &_M) : M(_M), i(0) { } |
49 explicit FalseIt(const BoolIterMap &_M) : M(_M), i(0) { } |
48 FalseIterator &operator++() { ++i; return *this;} |
50 FalseIt(Invalid) |
49 operator Edge() { return i<M.sep ? M.vals[i] : INVALID; } |
51 : M(*((BoolIterMap*)(0))), i(std::numeric_limits<int>::max()) { } |
50 operator bool() { return i<M.sep; } |
52 FalseIt &operator++() { ++i; return *this;} |
|
53 operator Key() { return i<M.sep ? M.vals[i] : INVALID; } |
|
54 bool operator !=(Invalid) { return i<M.sep; } |
|
55 bool operator ==(Invalid) { return i>=M.sep; } |
51 }; |
56 }; |
52 class TrueIterator |
57 ///\e |
|
58 class TrueIt |
53 { |
59 { |
54 BoolIterEdgeMap &M; |
60 BoolIterMap &M; |
55 int i; |
61 int i; |
56 public: |
62 public: |
57 TrueIterator(BoolIterEdgeMap &_M) : M(_M), i(M.vals.size()-1) { } |
63 explicit TrueIt(BoolIterMap &_M) : M(_M), i(M.vals.size()-1) { } |
58 TrueIterator &operator++() { --i; return *this;} |
64 TrueIt(Invalid) |
59 operator Edge() { return i>=M.sep ? M.vals[i] : INVALID; } |
65 : M(*((BoolIterMap*)(0))), i(-1) { } |
60 operator bool() { return i>=M.sep; } |
66 TrueIt &operator++() { --i; return *this;} |
|
67 operator Key() { return i>=M.sep ? M.vals[i] : INVALID; } |
|
68 bool operator !=(Invalid) { return i>=M.sep; } |
|
69 bool operator ==(Invalid) { return i<M.sep; } |
61 }; |
70 }; |
62 |
71 |
63 class RefType |
72 ///\e |
|
73 class RefType |
64 { |
74 { |
65 BoolIterEdgeMap &M; |
75 BoolIterMap &M; |
66 Edge e; |
76 Key k; |
67 public: |
77 public: |
68 RefType(BoolIterEdgeMap &_M,Edge _e) : M(_M), e(_e) { } |
78 RefType(BoolIterMap &_M,Key _k) : M(_M), k(_k) { } |
69 |
79 |
70 operator Value() const |
80 operator Value() const |
71 { |
81 { |
72 return M.isTrue(e); |
82 return M.isTrue(k); |
73 |
|
74 } |
83 } |
75 Value operator = (Value v) const |
84 Value operator = (Value v) const { M.set(k,v); return v; } |
76 { |
|
77 if(v) M.setTrue(e); |
|
78 else M.setFalse(e); |
|
79 return v; |
|
80 } |
|
81 }; |
85 }; |
82 |
86 |
83 public: |
87 public: |
84 BoolIterEdgeMap(Graph &_G) : G(_G), cref(G) |
88 explicit BoolIterMap(BaseMap &_m) : cref(_m) |
85 { |
89 { |
86 sep=0; |
90 sep=0; |
87 for(typename Graph::EdgeIt e(G);G.valid(e);G.next(e)) { |
91 for(typename BaseMap::MapSet::iterator i=cref.mapSet().begin(); |
88 cref[e]=sep; |
92 i!=cref.mapSet().end(); |
89 vals.push_back(e); |
93 ++i) { |
|
94 i->second=sep; |
|
95 vals.push_back(i->first); |
90 sep++; |
96 sep++; |
91 } |
97 } |
92 } |
98 } |
93 RefType operator[] (Edge e) { return RefType(*this,e);} |
99 RefType operator[] (Key k) { return RefType(*this,k);} |
|
100 Value operator[] (Key k) const { return isTrue(k);} |
94 }; |
101 }; |
95 |
102 |
96 int main() |
103 int main() |
97 { |
104 { |
98 typedef SmartGraph Graph; |
105 typedef SmartGraph Graph; |
102 |
109 |
103 Graph G; |
110 Graph G; |
104 |
111 |
105 for(int i=0;i<3;i++) G.addNode(); |
112 for(int i=0;i<3;i++) G.addNode(); |
106 |
113 |
107 for(NodeIt n(G);G.valid(n);G.next(n)) |
114 for(NodeIt n(G);n!=INVALID;++n) |
108 for(NodeIt m(G);G.valid(m);G.next(m)) if(n!=m) |
115 for(NodeIt m(G);m!=INVALID;++m) if(n!=m) |
109 G.addEdge(n,m); |
116 G.addEdge(n,m); |
110 |
117 |
111 //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e)) |
118 //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e)) |
112 |
119 |
113 BoolIterEdgeMap<Graph> map(G); |
120 Graph::EdgeMap<int> tem(G); |
|
121 typedef BoolIterMap<Graph::EdgeMap<int> > BoolIterEdgeMap; |
|
122 BoolIterEdgeMap map(tem); |
114 |
123 |
115 bool b=true; |
124 bool b=true; |
116 |
125 |
117 for(EdgeIt e(G);G.valid(e);G.next(e)) {map[e]=b;b=!b;} |
126 for(EdgeIt e(G);e!=INVALID;++e) {map[e]=b;b=!b;} |
118 |
127 |
119 std::cout << true << '\n'; |
128 std::cout << true << '\n'; |
120 |
129 |
121 for(EdgeIt e(G);G.valid(e);G.next(e)) |
130 for(EdgeIt e(G);e!=INVALID;++e) |
122 std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) |
131 std::cout << G.id(G.source(e)) << "->" << G.id(G.target(e)) |
123 << ": " << map[e] << '\n'; |
132 << ": " << map[e] << '\n'; |
124 std::cout << "True Edges:\n"; |
133 std::cout << "True Edges:\n"; |
125 for(BoolIterEdgeMap<Graph>::TrueIterator i(map);i;++i) |
134 for(BoolIterEdgeMap::TrueIt i(map);i!=INVALID;++i) |
126 std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n'; |
135 std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n'; |
127 std::cout << "False Edges:\n"; |
136 std::cout << "False Edges:\n"; |
128 for(BoolIterEdgeMap<Graph>::FalseIterator i(map);i;++i) |
137 for(BoolIterEdgeMap::FalseIt i(map);i!=INVALID;++i) |
129 std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n'; |
138 std::cout << G.id(G.source(i)) << "->" << G.id(G.target(i)) << '\n'; |
130 } |
139 } |
131 |
140 |