lemon-0.x: src/work/alpar/boolmap

     1 #include <iostream>

     2 #include <vector>

     3 #include <smart_graph.h>

     5 using namespace lemon;

     7 ///\todo This is only a static map!

     8 ///

     9 template<class GG>

    10 class BoolIterEdgeMap

    11 {

    12 public:

    13   typedef GG Graph;

    14   typedef typename GG::Edge Edge;

    16   typedef Edge KeyType;

    17   typedef bool ValueType;

    19   friend class RefType;

    20   friend class FalseIterator;

    21   friend class TrueIterator;

    23 private:

    24   Graph &G;

    25   typename Graph::EdgeMap<int> cref;

    26   std::vector<Edge> vals;

    27   int sep;           //map[e] is true <=> cref[e]>=sep

    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   }

    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++; } }

    41 public:

    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   };

    63   class RefType

    64   {

    65     BoolIterEdgeMap &M;

    66     Edge e;

    67   public:

    68     RefType(BoolIterEdgeMap &_M,Edge _e) : M(_M), e(_e) { }

    70     operator ValueType() const

    71     {

    72       return M.isTrue(e);

    74     }

    75     ValueType operator = (ValueType v) const

    76     {

    77       if(v) M.setTrue(e);

    78       else M.setFalse(e);

    79       return v;

    80     }

    81   };

    83 public:

    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 };

    96 int main()

    97 {

    98   typedef SmartGraph Graph;

    99   typedef Graph::NodeIt NodeIt;

   100   typedef Graph::OutEdgeIt OutEdgeIt;

   101   typedef Graph::EdgeIt EdgeIt;

   103   Graph G;

   105   for(int i=0;i<3;i++) G.addNode();

   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);

   111   //for(OutEdgeIt e(G,NodeIt(G));G.valid(e);G.next(e))

   113   BoolIterEdgeMap<Graph> map(G);

   115   bool b=true;

   117   for(EdgeIt e(G);G.valid(e);G.next(e)) {map[e]=b;b=!b;}

   119   std::cout << true << '\n';

   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 }

author	alpar
	Sat, 30 Oct 2004 18:33:14 +0000
changeset 950	d74557d1f100
parent 348	b63ea19e502e
child 986	e997802b855c
permissions	-rw-r--r--