COIN-OR::LEMON - Graph Library

Changeset 174:44700ed9ffaa in lemon-0.x for src/work


Ignore:
Timestamp:
03/12/04 10:19:54 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@250
Message:

towards on ListGraph?, SmartGraph? compatibility

Location:
src/work
Files:
5 added
7 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/emptygraph.h

    r165 r174  
    1 // -*-mode: c++; -*-
     1// -*- c++ -*-
     2#ifndef EMPTYGRAPH_H
     3#define EMPTYGRAPH_H
    24
    35#include <invalid.h>
     
    3537      Node() {}   //FIXME
    3638      /// Initialize the iterator to be invalid
    37       Node(Invalid) {};
     39      Node(Invalid) {}
    3840      //Node(const Node &) {}
    3941      bool operator==(Node n) const { return true; } //FIXME
     
    4850      NodeIt() {} //FIXME
    4951      /// Initialize the iterator to be invalid
    50       NodeIt(Invalid) {};
     52      NodeIt(Invalid) {}
    5153      /// Sets the iterator to the first node of \c G.
    5254      NodeIt(const EmptyGraph &G) {}
     
    6264      Edge() {}   //FIXME
    6365      /// Initialize the iterator to be invalid
    64       Edge(Invalid) {};
     66      Edge(Invalid) {}
    6567      //Edge(const Edge &) {}
    6668      bool operator==(Edge n) const { return true; } //FIXME
     
    7678      OutEdgeIt() {}
    7779      /// Initialize the iterator to be invalid
    78       OutEdgeIt(Invalid) {};
     80      OutEdgeIt(Invalid) {}
    7981      /// This constructor sets the iterator to first outgoing edge.
    8082   
     
    9294      InEdgeIt() {}
    9395      /// Initialize the iterator to be invalid
    94       InEdgeIt(Invalid) {};
     96      InEdgeIt(Invalid) {}
    9597      InEdgeIt(const EmptyGraph &, Node) {}   
    9698    };
     
    102104      EdgeIt() {}
    103105      /// Initialize the iterator to be invalid
    104       EdgeIt(Invalid) {};
     106      EdgeIt(Invalid) {}
    105107      EdgeIt(const EmptyGraph &) {}
    106108    };
     
    150152
    151153    /// Checks if a node iterator is valid
    152     bool valid(const Node) const { return true;};
     154    bool valid(const Node) const { return true;}
    153155    /// Checks if an edge iterator is valid
    154     bool valid(const Edge) const { return true;};
     156    bool valid(const Edge) const { return true;}
    155157
    156158    ///Gives back the \e id of a node.
    157     int id(const Node) const { return 0;};
     159    int id(const Node) const { return 0;}
    158160    ///Gives back the \e id of an edge.
    159     int id(const Edge) const { return 0;};
     161    int id(const Edge) const { return 0;}
    160162
    161163    //void setInvalid(Node &) const {};
     
    173175    int edgeNum() { return 0;}
    174176
    175     EmptyGraph() {};
    176     EmptyGraph(const EmptyGraph &G) {};
     177    EmptyGraph() {}
     178    EmptyGraph(const EmptyGraph &G) {}
    177179 
    178180 
     
    218220  // @}
    219221
    220 };
     222} //namespace hugo
    221223
    222224
     
    237239
    238240// }
     241
     242#endif // EMPTYGRAPH_H
  • src/work/alpar/smart_graph.h

    r164 r174  
    9797    Node head(Edge e) const { return edges[e.n].head; }
    9898
    99 //     Node aNode(const OutEdgeIt& e) const { return tail(e); }
    100 //     Node aNode(const InEdgeIt& e) const { return head(e); }
     99    // Marci
     100    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
     101    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
    101102//     //Node aNode(const SymEdge& e) const { return e.aNode(); }
    102103
    103 //     Node bNode(const OutEdgeIt& e) const { return head(e); }
    104 //     Node bNode(const InEdgeIt& e) const { return tail(e); }
     104    // Marci
     105    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
     106    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
    105107//     //Node bNode(const SymEdge& e) const { return e.bNode(); }
    106108
     
    117119    It first() const {
    118120      It e;
    119       getFirst(e);
     121      //Marci
     122      /*getF*/first(e);
    120123      return e;
    121124    }
     
    124127    It first(Node v) const {
    125128      It e;
    126       getFirst(e, v);
     129      //Marci
     130      /*getF*/first(e, v);
    127131      return e;
    128132    }
     
    139143    //{ It tmp; tmp.n=it.n+1; return tmp; }
    140144
    141     Node& next(Node& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
     145    //FIXME correction Marci: I changed to NodeIt from Node
     146    //NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
     147    NodeIt& next(NodeIt& it) const {
     148      it.n=(it.n+2)%(nodes.size()+1)-1;
     149      return it;
     150    }
    142151    OutEdgeIt& next(OutEdgeIt& it) const
    143152    { it.n=edges[it.n].next_out; return it; }
     
    217226    public:
    218227      Edge() { }
    219       Edge (Invalid i) { n=-1; }
     228      // Marci: kiszedtem az Invalid i-bol az i-t
     229      Edge (Invalid) { n=-1; }
    220230      bool operator==(const Edge i) const {return n==i.n;}
    221231      bool operator!=(const Edge i) const {return n!=i.n;}
  • src/work/iterator_bfs_demo.cc

    r158 r174  
     1// -*- c++ -*-
    12#include <iostream>
    23#include <vector>
    34#include <string>
    45
    5 #include <list_graph.hh>
    6 #include <bfs_iterator.hh>
     6#include <list_graph.h>
     7#include <smart_graph.h>
     8#include <bfs_iterator.h>
    79#include <graph_wrapper.h>
    810
     
    1921  EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
    2022    graph(_graph), node_name_map(_node_name_map) { }
    21   string get(typename Graph::EdgeIt e) const {
     23  string get(typename Graph::Edge e) const {
    2224    return
    2325      (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
     
    2729int main (int, char*[])
    2830{
    29   typedef ListGraph::NodeIt NodeIt;
    30   typedef ListGraph::EdgeIt EdgeIt;
    31   //typedef ListGraph::EachNodeIt EachNodeIt;
    32   //typedef ListGraph::EachEdgeIt EachEdgeIt;
    33   //typedef ListGraph::OutEdgeIt OutEdgeIt;
    34   //typedef ListGraph::InEdgeIt InEdgeIt;
    35   //typedef ListGraph::SymEdgeIt SymEdgeIt;
     31  //typedef SmartGraph Graph;
     32  typedef ListGraph Graph;
     33
     34  typedef Graph::Node Node;
     35  typedef Graph::Edge Edge;
     36  //typedef Graph::NodeIt NodeIt;
     37  //typedef Graph::EdgeIt EdgeIt;
     38  //typedef Graph::OutEdgeIt OutEdgeIt;
     39  //typedef Graph::InEdgeIt InEdgeIt;
     40  //typedef Graph::SymEdgeIt SymEdgeIt;
    3641 
    37   ListGraph G;
    38 
    39   NodeIt s=G.addNode();
    40   NodeIt v1=G.addNode();
    41   NodeIt v2=G.addNode();
    42   NodeIt v3=G.addNode();
    43   NodeIt v4=G.addNode();
    44   NodeIt t=G.addNode();
     42  Graph G;
     43
     44  Node s=G.addNode();
     45  Node v1=G.addNode();
     46  Node v2=G.addNode();
     47  Node v3=G.addNode();
     48  Node v4=G.addNode();
     49  Node t=G.addNode();
    4550 
    46   ListGraph::NodeMap<string> node_name(G);
     51  Graph::NodeMap<string> node_name(G);
    4752  node_name.set(s, "s");
    4853  node_name.set(v1, "v1");
     
    7378  cout << "    \\-->    ------------->         "<< endl;
    7479 
    75 /*
    76   {
    77   cout << "iterator bfs demo 4 ..." << endl;
    78   BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
    79   bfs.pushAndSetReached(s);
    80   while (!bfs.finished()) {
    81   if (OutEdgeIt(bfs).valid()) {
    82   cout << "OutEdgeIt: " << bfs;
    83   cout << " aNode: " << G.aNode(bfs);
    84   cout << " bNode: " << G.bNode(bfs) << " ";
    85   } else {
    86   cout << "OutEdgeIt: " << "invalid";
    87   cout << " aNode: " << bfs.aNode();
    88   cout << " bNode: " << "invalid" << " ";
    89   }
    90   if (bfs.isBNodeNewlyReached()) {
    91   cout << "bNodeIsNewlyReached ";
    92   } else {
    93   cout << "bNodeIsNotNewlyReached ";
    94   }
    95   if (bfs.isANodeExamined()) {
    96   cout << "aNodeIsExamined ";
    97   } else {
    98   cout << "aNodeIsNotExamined ";
    99   }
    100   cout << endl;
    101   ++bfs;
    102   }
    103   }
    104 
    105   {
    106   cout << "iterator dfs demo 4 ..." << endl;
    107   DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
    108   dfs.pushAndSetReached(s);
    109   while (!dfs.finished()) {
    110   ++dfs;
    111   if (OutEdgeIt(dfs).valid()) {
    112   cout << "OutEdgeIt: " << dfs;
    113   cout << " aNode: " << G.aNode(dfs);
    114   cout << " bNode: " << G.bNode(dfs) << " ";
    115   } else {
    116   cout << "OutEdgeIt: " << "invalid";
    117   cout << " aNode: " << dfs.aNode();
    118   cout << " bNode: " << "invalid" << " ";
    119   }
    120   if (dfs.isBNodeNewlyReached()) {
    121   cout << "bNodeIsNewlyReached ";
    122   } else {
    123   cout << "bNodeIsNotNewlyReached ";
    124   }
    125   if (dfs.isANodeExamined()) {
    126   cout << "aNodeIsExamined ";
    127   } else {
    128   cout << "aNodeIsNotExamined ";
    129   }
    130   cout << endl;
    131   //++dfs;
    132   }
    133   }
    134 */
    135 
    136 //   typedef TrivGraphWrapper<const ListGraph> CGW;
     80//   typedef TrivGraphWrapper<const Graph> CGW;
    13781//   CGW wG(G);
    13882
    13983//   cout << "bfs and dfs demo on the directed graph" << endl;
    140 //   for(CGW::EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) {
     84//   for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) {
    14185//     cout << n << ": ";
    14286//     cout << "out edges: ";
     
    15094
    15195  {
    152     typedef TrivGraphWrapper<const ListGraph> GW;
     96    typedef TrivGraphWrapper<const Graph> GW;
    15397    GW wG(G);
    15498
    155     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
     99    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
    156100   
    157101    cout << "bfs and dfs iterator demo on the directed graph" << endl;
    158     for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {
     102    for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
    159103      cout << node_name.get(n) << ": ";
    160104      cout << "out edges: ";
     
    226170
    227171  {
    228     typedef RevGraphWrapper<const ListGraph> GW;
     172    typedef RevGraphWrapper<const Graph> GW;
    229173    GW wG(G);
    230174   
    231     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
     175    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
    232176   
    233177    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
    234     for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {
     178    for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
    235179      cout << node_name.get(n) << ": ";
    236180      cout << "out edges: ";
     
    301245
    302246  {
    303     typedef UndirGraphWrapper<const ListGraph> GW;
     247    typedef UndirGraphWrapper<const Graph> GW;
    304248    GW wG(G);
    305249   
    306     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
     250    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
    307251   
    308252    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
    309     for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {
     253    for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
    310254      cout << node_name.get(n) << ": ";
    311255      cout << "out edges: ";
  • src/work/jacint/preflow.h

    r113 r174  
    527527
    528528  };
    529 }//namespace marci
    530 #endif
    531 
    532 
    533 
    534 
     529
     530} //namespace hugo
     531
     532#endif //PREFLOW_H
     533
     534
     535
     536
  • src/work/marci/edmonds_karp_demo.cc

    r168 r174  
     1// -*- c++ -*-
    12#include <iostream>
    23#include <fstream>
    34
    4 #include <list_graph.hh>
    5 #include <dimacs.hh>
    6 #include <edmonds_karp.hh>
     5#include <list_graph.h>
     6#include <smart_graph.h>
     7#include <dimacs.h>
     8#include <edmonds_karp.h>
    79#include <time_measure.h>
    810#include <graph_wrapper.h>
     
    1315// read_dimacs_demo < dimacs_max_flow_file
    1416
    15 /*
    16   struct Ize {
    17   };
     17
     18//   struct Ize {
     19//   };
    1820 
    19   struct Mize {
    20     Ize bumm;
    21   };
     21//   struct Mize {
     22//     Ize bumm;
     23//   };
    2224
    23   template <typename B>
    24     class Huha {
    25     public:
    26       int u;
    27       B brr;
    28     };
    29 */
     25//   template <typename B>
     26//     class Huha {
     27//     public:
     28//       int u;
     29//       B brr;
     30//     };
     31
    3032
    3133int main(int, char **) {
    32   typedef ListGraph::NodeIt NodeIt;
    33   typedef ListGraph::EachEdgeIt EachEdgeIt;
    3434
    35 /*
    36   Mize mize[10];
    37   Mize bize[0];
    38   Mize zize;
    39   typedef Mize Tize[0];
     35  typedef ListGraph MutableGraph;
    4036
    41   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
    42   std::cout << sizeof(bize) << std::endl;
     37  typedef SmartGraph Graph;
     38  typedef Graph::Node Node;
     39  typedef Graph::EdgeIt EdgeIt;
    4340
    4441
    45   Huha<Tize> k;
    46   std::cout << sizeof(k) << std::endl;
     42//   Mize mize[10];
     43//   Mize bize[0];
     44//   Mize zize;
     45//   typedef Mize Tize[0];
     46
     47//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
     48//   std::cout << sizeof(bize) << std::endl;
    4749
    4850
    49   struct Bumm {
    50     //int a;
    51     bool b;
    52   };
     51//   Huha<Tize> k;
     52//   std::cout << sizeof(k) << std::endl;
    5353
    54   std::cout << sizeof(Bumm) << std::endl;
    55 */
    5654
    57   ListGraph G;
    58   NodeIt s, t;
    59   ListGraph::EdgeMap<int> cap(G);
     55//   struct Bumm {
     56//     //int a;
     57//     bool b;
     58//   };
     59
     60//   std::cout << sizeof(Bumm) << std::endl;
     61
     62
     63  Graph G;
     64  Node s, t;
     65  Graph::EdgeMap<int> cap(G);
    6066  readDimacsMaxFlow(std::cin, G, s, t, cap);
    61 /*
    62   typedef TrivGraphWrapper<ListGraph> TGW;
    63   TGW gw(G);
    64   TGW::EachNodeIt sw;
    65   gw.getFirst(sw);
    66   std::cout << "p1:" << gw.nodeNum() << std::endl;
    67   gw.erase(sw);
    68   std::cout << "p2:" << gw.nodeNum() << std::endl;
    6967
    70   typedef const ListGraph cLG;
    71   typedef TrivGraphWrapper<const cLG> CTGW;
    72   CTGW cgw(G);
    73   CTGW::EachNodeIt csw;
    74   cgw.getFirst(csw);
    75   std::cout << "p1:" << cgw.nodeNum() << std::endl;
    76   //cgw.erase(csw);
    77   std::cout << "p2:" << cgw.nodeNum() << std::endl;
    78 */
     68//   typedef TrivGraphWrapper<Graph> TGW;
     69//   TGW gw(G);
     70//   TGW::NodeIt sw;
     71//   gw./*getF*/first(sw);
     72//   std::cout << "p1:" << gw.nodeNum() << std::endl;
     73//   gw.erase(sw);
     74//   std::cout << "p2:" << gw.nodeNum() << std::endl;
     75
     76//   typedef const Graph cLG;
     77//   typedef TrivGraphWrapper<const cLG> CTGW;
     78//   CTGW cgw(G);
     79//   CTGW::NodeIt csw;
     80//   cgw./*getF*/first(csw);
     81//   std::cout << "p1:" << cgw.nodeNum() << std::endl;
     82//   //cgw.erase(csw);
     83//   std::cout << "p2:" << cgw.nodeNum() << std::endl;
     84
    7985
    8086  {
    81   std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
    82   ListGraph::EdgeMap<int> flow(G); //0 flow
     87    std::cout << "SmartGraph..." << std::endl;
     88    std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
     89    Graph::EdgeMap<int> flow(G); //0 flow
    8390
    84   Timer ts;
    85   ts.reset();
    86   //double pre_time=currTime();
    87   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    88   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
    89   int i=0;
    90   while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) {
    91 //     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
     91    Timer ts;
     92    ts.reset();
     93
     94    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     95    //max_flow_test.augmentWithBlockingFlow<Graph>();
     96    int i=0;
     97    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
     98//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    9299//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    93100//     }
    94101//     std::cout<<std::endl;
    95     ++i;
    96   }
    97   //double post_time=currTime();
     102      ++i;
     103    }
    98104
    99   //std::cout << "maximum flow: "<< std::endl;
    100   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    101   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    102   //}
    103   //std::cout<<std::endl;
    104   std::cout << "elapsed time: " << ts << std::endl;
    105   std::cout << "number of augmentation phases: " << i << std::endl;
    106   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     105//   std::cout << "maximum flow: "<< std::endl;
     106//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     107//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     108//   }
     109//   std::cout<<std::endl;
     110    std::cout << "elapsed time: " << ts << std::endl;
     111    std::cout << "number of augmentation phases: " << i << std::endl;
     112    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    107113  }
    108114
    109115  {
    110   std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
    111   ListGraph::EdgeMap<int> flow(G); //0 flow
     116    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
     117    Graph::EdgeMap<int> flow(G); //0 flow
    112118
    113   Timer ts;
    114   ts.reset();
    115   //double pre_time=currTime();
    116   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    117   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
    118   int i=0;
    119   while (max_flow_test.augmentOnBlockingFlow2()) {
    120 //     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
     119    Timer ts;
     120    ts.reset();
     121
     122    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     123    //max_flow_test.augmentWithBlockingFlow<Graph>();
     124    int i=0;
     125    while (max_flow_test.augmentOnBlockingFlow2()) {
     126//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    121127//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    122128//     }
    123129//     std::cout<<std::endl;
    124     ++i;
    125   }
    126   //double post_time=currTime();
     130      ++i;
     131    }
    127132
    128   //std::cout << "maximum flow: "<< std::endl;
    129   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    130   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    131   //}
    132   //std::cout<<std::endl;
    133   std::cout << "elapsed time: " << ts << std::endl;
    134   std::cout << "number of augmentation phases: " << i << std::endl;
    135   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     133//   std::cout << "maximum flow: "<< std::endl;
     134//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     135//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     136//   }
     137//   std::cout<<std::endl;
     138    std::cout << "elapsed time: " << ts << std::endl;
     139    std::cout << "number of augmentation phases: " << i << std::endl;
     140    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    136141  }
    137142
    138143  {
    139   std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl;
    140   ListGraph::EdgeMap<int> flow(G); //0 flow
     144    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
     145    Graph::EdgeMap<int> flow(G); //0 flow
    141146
    142   Timer ts;
    143   ts.reset();
    144   //double pre_time=currTime();
    145   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    146   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
    147   int i=0;
    148   while (max_flow_test.augmentOnShortestPath()) {
    149 //     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
     147    Timer ts;
     148    ts.reset();
     149
     150    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     151    //max_flow_test.augmentWithBlockingFlow<Graph>();
     152    int i=0;
     153    while (max_flow_test.augmentOnShortestPath()) {
     154//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    150155//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    151156//     }
    152157//     std::cout<<std::endl;
    153     ++i;
     158      ++i;
     159    }
     160
     161//   std::cout << "maximum flow: "<< std::endl;
     162//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     163//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     164//   }
     165//   std::cout<<std::endl;
     166    std::cout << "elapsed time: " << ts << std::endl;
     167    std::cout << "number of augmentation phases: " << i << std::endl;
     168    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    154169  }
    155   //double post_time=currTime();
    156170
    157   //std::cout << "maximum flow: "<< std::endl;
    158   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    159   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    160   //}
    161   //std::cout<<std::endl;
    162   std::cout << "elapsed time: " << ts << std::endl;
    163   std::cout << "number of augmentation phases: " << i << std::endl;
    164   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    165   }
    166171
    167172  return 0;
  • src/work/marci/graph_wrapper.h

    r168 r174  
    1 // -*-mode: c++; -*-
     1// -*- c++ -*-
    22#ifndef GRAPH_WRAPPER_H
    33#define GRAPH_WRAPPER_H
     4
     5#include <invalid.h>
    46
    57namespace hugo {
     
    1214    typedef Graph BaseGraph;
    1315
     16    typedef typename Graph::Node Node;
    1417    typedef typename Graph::NodeIt NodeIt;
    15     typedef typename Graph::EachNodeIt EachNodeIt;
    16 
    17     typedef typename Graph::EdgeIt EdgeIt;
     18
     19    typedef typename Graph::Edge Edge;
    1820    typedef typename Graph::OutEdgeIt OutEdgeIt;
    1921    typedef typename Graph::InEdgeIt InEdgeIt;
    2022    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    21     typedef typename Graph::EachEdgeIt EachEdgeIt;
     23    typedef typename Graph::EdgeIt EdgeIt;
    2224
    2325    //TrivGraphWrapper() : graph(0) { }
     
    2729    Graph& getGraph() const { return (*graph); }
    2830   
    29     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    30     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    31       return graph->getFirst(i, p); }
     31    template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
     32    template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
     33      return graph->/*getF*/first(i, p); }
    3234   
    3335    template<typename I> I getNext(const I& i) const {
     
    3638
    3739    template< typename It > It first() const {
    38       It e; getFirst(e); return e; }
    39 
    40     template< typename It > It first(const NodeIt& v) const {
    41       It e; getFirst(e, v); return e; }
    42 
    43     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    44     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     40      It e; /*getF*/first(e); return e; }
     41
     42    template< typename It > It first(const Node& v) const {
     43      It e; /*getF*/first(e, v); return e; }
     44
     45    Node head(const Edge& e) const { return graph->head(e); }
     46    Node tail(const Edge& e) const { return graph->tail(e); }
    4547
    4648    template<typename I> bool valid(const I& i) const
     
    5355    int edgeNum() const { return graph->edgeNum(); }
    5456 
    55     template<typename I> NodeIt aNode(const I& e) const {
     57    template<typename I> Node aNode(const I& e) const {
    5658      return graph->aNode(e); }
    57     template<typename I> NodeIt bNode(const I& e) const {
     59    template<typename I> Node bNode(const I& e) const {
    5860      return graph->bNode(e); }
    5961 
    60     NodeIt addNode() const { return graph->addNode(); }
    61     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
     62    Node addNode() const { return graph->addNode(); }
     63    Edge addEdge(const Node& tail, const Node& head) const {
    6264      return graph->addEdge(tail, head); }
    6365 
     
    9193    typedef Graph BaseGraph;
    9294
    93     typedef typename Graph::NodeIt NodeIt;   
    94     typedef typename Graph::EachNodeIt EachNodeIt;
    95  
    96     typedef typename Graph::EdgeIt EdgeIt;
     95    typedef typename Graph::Node Node;   
     96    typedef typename Graph::NodeIt NodeIt;
     97 
     98    typedef typename Graph::Edge Edge;
    9799    typedef typename Graph::OutEdgeIt InEdgeIt;
    98100    typedef typename Graph::InEdgeIt OutEdgeIt;
    99101    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    100     typedef typename Graph::EachEdgeIt EachEdgeIt;
     102    typedef typename Graph::EdgeIt EdgeIt;
    101103
    102104    //RevGraphWrapper() : graph(0) { }
     
    106108    Graph& getGraph() const { return (*graph); }
    107109   
    108     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    109     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    110       return graph->getFirst(i, p); }
     110    template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
     111    template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
     112      return graph->/*getF*/first(i, p); }
    111113
    112114    template<typename I> I getNext(const I& i) const {
     
    115117
    116118    template< typename It > It first() const {
    117       It e; getFirst(e); return e; }
    118 
    119     template< typename It > It first(const NodeIt& v) const {
    120       It e; getFirst(e, v); return e; }
    121 
    122     NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
    123     NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
     119      It e; /*getF*/first(e); return e; }
     120
     121    template< typename It > It first(const Node& v) const {
     122      It e; /*getF*/first(e, v); return e; }
     123
     124    Node head(const Edge& e) const { return graph->tail(e); }
     125    Node tail(const Edge& e) const { return graph->head(e); }
    124126 
    125127    template<typename I> bool valid(const I& i) const
     
    129131    //{ return graph->setInvalid(i); }
    130132 
    131     template<typename I> NodeIt aNode(const I& e) const {
     133    template<typename I> Node aNode(const I& e) const {
    132134      return graph->aNode(e); }
    133     template<typename I> NodeIt bNode(const I& e) const {
     135    template<typename I> Node bNode(const I& e) const {
    134136      return graph->bNode(e); }
    135137
    136     NodeIt addNode() const { return graph->addNode(); }
    137     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
     138    Node addNode() const { return graph->addNode(); }
     139    Edge addEdge(const Node& tail, const Node& head) const {
    138140      return graph->addEdge(tail, head); }
    139141 
     
    170172    typedef Graph BaseGraph;
    171173
     174    typedef typename Graph::Node Node;
    172175    typedef typename Graph::NodeIt NodeIt;
    173     typedef typename Graph::EachNodeIt EachNodeIt;
    174 
    175     //typedef typename Graph::EdgeIt EdgeIt;
     176
     177    //typedef typename Graph::Edge Edge;
    176178    //typedef typename Graph::OutEdgeIt OutEdgeIt;
    177179    //typedef typename Graph::InEdgeIt InEdgeIt;
    178180    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    179     //typedef typename Graph::EachEdgeIt EachEdgeIt;
     181    //typedef typename Graph::EdgeIt EdgeIt;
    180182
    181183    //private:
    182     typedef typename Graph::EdgeIt GraphEdgeIt;
     184    typedef typename Graph::Edge GraphEdge;
    183185    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
    184186    typedef typename Graph::InEdgeIt GraphInEdgeIt;
     
    191193    Graph& getGraph() const { return (*graph); }
    192194 
    193     class EdgeIt {
     195    class Edge {
    194196      friend class UndirGraphWrapper<Graph>;
    195197      bool out_or_in; //true iff out
     
    197199      GraphInEdgeIt in;
    198200    public:
    199       EdgeIt() : out_or_in(true), out(), in() { }
    200       operator GraphEdgeIt() const {
     201      Edge() : out_or_in(), out(), in() { }
     202      Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
     203      operator GraphEdge() const {
    201204        if (out_or_in) return(out); else return(in);
    202205      }
    203     };
    204 
    205     class OutEdgeIt : public EdgeIt {
     206      friend bool operator==(const Edge& u, const Edge& v) {
     207        if (v.out_or_in)
     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 {
    206221      friend class UndirGraphWrapper<Graph>;
    207222    public:
    208       OutEdgeIt() : EdgeIt() { }
    209       OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() {
    210         _G.graph->getFirst(out, n);
     223      OutEdgeIt() : Edge() { }
     224      OutEdgeIt(const Invalid& i) : Edge(i) { }
     225      OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() {
     226        out_or_in=true;
     227        _G.graph->/*getF*/first(out, n);
    211228        if (!(_G.graph->valid(out))) {
    212229          out_or_in=false;
    213           _G.graph->getFirst(in, n);
     230          _G.graph->/*getF*/first(in, n);
    214231        }
    215232      }
    216233    };
    217234
    218     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
     235    OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
    219236      e.out_or_in=true;
    220       graph->getFirst(e.out, n);
     237      graph->/*getF*/first(e.out, n);
    221238      if (!(graph->valid(e.out))) {
    222239        e.out_or_in=false;
    223         graph->getFirst(e.in, n);
     240        graph->/*getF*/first(e.in, n);
    224241      }
    225242      return e;
     
    228245    OutEdgeIt& next(OutEdgeIt& e) const {
    229246      if (e.out_or_in) {
    230         NodeIt n=graph->tail(e.out);
     247        Node n=graph->tail(e.out);
    231248        graph->next(e.out);
    232249        if (!graph->valid(e.out)) {
    233250          e.out_or_in=false;
    234           graph->getFirst(e.in, n);
     251          graph->/*getF*/first(e.in, n);
    235252        }
    236253      } else {
     
    240257    }
    241258
    242     NodeIt aNode(const OutEdgeIt& e) const {
     259    Node aNode(const OutEdgeIt& e) const {
    243260      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 {
    245262      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
    246263
    247264    typedef OutEdgeIt InEdgeIt;
    248265
    249     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    250 //     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    251 //       return graph->getFirst(i, p); }
     266    template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
     267//     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
     268//       return graph->/*getF*/first(i, p); }
    252269   
    253270    template<typename I> I getNext(const I& i) const {
     
    256273
    257274    template< typename It > It first() const {
    258       It e; getFirst(e); return e; }
    259 
    260     template< typename It > It first(const NodeIt& v) const {
    261       It e; getFirst(e, v); return e; }
    262 
    263     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    264     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     275      It e; /*getF*/first(e); return e; }
     276
     277    template< typename It > It first(const Node& v) const {
     278      It e; /*getF*/first(e, v); return e; }
     279
     280    Node head(const Edge& e) const { return graph->head(e); }
     281    Node tail(const Edge& e) const { return graph->tail(e); }
    265282
    266283    template<typename I> bool valid(const I& i) const
     
    273290    int edgeNum() const { return graph->edgeNum(); }
    274291 
    275 //     template<typename I> NodeIt aNode(const I& e) const {
     292//     template<typename I> Node aNode(const I& e) const {
    276293//       return graph->aNode(e); }
    277 //     template<typename I> NodeIt bNode(const I& e) const {
     294//     template<typename I> Node bNode(const I& e) const {
    278295//       return graph->bNode(e); }
    279296 
    280     NodeIt addNode() const { return graph->addNode(); }
    281     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
     297    Node addNode() const { return graph->addNode(); }
     298    Edge addEdge(const Node& tail, const Node& head) const {
    282299      return graph->addEdge(tail, head); }
    283300 
     
    313330//     typedef Graph BaseGraph;
    314331
     332//     typedef typename Graph::Node Node;
     333//     typedef typename Graph::Edge Edge;
     334 
    315335//     typedef typename Graph::NodeIt NodeIt;
    316 //     typedef typename Graph::EdgeIt EdgeIt;
    317  
    318 //     typedef typename Graph::EachNodeIt EachNodeIt;
    319336   
    320337//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
     
    324341//     //typedef typename Graph::InEdgeIt SymEdgeIt;
    325342//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    326 //     typedef typename Graph::EachEdgeIt EachEdgeIt;
     343//     typedef typename Graph::EdgeIt EdgeIt;
    327344
    328345//     int nodeNum() const { return graph->nodeNum(); }
    329346//     int edgeNum() const { return graph->edgeNum(); }
    330347   
    331 //     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    332 //     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    333 //       return graph->getFirst(i, p); }
     348//     template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
     349//     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
     350//       return graph->/*getF*/first(i, p); }
    334351//     //template<typename I> I next(const I i); { return graph->goNext(i); }
    335352//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    336353
    337354//     template< typename It > It first() const {
    338 //       It e; getFirst(e); return e; }
    339 
    340 //     template< typename It > It first(NodeIt v) const {
    341 //       It e; getFirst(e, v); return e; }
    342 
    343 //     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    344 //     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
    345  
    346 //     template<typename I> NodeIt aNode(const I& e) const {
     355//       It e; /*getF*/first(e); return e; }
     356
     357//     template< typename It > It first(Node v) const {
     358//       It e; /*getF*/first(e, v); return e; }
     359
     360//     Node head(const Edge& e) const { return graph->head(e); }
     361//     Node tail(const Edge& e) const { return graph->tail(e); }
     362 
     363//     template<typename I> Node aNode(const I& e) const {
    347364//       return graph->aNode(e); }
    348 //     template<typename I> NodeIt bNode(const I& e) const {
     365//     template<typename I> Node bNode(const I& e) const {
    349366//       return graph->bNode(e); }
    350367 
     
    355372//     //{ return graph->setInvalid(i); }
    356373 
    357 //     NodeIt addNode() { return graph->addNode(); }
    358 //     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
     374//     Node addNode() { return graph->addNode(); }
     375//     Edge addEdge(const Node& tail, const Node& head) {
    359376//       return graph->addEdge(tail, head); }
    360377 
     
    378395  public:
    379396    typedef Graph BaseGraph;
     397    typedef typename Graph::Node Node;
    380398    typedef typename Graph::NodeIt NodeIt;
    381     typedef typename Graph::EachNodeIt EachNodeIt;
    382399  private:
    383400    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
    384401    typedef typename Graph::InEdgeIt OldInEdgeIt;
    385     const Graph* G;
     402    const Graph* graph;
    386403    FlowMap* flow;
    387404    const CapacityMap* capacity;
     
    390407    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
    391408             const CapacityMap& _capacity) :
    392       G(&_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) { }
     409      graph(&_G), flow(&_flow), capacity(&_capacity) { }
    395410
    396411    void setGraph(const Graph& _graph) { graph = &_graph; }
    397     const Graph& getGraph() const { return (*G); }
    398 
    399     class EdgeIt;
     412    const Graph& getGraph() const { return (*graph); }
     413
     414    class Edge;
    400415    class OutEdgeIt;
    401     friend class EdgeIt;
     416    friend class Edge;
    402417    friend class OutEdgeIt;
    403418
    404     class EdgeIt {
     419    class Edge {
    405420      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    406421    protected:
     
    409424      OldInEdgeIt in;
    410425    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) { }
    412428//       bool valid() const {
    413429//      return out_or_in && out.valid() || in.valid(); }
    414     };
    415 
    416 
    417     class OutEdgeIt : public EdgeIt {
     430      friend bool operator==(const Edge& u, const Edge& v) {
     431        if (v.out_or_in)
     432          return (u.out_or_in && u.out==v.out);
     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 {
    418446      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    419447    public:
    420448      OutEdgeIt() { }
    421449      //FIXME
    422       OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { }
     450      OutEdgeIt(const Edge& e) : Edge(e) { }
     451      OutEdgeIt(const Invalid& i) : Edge(i) { }
    423452    private:
    424       OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() {
    425         resG.G->getFirst(out, v);
    426         while( out.valid() && !(resG.free(out)>0) ) { ++out; }
    427         if (!out.valid()) {
     453      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
     454        resG.graph->/*getF*/first(out, v);
     455        while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
     456        if (!resG.graph->valid(out)) {
    428457          out_or_in=0;
    429           resG.G->getFirst(in, v);
    430           while( in.valid() && !(resG.free(in)>0) ) { ++in; }
     458          resG.graph->/*getF*/first(in, v);
     459          while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
    431460        }
    432461      }
     
    434463//       OutEdgeIt& operator++() {
    435464//      if (out_or_in) {
    436 //        NodeIt v=/*resG->*/G->aNode(out);
     465//        Node v=/*resG->*/G->aNode(out);
    437466//        ++out;
    438 //        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     467//        while( out.valid() && !(Edge::free()>0) ) { ++out; }
    439468//        if (!out.valid()) {
    440469//          out_or_in=0;
    441 //          G->getFirst(in, v);
    442 //          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     470//          G->/*getF*/first(in, v);
     471//          while( in.valid() && !(Edge::free()>0) ) { ++in; }
    443472//        }
    444473//      } else {
    445474//        ++in;
    446 //        while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     475//        while( in.valid() && !(Edge::free()>0) ) { ++in; }
    447476//      }
    448477//      return *this;
     
    450479    };
    451480
    452     class EachEdgeIt : public EdgeIt {
     481    class EdgeIt : public Edge {
    453482      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    454       typename Graph::EachNodeIt v;
    455     public:
    456       EachEdgeIt() { }
    457       //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
    458       EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() {
    459         resG.G->getFirst(v);
    460         if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt();
    461         while (out.valid() && !(resG.free(out)>0) ) { ++out; }
    462         while (v.valid() && !out.valid()) {
    463           ++v;
    464           if (v.valid()) resG.G->getFirst(out, v);
    465           while (out.valid() && !(resG.free(out)>0) ) { ++out; }
     483      typename Graph::NodeIt v;
     484    public:
     485      EdgeIt() { }
     486      //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
     487      EdgeIt(const Invalid& i) : Edge(i) { }
     488      EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
     489        resG.graph->/*getF*/first(v);
     490        if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); else out=OldOutEdgeIt(INVALID);
     491        while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
     492        while (resG.graph->valid(v) && !resG.graph->valid(out)) {
     493          resG.graph->next(v);
     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); }
    466496        }
    467         if (!out.valid()) {
     497        if (!resG.graph->valid(out)) {
    468498          out_or_in=0;
    469           resG.G->getFirst(v);
    470           if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();
    471           while (in.valid() && !(resG.free(in)>0) ) { ++in; }
    472           while (v.valid() && !in.valid()) {
    473             ++v;
    474             if (v.valid()) resG.G->getFirst(in, v);
    475             while (in.valid() && !(resG.free(in)>0) ) { ++in; }
     499          resG.graph->/*getF*/first(v);
     500          if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); else in=OldInEdgeIt(INVALID);
     501          while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
     502          while (resG.graph->valid(v) && !resG.graph->valid(in)) {
     503            resG.graph->next(v);
     504            if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v);
     505            while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
    476506          }
    477507        }
    478508      }
    479 //       EachEdgeIt& operator++() {
     509//       EdgeIt& operator++() {
    480510//      if (out_or_in) {
    481511//        ++out;
    482 //        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     512//        while (out.valid() && !(Edge::free()>0) ) { ++out; }
    483513//        while (v.valid() && !out.valid()) {
    484514//          ++v;
    485 //          if (v.valid()) G->getFirst(out, v);
    486 //          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     515//          if (v.valid()) G->/*getF*/first(out, v);
     516//          while (out.valid() && !(Edge::free()>0) ) { ++out; }
    487517//        }
    488518//        if (!out.valid()) {
    489519//          out_or_in=0;
    490 //          G->getFirst(v);
    491 //          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
    492 //          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     520//          G->/*getF*/first(v);
     521//          if (v.valid()) G->/*getF*/first(in, v); else in=OldInEdgeIt();
     522//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
    493523//          while (v.valid() && !in.valid()) {
    494524//            ++v;
    495 //            if (v.valid()) G->getFirst(in, v);
    496 //            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     525//            if (v.valid()) G->/*getF*/first(in, v);
     526//            while (in.valid() && !(Edge::free()>0) ) { ++in; }
    497527//          } 
    498528//        }
    499529//      } else {
    500530//        ++in;
    501 //        while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     531//        while (in.valid() && !(Edge::free()>0) ) { ++in; }
    502532//        while (v.valid() && !in.valid()) {
    503533//          ++v;
    504 //          if (v.valid()) G->getFirst(in, v);
    505 //          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     534//          if (v.valid()) G->/*getF*/first(in, v);
     535//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
    506536//        }
    507537//      }
     
    510540    };
    511541
    512     EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }
    513     OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const {
     542    NodeIt& /*getF*/first(NodeIt& v) const { return graph->/*getF*/first(v); }
     543    OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const {
    514544      e=OutEdgeIt(*this, v);
    515     }
    516     EachEdgeIt& getFirst(EachEdgeIt& e) const {
    517       e=EachEdgeIt(*this);
     545      return e;
     546    }
     547    EdgeIt& /*getF*/first(EdgeIt& e) const {
     548      e=EdgeIt(*this);
     549      return e;
    518550    }
    519551   
    520     EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
     552    NodeIt& next(NodeIt& n) const { return graph->next(n); }
    521553
    522554    OutEdgeIt& next(OutEdgeIt& e) const {
    523555      if (e.out_or_in) {
    524         NodeIt v=G->aNode(e.out);
    525         ++(e.out);
    526         while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
    527         if (!G->valid(e.out)) {
     556        Node v=graph->aNode(e.out);
     557        graph->next(e.out);
     558        while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
     559        if (!graph->valid(e.out)) {
    528560          e.out_or_in=0;
    529           G->getFirst(e.in, v);
    530           while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
     561          graph->/*getF*/first(e.in, v);
     562          while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
    531563        }
    532564      } else {
    533         ++(e.in);
    534         while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
     565        graph->next(e.in);
     566        while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
    535567      }
    536568      return e;
    537569    }
    538570
    539     EachEdgeIt& next(EachEdgeIt& e) const {
     571    EdgeIt& next(EdgeIt& e) const {
    540572      if (e.out_or_in) {
    541         ++(e.out);
    542         while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
    543           while (G->valid(e.v) && !G->valid(e.out)) {
    544             ++(e.v);
    545             if (G->valid(e.v)) G->getFirst(e.out, e.v);
    546             while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
     573        graph->next(e.out);
     574        while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
     575          while (graph->valid(e.v) && !graph->valid(e.out)) {
     576            graph->next(e.v);
     577            if (graph->valid(e.v)) graph->/*getF*/first(e.out, e.v);
     578            while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
    547579          }
    548           if (!G->valid(e.out)) {
     580          if (!graph->valid(e.out)) {
    549581            e.out_or_in=0;
    550             G->getFirst(e.v);
    551             if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
    552             while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
    553             while (G->valid(e.v) && !G->valid(e.in)) {
    554               ++(e.v);
    555               if (G->valid(e.v)) G->getFirst(e.in, e.v);
    556               while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
     582            graph->/*getF*/first(e.v);
     583            if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); else e.in=OldInEdgeIt(INVALID);
     584            while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
     585            while (graph->valid(e.v) && !graph->valid(e.in)) {
     586              graph->next(e.v);
     587              if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v);
     588              while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
    557589            } 
    558590          }
    559591        } else {
    560           ++(e.in);
    561           while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
    562           while (G->valid(e.v) && !G->valid(e.in)) {
    563             ++(e.v);
    564             if (G->valid(e.v)) G->getFirst(e.in, e.v);
    565             while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
     592          graph->next(e.in);
     593          while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
     594          while (graph->valid(e.v) && !graph->valid(e.in)) {
     595            graph->next(e.v);
     596            if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v);
     597            while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
    566598          }
    567599        }
     
    573605    It first() const {
    574606      It e;
    575       getFirst(e);
     607      /*getF*/first(e);
    576608      return e;
    577609    }
    578610
    579611    template< typename It >
    580     It first(NodeIt v) const {
     612    It first(Node v) const {
    581613      It e;
    582       getFirst(e, v);
     614      /*getF*/first(e, v);
    583615      return e;
    584616    }
    585617
    586     NodeIt tail(EdgeIt e) const {
    587       return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
    588     NodeIt head(EdgeIt e) const {
    589       return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
    590 
    591     NodeIt aNode(OutEdgeIt e) const {
    592       return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
    593     NodeIt bNode(OutEdgeIt e) const {
    594       return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
    595 
    596     int id(NodeIt v) const { return G->id(v); }
    597 
    598     bool valid(NodeIt n) const { return G->valid(n); }
    599     bool valid(EdgeIt e) const {
    600       return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
    601 
    602     void augment(const EdgeIt& e, Number a) const {
     618    Node tail(Edge e) const {
     619      return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
     620    Node head(Edge e) const {
     621      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
     622
     623    Node aNode(OutEdgeIt e) const {
     624      return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
     625    Node bNode(OutEdgeIt e) const {
     626      return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
     627
     628    int id(Node v) const { return graph->id(v); }
     629
     630    bool valid(Node n) const { return graph->valid(n); }
     631    bool valid(Edge e) const {
     632      return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
     633
     634    void augment(const Edge& e, Number a) const {
    603635      if (e.out_or_in) 
    604636        flow->set(e.out, flow->get(e.out)+a);
     
    607639    }
    608640
    609     Number free(const EdgeIt& e) const {
     641    Number free(const Edge& e) const {
    610642      if (e.out_or_in)
    611643        return (capacity->get(e.out)-flow->get(e.out));
     
    634666//       typename Graph::NodeMap<T> node_map;
    635667//     public:
    636 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
    637 //       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
    638 //       void set(NodeIt nit, T a) { node_map.set(nit, a); }
    639 //       T get(NodeIt nit) const { return node_map.get(nit); }
     668//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
     669//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
     670//       void set(Node nit, T a) { node_map.set(nit, a); }
     671//       T get(Node nit) const { return node_map.get(nit); }
    640672//     };
    641673
     
    646678      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
    647679      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) {
    649681        if (e.out_or_in)
    650682          forward_map.set(e.out, a);
     
    652684          backward_map.set(e.in, a);
    653685      }
    654       T get(EdgeIt e) {
     686      T get(Edge e) {
    655687        if (e.out_or_in)
    656688          return forward_map.get(e.out);
     
    671703      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
    672704      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)) {
    674706        OutEdgeIt e;
    675         ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
     707        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n);
    676708        first_out_edges.set(n, e);
    677709      }
     
    686718    //typedef Graph BaseGraph;
    687719
     720    //typedef typename Graph::Node Node;
    688721    //typedef typename Graph::NodeIt NodeIt;
    689     //typedef typename Graph::EachNodeIt EachNodeIt;
    690 
    691     //typedef typename Graph::EdgeIt EdgeIt;
     722
     723    //typedef typename Graph::Edge Edge;
    692724    //typedef typename Graph::OutEdgeIt OutEdgeIt;
    693725    //typedef typename Graph::InEdgeIt InEdgeIt;
    694726    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    695     //typedef typename Graph::EachEdgeIt EachEdgeIt;
    696 
     727    //typedef typename Graph::EdgeIt EdgeIt;
     728
     729    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
    697730    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
    698     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
    699 
    700     typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
     731
     732    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
    701733    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
    702734    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
    703735    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    704     //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
    705 
    706     EachNodeIt& getFirst(EachNodeIt& n) const {
    707       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
    708     }
    709 
    710     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
     736    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
     737
     738    NodeIt& /*getF*/first(NodeIt& n) const {
     739      return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n);
     740    }
     741
     742    OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
    711743      e=first_out_edges.get(n);
    712744      return e;
    713745    }
    714746   
    715     //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); }
    716     //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    717     //  return getFirst(i, p); }
     747    //ROSSZ template<typename I> I& /*getF*/first(I& i) const { return /*getF*/first(i); }
     748    //ROSSZ template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
     749    //  return /*getF*/first(i, p); }
    718750   
    719751    //template<typename I> I getNext(const I& i) const {
     
    722754
    723755    template< typename It > It first() const {
    724       It e; getFirst(e); return e; }
    725 
    726     template< typename It > It first(const NodeIt& v) const {
    727       It e; getFirst(e, v); return e; }
    728 
    729     //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    730     //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     756      It e; /*getF*/first(e); return e; }
     757
     758    template< typename It > It first(const Node& v) const {
     759      It e; /*getF*/first(e, v); return e; }
     760
     761    //Node head(const Edge& e) const { return graph->head(e); }
     762    //Node tail(const Edge& e) const { return graph->tail(e); }
    731763
    732764    //template<typename I> bool valid(const I& i) const
     
    736768    //int edgeNum() const { return graph->edgeNum(); }
    737769 
    738     //template<typename I> NodeIt aNode(const I& e) const {
     770    //template<typename I> Node aNode(const I& e) const {
    739771    //  return graph->aNode(e); }
    740     //template<typename I> NodeIt bNode(const I& e) const {
     772    //template<typename I> Node bNode(const I& e) const {
    741773    //  return graph->bNode(e); }
    742774 
    743     //NodeIt addNode() const { return graph->addNode(); }
    744     //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
     775    //Node addNode() const { return graph->addNode(); }
     776    //Edge addEdge(const Node& tail, const Node& head) const {
    745777    //  return graph->addEdge(tail, head); }
    746778 
     
    748780    //  first_out_edge(this->tail(e))=e;
    749781    //}
    750     void erase(const EdgeIt& e) {
     782    void erase(const Edge& e) {
    751783      OutEdgeIt f(e);
    752784      next(f);
     
    786818    //typedef Graph BaseGraph;
    787819
     820    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
    788821    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
    789     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
    790 
    791     typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
     822
     823    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
    792824    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
    793825    //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
    794826    //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;
    796828
    797829    //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
     
    803835    }
    804836
    805     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
    806       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
     837    OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
     838      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n);
    807839      while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
    808840        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
     
    810842    }
    811843
    812     EachNodeIt& next(EachNodeIt& e) const {
     844    NodeIt& next(NodeIt& e) const {
    813845      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
    814846    }
     
    821853    }
    822854
    823     EachNodeIt& getFirst(EachNodeIt& n) const {
    824       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
    825     }
    826 
    827     void erase(const EdgeIt& e) {
     855    NodeIt& /*getF*/first(NodeIt& n) const {
     856      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n);
     857    }
     858
     859    void erase(const Edge& e) {
    828860      OutEdgeIt f(e);
    829861      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
     
    839871    //Graph& getGraph() const { return (*graph); }
    840872   
    841     //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    842     //template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    843     //  return graph->getFirst(i, p); }
     873    //template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
     874    //template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
     875    //  return graph->/*getF*/first(i, p); }
    844876   
    845877    //template<typename I> I getNext(const I& i) const {
     
    848880
    849881    template< typename It > It first() const {
    850       It e; getFirst(e); return e; }
    851 
    852     template< typename It > It first(const NodeIt& v) const {
    853       It e; getFirst(e, v); return e; }
    854 
    855     //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    856     //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     882      It e; /*getF*/first(e); return e; }
     883
     884    template< typename It > It first(const Node& v) const {
     885      It e; /*getF*/first(e, v); return e; }
     886
     887    //Node head(const Edge& e) const { return graph->head(e); }
     888    //Node tail(const Edge& e) const { return graph->tail(e); }
    857889
    858890    //template<typename I> bool valid(const I& i) const
     
    865897    //int edgeNum() const { return graph->edgeNum(); }
    866898 
    867     //template<typename I> NodeIt aNode(const I& e) const {
     899    //template<typename I> Node aNode(const I& e) const {
    868900    //  return graph->aNode(e); }
    869     //template<typename I> NodeIt bNode(const I& e) const {
     901    //template<typename I> Node bNode(const I& e) const {
    870902    //  return graph->bNode(e); }
    871903 
    872     //NodeIt addNode() const { return graph->addNode(); }
    873     //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
     904    //Node addNode() const { return graph->addNode(); }
     905    //Edge addEdge(const Node& tail, const Node& head) const {
    874906    //  return graph->addEdge(tail, head); }
    875907 
     
    910942//     typedef Graph BaseGraph;
    911943
     944//     typedef typename Graph::Node Node;
     945//     typedef typename Graph::Edge Edge;
     946 
    912947//     typedef typename Graph::NodeIt NodeIt;
    913 //     typedef typename Graph::EdgeIt EdgeIt;
    914  
    915 //     typedef typename Graph::EachNodeIt EachNodeIt;
    916948   
    917949//     class OutEdgeIt {
    918950//     public:
    919 //       //Graph::NodeIt n;
     951//       //Graph::Node n;
    920952//       bool out_or_in;
    921953//       typename Graph::OutEdgeIt o;
     
    924956//     class InEdgeIt {
    925957//     public:
    926 //       //Graph::NodeIt n;
     958//       //Graph::Node n;
    927959//       bool out_or_in;
    928960//       typename Graph::OutEdgeIt o;
     
    930962//     };
    931963//     typedef typename Graph::SymEdgeIt SymEdgeIt;
    932 //     typedef typename Graph::EachEdgeIt EachEdgeIt;
     964//     typedef typename Graph::EdgeIt EdgeIt;
    933965
    934966//     int nodeNum() const { return graph->nodeNum(); }
    935967//     int edgeNum() const { return graph->edgeNum(); }
    936968
    937 //     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
    938 
    939 //     // EachEdge and SymEdge  is missing!!!!
    940 //     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
     969//     Node& /*getF*/first(Node& n) const { return graph->/*getF*/first(n); }
     970
     971//     // Edge and SymEdge  is missing!!!!
     972//     // Edge <-> In/OutEdgeIt conversion is missing!!!!
    941973
    942974//     //FIXME
    943 //     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
     975//     OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const
    944976//       {
    945977//      e.n=n;
    946 //      graph->getFirst(e.o,n);
     978//      graph->/*getF*/first(e.o,n);
    947979//      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
    948980//        graph->goNext(e.o);
    949981//      if(!graph->valid(e.o)) {
    950 //        graph->getFirst(e.i,n);
     982//        graph->/*getF*/first(e.i,n);
    951983//        while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
    952984//          graph->goNext(e.i);
     
    961993//   graph->goNext(e.o);
    962994//   if(graph->valid(e.o)) return e;
    963 //   else graph->getFirst(e.i,e.n);
     995//   else graph->/*getF*/first(e.i,e.n);
    964996//   }
    965997//   else {
     
    9741006
    9751007//     //FIXME
    976 //     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
     1008//     InEdgeIt& /*getF*/first(InEdgeIt& e, const Node& n) const
    9771009//       {
    9781010//      e.n=n;
    979 //      graph->getFirst(e.i,n);
     1011//      graph->/*getF*/first(e.i,n);
    9801012//      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
    9811013//        graph->goNext(e.i);
    9821014//      if(!graph->valid(e.i)) {
    983 //        graph->getFirst(e.o,n);
     1015//        graph->/*getF*/first(e.o,n);
    9841016//        while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
    9851017//          graph->goNext(e.o);
     
    9941026//   graph->goNext(e.i);
    9951027//   if(graph->valid(e.i)) return e;
    996 //   else graph->getFirst(e.o,e.n);
     1028//   else graph->/*getF*/first(e.o,e.n);
    9971029//   }
    9981030//   else {
     
    10101042
    10111043//     template< typename It > It first() const {
    1012 //       It e; getFirst(e); return e; }
    1013 
    1014 //     template< typename It > It first(NodeIt v) const {
    1015 //       It e; getFirst(e, v); return e; }
    1016 
    1017 //     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    1018 //     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
    1019  
    1020 //     template<typename I> NodeIt aNode(const I& e) const {
     1044//       It e; /*getF*/first(e); return e; }
     1045
     1046//     template< typename It > It first(Node v) const {
     1047//       It e; /*getF*/first(e, v); return e; }
     1048
     1049//     Node head(const Edge& e) const { return graph->head(e); }
     1050//     Node tail(const Edge& e) const { return graph->tail(e); }
     1051 
     1052//     template<typename I> Node aNode(const I& e) const {
    10211053//       return graph->aNode(e); }
    1022 //     template<typename I> NodeIt bNode(const I& e) const {
     1054//     template<typename I> Node bNode(const I& e) const {
    10231055//       return graph->bNode(e); }
    10241056 
     
    10291061//     //{ return graph->setInvalid(i); }
    10301062 
    1031 //     NodeIt addNode() { return graph->addNode(); }
    1032 //     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
     1063//     Node addNode() { return graph->addNode(); }
     1064//     Edge addEdge(const Node& tail, const Node& head) {
    10331065//       return graph->addEdge(tail, head); }
    10341066 
  • src/work/marci/makefile

    r168 r174  
    22CXX2 = g++-2.95
    33CXX3.3 = g++
    4 CXXFLAGS = -W -Wall -ansi -pedantic
     4CXXFLAGS = -W -Wall -ansi -pedantic -I. -I.. -I../alpar
    55LEDAROOT ?= /ledasrc/LEDA-4.1
    66
    7 BINARIES = edmonds_karp_demo edmonds_karp_demo_alpar preflow_demo_leda preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos
     7BINARIES = edmonds_karp_demo edmonds_karp_demo_alpar preflow_demo_leda preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos lg_vs_sg
    88
    99all: $(BINARIES)
     
    1717
    1818edmonds_karp_demo:
    19         $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
    20         $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo_prof.cc
     19        $(CXX3) $(CXXFLAGS) -g -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
     20        $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo.cc
     21
     22lg_vs_sg:
     23        $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o lg_vs_sg lg_vs_sg.cc
    2124
    2225edmonds_karp_demo_alpar:
Note: See TracChangeset for help on using the changeset viewer.