Transform circulation demo to test
authorAlpar Juttner <alpar@cs.elte.hu>
Mon, 01 Dec 2008 14:11:31 +0000
changeset 400fa341dd6ab23
parent 399 5a7dbeaed70e
child 401 26fd85a3087e
Transform circulation demo to test
demo/Makefile.am
demo/circulation-input.lgf
demo/circulation_demo.cc
test/Makefile.am
test/circulation_test.cc
     1.1 --- a/demo/Makefile.am	Fri Nov 21 14:42:47 2008 +0000
     1.2 +++ b/demo/Makefile.am	Mon Dec 01 14:11:31 2008 +0000
     1.3 @@ -1,19 +1,16 @@
     1.4  EXTRA_DIST += \
     1.5  	demo/CMakeLists.txt \
     1.6 -	demo/circulation-input.lgf \
     1.7  	demo/digraph.lgf
     1.8  
     1.9  if WANT_DEMO
    1.10  
    1.11  noinst_PROGRAMS += \
    1.12  	demo/arg_parser_demo \
    1.13 -	demo/circulation_demo \
    1.14  	demo/graph_to_eps_demo \
    1.15  	demo/lgf_demo
    1.16  
    1.17  endif WANT_DEMO
    1.18  
    1.19  demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc
    1.20 -demo_circulation_demo_SOURCES = demo/circulation_demo.cc
    1.21  demo_graph_to_eps_demo_SOURCES = demo/graph_to_eps_demo.cc
    1.22  demo_lgf_demo_SOURCES = demo/lgf_demo.cc
     2.1 --- a/demo/circulation-input.lgf	Fri Nov 21 14:42:47 2008 +0000
     2.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.3 @@ -1,32 +0,0 @@
     2.4 -@nodes 
     2.5 -coordinates_x   coordinates_y   delta   label   
     2.6 --396.638        -311.798        0       0       
     2.7 -154.409         -214.714        13      1       
     2.8 --378.119        -135.808        0       2       
     2.9 --138.182        -58.0452        0       3       
    2.10 -55              -76.1018        0       4       
    2.11 --167.302        169.88          0       5       
    2.12 -71.6876         38.7452         0       6       
    2.13 --328.784        257.777         0       7       
    2.14 -354.242         67.9628         -13     8       
    2.15 -147             266             0       9       
    2.16 -@edges 
    2.17 -                label   lo_cap  up_cap  
    2.18 -0       1       0       0       20      
    2.19 -0       2       1       0       0       
    2.20 -1       1       2       0       3       
    2.21 -1       2       3       0       8       
    2.22 -1       3       4       0       8       
    2.23 -2       5       5       0       5       
    2.24 -3       2       6       0       5       
    2.25 -3       5       7       0       5       
    2.26 -3       6       8       0       5       
    2.27 -4       3       9       0       3       
    2.28 -5       7       10      0       3       
    2.29 -5       6       11      0       10      
    2.30 -5       8       12      0       10      
    2.31 -6       8       13      0       8       
    2.32 -8       9       14      0       20      
    2.33 -8       1       15      0       5       
    2.34 -9       5       16      0       5       
    2.35 -@end
     3.1 --- a/demo/circulation_demo.cc	Fri Nov 21 14:42:47 2008 +0000
     3.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.3 @@ -1,107 +0,0 @@
     3.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
     3.5 - *
     3.6 - * This file is a part of LEMON, a generic C++ optimization library.
     3.7 - *
     3.8 - * Copyright (C) 2003-2008
     3.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    3.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
    3.11 - *
    3.12 - * Permission to use, modify and distribute this software is granted
    3.13 - * provided that this copyright notice appears in all copies. For
    3.14 - * precise terms see the accompanying LICENSE file.
    3.15 - *
    3.16 - * This software is provided "AS IS" with no warranty of any kind,
    3.17 - * express or implied, and with no claim as to its suitability for any
    3.18 - * purpose.
    3.19 - *
    3.20 - */
    3.21 -
    3.22 -///\ingroup demos
    3.23 -///\file
    3.24 -///\brief Demonstrating the usage of LEMON's General Flow algorithm
    3.25 -///
    3.26 -/// This demo program reads a general network circulation problem from the
    3.27 -/// file 'circulation-input.lgf', runs the preflow based algorithm for
    3.28 -/// finding a feasible solution and writes the output
    3.29 -/// to 'circulation-input.lgf'
    3.30 -///
    3.31 -/// \include circulation_demo.cc
    3.32 -
    3.33 -#include <iostream>
    3.34 -
    3.35 -#include <lemon/list_graph.h>
    3.36 -#include <lemon/circulation.h>
    3.37 -#include <lemon/lgf_reader.h>
    3.38 -#include <lemon/lgf_writer.h>
    3.39 -
    3.40 -using namespace lemon;
    3.41 -
    3.42 -
    3.43 -int main (int, char*[])
    3.44 -{
    3.45 -
    3.46 -    typedef ListDigraph Digraph;
    3.47 -    typedef Digraph::Node Node;
    3.48 -    typedef Digraph::NodeIt NodeIt;
    3.49 -    typedef Digraph::Arc Arc;
    3.50 -    typedef Digraph::ArcIt ArcIt;
    3.51 -    typedef Digraph::ArcMap<int> ArcMap;
    3.52 -    typedef Digraph::NodeMap<int> NodeMap;
    3.53 -    typedef Digraph::NodeMap<double> DNodeMap;
    3.54 -
    3.55 -    Digraph g;
    3.56 -    ArcMap lo(g);
    3.57 -    ArcMap up(g);
    3.58 -    NodeMap delta(g);
    3.59 -    NodeMap nid(g);
    3.60 -    ArcMap eid(g);
    3.61 -    DNodeMap cx(g);
    3.62 -    DNodeMap cy(g);
    3.63 -
    3.64 -    DigraphReader<Digraph>(g,"circulation-input.lgf").
    3.65 -      arcMap("lo_cap", lo).
    3.66 -      arcMap("up_cap", up).
    3.67 -      nodeMap("delta", delta).
    3.68 -      arcMap("label", eid).
    3.69 -      nodeMap("label", nid).
    3.70 -      nodeMap("coordinates_x", cx).
    3.71 -      nodeMap("coordinates_y", cy).
    3.72 -      run();
    3.73 -
    3.74 -    Circulation<Digraph> gen(g,lo,up,delta);
    3.75 -    bool ret=gen.run();
    3.76 -    if(ret)
    3.77 -      {
    3.78 -        std::cout << "\nA feasible flow has been found.\n";
    3.79 -        if(!gen.checkFlow()) std::cerr << "Oops!!!\n";
    3.80 -        DigraphWriter<Digraph>(g, "circulation-output.lgf").
    3.81 -          arcMap("lo_cap", lo).
    3.82 -          arcMap("up_cap", up).
    3.83 -          arcMap("flow", gen.flowMap()).
    3.84 -          nodeMap("delta", delta).
    3.85 -          arcMap("label", eid).
    3.86 -          nodeMap("label", nid).
    3.87 -          nodeMap("coordinates_x", cx).
    3.88 -          nodeMap("coordinates_y", cy).
    3.89 -          run();
    3.90 -      }
    3.91 -    else {
    3.92 -      std::cout << "\nThere is no such a flow\n";
    3.93 -      Digraph::NodeMap<int> bar(g);
    3.94 -      gen.barrierMap(bar);
    3.95 -      if(!gen.checkBarrier()) std::cerr << "Dual Oops!!!\n";
    3.96 -
    3.97 -      DigraphWriter<Digraph>(g, "circulation-output.lgf").
    3.98 -        arcMap("lo_cap", lo).
    3.99 -        arcMap("up_cap", up).
   3.100 -        nodeMap("barrier", bar).
   3.101 -        nodeMap("delta", delta).
   3.102 -        arcMap("label", eid).
   3.103 -        nodeMap("label", nid).
   3.104 -        nodeMap("coordinates_x", cx).
   3.105 -        nodeMap("coordinates_y", cy).
   3.106 -        run();
   3.107 -    }
   3.108 -  std::cout << "The output is written to file 'circulation-output.lgf'\n\n";
   3.109 -
   3.110 -}
     4.1 --- a/test/Makefile.am	Fri Nov 21 14:42:47 2008 +0000
     4.2 +++ b/test/Makefile.am	Mon Dec 01 14:11:31 2008 +0000
     4.3 @@ -8,6 +8,7 @@
     4.4  
     4.5  check_PROGRAMS += \
     4.6  	test/bfs_test \
     4.7 +        test/circulation_test \
     4.8          test/counter_test \
     4.9  	test/dfs_test \
    4.10  	test/digraph_test \
    4.11 @@ -33,6 +34,7 @@
    4.12  XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    4.13  
    4.14  test_bfs_test_SOURCES = test/bfs_test.cc
    4.15 +test_circulation_test_SOURCES = test/circulation_test.cc
    4.16  test_counter_test_SOURCES = test/counter_test.cc
    4.17  test_dfs_test_SOURCES = test/dfs_test.cc
    4.18  test_digraph_test_SOURCES = test/digraph_test.cc
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/test/circulation_test.cc	Mon Dec 01 14:11:31 2008 +0000
     5.3 @@ -0,0 +1,118 @@
     5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     5.5 + *
     5.6 + * This file is a part of LEMON, a generic C++ optimization library.
     5.7 + *
     5.8 + * Copyright (C) 2003-2008
     5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    5.11 + *
    5.12 + * Permission to use, modify and distribute this software is granted
    5.13 + * provided that this copyright notice appears in all copies. For
    5.14 + * precise terms see the accompanying LICENSE file.
    5.15 + *
    5.16 + * This software is provided "AS IS" with no warranty of any kind,
    5.17 + * express or implied, and with no claim as to its suitability for any
    5.18 + * purpose.
    5.19 + *
    5.20 + */
    5.21 +
    5.22 +///\ingroup demos
    5.23 +///\file
    5.24 +///\brief Demonstrating the usage of LEMON's General Flow algorithm
    5.25 +///
    5.26 +/// This demo program reads a general network circulation problem from the
    5.27 +/// file 'circulation-input.lgf', runs the preflow based algorithm for
    5.28 +/// finding a feasible solution and writes the output
    5.29 +/// to 'circulation-input.lgf'
    5.30 +///
    5.31 +/// \include circulation_demo.cc
    5.32 +
    5.33 +#include <iostream>
    5.34 +
    5.35 +#include "test_tools.h"
    5.36 +#include <lemon/list_graph.h>
    5.37 +#include <lemon/circulation.h>
    5.38 +#include <lemon/lgf_reader.h>
    5.39 +
    5.40 +using namespace lemon;
    5.41 +
    5.42 +char test_lgf[] =
    5.43 +  "@nodes\n"
    5.44 +  "label delta\n"
    5.45 +  "0     0\n"
    5.46 +  "1     13\n"
    5.47 +  "2     0\n"
    5.48 +  "3     0\n"
    5.49 +  "4     0\n"
    5.50 +  "5     0\n"
    5.51 +  "6     0\n"
    5.52 +  "7     0\n"
    5.53 +  "8     -13\n"
    5.54 +  "9     0\n"
    5.55 +  "@edges\n"
    5.56 +  "    label lo_cap up_cap\n"
    5.57 +  "0 1 0     0      20\n"
    5.58 +  "0 2 1     0      0\n"
    5.59 +  "1 1 2     0      3\n"
    5.60 +  "1 2 3     0      8\n"
    5.61 +  "1 3 4     0      8\n"
    5.62 +  "2 5 5     0      5\n"
    5.63 +  "3 2 6     0      5\n"
    5.64 +  "3 5 7     0      5\n"
    5.65 +  "3 6 8     0      5\n"
    5.66 +  "4 3 9     0      3\n"
    5.67 +  "5 7 10    0      3\n"
    5.68 +  "5 6 11    0      10\n"
    5.69 +  "5 8 12    0      10\n"
    5.70 +  "6 8 13    0      8\n"
    5.71 +  "8 9 14    0      20\n"
    5.72 +  "8 1 15    0      5\n"
    5.73 +  "9 5 16    0      5\n"
    5.74 +  "@attributes\n"
    5.75 +  "source 1\n"
    5.76 +  "sink   8\n";
    5.77 +
    5.78 +int main (int, char*[])
    5.79 +{
    5.80 +
    5.81 +    typedef ListDigraph Digraph;
    5.82 +    typedef Digraph::Node Node;
    5.83 +    typedef Digraph::NodeIt NodeIt;
    5.84 +    typedef Digraph::Arc Arc;
    5.85 +    typedef Digraph::ArcIt ArcIt;
    5.86 +    typedef Digraph::ArcMap<int> ArcMap;
    5.87 +    typedef Digraph::NodeMap<int> NodeMap;
    5.88 +    typedef Digraph::NodeMap<double> DNodeMap;
    5.89 +
    5.90 +    Digraph g;
    5.91 +    ArcMap lo(g);
    5.92 +    ArcMap up(g);
    5.93 +    NodeMap delta(g);
    5.94 +    NodeMap nid(g);
    5.95 +    ArcMap eid(g);
    5.96 +    Node source, sink;
    5.97 +    
    5.98 +    std::istringstream input(test_lgf);
    5.99 +    DigraphReader<Digraph>(g,input).
   5.100 +      arcMap("lo_cap", lo).
   5.101 +      arcMap("up_cap", up).
   5.102 +      nodeMap("delta", delta).
   5.103 +      arcMap("label", eid).
   5.104 +      nodeMap("label", nid).
   5.105 +      node("source",source).
   5.106 +      node("sink",sink).
   5.107 +      run();
   5.108 +
   5.109 +    Circulation<Digraph> gen(g,lo,up,delta);
   5.110 +    bool ret=gen.run();
   5.111 +    check(ret,"A feasible solution should have been found.");
   5.112 +    check(gen.checkFlow(), "The found flow is corrupt.");
   5.113 +    
   5.114 +    delta[source]=14;
   5.115 +    delta[sink]=-14;
   5.116 +    
   5.117 +    bool ret2=gen.run();
   5.118 +    check(!ret2,"A feasible solution should not have been found.");
   5.119 +    check(gen.checkBarrier(), "The found barrier is corrupt.");
   5.120 +
   5.121 +}