demo/lgf_demo.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 806 fa6f37d7a25b
parent 294 cbe3ec2d59d2
permissions -rw-r--r--
Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@127
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@127
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
deba@127
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@127
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@127
     8
 *
deba@127
     9
 * Permission to use, modify and distribute this software is granted
deba@127
    10
 * provided that this copyright notice appears in all copies. For
deba@127
    11
 * precise terms see the accompanying LICENSE file.
deba@127
    12
 *
deba@127
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@127
    14
 * express or implied, and with no claim as to its suitability for any
deba@127
    15
 * purpose.
deba@127
    16
 *
deba@127
    17
 */
deba@127
    18
deba@127
    19
///\ingroup demos
deba@127
    20
///\file
deba@127
    21
///\brief Demonstrating graph input and output
deba@127
    22
///
kpeter@191
    23
/// This program gives an example of how to read and write a digraph
alpar@209
    24
/// and additional maps from/to a stream or a file using the
kpeter@191
    25
/// \ref lgf-format "LGF" format.
deba@127
    26
///
deba@164
    27
/// The \c "digraph.lgf" file:
deba@164
    28
/// \include digraph.lgf
deba@164
    29
///
kpeter@191
    30
/// And the program which reads it and prints the digraph to the
kpeter@191
    31
/// standard output:
deba@164
    32
/// \include lgf_demo.cc
deba@127
    33
deba@127
    34
#include <iostream>
deba@127
    35
#include <lemon/smart_graph.h>
deba@127
    36
#include <lemon/lgf_reader.h>
deba@127
    37
#include <lemon/lgf_writer.h>
deba@127
    38
deba@127
    39
using namespace lemon;
deba@127
    40
deba@164
    41
int main() {
deba@164
    42
  SmartDigraph g;
deba@164
    43
  SmartDigraph::ArcMap<int> cap(g);
deba@164
    44
  SmartDigraph::Node s, t;
alpar@209
    45
kpeter@191
    46
  try {
kpeter@293
    47
    digraphReader(g, "digraph.lgf"). // read the directed graph into g
kpeter@191
    48
      arcMap("capacity", cap).       // read the 'capacity' arc map into cap
kpeter@191
    49
      node("source", s).             // read 'source' node to s
kpeter@191
    50
      node("target", t).             // read 'target' node to t
kpeter@191
    51
      run();
deba@290
    52
  } catch (Exception& error) { // check if there was any error
kpeter@191
    53
    std::cerr << "Error: " << error.what() << std::endl;
kpeter@191
    54
    return -1;
kpeter@191
    55
  }
deba@127
    56
kpeter@191
    57
  std::cout << "A digraph is read from 'digraph.lgf'." << std::endl;
deba@164
    58
  std::cout << "Number of nodes: " << countNodes(g) << std::endl;
deba@164
    59
  std::cout << "Number of arcs: " << countArcs(g) << std::endl;
deba@127
    60
deba@164
    61
  std::cout << "We can write it to the standard output:" << std::endl;
deba@127
    62
kpeter@293
    63
  digraphWriter(g).                // write g to the standard output
deba@164
    64
    arcMap("capacity", cap).       // write cap into 'capacity'
deba@164
    65
    node("source", s).             // write s to 'source'
deba@164
    66
    node("target", t).             // write t to 'target'
deba@164
    67
    run();
deba@127
    68
deba@127
    69
  return 0;
deba@127
    70
}