[415] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 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 "test_tools.h" |
---|
| 33 | #include <lemon/list_graph.h> |
---|
| 34 | #include <lemon/circulation.h> |
---|
| 35 | #include <lemon/lgf_reader.h> |
---|
| 36 | |
---|
| 37 | using namespace lemon; |
---|
| 38 | |
---|
| 39 | char test_lgf[] = |
---|
| 40 | "@nodes\n" |
---|
| 41 | "label delta\n" |
---|
| 42 | "0 0\n" |
---|
| 43 | "1 13\n" |
---|
| 44 | "2 0\n" |
---|
| 45 | "3 0\n" |
---|
| 46 | "4 0\n" |
---|
| 47 | "5 0\n" |
---|
| 48 | "6 0\n" |
---|
| 49 | "7 0\n" |
---|
| 50 | "8 -13\n" |
---|
| 51 | "9 0\n" |
---|
| 52 | "@edges\n" |
---|
| 53 | " label lo_cap up_cap\n" |
---|
| 54 | "0 1 0 0 20\n" |
---|
| 55 | "0 2 1 0 0\n" |
---|
| 56 | "1 1 2 0 3\n" |
---|
| 57 | "1 2 3 0 8\n" |
---|
| 58 | "1 3 4 0 8\n" |
---|
| 59 | "2 5 5 0 5\n" |
---|
| 60 | "3 2 6 0 5\n" |
---|
| 61 | "3 5 7 0 5\n" |
---|
| 62 | "3 6 8 0 5\n" |
---|
| 63 | "4 3 9 0 3\n" |
---|
| 64 | "5 7 10 0 3\n" |
---|
| 65 | "5 6 11 0 10\n" |
---|
| 66 | "5 8 12 0 10\n" |
---|
| 67 | "6 8 13 0 8\n" |
---|
| 68 | "8 9 14 0 20\n" |
---|
| 69 | "8 1 15 0 5\n" |
---|
| 70 | "9 5 16 0 5\n" |
---|
| 71 | "@attributes\n" |
---|
| 72 | "source 1\n" |
---|
| 73 | "sink 8\n"; |
---|
| 74 | |
---|
| 75 | int main (int, char*[]) |
---|
| 76 | { |
---|
| 77 | |
---|
| 78 | typedef ListDigraph Digraph; |
---|
| 79 | typedef Digraph::Node Node; |
---|
| 80 | typedef Digraph::NodeIt NodeIt; |
---|
| 81 | typedef Digraph::Arc Arc; |
---|
| 82 | typedef Digraph::ArcIt ArcIt; |
---|
| 83 | typedef Digraph::ArcMap<int> ArcMap; |
---|
| 84 | typedef Digraph::NodeMap<int> NodeMap; |
---|
| 85 | typedef Digraph::NodeMap<double> DNodeMap; |
---|
| 86 | |
---|
| 87 | Digraph g; |
---|
| 88 | ArcMap lo(g); |
---|
| 89 | ArcMap up(g); |
---|
| 90 | NodeMap delta(g); |
---|
| 91 | NodeMap nid(g); |
---|
| 92 | ArcMap eid(g); |
---|
| 93 | Node source, sink; |
---|
| 94 | |
---|
| 95 | std::istringstream input(test_lgf); |
---|
| 96 | DigraphReader<Digraph>(g,input). |
---|
| 97 | arcMap("lo_cap", lo). |
---|
| 98 | arcMap("up_cap", up). |
---|
| 99 | nodeMap("delta", delta). |
---|
| 100 | arcMap("label", eid). |
---|
| 101 | nodeMap("label", nid). |
---|
| 102 | node("source",source). |
---|
| 103 | node("sink",sink). |
---|
| 104 | run(); |
---|
| 105 | |
---|
| 106 | Circulation<Digraph> gen(g,lo,up,delta); |
---|
| 107 | bool ret=gen.run(); |
---|
| 108 | check(ret,"A feasible solution should have been found."); |
---|
| 109 | check(gen.checkFlow(), "The found flow is corrupt."); |
---|
| 110 | |
---|
| 111 | delta[source]=14; |
---|
| 112 | delta[sink]=-14; |
---|
| 113 | |
---|
| 114 | bool ret2=gen.run(); |
---|
| 115 | check(!ret2,"A feasible solution should not have been found."); |
---|
| 116 | check(gen.checkBarrier(), "The found barrier is corrupt."); |
---|
| 117 | |
---|
| 118 | } |
---|