lemon/karp_mmc.h
changeset 969 cfdbf1574403
parent 864 d3ea191c3412
child 1002 f63ba40a60f4
equal deleted inserted replaced
0:9de9f6214db8 1:265ef7dda9de
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
   189     PathDataNodeMap _data;
   189     PathDataNodeMap _data;
   190     // The processed nodes in the last round
   190     // The processed nodes in the last round
   191     std::vector<Node> _process;
   191     std::vector<Node> _process;
   192 
   192 
   193     Tolerance _tolerance;
   193     Tolerance _tolerance;
   194     
   194 
   195     // Infinite constant
   195     // Infinite constant
   196     const LargeCost INF;
   196     const LargeCost INF;
   197 
   197 
   198   public:
   198   public:
   199 
   199 
   337     /// \return \c true if a directed cycle exists in the digraph.
   337     /// \return \c true if a directed cycle exists in the digraph.
   338     bool findCycleMean() {
   338     bool findCycleMean() {
   339       // Initialization and find strongly connected components
   339       // Initialization and find strongly connected components
   340       init();
   340       init();
   341       findComponents();
   341       findComponents();
   342       
   342 
   343       // Find the minimum cycle mean in the components
   343       // Find the minimum cycle mean in the components
   344       for (int comp = 0; comp < _comp_num; ++comp) {
   344       for (int comp = 0; comp < _comp_num; ++comp) {
   345         if (!initComponent(comp)) continue;
   345         if (!initComponent(comp)) continue;
   346         processRounds();
   346         processRounds();
   347         updateMinMean();
   347         updateMinMean();
   487     bool initComponent(int comp) {
   487     bool initComponent(int comp) {
   488       _nodes = &(_comp_nodes[comp]);
   488       _nodes = &(_comp_nodes[comp]);
   489       int n = _nodes->size();
   489       int n = _nodes->size();
   490       if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
   490       if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
   491         return false;
   491         return false;
   492       }      
   492       }
   493       for (int i = 0; i < n; ++i) {
   493       for (int i = 0; i < n; ++i) {
   494         _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
   494         _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
   495       }
   495       }
   496       return true;
   496       return true;
   497     }
   497     }