COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 775:e46a1f0623a0 in lemon-0.x


Ignore:
Timestamp:
08/31/04 13:26:59 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1068
Message:

ResGraphWrapper?<Graph> is done, so does dimacs.h.

Location:
src
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • src/hugo/graph_wrapper.h

    r774 r775  
    348348  };
    349349
     350
     351
    350352  /// A graph wrapper for hiding nodes and edges from a graph.
    351353 
    … …  
    381383
    382384    typedef typename GraphWrapper<Graph>::Node Node;
    383     class NodeIt {
    384       friend class GraphWrapper<Graph>;
     385//     class NodeIt {
     386//       friend class GraphWrapper<Graph>;
     387//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
     388//       typename Graph::NodeIt n;
     389//      public:
     390//       NodeIt() { }
     391//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
     392//       NodeIt(const Invalid& i) : n(i) { }
     393//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
     394//      n(*(_G.graph)) {
     395//      while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
     396//        _G.graph->next(n);
     397//       }
     398//       operator Node() const { return Node(typename Graph::Node(n)); }
     399//     };
     400    class NodeIt : public Node {
     401      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
    385402      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    386       typename Graph::NodeIt n;
    387      public:
     403    public:
    388404      NodeIt() { }
    389       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
    390       NodeIt(const Invalid& i) : n(i) { }
    391       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
    392         n(*(_G.graph)) {
    393         while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
    394           _G.graph->next(n);
    395       }
    396       operator Node() const { return Node(typename Graph::Node(n)); }
     405      //      NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
     406      NodeIt(Invalid i) : Node(i) { }
     407      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
     408        Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
     409      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     410             const Node& n) :
     411        Node(n), gw(&_gw) { }
     412      NodeIt& operator++() {
     413        *(static_cast<Node*>(this))=
     414          ++(typename Graph::NodeIt(*(gw->graph), *this));
     415        while (*static_cast<Node*>(this)!=INVALID &&
     416               !(*(gw->node_filter_map))[*this])
     417          *(static_cast<Node*>(this))=
     418            ++(typename Graph::NodeIt(*(gw->graph), *this));
     419        return *this;
     420      }
    397421    };
    398422    typedef typename GraphWrapper<Graph>::Edge Edge;
    399     class OutEdgeIt {
    400       friend class GraphWrapper<Graph>;
     423    class OutEdgeIt : public Edge {
     424      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
    401425      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    402       typename Graph::OutEdgeIt e;
    403426    public:
    404427      OutEdgeIt() { }
    405       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    406       OutEdgeIt(const Invalid& i) : e(i) { }
    407       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
    408                 const Node& _n) :
    409         e(*(_G.graph), typename Graph::Node(_n)) {
    410         while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
    411           _G.graph->next(e);
    412       }
    413       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    414     };
    415     class InEdgeIt {
    416       friend class GraphWrapper<Graph>;
     428      //      OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
     429      OutEdgeIt(Invalid i) : Edge(i) { }
     430      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
     431        Edge(typename Graph::OutEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
     432      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     433             const Edge& e) :
     434        Edge(e), gw(&_gw) { }
     435      OutEdgeIt& operator++() {
     436        *(static_cast<Edge*>(this))=
     437          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     438        while (*static_cast<Edge*>(this)!=INVALID &&
     439               !(*(gw->edge_filter_map))[*this])
     440          *(static_cast<Edge*>(this))=
     441            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     442        return *this;
     443      }
     444    };
     445    class InEdgeIt : public Edge {
     446      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
    417447      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    418       typename Graph::InEdgeIt e;
    419448    public:
    420449      InEdgeIt() { }
    421       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    422       InEdgeIt(const Invalid& i) : e(i) { }
    423       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
    424                const Node& _n) :
    425         e(*(_G.graph), typename Graph::Node(_n)) {
    426         while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
    427           _G.graph->next(e);
    428       }
    429       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    430     };
    431     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    432     class EdgeIt {
    433       friend class GraphWrapper<Graph>;
     450      //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
     451      InEdgeIt(Invalid i) : Edge(i) { }
     452      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
     453        Edge(typename Graph::InEdgeIt(*(_gw.graph)), n), gw(&_gw) { }
     454      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     455             const Edge& e) :
     456        Edge(e), gw(&_gw) { }
     457      InEdgeIt& operator++() {
     458        *(static_cast<Edge*>(this))=
     459          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     460        while (*static_cast<Edge*>(this)!=INVALID &&
     461               !(*(gw->edge_filter_map))[*this])
     462          *(static_cast<Edge*>(this))=
     463            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     464        return *this;
     465      }
     466    };
     467    class EdgeIt : public Edge {
     468      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
    434469      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    435       typename Graph::EdgeIt e;
    436470    public:
    437471      EdgeIt() { }
    438       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
    439       EdgeIt(const Invalid& i) : e(i) { }
    440       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
    441         e(*(_G.graph)) {
    442         while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
    443           _G.graph->next(e);
    444       }
    445       operator Edge() const { return Edge(typename Graph::Edge(e)); }
     472      //      EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
     473      EdgeIt(Invalid i) : Edge(i) { }
     474      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
     475        Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
     476      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     477             const Edge& e) :
     478        Edge(e), gw(&_gw) { }
     479      EdgeIt& operator++() {
     480        *(static_cast<Edge*>(this))=
     481          ++(typename Graph::EdgeIt(*(gw->graph), *this));
     482        while (*static_cast<Edge*>(this)!=INVALID &&
     483               !(*(gw->edge_filter_map))[*this])
     484          *(static_cast<Edge*>(this))=
     485            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     486        return *this;
     487      }
    446488    };
    447489
    … …  
    459501    }
    460502   
    461     NodeIt& next(NodeIt& i) const {
    462       this->graph->next(i.n);
    463       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
    464         this->graph->next(i.n); }
    465       return i;
    466     }
    467     OutEdgeIt& next(OutEdgeIt& i) const {
    468       this->graph->next(i.e);
    469       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
    470         this->graph->next(i.e); }
    471       return i;
    472     }
    473     InEdgeIt& next(InEdgeIt& i) const {
    474       this->graph->next(i.e);
    475       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
    476         this->graph->next(i.e); }
    477       return i;
    478     }
    479     EdgeIt& next(EdgeIt& i) const {
    480       this->graph->next(i.e);
    481       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
    482         this->graph->next(i.e); }
    483       return i;
    484     }
    485 
    486     Node aNode(const OutEdgeIt& e) const {
    487       return Node(this->graph->aNode(e.e)); }
    488     Node aNode(const InEdgeIt& e) const {
    489       return Node(this->graph->aNode(e.e)); }
    490     Node bNode(const OutEdgeIt& e) const {
    491       return Node(this->graph->bNode(e.e)); }
    492     Node bNode(const InEdgeIt& e) const {
    493       return Node(this->graph->bNode(e.e)); }
     503//     NodeIt& next(NodeIt& i) const {
     504//       this->graph->next(i.n);
     505//       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
     506//      this->graph->next(i.n); }
     507//       return i;
     508//     }
     509//     OutEdgeIt& next(OutEdgeIt& i) const {
     510//       this->graph->next(i.e);
     511//       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
     512//      this->graph->next(i.e); }
     513//       return i;
     514//     }
     515//     InEdgeIt& next(InEdgeIt& i) const {
     516//       this->graph->next(i.e);
     517//       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
     518//      this->graph->next(i.e); }
     519//       return i;
     520//     }
     521//     EdgeIt& next(EdgeIt& i) const {
     522//       this->graph->next(i.e);
     523//       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
     524//      this->graph->next(i.e); }
     525//       return i;
     526//     }
     527
     528//     Node aNode(const OutEdgeIt& e) const {
     529//       return Node(this->graph->aNode(e.e)); }
     530//     Node aNode(const InEdgeIt& e) const {
     531//       return Node(this->graph->aNode(e.e)); }
     532//     Node bNode(const OutEdgeIt& e) const {
     533//       return Node(this->graph->bNode(e.e)); }
     534//     Node bNode(const InEdgeIt& e) const {
     535//       return Node(this->graph->bNode(e.e)); }
    494536
    495537    /// This function hides \c n in the graph, i.e. the iteration
    … …  
    754796          *(static_cast<GraphEdge*>(this))=
    755797            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    756         if (*static_cast<GraphEdge*>(this)==INVALID)
     798        if (*static_cast<GraphEdge*>(this)==INVALID) {
    757799          *static_cast<Edge*>(this)=
    758800            Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
    759         while (*static_cast<GraphEdge*>(this)!=INVALID &&
    760                !(*(gw->backward_filter))[*this])
    761           *(static_cast<GraphEdge*>(this))=
    762             ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     801          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     802                 !(*(gw->backward_filter))[*this])
     803            *(static_cast<GraphEdge*>(this))=
     804              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     805        }
    763806      }
    764807      OutEdgeIt(const SubBidirGraphWrapper<Graph,
    … …  
    774817            *(static_cast<GraphEdge*>(this))=
    775818              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    776           if (*static_cast<GraphEdge*>(this)==INVALID)
     819          if (*static_cast<GraphEdge*>(this)==INVALID) {
    777820            *static_cast<Edge*>(this)=
    778821              Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
    779           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    780                  !(*(gw->backward_filter))[*this])
    781             *(static_cast<GraphEdge*>(this))=
    782               ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     822            while (*static_cast<GraphEdge*>(this)!=INVALID &&
     823                   !(*(gw->backward_filter))[*this])
     824              *(static_cast<GraphEdge*>(this))=
     825                ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     826          }
    783827        } else {
    784828          *(static_cast<GraphEdge*>(this))=
    … …  
    810854          *(static_cast<GraphEdge*>(this))=
    811855            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    812         if (*static_cast<GraphEdge*>(this)==INVALID)
     856        if (*static_cast<GraphEdge*>(this)==INVALID) {
    813857          *static_cast<Edge*>(this)=
    814858            Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
    815         while (*static_cast<GraphEdge*>(this)!=INVALID &&
    816                !(*(gw->backward_filter))[*this])
    817           *(static_cast<GraphEdge*>(this))=
    818             ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     859          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     860                 !(*(gw->backward_filter))[*this])
     861            *(static_cast<GraphEdge*>(this))=
     862              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     863        }
    819864      }
    820865      InEdgeIt(const SubBidirGraphWrapper<Graph,
    … …  
    823868      InEdgeIt& operator++() {
    824869        if (!this->backward) {
    825           Node n=gw->head(*this);
     870          Node n=gw->tail(*this);
    826871          *(static_cast<GraphEdge*>(this))=
    827872            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    … …  
    830875            *(static_cast<GraphEdge*>(this))=
    831876              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    832           if (*static_cast<GraphEdge*>(this)==INVALID)
     877          if (*static_cast<GraphEdge*>(this)==INVALID) {
    833878            *static_cast<Edge*>(this)=
    834879              Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
    835           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    836                  !(*(gw->backward_filter))[*this])
    837             *(static_cast<GraphEdge*>(this))=
    838               ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     880            while (*static_cast<GraphEdge*>(this)!=INVALID &&
     881                   !(*(gw->backward_filter))[*this])
     882              *(static_cast<GraphEdge*>(this))=
     883                ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     884          }
    839885        } else {
    840886          *(static_cast<GraphEdge*>(this))=
    … …  
    860906//the unique invalid iterator
    861907      EdgeIt(const SubBidirGraphWrapper<Graph,
    862                 ForwardFilterMap, BackwardFilterMap>& _gw) :
    863         Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
     908             ForwardFilterMap, BackwardFilterMap>& _gw) :
     909        Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) {
    864910        while (*static_cast<GraphEdge*>(this)!=INVALID &&
    865911               !(*(gw->forward_filter))[*this])
    866912          *(static_cast<GraphEdge*>(this))=
    867913            ++(typename Graph::EdgeIt(*(gw->graph), *this));
    868         if (*static_cast<GraphEdge*>(this)==INVALID)
     914        if (*static_cast<GraphEdge*>(this)==INVALID) {
    869915          *static_cast<Edge*>(this)=
    870916            Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
    871         while (*static_cast<GraphEdge*>(this)!=INVALID &&
    872                !(*(gw->backward_filter))[*this])
    873           *(static_cast<GraphEdge*>(this))=
    874             ++(typename Graph::EdgeIt(*(gw->graph), *this));
     917          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     918                 !(*(gw->backward_filter))[*this])
     919            *(static_cast<GraphEdge*>(this))=
     920              ++(typename Graph::EdgeIt(*(gw->graph), *this));
     921        }
    875922      }
    876923      EdgeIt(const SubBidirGraphWrapper<Graph,
    … …  
    885932            *(static_cast<GraphEdge*>(this))=
    886933              ++(typename Graph::EdgeIt(*(gw->graph), *this));
    887           if (*static_cast<GraphEdge*>(this)==INVALID)
     934          if (*static_cast<GraphEdge*>(this)==INVALID) {
    888935            *static_cast<Edge*>(this)=
    889936              Edge(typename Graph::EdgeIt(*(gw->graph)), true);
    890           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    891                  !(*(gw->backward_filter))[*this])
    892             *(static_cast<GraphEdge*>(this))=
    893               ++(typename Graph::EdgeIt(*(gw->graph), *this));
     937            while (*static_cast<GraphEdge*>(this)!=INVALID &&
     938                   !(*(gw->backward_filter))[*this])
     939              *(static_cast<GraphEdge*>(this))=
     940                ++(typename Graph::EdgeIt(*(gw->graph), *this));
     941          }
    894942        } else {
    895943          *(static_cast<GraphEdge*>(this))=

  • src/work/marci/augmenting_flow.h

    r762 r775  
    10211021      case AFTER_AUGMENTING:
    10221022//      std::cout << "AFTER_AUGMENTING" << std::endl;
    1023         for(g->first(v); g->valid(v); g->next(v)) {
     1023        for(g->first(v); v!=INVALID; ++v) {
    10241024          if (level[v]) {
    10251025            M.set(v, true);
    … …  
    10311031      case AFTER_FAST_AUGMENTING:
    10321032//      std::cout << "AFTER_FAST_AUGMENTING" << std::endl;
    1033         for(g->first(v); g->valid(v); g->next(v)) {
     1033        for(g->first(v); v!=INVALID; ++v) {
    10341034          if (level[v]==number_of_augmentations) {
    10351035            M.set(v, true);
    … …  
    10541054
    10551055        OutEdgeIt e;
    1056         for(g->first(e,w) ; g->valid(e); g->next(e)) {
     1056        for(g->first(e,w) ; e!=INVALID; ++e) {
    10571057          Node v=g->head(e);
    10581058          if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
    … …  
    10631063
    10641064        InEdgeIt f;
    1065         for(g->first(f,w) ; g->valid(f); g->next(f)) {
     1065        for(g->first(f,w) ; f!=INVALID; ++f) {
    10661066          Node v=g->tail(f);
    10671067          if (!M[v] && (*flow)[f] > 0 ) {
    … …  
    11341134    while ( !bfs.finished() ) {
    11351135      ResGWOutEdgeIt e=bfs;
    1136       if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     1136      if (e!=INVALID && bfs.isBNodeNewlyReached()) {
    11371137        Node v=res_graph.tail(e);
    11381138        Node w=res_graph.head(e);
    11391139        pred.set(w, e);
    1140         if (res_graph.valid(pred[v])) {
     1140        if (pred[v]!=INVALID) {
    11411141          free.set(w, std::min(free[v], res_graph.resCap(e)));
    11421142        } else {
    … …  
    11521152      Node n=t;
    11531153      Num augment_value=free[t];
    1154       while (res_graph.valid(pred[n])) {
     1154      while (pred[n]!=INVALID) {
    11551155        ResGWEdge e=pred[n];
    11561156        res_graph.augment(e, augment_value);
    … …  
    11911191    while ( !bfs.finished() ) {
    11921192      ResGWOutEdgeIt e=bfs;
    1193       if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     1193      if (e!=INVALID && bfs.isBNodeNewlyReached()) {
    11941194        Node v=res_graph.tail(e);
    11951195        Node w=res_graph.head(e);
    11961196        pred.set(w, e);
    1197         if (res_graph.valid(pred[v])) {
     1197        if (pred[v]!=INVALID) {
    11981198          free.set(w, std::min(free[v], res_graph.resCap(e)));
    11991199        } else {
    … …  
    12091209      Node n=t;
    12101210      Num augment_value=free[t];
    1211       while (res_graph.valid(pred[n])) {
     1211      while (pred[n]!=INVALID) {
    12121212        ResGWEdge e=pred[n];
    12131213        res_graph.augment(e, augment_value);
    … …  
    12451245    {
    12461246      typename ResGW::NodeIt n;
    1247       for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
     1247      for(res_graph.first(n); n!=INVALID; ++n) {
    12481248        res_graph_to_F.set(n, F.addNode());
    12491249      }
    … …  
    12571257    while ( !bfs.finished() ) {
    12581258      ResGWOutEdgeIt e=bfs;
    1259       if (res_graph.valid(e)) {
     1259      if (e!=INVALID) {
    12601260        if (bfs.isBNodeNewlyReached()) {
    12611261          dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
    … …  
    13001300            typename MG::Node w=F.bNode(dfs);
    13011301            pred.set(w, dfs);
    1302             if (F.valid(pred[v])) {
     1302            if (pred[v]!=INVALID) {
    13031303              free.set(w, std::min(free[v], residual_capacity[dfs]));
    13041304            } else {
    … …  
    13201320        typename MG::Node n=tF;
    13211321        Num augment_value=free[tF];
    1322         while (F.valid(pred[n])) {
     1322        while (pred[n]!=INVALID) {
    13231323          typename MG::Edge e=pred[n];
    13241324          res_graph.augment(original_edge[e], augment_value);
    … …  
    13381338
    13391339
    1340 
    1341 
    13421340  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    13431341  bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
    … …  
    13551353    while ( !bfs.finished() ) {
    13561354      ResGWOutEdgeIt e=bfs;
    1357       if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     1355      if (e!=INVALID && bfs.isBNodeNewlyReached()) {
    13581356        dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
    13591357      }
    … …  
    13721370      first_out_edges(filter_res_graph);
    13731371    typename FilterResGW::NodeIt v;
    1374     for(filter_res_graph.first(v); filter_res_graph.valid(v);
    1375         filter_res_graph.next(v))
     1372    for(filter_res_graph.first(v); v!=INVALID; ++v)
    13761373      {
    13771374        typename FilterResGW::OutEdgeIt e;
    … …  
    14191416
    14201417              pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
    1421               if (erasing_res_graph.valid(pred[v])) {
     1418              if (pred[v]!=INVALID) {
    14221419                free1.set
    14231420                  (w, std::min(free1[v], res_graph.resCap

  • src/work/marci/makefile

    r773 r775  
    55
    66LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    7 BINARIES = graph_wrapper_time max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7
     7BINARIES = graph_wrapper_time max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7 proba8
    88#BINARIES = preflow_bug
    99#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda

  • src/work/marci/max_flow_demo.cc

    r762 r775  
    1717
    1818// Use a DIMACS max flow file as stdin.
    19 // read_dimacs_demo < dimacs_max_flow_file
    20 
    21 
    22 //   struct Ize {
    23 //   };
    24  
    25 //   struct Mize {
    26 //     Ize bumm;
    27 //   };
    28 
    29 //   template <typename B>
    30 //     class Huha {
    31 //     public:
    32 //       int u;
    33 //       B brr;
    34 //     };
    35 
     19// max_flow_demo < dimacs_max_flow_file
    3620
    3721int main(int, char **) {
    … …  
    4428  typedef Graph::Node Node;
    4529  typedef Graph::EdgeIt EdgeIt;
    46 
    47 
    48 //   Mize mize[10];
    49 //   Mize bize[0];
    50 //   Mize zize;
    51 //   typedef Mize Tize[0];
    52 
    53 //   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
    54 //   std::cout << sizeof(bize) << std::endl;
    55 
    56 
    57 //   Huha<Tize> k;
    58 //   std::cout << sizeof(k) << std::endl;
    59 
    60 
    61 //   struct Bumm {
    62 //     //int a;
    63 //     bool b;
    64 //   };
    65 
    66 //   std::cout << sizeof(Bumm) << std::endl;
    67 
    6830
    6931  Graph g;
    … …  
    142104
    143105//   {
    144 //     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     106//     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    145107//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    146108//     ts.reset();
    147109//     int i=0;
    148 //     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
     110//     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
    149111//     std::cout << "elapsed time: " << ts << std::endl;
    150112//     std::cout << "number of augmentation phases: " << i << std::endl;
    151 //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     113//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
     114
     115//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
     116//       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
     117//      std::cout << "Slackness does not hold!" << std::endl;
     118//       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
     119//      std::cout << "Slackness does not hold!" << std::endl;
     120//     }
    152121//   }
    153 
    154   {
    155     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    156     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    157     ts.reset();
    158     int i=0;
    159     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
    160     std::cout << "elapsed time: " << ts << std::endl;
    161     std::cout << "number of augmentation phases: " << i << std::endl;
    162     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
    163 
    164     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
    165       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
    166         std::cout << "Slackness does not hold!" << std::endl;
    167       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
    168         std::cout << "Slackness does not hold!" << std::endl;
    169     }
    170   }
    171122
    172123  {
Note: See TracChangeset for help on using the changeset viewer.