COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 331:f5461f8bc59b in lemon-0.x for src/work/athos/pf_demo.cc


Ignore:
Timestamp:
04/15/04 19:03:44 (20 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@449
Message:

Elkezdtem atirni a preflow_push-t. Csinaltam egy backupot graph wrapper nelkul (without gw, azaz wogw)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/athos/pf_demo.cc

    r201 r331  
    33#include <string>
    44
    5 #include "list_graph.hh"
    6 #include "marci_graph_traits.hh"
     5#include "list_graph.h"
     6//#include "marci_graph_traits.hh"
    77//#include "marci_property_vector.hh"
    88#include "preflow_push.hh"
    … …  
    1414{
    1515
    16  
    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   ListGraph flowG;
     16  typedef ListGraph::Node Node;
     17  typedef ListGraph::Edge Edge;
     18
     19  ListGraph graph;
    2720
    2821  /*
    … …  
    3023
    3124
    32   NodeIt s=flowG.addNode();
    33   NodeIt v1=flowG.addNode();
    34   NodeIt v2=flowG.addNode();
    35   NodeIt v3=flowG.addNode();
    36   NodeIt v4=flowG.addNode();
    37   NodeIt t=flowG.addNode();
     25  NodeIt s=graph.addNode();
     26  NodeIt v1=graph.addNode();
     27  NodeIt v2=graph.addNode();
     28  NodeIt v3=graph.addNode();
     29  NodeIt v4=graph.addNode();
     30  NodeIt t=graph.addNode();
    3831 
    3932
    40   EdgeIt s_v1=flowG.addEdge(s, v1);
    41   EdgeIt s_v2=flowG.addEdge(s, v2);
    42   EdgeIt v1_v2=flowG.addEdge(v1, v2);
    43   EdgeIt v2_v1=flowG.addEdge(v2, v1);
    44   EdgeIt v1_v3=flowG.addEdge(v1, v3);
    45   EdgeIt v3_v2=flowG.addEdge(v3, v2);
    46   EdgeIt v2_v4=flowG.addEdge(v2, v4);
    47   EdgeIt v4_v3=flowG.addEdge(v4, v3);
    48   EdgeIt v3_t=flowG.addEdge(v3, t);
    49   EdgeIt v4_t=flowG.addEdge(v4, t);
     33  EdgeIt s_v1=graph.addEdge(s, v1);
     34  EdgeIt s_v2=graph.addEdge(s, v2);
     35  EdgeIt v1_v2=graph.addEdge(v1, v2);
     36  EdgeIt v2_v1=graph.addEdge(v2, v1);
     37  EdgeIt v1_v3=graph.addEdge(v1, v3);
     38  EdgeIt v3_v2=graph.addEdge(v3, v2);
     39  EdgeIt v2_v4=graph.addEdge(v2, v4);
     40  EdgeIt v4_v3=graph.addEdge(v4, v3);
     41  EdgeIt v3_t=graph.addEdge(v3, t);
     42  EdgeIt v4_t=graph.addEdge(v4, t);
    5043
    51   ListGraph::EdgeMap<int> cap(flowG);
     44  ListGraph::EdgeMap<int> length(graph);
    5245
    53   cap.set(s_v1, 16);
    54   cap.set(s_v2, 13);
    55   cap.set(v1_v2, 10);
    56   cap.set(v2_v1, 4);
    57   cap.set(v1_v3, 12);
    58   cap.set(v3_v2, 9);
    59   cap.set(v2_v4, 14);
    60   cap.set(v4_v3, 7);
    61   cap.set(v3_t, 20);
    62   cap.set(v4_t, 4);
     46  length.set(s_v1, 16);
     47  length.set(s_v2, 13);
     48  length.set(v1_v2, 10);
     49  length.set(v2_v1, 4);
     50  length.set(v1_v3, 12);
     51  length.set(v3_v2, 9);
     52  length.set(v2_v4, 14);
     53  length.set(v4_v3, 7);
     54  length.set(v3_t, 20);
     55  length.set(v4_t, 4);
    6356  */
    6457
    … …  
    6659  //Ahuja könyv példája
    6760
    68   NodeIt s=flowG.addNode();
    69   NodeIt v2=flowG.addNode();
    70   NodeIt v3=flowG.addNode();
    71   NodeIt v4=flowG.addNode();
    72   NodeIt v5=flowG.addNode();
    73   NodeIt t=flowG.addNode();
     61  Node s=graph.addNode();
     62  Node v2=graph.addNode();
     63  Node v3=graph.addNode();
     64  Node v4=graph.addNode();
     65  Node v5=graph.addNode();
     66  Node t=graph.addNode();
    7467
    75   EdgeIt s_v2=flowG.addEdge(s, v2);
    76   EdgeIt s_v3=flowG.addEdge(s, v3);
    77   EdgeIt v2_v4=flowG.addEdge(v2, v4);
    78   EdgeIt v2_v5=flowG.addEdge(v2, v5);
    79   EdgeIt v3_v5=flowG.addEdge(v3, v5);
    80   EdgeIt v4_t=flowG.addEdge(v4, t);
    81   EdgeIt v5_t=flowG.addEdge(v5, t);
     68  Edge s_v2=graph.addEdge(s, v2);
     69  Edge s_v3=graph.addEdge(s, v3);
     70  Edge v2_v4=graph.addEdge(v2, v4);
     71  Edge v2_v5=graph.addEdge(v2, v5);
     72  Edge v3_v5=graph.addEdge(v3, v5);
     73  Edge v4_t=graph.addEdge(v4, t);
     74  Edge v5_t=graph.addEdge(v5, t);
    8275 
    8376  //Kis modositas
    84   //edge_iterator v2_s=flowG.add_edge(v2, s);
     77  //edge_iterator v2_s=graph.add_edge(v2, s);
    8578
    86   ListGraph::EdgeMap<int> cap(flowG);
     79  ListGraph::EdgeMap<int> length(graph);
    8780
    88   cap.set(s_v2, 10);
    89   cap.set(s_v3, 10);
    90   cap.set(v2_v4, 5);
    91   cap.set(v2_v5, 8);
    92   cap.set(v3_v5, 5);
    93   cap.set(v4_t, 8);
    94   cap.set(v5_t, 8);
     81  length.set(s_v2, 10);
     82  length.set(s_v3, 10);
     83  length.set(v2_v4, 5);
     84  length.set(v2_v5, 8);
     85  length.set(v3_v5, 5);
     86  length.set(v4_t, 8);
     87  length.set(v5_t, 8);
    9588
    9689  //Kis modositas
    97   //cap.put(v2_s, 100);
    98  
     90  //length.put(v2_s, 100);
    9991
    10092
    10193
    102   /*Egyszerû példa
    103   NodeIt s=flow_test.add_node();
    104   NodeIt v1=flow_test.add_node();
    105   NodeIt v2=flow_test.add_node();
    106   NodeIt t=flow_test.add_node();
    107  
    108   node_property_vector<list_graph, std::string> node_name(flow_test);
    109   node_name.put(s, "s");
    110   node_name.put(v1, "v1");
    111   node_name.put(v2, "v2");
    112   node_name.put(t, "t");
    113 
    114   edge_iterator s_v1=flow_test.add_edge(s, v1);
    115   edge_iterator v1_v2=flow_test.add_edge(v1, v2);
    116   edge_iterator v2_t=flow_test.add_edge(v2, t);
    117 
    118   edge_property_vector<list_graph, int> cap(flow_test);
    119    
    120   cap.put(s_v1, 16);
    121   cap.put(v1_v2, 10);
    122   cap.put(v2_t, 4);
    123   */
    124 
    12594  std::cout << "preflow-push algorithm test..." << std::endl;
    12695
    127   /*
    128   std::cout << "on directed graph graph" << std::endl; //<< flow_test;
    129   std::cout << "names and capacity values" << std::endl;
    130   for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) {
    131     std::cout << node_name.get(i) << ": ";
    132     std::cout << "out edges: ";
    133     for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
    134       std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
    135     std::cout << "in edges: ";
    136     for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
    137       std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
    138     std::cout << std::endl;
    139   }
    140   */
    14196 
    142   //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) {
    143   //  std::cout << i << " ";
    144   //}
    145  
    146   preflow_push<ListGraph, int> preflow_push_test(flowG, s, t, cap);
     97  preflow_push<ListGraph, int> preflow_push_test(graph, s, t, length);
    14798  cout << preflow_push_test.run()<<endl;
    14899
    … …  
    152103  return 0;
    153104}
    154 
    155 
    156 
    157 
    158 
    159 
    160 
    161 
    162 
Note: See TracChangeset for help on using the changeset viewer.