Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/graph_wrapper.h
changeset 197 fff43d9c7110
parent 168 27fbd1559fb7
child 199 98b93792541e
equal deleted inserted replaced
6:519477d6709c 7:5f32dbefd09d 
     1 // -*-mode: c++; -*-
 
     1 // -*- c++ -*-
 
     2 #ifndef GRAPH_WRAPPER_H
 
     2 #ifndef GRAPH_WRAPPER_H
 
     3 #define GRAPH_WRAPPER_H
 
     3 #define GRAPH_WRAPPER_H
 
       
     4 
       
     5 #include <invalid.h>
 
     4 
     6 
     5 namespace hugo {
 
     7 namespace hugo {
 
     6 
     8 
     7   template<typename Graph>
 
     9   template<typename Graph>
 
     8   class TrivGraphWrapper {
 
    10   class TrivGraphWrapper {
 
     9     Graph* graph;
 
    11     Graph* graph;
 
    10   
    12   
    11   public:
 
    13   public:
 
    12     typedef Graph BaseGraph;
 
    14     typedef Graph BaseGraph;
 
    13 
    15 
       
    16     typedef typename Graph::Node Node;
 
    14     typedef typename Graph::NodeIt NodeIt;
 
    17     typedef typename Graph::NodeIt NodeIt;
 
    15     typedef typename Graph::EachNodeIt EachNodeIt;
 
    18 
    16 
    19     typedef typename Graph::Edge Edge;
 
    17     typedef typename Graph::EdgeIt EdgeIt;
 
       
    18     typedef typename Graph::OutEdgeIt OutEdgeIt;
 
    20     typedef typename Graph::OutEdgeIt OutEdgeIt;
 
    19     typedef typename Graph::InEdgeIt InEdgeIt;
 
    21     typedef typename Graph::InEdgeIt InEdgeIt;
 
    20     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
    22     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
    21     typedef typename Graph::EachEdgeIt EachEdgeIt;
 
    23     typedef typename Graph::EdgeIt EdgeIt;
 
    22 
    24 
    23     //TrivGraphWrapper() : graph(0) { }
 
    25     //TrivGraphWrapper() : graph(0) { }
 
    24     TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
 
    26     TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
 
    25 
    27 
    26     void setGraph(Graph& _graph) { graph = &_graph; }
 
    28     void setGraph(Graph& _graph) { graph = &_graph; }
 
    27     Graph& getGraph() const { return (*graph); }
 
    29     Graph& getGraph() const { return (*graph); }
 
    28     
    30     
    29     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
 
    31     template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
 
    30     template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
    32     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 
    31       return graph->getFirst(i, p); }
 
    33       return graph->/*getF*/first(i, p); }
 
    32     
    34     
    33     template<typename I> I getNext(const I& i) const { 
    35     template<typename I> I getNext(const I& i) const { 
    34       return graph->getNext(i); }
 
    36       return graph->getNext(i); }
 
    35     template<typename I> I& next(I &i) const { return graph->next(i); }    
    37     template<typename I> I& next(I &i) const { return graph->next(i); }    
    36 
    38 
    37     template< typename It > It first() const { 
    39     template< typename It > It first() const { 
    38       It e; getFirst(e); return e; }
 
    40       It e; /*getF*/first(e); return e; }
 
    39 
    41 
    40     template< typename It > It first(const NodeIt& v) const { 
    42     template< typename It > It first(const Node& v) const { 
    41       It e; getFirst(e, v); return e; }
 
    43       It e; /*getF*/first(e, v); return e; }
 
    42 
    44 
    43     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
 
    45     Node head(const Edge& e) const { return graph->head(e); }
 
    44     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
 
    46     Node tail(const Edge& e) const { return graph->tail(e); }
 
    45 
    47 
    46     template<typename I> bool valid(const I& i) const 
    48     template<typename I> bool valid(const I& i) const 
    47       { return graph->valid(i); }
 
    49       { return graph->valid(i); }
 
    48   
    50   
    49     //template<typename I> void setInvalid(const I &i);
 
    51     //template<typename I> void setInvalid(const I &i);
 
    50     //{ return graph->setInvalid(i); }
 
    52     //{ return graph->setInvalid(i); }
 
    51 
    53 
    52     int nodeNum() const { return graph->nodeNum(); }
 
    54     int nodeNum() const { return graph->nodeNum(); }
 
    53     int edgeNum() const { return graph->edgeNum(); }
 
    55     int edgeNum() const { return graph->edgeNum(); }
 
    54   
    56   
    55     template<typename I> NodeIt aNode(const I& e) const { 
    57     template<typename I> Node aNode(const I& e) const { 
    56       return graph->aNode(e); }
 
    58       return graph->aNode(e); }
 
    57     template<typename I> NodeIt bNode(const I& e) const { 
    59     template<typename I> Node bNode(const I& e) const { 
    58       return graph->bNode(e); }
 
    60       return graph->bNode(e); }
 
    59   
    61   
    60     NodeIt addNode() const { return graph->addNode(); }
 
    62     Node addNode() const { return graph->addNode(); }
 
    61     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
    63     Edge addEdge(const Node& tail, const Node& head) const { 
    62       return graph->addEdge(tail, head); }
 
    64       return graph->addEdge(tail, head); }
 
    63   
    65   
    64     template<typename I> void erase(const I& i) const { graph->erase(i); }
 
    66     template<typename I> void erase(const I& i) const { graph->erase(i); }
 
    65   
    67   
    66     void clear() const { graph->clear(); }
 
    68     void clear() const { graph->clear(); }
 
    88     Graph* graph;
 
    90     Graph* graph;
 
    89   
    91   
    90   public:
 
    92   public:
 
    91     typedef Graph BaseGraph;
 
    93     typedef Graph BaseGraph;
 
    92 
    94 
    93     typedef typename Graph::NodeIt NodeIt;    
    95     typedef typename Graph::Node Node;    
    94     typedef typename Graph::EachNodeIt EachNodeIt;
 
    96     typedef typename Graph::NodeIt NodeIt;
 
    95   
    97   
    96     typedef typename Graph::EdgeIt EdgeIt;
 
    98     typedef typename Graph::Edge Edge;
 
    97     typedef typename Graph::OutEdgeIt InEdgeIt;
 
    99     typedef typename Graph::OutEdgeIt InEdgeIt;
 
    98     typedef typename Graph::InEdgeIt OutEdgeIt;
 
   100     typedef typename Graph::InEdgeIt OutEdgeIt;
 
    99     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   101     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   100     typedef typename Graph::EachEdgeIt EachEdgeIt;
 
   102     typedef typename Graph::EdgeIt EdgeIt;
 
   101 
   103 
   102     //RevGraphWrapper() : graph(0) { }
 
   104     //RevGraphWrapper() : graph(0) { }
 
   103     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
 
   105     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
 
   104 
   106 
   105     void setGraph(Graph& _graph) { graph = &_graph; }
 
   107     void setGraph(Graph& _graph) { graph = &_graph; }
 
   106     Graph& getGraph() const { return (*graph); }
 
   108     Graph& getGraph() const { return (*graph); }
 
   107     
   109     
   108     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
 
   110     template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
 
   109     template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
   111     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 
   110       return graph->getFirst(i, p); }
 
   112       return graph->/*getF*/first(i, p); }
 
   111 
   113 
   112     template<typename I> I getNext(const I& i) const { 
   114     template<typename I> I getNext(const I& i) const { 
   113       return graph->getNext(i); }
 
   115       return graph->getNext(i); }
 
   114     template<typename I> I& next(I &i) const { return graph->next(i); }    
   116     template<typename I> I& next(I &i) const { return graph->next(i); }    
   115 
   117 
   116     template< typename It > It first() const { 
   118     template< typename It > It first() const { 
   117       It e; getFirst(e); return e; }
 
   119       It e; /*getF*/first(e); return e; }
 
   118 
   120 
   119     template< typename It > It first(const NodeIt& v) const { 
   121     template< typename It > It first(const Node& v) const { 
   120       It e; getFirst(e, v); return e; }
 
   122       It e; /*getF*/first(e, v); return e; }
 
   121 
   123 
   122     NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
 
   124     Node head(const Edge& e) const { return graph->tail(e); }
 
   123     NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
 
   125     Node tail(const Edge& e) const { return graph->head(e); }
 
   124   
   126   
   125     template<typename I> bool valid(const I& i) const 
   127     template<typename I> bool valid(const I& i) const 
   126       { return graph->valid(i); }
 
   128       { return graph->valid(i); }
 
   127   
   129   
   128     //template<typename I> void setInvalid(const I &i);
 
   130     //template<typename I> void setInvalid(const I &i);
 
   129     //{ return graph->setInvalid(i); }
 
   131     //{ return graph->setInvalid(i); }
 
   130   
   132   
   131     template<typename I> NodeIt aNode(const I& e) const { 
   133     template<typename I> Node aNode(const I& e) const { 
   132       return graph->aNode(e); }
 
   134       return graph->aNode(e); }
 
   133     template<typename I> NodeIt bNode(const I& e) const { 
   135     template<typename I> Node bNode(const I& e) const { 
   134       return graph->bNode(e); }
 
   136       return graph->bNode(e); }
 
   135 
   137 
   136     NodeIt addNode() const { return graph->addNode(); }
 
   138     Node addNode() const { return graph->addNode(); }
 
   137     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
   139     Edge addEdge(const Node& tail, const Node& head) const { 
   138       return graph->addEdge(tail, head); }
 
   140       return graph->addEdge(tail, head); }
 
   139   
   141   
   140     int nodeNum() const { return graph->nodeNum(); }
 
   142     int nodeNum() const { return graph->nodeNum(); }
 
   141     int edgeNum() const { return graph->edgeNum(); }
 
   143     int edgeNum() const { return graph->edgeNum(); }
 
   142   
   144   
   167     Graph* graph;
 
   169     Graph* graph;
 
   168   
   170   
   169   public:
 
   171   public:
 
   170     typedef Graph BaseGraph;
 
   172     typedef Graph BaseGraph;
 
   171 
   173 
       
   174     typedef typename Graph::Node Node;
 
   172     typedef typename Graph::NodeIt NodeIt;
 
   175     typedef typename Graph::NodeIt NodeIt;
 
   173     typedef typename Graph::EachNodeIt EachNodeIt;
 
   176 
   174 
   177     //typedef typename Graph::Edge Edge;
 
   175     //typedef typename Graph::EdgeIt EdgeIt;
 
       
   176     //typedef typename Graph::OutEdgeIt OutEdgeIt;
 
   178     //typedef typename Graph::OutEdgeIt OutEdgeIt;
 
   177     //typedef typename Graph::InEdgeIt InEdgeIt;
 
   179     //typedef typename Graph::InEdgeIt InEdgeIt;
 
   178     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   180     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   179     //typedef typename Graph::EachEdgeIt EachEdgeIt;
 
   181     //typedef typename Graph::EdgeIt EdgeIt;
 
   180 
   182 
   181     //private:
 
   183     //private:
 
   182     typedef typename Graph::EdgeIt GraphEdgeIt;
 
   184     typedef typename Graph::Edge GraphEdge;
 
   183     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
 
   185     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
 
   184     typedef typename Graph::InEdgeIt GraphInEdgeIt;
 
   186     typedef typename Graph::InEdgeIt GraphInEdgeIt;
 
   185     //public:
 
   187     //public:
 
   186 
   188 
   187     //UndirGraphWrapper() : graph(0) { }
 
   189     //UndirGraphWrapper() : graph(0) { }
 
   188     UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
 
   190     UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
 
   189 
   191 
   190     void setGraph(Graph& _graph) { graph = &_graph; }
 
   192     void setGraph(Graph& _graph) { graph = &_graph; }
 
   191     Graph& getGraph() const { return (*graph); }
 
   193     Graph& getGraph() const { return (*graph); }
 
   192   
   194   
   193     class EdgeIt {
 
   195     class Edge {
 
   194       friend class UndirGraphWrapper<Graph>;
 
   196       friend class UndirGraphWrapper<Graph>;
 
   195       bool out_or_in; //true iff out
 
   197       bool out_or_in; //true iff out
 
   196       GraphOutEdgeIt out;
 
   198       GraphOutEdgeIt out;
 
   197       GraphInEdgeIt in;
 
   199       GraphInEdgeIt in;
 
   198     public:
 
   200     public:
 
   199       EdgeIt() : out_or_in(true), out(), in() { }
 
   201       Edge() : out_or_in(), out(), in() { }
 
   200       operator GraphEdgeIt() const {
 
   202       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
 
       
   203       operator GraphEdge() const {
 
   201 	if (out_or_in) return(out); else return(in);
 
   204 	if (out_or_in) return(out); else return(in);
 
   202       }
 
   205       }
 
   203     };
 
   206       friend bool operator==(const Edge& u, const Edge& v) { 
   204 
   207 	if (v.out_or_in) 
   205     class OutEdgeIt : public EdgeIt {
 
   208 	  return (u.out_or_in && u.out==v.out);
 
       
   209 	else
 
       
   210 	  return (!u.out_or_in && u.in==v.in);
 
       
   211       } 
       
   212       friend bool operator!=(const Edge& u, const Edge& v) { 
       
   213 	if (v.out_or_in) 
       
   214 	  return (!u.out_or_in || u.out!=v.out);
 
       
   215 	else
 
       
   216 	  return (u.out_or_in || u.in!=v.in);
 
       
   217       } 
       
   218     };
 
       
   219 
       
   220     class OutEdgeIt : public Edge {
 
   206       friend class UndirGraphWrapper<Graph>;
 
   221       friend class UndirGraphWrapper<Graph>;
 
   207     public:
 
   222     public:
 
   208       OutEdgeIt() : EdgeIt() { }
 
   223       OutEdgeIt() : Edge() { }
 
   209       OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() { 
   224       OutEdgeIt(const Invalid& i) : Edge(i) { }
 
   210 	_G.graph->getFirst(out, n);
 
   225       OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() { 
       
   226 	out_or_in=true;
 
       
   227 	_G.graph->/*getF*/first(out, n);
 
   211 	if (!(_G.graph->valid(out))) {
 
   228 	if (!(_G.graph->valid(out))) {
 
   212 	  out_or_in=false;
 
   229 	  out_or_in=false;
 
   213 	  _G.graph->getFirst(in, n);
 
   230 	  _G.graph->/*getF*/first(in, n);
 
   214 	}
 
   231 	}
 
   215       }
 
   232       }
 
   216     };
 
   233     };
 
   217 
   234 
   218     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
 
   235     OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
 
   219       e.out_or_in=true;
 
   236       e.out_or_in=true;
 
   220       graph->getFirst(e.out, n);
 
   237       graph->/*getF*/first(e.out, n);
 
   221       if (!(graph->valid(e.out))) {
 
   238       if (!(graph->valid(e.out))) {
 
   222 	e.out_or_in=false;
 
   239 	e.out_or_in=false;
 
   223 	graph->getFirst(e.in, n);
 
   240 	graph->/*getF*/first(e.in, n);
 
   224       }
 
   241       }
 
   225       return e;
 
   242       return e;
 
   226     }
 
   243     }
 
   227 
   244 
   228     OutEdgeIt& next(OutEdgeIt& e) const {
 
   245     OutEdgeIt& next(OutEdgeIt& e) const {
 
   229       if (e.out_or_in) {
 
   246       if (e.out_or_in) {
 
   230 	NodeIt n=graph->tail(e.out);
 
   247 	Node n=graph->tail(e.out);
 
   231 	graph->next(e.out);
 
   248 	graph->next(e.out);
 
   232 	if (!graph->valid(e.out)) {
 
   249 	if (!graph->valid(e.out)) {
 
   233 	  e.out_or_in=false;
 
   250 	  e.out_or_in=false;
 
   234 	  graph->getFirst(e.in, n);
 
   251 	  graph->/*getF*/first(e.in, n);
 
   235 	}
 
   252 	}
 
   236       } else {
 
   253       } else {
 
   237 	graph->next(e.in);
 
   254 	graph->next(e.in);
 
   238       }
 
   255       }
 
   239       return e;
 
   256       return e;
 
   240     }
 
   257     }
 
   241 
   258 
   242     NodeIt aNode(const OutEdgeIt& e) const { 
   259     Node aNode(const OutEdgeIt& e) const { 
   243       if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
 
   260       if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
 
   244     NodeIt bNode(const OutEdgeIt& e) const { 
   261     Node bNode(const OutEdgeIt& e) const { 
   245       if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
 
   262       if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
 
   246 
   263 
   247     typedef OutEdgeIt InEdgeIt; 
   264     typedef OutEdgeIt InEdgeIt; 
   248 
   265 
   249     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
 
   266     template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
 
   250 //     template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
   267 //     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 
   251 //       return graph->getFirst(i, p); }
 
   268 //       return graph->/*getF*/first(i, p); }
 
   252     
   269     
   253     template<typename I> I getNext(const I& i) const { 
   270     template<typename I> I getNext(const I& i) const { 
   254       return graph->getNext(i); }
 
   271       return graph->getNext(i); }
 
   255     template<typename I> I& next(I &i) const { return graph->next(i); }    
   272     template<typename I> I& next(I &i) const { return graph->next(i); }    
   256 
   273 
   257     template< typename It > It first() const { 
   274     template< typename It > It first() const { 
   258       It e; getFirst(e); return e; }
 
   275       It e; /*getF*/first(e); return e; }
 
   259 
   276 
   260     template< typename It > It first(const NodeIt& v) const { 
   277     template< typename It > It first(const Node& v) const { 
   261       It e; getFirst(e, v); return e; }
 
   278       It e; /*getF*/first(e, v); return e; }
 
   262 
   279 
   263     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
 
   280     Node head(const Edge& e) const { return graph->head(e); }
 
   264     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
 
   281     Node tail(const Edge& e) const { return graph->tail(e); }
 
   265 
   282 
   266     template<typename I> bool valid(const I& i) const 
   283     template<typename I> bool valid(const I& i) const 
   267       { return graph->valid(i); }
 
   284       { return graph->valid(i); }
 
   268   
   285   
   269     //template<typename I> void setInvalid(const I &i);
 
   286     //template<typename I> void setInvalid(const I &i);
 
   270     //{ return graph->setInvalid(i); }
 
   287     //{ return graph->setInvalid(i); }
 
   271 
   288 
   272     int nodeNum() const { return graph->nodeNum(); }
 
   289     int nodeNum() const { return graph->nodeNum(); }
 
   273     int edgeNum() const { return graph->edgeNum(); }
 
   290     int edgeNum() const { return graph->edgeNum(); }
 
   274   
   291   
   275 //     template<typename I> NodeIt aNode(const I& e) const { 
   292 //     template<typename I> Node aNode(const I& e) const { 
   276 //       return graph->aNode(e); }
 
   293 //       return graph->aNode(e); }
 
   277 //     template<typename I> NodeIt bNode(const I& e) const { 
   294 //     template<typename I> Node bNode(const I& e) const { 
   278 //       return graph->bNode(e); }
 
   295 //       return graph->bNode(e); }
 
   279   
   296   
   280     NodeIt addNode() const { return graph->addNode(); }
 
   297     Node addNode() const { return graph->addNode(); }
 
   281     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
   298     Edge addEdge(const Node& tail, const Node& head) const { 
   282       return graph->addEdge(tail, head); }
 
   299       return graph->addEdge(tail, head); }
 
   283   
   300   
   284     template<typename I> void erase(const I& i) const { graph->erase(i); }
 
   301     template<typename I> void erase(const I& i) const { graph->erase(i); }
 
   285   
   302   
   286     void clear() const { graph->clear(); }
 
   303     void clear() const { graph->clear(); }
 
   310 //     Graph* graph;
 
   327 //     Graph* graph;
 
   311   
   328   
   312 //   public:
 
   329 //   public:
 
   313 //     typedef Graph BaseGraph;
 
   330 //     typedef Graph BaseGraph;
 
   314 
   331 
       
   332 //     typedef typename Graph::Node Node;
 
       
   333 //     typedef typename Graph::Edge Edge;
 
       
   334   
   315 //     typedef typename Graph::NodeIt NodeIt;
 
   335 //     typedef typename Graph::NodeIt NodeIt;
 
   316 //     typedef typename Graph::EdgeIt EdgeIt;
 
       
   317   
       
   318 //     typedef typename Graph::EachNodeIt EachNodeIt;
 
       
   319     
   336     
   320 //     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
 
   337 //     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
 
   321 //     //iranyitatlant, ami van
 
   338 //     //iranyitatlant, ami van
 
   322 //     //mert csak 1 dolgot lehet be typedef-elni
 
   339 //     //mert csak 1 dolgot lehet be typedef-elni
 
   323 //     typedef typename Graph::OutEdgeIt SymEdgeIt;
 
   340 //     typedef typename Graph::OutEdgeIt SymEdgeIt;
 
   324 //     //typedef typename Graph::InEdgeIt SymEdgeIt;
 
   341 //     //typedef typename Graph::InEdgeIt SymEdgeIt;
 
   325 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   342 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   326 //     typedef typename Graph::EachEdgeIt EachEdgeIt;
 
   343 //     typedef typename Graph::EdgeIt EdgeIt;
 
   327 
   344 
   328 //     int nodeNum() const { return graph->nodeNum(); }
 
   345 //     int nodeNum() const { return graph->nodeNum(); }
 
   329 //     int edgeNum() const { return graph->edgeNum(); }
 
   346 //     int edgeNum() const { return graph->edgeNum(); }
 
   330     
   347     
   331 //     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
 
   348 //     template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
 
   332 //     template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
   349 //     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 
   333 //       return graph->getFirst(i, p); }
 
   350 //       return graph->/*getF*/first(i, p); }
 
   334 //     //template<typename I> I next(const I i); { return graph->goNext(i); }
 
   351 //     //template<typename I> I next(const I i); { return graph->goNext(i); }
 
   335 //     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
 
   352 //     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
 
   336 
   353 
   337 //     template< typename It > It first() const { 
   354 //     template< typename It > It first() const { 
   338 //       It e; getFirst(e); return e; }
 
   355 //       It e; /*getF*/first(e); return e; }
 
   339 
   356 
   340 //     template< typename It > It first(NodeIt v) const { 
   357 //     template< typename It > It first(Node v) const { 
   341 //       It e; getFirst(e, v); return e; }
 
   358 //       It e; /*getF*/first(e, v); return e; }
 
   342 
   359 
   343 //     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
 
   360 //     Node head(const Edge& e) const { return graph->head(e); }
 
   344 //     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
 
   361 //     Node tail(const Edge& e) const { return graph->tail(e); }
 
   345   
   362   
   346 //     template<typename I> NodeIt aNode(const I& e) const { 
   363 //     template<typename I> Node aNode(const I& e) const { 
   347 //       return graph->aNode(e); }
 
   364 //       return graph->aNode(e); }
 
   348 //     template<typename I> NodeIt bNode(const I& e) const { 
   365 //     template<typename I> Node bNode(const I& e) const { 
   349 //       return graph->bNode(e); }
 
   366 //       return graph->bNode(e); }
 
   350   
   367   
   351 //     //template<typename I> bool valid(const I i);
 
   368 //     //template<typename I> bool valid(const I i);
 
   352 //     //{ return graph->valid(i); }
 
   369 //     //{ return graph->valid(i); }
 
   353   
   370   
   354 //     //template<typename I> void setInvalid(const I &i);
 
   371 //     //template<typename I> void setInvalid(const I &i);
 
   355 //     //{ return graph->setInvalid(i); }
 
   372 //     //{ return graph->setInvalid(i); }
 
   356   
   373   
   357 //     NodeIt addNode() { return graph->addNode(); }
 
   374 //     Node addNode() { return graph->addNode(); }
 
   358 //     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 
   375 //     Edge addEdge(const Node& tail, const Node& head) { 
   359 //       return graph->addEdge(tail, head); }
 
   376 //       return graph->addEdge(tail, head); }
 
   360   
   377   
   361 //     template<typename I> void erase(const I& i) { graph->erase(i); }
 
   378 //     template<typename I> void erase(const I& i) { graph->erase(i); }
 
   362   
   379   
   363 //     void clear() { graph->clear(); }
 
   380 //     void clear() { graph->clear(); }
 
   375 
   392 
   376   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
 
   393   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
 
   377   class ResGraphWrapper {
 
   394   class ResGraphWrapper {
 
   378   public:
 
   395   public:
 
   379     typedef Graph BaseGraph;
 
   396     typedef Graph BaseGraph;
 
       
   397     typedef typename Graph::Node Node;
 
   380     typedef typename Graph::NodeIt NodeIt;
 
   398     typedef typename Graph::NodeIt NodeIt;
 
   381     typedef typename Graph::EachNodeIt EachNodeIt;
 
       
   382   private:
 
   399   private:
 
   383     typedef typename Graph::OutEdgeIt OldOutEdgeIt;
 
   400     typedef typename Graph::OutEdgeIt OldOutEdgeIt;
 
   384     typedef typename Graph::InEdgeIt OldInEdgeIt;
 
   401     typedef typename Graph::InEdgeIt OldInEdgeIt;
 
   385     const Graph* G;
 
   402     const Graph* graph;
 
   386     FlowMap* flow;
 
   403     FlowMap* flow;
 
   387     const CapacityMap* capacity;
 
   404     const CapacityMap* capacity;
 
   388   public:
 
   405   public:
 
   389 
   406 
   390     ResGraphWrapper(const Graph& _G, FlowMap& _flow, 
   407     ResGraphWrapper(const Graph& _G, FlowMap& _flow, 
   391 	     const CapacityMap& _capacity) : 
   408 	     const CapacityMap& _capacity) : 
   392       G(&_G), flow(&_flow), capacity(&_capacity) { }
 
   409       graph(&_G), flow(&_flow), capacity(&_capacity) { }
 
   393 //     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : 
       
   394 //       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
 
       
   395 
   410 
   396     void setGraph(const Graph& _graph) { graph = &_graph; }
 
   411     void setGraph(const Graph& _graph) { graph = &_graph; }
 
   397     const Graph& getGraph() const { return (*G); }
 
   412     const Graph& getGraph() const { return (*graph); }
 
   398 
   413 
   399     class EdgeIt; 
   414     class Edge; 
   400     class OutEdgeIt; 
   415     class OutEdgeIt; 
   401     friend class EdgeIt; 
   416     friend class Edge; 
   402     friend class OutEdgeIt; 
   417     friend class OutEdgeIt; 
   403 
   418 
   404     class EdgeIt {
 
   419     class Edge {
 
   405       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
 
   420       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
 
   406     protected:
 
   421     protected:
 
   407       bool out_or_in; //true, iff out
 
   422       bool out_or_in; //true, iff out
 
   408       OldOutEdgeIt out;
 
   423       OldOutEdgeIt out;
 
   409       OldInEdgeIt in;
 
   424       OldInEdgeIt in;
 
   410     public:
 
   425     public:
 
   411       EdgeIt() : out_or_in(true) { } 
   426       Edge() : out_or_in(true) { } 
       
   427       Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
 
   412 //       bool valid() const { 
   428 //       bool valid() const { 
   413 // 	return out_or_in && out.valid() || in.valid(); }
 
   429 // 	return out_or_in && out.valid() || in.valid(); }
 
   414     };
 
   430       friend bool operator==(const Edge& u, const Edge& v) { 
   415 
   431 	if (v.out_or_in) 
   416 
   432 	  return (u.out_or_in && u.out==v.out);
 
   417     class OutEdgeIt : public EdgeIt {
 
   433 	else
 
       
   434 	  return (!u.out_or_in && u.in==v.in);
 
       
   435       } 
       
   436       friend bool operator!=(const Edge& u, const Edge& v) { 
       
   437 	if (v.out_or_in) 
       
   438 	  return (!u.out_or_in || u.out!=v.out);
 
       
   439 	else
 
       
   440 	  return (u.out_or_in || u.in!=v.in);
 
       
   441       } 
       
   442     };
 
       
   443 
       
   444 
       
   445     class OutEdgeIt : public Edge {
 
   418       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
 
   446       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
 
   419     public:
 
   447     public:
 
   420       OutEdgeIt() { }
 
   448       OutEdgeIt() { }
 
   421       //FIXME
 
   449       //FIXME
 
   422       OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { }
 
   450       OutEdgeIt(const Edge& e) : Edge(e) { }
 
       
   451       OutEdgeIt(const Invalid& i) : Edge(i) { }
 
   423     private:
 
   452     private:
 
   424       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() { 
   453       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 
   425 	resG.G->getFirst(out, v);
 
   454 	resG.graph->/*getF*/first(out, v);
 
   426 	while( out.valid() && !(resG.free(out)>0) ) { ++out; }
 
   455 	while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
 
   427 	if (!out.valid()) {
 
   456 	if (!resG.graph->valid(out)) {
 
   428 	  out_or_in=0;
 
   457 	  out_or_in=0;
 
   429 	  resG.G->getFirst(in, v);
 
   458 	  resG.graph->/*getF*/first(in, v);
 
   430 	  while( in.valid() && !(resG.free(in)>0) ) { ++in; }
 
   459 	  while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
 
   431 	}
 
   460 	}
 
   432       }
 
   461       }
 
   433 //     public:
 
   462 //     public:
 
   434 //       OutEdgeIt& operator++() { 
   463 //       OutEdgeIt& operator++() { 
   435 // 	if (out_or_in) {
 
   464 // 	if (out_or_in) {
 
   436 // 	  NodeIt v=/*resG->*/G->aNode(out);
 
   465 // 	  Node v=/*resG->*/G->aNode(out);
 
   437 // 	  ++out;
 
   466 // 	  ++out;
 
   438 // 	  while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
 
   467 // 	  while( out.valid() && !(Edge::free()>0) ) { ++out; }
 
   439 // 	  if (!out.valid()) {
 
   468 // 	  if (!out.valid()) {
 
   440 // 	    out_or_in=0;
 
   469 // 	    out_or_in=0;
 
   441 // 	    G->getFirst(in, v); 
   470 // 	    G->/*getF*/first(in, v); 
   442 // 	    while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
 
   471 // 	    while( in.valid() && !(Edge::free()>0) ) { ++in; }
 
   443 // 	  }
 
   472 // 	  }
 
   444 // 	} else {
 
   473 // 	} else {
 
   445 // 	  ++in;
 
   474 // 	  ++in;
 
   446 // 	  while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } 
   475 // 	  while( in.valid() && !(Edge::free()>0) ) { ++in; } 
   447 // 	}
 
   476 // 	}
 
   448 // 	return *this; 
   477 // 	return *this; 
   449 //       }
 
   478 //       }
 
   450     };
 
   479     };
 
   451 
   480 
   452     class EachEdgeIt : public EdgeIt {
 
   481     class EdgeIt : public Edge {
 
   453       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
 
   482       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
 
   454       typename Graph::EachNodeIt v;
 
   483       typename Graph::NodeIt v;
 
   455     public:
 
   484     public:
 
   456       EachEdgeIt() { }
 
   485       EdgeIt() { }
 
   457       //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
 
   486       //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
 
   458       EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() { 
   487       EdgeIt(const Invalid& i) : Edge(i) { }
 
   459 	resG.G->getFirst(v);
 
   488       EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { 
   460 	if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt();
 
   489 	resG.graph->/*getF*/first(v);
 
   461 	while (out.valid() && !(resG.free(out)>0) ) { ++out; }
 
   490 	if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); else out=OldOutEdgeIt(INVALID);
 
   462 	while (v.valid() && !out.valid()) { 
   491 	while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
 
   463 	  ++v; 
   492 	while (resG.graph->valid(v) && !resG.graph->valid(out)) { 
   464 	  if (v.valid()) resG.G->getFirst(out, v); 
   493 	  resG.graph->next(v); 
   465 	  while (out.valid() && !(resG.free(out)>0) ) { ++out; }
 
   494 	  if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); 
       
   495 	  while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
 
   466 	}
 
   496 	}
 
   467 	if (!out.valid()) {
 
   497 	if (!resG.graph->valid(out)) {
 
   468 	  out_or_in=0;
 
   498 	  out_or_in=0;
 
   469 	  resG.G->getFirst(v);
 
   499 	  resG.graph->/*getF*/first(v);
 
   470 	  if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();
 
   500 	  if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); else in=OldInEdgeIt(INVALID);
 
   471 	  while (in.valid() && !(resG.free(in)>0) ) { ++in; }
 
   501 	  while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
 
   472 	  while (v.valid() && !in.valid()) { 
   502 	  while (resG.graph->valid(v) && !resG.graph->valid(in)) { 
   473 	    ++v; 
   503 	    resG.graph->next(v); 
   474 	    if (v.valid()) resG.G->getFirst(in, v); 
   504 	    if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); 
   475 	    while (in.valid() && !(resG.free(in)>0) ) { ++in; }
 
   505 	    while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
 
   476 	  }
 
   506 	  }
 
   477 	}
 
   507 	}
 
   478       }
 
   508       }
 
   479 //       EachEdgeIt& operator++() { 
   509 //       EdgeIt& operator++() { 
   480 // 	if (out_or_in) {
 
   510 // 	if (out_or_in) {
 
   481 // 	  ++out;
 
   511 // 	  ++out;
 
   482 // 	  while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
 
   512 // 	  while (out.valid() && !(Edge::free()>0) ) { ++out; }
 
   483 // 	  while (v.valid() && !out.valid()) { 
   513 // 	  while (v.valid() && !out.valid()) { 
   484 // 	    ++v; 
   514 // 	    ++v; 
   485 // 	    if (v.valid()) G->getFirst(out, v); 
   515 // 	    if (v.valid()) G->/*getF*/first(out, v); 
   486 // 	    while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
 
   516 // 	    while (out.valid() && !(Edge::free()>0) ) { ++out; }
 
   487 // 	  }
 
   517 // 	  }
 
   488 // 	  if (!out.valid()) {
 
   518 // 	  if (!out.valid()) {
 
   489 // 	    out_or_in=0;
 
   519 // 	    out_or_in=0;
 
   490 // 	    G->getFirst(v);
 
   520 // 	    G->/*getF*/first(v);
 
   491 // 	    if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
 
   521 // 	    if (v.valid()) G->/*getF*/first(in, v); else in=OldInEdgeIt();
 
   492 // 	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
 
   522 // 	    while (in.valid() && !(Edge::free()>0) ) { ++in; }
 
   493 // 	    while (v.valid() && !in.valid()) { 
   523 // 	    while (v.valid() && !in.valid()) { 
   494 // 	      ++v; 
   524 // 	      ++v; 
   495 // 	      if (v.valid()) G->getFirst(in, v); 
   525 // 	      if (v.valid()) G->/*getF*/first(in, v); 
   496 // 	      while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
 
   526 // 	      while (in.valid() && !(Edge::free()>0) ) { ++in; }
 
   497 // 	    }  
   527 // 	    }  
   498 // 	  }
 
   528 // 	  }
 
   499 // 	} else {
 
   529 // 	} else {
 
   500 // 	  ++in;
 
   530 // 	  ++in;
 
   501 // 	  while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
 
   531 // 	  while (in.valid() && !(Edge::free()>0) ) { ++in; }
 
   502 // 	  while (v.valid() && !in.valid()) { 
   532 // 	  while (v.valid() && !in.valid()) { 
   503 // 	    ++v; 
   533 // 	    ++v; 
   504 // 	    if (v.valid()) G->getFirst(in, v); 
   534 // 	    if (v.valid()) G->/*getF*/first(in, v); 
   505 // 	    while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
 
   535 // 	    while (in.valid() && !(Edge::free()>0) ) { ++in; }
 
   506 // 	  }
 
   536 // 	  }
 
   507 // 	}
 
   537 // 	}
 
   508 // 	return *this;
 
   538 // 	return *this;
 
   509 //       }
 
   539 //       }
 
   510     };
 
   540     };
 
   511 
   541 
   512     EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }
 
   542     NodeIt& /*getF*/first(NodeIt& v) const { return graph->/*getF*/first(v); }
 
   513     OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const { 
   543     OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const { 
   514       e=OutEdgeIt(*this, v); 
   544       e=OutEdgeIt(*this, v); 
   515     }
 
   545       return e;
 
   516     EachEdgeIt& getFirst(EachEdgeIt& e) const { 
   546     }
 
   517       e=EachEdgeIt(*this); 
   547     EdgeIt& /*getF*/first(EdgeIt& e) const { 
       
   548       e=EdgeIt(*this); 
       
   549       return e;
 
   518     }
 
   550     }
 
   519    
   551    
   520     EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
 
   552     NodeIt& next(NodeIt& n) const { return graph->next(n); }
 
   521 
   553 
   522     OutEdgeIt& next(OutEdgeIt& e) const { 
   554     OutEdgeIt& next(OutEdgeIt& e) const { 
   523       if (e.out_or_in) {
 
   555       if (e.out_or_in) {
 
   524 	NodeIt v=G->aNode(e.out);
 
   556 	Node v=graph->aNode(e.out);
 
   525 	++(e.out);
 
   557 	graph->next(e.out);
 
   526 	while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
 
   558 	while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
 
   527 	if (!G->valid(e.out)) {
 
   559 	if (!graph->valid(e.out)) {
 
   528 	  e.out_or_in=0;
 
   560 	  e.out_or_in=0;
 
   529 	  G->getFirst(e.in, v); 
   561 	  graph->/*getF*/first(e.in, v); 
   530 	  while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
 
   562 	  while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
 
   531 	}
 
   563 	}
 
   532       } else {
 
   564       } else {
 
   533 	++(e.in);
 
   565 	graph->next(e.in);
 
   534 	while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); } 
   566 	while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } 
   535       }
 
   567       }
 
   536       return e;
 
   568       return e;
 
   537     }
 
   569     }
 
   538 
   570 
   539     EachEdgeIt& next(EachEdgeIt& e) const { 
   571     EdgeIt& next(EdgeIt& e) const { 
   540       if (e.out_or_in) {
 
   572       if (e.out_or_in) {
 
   541 	++(e.out);
 
   573 	graph->next(e.out);
 
   542 	while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
 
   574 	while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
 
   543 	  while (G->valid(e.v) && !G->valid(e.out)) { 
   575 	  while (graph->valid(e.v) && !graph->valid(e.out)) { 
   544 	    ++(e.v); 
   576 	    graph->next(e.v); 
   545 	    if (G->valid(e.v)) G->getFirst(e.out, e.v); 
   577 	    if (graph->valid(e.v)) graph->/*getF*/first(e.out, e.v); 
   546 	    while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
 
   578 	    while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
 
   547 	  }
 
   579 	  }
 
   548 	  if (!G->valid(e.out)) {
 
   580 	  if (!graph->valid(e.out)) {
 
   549 	    e.out_or_in=0;
 
   581 	    e.out_or_in=0;
 
   550 	    G->getFirst(e.v);
 
   582 	    graph->/*getF*/first(e.v);
 
   551 	    if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
 
   583 	    if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); else e.in=OldInEdgeIt(INVALID);
 
   552 	    while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
 
   584 	    while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
 
   553 	    while (G->valid(e.v) && !G->valid(e.in)) { 
   585 	    while (graph->valid(e.v) && !graph->valid(e.in)) { 
   554 	      ++(e.v); 
   586 	      graph->next(e.v); 
   555 	      if (G->valid(e.v)) G->getFirst(e.in, e.v); 
   587 	      if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); 
   556 	      while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
 
   588 	      while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
 
   557 	    }  
   589 	    }  
   558 	  }
 
   590 	  }
 
   559 	} else {
 
   591 	} else {
 
   560 	  ++(e.in);
 
   592 	  graph->next(e.in);
 
   561 	  while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
 
   593 	  while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
 
   562 	  while (G->valid(e.v) && !G->valid(e.in)) { 
   594 	  while (graph->valid(e.v) && !graph->valid(e.in)) { 
   563 	    ++(e.v); 
   595 	    graph->next(e.v); 
   564 	    if (G->valid(e.v)) G->getFirst(e.in, e.v); 
   596 	    if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); 
   565 	    while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
 
   597 	    while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
 
   566 	  }
 
   598 	  }
 
   567 	}
 
   599 	}
 
   568 	return e;
 
   600 	return e;
 
   569       }
 
   601       }
 
   570     
   602     
   571 
   603 
   572     template< typename It >
 
   604     template< typename It >
 
   573     It first() const { 
   605     It first() const { 
   574       It e;
 
   606       It e;
 
   575       getFirst(e);
 
   607       /*getF*/first(e);
 
   576       return e; 
   608       return e; 
   577     }
 
   609     }
 
   578 
   610 
   579     template< typename It >
 
   611     template< typename It >
 
   580     It first(NodeIt v) const { 
   612     It first(Node v) const { 
   581       It e;
 
   613       It e;
 
   582       getFirst(e, v);
 
   614       /*getF*/first(e, v);
 
   583       return e; 
   615       return e; 
   584     }
 
   616     }
 
   585 
   617 
   586     NodeIt tail(EdgeIt e) const { 
   618     Node tail(Edge e) const { 
   587       return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
 
   619       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
 
   588     NodeIt head(EdgeIt e) const { 
   620     Node head(Edge e) const { 
   589       return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
 
   621       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
 
   590 
   622 
   591     NodeIt aNode(OutEdgeIt e) const { 
   623     Node aNode(OutEdgeIt e) const { 
   592       return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
 
   624       return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
 
   593     NodeIt bNode(OutEdgeIt e) const { 
   625     Node bNode(OutEdgeIt e) const { 
   594       return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
 
   626       return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
 
   595 
   627 
   596     int id(NodeIt v) const { return G->id(v); }
 
   628     int id(Node v) const { return graph->id(v); }
 
   597 
   629 
   598     bool valid(NodeIt n) const { return G->valid(n); }
 
   630     bool valid(Node n) const { return graph->valid(n); }
 
   599     bool valid(EdgeIt e) const { 
   631     bool valid(Edge e) const { 
   600       return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
 
   632       return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
 
   601 
   633 
   602     void augment(const EdgeIt& e, Number a) const {
 
   634     void augment(const Edge& e, Number a) const {
 
   603       if (e.out_or_in)  
   635       if (e.out_or_in)  
   604 	flow->set(e.out, flow->get(e.out)+a);
 
   636 	flow->set(e.out, flow->get(e.out)+a);
 
   605       else  
   637       else  
   606 	flow->set(e.in, flow->get(e.in)-a);
 
   638 	flow->set(e.in, flow->get(e.in)-a);
 
   607     }
 
   639     }
 
   608 
   640 
   609     Number free(const EdgeIt& e) const { 
   641     Number free(const Edge& e) const { 
   610       if (e.out_or_in) 
   642       if (e.out_or_in) 
   611 	return (capacity->get(e.out)-flow->get(e.out)); 
   643 	return (capacity->get(e.out)-flow->get(e.out)); 
   612       else 
   644       else 
   613 	return (flow->get(e.in)); 
   645 	return (flow->get(e.in)); 
   614     }
 
   646     }
 
   631 
   663 
   632 //     template <typename T>
 
   664 //     template <typename T>
 
   633 //     class NodeMap {
 
   665 //     class NodeMap {
 
   634 //       typename Graph::NodeMap<T> node_map; 
   666 //       typename Graph::NodeMap<T> node_map; 
   635 //     public:
 
   667 //     public:
 
   636 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
 
   668 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
 
   637 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
 
   669 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
 
   638 //       void set(NodeIt nit, T a) { node_map.set(nit, a); }
 
   670 //       void set(Node nit, T a) { node_map.set(nit, a); }
 
   639 //       T get(NodeIt nit) const { return node_map.get(nit); }
 
   671 //       T get(Node nit) const { return node_map.get(nit); }
 
   640 //     };
 
   672 //     };
 
   641 
   673 
   642     template <typename T>
 
   674     template <typename T>
 
   643     class EdgeMap {
 
   675     class EdgeMap {
 
   644       typename Graph::EdgeMap<T> forward_map, backward_map; 
   676       typename Graph::EdgeMap<T> forward_map, backward_map; 
   645     public:
 
   677     public:
 
   646       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
 
   678       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
 
   647       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
 
   679       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
 
   648       void set(EdgeIt e, T a) { 
   680       void set(Edge e, T a) { 
   649 	if (e.out_or_in) 
   681 	if (e.out_or_in) 
   650 	  forward_map.set(e.out, a); 
   682 	  forward_map.set(e.out, a); 
   651 	else 
   683 	else 
   652 	  backward_map.set(e.in, a); 
   684 	  backward_map.set(e.in, a); 
   653       }
 
   685       }
 
   654       T get(EdgeIt e) { 
   686       T get(Edge e) { 
   655 	if (e.out_or_in) 
   687 	if (e.out_or_in) 
   656 	  return forward_map.get(e.out); 
   688 	  return forward_map.get(e.out); 
   657 	else 
   689 	else 
   658 	  return backward_map.get(e.in); 
   690 	  return backward_map.get(e.in); 
   659       }
 
   691       }
 
   668   public:
 
   700   public:
 
   669     ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow, 
   701     ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow, 
   670 			   const CapacityMap& _capacity) : 
   702 			   const CapacityMap& _capacity) : 
   671       ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), 
   703       ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), 
   672       first_out_edges(*this) /*, dist(*this)*/ { 
   704       first_out_edges(*this) /*, dist(*this)*/ { 
   673       for(EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) {
 
   705       for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
 
   674 	OutEdgeIt e;
 
   706 	OutEdgeIt e;
 
   675 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
 
   707 	ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n);
 
   676 	first_out_edges.set(n, e);
 
   708 	first_out_edges.set(n, e);
 
   677       }
 
   709       }
 
   678     }
 
   710     }
 
   679 
   711 
   680     //void setGraph(Graph& _graph) { graph = &_graph; }
 
   712     //void setGraph(Graph& _graph) { graph = &_graph; }
 
   683     //TrivGraphWrapper() : graph(0) { }
 
   715     //TrivGraphWrapper() : graph(0) { }
 
   684     //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
 
   716     //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
 
   685 
   717 
   686     //typedef Graph BaseGraph;
 
   718     //typedef Graph BaseGraph;
 
   687 
   719 
       
   720     //typedef typename Graph::Node Node;
 
   688     //typedef typename Graph::NodeIt NodeIt;
 
   721     //typedef typename Graph::NodeIt NodeIt;
 
   689     //typedef typename Graph::EachNodeIt EachNodeIt;
 
   722 
   690 
   723     //typedef typename Graph::Edge Edge;
 
   691     //typedef typename Graph::EdgeIt EdgeIt;
 
       
   692     //typedef typename Graph::OutEdgeIt OutEdgeIt;
 
   724     //typedef typename Graph::OutEdgeIt OutEdgeIt;
 
   693     //typedef typename Graph::InEdgeIt InEdgeIt;
 
   725     //typedef typename Graph::InEdgeIt InEdgeIt;
 
   694     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   726     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   695     //typedef typename Graph::EachEdgeIt EachEdgeIt;
 
   727     //typedef typename Graph::EdgeIt EdgeIt;
 
   696 
   728 
       
   729     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
 
   697     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
 
   730     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
 
   698     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
 
   731 
   699 
   732     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
 
   700     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
 
       
   701     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
 
   733     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
 
   702     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
 
   734     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
 
   703     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   735     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   704     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
 
   736     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
 
   705 
   737 
   706     EachNodeIt& getFirst(EachNodeIt& n) const { 
   738     NodeIt& /*getF*/first(NodeIt& n) const { 
   707       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
 
   739       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n);
 
   708     }
 
   740     }
 
   709 
   741 
   710     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const { 
   742     OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { 
   711       e=first_out_edges.get(n);
 
   743       e=first_out_edges.get(n);
 
   712       return e;
 
   744       return e;
 
   713     }
 
   745     }
 
   714     
   746     
   715     //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); }
 
   747     //ROSSZ template<typename I> I& /*getF*/first(I& i) const { return /*getF*/first(i); }
 
   716     //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
   748     //ROSSZ template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 
   717     //  return getFirst(i, p); }
 
   749     //  return /*getF*/first(i, p); }
 
   718     
   750     
   719     //template<typename I> I getNext(const I& i) const { 
   751     //template<typename I> I getNext(const I& i) const { 
   720     //  return graph->getNext(i); }
 
   752     //  return graph->getNext(i); }
 
   721     //template<typename I> I& next(I &i) const { return graph->next(i); }    
   753     //template<typename I> I& next(I &i) const { return graph->next(i); }    
   722 
   754 
   723     template< typename It > It first() const { 
   755     template< typename It > It first() const { 
   724       It e; getFirst(e); return e; }
 
   756       It e; /*getF*/first(e); return e; }
 
   725 
   757 
   726     template< typename It > It first(const NodeIt& v) const { 
   758     template< typename It > It first(const Node& v) const { 
   727       It e; getFirst(e, v); return e; }
 
   759       It e; /*getF*/first(e, v); return e; }
 
   728 
   760 
   729     //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
 
   761     //Node head(const Edge& e) const { return graph->head(e); }
 
   730     //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
 
   762     //Node tail(const Edge& e) const { return graph->tail(e); }
 
   731 
   763 
   732     //template<typename I> bool valid(const I& i) const 
   764     //template<typename I> bool valid(const I& i) const 
   733     //  { return graph->valid(i); }
 
   765     //  { return graph->valid(i); }
 
   734   
   766   
   735     //int nodeNum() const { return graph->nodeNum(); }
 
   767     //int nodeNum() const { return graph->nodeNum(); }
 
   736     //int edgeNum() const { return graph->edgeNum(); }
 
   768     //int edgeNum() const { return graph->edgeNum(); }
 
   737   
   769   
   738     //template<typename I> NodeIt aNode(const I& e) const { 
   770     //template<typename I> Node aNode(const I& e) const { 
   739     //  return graph->aNode(e); }
 
   771     //  return graph->aNode(e); }
 
   740     //template<typename I> NodeIt bNode(const I& e) const { 
   772     //template<typename I> Node bNode(const I& e) const { 
   741     //  return graph->bNode(e); }
 
   773     //  return graph->bNode(e); }
 
   742   
   774   
   743     //NodeIt addNode() const { return graph->addNode(); }
 
   775     //Node addNode() const { return graph->addNode(); }
 
   744     //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
   776     //Edge addEdge(const Node& tail, const Node& head) const { 
   745     //  return graph->addEdge(tail, head); }
 
   777     //  return graph->addEdge(tail, head); }
 
   746   
   778   
   747     //void erase(const OutEdgeIt& e) {
 
   779     //void erase(const OutEdgeIt& e) {
 
   748     //  first_out_edge(this->tail(e))=e;
 
   780     //  first_out_edge(this->tail(e))=e;
 
   749     //}
 
   781     //}
 
   750     void erase(const EdgeIt& e) {
 
   782     void erase(const Edge& e) {
 
   751       OutEdgeIt f(e);
 
   783       OutEdgeIt f(e);
 
   752       next(f);
 
   784       next(f);
 
   753       first_out_edges.set(this->tail(e), f);
 
   785       first_out_edges.set(this->tail(e), f);
 
   754     }
 
   786     }
 
   755     //template<typename I> void erase(const I& i) const { graph->erase(i); }
 
   787     //template<typename I> void erase(const I& i) const { graph->erase(i); }
 
   783     //Graph* graph;
 
   815     //Graph* graph;
 
   784   
   816   
   785   public:
 
   817   public:
 
   786     //typedef Graph BaseGraph;
 
   818     //typedef Graph BaseGraph;
 
   787 
   819 
       
   820     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
 
   788     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
 
   821     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
 
   789     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
 
   822 
   790 
   823     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
 
   791     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
 
       
   792     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
 
   824     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
 
   793     //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
 
   825     //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
 
   794     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   826     //typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   795     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
 
   827     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
 
   796 
   828 
   797     //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
 
   829     //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
 
   798     
   830     
   799   public:
 
   831   public:
 
   800     FilterGraphWrapper(const Graph& _G, FlowMap& _flow, 
   832     FilterGraphWrapper(const Graph& _G, FlowMap& _flow, 
   801 			   const CapacityMap& _capacity) : 
   833 			   const CapacityMap& _capacity) : 
   802       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) { 
   834       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) { 
   803     }
 
   835     }
 
   804 
   836 
   805     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
 
   837     OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
 
   806       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
 
   838       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n);
 
   807       while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 
   839       while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 
   808 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
 
   840 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
 
   809       return e;
 
   841       return e;
 
   810     }
 
   842     }
 
   811 
   843 
   812     EachNodeIt& next(EachNodeIt& e) const {
 
   844     NodeIt& next(NodeIt& e) const {
 
   813       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
 
   845       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
 
   814     }
 
   846     }
 
   815 
   847 
   816     OutEdgeIt& next(OutEdgeIt& e) const {
 
   848     OutEdgeIt& next(OutEdgeIt& e) const {
 
   817       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
 
   849       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
 
   818       while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 
   850       while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e)))) 
   819 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
 
   851 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
 
   820       return e;
 
   852       return e;
 
   821     }
 
   853     }
 
   822 
   854 
   823     EachNodeIt& getFirst(EachNodeIt& n) const {
 
   855     NodeIt& /*getF*/first(NodeIt& n) const {
 
   824       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
 
   856       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n);
 
   825     }
 
   857     }
 
   826 
   858 
   827     void erase(const EdgeIt& e) {
 
   859     void erase(const Edge& e) {
 
   828       OutEdgeIt f(e);
 
   860       OutEdgeIt f(e);
 
   829       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
 
   861       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
 
   830       while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f)))) 
   862       while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f)))) 
   831 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
 
   863 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
 
   832       first_out_edges.set(this->tail(e), f);
 
   864       first_out_edges.set(this->tail(e), f);
 
   836     //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
 
   868     //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
 
   837 
   869 
   838     //void setGraph(Graph& _graph) { graph = &_graph; }
 
   870     //void setGraph(Graph& _graph) { graph = &_graph; }
 
   839     //Graph& getGraph() const { return (*graph); }
 
   871     //Graph& getGraph() const { return (*graph); }
 
   840     
   872     
   841     //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
 
   873     //template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
 
   842     //template<typename I, typename P> I& getFirst(I& i, const P& p) const { 
   874     //template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const { 
   843     //  return graph->getFirst(i, p); }
 
   875     //  return graph->/*getF*/first(i, p); }
 
   844     
   876     
   845     //template<typename I> I getNext(const I& i) const { 
   877     //template<typename I> I getNext(const I& i) const { 
   846     //  return graph->getNext(i); }
 
   878     //  return graph->getNext(i); }
 
   847     //template<typename I> I& next(I &i) const { return graph->next(i); }    
   879     //template<typename I> I& next(I &i) const { return graph->next(i); }    
   848 
   880 
   849     template< typename It > It first() const { 
   881     template< typename It > It first() const { 
   850       It e; getFirst(e); return e; }
 
   882       It e; /*getF*/first(e); return e; }
 
   851 
   883 
   852     template< typename It > It first(const NodeIt& v) const { 
   884     template< typename It > It first(const Node& v) const { 
   853       It e; getFirst(e, v); return e; }
 
   885       It e; /*getF*/first(e, v); return e; }
 
   854 
   886 
   855     //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
 
   887     //Node head(const Edge& e) const { return graph->head(e); }
 
   856     //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
 
   888     //Node tail(const Edge& e) const { return graph->tail(e); }
 
   857 
   889 
   858     //template<typename I> bool valid(const I& i) const 
   890     //template<typename I> bool valid(const I& i) const 
   859     //  { return graph->valid(i); }
 
   891     //  { return graph->valid(i); }
 
   860   
   892   
   861     //template<typename I> void setInvalid(const I &i);
 
   893     //template<typename I> void setInvalid(const I &i);
 
   862     //{ return graph->setInvalid(i); }
 
   894     //{ return graph->setInvalid(i); }
 
   863 
   895 
   864     //int nodeNum() const { return graph->nodeNum(); }
 
   896     //int nodeNum() const { return graph->nodeNum(); }
 
   865     //int edgeNum() const { return graph->edgeNum(); }
 
   897     //int edgeNum() const { return graph->edgeNum(); }
 
   866   
   898   
   867     //template<typename I> NodeIt aNode(const I& e) const { 
   899     //template<typename I> Node aNode(const I& e) const { 
   868     //  return graph->aNode(e); }
 
   900     //  return graph->aNode(e); }
 
   869     //template<typename I> NodeIt bNode(const I& e) const { 
   901     //template<typename I> Node bNode(const I& e) const { 
   870     //  return graph->bNode(e); }
 
   902     //  return graph->bNode(e); }
 
   871   
   903   
   872     //NodeIt addNode() const { return graph->addNode(); }
 
   904     //Node addNode() const { return graph->addNode(); }
 
   873     //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const { 
   905     //Edge addEdge(const Node& tail, const Node& head) const { 
   874     //  return graph->addEdge(tail, head); }
 
   906     //  return graph->addEdge(tail, head); }
 
   875   
   907   
   876     //template<typename I> void erase(const I& i) const { graph->erase(i); }
 
   908     //template<typename I> void erase(const I& i) const { graph->erase(i); }
 
   877   
   909   
   878     //void clear() const { graph->clear(); }
 
   910     //void clear() const { graph->clear(); }
 
   907 //     Graph* graph;
 
   939 //     Graph* graph;
 
   908   
   940   
   909 //   public:
 
   941 //   public:
 
   910 //     typedef Graph BaseGraph;
 
   942 //     typedef Graph BaseGraph;
 
   911 
   943 
       
   944 //     typedef typename Graph::Node Node;
 
       
   945 //     typedef typename Graph::Edge Edge;
 
       
   946   
   912 //     typedef typename Graph::NodeIt NodeIt;
 
   947 //     typedef typename Graph::NodeIt NodeIt;
 
   913 //     typedef typename Graph::EdgeIt EdgeIt;
 
       
   914   
       
   915 //     typedef typename Graph::EachNodeIt EachNodeIt;
 
       
   916    
   948    
   917 //     class OutEdgeIt {
 
   949 //     class OutEdgeIt {
 
   918 //     public:
 
   950 //     public:
 
   919 //       //Graph::NodeIt n;
 
   951 //       //Graph::Node n;
 
   920 //       bool out_or_in;
 
   952 //       bool out_or_in;
 
   921 //       typename Graph::OutEdgeIt o;
 
   953 //       typename Graph::OutEdgeIt o;
 
   922 //       typename Graph::InEdgeIt i;   
   954 //       typename Graph::InEdgeIt i;   
   923 //     };
 
   955 //     };
 
   924 //     class InEdgeIt {
 
   956 //     class InEdgeIt {
 
   925 //     public:
 
   957 //     public:
 
   926 //       //Graph::NodeIt n;
 
   958 //       //Graph::Node n;
 
   927 //       bool out_or_in;
 
   959 //       bool out_or_in;
 
   928 //       typename Graph::OutEdgeIt o;
 
   960 //       typename Graph::OutEdgeIt o;
 
   929 //       typename Graph::InEdgeIt i;   
   961 //       typename Graph::InEdgeIt i;   
   930 //     };
 
   962 //     };
 
   931 //     typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   963 //     typedef typename Graph::SymEdgeIt SymEdgeIt;
 
   932 //     typedef typename Graph::EachEdgeIt EachEdgeIt;
 
   964 //     typedef typename Graph::EdgeIt EdgeIt;
 
   933 
   965 
   934 //     int nodeNum() const { return graph->nodeNum(); }
 
   966 //     int nodeNum() const { return graph->nodeNum(); }
 
   935 //     int edgeNum() const { return graph->edgeNum(); }
 
   967 //     int edgeNum() const { return graph->edgeNum(); }
 
   936 
   968 
   937 //     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
 
   969 //     Node& /*getF*/first(Node& n) const { return graph->/*getF*/first(n); }
 
   938 
   970 
   939 //     // EachEdge and SymEdge  is missing!!!!
 
   971 //     // Edge and SymEdge  is missing!!!!
 
   940 //     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
 
   972 //     // Edge <-> In/OutEdgeIt conversion is missing!!!!
 
   941 
   973 
   942 //     //FIXME
 
   974 //     //FIXME
 
   943 //     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const 
   975 //     OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const 
   944 //       {
 
   976 //       {
 
   945 // 	e.n=n;
 
   977 // 	e.n=n;
 
   946 // 	graph->getFirst(e.o,n);
 
   978 // 	graph->/*getF*/first(e.o,n);
 
   947 // 	while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
 
   979 // 	while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
 
   948 // 	  graph->goNext(e.o);
 
   980 // 	  graph->goNext(e.o);
 
   949 // 	if(!graph->valid(e.o)) {
 
   981 // 	if(!graph->valid(e.o)) {
 
   950 // 	  graph->getFirst(e.i,n);
 
   982 // 	  graph->/*getF*/first(e.i,n);
 
   951 // 	  while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
 
   983 // 	  while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
 
   952 // 	    graph->goNext(e.i);
 
   984 // 	    graph->goNext(e.i);
 
   953 // 	}
 
   985 // 	}
 
   954 // 	return e;
 
   986 // 	return e;
 
   955 //       }
 
   987 //       }
 
   958 //   {
 
   990 //   {
 
   959 //   if(graph->valid(e.o)) {
 
   991 //   if(graph->valid(e.o)) {
 
   960 //   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
 
   992 //   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
 
   961 //   graph->goNext(e.o);
 
   993 //   graph->goNext(e.o);
 
   962 //   if(graph->valid(e.o)) return e;
 
   994 //   if(graph->valid(e.o)) return e;
 
   963 //   else graph->getFirst(e.i,e.n);
 
   995 //   else graph->/*getF*/first(e.i,e.n);
 
   964 //   }
 
   996 //   }
 
   965 //   else {
 
   997 //   else {
 
   966 //   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
 
   998 //   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
 
   967 //   graph->goNext(e.i);
 
   999 //   graph->goNext(e.i);
 
   968 //   return e;
 
  1000 //   return e;
 
   971 //   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
 
  1003 //   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
 
   972 // */
 
  1004 // */
 
   973 //     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
 
  1005 //     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
 
   974 
  1006 
   975 //     //FIXME
 
  1007 //     //FIXME
 
   976 //     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const 
  1008 //     InEdgeIt& /*getF*/first(InEdgeIt& e, const Node& n) const 
   977 //       {
 
  1009 //       {
 
   978 // 	e.n=n;
 
  1010 // 	e.n=n;
 
   979 // 	graph->getFirst(e.i,n);
 
  1011 // 	graph->/*getF*/first(e.i,n);
 
   980 // 	while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
 
  1012 // 	while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
 
   981 // 	  graph->goNext(e.i);
 
  1013 // 	  graph->goNext(e.i);
 
   982 // 	if(!graph->valid(e.i)) {
 
  1014 // 	if(!graph->valid(e.i)) {
 
   983 // 	  graph->getFirst(e.o,n);
 
  1015 // 	  graph->/*getF*/first(e.o,n);
 
   984 // 	  while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
 
  1016 // 	  while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
 
   985 // 	    graph->goNext(e.o);
 
  1017 // 	    graph->goNext(e.o);
 
   986 // 	}
 
  1018 // 	}
 
   987 // 	return e;
 
  1019 // 	return e;
 
   988 //       }
 
  1020 //       }
 
   991 //   {
 
  1023 //   {
 
   992 //   if(graph->valid(e.i)) {
 
  1024 //   if(graph->valid(e.i)) {
 
   993 //   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
 
  1025 //   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
 
   994 //   graph->goNext(e.i);
 
  1026 //   graph->goNext(e.i);
 
   995 //   if(graph->valid(e.i)) return e;
 
  1027 //   if(graph->valid(e.i)) return e;
 
   996 //   else graph->getFirst(e.o,e.n);
 
  1028 //   else graph->/*getF*/first(e.o,e.n);
 
   997 //   }
 
  1029 //   }
 
   998 //   else {
 
  1030 //   else {
 
   999 //   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
 
  1031 //   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
 
  1000 //   graph->goNext(e.o);
 
  1032 //   graph->goNext(e.o);
 
  1001 //   return e;
 
  1033 //   return e;
 
  1007 
  1039 
  1008 //     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
 
  1040 //     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
 
  1009 //     //template<typename I> I next(const I i); { return graph->goNext(i); }
 
  1041 //     //template<typename I> I next(const I i); { return graph->goNext(i); }
 
  1010 
  1042 
  1011 //     template< typename It > It first() const { 
  1043 //     template< typename It > It first() const { 
  1012 //       It e; getFirst(e); return e; }
 
  1044 //       It e; /*getF*/first(e); return e; }
 
  1013 
  1045 
  1014 //     template< typename It > It first(NodeIt v) const { 
  1046 //     template< typename It > It first(Node v) const { 
  1015 //       It e; getFirst(e, v); return e; }
 
  1047 //       It e; /*getF*/first(e, v); return e; }
 
  1016 
  1048 
  1017 //     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
 
  1049 //     Node head(const Edge& e) const { return graph->head(e); }
 
  1018 //     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
 
  1050 //     Node tail(const Edge& e) const { return graph->tail(e); }
 
  1019   
  1051   
  1020 //     template<typename I> NodeIt aNode(const I& e) const { 
  1052 //     template<typename I> Node aNode(const I& e) const { 
  1021 //       return graph->aNode(e); }
 
  1053 //       return graph->aNode(e); }
 
  1022 //     template<typename I> NodeIt bNode(const I& e) const { 
  1054 //     template<typename I> Node bNode(const I& e) const { 
  1023 //       return graph->bNode(e); }
 
  1055 //       return graph->bNode(e); }
 
  1024   
  1056   
  1025 //     //template<typename I> bool valid(const I i);
 
  1057 //     //template<typename I> bool valid(const I i);
 
  1026 //     //{ return graph->valid(i); }
 
  1058 //     //{ return graph->valid(i); }
 
  1027   
  1059   
  1028 //     //template<typename I> void setInvalid(const I &i);
 
  1060 //     //template<typename I> void setInvalid(const I &i);
 
  1029 //     //{ return graph->setInvalid(i); }
 
  1061 //     //{ return graph->setInvalid(i); }
 
  1030   
  1062   
  1031 //     NodeIt addNode() { return graph->addNode(); }
 
  1063 //     Node addNode() { return graph->addNode(); }
 
  1032 //     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) { 
  1064 //     Edge addEdge(const Node& tail, const Node& head) { 
  1033 //       return graph->addEdge(tail, head); }
 
  1065 //       return graph->addEdge(tail, head); }
 
  1034   
  1066   
  1035 //     template<typename I> void erase(const I& i) { graph->erase(i); }
 
  1067 //     template<typename I> void erase(const I& i) { graph->erase(i); }
 
  1036   
  1068   
  1037 //     void clear() { graph->clear(); }
 
  1069 //     void clear() { graph->clear(); }
lemon-0.x