test/circulation_test.cc
changeset 437 6c1ac149ebf8
parent 400 fa341dd6ab23
child 440 88ed40ad0d4f
equal deleted inserted replaced
0:317c1b80dcd6 1:7ac0285fd776
    14  * express or implied, and with no claim as to its suitability for any
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    15  * purpose.
    16  *
    16  *
    17  */
    17  */
    18 
    18 
    19 ///\ingroup demos
       
    20 ///\file
       
    21 ///\brief Demonstrating the usage of LEMON's General Flow algorithm
       
    22 ///
       
    23 /// This demo program reads a general network circulation problem from the
       
    24 /// file 'circulation-input.lgf', runs the preflow based algorithm for
       
    25 /// finding a feasible solution and writes the output
       
    26 /// to 'circulation-input.lgf'
       
    27 ///
       
    28 /// \include circulation_demo.cc
       
    29 
       
    30 #include <iostream>
    19 #include <iostream>
    31 
    20 
    32 #include "test_tools.h"
    21 #include "test_tools.h"
    33 #include <lemon/list_graph.h>
    22 #include <lemon/list_graph.h>
    34 #include <lemon/circulation.h>
    23 #include <lemon/circulation.h>
    35 #include <lemon/lgf_reader.h>
    24 #include <lemon/lgf_reader.h>
       
    25 #include <lemon/concepts/digraph.h>
       
    26 #include <lemon/concepts/maps.h>
    36 
    27 
    37 using namespace lemon;
    28 using namespace lemon;
    38 
    29 
    39 char test_lgf[] =
    30 char test_lgf[] =
    40   "@nodes\n"
    31   "@nodes\n"
    41   "label delta\n"
    32   "label\n"
    42   "0     0\n"
    33   "0\n"
    43   "1     13\n"
    34   "1\n"
    44   "2     0\n"
    35   "2\n"
    45   "3     0\n"
    36   "3\n"
    46   "4     0\n"
    37   "4\n"
    47   "5     0\n"
    38   "5\n"
    48   "6     0\n"
    39   "@arcs\n"
    49   "7     0\n"
    40   "     lcap  ucap\n"
    50   "8     -13\n"
    41   "0 1  2  10\n"
    51   "9     0\n"
    42   "0 2  2  6\n"
    52   "@edges\n"
    43   "1 3  4  7\n"
    53   "    label lo_cap up_cap\n"
    44   "1 4  0  5\n"
    54   "0 1 0     0      20\n"
    45   "2 4  1  3\n"
    55   "0 2 1     0      0\n"
    46   "3 5  3  8\n"
    56   "1 1 2     0      3\n"
    47   "4 5  3  7\n"
    57   "1 2 3     0      8\n"
       
    58   "1 3 4     0      8\n"
       
    59   "2 5 5     0      5\n"
       
    60   "3 2 6     0      5\n"
       
    61   "3 5 7     0      5\n"
       
    62   "3 6 8     0      5\n"
       
    63   "4 3 9     0      3\n"
       
    64   "5 7 10    0      3\n"
       
    65   "5 6 11    0      10\n"
       
    66   "5 8 12    0      10\n"
       
    67   "6 8 13    0      8\n"
       
    68   "8 9 14    0      20\n"
       
    69   "8 1 15    0      5\n"
       
    70   "9 5 16    0      5\n"
       
    71   "@attributes\n"
    48   "@attributes\n"
    72   "source 1\n"
    49   "source 0\n"
    73   "sink   8\n";
    50   "sink   5\n";
       
    51 
       
    52 void checkCirculationCompile()
       
    53 {
       
    54   typedef int VType;
       
    55   typedef concepts::Digraph Digraph;
       
    56 
       
    57   typedef Digraph::Node Node;
       
    58   typedef Digraph::Arc Arc;
       
    59   typedef concepts::ReadMap<Arc,VType> CapMap;
       
    60   typedef concepts::ReadMap<Node,VType> DeltaMap;
       
    61   typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
       
    62   typedef concepts::WriteMap<Node,bool> BarrierMap;
       
    63 
       
    64   typedef Elevator<Digraph, Digraph::Node> Elev;
       
    65   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
       
    66 
       
    67   Digraph g;
       
    68   Node n;
       
    69   Arc a;
       
    70   CapMap lcap, ucap;
       
    71   DeltaMap delta;
       
    72   FlowMap flow;
       
    73   BarrierMap bar;
       
    74 
       
    75   Circulation<Digraph, CapMap, CapMap, DeltaMap>
       
    76     ::SetFlowMap<FlowMap>
       
    77     ::SetElevator<Elev>
       
    78     ::SetStandardElevator<LinkedElev>
       
    79     ::Create circ_test(g,lcap,ucap,delta);
       
    80 
       
    81   circ_test.lowerCapMap(lcap);
       
    82   circ_test.upperCapMap(ucap);
       
    83   circ_test.deltaMap(delta);
       
    84   flow = circ_test.flowMap();
       
    85   circ_test.flowMap(flow);
       
    86 
       
    87   circ_test.init();
       
    88   circ_test.greedyInit();
       
    89   circ_test.start();
       
    90   circ_test.run();
       
    91 
       
    92   circ_test.barrier(n);
       
    93   circ_test.barrierMap(bar);
       
    94   circ_test.flow(a);
       
    95 }
       
    96 
       
    97 template <class G, class LM, class UM, class DM>
       
    98 void checkCirculation(const G& g, const LM& lm, const UM& um,
       
    99                       const DM& dm, bool find)
       
   100 {
       
   101   Circulation<G, LM, UM, DM> circ(g, lm, um, dm);
       
   102   bool ret = circ.run();
       
   103   if (find) {
       
   104     check(ret, "A feasible solution should have been found.");
       
   105     check(circ.checkFlow(), "The found flow is corrupt.");
       
   106     check(!circ.checkBarrier(), "A barrier should not have been found.");
       
   107   } else {
       
   108     check(!ret, "A feasible solution should not have been found.");
       
   109     check(circ.checkBarrier(), "The found barrier is corrupt.");
       
   110   }
       
   111 }
    74 
   112 
    75 int main (int, char*[])
   113 int main (int, char*[])
    76 {
   114 {
       
   115   typedef ListDigraph Digraph;
       
   116   DIGRAPH_TYPEDEFS(Digraph);
    77 
   117 
    78     typedef ListDigraph Digraph;
   118   Digraph g;
    79     typedef Digraph::Node Node;
   119   IntArcMap lo(g), up(g);
    80     typedef Digraph::NodeIt NodeIt;
   120   IntNodeMap delta(g, 0);
    81     typedef Digraph::Arc Arc;
   121   Node s, t;
    82     typedef Digraph::ArcIt ArcIt;
       
    83     typedef Digraph::ArcMap<int> ArcMap;
       
    84     typedef Digraph::NodeMap<int> NodeMap;
       
    85     typedef Digraph::NodeMap<double> DNodeMap;
       
    86 
   122 
    87     Digraph g;
   123   std::istringstream input(test_lgf);
    88     ArcMap lo(g);
   124   DigraphReader<Digraph>(g,input).
    89     ArcMap up(g);
   125     arcMap("lcap", lo).
    90     NodeMap delta(g);
   126     arcMap("ucap", up).
    91     NodeMap nid(g);
   127     node("source",s).
    92     ArcMap eid(g);
   128     node("sink",t).
    93     Node source, sink;
   129     run();
    94     
       
    95     std::istringstream input(test_lgf);
       
    96     DigraphReader<Digraph>(g,input).
       
    97       arcMap("lo_cap", lo).
       
    98       arcMap("up_cap", up).
       
    99       nodeMap("delta", delta).
       
   100       arcMap("label", eid).
       
   101       nodeMap("label", nid).
       
   102       node("source",source).
       
   103       node("sink",sink).
       
   104       run();
       
   105 
   130 
   106     Circulation<Digraph> gen(g,lo,up,delta);
   131   delta[s] = 7; delta[t] = -7;
   107     bool ret=gen.run();
   132   checkCirculation(g, lo, up, delta, true);
   108     check(ret,"A feasible solution should have been found.");
       
   109     check(gen.checkFlow(), "The found flow is corrupt.");
       
   110     
       
   111     delta[source]=14;
       
   112     delta[sink]=-14;
       
   113     
       
   114     bool ret2=gen.run();
       
   115     check(!ret2,"A feasible solution should not have been found.");
       
   116     check(gen.checkBarrier(), "The found barrier is corrupt.");
       
   117 
   133 
       
   134   delta[s] = 13; delta[t] = -13;
       
   135   checkCirculation(g, lo, up, delta, true);
       
   136 
       
   137   delta[s] = 6; delta[t] = -6;
       
   138   checkCirculation(g, lo, up, delta, false);
       
   139 
       
   140   delta[s] = 14; delta[t] = -14;
       
   141   checkCirculation(g, lo, up, delta, false);
       
   142 
       
   143   delta[s] = 7; delta[t] = -13;
       
   144   checkCirculation(g, lo, up, delta, true);
       
   145 
       
   146   delta[s] = 5; delta[t] = -15;
       
   147   checkCirculation(g, lo, up, delta, true);
       
   148 
       
   149   delta[s] = 10; delta[t] = -11;
       
   150   checkCirculation(g, lo, up, delta, true);
       
   151 
       
   152   delta[s] = 11; delta[t] = -10;
       
   153   checkCirculation(g, lo, up, delta, false);
       
   154 
       
   155   return 0;
   118 }
   156 }