COIN-OR::LEMON - Graph Library

Changeset 737:2d867176d10e in lemon-0.x


Ignore:
Timestamp:
07/23/04 19:13:23 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@994
Message:

Several changes in Kruskal alg.

  • Input object interface was changed to an STL compatible one.
  • template parameters of class KruskalPairVec? has been simplified.
  • (the most of) the names meet the naming conventions.
  • a lot of (but still not enough) documentation has been added.
  • class KruskalMapVec? has been commented out.
Location:
src/work/johanna
Files:
2 edited

Legend:

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

    r682 r737  
    44
    55#include <algorithm>
    6 #include <unionfind.h>
    7 #include <for_each_macros.h>
     6#include <hugo/unionfind.h>
    87
    98///\file
     
    1211namespace hugo {
    1312
    14   /// Kruskal's algorithm to compute a minimum cost tree
     13  /// Kruskal's algorithm to find a minimum cost tree of a graph.
     14
     15  /// This function runs Kruskal's algorithm to find a minimum cost tree.
     16  /// \param G The graph the algorithm runs on.
     17  /// \param in This object is used to describe the edge costs. It must
     18  /// be an STL 'forward container'
     19  /// with value_type <tt> std::pair<Graph::Edge,X> </tt>,
     20  /// where X is the type of the costs. It must contain every edge in
     21  /// cost-ascending order.
     22  /// \retval out This must be a writeable EdgeMap. After running the algorithm
     23  /// this will contain the found minimum cost spanning tree: the value of an
     24  /// edge will be set to \c true if it belongs to the tree, otherwise it will
     25  /// be set to \c false. The value of each edge will be set exactly once.\n
     26  /// For the sake of simplicity, there is a helper class KruskalPairVec,
     27  /// which converts a
     28  /// simple EdgeMap to an input of this form. Alternatively, you can use
     29  /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
     30  /// the edge costs are given by an EdgeMap.
     31  /// \return The cost of the found tree.
    1532
    1633  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
    17   typename InputEdgeOrder::ValueType
    18   Kruskal(Graph const& G, InputEdgeOrder const& edges,
    19           OutBoolMap& out_map)
     34  typename InputEdgeOrder::value_type::second_type
     35  kruskal(Graph const& G, InputEdgeOrder const& in,
     36                 OutBoolMap& out)
    2037  {
    21     typedef typename InputEdgeOrder::ValueType EdgeCost;
    22     typedef typename Graph::NodeMap<int> NodeIntMap;
     38    typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
     39    typedef typename Graph::template NodeMap<int> NodeIntMap;
    2340    typedef typename Graph::Node Node;
    2441
    25     NodeIntMap comp_map(G, -1);
    26     UnionFind<Node,NodeIntMap> uf(comp_map);
     42    NodeIntMap comp(G, -1);
     43    UnionFind<Node,NodeIntMap> uf(comp);
    2744     
    2845    EdgeCost tot_cost = 0;
    29     for (typename InputEdgeOrder::const_iterator p = edges.begin();
    30          p!=edges.end(); ++p ) {
    31       if ( uf.join(G.head(edges.first(p)),
    32                              G.tail(edges.first(p))) ) {
    33         out_map.set(edges.first(p), true);
    34         tot_cost += edges.second(p);
     46    for (typename InputEdgeOrder::const_iterator p = in.begin();
     47         p!=in.end(); ++p ) {
     48      if ( uf.join(G.head((*p).first),
     49                   G.tail((*p).first)) ) {
     50        out.set((*p).first, true);
     51        tot_cost += (*p).second;
    3552      }
    3653      else {
    37         out_map.set(edges.first(p), false);
     54        out.set((*p).first, false);
    3855      }
    3956    }
     
    5875  inline
    5976  typename InputEdgeOrder::ValueType
    60   Kruskal(Graph const& G, InputEdgeOrder const& edges,
     77  kruskal(Graph const& G, InputEdgeOrder const& edges,
    6178          OutBoolMap const& out_map)
    6279  {
    6380    NonConstMapWr<OutBoolMap> map_wr(out_map);
    64     return Kruskal(G, edges, map_wr);
     81    return kruskal(G, edges, map_wr);
    6582  } 
    6683
     
    7087  /// A writable bool-map that makes a sequence of "true" keys
    7188
    72   /// A writable bool-map that creates a sequence out of keys that receive
     89  /// A writable bool-map that creates a sequence out of keys that receives
    7390  /// the value "true".
    7491  /// \warning Not a regular property map, as it doesn't know its KeyType
     
    96113  /* ** ** InputSource -ok ** ** */
    97114
    98   template<typename Key, typename Val>
    99   class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
    100 
    101   public:
    102     typedef std::vector< std::pair<Key,Val> > Parent;
    103     typedef Key KeyType;
    104     typedef Val ValueType;
    105     typedef std::pair<Key,Val> PairType;
    106 
    107     typedef typename Parent::iterator iterator;
    108     typedef typename Parent::const_iterator const_iterator;
     115  /// Kruskal input source.
     116
     117  /// Kruskal input source.
     118  ///
     119  template<typename Graph, typename Map>
     120  class KruskalPairVec
     121    : public std::vector< std::pair<typename Graph::Edge,
     122                                    typename Map::ValueType> > {
     123   
     124  public:
     125    typedef std::vector< std::pair<typename Graph::Edge,
     126                                   typename Map::ValueType> > Parent;
     127    typedef typename Parent::value_type value_type;
     128//     typedef Key KeyType;
     129//     typedef Val ValueType;
     130//     typedef std::pair<Key,Val> PairType;
     131//     typedef typename Parent::iterator iterator;
     132//     typedef typename Parent::const_iterator const_iterator;
    109133
    110134  private:
    111135    class comparePair {
    112136    public:
    113       bool operator()(PairType const& a, PairType const& b) {
     137      bool operator()(const value_type& a,
     138                      const value_type& b) {
    114139        return a.second < b.second;
    115140      }
     
    122147   
    123148    void sort() {
    124       std::sort(begin(), end(), comparePair());
     149      std::sort(this->begin(), this->end(), comparePair());
    125150    }
    126151
    127152    // FIXME: nem nagyon illik ez ide...
    128     template<typename Graph, typename Map>
    129153    KruskalPairVec(Graph const& G, Map const& m) {
    130154      typedef typename Graph::EdgeIt EdgeIt;
    131 
    132       clear();
    133       FOR_EACH_LOC(EdgeIt, e, G) {
    134       // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
     155     
     156      this->clear();
     157      for(EdgeIt e(G);G.valid(e);G.next(e)) {
     158        // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
    135159        push_back(make_pair(e, m[e]));
    136160      }
     
    138162    }
    139163
    140     Key const& first(const_iterator i) const { return i->first; }
    141     Key& first(iterator i) { return i->first; }
    142 
    143     Val const& second(const_iterator i) const { return i->second; }
    144     Val& second(iterator i) { return i->second; }
     164//     Key const& first(const_iterator i) const { return i->first; }
     165//     Key& first(iterator i) { return i->first; }
     166
     167//     Val const& second(const_iterator i) const { return i->second; }
     168//     Val& second(iterator i) { return i->second; }
    145169  };
    146170
    147171
    148   template <typename Map>
    149   class KruskalMapVec : public std::vector<typename Map::KeyType> {
    150   public:
    151 
    152     typedef typename Map::KeyType KeyType;
    153     typedef typename Map::ValueType ValueType;
    154 
    155     typedef typename std::vector<KeyType> Parent;
    156     typedef typename Parent::iterator iterator;
    157     typedef typename Parent::const_iterator const_iterator;
    158 
    159   private:
    160 
    161     const Map &m;
    162 
    163     class compareKeys {
    164       const Map &m;
    165     public:
    166       compareKeys(Map const &_m) : m(_m) {}
    167       bool operator()(KeyType const& a, KeyType const& b) {
    168         return m[a] < m[b];
    169       }
    170     };
    171 
    172   public:
    173 
    174     KruskalMapVec(Map const& _m) : m(_m) {}
    175 
    176     void sort() {
    177       std::sort(begin(), end(), compareKeys(m));
    178     }
    179 
    180     // FIXME: nem nagyon illik ez ide...
    181     template<typename Graph>
    182     KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
    183       typedef typename Graph::EdgeIt EdgeIt;
    184 
    185       clear();
    186       FOR_EACH_LOC(EdgeIt, e, G) {
    187       // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
    188         push_back(e);
    189       }
    190       sort();
    191     }
    192 
    193     KeyType const& first(const_iterator i) const { return *i; }
    194     KeyType& first(iterator i) { return *i; }
    195 
    196     ValueType const& second(const_iterator i) const { return m[*i]; }
    197     ValueType& second(iterator i) { return m[*i]; }
    198   };
     172//   template <typename Map>
     173//   class KruskalMapVec : public std::vector<typename Map::KeyType> {
     174//   public:
     175   
     176//     typedef typename Map::KeyType KeyType;
     177//     typedef typename Map::ValueType ValueType;
     178
     179//     typedef typename std::vector<KeyType> Parent;
     180//     typedef typename Parent::iterator iterator;
     181//     typedef typename Parent::const_iterator const_iterator;
     182
     183//   private:
     184
     185//     const Map &m;
     186
     187//     class compareKeys {
     188//       const Map &m;
     189//     public:
     190//       compareKeys(Map const &_m) : m(_m) {}
     191//       bool operator()(KeyType const& a, KeyType const& b) {
     192//      return m[a] < m[b];
     193//       }
     194//     };
     195
     196//   public:
     197
     198//     KruskalMapVec(Map const& _m) : m(_m) {}
     199
     200//     void sort() {
     201//       std::sort(begin(), end(), compareKeys(m));
     202//     }
     203
     204//     // FIXME: nem nagyon illik ez ide...
     205//     template<typename Graph>
     206//     KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
     207//       typedef typename Graph::EdgeIt EdgeIt;
     208
     209//       clear();
     210//       for(EdgeIt e(G);G.valid(e);G.next(e)) {
     211//       // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e))
     212//      push_back(e);
     213//       }
     214//       sort();
     215//     }
     216
     217//     KeyType const& first(const_iterator i) const { return *i; }
     218//     KeyType& first(iterator i) { return *i; }
     219
     220//     ValueType const& second(const_iterator i) const { return m[*i]; }
     221//     ValueType& second(iterator i) { return m[*i]; }
     222//   };
    199223
    200224  /* ** ** Wrapper fuggvenyek ** ** */
     
    203227  /// \brief Wrapper to Kruskal().
    204228  /// Input is from an EdgeMap, output is a plain boolmap.
     229
     230  ///\todo some more words would be nice here.
     231  ///
    205232  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
    206233  inline
    207234  typename EdgeCostMap::ValueType
    208   Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
    209                                    EdgeCostMap const& edge_costs,
    210                                    RetEdgeBoolMap &ret_bool_map) {
    211 
    212     typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
    213       InputVec;
     235  kruskalEdgeMap(Graph const& G,
     236                        EdgeCostMap const& edge_costs,
     237                        RetEdgeBoolMap &ret_bool_map) {
     238   
     239    typedef KruskalPairVec<Graph,EdgeCostMap> InputVec;
     240   
    214241    InputVec iv(G, edge_costs);
    215 
    216     return Kruskal(G, iv, ret_bool_map);
     242    return kruskal(G, iv, ret_bool_map);
    217243  }
    218244
     
    220246  /// \brief Wrapper to Kruskal().
    221247  /// Input is from an EdgeMap, output is to a sequence.
     248
     249  ///\todo it does not follow the naming convention.
     250  ///
    222251  template <typename Graph, typename EdgeCostMap, typename RetIterator>
    223252  inline
    224253  typename EdgeCostMap::ValueType
    225   Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
    226                                     EdgeCostMap const& edge_costs,
    227                                     RetIterator ret_iterator) {
     254  kruskalEdgeMap_IteratorOut(const Graph& G,
     255                             const EdgeCostMap& edge_costs,
     256                             RetIterator ret_iterator)
     257  {
     258    typedef typename EdgeCostMap::ValueType ValueType;
     259   
    228260    typedef SequenceOutput<RetIterator> OutMap;
    229261    OutMap out(ret_iterator);
    230262
    231     typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
    232       InputVec;
     263    typedef KruskalPairVec<Graph, EdgeCostMap> InputVec;
     264
    233265    InputVec iv(G, edge_costs);
    234266
    235     return Kruskal(G, iv, out);
     267    return kruskal(G, iv, out);
    236268  }
    237269
  • src/work/johanna/kruskal_test.cc

    r352 r737  
    55
    66#include <kruskal.h>
    7 #include <list_graph.h>
     7#include <hugo/list_graph.h>
    88
    99
     
    7272
    7373  cout << "Uniform 2-es koltseggel: "
    74        << Kruskal_EdgeCostMapIn_BoolMapOut(G, edge_cost_map, tree_map)
     74       << kruskalEdgeMap(G, edge_cost_map, tree_map)
    7575       << endl;
    7676
     
    9090
    9191  cout << "Nemkonst koltseggel (-31): "
    92        << Kruskal_EdgeCostMapIn_IteratorOut(G, edge_cost_map,
    93                                             back_inserter(tree_edge_vec))
     92       << kruskalEdgeMap_IteratorOut(G, edge_cost_map,
     93                                     back_inserter(tree_edge_vec))
    9494       << endl;
    9595
     
    9797  for(vector<Edge>::iterator e = tree_edge_vec.begin();
    9898      e != tree_edge_vec.end(); ++e, ++i) {
    99     cout << i << ". el: " << *e << endl;
     99    cout << i << ". el: " << G.id(*e) << endl;
    100100  }
    101101
     
    108108//                vec_filler)
    109109//        << endl;
    110   cout << "Nemkonst koltseggel tarhatekonyabban: "
    111        << Kruskal(G,
    112                   KruskalMapVec<ECostMap>(G, edge_cost_map),
    113                   makeSequenceOutput(back_inserter(tree_edge_vec))
    114                   )
    115        << endl;
    116110
    117   i = 1;
    118   for(vector<Edge>::iterator e = tree_edge_vec.begin();
    119       e != tree_edge_vec.end(); ++e, ++i) {
    120     cout << i << ". el: " << *e << endl;
    121   }
     111//   cout << "Nemkonst koltseggel tarhatekonyabban: "
     112//        << kruskal(G,
     113//                KruskalMapVec<ECostMap>(G, edge_cost_map),
     114//                makeSequenceOutput(back_inserter(tree_edge_vec))
     115//                )
     116//        << endl;
    122117
     118//   i = 1;
     119//   for(vector<Edge>::iterator e = tree_edge_vec.begin();
     120//       e != tree_edge_vec.end(); ++e, ++i) {
     121//     cout << i << ". el: " << *e << endl;
     122//   }
     123
     124// **********************************************************************
    123125
    124126//   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
Note: See TracChangeset for help on using the changeset viewer.