COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/dimacs.h @ 526:def920ddaba7

Last change on this file since 526:def920ddaba7 was 465:d72e56f1730d, checked in by marci, 18 years ago

mods implied by preflow mods

File size: 1.8 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_DIMACS_H
3#define HUGO_DIMACS_H
4
5#include <iostream>
6#include <string>
7#include <vector>
8
9/// \file
10/// \brief Dimacs file format reader.
11
12namespace hugo {
13
14  /// Dimacs flow file format reader function.
15
16  /// This function reads a flow instance from dimacs flow format.
17  /// At the beginning \c g is cleared by \c g.clear().
18  /// If the data coming from \c is is a max flow problem instance, then
19  /// \c s and \c t will be respectively the source and target nodes
20  /// and \c capacity will contain the edge capacities.
21  /// If the data is a shortest path problem instance then \c s will be the
22  /// source node and \c capacity will contain the edge lengths.
23  ///
24  ///\author Marton Makai
25  template<typename Graph, typename CapacityMap>
26  void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
27    g.clear();
28    int cap;
29    char d;
30    std::string problem;
31    char c;
32    int i, j;
33    std::string str;
34    int n, m;
35    typename Graph::Edge e;
36    std::vector<typename Graph::Node> nodes;
37    while (is>>c) {
38      switch (c) {
39      case 'c': //comment
40        getline(is, str);
41        break;
42      case 'p': //problem definition
43        is >> problem >> n >> m;
44        getline(is, str);
45        nodes.resize(n+1);
46        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
47        break;
48      case 'n': //node definition
49        if (problem=="sp") { //shortest path problem
50          is >> i;
51          getline(is, str);
52          s=nodes[i];
53        }
54        if (problem=="max") { //max flow problem
55          is >> i >> d;
56          getline(is, str);
57          if (d=='s') s=nodes[i];
58          if (d=='t') t=nodes[i];
59        }
60        break;
61      case 'a':
62        is >> i >> j >> cap;
63        getline(is, str);
64        e=g.addEdge(nodes[i], nodes[j]);
65        capacity.update();
66        capacity.set(e, cap);
67        break;
68      }
69    }
70  }
71 
72} //namespace hugo
73
74#endif //HUGO_DIMACS_H
Note: See TracBrowser for help on using the repository browser.