# source:lemon-0.x/demo/circulation_demo.cc@2390:8450951a8e2d

Last change on this file since 2390:8450951a8e2d was 2375:e30a0fdad0d7, checked in by Alpar Juttner, 13 years ago

A preflow based general network circulation algorithm and a simple demo

File size: 3.0 KB
Line
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
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>
35#include <lemon/graph_writer.h>
36
37using namespace lemon;
38
39
40int 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
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}
Note: See TracBrowser for help on using the repository browser.