demo/circulation_demo.cc
author ladanyi
Sat, 13 Oct 2007 08:48:07 +0000
changeset 2495 e4f8367beb41
parent 2375 e30a0fdad0d7
child 2526 b7727edd44f2
permissions -rw-r--r--
Added the function isFinite(), and replaced the calls to finite() with it.
This was necessary because finite() is not a standard function. Neither can
we use its standard counterpart isfinite(), because it was introduced only
in C99, and therefore it is not supplied by all C++ implementations.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    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>
    31 
    32 #include <lemon/list_graph.h>
    33 #include <lemon/circulation.h>
    34 #include <lemon/graph_reader.h>
    35 #include <lemon/graph_writer.h>
    36 
    37 using namespace lemon;
    38 
    39 
    40 int main (int, char*[])
    41 {
    42 
    43     typedef ListGraph Graph;
    44     typedef Graph::Node Node;
    45     typedef Graph::NodeIt NodeIt;
    46     typedef Graph::Edge Edge;
    47     typedef Graph::EdgeIt EdgeIt;
    48     typedef Graph::EdgeMap<int> EdgeMap;
    49     typedef Graph::NodeMap<int> NodeMap;
    50     typedef Graph::NodeMap<double> DNodeMap;
    51 
    52     Graph g;
    53     EdgeMap lo(g);
    54     EdgeMap up(g);
    55     EdgeMap x(g);
    56     NodeMap delta(g);
    57     NodeMap nid(g);
    58     EdgeMap eid(g);
    59     DNodeMap cx(g);
    60     DNodeMap cy(g);
    61     
    62     GraphReader<Graph>("circulation-input.lgf", g).
    63       readEdgeMap("lo_cap", lo).
    64       readEdgeMap("up_cap", up).
    65       readNodeMap("delta", delta).
    66       readEdgeMap("label", eid).
    67       readNodeMap("label", nid).
    68       readNodeMap("coordinates_x", cx).
    69       readNodeMap("coordinates_y", cy).
    70       run();
    71 
    72     Circulation<Graph,int> gen(g,lo,up,delta,x);
    73     int ret=gen.run();
    74     if(ret==-1)
    75       {
    76 	std::cout << "\nA feasible flow has been found.\n";
    77 	if(!gen.checkX(x)) std::cerr << "Oops!!!\n";
    78 	GraphWriter<Graph>("circulation-output.lgf", g).
    79 	  writeEdgeMap("lo_cap", lo).
    80 	  writeEdgeMap("up_cap", up).
    81 	  writeEdgeMap("flow", x).
    82 	  writeNodeMap("delta", delta).
    83 	  writeEdgeMap("label", eid).
    84 	  writeNodeMap("label", nid).
    85 	  writeNodeMap("coordinates_x", cx).
    86 	  writeNodeMap("coordinates_y", cy).
    87 	  run();
    88       }
    89     else {
    90       std::cout << "\nThere is no such a flow\n";
    91       Graph::NodeMap<int> bar(g);
    92       gen.barrier(bar,ret);
    93       if(!gen.checkBarrier(bar)) std::cerr << "Dual Oops!!!\n";
    94 
    95       GraphWriter<Graph>("circulation-output.lgf", g).
    96 	writeEdgeMap("lo_cap", lo).
    97 	writeEdgeMap("up_cap", up).
    98 	writeNodeMap("barrier", bar).
    99 	writeNodeMap("delta", delta).
   100 	writeEdgeMap("label", eid).
   101 	writeNodeMap("label", nid).
   102 	writeNodeMap("coordinates_x", cx).
   103 	writeNodeMap("coordinates_y", cy).
   104 	run();
   105     }
   106   std::cout << "The output is written to file 'circulation-output.lgf'\n\n";
   107     
   108 }