COIN-OR::LEMON - Graph Library

Changeset 575:bdf7fb750e0e in lemon-0.x


Ignore:
Timestamp:
05/07/04 12:34:36 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@751
Message:

Docs added

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/dimacs.h

    r549 r575  
    88#include <hugo/maps.h>
    99
     10/// \ingroup misc
    1011/// \file
    1112/// \brief Dimacs file format reader.
     
    1314namespace hugo {
    1415
    15   /// Dimacs flow file format reader function.
    16 
    17   /// This function reads a flow instance from dimacs flow format.
    18   /// At the beginning \c g is cleared by \c g.clear().
    19   /// If the data coming from \c is is a max flow problem instance, then
    20   /// \c s and \c t will be respectively the source and target nodes
    21   /// and \c capacity will contain the edge capacities.
    22   /// If the data is a shortest path problem instance then \c s will be the
    23   /// source node and \c capacity will contain the edge lengths.
    24   ///
    25   ///\author Marton Makai
    26   template<typename Graph, typename CapacityMap>
    27   void readDimacsMaxFlow(std::istream& is, Graph &g,
    28                          typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
    29     g.clear();
    30     int cap;
    31     char d;
    32     std::string problem;
    33     char c;
    34     int i, j;
    35     std::string str;
    36     int n, m;
    37     typename Graph::Edge e;
    38     std::vector<typename Graph::Node> nodes;
    39     while (is>>c) {
    40       switch (c) {
    41       case 'c': //comment
    42         getline(is, str);
    43         break;
    44       case 'p': //problem definition
    45         is >> problem >> n >> m;
    46         getline(is, str);
    47         nodes.resize(n+1);
    48         for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
    49         break;
    50       case 'n': //node definition
    51         if (problem=="sp") { //shortest path problem
    52           is >> i;
    53           getline(is, str);
    54           s=nodes[i];
    55         }
    56         if (problem=="max") { //max flow problem
    57           is >> i >> d;
    58           getline(is, str);
    59           if (d=='s') s=nodes[i];
    60           if (d=='t') t=nodes[i];
    61         }
    62         break;
    63       case 'a':
    64         is >> i >> j >> cap;
    65         getline(is, str);
    66         e=g.addEdge(nodes[i], nodes[j]);
    67         capacity.update();
    68         capacity.set(e, cap);
    69         break;
    70       }
    71     }
    72   }
    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   }
    81 
    82   /// sg problem
    83   template<typename Graph, typename CapacityMap>
    84   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
    85     typename Graph::Node u;
    86     NullMap<typename Graph::Edge, int> n;
    87     readDimacs(is, g, capacity, u, u, n);
    88   }
    89 
    90   /// shortest path problem
    91   template<typename Graph, typename CapacityMap>
    92   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
    93                   typename Graph::Node &s) {
    94     NullMap<typename Graph::Edge, int> n;
    95     readDimacs(is, g, capacity, s, s, n);
    96   }
    97 
    98   /// max flow problem
    99   template<typename Graph, typename CapacityMap>
    100   void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
    101                   typename Graph::Node &s, typename Graph::Node &t) {
    102     NullMap<typename Graph::Edge, int> n;
    103     readDimacs(is, g, capacity, s, t, n);
    104   }
    105 
    106   /// min cost flow problem
     16
     17  /// \addtogroup misc
     18  /// @{
     19
     20  /// Dimacs min cost flow reader function.
     21
     22  /// This function reads a min cost flow instance from dimacs format,
     23  /// i.e. from dimacs files having a line starting with \c p \c "min".
     24  /// At the beginning \c g is cleared by \c g.clear(). The edge
     25  /// capacities are written to \c capacity, \c s and \c t are set to
     26  /// the source and the target nodes resp. and the cost of the edges
     27  /// are written to \c cost.
     28  ///
     29  /// \author Marton Makai
    10730  template<typename Graph, typename CapacityMap, typename CostMap>
    10831  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
     
    14568        break;
    14669      case 'a':
    147         if ( problem == "mat" ) {
    148           is >> i >> j;
    149           getline(is, str);
    150           g.addEdge(nodes[i], nodes[j]);
    151         }
    15270        if ( problem == "max" || problem == "sp") {
    15371          is >> i >> j >> _cap;
     
    15674          capacity.update();
    15775          capacity.set(e, _cap);
    158         }
    159         if ( problem == "min" ) {
    160           is >> i >> j >> _cap >> _cost;
    161           getline(is, str);
    162           e=g.addEdge(nodes[i], nodes[j]);
    163           capacity.update();
    164           capacity.set(e, _cap);
    165           cost.update();
    166           cost.set(e, _cost);
     76        } else {
     77          if ( problem == "min" ) {
     78            is >> i >> j >> _cap >> _cost;
     79            getline(is, str);
     80            e=g.addEdge(nodes[i], nodes[j]);
     81            capacity.update();
     82            capacity.set(e, _cap);
     83            cost.update();
     84            cost.set(e, _cost);
     85          } else {
     86            is >> i >> j;
     87            getline(is, str);
     88            g.addEdge(nodes[i], nodes[j]);
     89          }
    16790        }
    16891        break;
     
    17093    }
    17194  }
     95
     96
     97  /// Dimacs max flow reader function.
     98
     99  /// This function reads a max flow instance from dimacs format,
     100  /// i.e. from dimacs files having a line starting with \c p \c
     101  /// "max".  At the beginning \c g is cleared by \c g.clear(). The
     102  /// edge capacities are written to \c capacity and \c s and \c t are
     103  /// set to the source and the target nodes.
     104  ///
     105  /// \author Marton Makai
     106  template<typename Graph, typename CapacityMap>
     107  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
     108                  typename Graph::Node &s, typename Graph::Node &t) {
     109    NullMap<typename Graph::Edge, int> n;
     110    readDimacs(is, g, capacity, s, t, n);
     111  }
     112
     113
     114  /// Dimacs shortest path reader function.
     115
     116  /// This function reads a shortest path instance from dimacs format,
     117  /// i.e. from dimacs files having a line starting with \c p \c "sp".
     118  /// At the beginning \c g is cleared by \c g.clear(). The edge
     119  /// capacities are written to \c capacity and \c s is set to the
     120  /// source node.
     121  ///
     122  /// \author Marton Makai
     123  template<typename Graph, typename CapacityMap>
     124  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
     125                  typename Graph::Node &s) {
     126    NullMap<typename Graph::Edge, int> n;
     127    readDimacs(is, g, capacity, s, s, n);
     128  }
     129
     130
     131  /// Dimacs capacitated graph reader function.
     132
     133  /// This function reads an edge capacitated graph instance from
     134  /// dimacs format.  At the beginning \c g is cleared by \c g.clear()
     135  /// and the edge capacities are written to \c capacity.
     136  ///
     137  /// \author Marton Makai
     138  template<typename Graph, typename CapacityMap>
     139  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
     140    typename Graph::Node u;
     141    NullMap<typename Graph::Edge, int> n;
     142    readDimacs(is, g, capacity, u, u, n);
     143  }
     144
     145
     146  /// Dimacs plain graph reader function.
     147
     148  /// This function reads a graph without any designated nodes and
     149  /// maps from dimacs format, i.e. from dimacs files having a line
     150  /// starting with \c p \c "mat".  At the beginning \c g is cleared
     151  /// by \c g.clear().
     152  ///
     153  /// \author Marton Makai
     154  template<typename Graph>
     155  void readDimacs(std::istream& is, Graph &g) {
     156    typename Graph::Node u;
     157    NullMap<typename Graph::Edge, int> n;
     158    readDimacs(is, g, n, u, u, n);
     159  }
     160 
    172161
    173162
     
    200189
    201190
     191  /// @}
    202192
    203193} //namespace hugo
    204194
    205195#endif //HUGO_DIMACS_H
     196
     197//  template<typename Graph, typename CapacityMap>
     198//   void readDimacsMaxFlow(std::istream& is, Graph &g,
     199//                       typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
     200//     g.clear();
     201//     int cap;
     202//     char d;
     203//     std::string problem;
     204//     char c;
     205//     int i, j;
     206//     std::string str;
     207//     int n, m;
     208//     typename Graph::Edge e;
     209//     std::vector<typename Graph::Node> nodes;
     210//     while (is>>c) {
     211//       switch (c) {
     212//       case 'c': //comment
     213//      getline(is, str);
     214//      break;
     215//       case 'p': //problem definition
     216//      is >> problem >> n >> m;
     217//      getline(is, str);
     218//      nodes.resize(n+1);
     219//      for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
     220//      break;
     221//       case 'n': //node definition
     222//      if (problem=="sp") { //shortest path problem
     223//        is >> i;
     224//        getline(is, str);
     225//        s=nodes[i];
     226//      }
     227//      if (problem=="max") { //max flow problem
     228//        is >> i >> d;
     229//        getline(is, str);
     230//        if (d=='s') s=nodes[i];
     231//        if (d=='t') t=nodes[i];
     232//      }
     233//      break;
     234//       case 'a':
     235//      is >> i >> j >> cap;
     236//      getline(is, str);
     237//      e=g.addEdge(nodes[i], nodes[j]);
     238//      capacity.update();
     239//      capacity.set(e, cap);
     240//      break;
     241//       }
     242//     }
     243//   }
Note: See TracChangeset for help on using the changeset viewer.