COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2413:21eb3ccdc3df in lemon-0.x for lemon/dimacs.h


Ignore:
Timestamp:
03/22/07 16:40:50 (17 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3244
Message:

Right dimacs format for min cost flows
Bug fixes in tolerance and min_mean_cycle

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/dimacs.h

    r2391 r2413  
    2828/// \ingroup dimacs_group
    2929/// \file
    30 /// \brief Dimacs file format reader.
     30/// \brief DIMACS file format reader.
    3131
    3232namespace lemon {
    3333
    34   ///
    3534  ///@defgroup dimacs_group DIMACS format
    3635  ///\brief Read and write files in DIMACS format
    … …  
    4241  /// \addtogroup dimacs_group
    4342  /// @{
    44 
    45   /// Dimacs min cost flow reader function.
    46 
    47   /// This function reads a min cost flow instance from dimacs format,
    48   /// i.e. from dimacs files having a line starting with
    49   ///\code
    50   /// p "min"
    51   ///\endcode
    52   /// At the beginning \c g is cleared by \c g.clear(). The edge
    53   /// capacities are written to \c capacity, \c s and \c t are set to
    54   /// the source and the target nodes resp. and the cost of the edges
    55   /// are written to \c cost.
    56   ///
    57   /// \author Marton Makai
    58   template<typename Graph, typename CapacityMap, typename CostMap>
    59   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
    60                   typename Graph::Node &s, typename Graph::Node &t,
    61                   CostMap& cost) {
     43 
     44  /// DIMACS min cost flow reader function.
     45  ///
     46  /// This function reads a min cost flow instance from DIMACS format,
     47  /// i.e. from DIMACS files having a line starting with
     48  /// \code
     49  ///   p min
     50  /// \endcode
     51  /// At the beginning \c g is cleared by \c g.clear(). The supply
     52  /// amount of the nodes are written to \c supply (signed). The
     53  /// lower bounds, capacities and costs of the edges are written to
     54  /// \c lower, \c capacity and \c cost.
     55  ///
     56  /// \author Marton Makai and Peter Kovacs
     57  template <typename Graph, typename SupplyMap,
     58    typename CapacityMap, typename CostMap>
     59  void readDimacs( std::istream& is,
     60                   Graph &g,
     61                   SupplyMap& supply,
     62                   CapacityMap& lower,
     63                   CapacityMap& capacity,
     64                   CostMap& cost )
     65  {
    6266    g.clear();
    63     typename CapacityMap::Value _cap;
    64     typename CostMap::Value _cost;
    65     char d;
    66     std::string problem;
     67    std::vector<typename Graph::Node> nodes;
     68    typename Graph::Edge e;
     69    std::string problem, str;
    6770    char c;
     71    int n, m;
    6872    int i, j;
    69     std::string str;
    70     int n, m;
    71     typename Graph::Edge e;
    72     std::vector<typename Graph::Node> nodes;
    73     while (is>>c) {
     73    typename SupplyMap::Value sup;
     74    typename CapacityMap::Value low;
     75    typename CapacityMap::Value cap;
     76    typename CostMap::Value co;
     77    while (is >> c) {
    7478      switch (c) {
    75       case 'c': //comment
    76         getline(is, str);
    77         break;
    78       case 'p': //problem definition
     79      case 'c': // comment line
     80        getline(is, str);
     81        break;
     82      case 'p': // problem definition line
    7983        is >> problem >> n >> m;
    8084        getline(is, str);
    81         nodes.resize(n+1);
    82         for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
    83         break;
    84       case 'n': //node definition
    85         if (problem=="sp") { //shortest path problem
    86           is >> i;
    87           getline(is, str);
    88           s=nodes[i];
    89         }
    90         if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
    91           is >> i >> d;
    92           getline(is, str);
    93           if (d=='s') s=nodes[i];
    94           if (d=='t') t=nodes[i];
    95         }
    96         break;
    97       case 'a':
    98         if ( problem == "max" || problem == "sp") {
    99           is >> i >> j >> _cap;
    100           getline(is, str);
    101           e=g.addEdge(nodes[i], nodes[j]);
    102           //capacity.update();
    103           capacity.set(e, _cap);
    104         } else {
    105           if ( problem == "min" ) {
    106             is >> i >> j >> _cap >> _cost;
    107             getline(is, str);
    108             e=g.addEdge(nodes[i], nodes[j]);
    109             //capacity.update();
    110             capacity.set(e, _cap);
    111             //cost.update();
    112             cost.set(e, _cost);
    113           } else {
    114             is >> i >> j;
    115             getline(is, str);
    116             g.addEdge(nodes[i], nodes[j]);
    117           }
    118         }
     85        if (problem != "min") return;
     86        nodes.resize(n + 1);
     87        for (int k = 1; k <= n; ++k) {
     88          nodes[k] = g.addNode();
     89          supply[nodes[k]] = 0;
     90        }
     91        break;
     92      case 'n': // node definition line
     93        is >> i >> sup;
     94        getline(is, str);
     95        supply.set(nodes[i], sup);
     96        break;
     97      case 'a': // edge (arc) definition line
     98        is >> i >> j >> low >> cap >> co;
     99        getline(is, str);
     100        e = g.addEdge(nodes[i], nodes[j]);
     101        lower.set(e, low);
     102        if (cap >= 0)
     103          capacity.set(e, cap);
     104        else
     105          capacity.set(e, -1);
     106        cost.set(e, co);
    119107        break;
    120108      }
    … …  
    122110  }
    123111
    124 
    125   /// Dimacs max flow reader function.
    126 
    127   /// This function reads a max flow instance from dimacs format,
    128   /// i.e. from dimacs files having a line starting with
    129   ///\code
    130   /// p "max"
    131   ///\endcode
    132   ///At the beginning \c g is cleared by \c g.clear(). The
    133   /// edge capacities are written to \c capacity and \c s and \c t are
     112  /// DIMACS max flow reader function.
     113  ///
     114  /// This function reads a max flow instance from DIMACS format,
     115  /// i.e. from DIMACS files having a line starting with
     116  /// \code
     117  ///   p max
     118  /// \endcode
     119  /// At the beginning \c g is cleared by \c g.clear(). The edge
     120  /// capacities are written to \c capacity and \c s and \c t are
    134121  /// set to the source and the target nodes.
    135122  ///
    … …  
    138125  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
    139126                  typename Graph::Node &s, typename Graph::Node &t) {
    140     NullMap<typename Graph::Edge, int> n;
    141     readDimacs(is, g, capacity, s, t, n);
    142   }
    143 
    144 
    145   /// Dimacs shortest path reader function.
    146 
    147   /// This function reads a shortest path instance from dimacs format,
    148   /// i.e. from dimacs files having a line starting with
    149   ///\code
    150   /// p "sp"
    151   ///\endcode
     127    g.clear();
     128    std::vector<typename Graph::Node> nodes;
     129    typename Graph::Edge e;
     130    std::string problem;
     131    char c, d;
     132    int n, m;
     133    int i, j;
     134    typename CapacityMap::Value _cap;
     135    std::string str;
     136    while (is >> c) {
     137      switch (c) {
     138      case 'c': // comment line
     139        getline(is, str);
     140        break;
     141      case 'p': // problem definition line
     142        is >> problem >> n >> m;
     143        getline(is, str);
     144        nodes.resize(n + 1);
     145        for (int k = 1; k <= n; ++k)
     146          nodes[k] = g.addNode();
     147        break;
     148      case 'n': // node definition line
     149        if (problem == "sp") { // shortest path problem
     150          is >> i;
     151          getline(is, str);
     152          s = nodes[i];
     153        }
     154        if (problem == "max") { // max flow problem
     155          is >> i >> d;
     156          getline(is, str);
     157          if (d == 's') s = nodes[i];
     158          if (d == 't') t = nodes[i];
     159        }
     160        break;
     161      case 'a': // edge (arc) definition line
     162        if (problem == "max" || problem == "sp") {
     163          is >> i >> j >> _cap;
     164          getline(is, str);
     165          e = g.addEdge(nodes[i], nodes[j]);
     166          capacity.set(e, _cap);
     167        } else {
     168          is >> i >> j;
     169          getline(is, str);
     170          g.addEdge(nodes[i], nodes[j]);
     171        }
     172        break;
     173      }
     174    }
     175  }
     176
     177  /// DIMACS shortest path reader function.
     178  ///
     179  /// This function reads a shortest path instance from DIMACS format,
     180  /// i.e. from DIMACS files having a line starting with
     181  /// \code
     182  ///   p sp
     183  /// \endcode
    152184  /// At the beginning \c g is cleared by \c g.clear(). The edge
    153185  /// capacities are written to \c capacity and \c s is set to the
    … …  
    158190  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
    159191                  typename Graph::Node &s) {
    160     NullMap<typename Graph::Edge, int> n;
    161     readDimacs(is, g, capacity, s, s, n);
    162   }
    163 
    164 
    165   /// Dimacs capacitated graph reader function.
    166 
     192    readDimacs(is, g, capacity, s, s);
     193  }
     194
     195  /// DIMACS capacitated graph reader function.
     196  ///
    167197  /// This function reads an edge capacitated graph instance from
    168   /// dimacs format. At the beginning \c g is cleared by \c g.clear()
     198  /// DIMACS format. At the beginning \c g is cleared by \c g.clear()
    169199  /// and the edge capacities are written to \c capacity.
    170200  ///
    … …  
    173203  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
    174204    typename Graph::Node u;
    175     NullMap<typename Graph::Edge, int> n;
    176     readDimacs(is, g, capacity, u, u, n);
    177   }
    178 
    179 
    180   /// Dimacs plain graph reader function.
    181 
     205    readDimacs(is, g, capacity, u, u);
     206  }
     207
     208  /// DIMACS plain graph reader function.
     209  ///
    182210  /// This function reads a graph without any designated nodes and
    183   /// maps from dimacs format, i.e. from dimacs files having a line
     211  /// maps from DIMACS format, i.e. from DIMACS files having a line
    184212  /// starting with
    185   ///\code
    186   /// p "mat"
    187   ///\endcode
    188   /// At the beginning \c g is cleared
    189   /// by \c g.clear().
     213  /// \code
     214  ///   p mat
     215  /// \endcode
     216  /// At the beginning \c g is cleared by \c g.clear().
    190217  ///
    191218  /// \author Marton Makai
    … …  
    194221    typename Graph::Node u;
    195222    NullMap<typename Graph::Edge, int> n;
    196     readDimacs(is, g, n, u, u, n);
     223    readDimacs(is, g, n, u, u);
    197224  }
    198225 
    199 
    200 
    201  
    202   /// write matching problem
     226  /// DIMACS plain graph writer function.
     227  ///
     228  /// This function writes a graph without any designated nodes and
     229  /// maps into DIMACS format, i.e. into DIMACS file having a line
     230  /// starting with
     231  /// \code
     232  ///   p mat
     233  /// \endcode
     234  ///
     235  /// \author Marton Makai
    203236  template<typename Graph>
    204237  void writeDimacs(std::ostream& os, const Graph &g) {
    … …  
    206239    typedef typename Graph::EdgeIt EdgeIt; 
    207240   
     241    os << "c matching problem" << std::endl;
     242    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
     243
    208244    typename Graph::template NodeMap<int> nodes(g);
    209 
    210     os << "c matching problem" << std::endl;
    211 
    212     int i=1;
    213     for(NodeIt v(g); v!=INVALID; ++v) {
     245    int i = 1;
     246    for(NodeIt v(g); v != INVALID; ++v) {
    214247      nodes.set(v, i);
    215248      ++i;
    216249    }   
    217    
    218     os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
    219 
    220     for(EdgeIt e(g); e!=INVALID; ++e) {
     250    for(EdgeIt e(g); e != INVALID; ++e) {
    221251      os << "a " << nodes[g.source(e)] << " " << nodes[g.target(e)] << std::endl;
    222252    }
    223 
    224253  }
    225254
Note: See TracChangeset for help on using the changeset viewer.