COIN-OR::LEMON - Graph Library

Changeset 218:5964f1c64ca1 in lemon-0.x


Ignore:
Timestamp:
03/20/04 18:01:45 (20 years ago)
Author:
beckerjc
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@314
Message:

unionfind: componentSize tagfv

kruskal: osztalyositva; lehet beadni sajat elorendezett el-koltseg vektort

nem tul elegans megoldas...

Location:
src/work/johanna
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/work/johanna/Makefile

    r150 r218  
    11BINARIES = kruskal_test
    2 INCLUDEDIRS= -I. -I.. -I../../include
     2INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos}
    33include ../makefile
    44
  • src/work/johanna/kruskal.h

    r150 r218  
    88namespace hugo {
    99
    10   template <typename EdgeCostPair> static
    11   bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) {
    12     return a.second < b.second;
    13   }
     10
     11  template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap>
     12  class MinCostTreeKruskal
     13  {
     14
     15    typedef typename Graph::EdgeIt EdgeIt;
     16    typedef typename Graph::Edge Edge;
     17
     18  public:
     19    typedef typename EdgeCostMap::ValueType EdgeCost;
     20    typedef std::pair<Edge, EdgeCost> EdgeCostPair;
     21    typedef std::vector<EdgeCostPair> EdgeCostVector;
     22   
     23  private:
     24    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:
    1437
    1538
    16   template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap>
     39    MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap,
     40                       EdgeBoolMap& _treemap) : G(_G), costmap(_costmap),
     41                                                treemap(_treemap) {}
     42 
    1743
    18   typename EdgeDoubleMap::ValueType
    19   MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap,
    20                      EdgeBoolMap& treemap)
    21   {
     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);
    2254   
    23     typedef typename EdgeDoubleMap::ValueType EDouble;
    24     typedef typename Graph::EachEdgeIt EachEdgeIt;
    25     typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair;
    26 
    27 
    28     typedef std::vector<EdgeCostPair> EdgeCostVector;
    29     EdgeCostVector rank;
    30 
    31     for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
    32       rank.push_back(make_pair(e, costmap.get(e)));
    3355    }
    3456
    35    
    36     std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>);
     57    EdgeCost run(EdgeCostVector const &rank)
     58    {
     59      typedef typename Graph::NodeMap<int> NodeIntMap;
     60      typedef typename Graph::Node Node;
     61      NodeIntMap comp_map(G, -1);
     62      UnionFind<Node,NodeIntMap> uf(comp_map);
     63     
     64      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;
     70        }
     71        else {
     72          treemap.set(p->first, false);
     73        }
     74      }
     75      return tot_cost;
    3776
    38     typedef typename Graph::NodeMap<int> NodeIntMap;
    39     typedef typename Graph::NodeIt NodeIt;
    40     NodeIntMap comp_map(G, -1);
    41     UnionFind<NodeIt,NodeIntMap> uf(comp_map);
     77    }
    4278
    43     EDouble tot_cost = 0;
    44     for (typename EdgeCostVector::iterator p = rank.begin();
    45          p!=rank.end(); ++p ) {
    46       if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
    47         treemap.set(p->first, true);
    48         tot_cost += p->second;
    49       }
    50       else {
    51         treemap.set(p->first, false);
    52       }
    53     }
    54     return tot_cost;
    55   }
     79  };
    5680
    5781
  • src/work/johanna/kruskal_test.cc

    r150 r218  
    44
    55#include <kruskal.h>
    6 #include <list_graph.hh>
     6#include <list_graph.h>
    77
    88
     
    2626
    2727
     28// Egy olyan "map", ami nem tud semmit, csak a typedef-eket.
     29// Valami elegansabb megoldas kene a Kruskalban...
     30
     31template <typename K, typename V>
     32class DummyMap {
     33public:
     34  typedef K KeyType;
     35  typedef V ValueType;
     36};
     37
    2838int main() {
    2939
     40  typedef ListGraph::Node Node;
     41  typedef ListGraph::Edge Edge;
    3042  typedef ListGraph::NodeIt NodeIt;
    3143  typedef ListGraph::EdgeIt EdgeIt;
    32   typedef ListGraph::EachNodeIt EachNodeIt;
    33   typedef ListGraph::EachEdgeIt EachEdgeIt;
    3444
    3545  ListGraph G;
    3646
    37   NodeIt s=G.addNode();
    38   NodeIt v1=G.addNode();
    39   NodeIt v2=G.addNode();
    40   NodeIt v3=G.addNode();
    41   NodeIt v4=G.addNode();
    42   NodeIt t=G.addNode();
     47  Node s=G.addNode();
     48  Node v1=G.addNode();
     49  Node v2=G.addNode();
     50  Node v3=G.addNode();
     51  Node v4=G.addNode();
     52  Node t=G.addNode();
    4353 
    44   G.addEdge(s, v1);
    45   G.addEdge(s, v2);
    46   G.addEdge(v1, v2);
    47   G.addEdge(v2, v1);
    48   G.addEdge(v1, v3);
    49   G.addEdge(v3, v2);
    50   G.addEdge(v2, v4);
    51   G.addEdge(v4, v3);
    52   G.addEdge(v3, t);
    53   G.addEdge(v4, t);
     54  Edge e1 = G.addEdge(s, v1);
     55  Edge e2 = G.addEdge(s, v2);
     56  Edge e3 = G.addEdge(v1, v2);
     57  Edge e4 = G.addEdge(v2, v1);
     58  Edge e5 = G.addEdge(v1, v3);
     59  Edge e6 = G.addEdge(v3, v2);
     60  Edge e7 = G.addEdge(v2, v4);
     61  Edge e8 = G.addEdge(v4, v3);
     62  Edge e9 = G.addEdge(v3, t);
     63  Edge e10 = G.addEdge(v4, t);
    5464
    55   ListGraph::EdgeMap<double> edge_cost_map(G, 2);
    56   ListGraph::EdgeMap<bool> tree_map(G);
     65  typedef ListGraph::EdgeMap<double> ECostMap;
     66  typedef ListGraph::EdgeMap<bool> EBoolMap;
     67
     68  ECostMap edge_cost_map(G, 2);
     69  EBoolMap tree_map(G);
    5770 
    58   double k0lts = MinCostTreeKruskal(G, edge_cost_map, tree_map);
     71  typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
    5972
    60   cout << k0lts << endl;
     73  MCTK mctk(G, edge_cost_map, tree_map);
     74  double k0lts = mctk.run();
     75
     76  cout << "Uniform 2-es koltseggel: " << k0lts << endl;
     77
     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));
     92
     93  k0lts = mctk2.run(ecv);
     94  cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
     95       << k0lts << endl;
     96
    6197
    6298  return 0;
  • src/work/johanna/unionfind.h

    r150 r218  
    11// -*- c++ -*- //
    2 #ifndef UNION_FIND_H
    3 #define UNION_FIND_H
     2#ifndef HUGO_UNION_FIND_H
     3#define HUGO_UNION_FIND_H
    44
    55#include <vector>
     
    6969    }
    7070
     71    int componentSize(T a)
     72    {
     73      int ca = whichComponent(a);
     74      return data[ca].second;
     75    }
     76
    7177  };
    7278
    7379} //namespace hugo
    7480
    75 #endif //UNION_FIND_H
     81#endif //HUGO_UNION_FIND_H
Note: See TracChangeset for help on using the changeset viewer.