COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/dimacs.h @ 427:a677104e946a

Last change on this file since 427:a677104e946a was 427:a677104e946a, checked in by Mihaly Barasz, 16 years ago

Minor doc corrections

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