COIN-OR::LEMON - Graph Library

Changeset 246:dc95ca4ebc7b in lemon-0.x


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

koztes valtozat

Location:
src/work/johanna
Files:
2 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
  • src/work/johanna/kruskal_test.cc

    r218 r246  
    22#include <iostream>
    33#include <map>
     4#include <vector>
    45
    56#include <kruskal.h>
     
    6970  EBoolMap tree_map(G);
    7071 
    71   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
    7272
    73   MCTK mctk(G, edge_cost_map, tree_map);
    74   double k0lts = mctk.run();
     73  cout << "Uniform 2-es koltseggel: "
     74       << kruskal1(G, edge_cost_map, tree_map)
     75       << endl;
    7576
    76   cout << "Uniform 2-es koltseggel: " << k0lts << endl;
    7777
    78   // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
    79   typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
    80   MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
    81   MCTK2::EdgeCostVector ecv;
    82   ecv.push_back(make_pair(e1, 10));
    83   ecv.push_back(make_pair(e2, 9));
    84   ecv.push_back(make_pair(e3, 8));
    85   ecv.push_back(make_pair(e4, 7));
    86   ecv.push_back(make_pair(e5, 6));
    87   ecv.push_back(make_pair(e6, 5));
    88   ecv.push_back(make_pair(e7, 4));
    89   ecv.push_back(make_pair(e8, 3));
    90   ecv.push_back(make_pair(e9, 2));
    91   ecv.push_back(make_pair(e10, 1));
     78  edge_cost_map.set(e1, -10);
     79  edge_cost_map.set(e2, -9);
     80  edge_cost_map.set(e3, -8);
     81  edge_cost_map.set(e4, -7);
     82  edge_cost_map.set(e5, -6);
     83  edge_cost_map.set(e6, -5);
     84  edge_cost_map.set(e7, -4);
     85  edge_cost_map.set(e8, -3);
     86  edge_cost_map.set(e9, -2);
     87  edge_cost_map.set(e10, -1);
    9288
    93   k0lts = mctk2.run(ecv);
    94   cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
    95        << k0lts << endl;
     89  vector<Edge> tree_edge_vec;
     90
     91  cout << "Nemkonst koltseggel (-31): "
     92       << kruskal2(G, edge_cost_map, back_inserter(tree_edge_vec))
     93       << endl;
     94
     95  int i = 1;
     96  for(vector<Edge>::iterator e = tree_edge_vec.begin();
     97      e != tree_edge_vec.end(); ++e, ++i) {
     98    cout << i << ". el: " << *e << endl;
     99  }
     100
     101
     102//   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
     103
     104//   MCTK mctk(G, edge_cost_map, tree_map);
     105//   double k0lts = mctk.run();
     106
     107//   cout << "Uniform 2-es koltseggel: " << k0lts << endl;
     108
     109//   // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
     110//   typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
     111//   MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
     112//   MCTK2::EdgeCostVector ecv;
     113//   ecv.push_back(make_pair(e1, 10));
     114//   ecv.push_back(make_pair(e2, 9));
     115//   ecv.push_back(make_pair(e3, 8));
     116//   ecv.push_back(make_pair(e4, 7));
     117//   ecv.push_back(make_pair(e5, 6));
     118//   ecv.push_back(make_pair(e6, 5));
     119//   ecv.push_back(make_pair(e7, 4));
     120//   ecv.push_back(make_pair(e8, 3));
     121//   ecv.push_back(make_pair(e9, 2));
     122//   ecv.push_back(make_pair(e10, 1));
     123
     124//   k0lts = mctk2.run(ecv);
     125//   cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
     126//        << k0lts << endl;
    96127
    97128
Note: See TracChangeset for help on using the changeset viewer.