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 +}