COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/dimacs.h @ 442:267dfa567ad3

Last change on this file since 442:267dfa567ad3 was 442:267dfa567ad3, checked in by Mihaly Barasz, 20 years ago

oops

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  template<typename Graph, typename CapacityMap>
24  void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
25    g.clear();
26    int cap;
27    char d;
28    std::string problem;
29    char c;
30    int i, j;
31    std::string str;
32    int n, m;
33    typename Graph::Edge e;
34    std::vector<typename Graph::Node> nodes;
35    while (is>>c) {
36      switch (c) {
37      case 'c': //comment
38        getline(is, str);
39        break;
40      case 'p': //problem definition
41        is >> problem >> n >> m;
42        getline(is, str);
43        nodes.resize(n+1);
44        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
45        break;
46      case 'n': //node definition
47        if (problem=="sp") { //shortest path problem
48          is >> i;
49          getline(is, str);
50          s=nodes[i];
51        }
52        if (problem=="max") { //max flow problem
53          is >> i >> d;
54          getline(is, str);
55          if (d=='s') s=nodes[i];
56          if (d=='t') t=nodes[i];
57        }
58        break;
59      case 'a':
60        is >> i >> j >> cap;
61        getline(is, str);
62        e=g.addEdge(nodes[i], nodes[j]);
63        capacity.update();
64        capacity.set(e, cap);
65        break;
66      }
67    }
68  }
69 
70} //namespace hugo
71
72#endif //HUGO_DIMACS_H
Note: See TracBrowser for help on using the repository browser.