COIN-OR::LEMON - Graph Library

Changeset 77:69b2d279c8f0 in lemon-0.x for src/work/athos/pf_demo.cc


Ignore:
Timestamp:
02/16/04 16:57:59 (17 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@100
Message:

Kijavitottam a preflow_push algoritmust az uj koncept szerint.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/pf_demo.cc

    r36 r77  
    33#include <string>
    44
    5 #include "marci_list_graph.hh"
     5#include "list_graph.hh"
    66#include "marci_graph_traits.hh"
    7 #include "marci_property_vector.hh"
     7//#include "marci_property_vector.hh"
    88#include "preflow_push.hh"
    99
     
    1313int main (int, char*[])
    1414{
    15   typedef graph_traits<list_graph>::node_iterator node_iterator;
    16   typedef graph_traits<list_graph>::edge_iterator edge_iterator;
    17   typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
    18   typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
    19   typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
    20   typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
    21   typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
    2215
    23   list_graph flow_test;
    24  
    2516 
     17  typedef ListGraph::NodeIt NodeIt;
     18  typedef ListGraph::EdgeIt EdgeIt;
     19  /*
     20  typedef ListGraph::EachNodeIt EachNodeIt;
     21  typedef ListGraph::EachEdgeIt EachEdgeIt;
     22  typedef ListGraph::OutEdgeIt OutEdgeIt;
     23  typedef ListGraph::InEdgeIt InEdgeIt;
     24  typedef ListGraph::SymEdgeIt SymEdgeIt;
     25  */
     26 
     27  //Marci példája
     28  ListGraph flowG;
     29
     30  NodeIt s=flowG.addNode();
     31  NodeIt v1=flowG.addNode();
     32  NodeIt v2=flowG.addNode();
     33  NodeIt v3=flowG.addNode();
     34  NodeIt v4=flowG.addNode();
     35  NodeIt t=flowG.addNode();
     36 
     37
     38  EdgeIt s_v1=flowG.addEdge(s, v1);
     39  EdgeIt s_v2=flowG.addEdge(s, v2);
     40  EdgeIt v1_v2=flowG.addEdge(v1, v2);
     41  EdgeIt v2_v1=flowG.addEdge(v2, v1);
     42  EdgeIt v1_v3=flowG.addEdge(v1, v3);
     43  EdgeIt v3_v2=flowG.addEdge(v3, v2);
     44  EdgeIt v2_v4=flowG.addEdge(v2, v4);
     45  EdgeIt v4_v3=flowG.addEdge(v4, v3);
     46  EdgeIt v3_t=flowG.addEdge(v3, t);
     47  EdgeIt v4_t=flowG.addEdge(v4, t);
     48
     49  ListGraph::EdgeMap<int> cap(flowG);
     50
     51  cap.set(s_v1, 16);
     52  cap.set(s_v2, 13);
     53  cap.set(v1_v2, 10);
     54  cap.set(v2_v1, 4);
     55  cap.set(v1_v3, 12);
     56  cap.set(v3_v2, 9);
     57  cap.set(v2_v4, 14);
     58  cap.set(v4_v3, 7);
     59  cap.set(v3_t, 20);
     60  cap.set(v4_t, 4);
     61
     62
     63
     64
     65
     66
     67
     68  /*
    2669  //Ahuja könyv példája
    2770  node_iterator s=flow_test.add_node();
    28   node_iterator v2=flow_test.add_node();
    29   node_iterator v3=flow_test.add_node();
    30   node_iterator v4=flow_test.add_node();
    31   node_iterator v5=flow_test.add_node();
    32   node_iterator t=flow_test.add_node();
     71  NodeIt v2=flow_test.add_node();
     72  NodeIt v3=flow_test.add_node();
     73  NodeIt v4=flow_test.add_node();
     74  NodeIt v5=flow_test.add_node();
     75  NodeIt t=flow_test.add_node();
    3376 
    3477  node_property_vector<list_graph, std::string> node_name(flow_test);
     
    71114  //cap.put(t_s, 20);
    72115
    73  
    74   /*
    75   //Marci példája
    76   node_iterator s=flow_test.add_node();
    77   node_iterator v1=flow_test.add_node();
    78   node_iterator v2=flow_test.add_node();
    79   node_iterator v3=flow_test.add_node();
    80   node_iterator v4=flow_test.add_node();
    81   node_iterator t=flow_test.add_node();
    82  
    83   node_property_vector<list_graph, std::string> node_name(flow_test);
    84   node_name.put(s, "s");
    85   node_name.put(v1, "v1");
    86   node_name.put(v2, "v2");
    87   node_name.put(v3, "v3");
    88   node_name.put(v4, "v4");
    89   node_name.put(t, "t");
     116  */
    90117
    91   edge_iterator s_v1=flow_test.add_edge(s, v1);
    92   edge_iterator s_v2=flow_test.add_edge(s, v2);
    93   edge_iterator v1_v2=flow_test.add_edge(v1, v2);
    94   edge_iterator v2_v1=flow_test.add_edge(v2, v1);
    95   edge_iterator v1_v3=flow_test.add_edge(v1, v3);
    96   edge_iterator v3_v2=flow_test.add_edge(v3, v2);
    97   edge_iterator v2_v4=flow_test.add_edge(v2, v4);
    98   edge_iterator v4_v3=flow_test.add_edge(v4, v3);
    99   edge_iterator v3_t=flow_test.add_edge(v3, t);
    100   edge_iterator v4_t=flow_test.add_edge(v4, t);
    101  
    102   edge_property_vector<list_graph, int> cap(flow_test); 
    103   cap.put(s_v1, 16);
    104   cap.put(s_v2, 13);
    105   cap.put(v1_v2, 10);
    106   cap.put(v2_v1, 4);
    107   cap.put(v1_v3, 12);
    108   cap.put(v3_v2, 9);
    109   cap.put(v2_v4, 14);
    110   cap.put(v4_v3, 7);
    111   cap.put(v3_t, 20);
    112   cap.put(v4_t, 4);
    113   */
     118
     119
    114120  /*Egyszerû példa
    115   node_iterator s=flow_test.add_node();
    116   node_iterator v1=flow_test.add_node();
    117   node_iterator v2=flow_test.add_node();
    118   node_iterator t=flow_test.add_node();
     121  NodeIt s=flow_test.add_node();
     122  NodeIt v1=flow_test.add_node();
     123  NodeIt v2=flow_test.add_node();
     124  NodeIt t=flow_test.add_node();
    119125 
    120126  node_property_vector<list_graph, std::string> node_name(flow_test);
     
    136142
    137143  std::cout << "preflow-push algorithm test..." << std::endl;
     144
     145  /*
    138146  std::cout << "on directed graph graph" << std::endl; //<< flow_test;
    139147  std::cout << "names and capacity values" << std::endl;
    140   for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
     148  for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {
    141149    std::cout << node_name.get(i) << ": ";
    142150    std::cout << "out edges: ";
     
    148156    std::cout << std::endl;
    149157  }
    150 
     158  */
    151159 
    152   //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
     160  //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) {
    153161  //  std::cout << i << " ";
    154162  //}
    155163 
    156   preflow_push<list_graph, int> preflow_push_test(flow_test, s, t, cap);
     164  preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap);
    157165  cout << preflow_push_test.run()<<endl;
    158166
Note: See TracChangeset for help on using the changeset viewer.