COIN-OR::LEMON - Graph Library

Changeset 528:c00f6ebbe1e6 in lemon-0.x


Ignore:
Timestamp:
05/04/04 18:16:49 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@694
Message:

Able to read min cost flow, max flow, shortest path, matching testgraphs

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/include/dimacs.h

    r465 r528  
    66#include <string>
    77#include <vector>
     8#include <maps.h>
    89
    910/// \file
     
    2425  ///\author Marton Makai
    2526  template<typename Graph, typename CapacityMap>
    26   void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
     27  void readDimacsMaxFlow(std::istream& is, Graph &g,
     28                         typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
    2729    g.clear();
    2830    int cap;
     
    6971    }
    7072  }
     73
     74  /// matching problem
     75  template<typename Graph>
     76  void readDimacs(std::istream& is, Graph &g) {
     77    typename Graph::Node u;
     78    NullMap<typename Graph::Edge, int> n;
     79    readDimacs(is, g, n, u, u, n);
     80    std::cout<<"igen en.";
     81  }
     82
     83  /// sg problem
     84  template<typename Graph, typename CapacityMap>
     85  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
     86    typename Graph::Node u;
     87    NullMap<typename Graph::Edge, int> n;
     88    readDimacs(is, g, cap, u, u, n);
     89  }
     90
     91  /// shortest path problem
     92  template<typename Graph, typename CapacityMap>
     93  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
     94                  typename Graph::Node &s) {
     95    NullMap<typename Graph::Edge, int> n;
     96    readDimacs(is, g, capacity, s, s, n);
     97  }
     98
     99  /// max flow problem
     100  template<typename Graph, typename CapacityMap>
     101  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
     102                  typename Graph::Node &s, typename Graph::Node &t) {
     103    NullMap<typename Graph::Edge, int> n;
     104    readDimacs(is, g, capacity, s, t, n);
     105  }
     106
     107  /// min cost flow problem
     108  template<typename Graph, typename CapacityMap, typename CostMap>
     109  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
     110                  typename Graph::Node &s, typename Graph::Node &t,
     111                  CostMap& cost) {
     112    g.clear();
     113    typename CapacityMap::ValueType _cap;
     114    typename CostMap::ValueType _cost;
     115    char d;
     116    std::string problem;
     117    char c;
     118    int i, j;
     119    std::string str;
     120    int n, m;
     121    typename Graph::Edge e;
     122    std::vector<typename Graph::Node> nodes;
     123    while (is>>c) {
     124      switch (c) {
     125      case 'c': //comment
     126        getline(is, str);
     127        break;
     128      case 'p': //problem definition
     129        is >> problem >> n >> m;
     130        getline(is, str);
     131        nodes.resize(n+1);
     132        for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
     133        break;
     134      case 'n': //node definition
     135        if (problem=="sp") { //shortest path problem
     136          is >> i;
     137          getline(is, str);
     138          s=nodes[i];
     139        }
     140        if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
     141          is >> i >> d;
     142          getline(is, str);
     143          if (d=='s') s=nodes[i];
     144          if (d=='t') t=nodes[i];
     145        }
     146        break;
     147      case 'a':
     148        if ( problem == "mat" ) {
     149          is >> i >> j;
     150          getline(is, str);
     151          g.addEdge(nodes[i], nodes[j]);
     152        }
     153        if ( problem == "max" || problem == "sp") {
     154          is >> i >> j >> _cap;
     155          getline(is, str);
     156          e=g.addEdge(nodes[i], nodes[j]);
     157          capacity.update();
     158          capacity.set(e, _cap);
     159        }
     160        if ( problem == "min" ) {
     161          is >> i >> j >> _cap >> _cost;
     162          getline(is, str);
     163          e=g.addEdge(nodes[i], nodes[j]);
     164          capacity.update();
     165          capacity.set(e, _cap);
     166          cost.update();
     167          cost.set(e, _cost);
     168        }
     169        break;
     170      }
     171    }
     172  }
     173
     174
    71175 
     176  /// write matching problem
     177  template<typename Graph>
     178  void writeDimacs(std::ostream& os, const Graph &g) {
     179    typedef typename Graph::NodeIt NodeIt;
     180    typedef typename Graph::EdgeIt EdgeIt; 
     181   
     182    typename Graph::template NodeMap<int> nodes(g);
     183
     184    os << "c matching problem" << std::endl;
     185
     186    int i=1;
     187    NodeIt v;
     188    for(g.first(v); g.valid(v); g.next(v)) {
     189      nodes.set(v, i);
     190      ++i;
     191    }   
     192   
     193    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
     194
     195    EdgeIt e;
     196    for(g.first(e); g.valid(e); g.next(e)) {
     197      os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
     198    }
     199
     200  }
     201
     202
     203
    72204} //namespace hugo
    73205
Note: See TracChangeset for help on using the changeset viewer.