COIN-OR::LEMON - Graph Library

Changeset 246:dc95ca4ebc7b in lemon-0.x for src/work/johanna/kruskal.h


Ignore:
Timestamp:
03/26/04 14:59:59 (16 years ago)
Author:
beckerjc
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@346
Message:

koztes valtozat

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/johanna/kruskal.h

    r218 r246  
    88namespace hugo {
    99
    10 
    11   template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap>
     10  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
     11  typename EdgeCostMap::ValueType
     12  kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
     13           RetEdgeBoolMap &ret_bool_map);
     14
     15  template <typename Graph, typename EdgeCostMap, typename RetIterator>
     16  typename EdgeCostMap::ValueType
     17  kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
     18           RetIterator ret_iterator);
     19
     20  // FIXME: ret_iterator nem lehet referencia!!!
     21
     22  template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap>
     23  typename EdgeCostPairVec::value_type::second_type
     24  kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
     25           RetEdgeBoolMap &ret_bool_map);
     26
     27  template <typename Graph, typename EdgeCostPairVec, typename RetIterator>
     28  typename EdgeCostPairVec::value_type::second_type
     29  kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
     30           RetIterator &ret_iterator);
     31
     32  template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap>
     33  int
     34  kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec,
     35           RetEdgeBoolMap &ret_bool_map);
     36
     37  template <typename Graph, typename EdgePairVec, typename RetIterator>
     38  int
     39  kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec,
     40           RetIterator &ret_iterator);
     41
     42
     43  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap,
     44            typename RetIterator>
     45  typename EdgeCostMap::ValueType
     46  kruskal7(Graph const& G, EdgeCostMap const& edge_costs,
     47           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
     48
     49  template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap,
     50            typename RetIterator>
     51  typename EdgeCostPairVec::value_type::second_type
     52  kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
     53           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
     54
     55  template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap,
     56            typename RetIterator>
     57  int
     58  kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec,
     59           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
     60
     61
     62
     63
     64  template <typename Graph, typename InputEdgeOrder, typename OutputObserver>
    1265  class MinCostTreeKruskal
    1366  {
     
    1770
    1871  public:
    19     typedef typename EdgeCostMap::ValueType EdgeCost;
    20     typedef std::pair<Edge, EdgeCost> EdgeCostPair;
    21     typedef std::vector<EdgeCostPair> EdgeCostVector;
     72    typedef typename InputEdgeOrder::ValueType EdgeCost;
    2273   
    2374  private:
    2475    Graph const &G;
    25     EdgeCostMap const &costmap;
    26     EdgeBoolMap& treemap;
    27    
    28     //template <typename EdgeCostPair>
    29     class comparePair {
    30     public:
    31       bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) {
    32         return a.second < b.second;
    33       }
    34     };
    35 
    36   public:
    37 
    38 
    39     MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap,
    40                        EdgeBoolMap& _treemap) : G(_G), costmap(_costmap),
    41                                                 treemap(_treemap) {}
     76    InputEdgeOrder const &edges;
     77    OutputObserver &out_obs;
     78
     79  public:
     80
     81
     82    MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges,
     83                       OutputObserver& _out_obs) :
     84      G(_G), edges(_edges), out_obs(_out_obs) {}
    4285 
    4386
    44     EdgeCost run()
    45     {
    46      EdgeCostVector rank;
    47      for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
    48         rank.push_back(make_pair(e, costmap.get(e)));
    49       }
    50      
    51       std::sort(rank.begin(), rank.end(), comparePair());
    52 
    53       return run(rank);
    54    
    55     }
    56 
    57     EdgeCost run(EdgeCostVector const &rank)
     87    EdgeCost run()
    5888    {
    5989      typedef typename Graph::NodeMap<int> NodeIntMap;
     
    6393     
    6494      EdgeCost tot_cost = 0;
    65       for (typename EdgeCostVector::const_iterator p = rank.begin();
    66            p!=rank.end(); ++p ) {
    67         if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
    68           treemap.set(p->first, true);
    69           tot_cost += p->second;
     95      for (typename InputEdgeOrder::const_iterator p = edges.begin();
     96           p!=edges.end(); ++p ) {
     97        if ( uf.joinComponents(G.head(edges.first(p)),
     98                               G.tail(edges.first(p))) ) {
     99          out_obs.setTrue(edges.first(p));
     100          tot_cost += edges.second(p);
    70101        }
    71102        else {
    72           treemap.set(p->first, false);
     103          out_obs.setFalse(edges.first(p));
    73104        }
    74105      }
    75106      return tot_cost;
    76 
    77     }
    78 
    79   };
     107    }
     108
     109  };
     110
     111 
     112  /* ** ** Output-objektumok (Observerek (?)) ** ** */
     113 
     114  template <typename BoolMap>
     115  class BoolMapOutput {
     116    BoolMap &bm;
     117    typedef typename BoolMap::KeyType KeyType;
     118
     119  public:
     120    BoolMapOutput(BoolMap &_bm) : bm(_bm) {}
     121
     122    void setTrue(KeyType const& k) { bm.set(k, true); }
     123    void setFalse(KeyType const& k) { bm.set(k, false); }
     124  };
     125
     126  template <typename Iterator>
     127  class SequenceOutput {
     128    Iterator &it;
     129
     130  public:
     131    SequenceOutput(Iterator &_it) : it(_it) {}
     132
     133    template<typename KeyType>
     134    void setTrue(KeyType const& k) { *it=k; ++it; }
     135    template<typename KeyType>
     136    void setFalse(KeyType const& k) {}
     137  };
     138
     139  template <typename BoolMap, typename Iterator>
     140  class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> {
     141    typedef BoolMapOutput<BoolMap> BMO;
     142    typedef SequenceOutput<Iterator> SO;
     143  public:
     144    CombinedOutput(BoolMap &_bm, Iterator &_it) :
     145      BMO(_bm), SO(_it) {}
     146
     147    template<typename KeyType>
     148    void setTrue(KeyType const& k) {
     149      BMO::setTrue(k);
     150      SO::setTrue(k);
     151    }
     152    template<typename KeyType>
     153    void setFalse(KeyType const& k) {
     154      BMO::setFalse(k);
     155      SO::setFalse(k);     
     156    }
     157  };
     158
     159
     160  /* ** ** InputSource -ok ** ** */
     161
     162  template<typename Key, typename Val>
     163  class PairVec : public std::vector< std::pair<Key,Val> > {
     164
     165  public:
     166    typedef std::vector< std::pair<Key,Val> > Parent;
     167    typedef Key KeyType;
     168    typedef Val ValueType;
     169    typedef std::pair<Key,Val> PairType;
     170
     171    typedef typename Parent::iterator iterator;
     172    typedef typename Parent::const_iterator const_iterator;
     173
     174
     175  private:
     176
     177    class comparePair {
     178    public:
     179      bool operator()(PairType const& a, PairType const& b) {
     180        return a.second < b.second;
     181      }
     182    };
     183
     184  public:
     185
     186    // FIXME: kell ez?
     187    // PairVec(Parent const& p) : Parent(p) {}
     188   
     189    void sort() {
     190      std::sort(begin(), end(), comparePair());
     191    }
     192
     193    // FIXME: nem nagyon illik ez ide...
     194    template<typename Graph, typename Map>
     195    void readGraphEdgeMap(Graph const& G, Map const& m) {
     196      typedef typename Graph::EdgeIt EdgeIt;
     197
     198      clear();
     199      for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
     200        push_back(make_pair(e, m[e]));
     201      }
     202
     203      sort();
     204    }
     205
     206    int alma() { return 5; /* FIXME */ }
     207
     208    Key const& first(const_iterator i) const { return i->first; }
     209    Key& first(iterator i) { return i->first; }
     210
     211    Val const& second(const_iterator i) const { return i->second; }
     212    Val& second(iterator i) { return i->second; }
     213  };
     214
     215  /* ** ** Wrapper fuggvenyek ** ** */
     216
     217  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
     218  typename EdgeCostMap::ValueType
     219  kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
     220           RetEdgeBoolMap &ret_bool_map) {
     221    typedef BoolMapOutput<RetEdgeBoolMap> OutObs;
     222    OutObs out(ret_bool_map);
     223
     224    typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
     225      InputVec;
     226    InputVec iv;
     227    iv.readGraphEdgeMap(G, edge_costs);
     228
     229    MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
     230    return mctk.run();
     231  }
     232
     233  template <typename Graph, typename EdgeCostMap, typename RetIterator>
     234  typename EdgeCostMap::ValueType
     235  kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
     236           RetIterator ret_iterator) {
     237    typedef SequenceOutput<RetIterator> OutObs;
     238    OutObs out(ret_iterator);
     239
     240    typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
     241      InputVec;
     242    InputVec iv;
     243    iv.readGraphEdgeMap(G, edge_costs);
     244
     245    MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
     246    return mctk.run();   
     247  }
    80248
    81249
Note: See TracChangeset for help on using the changeset viewer.