demo/circulation_demo.cc
author convert-repo
Thu, 04 Mar 2010 19:34:55 +0000
changeset 2659 611ced85018b
parent 2526 b7727edd44f2
permissions -rw-r--r--
update tags
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     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     NodeMap delta(g);
    56     NodeMap nid(g);
    57     EdgeMap eid(g);
    58     DNodeMap cx(g);
    59     DNodeMap cy(g);
    60     
    61     GraphReader<Graph>("circulation-input.lgf", g).
    62       readEdgeMap("lo_cap", lo).
    63       readEdgeMap("up_cap", up).
    64       readNodeMap("delta", delta).
    65       readEdgeMap("label", eid).
    66       readNodeMap("label", nid).
    67       readNodeMap("coordinates_x", cx).
    68       readNodeMap("coordinates_y", cy).
    69       run();
    70 
    71     Circulation<Graph> gen(g,lo,up,delta);
    72     bool ret=gen.run();
    73     if(ret)
    74       {
    75 	std::cout << "\nA feasible flow has been found.\n";
    76 	if(!gen.checkFlow()) std::cerr << "Oops!!!\n";
    77 	GraphWriter<Graph>("circulation-output.lgf", g).
    78 	  writeEdgeMap("lo_cap", lo).
    79 	  writeEdgeMap("up_cap", up).
    80 	  writeEdgeMap("flow", gen.flowMap()).
    81 	  writeNodeMap("delta", delta).
    82 	  writeEdgeMap("label", eid).
    83 	  writeNodeMap("label", nid).
    84 	  writeNodeMap("coordinates_x", cx).
    85 	  writeNodeMap("coordinates_y", cy).
    86 	  run();
    87       }
    88     else {
    89       std::cout << "\nThere is no such a flow\n";
    90       Graph::NodeMap<int> bar(g);
    91       gen.barrierMap(bar);
    92       if(!gen.checkBarrier()) std::cerr << "Dual Oops!!!\n";
    93 
    94       GraphWriter<Graph>("circulation-output.lgf", g).
    95 	writeEdgeMap("lo_cap", lo).
    96 	writeEdgeMap("up_cap", up).
    97 	writeNodeMap("barrier", bar).
    98 	writeNodeMap("delta", delta).
    99 	writeEdgeMap("label", eid).
   100 	writeNodeMap("label", nid).
   101 	writeNodeMap("coordinates_x", cx).
   102 	writeNodeMap("coordinates_y", cy).
   103 	run();
   104     }
   105   std::cout << "The output is written to file 'circulation-output.lgf'\n\n";
   106     
   107 }