COIN-OR::LEMON - Graph Library

Changeset 2424:95cd24940d00 in lemon-0.x for test/kruskal_test.cc


Ignore:
Timestamp:
04/19/07 17:11:58 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3260
Message:

Redesigned Kruskal algorithm

The interface of function type implementation is not changed
Additional class type implementation

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/kruskal_test.cc

    r2391 r2424  
    2424#include <lemon/kruskal.h>
    2525#include <lemon/list_graph.h>
     26
    2627#include <lemon/concepts/maps.h>
    2728#include <lemon/concepts/graph.h>
     29#include <lemon/concepts/ugraph.h>
    2830
    2931
     
    3436{
    3537  concepts::WriteMap<concepts::Graph::Edge,bool> w;
     38  concepts::WriteMap<concepts::UGraph::UEdge,bool> uw;
     39
     40  concepts::ReadMap<concepts::Graph::Edge,int> r;
     41  concepts::ReadMap<concepts::UGraph::UEdge,int> ur;
    3642
    3743  concepts::Graph g;
    38   kruskal(g,
    39           concepts::ReadMap<concepts::Graph::Edge,int>(),
    40           w);
     44  concepts::UGraph ug;
     45
     46  kruskal(g, r, w);
     47  kruskal(ug, ur, uw);
     48
     49  std::vector<std::pair<concepts::Graph::Edge, int> > rs;
     50  std::vector<std::pair<concepts::UGraph::UEdge, int> > urs;
     51
     52  kruskal(g, rs, w);
     53  kruskal(ug, urs, uw);
     54
     55  std::vector<concepts::Graph::Edge> ws;
     56  std::vector<concepts::UGraph::UEdge> uws;
     57
     58  kruskal(g, r, ws.begin());
     59  kruskal(ug, ur, uws.begin());
     60
     61  Kruskal<concepts::UGraph,concepts::ReadMap<concepts::UGraph::UEdge,int> >
     62    alg(ug, ur);
     63
     64  alg.init();
     65  alg.initPresorted(uws.begin(), uws.end());
     66  alg.reinit();
     67 
     68  alg.emptyQueue();
     69 
     70  alg.nextEdge();
     71  alg.processNextEdge();
     72  alg.processEdge(concepts::UGraph::UEdge());
     73
     74  alg.run();
     75 
     76  alg.treeMap();
     77  alg.tree(concepts::UGraph::UEdge());
    4178}
    4279
    4380int main() {
    4481
    45   typedef ListGraph::Node Node;
    46   typedef ListGraph::Edge Edge;
    47   typedef ListGraph::NodeIt NodeIt;
    48   typedef ListGraph::EdgeIt EdgeIt;
     82  typedef ListUGraph::Node Node;
     83  typedef ListUGraph::UEdge UEdge;
     84  typedef ListUGraph::NodeIt NodeIt;
     85  typedef ListUGraph::EdgeIt EdgeIt;
    4986
    50   ListGraph G;
     87  ListUGraph G;
    5188
    5289  Node s=G.addNode();
     
    5794  Node t=G.addNode();
    5895 
    59   Edge e1 = G.addEdge(s, v1);
    60   Edge e2 = G.addEdge(s, v2);
    61   Edge e3 = G.addEdge(v1, v2);
    62   Edge e4 = G.addEdge(v2, v1);
    63   Edge e5 = G.addEdge(v1, v3);
    64   Edge e6 = G.addEdge(v3, v2);
    65   Edge e7 = G.addEdge(v2, v4);
    66   Edge e8 = G.addEdge(v4, v3);
    67   Edge e9 = G.addEdge(v3, t);
    68   Edge e10 = G.addEdge(v4, t);
     96  UEdge e1 = G.addEdge(s, v1);
     97  UEdge e2 = G.addEdge(s, v2);
     98  UEdge e3 = G.addEdge(v1, v2);
     99  UEdge e4 = G.addEdge(v2, v1);
     100  UEdge e5 = G.addEdge(v1, v3);
     101  UEdge e6 = G.addEdge(v3, v2);
     102  UEdge e7 = G.addEdge(v2, v4);
     103  UEdge e8 = G.addEdge(v4, v3);
     104  UEdge e9 = G.addEdge(v3, t);
     105  UEdge e10 = G.addEdge(v4, t);
    69106
    70   typedef ListGraph::EdgeMap<int> ECostMap;
    71   typedef ListGraph::EdgeMap<bool> EBoolMap;
     107  typedef ListUGraph::UEdgeMap<int> ECostMap;
     108  typedef ListUGraph::UEdgeMap<bool> EBoolMap;
    72109
    73110  ECostMap edge_cost_map(G, 2);
     
    76113
    77114  //Test with const map.
    78   check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
     115  check(kruskal(G, ConstMap<ListUGraph::UEdge,int>(2), tree_map)==10,
    79116        "Total cost should be 10");
    80117  //Test with a edge map (filled with uniform costs).
     
    93130  edge_cost_map.set(e10, -1);
    94131
    95   vector<Edge> tree_edge_vec(5);
     132  vector<UEdge> tree_edge_vec(5);
    96133
    97134  //Test with a edge map and inserter.
     
    108145        "Total cost should be -31.");
    109146 
    110   tree_edge_vec.clear();
     147//   tree_edge_vec.clear();
    111148 
    112   //The above test could also be coded like this:
    113   check(kruskal(G,
    114                 makeKruskalMapInput(G, edge_cost_map),
    115                 makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
    116         ==-31,
    117         "Total cost should be -31.");
     149//   //The above test could also be coded like this:
     150//   check(kruskal(G,
     151//              makeKruskalMapInput(G, edge_cost_map),
     152//              makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
     153//      ==-31,
     154//      "Total cost should be -31.");
    118155
    119156  check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
     
    126163        "Wrong tree.");
    127164
     165  Kruskal<ListUGraph, ECostMap> ka(G, edge_cost_map);
     166 
     167  ka.run();
     168 
     169  check(ka.tree(e1) &&
     170        ka.tree(e2) &&
     171        ka.tree(e5) &&
     172        ka.tree(e7) &&
     173        ka.tree(e9),
     174        "Wrong tree.");
     175
     176  check(ka.treeValue() == -31,
     177        "Total cost should be -31.");
     178
    128179  return 0;
    129180}
Note: See TracChangeset for help on using the changeset viewer.