COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 78:ecc1171307be in lemon-0.x for src/work/jacint/flow_test.cc


Ignore:
Timestamp:
02/16/04 17:15:58 (20 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@101
Message:

modern valtozat

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/jacint/flow_test.cc

    r72 r78  
    33#include <string>
    44
    5 #include <marci_list_graph.hh>
    6 #include <marci_graph_traits.hh>
    7 #include <marci_property_vector.hh>
    8 #include <preflow_push_hl.hh>
    9 #include <preflow_push_max_flow.hh>
    10 #include <reverse_bfs.hh>
    11 //#include <dijkstra.hh>
     5#include <list_graph.hh>
     6#include <preflow_push_hl.h>
     7#include <preflow_push_max_flow.h>
     8#include <reverse_bfs.h>
     9//#include <dijkstra.h>
    1210
    1311using namespace marci;
    … …  
    1614int main (int, char*[])
    1715{
    18   typedef graph_traits<list_graph>::node_iterator node_iterator;
    19   typedef graph_traits<list_graph>::edge_iterator edge_iterator;
    20   typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
    21   typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
    22   typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
    23   typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
    24   typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
    25 
    26   list_graph flow_test;
     16  typedef ListGraph::NodeIt NodeIt;
     17  typedef ListGraph::EdgeIt EdgeIt;
     18  typedef ListGraph::EachNodeIt EachNodeIt;
     19  typedef ListGraph::EachEdgeIt EachEdgeIt;
     20  typedef ListGraph::OutEdgeIt OutEdgeIt;
     21  typedef ListGraph::InEdgeIt InEdgeIt;
     22 
     23  ListGraph flow_test;
    2724 
    2825    //Ahuja könyv példája, maxflowvalue=13
    29   node_iterator s=flow_test.add_node();
    30   node_iterator v1=flow_test.add_node();
    31   node_iterator v2=flow_test.add_node();
    32   node_iterator v3=flow_test.add_node();
    33   node_iterator v4=flow_test.add_node();
    34   node_iterator v5=flow_test.add_node();
    35   node_iterator t=flow_test.add_node();
    36  
    37   node_property_vector<list_graph, std::string> node_name(flow_test);
    38   node_name.put(s, "s");
    39   node_name.put(v1, "v1");
    40   node_name.put(v2, "v2");
    41   node_name.put(v3, "v3");
    42   node_name.put(v4, "v4");
    43   node_name.put(v5, "v5");
    44   node_name.put(t, "t");
    45 
    46   edge_iterator s_v1=flow_test.add_edge(s, v1);
    47   edge_iterator s_v2=flow_test.add_edge(s, v2);
    48   edge_iterator s_v3=flow_test.add_edge(s, v3);
    49   edge_iterator v2_v4=flow_test.add_edge(v2, v4);
    50   edge_iterator v2_v5=flow_test.add_edge(v2, v5);
    51   edge_iterator v3_v5=flow_test.add_edge(v3, v5);
    52   edge_iterator v4_t=flow_test.add_edge(v4, t);
    53   edge_iterator v5_t=flow_test.add_edge(v5, t);
    54   edge_iterator v2_s=flow_test.add_edge(v2, s);
    55  
    56   edge_property_vector<list_graph, int> cap(flow_test); 
    57   cap.put(s_v1, 0);
    58   cap.put(s_v2, 10);
    59   cap.put(s_v3, 10);
    60   cap.put(v2_v4, 5);
    61   cap.put(v2_v5, 8);
    62   cap.put(v3_v5, 5);
    63   cap.put(v4_t, 8);
    64   cap.put(v5_t, 8);
    65   cap.put(v2_s, 0);
     26  NodeIt s=flow_test.addNode();
     27  NodeIt v1=flow_test.addNode();
     28  NodeIt v2=flow_test.addNode();
     29  NodeIt v3=flow_test.addNode();
     30  NodeIt v4=flow_test.addNode();
     31  NodeIt v5=flow_test.addNode();
     32  NodeIt t=flow_test.addNode();
     33 
     34  ListGraph::NodeMap<std::string> Node_name(flow_test);
     35  Node_name.set(s, "s");
     36  Node_name.set(v1, "v1");
     37  Node_name.set(v2, "v2");
     38  Node_name.set(v3, "v3");
     39  Node_name.set(v4, "v4");
     40  Node_name.set(v5, "v5");
     41  Node_name.set(t, "t");
     42
     43  EdgeIt s_v1=flow_test.addEdge(s, v1);
     44  EdgeIt s_v2=flow_test.addEdge(s, v2);
     45  EdgeIt s_v3=flow_test.addEdge(s, v3);
     46  EdgeIt v2_v4=flow_test.addEdge(v2, v4);
     47  EdgeIt v2_v5=flow_test.addEdge(v2, v5);
     48  EdgeIt v3_v5=flow_test.addEdge(v3, v5);
     49  EdgeIt v4_t=flow_test.addEdge(v4, t);
     50  EdgeIt v5_t=flow_test.addEdge(v5, t);
     51  EdgeIt v2_s=flow_test.addEdge(v2, s);
     52 
     53   ListGraph::EdgeMap<int> cap(flow_test); 
     54  cap.set(s_v1, 0);
     55  cap.set(s_v2, 10);
     56  cap.set(s_v3, 10);
     57  cap.set(v2_v4, 5);
     58  cap.set(v2_v5, 8);
     59  cap.set(v3_v5, 5);
     60  cap.set(v4_t, 8);
     61  cap.set(v5_t, 8);
     62  cap.set(v2_s, 0);
    6663
    6764
    6865 
    6966  //Marci példája, maxflowvalue=23
    70   /*  node_iterator s=flow_test.add_node();
    71   node_iterator v1=flow_test.add_node();
    72   node_iterator v2=flow_test.add_node();
    73   node_iterator v3=flow_test.add_node();
    74   node_iterator v4=flow_test.add_node();
    75   node_iterator t=flow_test.add_node();
    76   node_iterator w=flow_test.add_node();
    77 
    78  
    79   node_property_vector<list_graph, std::string> node_name(flow_test);
    80   node_name.put(s, "s");
    81   node_name.put(v1, "v1");
    82   node_name.put(v2, "v2");
    83   node_name.put(v3, "v3");
    84   node_name.put(v4, "v4");
    85   node_name.put(t, "t");
    86   node_name.put(w, "w");
    87 
    88   edge_iterator s_v1=flow_test.add_edge(s, v1);
    89   edge_iterator s_v2=flow_test.add_edge(s, v2);
    90   edge_iterator v1_v2=flow_test.add_edge(v1, v2);
    91   edge_iterator v2_v1=flow_test.add_edge(v2, v1);
    92   edge_iterator v1_v3=flow_test.add_edge(v1, v3);
    93   edge_iterator v3_v2=flow_test.add_edge(v3, v2);
    94   edge_iterator v2_v4=flow_test.add_edge(v2, v4);
    95   edge_iterator v4_v3=flow_test.add_edge(v4, v3);
    96   edge_iterator v3_t=flow_test.add_edge(v3, t);
    97   edge_iterator v4_t=flow_test.add_edge(v4, t);
    98   edge_iterator v3_v3=flow_test.add_edge(v3, v3);
    99   edge_iterator s_w=flow_test.add_edge(s, w);
    100   //  edge_iterator v2_s=flow_test.add_edge(v2, s);
    101  
    102 
    103 
    104   edge_property_vector<list_graph, int> cap(flow_test);  //serves as length in dijkstra
    105   cap.put(s_v1, 16);
    106   cap.put(s_v2, 13);
    107   cap.put(v1_v2, 10);
    108   cap.put(v2_v1, 4);
    109   cap.put(v1_v3, 12);
    110   cap.put(v3_v2, 9);
    111   cap.put(v2_v4, 14);
    112   cap.put(v4_v3, 7);
    113   cap.put(v3_t, 20);
    114   cap.put(v4_t, 4);
    115   cap.put(v3_v3, 4);
    116   cap.put(s_w, 4);
    117   //  cap.put(v2_s, 0);
     67  /*  NodeIt s=flow_test.addNode();
     68  NodeIt v1=flow_test.addNode();
     69  NodeIt v2=flow_test.addNode();
     70  NodeIt v3=flow_test.addNode();
     71  NodeIt v4=flow_test.addNode();
     72  NodeIt t=flow_test.addNode();
     73  NodeIt w=flow_test.addNode();
     74
     75 
     76  NodeMap<ListGraph, std::string> Node_name(flow_test);
     77  Node_name.set(s, "s");
     78  Node_name.set(v1, "v1");
     79  Node_name.set(v2, "v2");
     80  Node_name.set(v3, "v3");
     81  Node_name.set(v4, "v4");
     82  Node_name.set(t, "t");
     83  Node_name.set(w, "w");
     84
     85  EdgeIt s_v1=flow_test.addEdge(s, v1);
     86  EdgeIt s_v2=flow_test.addEdge(s, v2);
     87  EdgeIt v1_v2=flow_test.addEdge(v1, v2);
     88  EdgeIt v2_v1=flow_test.addEdge(v2, v1);
     89  EdgeIt v1_v3=flow_test.addEdge(v1, v3);
     90  EdgeIt v3_v2=flow_test.addEdge(v3, v2);
     91  EdgeIt v2_v4=flow_test.addEdge(v2, v4);
     92  EdgeIt v4_v3=flow_test.addEdge(v4, v3);
     93  EdgeIt v3_t=flow_test.addEdge(v3, t);
     94  EdgeIt v4_t=flow_test.addEdge(v4, t);
     95  EdgeIt v3_v3=flow_test.addEdge(v3, v3);
     96  EdgeIt s_w=flow_test.addEdge(s, w);
     97  //  EdgeIt v2_s=flow_test.addEdge(v2, s);
     98 
     99
     100
     101  EdgeMap<ListGraph, int> cap(flow_test);  //serves as length in dijkstra
     102  cap.set(s_v1, 16);
     103  cap.set(s_v2, 13);
     104  cap.set(v1_v2, 10);
     105  cap.set(v2_v1, 4);
     106  cap.set(v1_v3, 12);
     107  cap.set(v3_v2, 9);
     108  cap.set(v2_v4, 14);
     109  cap.set(v4_v3, 7);
     110  cap.set(v3_t, 20);
     111  cap.set(v4_t, 4);
     112  cap.set(v3_v3, 4);
     113  cap.set(s_w, 4);
     114  //  cap.set(v2_s, 0);
    118115
    119116*/
    120117
    121118  //pelda 3, maxflowvalue=4
    122   /*      node_iterator s=flow_test.add_node();
    123   node_iterator v1=flow_test.add_node();
    124   node_iterator v2=flow_test.add_node();
    125   node_iterator t=flow_test.add_node();
    126   node_iterator w=flow_test.add_node();
    127  
    128   node_property_vector<list_graph, std::string> node_name(flow_test);
    129   node_name.put(s, "s");
    130   node_name.put(v1, "v1");
    131   node_name.put(v2, "v2");
    132   node_name.put(t, "t");
    133   node_name.put(w, "w");
    134 
    135   edge_iterator s_v1=flow_test.add_edge(s, v1);
    136   edge_iterator v1_v2=flow_test.add_edge(v1, v2);
    137   edge_iterator v2_t=flow_test.add_edge(v2, t);
    138   edge_iterator v1_v1=flow_test.add_edge(v1, v1);
    139   edge_iterator s_w=flow_test.add_edge(s, w);
    140 
    141 
    142   edge_property_vector<list_graph, int> cap(flow_test);
     119  /*      NodeIt s=flow_test.addNode();
     120  NodeIt v1=flow_test.addNode();
     121  NodeIt v2=flow_test.addNode();
     122  NodeIt t=flow_test.addNode();
     123  NodeIt w=flow_test.addNode();
     124 
     125  NodeMap<ListGraph, std::string> Node_name(flow_test);
     126  Node_name.set(s, "s");
     127  Node_name.set(v1, "v1");
     128  Node_name.set(v2, "v2");
     129  Node_name.set(t, "t");
     130  Node_name.set(w, "w");
     131
     132  EdgeIt s_v1=flow_test.addEdge(s, v1);
     133  EdgeIt v1_v2=flow_test.addEdge(v1, v2);
     134  EdgeIt v2_t=flow_test.addEdge(v2, t);
     135  EdgeIt v1_v1=flow_test.addEdge(v1, v1);
     136  EdgeIt s_w=flow_test.addEdge(s, w);
     137
     138
     139  EdgeMap<ListGraph, int> cap(flow_test);
    143140   
    144   cap.put(s_v1, 16);
    145   cap.put(v1_v2, 10);
    146   cap.put(v2_t, 4);
    147   cap.put(v1_v1, 3);
    148   cap.put(s_w, 5);
     141  cap.set(s_v1, 16);
     142  cap.set(v1_v2, 10);
     143  cap.set(v2_t, 4);
     144  cap.set(v1_v1, 3);
     145  cap.set(s_w, 5);
    149146  */
    150147 
    … …  
    154151  std::cout << "Testing reverse_bfs..." << std::endl;
    155152 
    156   reverse_bfs<list_graph> bfs_test(flow_test, t);
     153  reverse_bfs<ListGraph> bfs_test(flow_test, t);
    157154
    158155  bfs_test.run();
    159156
    160   for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
     157  for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
    161158    std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
    162159    }
    … …  
    168165  std::cout << "Testing preflow_push_hl..." << std::endl;
    169166 
    170   preflow_push_hl<list_graph, int> preflow_push_test(flow_test, s, t, cap);
     167  preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);
    171168
    172169  preflow_push_test.run();
    … …  
    174171  std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
    175172
    176   std::cout<< "The flow on edge s-v1 is "<< preflow_push_test.flowonedge(s_v1) << "."<<std::endl;
    177 
    178   edge_property_vector<list_graph, int> flow=preflow_push_test.allflow(); 
    179   for (each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) {
    180     std::cout <<"Flow on edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
     173  std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;
     174
     175   ListGraph::EdgeMap<int> flow=preflow_push_test.allflow(); 
     176  for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {
     177    std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
    181178    }
    182179
    183180  std::cout << "A minimum cut: " <<std::endl; 
    184   node_property_vector<list_graph, bool> mincut=preflow_push_test.mincut();
    185 
    186   for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
    187       if (mincut.get(v)) std::cout <<node_name.get(v)<< " ";
     181   ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();
     182
     183  for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
     184      if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";
    188185    }
    189186 
    … …  
    195192  std::cout << "Testing preflow_push_max_flow..." << std::endl;
    196193 
    197   preflow_push_max_flow<list_graph, int> max_flow_test(flow_test, s, t, cap);
     194  preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);
    198195
    199196  max_flow_test.run();
    … …  
    202199
    203200  std::cout << "A minimum cut: " <<std::endl; 
    204   node_property_vector<list_graph, bool> mincut2=max_flow_test.mincut();
    205 
    206   for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
    207     if (mincut2.get(v)) std::cout <<node_name.get(v)<< " ";
     201   ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();
     202
     203  for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
     204    if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";
    208205  }
    209206 
    … …  
    214211    std::cout << "Testing dijkstra..." << std::endl;
    215212 
    216     node_iterator root=v2;
    217 
    218     dijkstra<list_graph, int> dijkstra_test(flow_test, root, cap);
     213    NodeIt root=v2;
     214
     215    dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap);
    219216
    220217    dijkstra_test.run();
    221218
    222     for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
     219    for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
    223220      if (dijkstra_test.reach(w)) {
    224221      std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);
    225222      if (dijkstra_test.pred(w).valid()) {
    226       std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl;
     223      std::cout <<", a shortest path from the root ends with Edge " << dijkstra_test.pred(w) <<std::endl;
    227224      } else {
    228225       std::cout <<", this is the root."<<std::endl; }
Note: See TracChangeset for help on using the changeset viewer.