COIN-OR::LEMON - Graph Library

Changeset 349:42c660f58702 in lemon-0.x


Ignore:
Timestamp:
04/17/04 21:19:57 (16 years ago)
Author:
beckerjc
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@468
Message:

Kruskal lenyegeben kesz.
Kell meg dokumentalni, meg meg egy par jol hasznalhato wrapper fv.
Es valamit meg kene csinalni azzal, hogy nem const ref. a kimeno boolmap,

viszont sokszor "on-the-fly" akarjuk megkonstrualni (es ilyenkor persze a
const-os mapet is lehet set-elni...)

Location:
src/work/johanna
Files:
3 edited

Legend:

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

    r246 r349  
    33#define HUGO_KRUSKAL_H
    44
    5 #include "unionfind.h"
    65#include <algorithm>
     6#include <unionfind.h>
     7#include <for_each_macros.h>
    78
    89namespace hugo {
    910
    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>
    65   class MinCostTreeKruskal
     11  /// Kruskal's algorithm to compute a minimum cost tree
     12
     13  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
     14  typename InputEdgeOrder::ValueType
     15  Kruskal(Graph const& G, InputEdgeOrder const& edges,
     16          OutBoolMap& out_map)
    6617  {
    67 
    68     typedef typename Graph::EdgeIt EdgeIt;
    69     typedef typename Graph::Edge Edge;
    70 
    71   public:
    7218    typedef typename InputEdgeOrder::ValueType EdgeCost;
    73    
    74   private:
    75     Graph const &G;
    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) {}
     19    typedef typename Graph::NodeMap<int> NodeIntMap;
     20    typedef typename Graph::Node Node;
     21
     22    NodeIntMap comp_map(G, -1);
     23    UnionFind<Node,NodeIntMap> uf(comp_map);
     24     
     25    EdgeCost tot_cost = 0;
     26    for (typename InputEdgeOrder::const_iterator p = edges.begin();
     27         p!=edges.end(); ++p ) {
     28      if ( uf.joinComponents(G.head(edges.first(p)),
     29                             G.tail(edges.first(p))) ) {
     30        out_map.set(edges.first(p), true);
     31        tot_cost += edges.second(p);
     32      }
     33      else {
     34        out_map.set(edges.first(p), false);
     35      }
     36    }
     37    return tot_cost;
     38  }
     39
     40
    8541 
    86 
    87     EdgeCost run()
    88     {
    89       typedef typename Graph::NodeMap<int> NodeIntMap;
    90       typedef typename Graph::Node Node;
    91       NodeIntMap comp_map(G, -1);
    92       UnionFind<Node,NodeIntMap> uf(comp_map);
    93      
    94       EdgeCost tot_cost = 0;
    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);
    101         }
    102         else {
    103           out_obs.setFalse(edges.first(p));
    104         }
    105       }
    106       return tot_cost;
    107     }
    108 
     42  /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
     43 
     44  /// A writable bool-map that makes a sequence of "true" keys
     45
     46  /// A writable bool-map that creates a sequence out of keys that receive
     47  /// the value "true".
     48  /// \warning Not a regular property map, as it doesn't know its KeyType
     49
     50  template<typename Iterator>
     51  class SequenceOutput {
     52    Iterator it;
     53
     54  public:
     55    typedef bool ValueType;
     56
     57    SequenceOutput(Iterator const &_it) : it(_it) {}
     58
     59    template<typename KeyType>
     60    void set(KeyType const& k, bool v) { if(v) {*it=k; ++it;} }
    10961  };
    11062
    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 
     63  template<typename Iterator>
     64  inline
     65  SequenceOutput<Iterator>
     66  makeSequenceOutput(Iterator it) {
     67    return SequenceOutput<Iterator>(it);
     68  }
    15969
    16070  /* ** ** InputSource -ok ** ** */
    16171
    16272  template<typename Key, typename Val>
    163   class PairVec : public std::vector< std::pair<Key,Val> > {
     73  class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
    16474
    16575  public:
     
    17282    typedef typename Parent::const_iterator const_iterator;
    17383
    174 
    17584  private:
    176 
    17785    class comparePair {
    17886    public:
     
    18593
    18694    // FIXME: kell ez?
    187     // PairVec(Parent const& p) : Parent(p) {}
     95    // KruskalPairVec(Parent const& p) : Parent(p) {}
    18896   
    18997    void sort() {
     
    193101    // FIXME: nem nagyon illik ez ide...
    194102    template<typename Graph, typename Map>
    195     void readGraphEdgeMap(Graph const& G, Map const& m) {
     103    KruskalPairVec(Graph const& G, Map const& m) {
    196104      typedef typename Graph::EdgeIt EdgeIt;
    197105
    198106      clear();
    199       for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
     107      FOR_EACH_LOC(EdgeIt, e, G) {
     108      // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
    200109        push_back(make_pair(e, m[e]));
    201110      }
    202 
    203111      sort();
    204112    }
    205 
    206     int alma() { return 5; /* FIXME */ }
    207113
    208114    Key const& first(const_iterator i) const { return i->first; }
     
    213119  };
    214120
     121
     122  template <typename Map>
     123  class KruskalMapVec : public std::vector<typename Map::KeyType> {
     124  public:
     125
     126    typedef typename Map::KeyType KeyType;
     127    typedef typename Map::ValueType ValueType;
     128
     129    typedef typename std::vector<KeyType> Parent;
     130    typedef typename Parent::iterator iterator;
     131    typedef typename Parent::const_iterator const_iterator;
     132
     133  private:
     134
     135    const Map &m;
     136
     137    class compareKeys {
     138      const Map &m;
     139    public:
     140      compareKeys(Map const &_m) : m(_m) {}
     141      bool operator()(KeyType const& a, KeyType const& b) {
     142        return m[a] < m[b];
     143      }
     144    };
     145
     146  public:
     147
     148    KruskalMapVec(Map const& _m) : m(_m) {}
     149
     150    void sort() {
     151      std::sort(begin(), end(), compareKeys(m));
     152    }
     153
     154    // FIXME: nem nagyon illik ez ide...
     155    template<typename Graph>
     156    KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
     157      typedef typename Graph::EdgeIt EdgeIt;
     158
     159      clear();
     160      FOR_EACH_LOC(EdgeIt, e, G) {
     161      // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
     162        push_back(e);
     163      }
     164      sort();
     165    }
     166
     167    KeyType const& first(const_iterator i) const { return *i; }
     168    KeyType& first(iterator i) { return *i; }
     169
     170    ValueType const& second(const_iterator i) const { return m[*i]; }
     171    ValueType& second(iterator i) { return m[*i]; }
     172  };
     173
    215174  /* ** ** Wrapper fuggvenyek ** ** */
    216175
     176
     177  /// \brief Wrapper to Kruskal().
     178  /// Input is from an EdgeMap, output is a plain boolmap.
    217179  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
    218180  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>
     181  Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
     182                                   EdgeCostMap const& edge_costs,
     183                                   RetEdgeBoolMap &ret_bool_map) {
     184
     185    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
    225186      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 
     187    InputVec iv(G, edge_costs);
     188
     189    return Kruskal(G, iv, ret_bool_map);
     190  }
     191
     192
     193  /// \brief Wrapper to Kruskal().
     194  /// Input is from an EdgeMap, output is to a sequence.
    233195  template <typename Graph, typename EdgeCostMap, typename RetIterator>
    234196  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>
     197  Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
     198                                    EdgeCostMap const& edge_costs,
     199                                    RetIterator ret_iterator) {
     200    typedef SequenceOutput<RetIterator> OutMap;
     201    OutMap out(ret_iterator);
     202
     203    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
    241204      InputVec;
    242     InputVec iv;
    243     iv.readGraphEdgeMap(G, edge_costs);
    244 
    245     MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
    246     return mctk.run();   
     205    InputVec iv(G, edge_costs);
     206
     207    return Kruskal(G, iv, out);
    247208  }
    248209
  • src/work/johanna/kruskal_test.cc

    r246 r349  
    7272
    7373  cout << "Uniform 2-es koltseggel: "
    74        << kruskal1(G, edge_cost_map, tree_map)
     74       << Kruskal_EdgeCostMapIn_BoolMapOut(G, edge_cost_map, tree_map)
    7575       << endl;
    7676
     
    9090
    9191  cout << "Nemkonst koltseggel (-31): "
    92        << kruskal2(G, edge_cost_map, back_inserter(tree_edge_vec))
     92       << Kruskal_EdgeCostMapIn_IteratorOut(G, edge_cost_map,
     93                                            back_inserter(tree_edge_vec))
    9394       << endl;
    9495
    9596  int i = 1;
     97  for(vector<Edge>::iterator e = tree_edge_vec.begin();
     98      e != tree_edge_vec.end(); ++e, ++i) {
     99    cout << i << ". el: " << *e << endl;
     100  }
     101
     102  tree_edge_vec.clear();
     103  SequenceOutput< back_insert_iterator< vector<Edge> > >
     104    vec_filler(back_inserter(tree_edge_vec));
     105  cout << "Nemkonst koltseggel tarhatekonyabban: "
     106       << Kruskal(G,
     107                  KruskalMapVec<ECostMap>(G, edge_cost_map),
     108                  vec_filler)
     109       << endl;
     110
     111  i = 1;
    96112  for(vector<Edge>::iterator e = tree_edge_vec.begin();
    97113      e != tree_edge_vec.end(); ++e, ++i) {
  • src/work/johanna/unionfind.h

    r218 r349  
    2525    int whichComponent(T a)
    2626    {
    27       int comp0 = map.get(a);
     27      int comp0 = map[a];
    2828      if (comp0 < 0) {
    2929        return insertNewElement(a);
Note: See TracChangeset for help on using the changeset viewer.