src/work/marci/bipartite_graph_wrapper.h
author marci
Fri, 07 May 2004 06:33:02 +0000
changeset 565 18787f6db0db
parent 557 9c0ce0a1f000
child 641 bfd6c14e2975
permissions -rw-r--r--
ResGraphWrapper mods.
marci@174
     1
// -*- c++ -*-
marci@496
     2
#ifndef HUGO_BIPARTITE_GRAPH_WRAPPER_H
marci@496
     3
#define HUGO_BIPARTITE_GRAPH_WRAPPER_H
marci@76
     4
klao@491
     5
///\ingroup gwrappers
alpar@457
     6
///\file
alpar@457
     7
///\brief Several graph wrappers.
alpar@457
     8
///
alpar@457
     9
///This file contains several useful graph wrapper functions.
alpar@457
    10
///
alpar@457
    11
///\author Marton Makai
alpar@457
    12
marci@555
    13
#include <hugo/invalid.h>
marci@368
    14
#include <iter_map.h>
marci@557
    15
#include <hugo/graph_wrapper.h>
marci@174
    16
alpar@105
    17
namespace hugo {
marci@76
    18
marci@368
    19
  /// A wrapper for composing a bipartite graph.
marci@371
    20
  /// \c _graph have to be a reference to a graph of type \c Graph 
marci@371
    21
  /// and \c _s_false_t_true_map is an \c IterableBoolMap 
marci@368
    22
  /// reference containing the elements for the 
marci@371
    23
  /// color classes S and T. \c _graph is to be referred to an undirected 
marci@371
    24
  /// graph or a directed graph with edges oriented from S to T.
alpar@457
    25
  ///
alpar@457
    26
  ///\author Marton Makai
marci@368
    27
  template<typename Graph> 
marci@368
    28
  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
marci@497
    29
  protected:
marci@389
    30
    typedef IterableBoolMap< typename Graph::template NodeMap<int> > 
marci@389
    31
    SFalseTTrueMap;
marci@368
    32
    SFalseTTrueMap* s_false_t_true_map;
marci@393
    33
marci@501
    34
    BipartiteGraphWrapper() : GraphWrapper<Graph>()/*, 
marci@501
    35
						     S_CLASS(false), T_CLASS(true)*/ { }
marci@497
    36
    void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) { 
marci@499
    37
      s_false_t_true_map=&_s_false_t_true_map;
marci@497
    38
    }
marci@497
    39
marci@368
    40
  public:
marci@409
    41
    //marci
marci@409
    42
    //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
marci@502
    43
    static const bool S_CLASS;
marci@502
    44
    static const bool T_CLASS;
marci@379
    45
    
marci@501
    46
    //bool S_CLASS;
marci@501
    47
    //bool T_CLASS;
marci@409
    48
marci@368
    49
    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 
marci@500
    50
      : GraphWrapper<Graph>(_graph), 
marci@501
    51
	s_false_t_true_map(&_s_false_t_true_map)/*, 
marci@501
    52
						  S_CLASS(false), T_CLASS(true)*/ { }
marci@368
    53
    typedef typename GraphWrapper<Graph>::Node Node;
marci@368
    54
    //using GraphWrapper<Graph>::NodeIt;
marci@368
    55
    typedef typename GraphWrapper<Graph>::Edge Edge;
marci@368
    56
    //using GraphWrapper<Graph>::EdgeIt;
marci@393
    57
    class ClassNodeIt;
marci@393
    58
    friend class ClassNodeIt;
marci@393
    59
    class OutEdgeIt;
marci@393
    60
    friend class OutEdgeIt;
marci@393
    61
    class InEdgeIt;
marci@393
    62
    friend class InEdgeIt;
marci@379
    63
    class ClassNodeIt {
marci@393
    64
      friend class BipartiteGraphWrapper<Graph>;
marci@393
    65
    protected:
marci@368
    66
      Node n;
marci@368
    67
    public:
marci@379
    68
      ClassNodeIt() { }
marci@379
    69
      ClassNodeIt(const Invalid& i) : n(i) { }
marci@379
    70
      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { 
marci@379
    71
	_G.s_false_t_true_map->first(n, _class); 
marci@368
    72
      }
marci@381
    73
      //FIXME needed in new concept, important here
marci@381
    74
      ClassNodeIt(const Node& _n) : n(_n) { }
marci@368
    75
      operator Node() const { return n; }
marci@368
    76
    };
marci@379
    77
//     class SNodeIt {
marci@379
    78
//       Node n;
marci@379
    79
//     public:
marci@379
    80
//       SNodeIt() { }
marci@379
    81
//       SNodeIt(const Invalid& i) : n(i) { }
marci@379
    82
//       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
marci@379
    83
// 	_G.s_false_t_true_map->first(n, false); 
marci@379
    84
//       }
marci@379
    85
//       operator Node() const { return n; }
marci@379
    86
//     };
marci@379
    87
//     class TNodeIt {
marci@379
    88
//       Node n;
marci@379
    89
//     public:
marci@379
    90
//       TNodeIt() { }
marci@379
    91
//       TNodeIt(const Invalid& i) : n(i) { }
marci@379
    92
//       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
marci@379
    93
// 	_G.s_false_t_true_map->first(n, true); 
marci@379
    94
//       }
marci@379
    95
//       operator Node() const { return n; }
marci@379
    96
//     };
marci@368
    97
    class OutEdgeIt { 
marci@393
    98
      friend class BipartiteGraphWrapper<Graph>;
marci@393
    99
    protected:
marci@368
   100
      typename Graph::OutEdgeIt e;
marci@368
   101
    public:
marci@368
   102
      OutEdgeIt() { }
marci@368
   103
      OutEdgeIt(const Invalid& i) : e(i) { }
marci@368
   104
      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
marci@368
   105
	if (!(*(_G.s_false_t_true_map))[_n]) 
marci@379
   106
	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
marci@368
   107
	else 
marci@368
   108
	  e=INVALID;
marci@368
   109
      }
marci@368
   110
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@368
   111
    };
marci@368
   112
    class InEdgeIt { 
marci@393
   113
      friend class BipartiteGraphWrapper<Graph>;
marci@393
   114
    protected:
marci@368
   115
      typename Graph::InEdgeIt e;
marci@368
   116
    public:
marci@368
   117
      InEdgeIt() { }
marci@368
   118
      InEdgeIt(const Invalid& i) : e(i) { }
marci@368
   119
      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
marci@368
   120
	if ((*(_G.s_false_t_true_map))[_n]) 
marci@379
   121
	  e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
marci@368
   122
	else 
marci@368
   123
	  e=INVALID;
marci@368
   124
      }
marci@368
   125
      operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@368
   126
    };
marci@368
   127
marci@368
   128
    using GraphWrapper<Graph>::first;
marci@379
   129
    ClassNodeIt& first(ClassNodeIt& n, bool _class) const { 
marci@393
   130
      n=ClassNodeIt(*this, _class) ; return n; }
marci@379
   131
//    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
marci@379
   132
//    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
marci@379
   133
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@379
   134
      i=OutEdgeIt(*this, p); return i;
marci@379
   135
    }
marci@379
   136
    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
marci@379
   137
      i=InEdgeIt(*this, p); return i;
marci@379
   138
    }
marci@368
   139
marci@368
   140
    using GraphWrapper<Graph>::next;
marci@379
   141
    ClassNodeIt& next(ClassNodeIt& n) const { 
marci@393
   142
      this->s_false_t_true_map->next(n.n); return n; 
marci@368
   143
    }
marci@379
   144
//     SNodeIt& next(SNodeIt& n) const { 
marci@379
   145
//       this->s_false_t_true_map->next(n); return n; 
marci@379
   146
//     }
marci@379
   147
//     TNodeIt& next(TNodeIt& n) const { 
marci@379
   148
//       this->s_false_t_true_map->next(n); return n; 
marci@379
   149
//     }
marci@389
   150
    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
marci@389
   151
    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
marci@368
   152
marci@368
   153
    Node tail(const Edge& e) { 
marci@368
   154
      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
marci@368
   155
	return Node(this->graph->tail(e));
marci@368
   156
      else
marci@368
   157
	return Node(this->graph->head(e));	
marci@368
   158
    }
marci@368
   159
    Node head(const Edge& e) { 
marci@368
   160
      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
marci@368
   161
	return Node(this->graph->head(e));
marci@368
   162
      else
marci@368
   163
	return Node(this->graph->tail(e));	
marci@368
   164
    }
marci@368
   165
marci@368
   166
    Node aNode(const OutEdgeIt& e) const { 
marci@368
   167
      return Node(this->graph->aNode(e.e)); 
marci@368
   168
    }
marci@368
   169
    Node aNode(const InEdgeIt& e) const { 
marci@368
   170
      return Node(this->graph->aNode(e.e)); 
marci@368
   171
    }
marci@368
   172
    Node bNode(const OutEdgeIt& e) const { 
marci@368
   173
      return Node(this->graph->bNode(e.e)); 
marci@368
   174
    }
marci@368
   175
    Node bNode(const InEdgeIt& e) const { 
marci@368
   176
      return Node(this->graph->bNode(e.e)); 
marci@368
   177
    }
marci@379
   178
marci@379
   179
    bool inSClass(const Node& n) const {
marci@381
   180
      return !(*(this->s_false_t_true_map))[n];
marci@379
   181
    }
marci@379
   182
    bool inTClass(const Node& n) const {
marci@381
   183
      return (*(this->s_false_t_true_map))[n];
marci@379
   184
    }
marci@368
   185
  };
marci@368
   186
marci@502
   187
marci@502
   188
  template<typename G>
marci@502
   189
  const bool BipartiteGraphWrapper<G>::S_CLASS=false;
marci@502
   190
  template<typename G>
marci@502
   191
  const bool BipartiteGraphWrapper<G>::T_CLASS=true;
marci@502
   192
marci@502
   193
marci@502
   194
marci@502
   195
marci@502
   196
marci@502
   197
marci@502
   198
marci@502
   199
marci@502
   200
marci@502
   201
marci@502
   202
marci@502
   203
marci@497
   204
  ///\bug Do not use this while the bipartitemap augmentation 
marci@497
   205
  /// does not work well.
marci@497
   206
  template<typename Graph>
marci@497
   207
  class BipartiteGraph : public BipartiteGraphWrapper<Graph> {
marci@497
   208
    typedef IterableBoolMap< typename Graph::template NodeMap<int> > 
marci@497
   209
    SFalseTTrueMap;
marci@497
   210
    typedef BipartiteGraphWrapper<Graph> Parent;
marci@497
   211
  protected:
marci@497
   212
    Graph gr;
marci@497
   213
    typename Graph::template NodeMap<int> bipartite_map;
marci@497
   214
    SFalseTTrueMap s_false_t_true_map;
marci@497
   215
  public:
marci@497
   216
    typedef typename Parent::Node Node;
marci@497
   217
    typedef typename Parent::Edge Edge;
marci@499
   218
    BipartiteGraph() : BipartiteGraphWrapper<Graph>(), 
marci@500
   219
		       gr(), bipartite_map(gr, -1), 
marci@497
   220
		       s_false_t_true_map(bipartite_map) { 
marci@497
   221
      Parent::setGraph(gr); 
marci@499
   222
      Parent::setSFalseTTrueMap(s_false_t_true_map);
marci@497
   223
    }
marci@497
   224
marci@497
   225
    /// the \c bool parameter which can be \c S_Class or \c T_Class shows 
marci@497
   226
    /// the color class where the new node is to be inserted.
marci@498
   227
    Node addNode(bool b) {
marci@498
   228
      Node n=Parent::graph->addNode();
marci@498
   229
      bipartite_map.update();
marci@501
   230
      //bipartite_map.set(n, -1);
marci@498
   231
      s_false_t_true_map.insert(n, b);
marci@498
   232
      return n;
marci@498
   233
    }
marci@497
   234
marci@497
   235
    /// A new edge is inserted.
marci@497
   236
    ///\pre \c tail have to be in \c S_Class and \c head in \c T_Class.
marci@498
   237
    Edge addEdge(const Node& tail, const Node& head) {
marci@498
   238
      return Parent::graph->addEdge(tail, head);
marci@498
   239
    }
marci@497
   240
marci@498
   241
    void erase(const Node& n) {
marci@498
   242
      s_false_t_true_map.remove(n);
marci@498
   243
      Parent::graph->erase(n);
marci@498
   244
    }
marci@498
   245
    void erase(const Edge& e) {
marci@498
   246
      Parent::graph->erase(e);
marci@498
   247
    }
marci@497
   248
    
marci@497
   249
    void clear() {
marci@558
   250
      FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e);
marci@558
   251
      FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n);
marci@497
   252
    }
marci@497
   253
  };
marci@497
   254
marci@497
   255
marci@435
   256
  template<typename Graph>
marci@435
   257
  class stGraphWrapper;
marci@435
   258
marci@435
   259
//   template<typename Graph> 
marci@435
   260
//   std::ostream& 
marci@435
   261
//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) { 
marci@435
   262
//     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 
marci@435
   263
//     return os; 
marci@435
   264
//   }
marci@435
   265
//   template<typename Graph> 
marci@435
   266
//   std::ostream& 
marci@435
   267
//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) { 
marci@435
   268
//     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 
marci@435
   269
//       " node: " << i.n << ")"; 
marci@435
   270
//     return os; 
marci@435
   271
//   }
marci@341
   272
marci@379
   273
  /// experimentral, do not try it.
marci@379
   274
  /// It eats a bipartite graph, oriented from S to T.
marci@379
   275
  /// Such one can be made e.g. by the above wrapper.
alpar@457
   276
  ///
alpar@457
   277
  ///\author Marton Makai
marci@379
   278
  template<typename Graph>
marci@379
   279
  class stGraphWrapper : public GraphWrapper<Graph> {
marci@379
   280
  public:
marci@379
   281
    class Node; 
marci@381
   282
    friend class Node;
marci@379
   283
//GN, int
marci@379
   284
//0 normalis, 1 s, 2, true, ez az iteralasi sorrend, 
marci@379
   285
//es a vege a false azaz (invalid, 3)    
marci@379
   286
    class NodeIt;
marci@381
   287
    friend class NodeIt;
marci@379
   288
//GNI, int
marci@379
   289
    class Edge;
marci@381
   290
    friend class Edge;
marci@379
   291
//GE, int, GN
marci@379
   292
//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
marci@379
   293
//invalid: (invalid, 3, invalid)
marci@379
   294
    class OutEdgeIt;
marci@381
   295
    friend class OutEdgeIt;
marci@379
   296
//GO, int, GNI
marci@379
   297
//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
marci@379
   298
//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
marci@379
   299
//t-bol (invalid, 3, invalid)
marci@379
   300
    class InEdgeIt;
marci@381
   301
    friend class InEdgeIt;
marci@379
   302
//GI, int, GNI
marci@379
   303
//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
marci@379
   304
//s-be (invalid, 3, invalid)
marci@379
   305
//t-be (invalid, 2, first), ... (invalid, 3, invalid)
marci@379
   306
    class EdgeIt;
marci@381
   307
    friend class EdgeIt;
marci@379
   308
//(first, 0, invalid) ...
marci@379
   309
//(invalid, 1, vmi)
marci@379
   310
//(invalid, 2, vmi)
marci@379
   311
//invalid, 3, invalid)
marci@379
   312
    template <typename T> class NodeMap;
marci@510
   313
    template <typename T> class EdgeMap;
marci@341
   314
marci@379
   315
//    template <typename T> friend class NodeMap;
marci@379
   316
//    template <typename T> friend class EdgeMap;
marci@341
   317
marci@502
   318
    ///\todo FIXME ezt majd static-ra kell javitani
marci@379
   319
    const Node S_NODE;
marci@379
   320
    const Node T_NODE;
marci@341
   321
marci@379
   322
    static const bool S_CLASS=false;
marci@379
   323
    static const bool T_CLASS=true;
marci@341
   324
marci@379
   325
    stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) , 
marci@379
   326
				    S_NODE(INVALID, 1), 
marci@379
   327
				    T_NODE(INVALID, 2) { }
marci@341
   328
marci@435
   329
    
marci@435
   330
//    std::ostream& 
marci@435
   331
//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
marci@435
   332
//    friend std::ostream& 
marci@435
   333
//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
marci@435
   334
//    friend std::ostream& 
marci@435
   335
//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);
marci@435
   336
marci@379
   337
    class Node : public Graph::Node {
marci@379
   338
    protected:
marci@379
   339
      friend class GraphWrapper<Graph>;
marci@379
   340
      friend class stGraphWrapper<Graph>;
marci@389
   341
      template <typename T> friend class NodeMap;
marci@380
   342
      friend class Edge;
marci@380
   343
      friend class OutEdgeIt;
marci@380
   344
      friend class InEdgeIt;
marci@380
   345
      friend class EdgeIt;
marci@379
   346
      int spec; 
marci@379
   347
    public:
marci@379
   348
      Node() { }
marci@379
   349
      Node(const typename Graph::Node& _n, int _spec=0) : 
marci@379
   350
	Graph::Node(_n), spec(_spec) { }
marci@379
   351
      Node(const Invalid& i) : Graph::Node(i), spec(3) { }
marci@379
   352
      friend bool operator==(const Node& u, const Node& v) { 
marci@379
   353
	return (u.spec==v.spec && 
marci@379
   354
		static_cast<typename Graph::Node>(u)==
marci@379
   355
		static_cast<typename Graph::Node>(v));
marci@379
   356
      } 
marci@379
   357
      friend bool operator!=(const Node& u, const Node& v) { 
marci@379
   358
	return (v.spec!=u.spec || 
marci@379
   359
		static_cast<typename Graph::Node>(u)!=
marci@379
   360
		static_cast<typename Graph::Node>(v));
marci@409
   361
      }
marci@435
   362
//      template<typename G> 
marci@435
   363
//      friend std::ostream& 
marci@435
   364
//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i); 
marci@435
   365
      friend std::ostream& operator<< (std::ostream& os, const Node& i);
marci@379
   366
      int getSpec() const { return spec; }
marci@379
   367
    };
marci@409
   368
marci@379
   369
    class NodeIt { 
marci@379
   370
      friend class GraphWrapper<Graph>;
marci@379
   371
      friend class stGraphWrapper<Graph>;
marci@379
   372
      typename Graph::NodeIt n;
marci@379
   373
      int spec; 
marci@379
   374
     public:
marci@379
   375
      NodeIt() { }
marci@379
   376
      NodeIt(const typename Graph::NodeIt& _n, int _spec) : 
marci@379
   377
	n(_n), spec(_spec) { }
marci@379
   378
      NodeIt(const Invalid& i) : n(i), spec(3) { }
marci@381
   379
      NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 
marci@409
   380
	if (!_G.graph->valid(n)) spec=1;
marci@379
   381
      }
marci@379
   382
      operator Node() const { return Node(n, spec); }
marci@379
   383
    };
marci@409
   384
marci@379
   385
    class Edge : public Graph::Edge {
marci@379
   386
      friend class GraphWrapper<Graph>;
marci@379
   387
      friend class stGraphWrapper<Graph>;
marci@510
   388
      template <typename T> friend class EdgeMap;
marci@379
   389
      int spec;
marci@379
   390
      typename Graph::Node n;
marci@379
   391
    public:
marci@379
   392
      Edge() { }
marci@379
   393
      Edge(const typename Graph::Edge& _e, int _spec, 
marci@379
   394
	   const typename Graph::Node& _n) : 
marci@379
   395
	Graph::Edge(_e), spec(_spec), n(_n) { 
marci@379
   396
      }
marci@379
   397
      Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
marci@379
   398
      friend bool operator==(const Edge& u, const Edge& v) { 
marci@379
   399
	return (u.spec==v.spec && 
marci@379
   400
		static_cast<typename Graph::Edge>(u)==
marci@379
   401
		static_cast<typename Graph::Edge>(v) && 
marci@379
   402
		u.n==v.n);
marci@379
   403
      } 
marci@379
   404
      friend bool operator!=(const Edge& u, const Edge& v) { 
marci@379
   405
	return (v.spec!=u.spec || 
marci@379
   406
		static_cast<typename Graph::Edge>(u)!=
marci@379
   407
		static_cast<typename Graph::Edge>(v) || 
marci@379
   408
		u.n!=v.n);
marci@379
   409
      } 
marci@435
   410
//      template<typename G> 
marci@435
   411
//      friend std::ostream& 
marci@435
   412
//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i); 
marci@435
   413
      friend std::ostream& operator<< (std::ostream& os, const Edge& i);
marci@379
   414
      int getSpec() const { return spec; }
marci@510
   415
      typename Graph::Node getNode() const { return n; }
marci@379
   416
    };
marci@409
   417
marci@379
   418
    class OutEdgeIt { 
marci@379
   419
      friend class GraphWrapper<Graph>;
marci@379
   420
      friend class stGraphWrapper<Graph>;
marci@379
   421
      typename Graph::OutEdgeIt e;
marci@379
   422
      int spec;
marci@379
   423
      typename Graph::ClassNodeIt n;
marci@379
   424
    public:
marci@379
   425
      OutEdgeIt() { }
marci@379
   426
      OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, 
marci@379
   427
		const typename Graph::ClassNodeIt& _n) : 
marci@379
   428
	e(_e), spec(_spec), n(_n) { 
marci@379
   429
      }
marci@379
   430
      OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
marci@381
   431
      OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
marci@379
   432
	switch (_n.spec) {
marci@379
   433
	  case 0 : 
marci@381
   434
	    if (_G.graph->inSClass(_n)) { //S, van normalis kiel 
marci@379
   435
	      e=typename Graph::OutEdgeIt(*(_G.graph), 
marci@379
   436
					  typename Graph::Node(_n)); 
marci@379
   437
	      spec=0;
marci@379
   438
	      n=INVALID;
marci@379
   439
	      if (!_G.graph->valid(e)) spec=3;
marci@379
   440
	    } else { //T, specko kiel van
marci@379
   441
	      e=INVALID;
marci@379
   442
	      spec=2;
marci@379
   443
	      n=_n;
marci@379
   444
	    }
marci@379
   445
	    break;
marci@379
   446
	  case 1:
marci@379
   447
	    e=INVALID;
marci@379
   448
	    spec=1;
marci@379
   449
	    _G.graph->first(n, S_CLASS); //s->vmi;
marci@379
   450
	    if (!_G.graph->valid(n)) spec=3; //Ha S ures
marci@379
   451
	    break;
marci@379
   452
	  case 2:
marci@379
   453
	    e=INVALID;
marci@379
   454
	    spec=3;
marci@379
   455
	    n=INVALID;
marci@379
   456
	    break;
marci@379
   457
	}
marci@379
   458
      }
marci@379
   459
      operator Edge() const { return Edge(e, spec, n); }
marci@379
   460
    };
marci@409
   461
marci@379
   462
    class InEdgeIt { 
marci@379
   463
      friend class GraphWrapper<Graph>;
marci@379
   464
      friend class stGraphWrapper<Graph>;
marci@379
   465
      typename Graph::InEdgeIt e;
marci@379
   466
      int spec;
marci@379
   467
      typename Graph::ClassNodeIt n;
marci@379
   468
    public:
marci@379
   469
      InEdgeIt() { }
marci@379
   470
      InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, 
marci@379
   471
	       const typename Graph::ClassNodeIt& _n) : 
marci@379
   472
	e(_e), spec(_spec), n(_n) { 
marci@379
   473
      }
marci@379
   474
      InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
marci@381
   475
      InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
marci@379
   476
	switch (_n.spec) {
marci@379
   477
	  case 0 : 
marci@381
   478
	    if (_G.graph->inTClass(_n)) { //T, van normalis beel 
marci@379
   479
	      e=typename Graph::InEdgeIt(*(_G.graph), 
marci@379
   480
					 typename Graph::Node(_n)); 
marci@379
   481
	      spec=0;
marci@379
   482
	      n=INVALID;
marci@379
   483
	      if (!_G.graph->valid(e)) spec=3;
marci@379
   484
	    } else { //S, specko beel van
marci@379
   485
	      e=INVALID;
marci@379
   486
	      spec=1;
marci@379
   487
	      n=_n;
marci@379
   488
	    }
marci@379
   489
	    break;
marci@379
   490
	  case 1:
marci@379
   491
	    e=INVALID;
marci@379
   492
	    spec=3;
marci@379
   493
	    n=INVALID;
marci@409
   494
	    break;
marci@379
   495
	  case 2:
marci@379
   496
	    e=INVALID;
marci@409
   497
	    spec=2;
marci@379
   498
	    _G.graph->first(n, T_CLASS); //vmi->t;
marci@379
   499
	    if (!_G.graph->valid(n)) spec=3; //Ha T ures
marci@379
   500
	    break;
marci@379
   501
	}
marci@379
   502
      }
marci@379
   503
      operator Edge() const { return Edge(e, spec, n); }
marci@379
   504
    };
marci@409
   505
marci@379
   506
    class EdgeIt { 
marci@379
   507
      friend class GraphWrapper<Graph>;
marci@379
   508
      friend class stGraphWrapper<Graph>;
marci@379
   509
      typename Graph::EdgeIt e;
marci@379
   510
      int spec;
marci@379
   511
      typename Graph::ClassNodeIt n;
marci@379
   512
    public:
marci@379
   513
      EdgeIt() { }
marci@379
   514
      EdgeIt(const typename Graph::EdgeIt& _e, int _spec, 
marci@379
   515
	     const typename Graph::ClassNodeIt& _n) : 
marci@379
   516
	e(_e), spec(_spec), n(_n) { }
marci@379
   517
      EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
marci@381
   518
      EdgeIt(const stGraphWrapper<Graph>& _G) : 
marci@379
   519
	e(*(_G.graph)), spec(0), n(INVALID) { 
marci@379
   520
	if (!_G.graph->valid(e)) {
marci@379
   521
	  spec=1;
marci@379
   522
	  _G.graph->first(n, S_CLASS);
marci@379
   523
	  if (!_G.graph->valid(n)) { //Ha S ures
marci@379
   524
	    spec=2;
marci@379
   525
	    _G.graph->first(n, T_CLASS);
marci@379
   526
	    if (!_G.graph->valid(n)) { //Ha T ures
marci@379
   527
	      spec=3;
marci@379
   528
	    }
marci@379
   529
	  }
marci@379
   530
	}
marci@379
   531
      }
marci@379
   532
      operator Edge() const { return Edge(e, spec, n); }
marci@379
   533
    };
marci@341
   534
   
marci@379
   535
    NodeIt& first(NodeIt& i) const { 
marci@379
   536
      i=NodeIt(*this); return i;
marci@379
   537
    }
marci@379
   538
    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@379
   539
      i=OutEdgeIt(*this, p); return i;
marci@379
   540
    }
marci@379
   541
    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
marci@379
   542
      i=InEdgeIt(*this, p); return i;
marci@379
   543
    }
marci@379
   544
    EdgeIt& first(EdgeIt& i) const { 
marci@379
   545
      i=EdgeIt(*this); return i;
marci@379
   546
    }
marci@341
   547
marci@379
   548
    NodeIt& next(NodeIt& i) const { 
marci@379
   549
      switch (i.spec) {
marci@379
   550
	case 0:
marci@389
   551
	  this->graph->next(i.n);
marci@389
   552
	  if (!this->graph->valid(i.n)) {
marci@379
   553
	    i.spec=1;
marci@379
   554
	  }
marci@379
   555
	  break;
marci@379
   556
	case 1:
marci@379
   557
	  i.spec=2;
marci@379
   558
	  break;
marci@379
   559
	case 2:
marci@379
   560
	  i.spec=3;
marci@379
   561
	  break;
marci@379
   562
      }
marci@379
   563
      return i; 
marci@379
   564
    }
marci@379
   565
    OutEdgeIt& next(OutEdgeIt& i) const { 
marci@393
   566
      typename Graph::Node v;
marci@379
   567
      switch (i.spec) {
marci@379
   568
	case 0: //normal edge
marci@409
   569
	  v=this->graph->aNode(i.e);
marci@389
   570
	  this->graph->next(i.e);
marci@389
   571
	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
marci@389
   572
	    if (this->graph->inSClass(v)) { //S, nincs kiel
marci@379
   573
	      i.spec=3;
marci@379
   574
	      i.n=INVALID;
marci@379
   575
	    } else { //T, van kiel
marci@379
   576
	      i.spec=2; 
marci@379
   577
	      i.n=v;
marci@379
   578
	    }
marci@379
   579
	  }
marci@379
   580
	  break;
marci@379
   581
	case 1: //s->vmi
marci@389
   582
	  this->graph->next(i.n);
marci@389
   583
	  if (!this->graph->valid(i.n)) i.spec=3;
marci@379
   584
	  break;
marci@379
   585
	case 2: //vmi->t
marci@379
   586
	  i.spec=3;
marci@379
   587
	  i.n=INVALID;
marci@379
   588
	  break;
marci@379
   589
      }
marci@379
   590
      return i; 
marci@379
   591
    }
marci@379
   592
    InEdgeIt& next(InEdgeIt& i) const { 
marci@393
   593
      typename Graph::Node v;
marci@379
   594
      switch (i.spec) {
marci@379
   595
	case 0: //normal edge
marci@393
   596
	  v=this->graph->aNode(i.e);
marci@389
   597
	  this->graph->next(i.e);
marci@389
   598
	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
marci@389
   599
	    if (this->graph->inTClass(v)) { //S, nincs beel
marci@379
   600
	      i.spec=3;
marci@379
   601
	      i.n=INVALID;
marci@379
   602
	    } else { //S, van beel
marci@379
   603
	      i.spec=1; 
marci@379
   604
	      i.n=v;
marci@379
   605
	    }
marci@379
   606
	  }
marci@379
   607
	  break;
marci@379
   608
	case 1: //s->vmi
marci@379
   609
	  i.spec=3;
marci@379
   610
	  i.n=INVALID;
marci@379
   611
	  break;
marci@379
   612
	case 2: //vmi->t
marci@389
   613
	  this->graph->next(i.n);
marci@389
   614
	  if (!this->graph->valid(i.n)) i.spec=3;
marci@379
   615
	  break;
marci@379
   616
      }
marci@379
   617
      return i; 
marci@379
   618
    }
marci@341
   619
marci@379
   620
    EdgeIt& next(EdgeIt& i) const { 
marci@379
   621
      switch (i.spec) {
marci@379
   622
	case 0:
marci@389
   623
	  this->graph->next(i.e);
marci@389
   624
	  if (!this->graph->valid(i.e)) { 
marci@379
   625
	    i.spec=1;
marci@389
   626
	    this->graph->first(i.n, S_CLASS);
marci@389
   627
	    if (!this->graph->valid(i.n)) {
marci@379
   628
	      i.spec=2;
marci@389
   629
	      this->graph->first(i.n, T_CLASS);
marci@389
   630
	      if (!this->graph->valid(i.n)) i.spec=3;
marci@379
   631
	    }
marci@379
   632
	  }
marci@379
   633
	  break;
marci@379
   634
	case 1:
marci@389
   635
	  this->graph->next(i.n);
marci@389
   636
	  if (!this->graph->valid(i.n)) {
marci@379
   637
	    i.spec=2;
marci@389
   638
	    this->graph->first(i.n, T_CLASS);
marci@389
   639
	    if (!this->graph->valid(i.n)) i.spec=3;
marci@379
   640
	  }
marci@379
   641
	  break;
marci@379
   642
	case 2:
marci@389
   643
	  this->graph->next(i.n);
marci@389
   644
	  if (!this->graph->valid(i.n)) i.spec=3;
marci@379
   645
	  break;
marci@379
   646
      }
marci@379
   647
      return i; 
marci@379
   648
    }    
marci@341
   649
marci@379
   650
    Node tail(const Edge& e) const { 
marci@379
   651
      switch (e.spec) {
marci@393
   652
      case 0: 
marci@393
   653
	return Node(this->graph->tail(e));
marci@393
   654
	break;
marci@393
   655
      case 1:
marci@393
   656
	return S_NODE;
marci@393
   657
	break;
marci@393
   658
      case 2:
marci@393
   659
      default:
marci@393
   660
	return Node(e.n);
marci@393
   661
	break;
marci@379
   662
      }
marci@379
   663
    }
marci@379
   664
    Node head(const Edge& e) const { 
marci@379
   665
      switch (e.spec) {
marci@393
   666
      case 0: 
marci@393
   667
	return Node(this->graph->head(e));
marci@393
   668
	break;
marci@393
   669
      case 1:
marci@393
   670
	return Node(e.n);
marci@393
   671
	break;
marci@393
   672
      case 2:
marci@393
   673
      default:
marci@393
   674
	return T_NODE;
marci@393
   675
	break;
marci@379
   676
      }
marci@379
   677
    }
marci@341
   678
marci@379
   679
    bool valid(const Node& n) const { return (n.spec<3); }
marci@379
   680
    bool valid(const Edge& e) const { return (e.spec<3); }
marci@379
   681
marci@409
   682
    int nodeNum() const { return this->graph->nodeNum()+2; }
marci@409
   683
    int edgeNum() const { 
marci@409
   684
      return this->graph->edgeNum()+this->graph->nodeNum(); 
marci@409
   685
    }
marci@341
   686
  
marci@379
   687
    Node aNode(const OutEdgeIt& e) const { return tail(e); }
marci@379
   688
    Node aNode(const InEdgeIt& e) const { return head(e); }
marci@379
   689
    Node bNode(const OutEdgeIt& e) const { return head(e); }
marci@379
   690
    Node bNode(const InEdgeIt& e) const { return tail(e); }
marci@409
   691
marci@409
   692
    void addNode() const { }
marci@409
   693
    void addEdge() const { }
marci@409
   694
    
marci@389
   695
//    Node addNode() const { return Node(this->graph->addNode()); }
marci@379
   696
//    Edge addEdge(const Node& tail, const Node& head) const { 
marci@389
   697
//      return Edge(this->graph->addEdge(tail, head)); }
marci@341
   698
marci@389
   699
//    void erase(const Node& i) const { this->graph->erase(i); }
marci@389
   700
//    void erase(const Edge& i) const { this->graph->erase(i); }
marci@341
   701
  
marci@389
   702
//    void clear() const { this->graph->clear(); }
marci@341
   703
    
marci@389
   704
    template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { 
marci@389
   705
      typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
marci@510
   706
    protected:
marci@379
   707
      T s_value, t_value;
marci@379
   708
    public:
marci@409
   709
      NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G), 
marci@409
   710
						  s_value(), 
marci@409
   711
						  t_value() { }
marci@389
   712
      NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
marci@389
   713
						      s_value(a), 
marci@389
   714
						      t_value(a) { }
marci@379
   715
      T operator[](const Node& n) const { 
marci@379
   716
	switch (n.spec) {
marci@393
   717
	case 0: 
marci@393
   718
	  return Parent::operator[](n);
marci@393
   719
	case 1:
marci@393
   720
	  return s_value;
marci@393
   721
	case 2: 
marci@393
   722
	default:
marci@393
   723
	  return t_value;
marci@379
   724
	}
marci@379
   725
      }
marci@379
   726
      void set(const Node& n, T t) { 
marci@379
   727
	switch (n.spec) {
marci@393
   728
	case 0: 
marci@393
   729
	  GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
marci@393
   730
	  break;
marci@393
   731
	case 1:
marci@393
   732
	  s_value=t;
marci@393
   733
	  break;
marci@393
   734
	case 2:
marci@393
   735
	default:
marci@393
   736
	  t_value=t;
marci@393
   737
	  break;
marci@379
   738
	}
marci@379
   739
      }
marci@379
   740
    };
marci@341
   741
marci@510
   742
    /// This class is to wrap a node-map of \c Graph and two variables 
marci@510
   743
    /// storing values for \c S_NODE and \c T_NODE to a node-map of 
marci@510
   744
    /// stGraphWrapper<Graph>.
marci@510
   745
    template<typename NM> class NodeMapWrapper { 
marci@510
   746
    public:
marci@510
   747
      typedef Node KeyType;
marci@510
   748
      typedef typename NM::ValueType ValueType;
marci@510
   749
    protected:
marci@510
   750
      NM* nm;
marci@510
   751
      ValueType* s_value, t_value;
marci@510
   752
    public:
marci@510
   753
      NodeMapWrapper(NM& _nm, ValueType& _s_value, ValueType& _t_value) : 
marci@510
   754
	nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }
marci@510
   755
      ValueType operator[](const Node& n) const { 
marci@510
   756
	switch (n.getSpec()) {
marci@510
   757
	case 0: 
marci@510
   758
	  return (*nm)[n];
marci@510
   759
	case 1:
marci@510
   760
	  return *s_value;
marci@510
   761
	case 2: 
marci@510
   762
	default:
marci@510
   763
	  return *t_value;
marci@510
   764
	}
marci@510
   765
      }
marci@510
   766
      void set(const Node& n, ValueType t) { 
marci@510
   767
	switch (n.getSpec()) {
marci@510
   768
	case 0: 
marci@510
   769
	  nm->set(n, t);
marci@510
   770
	  break;
marci@510
   771
	case 1:
marci@510
   772
	  *s_value=t;
marci@510
   773
	  break;
marci@510
   774
	case 2:
marci@510
   775
	default:
marci@510
   776
	  *t_value=t;
marci@510
   777
	  break;
marci@510
   778
	}
marci@510
   779
      }
marci@510
   780
    };
marci@510
   781
marci@510
   782
    template<typename T> 
marci@510
   783
    class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 
marci@510
   784
      typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
marci@510
   785
    protected:
marci@389
   786
      typename GraphWrapper<Graph>::template NodeMap<T> node_value;
marci@379
   787
    public:
marci@393
   788
      EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), 
marci@393
   789
						 node_value(_G) { }
marci@389
   790
      EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
marci@389
   791
						      node_value(_G, a) { }
marci@379
   792
      T operator[](const Edge& e) const { 
marci@379
   793
	switch (e.spec) {
marci@393
   794
	case 0: 
marci@393
   795
	  return Parent::operator[](e);
marci@393
   796
	case 1:
marci@393
   797
	  return node_value[e.n];
marci@393
   798
	case 2:
marci@393
   799
	default:
marci@393
   800
	  return node_value[e.n];
marci@379
   801
	}
marci@379
   802
      }
marci@379
   803
      void set(const Edge& e, T t) { 
marci@379
   804
	switch (e.spec) {
marci@393
   805
	case 0: 
marci@409
   806
	  Parent::set(e, t);
marci@393
   807
	  break;
marci@393
   808
	case 1:
marci@393
   809
	  node_value.set(e.n, t);
marci@393
   810
	  break;
marci@393
   811
	case 2:
marci@393
   812
	default:
marci@393
   813
	  node_value.set(e.n, t);
marci@393
   814
	  break;
marci@379
   815
	}
marci@379
   816
      }
marci@379
   817
    };
marci@409
   818
marci@510
   819
    /// This class is to wrap an edge-map and a node-map of \c Graph 
marci@510
   820
    /// to an edge-map of stGraphWrapper<Graph>.
marci@510
   821
    template<typename EM, typename NM> 
marci@510
   822
    class EdgeMapWrapper {
marci@510
   823
    public: 
marci@510
   824
      typedef Edge KeyType;
marci@510
   825
      typedef typename EM::ValueType ValueType;
marci@510
   826
    protected:
marci@510
   827
      EM* em;
marci@510
   828
      NM* nm;
marci@510
   829
    public:
marci@510
   830
      EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }
marci@510
   831
      ValueType operator[](const Edge& e) const { 
marci@510
   832
	switch (e.getSpec()) {
marci@510
   833
	case 0: 
marci@510
   834
	  return (*em)[e];
marci@510
   835
	case 1:
marci@510
   836
	  return (*nm)[e.getNode()];
marci@510
   837
	case 2:
marci@510
   838
	default:
marci@510
   839
	  return (*nm)[e.getNode()];
marci@510
   840
	}
marci@510
   841
      }
marci@510
   842
      void set(const Edge& e, ValueType t) { 
marci@510
   843
	switch (e.getSpec()) {
marci@510
   844
	case 0: 
marci@510
   845
	  em->set(e, t);
marci@510
   846
	  break;
marci@510
   847
	case 1:
marci@510
   848
	  nm->set(e.getNode(), t);
marci@510
   849
	  break;
marci@510
   850
	case 2:
marci@510
   851
	default:
marci@510
   852
	  nm->set(e.getNode(), t);
marci@510
   853
	  break;
marci@510
   854
	}
marci@510
   855
      }
marci@510
   856
    };
marci@510
   857
marci@409
   858
marci@435
   859
//  template<typename G> 
marci@435
   860
    friend std::ostream& 
marci@435
   861
    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) { 
marci@409
   862
      os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 
marci@409
   863
      return os; 
marci@409
   864
    }
marci@435
   865
//  template<typename G> 
marci@435
   866
    friend std::ostream& 
marci@435
   867
    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) { 
marci@409
   868
      os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 
marci@409
   869
	" node: " << i.n << ")"; 
marci@409
   870
      return os; 
marci@409
   871
    }
marci@409
   872
marci@379
   873
  };
marci@379
   874
alpar@406
   875
  ///@}
marci@341
   876
alpar@105
   877
} //namespace hugo
marci@76
   878
alpar@406
   879
marci@510
   880
#endif //HUGO_BIPARTITE_GRAPH_WRAPPER_H
marci@76
   881