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


Ignore:
Timestamp:
03/22/07 16:40:50 (16 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

Files:
5 edited

Legend:

Unmodified
Added
Removed

  • demo/dim_to_dot.cc

    r2391 r2413  
    1818
    1919///\file
    20 ///\brief Dim (Dimacs) to Dot (Graphviz) converter
     20///\brief Dim (DIMACS) to Dot (Graphviz) converter
    2121///
    22 /// This program can convert the dimacs format to graphviz dot format.
     22/// This program can convert the DIMACS format to Graphviz format.
    2323///
    24 /// Use a DIMACS max flow file as stdin.
     24/// <tt>dim_to_dot dimacs_max_flow_file > dot_output_file</tt>
    2525///
    26 /// <tt>dim_to_dot < dimacs_max_flow_file > dot_output_file</tt>
    27 ///
    28 /// This program makes a dot file from a dimacs max flow file.
    29 /// This program can be an aid in making up to date visualized documantation
    30 /// of demo programs.
     26/// This program makes a dot file from a DIMACS max flow file.
     27/// This program can be an aid in making up to date visualized
     28/// documantation of demo programs.
    3129///
    3230/// \include dim_to_dot.cc
    … …  
    4745  if(argc<2)
    4846  {
    49       std::cerr << "USAGE: sub_graph_adaptor_demo input_file.dim" << std::endl;
     47      std::cerr << "USAGE: dim_to_dot input_file.dim" << std::endl;
    5048      std::cerr << "The file 'input_file.dim' has to contain a max flow instance in DIMACS format (e.g. sub_graph_adaptor_demo.dim is such a file)." << std::endl;
    5149      return 0;
    5250  }
    53 
    5451
    5552  //input stream to read the graph from

  • 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

  • lemon/min_mean_cycle.h

    r2409 r2413  
    3434  /// @{
    3535
    36   /// \brief Implementation of Karp's algorithm for finding a 
    37   /// minimum mean cycle.
     36  /// \brief Implementation of Karp's algorithm for finding a
     37  /// minimum mean (directed) cycle.
    3838  ///
    39   /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's 
    40   /// algorithm for finding a minimum mean cycle.
     39  /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's
     40  /// algorithm for finding a minimum mean (directed) cycle.
    4141  ///
    4242  /// \param Graph The directed graph type the algorithm runs on.
    … …  
    5858    typedef typename Graph::Edge Edge;
    5959    typedef typename Graph::EdgeIt EdgeIt;
    60     typedef typename Graph::InEdgeIt InEdgeIt;
    6160    typedef typename Graph::OutEdgeIt OutEdgeIt;
    6261
    6362    typedef typename LengthMap::Value Length;
    64    
     63
    6564    typedef typename Graph::template NodeMap<int> IntNodeMap;
    6665    typedef typename Graph::template NodeMap<Edge> PredNodeMap;
    … …  
    7069
    7170  protected:
    72  
     71
    7372    /// \brief Data sturcture for path data.
    74     struct PathData {
     73    struct PathData
     74    {
    7575      bool found;
    7676      Length dist;
    7777      Edge pred;
    78       PathData(bool _found = false, Length _dist = 0) : 
     78      PathData(bool _found = false, Length _dist = 0) :
    7979        found(_found), dist(_dist), pred(INVALID) {}
    80       PathData(bool _found, Length _dist, Edge _pred) : 
     80      PathData(bool _found, Length _dist, Edge _pred) :
    8181        found(_found), dist(_dist), pred(_pred) {}
    8282    };
    83    
     83
    8484  private:
    85  
    86     typedef typename Graph::template NodeMap<std::vector<PathData> > PathVectorNodeMap;
    87  
     85
     86    typedef typename Graph::template NodeMap<std::vector<PathData> >
     87      PathDataNodeMap;
     88
    8889  protected:
    8990
    … …  
    9394    /// component. dmap[v][k] is the length of a shortest directed walk
    9495    /// to node v from the starting node containing exactly k edges.
    95     PathVectorNodeMap dmap;
     96    PathDataNodeMap dmap;
    9697   
    9798    /// \brief The directed graph the algorithm runs on.
    … …  
    104105    /// \brief The number of edges in the found cycle.
    105106    int cycle_size;
     107    /// \brief A node for obtaining a minimum mean cycle.
     108    Node cycle_node;
     109
    106110    /// \brief The found cycle.
    107111    Path *cycle_path;
    108     /// \brief The found cycle.
     112    /// \brief The algorithm uses local \ref lemon::Path "Path"
     113    /// structure to store the found cycle.
    109114    bool local_path;
    110115   
    … …  
    113118    /// \brief The number of strongly connected components.
    114119    int comp_num;
    115     /// \brief %Counter for identifying the current component.
     120    /// \brief Counter for identifying the current component.
    116121    int comp_cnt;
    117122    /// \brief Nodes of the current component.
    … …  
    130135    MinMeanCycle( const Graph& _graph,
    131136                  const LengthMap& _length ) :
    132       graph(_graph), length(_length), dmap(_graph),
    133       cycle_length(0), cycle_size(-1), comp(_graph),
     137      graph(_graph), length(_length), dmap(_graph), comp(_graph),
     138      cycle_length(0), cycle_size(-1), cycle_node(INVALID),
    134139      cycle_path(NULL), local_path(false)
    135140    { }
    … …  
    141146
    142147  protected:
    143    
    144     /// \brief Initializes the internal data structures.
    145     void init() {
    146       comp_num = stronglyConnectedComponents(graph, comp);
    147       if (!cycle_path) {
    148         local_path = true;
    149         cycle_path = new Path;
    150       }
    151     }
    152148
    153149    /// \brief Initializes the internal data structures for the current
    … …  
    159155        if (comp[v] == comp_cnt) nodes.push_back(v);
    160156      }
    161 
    162157      // Creating vectors for all nodes
    163158      int n = nodes.size();
    … …  
    167162    }
    168163   
    169     /// \brief Processes all rounds of computing required path data.
     164    /// \brief Processes all rounds of computing required path data for
     165    /// the current component.
    170166    void processRounds() {
    171167      dmap[nodes[0]][0] = PathData(true, 0);
    172168      process.clear();
    173       for (OutEdgeIt oe(graph, nodes[0]); oe != INVALID; ++oe) {
    174         Node v = graph.target(oe);
     169      // Processing the first round
     170      for (OutEdgeIt e(graph, nodes[0]); e != INVALID; ++e) {
     171        Node v = graph.target(e);
    175172        if (comp[v] != comp_cnt || v == nodes[0]) continue;
    176         dmap[v][1] = PathData(true, length[oe], oe);
     173        dmap[v][1] = PathData(true, length[e], e);
    177174        process.push_back(v);
    178175      }
     176      // Processing other rounds
    179177      int n = nodes.size(), k;
    180178      for (k = 2; k <= n && process.size() < n; ++k) {
    … …  
    191189      NodeVector next;
    192190      for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) {
    193         for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
    194           Node v = graph.target(oe);
     191        for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
     192          Node v = graph.target(e);
    195193          if (comp[v] != comp_cnt) continue;
    196           if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
    197             if (!dmap[v][k].found) next.push_back(v);
    198             dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
     194          if (!dmap[v][k].found) {
     195            next.push_back(v);
     196            dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
     197          }
     198          else if (dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist) {
     199            dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
    199200          }
    200201        }
    … …  
    207208    void processNextFullRound(int k) {
    208209      for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {
    209         for (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
    210           Node v = graph.target(oe);
     210        for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
     211          Node v = graph.target(e);
    211212          if (comp[v] != comp_cnt) continue;
    212           if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
    213             dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
     213          if ( !dmap[v][k].found ||
     214               dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist ) {
     215            dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
    214216          }
    215217        }
    … …  
    217219    }
    218220   
    219     /// \brief Finds the minimum cycle mean value according to the path
    220     /// data stored in \ref dmap.
    221     ///
    222     /// Finds the minimum cycle mean value according to the path data
    223     /// stored in \ref dmap.
    224     ///
    225     /// \retval min_length The total length of the found cycle.
    226     /// \retval min_size The number of edges in the found cycle.
    227     /// \retval min_node A node for obtaining a critical cycle.
    228     ///
    229     /// \return \c true if a cycle exists in the graph.
    230     bool findMinCycleMean(Length &min_length, int &min_size, Node &min_node) {
     221    /// \brief Finds the minimum cycle mean value in the current
     222    /// component.
     223    bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) {
    231224      bool found_min = false;
    232225      for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
     226        int n = nodes.size();
     227        if (!dmap[*vi][n].found) continue;
    233228        Length len;
    234229        int size;
    235230        bool found_one = false;
    236         int n = nodes.size();
    237231        for (int k = 0; k < n; ++k) {
     232          if (!dmap[*vi][k].found) continue;
    238233          Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist;
    239234          int _size = n - k;
    240           if ( dmap[*vi][n].found && dmap[*vi][k].found && (!found_one || len * _size < _len * size) ) {
     235          if (!found_one || len * _size < _len * size) {
    241236            found_one = true;
    242237            len = _len;
    … …  
    244239          }
    245240        }
    246         if (found_one && (!found_min || len * min_size < min_length * size)) {
     241        if ( found_one &&
     242             (!found_min || len * min_size < min_length * size) ) {
    247243          found_min = true;
    248244          min_length = len;
    … …  
    254250    }
    255251   
    256     /// \brief Finds a critical (minimum mean) cycle according to the
    257     /// path data stored in \ref dmap.
    258     void findCycle(const Node &min_n) {
    259       IntNodeMap reached(graph, -1);
    260       int r = reached[min_n] = dmap[min_n].size() - 1;
    261       Node u = graph.source(dmap[min_n][r].pred);
    262       while (reached[u] < 0) {
    263         reached[u] = --r;
    264         u = graph.source(dmap[u][r].pred);
    265       }
    266       r = reached[u];
    267       Edge ce = dmap[u][r].pred;
    268       cycle_path->addFront(ce);
    269       Node v;
    270       while ((v = graph.source(ce)) != u) {
    271         ce = dmap[v][--r].pred;
    272         cycle_path->addFront(ce);
    273       }
    274     }
    275    
    276   public:
    277 
     252  public: 
     253   
    278254    /// \brief Runs the algorithm.
    279255    ///
    … …  
    281257    ///
    282258    /// \return \c true if a cycle exists in the graph.
     259    ///
     260    /// \note Apart from the return value, m.run() is just a shortcut
     261    /// of the following code.
     262    /// \code
     263    ///   m.init();
     264    ///   m.findMinMean();
     265    ///   m.findCycle();
     266    /// \endcode
    283267    bool run() {
    284268      init();
    285       // Searching for the minimum mean cycle in all components
    286       bool found_cycle = false;
    287       Node cycle_node;
     269      findMinMean();
     270      return findCycle();
     271    }
     272   
     273    /// \brief Initializes the internal data structures.
     274    void init() {
     275      comp_num = stronglyConnectedComponents(graph, comp);
     276      if (!cycle_path) {
     277        local_path = true;
     278        cycle_path = new Path;
     279      }
     280    }
     281
     282    /// \brief Finds the minimum cycle mean value in the graph.
     283    ///
     284    /// Computes all the required path data and finds the minimum cycle
     285    /// mean value in the graph.
     286    ///
     287    /// \return \c true if a cycle exists in the graph.
     288    ///
     289    /// \pre \ref init() must be called before using this function.
     290    bool findMinMean() {
     291      cycle_node = INVALID;
    288292      for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {
    289      
    290293        initCurrent();
    291294        processRounds();
    … …  
    294297        int min_size;
    295298        Node min_node;
    296         bool found_min = findMinCycleMean(min_length, min_size, min_node);
     299        bool found_min = findCurrentMin(min_length, min_size, min_node);
    297300       
    298         if ( found_min && (!found_cycle || min_length * cycle_size  < cycle_length * min_size) ) {
    299           found_cycle = true;
     301        if ( found_min && (cycle_node == INVALID ||
     302             min_length * cycle_size < cycle_length * min_size) ) {
    300303          cycle_length = min_length;
    301304          cycle_size = min_size;
    … …  
    303306        }
    304307      }
    305       if (found_cycle) findCycle(cycle_node);
    306       return found_cycle;
    307     }
    308    
    309     /// \brief Returns the total length of the found critical cycle.
    310     ///
    311     /// Returns the total length of the found critical cycle.
     308      return (cycle_node != INVALID);
     309    }
     310   
     311    /// \brief Finds a critical (minimum mean) cycle.
     312    ///
     313    /// Finds a critical (minimum mean) cycle using the path data
     314    /// stored in \ref dmap.
     315    ///
     316    /// \return \c true if a cycle exists in the graph.
     317    ///
     318    /// \pre \ref init() and \ref findMinMean() must be called before
     319    /// using this function.
     320    bool findCycle() {
     321      if (cycle_node == INVALID) return false;
     322      cycle_length = 0;
     323      cycle_size = 0;
     324      IntNodeMap reached(graph, -1);
     325      int r = reached[cycle_node] = dmap[cycle_node].size() - 1;
     326      Node u = graph.source(dmap[cycle_node][r].pred);
     327      while (reached[u] < 0) {
     328        reached[u] = --r;
     329        u = graph.source(dmap[u][r].pred);
     330      }
     331      r = reached[u];
     332      Edge e = dmap[u][r].pred;
     333      cycle_path->addFront(e);
     334      cycle_length = cycle_length + length[e];
     335      ++cycle_size;
     336      Node v;
     337      while ((v = graph.source(e)) != u) {
     338        e = dmap[v][--r].pred;
     339        cycle_path->addFront(e);
     340        cycle_length = cycle_length + length[e];
     341        ++cycle_size;
     342      }
     343      return true;
     344    }
     345
     346    /// \brief Resets the internal data structures.
     347    ///
     348    /// Resets the internal data structures so that \ref findMinMean()
     349    /// and \ref findCycle() can be called again (e.g. when the
     350    /// underlaying graph has been modified).
     351    void reset() {
     352      for (NodeIt u(graph); u != INVALID; ++u)
     353        dmap[u].clear();
     354      cycle_node = INVALID;
     355      if (cycle_path) cycle_path->clear();
     356      comp_num = stronglyConnectedComponents(graph, comp);
     357    }
     358   
     359    /// \brief Returns the total length of the found cycle.
     360    ///
     361    /// Returns the total length of the found cycle.
    312362    ///
    313363    /// \pre \ref run() must be called before using this function.
    … …  
    316366    }
    317367   
    318     /// \brief Returns the number of edges in the found critical
    319     /// cycle.
    320     ///
    321     /// Returns the number of edges in the found critical cycle.
     368    /// \brief Returns the number of edges in the found cycle.
     369    ///
     370    /// Returns the number of edges in the found cycle.
    322371    ///
    323372    /// \pre \ref run() must be called before using this function.
    … …  
    326375    }
    327376   
    328     /// \brief Returns the mean length of the found critical cycle.
    329     ///
    330     /// Returns the mean length of the found critical cycle.
     377    /// \brief Returns the mean length of the found cycle.
     378    ///
     379    /// Returns the mean length of the found cycle.
    331380    ///
    332381    /// \pre \ref run() must be called before using this function.
    333382    ///
    334383    /// \warning LengthMap::Value must be convertible to double.
     384    ///
     385    /// \note m.minMean() is just a shortcut of the following code.
     386    /// \code
     387    ///   return m.cycleEdgeNum() / double(m.cycleLength());
     388    /// \endcode
    335389    double minMean() const {
    336       return (double)cycle_length / (double)cycle_size;
     390      return cycle_length / (double)cycle_size;
    337391    }
    338392
    339393    /// \brief Returns a const reference to the \ref lemon::Path "Path"
    340     /// structure of the found flow.
     394    /// structure of the found cycle.
    341395    ///
    342396    /// Returns a const reference to the \ref lemon::Path "Path"
    343     /// structure of the found flow.
     397    /// structure of the found cycle.
    344398    ///
    345399    /// \pre \ref run() must be called before using this function.

  • lemon/tolerance.h

    r2391 r2413  
    306306    static Value zero() {return 0;}
    307307  };
     308 
     309
     310  ///Long integer specialization of \ref Tolerance.
     311
     312  ///Long integer specialization of \ref Tolerance.
     313  ///\sa Tolerance
     314  template<>
     315  class Tolerance<long int>
     316  {
     317  public:
     318    ///\e
     319    typedef long int Value;
     320
     321    ///\name Comparisons
     322    ///See \ref Tolerance for more details.
     323
     324    ///@{
     325
     326    ///Returns \c true if \c a is \e surely strictly less than \c b
     327    static bool less(Value a,Value b) { return a<b;}
     328    ///Returns \c true if \c a is \e surely different from \c b
     329    static bool different(Value a,Value b) { return a!=b; }
     330    ///Returns \c true if \c a is \e surely positive
     331    static bool positive(Value a) { return 0<a; }
     332    ///Returns \c true if \c a is \e surely negative
     333    static bool negative(Value a) { return 0>a; }
     334    ///Returns \c true if \c a is \e surely non-zero
     335    static bool nonZero(Value a) { return a!=0;};
     336
     337    ///@}
     338
     339    ///Returns zero
     340    static Value zero() {return 0;}
     341  };
     342
     343  ///Unsigned long integer specialization of \ref Tolerance.
     344
     345  ///Unsigned long integer specialization of \ref Tolerance.
     346  ///\sa Tolerance
     347  template<>
     348  class Tolerance<unsigned long int>
     349  {
     350  public:
     351    ///\e
     352    typedef unsigned long int Value;
     353
     354    ///\name Comparisons
     355    ///See \ref Tolerance for more details.
     356
     357    ///@{
     358
     359    ///Returns \c true if \c a is \e surely strictly less than \c b
     360    static bool less(Value a,Value b) { return a<b;}
     361    ///Returns \c true if \c a is \e surely different from \c b
     362    static bool different(Value a,Value b) { return a!=b; }
     363    ///Returns \c true if \c a is \e surely positive
     364    static bool positive(Value a) { return 0<a; }
     365    ///Returns \c true if \c a is \e surely negative
     366    static bool negative(Value) { return false; }
     367    ///Returns \c true if \c a is \e surely non-zero
     368    static bool nonZero(Value a) { return a!=0;};
     369
     370    ///@}
     371
     372    ///Returns zero
     373    static Value zero() {return 0;}
     374  };
    308375
    309376#if defined __GNUC__ && !defined __STRICT_ANSI__

  • tools/dim_to_lgf.cc

    r2410 r2413  
    4747  typedef Graph::EdgeIt EdgeIt;
    4848  typedef Graph::NodeIt NodeIt;
    49   typedef Graph::EdgeMap<double> DoubleMap;
     49  typedef Graph::EdgeMap<double> DoubleEdgeMap;
     50  typedef Graph::NodeMap<double> DoubleNodeMap;
    5051
    5152  std::string inputName;
    … …  
    116117  if (mincostflow) {
    117118    Graph graph;
    118     Node s, t;
    119     DoubleMap cost(graph), capacity(graph);
    120     readDimacs(is, graph, capacity, s, t, cost);
     119    DoubleNodeMap supply(graph);
     120    DoubleEdgeMap lower(graph), capacity(graph), cost(graph);
     121    readDimacs(is, graph, supply, lower, capacity, cost);
    121122    GraphWriter<Graph>(os, graph).
     123      writeNodeMap("supply", supply).
     124      writeEdgeMap("lower", lower).
    122125      writeEdgeMap("capacity", capacity).
    123       writeNode("source", s).
    124       writeNode("target", t).
    125126      writeEdgeMap("cost", cost).
    126127      run();
    … …  
    128129    Graph graph;
    129130    Node s, t;
    130     DoubleMap capacity(graph);
     131    DoubleEdgeMap capacity(graph);
    131132    readDimacs(is, graph, capacity, s, t);
    132133    GraphWriter<Graph>(os, graph).
    … …  
    138139    Graph graph;
    139140    Node s;
    140     DoubleMap capacity(graph);
     141    DoubleEdgeMap capacity(graph);
    141142    readDimacs(is, graph, capacity, s);
    142143    GraphWriter<Graph>(os, graph).
    … …  
    146147  } else if (capacitated) {
    147148    Graph graph;
    148     DoubleMap capacity(graph);
     149    DoubleEdgeMap capacity(graph);
    149150    readDimacs(is, graph, capacity);
    150151    GraphWriter<Graph>(os, graph).
Note: See TracChangeset for help on using the changeset viewer.