COIN-OR::LEMON - Graph Library

Changeset 333:e0a80761dfd9 in lemon-0.x


Ignore:
Timestamp:
04/15/04 22:19:26 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@452
Message:

makroizeles

Location:
src/work/marci
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/edmonds_karp_demo.cc

    r330 r333  
    1010//#include <graph_wrapper.h>
    1111#include <preflow.h>
     12#include <for_each_macros.h>
    1213
    1314using namespace hugo;
     
    6768  Graph::EdgeMap<int> cap(G);
    6869  readDimacsMaxFlow(std::cin, G, s, t, cap);
     70  Timer ts;
     71  Graph::EdgeMap<int> flow(G); //0 flow
     72  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     73    pre_flow_test(G, s, t, cap, flow);
     74  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     75    max_flow_test(G, s, t, cap, flow);
    6976
    7077  {
    7178    std::cout << "preflow ..." << std::endl;
    72     Graph::EdgeMap<int> flow(G); //0 flow
    73 
    74     Timer ts;
    7579    ts.reset();
    76 
    77     Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    78       max_flow_test(G, s, t, cap, flow);
    79     max_flow_test.run();
    80 //    int i=0;
    81 //    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
    82 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    83 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    84 //     }
    85 //     std::cout<<std::endl;
    86 //      ++i;
    87 //    }
    88 
    89 //   std::cout << "maximum flow: "<< std::endl;
    90 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    91 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    92 //   }
    93 //   std::cout<<std::endl;
     80    pre_flow_test.run();
    9481    std::cout << "elapsed time: " << ts << std::endl;
    95 //    std::cout << "number of augmentation phases: " << i << std::endl;
    96     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     82    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    9783  }
    9884
    9985  {
    10086    std::cout << "physical blocking flow augmentation ..." << std::endl;
    101     Graph::EdgeMap<int> flow(G); //0 flow
    102 
    103     Timer ts;
     87    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    10488    ts.reset();
    105 
    106     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    107       max_flow_test(G, s, t, cap, flow);
    10889    int i=0;
    109     while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
    110 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    111 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    112 //     }
    113 //     std::cout<<std::endl;
    114       ++i;
    115     }
    116 
    117 //   std::cout << "maximum flow: "<< std::endl;
    118 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    119 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    120 //   }
    121 //   std::cout<<std::endl;
     90    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    12291    std::cout << "elapsed time: " << ts << std::endl;
    12392    std::cout << "number of augmentation phases: " << i << std::endl;
     
    12796  {
    12897    std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    129     Graph::EdgeMap<int> flow(G); //0 flow
    130 
    131     Timer ts;
     98    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    13299    ts.reset();
    133 
    134     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    135       max_flow_test(G, s, t, cap, flow);
    136100    int i=0;
    137     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    138 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    139 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    140 //     }
    141 //     std::cout<<std::endl;
    142       ++i;
    143     }
    144 
    145 //   std::cout << "maximum flow: "<< std::endl;
    146 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    147 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    148 //   }
    149 //   std::cout<<std::endl;
     101    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    150102    std::cout << "elapsed time: " << ts << std::endl;
    151103    std::cout << "number of augmentation phases: " << i << std::endl;
     
    155107  {
    156108    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    157     Graph::EdgeMap<int> flow(G); //0 flow
    158 
    159     Timer ts;
     109    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    160110    ts.reset();
    161 
    162     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    163       max_flow_test(G, s, t, cap, flow);
    164111    int i=0;
    165     while (max_flow_test.augmentOnBlockingFlow2()) {
    166 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    167 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    168 //     }
    169 //     std::cout<<std::endl;
    170       ++i;
    171     }
    172 
    173 //   std::cout << "maximum flow: "<< std::endl;
    174 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    175 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    176 //   }
    177 //   std::cout<<std::endl;
     112    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
    178113    std::cout << "elapsed time: " << ts << std::endl;
    179114    std::cout << "number of augmentation phases: " << i << std::endl;
     
    183118  {
    184119    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    185     Graph::EdgeMap<int> flow(G); //0 flow
    186 
    187     Timer ts;
     120    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    188121    ts.reset();
    189 
    190     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    191       max_flow_test(G, s, t, cap, flow);
    192122    int i=0;
    193     while (max_flow_test.augmentOnShortestPath()) {
    194 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    195 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    196 //     }
    197 //     std::cout<<std::endl;
    198       ++i;
    199     }
    200 
    201 //   std::cout << "maximum flow: "<< std::endl;
    202 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    203 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    204 //   }
    205 //   std::cout<<std::endl;
     123    while (max_flow_test.augmentOnShortestPath()) { ++i; }
    206124    std::cout << "elapsed time: " << ts << std::endl;
    207125    std::cout << "number of augmentation phases: " << i << std::endl;
  • src/work/marci/for_each_macros.h

    r330 r333  
    4444//FIXME ezt hogy a gorcsbe birja levezetni. Csak ugy leveszi a const-ot??
    4545  template<typename It, typename Graph>
    46   It loopFirst(const It& i, const Graph& g) {
    47     It e=i; g.first(e); return e;
     46  It loopFirst(const It&, const Graph& g) {
     47    It e; g.first(e); return e;
    4848  }
    4949
    5050  template<typename It, typename Graph, typename Node>
    51   It loopFirst(const It& i, const Graph& g, const Node& v) {
    52     It e=i; g.first(e, v); return e;
     51  It loopFirst(const It&, const Graph& g, const Node& v) {
     52    It e; g.first(e, v); return e;
    5353  }
    5454
     
    7272//   }
    7373
    74 #define FOR_EACH_LOC(Ittype, e, g) for(Ittype (e)=loopFirst(Ittype(), (g)); (g).valid((e)); (g).next((e)))
    75 #define FOR_EACH_INC_LOC(Ittype, e, g, v) for(Ittype (e)=loopFirst(Ittype(), (g), (v)); (g).valid((e)); (g).next((e)))
     74#define FOR_EACH_LOC(Ittype, e, g) for(Ittype e=loopFirst(Ittype(), (g)); (g).valid(e); (g).next(e))
     75#define FOR_EACH_INC_LOC(Ittype, e, g, v) for(Ittype e=loopFirst(Ittype(), (g), (v)); (g).valid(e); (g).next(e))
    7676
    77 // #define FOR_EACH_EDGE_LOC(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
     77// #define FOR_EACH_EDGE_LOC(e, g) ezt nem tom hogy kell for((g).first((e)); (g).valid((e)); (g).next((e)))
    7878// #define FOR_EACH_NODE_LOC(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
    7979// #define FOR_EACH_INEDGE_LOC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
  • src/work/marci/graph_concept.h

    r332 r333  
    365365  };
    366366
    367   /// An empty graph class which provides a function to get the number
    368   /// of its nodes.
     367  /// An empty node-eraseable graph class.
     368 
     369  /// An empty graph class which provides a function to
     370  /// delete any of its nodes.
     371  class NodeEraseableGraphSkeleturo : public GraphSkeleturo
     372  {
     373  public:
     374    /// Deletes a node.
     375    void erase(Node n) {}
     376  };
     377
     378  /// An empty edge-eraseable graph class.
     379 
     380  /// An empty graph class which provides a function to delete any
     381  /// of its edges.
     382  class EdgeEraseableGraphSkeleturo : public GraphSkeleturo
     383  {
     384  public:
     385    /// Deletes a node.
     386    void erase(Edge n) {}
     387  };
     388
     389  /// An empty graph class which provides a function to get the number of its nodes.
    369390 
    370391  /// This graph class provides a function for getting the number of its
     
    374395  /// the implementation can be circumstantial, that is why this composes a
    375396  /// separate concept.
    376   class NodeCountingGraphSkeleturo
     397  class NodeCountingGraphSkeleturo : public GraphSkeleturo
    377398  {
    378399  public:
     
    381402  };
    382403
    383   /// An empty graph class which provides a function to get the number of its
    384   /// edges.
     404  /// An empty graph class which provides a function to get the number of its edges.
    385405 
    386406  /// This graph class provides a function for getting the number of its
     
    390410  /// the implementation can be circumstantial, that is why this composes a
    391411  /// separate concept.
    392   class EdgeCountingGraphSkeleturo
     412  class EdgeCountingGraphSkeleturo : public GraphSkeleturo
    393413  {
    394414  public:
Note: See TracChangeset for help on using the changeset viewer.