COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/boolmap_iter.cc @ 493:bbd1db03f0fe

Last change on this file since 493:bbd1db03f0fe was 348:b63ea19e502e, checked in by Alpar Juttner, 20 years ago

A bool Edge Map with iterators that goes through the true or the false edges.

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