COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
03/20/04 18:01:45 (17 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...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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;
Note: See TracChangeset for help on using the changeset viewer.