COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/dimacs.h @ 423:fac60be3129b

Last change on this file since 423:fac60be3129b was 423:fac60be3129b, checked in by marci, 16 years ago

misc

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