COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 379:a5bff2813c4d in lemon-0.x for src/work


Ignore:
Timestamp:
04/23/04 09:41:48 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@509
Message:

.

Location:
src/work/marci
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/bipartite_graph_wrapper_test.cc

    r368 r379  
    1111#include <bfs_iterator.h>
    1212#include <graph_wrapper.h>
     13#include <maps.h>
     14#include <edmonds_karp.h>
    1315
    1416using namespace hugo;
    … …  
    4244    std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
    4345  }
    44 //   Graph::NodeMap<OutEdgeIt> pred(G);
    45 //   Timer ts;
    46 //   {
    47 //     ts.reset();
    48 //     Graph::NodeMap<bool> reached(G);
    49 //     reached.set(s, true);
    50 //     pred.set(s, INVALID);
    51 //     std::queue<Node> bfs_queue;
    52 //     bfs_queue.push(t);
    53 //     while (!bfs_queue.empty()) {
    54 //       Node v=bfs_queue.front();     
    55 //       bfs_queue.pop();
    56 //       OutEdgeIt e;
    57 //       for(G.first(e,v); G.valid(e); G.next(e)) {
    58 //      Node w=G.head(e);
    59 //      if (!reached[w]) {
    60 //        bfs_queue.push(w);
    61 //        reached.set(w, true);
    62 //        pred.set(w, e);
    63 //      }
    64 //       }
    65 //     }
    6646
    67 //     std::cout << ts << std::endl;
    68 //   }
     47  BGW::NodeMap<int> dbyj(bgw);
     48  BGW::EdgeMap<int> dbyxcj(bgw);
    6949
    70 //   {
    71 //     ts.reset();     
    72 //     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
    73 //     bfs.pushAndSetReached(s);
    74 //     pred.set(s, INVALID);
    75 //     while (!bfs.finished()) {
    76 //       ++bfs;
    77 //       if (G.valid(bfs) && bfs.isBNodeNewlyReached())
    78 //      pred.set(bfs.bNode(), bfs);
    79 //     }
    80 //     std::cout << ts << std::endl;
    81 //   }
     50  typedef stGraphWrapper<BGW> stGW;
     51  stGW stgw(bgw);
     52  ConstMap<stGW::Edge, int> const1map(1);
     53  stGW::NodeMap<int> ize(stgw);
     54  stGW::EdgeMap<int> flow(stgw);
     55
     56  BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
     57  Graph::NodeIt si;
     58  Graph::Node s;
     59  s=g.first(si);
     60  bfs.pushAndSetReached(BGW::Node(s));
     61  while (!bfs.finished()) ++bfs;
     62
     63  BGW::EdgeMap<bool> cap(bgw);
     64  BGW::EdgeMap<bool> flow1(bgw);
     65
     66  typedef ResGraphWrapper< BGW, int, BGW::EdgeMap<bool>, BGW::EdgeMap<bool> >
     67    RBGW;
     68  RBGW rbgw(bgw, cap, flow1);
     69  RBGW::NodeMap<int> u(rbgw);
     70 
     71
     72  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
     73    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
     74  max_flow_test.augmentOnShortestPath();
    8275
    8376  return 0;

  • src/work/marci/graph_wrapper.h

    r376 r379  
    157157    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
    158158
     159    Node tail(const Edge& e) const {
     160      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
    159161    Node head(const Edge& e) const {
    160162      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
    161     Node tail(const Edge& e) const {
    162       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
    163163
    164164    bool valid(const Node& n) const {
    … …  
    222222      friend class GraphWrapper<Graph>;
    223223      friend class RevGraphWrapper<Graph>;
    224       typename Graph::OutEdgeIt e;
     224      typename Graph::InEdgeIt e;
    225225    public:
    226226      OutEdgeIt() { }
    227       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
     227      OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    228228      OutEdgeIt(const Invalid& i) : e(i) { }
    229229      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
    … …  
    234234      friend class GraphWrapper<Graph>;
    235235      friend class RevGraphWrapper<Graph>;
    236       typename Graph::InEdgeIt e;
     236      typename Graph::OutEdgeIt e;
    237237    public:
    238238      InEdgeIt() { }
    239       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
     239      InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
    240240      InEdgeIt(const Invalid& i) : e(i) { }
    241241      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
    … …  
    260260    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    261261    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     262
     263    Node tail(const Edge& e) const {
     264      return GraphWrapper<Graph>::head(e); }
     265    Node head(const Edge& e) const {
     266      return GraphWrapper<Graph>::tail(e); }
     267
    262268  };
    263269
    … …  
    884890   
    885891  public:
     892    static const bool S_CLASS=false;
     893    static const bool T_CLASS=true;
     894   
    886895    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
    887896      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
    … …  
    891900    typedef typename GraphWrapper<Graph>::Edge Edge;
    892901    //using GraphWrapper<Graph>::EdgeIt;
    893     class SNodeIt {
     902    class ClassNodeIt {
    894903      Node n;
    895904    public:
    896       SNodeIt() { }
    897       SNodeIt(const Invalid& i) : n(i) { }
    898       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
    899         _G.s_false_t_true_map->first(n, false);
     905      ClassNodeIt() { }
     906      ClassNodeIt(const Invalid& i) : n(i) { }
     907      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
     908        _G.s_false_t_true_map->first(n, _class);
    900909      }
    901910      operator Node() const { return n; }
    902911    };
    903     class TNodeIt {
    904       Node n;
    905     public:
    906       TNodeIt() { }
    907       TNodeIt(const Invalid& i) : n(i) { }
    908       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
    909         _G.s_false_t_true_map->first(n, true);
    910       }
    911       operator Node() const { return n; }
    912     };
     912//     class SNodeIt {
     913//       Node n;
     914//     public:
     915//       SNodeIt() { }
     916//       SNodeIt(const Invalid& i) : n(i) { }
     917//       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
     918//      _G.s_false_t_true_map->first(n, false);
     919//       }
     920//       operator Node() const { return n; }
     921//     };
     922//     class TNodeIt {
     923//       Node n;
     924//     public:
     925//       TNodeIt() { }
     926//       TNodeIt(const Invalid& i) : n(i) { }
     927//       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
     928//      _G.s_false_t_true_map->first(n, true);
     929//       }
     930//       operator Node() const { return n; }
     931//     };
    913932    class OutEdgeIt {
    914933    public:
     934
    915935      typename Graph::OutEdgeIt e;
    916936    public:
    … …  
    919939      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
    920940        if (!(*(_G.s_false_t_true_map))[_n])
    921           e=OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
     941          e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
    922942        else
    923943          e=INVALID;
    … …  
    933953      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
    934954        if ((*(_G.s_false_t_true_map))[_n])
    935           e=InEdgeIt(*(_G.graph), typename Graph::Node(_n));
     955          e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
    936956        else
    937957          e=INVALID;
    … …  
    941961
    942962    using GraphWrapper<Graph>::first;
    943     SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
    944     TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
     963    ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
     964      n=SNodeIt(*this, _class) ; return n; }
     965//    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
     966//    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
     967    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     968      i=OutEdgeIt(*this, p); return i;
     969    }
     970    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     971      i=InEdgeIt(*this, p); return i;
     972    }
    945973
    946974    using GraphWrapper<Graph>::next;
    947     SNodeIt& next(SNodeIt& n) const {
     975    ClassNodeIt& next(ClassNodeIt& n) const {
    948976      this->s_false_t_true_map->next(n); return n;
    949977    }
    950     TNodeIt& next(TNodeIt& n) const {
    951       this->s_false_t_true_map->next(n); return n;
    952     }
     978//     SNodeIt& next(SNodeIt& n) const {
     979//       this->s_false_t_true_map->next(n); return n;
     980//     }
     981//     TNodeIt& next(TNodeIt& n) const {
     982//       this->s_false_t_true_map->next(n); return n;
     983//     }
     984    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
     985    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
    953986
    954987    Node tail(const Edge& e) {
    … …  
    9771010      return Node(this->graph->bNode(e.e));
    9781011    }
     1012
     1013    bool inSClass(const Node& n) const {
     1014      return !(this->s_false_t_true_map[n]);
     1015    }
     1016    bool inTClass(const Node& n) const {
     1017      return (this->s_false_t_true_map[n]);
     1018    }
    9791019  };
    9801020
    9811021
    982 
    983 //   /// experimentral, do not try it.
    984 //   template<typename Graph>
    985 //   class stGraphWrapper : public GraphWrapper<Graph> {
    986 //   public:
    987 //     class Node;
    988 //     class NodeIt;
    989 //     class Edge;
    990 //     class OutEdgeIt;
    991 //     class InEdgeIt;
    992 //     class EdgeIt;
    993 
    994 //     const Node s;
    995 //     const Node t;
    996 
    997 //     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph),
    998 //                                  s(INVALID, 1), t(INVALID, 2) { }
    999 
    1000 //     class Node : public Graph::Node {
    1001 //       friend class GraphWrapper<Graph>;
    1002 //       friend class stGraphWrapper<Graph>;
    1003 //     protected:
    1004 //       int spec; //0 if real node, 1 iff s, 2 iff t
    1005 //     public:
    1006 //       Node() { }
    1007 //       Node(const typename Graph::Node& _n, int _spec=0) :
    1008 //      Graph::Node(_n), spec(_spec) { }
    1009 //       Node(const Invalid& i) : Graph::Node(i), spec(2) { }
    1010 //       //invalid: (invalid, 2);
    1011 //     };
    1012 
    1013 //     class NodeIt {
    1014 //       friend class GraphWrapper<Graph>;
    1015 //       friend class stGraphWrapper<Graph>;
    1016 //       typename Graph::NodeIt n;
    1017 //       int spec;
    1018 //      public:
    1019 //       NodeIt() { }
    1020 //       NodeIt(const typename Graph::NodeIt& _n, int _spec=0) :
    1021 //      n(_n), spec(_spec) { }
    1022 //       NodeIt(const Invalid& i) : n(i), spec(2) { }
    1023 //       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
    1024 //      if (!_G->valid(n)) spec=1;
    1025 //       }
    1026 //       operator Node() const { return Node(n, spec); }
    1027 //     };
    1028 // //    typedef typename Graph::Edge Edge;
    1029 //     class Edge : public Graph::Edge {
    1030 //       friend class GraphWrapper<Graph>;
    1031 //       friend class stGraphWrapper<Graph>;
    1032 //       Node tail_spec;
    1033 //       Node head_spec;
    1034 //     public:
    1035 //       Edge() { }
    1036 //       Edge(const typename Graph::Edge& _e) :
    1037 //      Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) {
    1038 //      //a tail-t es a head-et real node-ra csinaljuk
    1039 //       }
    1040 //       Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { }
    1041 //     };
    1042 //     class OutEdgeIt {
    1043 //       friend class GraphWrapper<Graph>;
    1044 //       friend class stGraphWrapper<Graph>;
    1045 //       typename Graph::OutEdgeIt e;
    1046 //       Node tail_spec;
    1047 //       Node head_spec;
    1048 //     public:
    1049 //       OutEdgeIt() { }
    1050 //       OutEdgeIt(const typename Graph::OutEdgeIt& _e) :
    1051 //      e(_e), tail_spec(i, 0), head_spec(i, 0) {
    1052 //      //a tail-t es a head-et real node-ra csinaljuk
    1053 //       }
    1054 //       OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { }
    1055 //       //invalid: (barmi, 0, 2)
    1056 //       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
    1057 //      switch (_n.spec) {
    1058 //      case 0 :
    1059 //        e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
    1060 //        _tail.spec=0;
    1061 //        _head.spec=0;
    1062 //        if (!_G.graph->valid(e)) spec=1;
    1063 //        break;
    1064 //      case 1:
    1065 //        e=INVALID;
    1066 //        _tail.spec=1;
    1067 //        _head(_G.graph->first(typename Graph::NodeIt()));
    1068 //        if _head.spec==1
    1069 //        break;
    1070 //      };
    1071        
    1072 //        }
    1073 //       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    1074 //     };
    1075 //     class InEdgeIt {
    1076 //       friend class GraphWrapper<Graph>;
    1077 //       typename Graph::InEdgeIt e;
    1078 //     public:
    1079 //       InEdgeIt() { }
    1080 //       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    1081 //       InEdgeIt(const Invalid& i) : e(i) { }
    1082 //       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
    1083 //      e(*(_G.graph), typename Graph::Node(_n)) { }
    1084 //       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    1085 //     };
    1086 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    1087 //     class EdgeIt {
    1088 //       friend class GraphWrapper<Graph>;
    1089 //       typename Graph::EdgeIt e;
    1090 //     public:
    1091 //       EdgeIt() { }
    1092 //       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
    1093 //       EdgeIt(const Invalid& i) : e(i) { }
    1094 //       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
    1095 //       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    1096 //     };
     1022  /// experimentral, do not try it.
     1023  /// It eats a bipartite graph, oriented from S to T.
     1024  /// Such one can be made e.g. by the above wrapper.
     1025  template<typename Graph>
     1026  class stGraphWrapper : public GraphWrapper<Graph> {
     1027  public:
     1028    class Node;
     1029//GN, int
     1030//0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
     1031//es a vege a false azaz (invalid, 3)   
     1032    class NodeIt;
     1033//GNI, int
     1034    class Edge;
     1035//GE, int, GN
     1036//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
     1037//invalid: (invalid, 3, invalid)
     1038    class OutEdgeIt;
     1039//GO, int, GNI
     1040//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
     1041//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
     1042//t-bol (invalid, 3, invalid)
     1043    class InEdgeIt;
     1044//GI, int, GNI
     1045//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
     1046//s-be (invalid, 3, invalid)
     1047//t-be (invalid, 2, first), ... (invalid, 3, invalid)
     1048    class EdgeIt;
     1049//(first, 0, invalid) ...
     1050//(invalid, 1, vmi)
     1051//(invalid, 2, vmi)
     1052//invalid, 3, invalid)
     1053    template <typename T> class NodeMap;
     1054    template <typename T> class EdgeMap;
     1055
     1056//    template <typename T> friend class NodeMap;
     1057//    template <typename T> friend class EdgeMap;
     1058
     1059    const Node S_NODE;
     1060    const Node T_NODE;
     1061
     1062    static const bool S_CLASS=false;
     1063    static const bool T_CLASS=true;
     1064
     1065    stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
     1066                                    S_NODE(INVALID, 1),
     1067                                    T_NODE(INVALID, 2) { }
     1068
     1069    class Node : public Graph::Node {
     1070    protected:
     1071      friend class GraphWrapper<Graph>;
     1072      friend class stGraphWrapper<Graph>;
     1073      template <typename T> friend class stGraphWrapper<Graph>::NodeMap;
     1074      int spec;
     1075    public:
     1076      Node() { }
     1077      Node(const typename Graph::Node& _n, int _spec=0) :
     1078        Graph::Node(_n), spec(_spec) { }
     1079      Node(const Invalid& i) : Graph::Node(i), spec(3) { }
     1080      friend bool operator==(const Node& u, const Node& v) {
     1081        return (u.spec==v.spec &&
     1082                static_cast<typename Graph::Node>(u)==
     1083                static_cast<typename Graph::Node>(v));
     1084      }
     1085      friend bool operator!=(const Node& u, const Node& v) {
     1086        return (v.spec!=u.spec ||
     1087                static_cast<typename Graph::Node>(u)!=
     1088                static_cast<typename Graph::Node>(v));
     1089      }
     1090      int getSpec() const { return spec; }
     1091    };
     1092    class NodeIt {
     1093      friend class GraphWrapper<Graph>;
     1094      friend class stGraphWrapper<Graph>;
     1095      typename Graph::NodeIt n;
     1096      int spec;
     1097     public:
     1098      NodeIt() { }
     1099      NodeIt(const typename Graph::NodeIt& _n, int _spec) :
     1100        n(_n), spec(_spec) { }
     1101      NodeIt(const Invalid& i) : n(i), spec(3) { }
     1102      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
     1103        if (!_G->valid(n)) spec=1;
     1104      }
     1105      operator Node() const { return Node(n, spec); }
     1106    };
     1107    class Edge : public Graph::Edge {
     1108      friend class GraphWrapper<Graph>;
     1109      friend class stGraphWrapper<Graph>;
     1110      template <typename T> friend class stGraphWrapper<Graph>::EdgeMap;
     1111      int spec;
     1112      typename Graph::Node n;
     1113    public:
     1114      Edge() { }
     1115      Edge(const typename Graph::Edge& _e, int _spec,
     1116           const typename Graph::Node& _n) :
     1117        Graph::Edge(_e), spec(_spec), n(_n) {
     1118      }
     1119      Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
     1120      friend bool operator==(const Edge& u, const Edge& v) {
     1121        return (u.spec==v.spec &&
     1122                static_cast<typename Graph::Edge>(u)==
     1123                static_cast<typename Graph::Edge>(v) &&
     1124                u.n==v.n);
     1125      }
     1126      friend bool operator!=(const Edge& u, const Edge& v) {
     1127        return (v.spec!=u.spec ||
     1128                static_cast<typename Graph::Edge>(u)!=
     1129                static_cast<typename Graph::Edge>(v) ||
     1130                u.n!=v.n);
     1131      }
     1132      int getSpec() const { return spec; }
     1133    };
     1134    class OutEdgeIt {
     1135      friend class GraphWrapper<Graph>;
     1136      friend class stGraphWrapper<Graph>;
     1137      typename Graph::OutEdgeIt e;
     1138      int spec;
     1139      typename Graph::ClassNodeIt n;
     1140    public:
     1141      OutEdgeIt() { }
     1142      OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
     1143                const typename Graph::ClassNodeIt& _n) :
     1144        e(_e), spec(_spec), n(_n) {
     1145      }
     1146      OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
     1147      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
     1148        switch (_n.spec) {
     1149          case 0 :
     1150            if (_G.graph->inSClass) { //S, van normalis kiel
     1151              e=typename Graph::OutEdgeIt(*(_G.graph),
     1152                                          typename Graph::Node(_n));
     1153              spec=0;
     1154              n=INVALID;
     1155              if (!_G.graph->valid(e)) spec=3;
     1156            } else { //T, specko kiel van
     1157              e=INVALID;
     1158              spec=2;
     1159              n=_n;
     1160            }
     1161            break;
     1162          case 1:
     1163            e=INVALID;
     1164            spec=1;
     1165            _G.graph->first(n, S_CLASS); //s->vmi;
     1166            if (!_G.graph->valid(n)) spec=3; //Ha S ures
     1167            break;
     1168          case 2:
     1169            e=INVALID;
     1170            spec=3;
     1171            n=INVALID;
     1172            break;
     1173        }
     1174      }
     1175      operator Edge() const { return Edge(e, spec, n); }
     1176    };
     1177    class InEdgeIt {
     1178      friend class GraphWrapper<Graph>;
     1179      friend class stGraphWrapper<Graph>;
     1180      typename Graph::InEdgeIt e;
     1181      int spec;
     1182      typename Graph::ClassNodeIt n;
     1183    public:
     1184      InEdgeIt() { }
     1185      InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
     1186               const typename Graph::ClassNodeIt& _n) :
     1187        e(_e), spec(_spec), n(_n) {
     1188      }
     1189      InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
     1190      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
     1191        switch (_n.spec) {
     1192          case 0 :
     1193            if (_G.graph->inTClass) { //T, van normalis beel
     1194              e=typename Graph::InEdgeIt(*(_G.graph),
     1195                                         typename Graph::Node(_n));
     1196              spec=0;
     1197              n=INVALID;
     1198              if (!_G.graph->valid(e)) spec=3;
     1199            } else { //S, specko beel van
     1200              e=INVALID;
     1201              spec=1;
     1202              n=_n;
     1203            }
     1204            break;
     1205          case 1:
     1206            e=INVALID;
     1207            spec=3;
     1208            n=INVALID;
     1209          case 2:
     1210            e=INVALID;
     1211            spec=1;
     1212            _G.graph->first(n, T_CLASS); //vmi->t;
     1213            if (!_G.graph->valid(n)) spec=3; //Ha T ures
     1214            break;
     1215        }
     1216      }
     1217      operator Edge() const { return Edge(e, spec, n); }
     1218    };
     1219    class EdgeIt {
     1220      friend class GraphWrapper<Graph>;
     1221      friend class stGraphWrapper<Graph>;
     1222      typename Graph::EdgeIt e;
     1223      int spec;
     1224      typename Graph::ClassNodeIt n;
     1225    public:
     1226      EdgeIt() { }
     1227      EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
     1228             const typename Graph::ClassNodeIt& _n) :
     1229        e(_e), spec(_spec), n(_n) { }
     1230      EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
     1231      EdgeIt(const GraphWrapper<Graph>& _G) :
     1232        e(*(_G.graph)), spec(0), n(INVALID) {
     1233        if (!_G.graph->valid(e)) {
     1234          spec=1;
     1235          _G.graph->first(n, S_CLASS);
     1236          if (!_G.graph->valid(n)) { //Ha S ures
     1237            spec=2;
     1238            _G.graph->first(n, T_CLASS);
     1239            if (!_G.graph->valid(n)) { //Ha T ures
     1240              spec=3;
     1241            }
     1242          }
     1243        }
     1244      }
     1245      operator Edge() const { return Edge(e, spec, n); }
     1246    };
    10971247   
    1098 //     NodeIt& first(NodeIt& i) const {
    1099 //       i=NodeIt(*this); return i;
    1100 //     }
    1101 //     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    1102 //       i=OutEdgeIt(*this, p); return i;
    1103 //     }
    1104 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    1105 //       i=InEdgeIt(*this, p); return i;
    1106 //     }
    1107 //     EdgeIt& first(EdgeIt& i) const {
    1108 //       i=EdgeIt(*this); return i;
    1109 //     }
    1110 
    1111 //     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    1112 //     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
    1113 //     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
    1114 //     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
    1115 
    1116 //     Node head(const Edge& e) const {
    1117 //       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
    1118 //     Node tail(const Edge& e) const {
    1119 //       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
    1120 
    1121 //     bool valid(const Node& n) const {
    1122 //       return graph->valid(static_cast<typename Graph::Node>(n)); }
    1123 //     bool valid(const Edge& e) const {
    1124 //       return graph->valid(static_cast<typename Graph::Edge>(e)); }
    1125 
    1126 //     int nodeNum() const { return graph->nodeNum(); }
    1127 //     int edgeNum() const { return graph->edgeNum(); }
     1248    NodeIt& first(NodeIt& i) const {
     1249      i=NodeIt(*this); return i;
     1250    }
     1251    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     1252      i=OutEdgeIt(*this, p); return i;
     1253    }
     1254    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     1255      i=InEdgeIt(*this, p); return i;
     1256    }
     1257    EdgeIt& first(EdgeIt& i) const {
     1258      i=EdgeIt(*this); return i;
     1259    }
     1260
     1261    NodeIt& next(NodeIt& i) const {
     1262      switch (i.spec) {
     1263        case 0:
     1264          graph->next(i.n);
     1265          if (!graph->valid(i.n)) {
     1266            i.spec=1;
     1267          }
     1268          break;
     1269        case 1:
     1270          i.spec=2;
     1271          break;
     1272        case 2:
     1273          i.spec=3;
     1274          break;
     1275      }
     1276      return i;
     1277    }
     1278    OutEdgeIt& next(OutEdgeIt& i) const {
     1279      switch (i.spec) {
     1280        case 0: //normal edge
     1281          typename Graph::Node v=graph->aNode(i.e);
     1282          graph->next(i.e);
     1283          if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
     1284            if (graph->inSClass(v)) { //S, nincs kiel
     1285              i.spec=3;
     1286              i.n=INVALID;
     1287            } else { //T, van kiel
     1288              i.spec=2;
     1289              i.n=v;
     1290            }
     1291          }
     1292          break;
     1293        case 1: //s->vmi
     1294          graph->next(i.n);
     1295          if (!graph->valid(i.n)) i.spec=3;
     1296          break;
     1297        case 2: //vmi->t
     1298          i.spec=3;
     1299          i.n=INVALID;
     1300          break;
     1301      }
     1302      return i;
     1303    }
     1304    InEdgeIt& next(InEdgeIt& i) const {
     1305      switch (i.spec) {
     1306        case 0: //normal edge
     1307          typename Graph::Node v=graph->aNode(i.e);
     1308          graph->next(i.e);
     1309          if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
     1310            if (graph->inTClass(v)) { //S, nincs beel
     1311              i.spec=3;
     1312              i.n=INVALID;
     1313            } else { //S, van beel
     1314              i.spec=1;
     1315              i.n=v;
     1316            }
     1317          }
     1318          break;
     1319        case 1: //s->vmi
     1320          i.spec=3;
     1321          i.n=INVALID;
     1322          break;
     1323        case 2: //vmi->t
     1324          graph->next(i.n);
     1325          if (!graph->valid(i.n)) i.spec=3;
     1326          break;
     1327      }
     1328      return i;
     1329    }
     1330
     1331    EdgeIt& next(EdgeIt& i) const {
     1332      switch (i.spec) {
     1333        case 0:
     1334          graph->next(i.e);
     1335          if (!graph->valid(i.e)) {
     1336            i.spec=1;
     1337            graph->first(n, S_CLASS);
     1338            if (!graph->valid(i.n)) {
     1339              i.spec=2;
     1340              graph->first(n, T_CLASS);
     1341              if (!graph->valid(i.n)) spec=3;
     1342            }
     1343          }
     1344          break;
     1345        case 1:
     1346          graph->next(i.n);
     1347          if (!graph->valid(i.n)) {
     1348            i.spec=2;
     1349            graph->first(n, T_CLASS);
     1350            if (!graph->valid(i.n)) spec=3;
     1351          }
     1352          break;
     1353        case 2:
     1354          graph->next(i.n);
     1355          if (!graph->valid(i.n)) i.spec=3;
     1356          break;
     1357      }
     1358      return i;
     1359    }   
     1360
     1361    Node tail(const Edge& e) const {
     1362      switch (e.spec) {
     1363        case 0:
     1364          return Node(graph->tail(e));
     1365          break;
     1366        case 1:
     1367          return S_NODE;
     1368          break;
     1369        case 2:
     1370          return Node(e.n);
     1371          break;
     1372      }
     1373    }
     1374    Node head(const Edge& e) const {
     1375      switch (e.spec) {
     1376        case 0:
     1377          return Node(graph->head(e));
     1378          break;
     1379        case 1:
     1380          return Node(e.n);
     1381          break;
     1382        case 2:
     1383          return T_NODE;
     1384          break;
     1385      }
     1386    }
     1387
     1388    bool valid(const Node& n) const { return (n.spec<3); }
     1389    bool valid(const Edge& e) const { return (e.spec<3); }
     1390
     1391//    int nodeNum() const { return graph->nodeNum(); }
     1392//    int edgeNum() const { return graph->edgeNum(); }
    11281393 
    1129 //     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    1130 //     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    1131 //     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    1132 //     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
     1394    Node aNode(const OutEdgeIt& e) const { return tail(e); }
     1395    Node aNode(const InEdgeIt& e) const { return head(e); }
     1396    Node bNode(const OutEdgeIt& e) const { return head(e); }
     1397    Node bNode(const InEdgeIt& e) const { return tail(e); }
    11331398 
    1134 //     Node addNode() const { return Node(graph->addNode()); }
    1135 //     Edge addEdge(const Node& tail, const Node& head) const {
    1136 //       return Edge(graph->addEdge(tail, head)); }
    1137 
    1138 //     void erase(const Node& i) const { graph->erase(i); }
    1139 //     void erase(const Edge& i) const { graph->erase(i); }
     1399//    Node addNode() const { return Node(graph->addNode()); }
     1400//    Edge addEdge(const Node& tail, const Node& head) const {
     1401//      return Edge(graph->addEdge(tail, head)); }
     1402
     1403//    void erase(const Node& i) const { graph->erase(i); }
     1404//    void erase(const Edge& i) const { graph->erase(i); }
    11401405 
    1141 //     void clear() const { graph->clear(); }
     1406//    void clear() const { graph->clear(); }
    11421407   
    1143 //     template<typename T> class NodeMap : public Graph::NodeMap<T> {
    1144 //     public:
    1145 //       NodeMap(const GraphWrapper<Graph>& _G) : 
    1146 //      Graph::NodeMap<T>(*(_G.graph)) { }
    1147 //       NodeMap(const GraphWrapper<Graph>& _G, T a) :
    1148 //      Graph::NodeMap<T>(*(_G.graph), a) { }
    1149 //     };
    1150 
    1151 //     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
    1152 //     public:
    1153 //       EdgeMap(const GraphWrapper<Graph>& _G) : 
    1154 //      Graph::EdgeMap<T>(*(_G.graph)) { }
    1155 //       EdgeMap(const GraphWrapper<Graph>& _G, T a) :
    1156 //      Graph::EdgeMap<T>(*(_G.graph), a) { }
    1157 //     };
    1158 //   };
     1408    template<typename T> class NodeMap : public GraphWrapper<Graph>::NodeMap<T> {
     1409      T s_value, t_value;
     1410    public:
     1411      NodeMap(const stGraphWrapper<Graph>& _G) : 
     1412        GraphWrapper<Graph>::NodeMap<T>(_G) { }
     1413      NodeMap(const stGraphWrapper<Graph>& _G, T a) :
     1414        GraphWrapper<Graph>::NodeMap<T>(_G, a), s_value(a), t_value(a) { }
     1415      T operator[](const Node& n) const {
     1416        switch (n.spec) {
     1417          case 0:
     1418            return (*this)[n];
     1419            break;
     1420          case 1:
     1421            return s_value;
     1422            break;
     1423          case 2:
     1424            return t_value;
     1425            break;
     1426        }
     1427      }
     1428      void set(const Node& n, T t) {
     1429        switch (n.spec) {
     1430          case 0:
     1431            GraphWrapper<Graph>::NodeMap<T>::set(n, t);
     1432            break;
     1433          case 1:
     1434            s_value=t;
     1435            break;
     1436          case 2:
     1437            t_value=t;
     1438            break;
     1439        }
     1440      }
     1441    };
     1442
     1443    template<typename T> class EdgeMap : public GraphWrapper<Graph>::EdgeMap<T> {
     1444      typename GraphWrapper<Graph>::NodeMap<T> node_value;
     1445    public:
     1446      EdgeMap(const stGraphWrapper<Graph>& _G) : 
     1447        GraphWrapper<Graph>::EdgeMap<T>(_G), node_value(_G) { }
     1448      EdgeMap(const stGraphWrapper<Graph>& _G, T a) :
     1449        GraphWrapper<Graph>::EdgeMap<T>(_G, a), node_value(_G, a) { }
     1450      T operator[](const Edge& e) const {
     1451        switch (e.spec) {
     1452          case 0:
     1453            return (*this)[e];
     1454            break;
     1455          case 1:
     1456            return node_value[e.n];
     1457            break;
     1458          case 2:
     1459            return node_value[e.n];
     1460            break;
     1461        }
     1462      }
     1463      void set(const Edge& e, T t) {
     1464        switch (e.spec) {
     1465          case 0:
     1466            GraphWrapper<Graph>::set(e, t);
     1467            break;
     1468          case 1:
     1469            node_value.set(e, t);
     1470            break;
     1471          case 2:
     1472            node_value.set(e, t);
     1473            break;
     1474        }
     1475      }
     1476    };
     1477  };
     1478
    11591479
    11601480} //namespace hugo

  • src/work/marci/lg_vs_sg.cc

    r334 r379  
    3636    Graph::EdgeMap<int> flow(G); //0 flow
    3737    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    38       pre_flow_test(G, s, t, cap, flow);
     38      pre_flow_test(G, s, t, cap, flow, true);
    3939    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    4040      max_flow_test(G, s, t, cap, flow);
    … …  
    110110    Graph::EdgeMap<int> flow(G); //0 flow
    111111    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    112       pre_flow_test(G, s, t, cap, flow);
     112      pre_flow_test(G, s, t, cap, flow, true);
    113113    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    114114      max_flow_test(G, s, t, cap, flow);
Note: See TracChangeset for help on using the changeset viewer.