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


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

Location:
src/work/jacint
Files:
2 added
4 edited

Legend:

Unmodified
Added
Removed

  • src/work/jacint/dijkstra.hh

    r50 r78  
    22 *dijkstra
    33 *by jacint
    4  *Performs Dijkstra's algorithm from node s.
     4 *Performs Dijkstra's algorithm from Node s.
    55 *
    66 *Constructor:
    77 *
    8  *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance)
     8 *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance)
    99 *
    1010 *
    … …  
    1717 *
    1818 *
    19  *T dist(node_iterator v) : returns the distance from s to v.
     19 *T dist(NodeIt v) : returns the distance from s to v.
    2020 *   It is 0 if v is not reachable from s.
    2121 *
    2222 *
    23  *edge_iterator pred(node_iterator v)
    24  *   Returns the last edge of a shortest s-v path.
     23 *EdgeIt pred(NodeIt v)
     24 *   Returns the last Edge of a shortest s-v path.
    2525 *   Returns an invalid iterator if v=s or v is not
    2626 *   reachable from s.
    2727 *
    2828 *
    29  *bool reach(node_iterator v) : true if v is reachable from s
     29 *bool reach(NodeIt v) : true if v is reachable from s
    3030 *
    3131 *
    … …  
    4949
    5050#include <marci_graph_traits.hh>
    51 #include <marci_property_vector.hh>
     51#include <marciMap.hh>
    5252
    5353
    … …  
    6161    template <typename graph_type, typename T>
    6262    class dijkstra{
    63       typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    64       typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    65       typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    66       typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
    67       typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
     63      typedef typename graph_traits<graph_type>::NodeIt NodeIt;
     64      typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
     65      typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
     66      typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
     67      typedef typename graph_traits<graph_type>::OutEdgeIt OutEdgeIt;
    6868     
    6969     
    7070      graph_type& G;
    71       node_iterator s;
    72       node_property_vector<graph_type, edge_iterator> predecessor;
    73       node_property_vector<graph_type, T> distance;
    74       edge_property_vector<graph_type, T> length;
    75       node_property_vector<graph_type, bool> reached;
     71      NodeIt s;
     72      NodeMap<graph_type, EdgeIt> predecessor;
     73      NodeMap<graph_type, T> distance;
     74      EdgeMap<graph_type, T> length;
     75      NodeMap<graph_type, bool> reached;
    7676         
    7777  public :
    7878
    7979    /*
    80       The distance of all the nodes is 0.
     80      The distance of all the Nodes is 0.
    8181    */
    82     dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<graph_type, T>& _length) :
     82    dijkstra(graph_type& _G, NodeIt _s, EdgeMap<graph_type, T>& _length) :
    8383      G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { }
    8484   
    … …  
    8686     
    8787      /*By Misi.*/
    88       struct node_dist_comp
     88      struct Node_dist_comp
    8989      {
    90         node_property_vector<graph_type, T> &d;
    91         node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {}
     90        NodeMap<graph_type, T> &d;
     91        Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {}
    9292       
    93         bool operator()(const node_iterator& u, const node_iterator& v) const
     93        bool operator()(const NodeIt& u, const NodeIt& v) const
    9494        { return d.get(u) < d.get(v); }
    9595      };
    … …  
    9999      void run() {
    100100       
    101         node_property_vector<graph_type, bool> scanned(G, false);
    102         std::priority_queue<node_iterator, vector<node_iterator>, node_dist_comp>
    103           heap(( node_dist_comp(distance) ));
     101        NodeMap<graph_type, bool> scanned(G, false);
     102        std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp>
     103          heap(( Node_dist_comp(distance) ));
    104104     
    105105        heap.push(s);
    … …  
    108108        while (!heap.empty()) {
    109109
    110           node_iterator v=heap.top();   
     110          NodeIt v=heap.top(); 
    111111          heap.pop();
    112112
    … …  
    114114          if (!scanned.get(v)) {
    115115       
    116             for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) {
    117               node_iterator w=G.head(e);
     116            for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
     117              NodeIt w=G.head(e);
    118118
    119119              if (!scanned.get(w)) {
    … …  
    148148
    149149      /*
    150        *Returns the distance of the node v.
    151        *It is 0 for the root and for the nodes not
     150       *Returns the distance of the Node v.
     151       *It is 0 for the root and for the Nodes not
    152152       *reachable form the root.
    153153       */     
    154       T dist(node_iterator v) {
     154      T dist(NodeIt v) {
    155155        return -distance.get(v);
    156156      }
    … …  
    159159
    160160      /*
    161        *  Returns the last edge of a shortest s-v path.
     161       *  Returns the last Edge of a shortest s-v path.
    162162       *  Returns an invalid iterator if v=root or v is not
    163163       *  reachable from the root.
    164164       */     
    165       edge_iterator pred(node_iterator v) {
     165      EdgeIt pred(NodeIt v) {
    166166        if (v!=s) { return predecessor.get(v);}
    167         else {return edge_iterator();}
     167        else {return EdgeIt();}
    168168      }
    169169     
    170170
    171171     
    172       bool reach(node_iterator v) {
     172      bool reach(NodeIt v) {
    173173        return reached.get(v);
    174174      }

  • 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; }

  • src/work/jacint/preflow_push_hl.h

    r72 r78  
    3030#include <stack>
    3131
    32 #include <reverse_bfs.hh>
     32#include <reverse_bfs.h>
    3333
    3434namespace marci {
    3535
    36   template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
     36  template <typename Graph, typename T>
    3737  class preflow_push_hl {
    3838   
    … …  
    4848    NodeIt s;
    4949    NodeIt t;
    50     Graph::EdgeMap<T> flow;
    51     Graph::EdgeMap<T> capacity;
     50    typename Graph::EdgeMap<T> flow;
     51    typename Graph::EdgeMap<T> capacity;
    5252    T value;
    53     Graph::NodeMap<bool> mincutvector;
     53    typename Graph::NodeMap<bool> mincutvector;
    5454
    5555   
    … …  
    5757
    5858    preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t,
    59                     Graph::EdgeMap<T>& _capacity) :
     59                    typename Graph::EdgeMap<T>& _capacity) :
    6060      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { }
    6161
    … …  
    6969    void run() {
    7070 
    71       Graph::NodeMap<int> level(G);         //level of Node
    72       Graph::NodeMap<T> excess(G);          //excess of Node
     71      typename Graph::NodeMap<int> level(G);         //level of Node
     72      typename Graph::NodeMap<T> excess(G);          //excess of Node
    7373           
    7474      int n=G.nodeNum();                        //number of Nodes
    … …  
    8383      /*Reverse_bfs from t, to find the starting level.*/
    8484
    85       reverse_bfs<list_graph> bfs(G, t);
     85      reverse_bfs<Graph> bfs(G, t);
    8686      bfs.run();
    8787      for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
    … …  
    269269    */
    270270
    271     EdgeMap<graph_type, T> allflow() {
     271    typename Graph::EdgeMap<T> allflow() {
    272272      return flow;
    273273    }
    … …  
    279279    */
    280280   
    281     NodeMap<graph_type, bool> mincut() {
     281    typename Graph::NodeMap<bool> mincut() {
    282282   
    283283      std::queue<NodeIt> queue;
    … …  
    311311   
    312312    }
    313 
    314 
    315313  };
    316314}//namespace marci

  • src/work/jacint/reverse_bfs.hh

    r50 r78  
    22reverse_bfs
    33by jacint
    4 Performs a bfs on the out edges. It does not count predecessors,
     4Performs a bfs on the out Edges. It does not count predecessors,
    55only the distances, but one can easily modify it to know the pred as well.
    66
    77Constructor:
    88
    9 reverse_bfs(graph_type& G, node_iterator t)
     9reverse_bfs(graph_type& G, NodeIt t)
    1010
    1111
    … …  
    1717  The following function should be used after run() was already run.
    1818
    19 int dist(node_iterator v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
     19int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v.
    2020
    2121*/
    … …  
    2626
    2727#include <marci_graph_traits.hh>
    28 #include <marci_property_vector.hh>
     28#include <marciMap.hh>
    2929
    3030
    … …  
    3434  template <typename graph_type>
    3535  class reverse_bfs {
    36     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    37     //typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    38     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    39     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
     36    typedef typename graph_traits<graph_type>::NodeIt NodeIt;
     37    //typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
     38    typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
     39    typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
    4040
    4141
    4242    graph_type& G;
    43     node_iterator t;
    44 //    node_property_vector<graph_type, edge_iterator> pred;
    45     node_property_vector<graph_type, int> distance;
     43    NodeIt t;
     44//    NodeMap<graph_type, EdgeIt> pred;
     45    NodeMap<graph_type, int> distance;
    4646   
    4747
    … …  
    4949
    5050    /*
    51       The distance of the nodes is n, except t for which it is 0.
     51      The distance of the Nodes is n, except t for which it is 0.
    5252    */
    53     reverse_bfs(graph_type& _G, node_iterator _t) : G(_G), t(_t), distance(G, number_of(G.first_node())) {
     53    reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) {
    5454      distance.put(t,0);
    5555    }
    … …  
    5757    void run() {
    5858
    59       node_property_vector<graph_type, bool> reached(G, false);
     59      NodeMap<graph_type, bool> reached(G, false);
    6060      reached.put(t, true);
    6161
    62       std::queue<node_iterator> bfs_queue;
     62      std::queue<NodeIt> bfs_queue;
    6363      bfs_queue.push(t);
    6464
    6565      while (!bfs_queue.empty()) {
    6666
    67         node_iterator v=bfs_queue.front();     
     67        NodeIt v=bfs_queue.front();     
    6868        bfs_queue.pop();
    6969
    70         for(in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {
    71           node_iterator w=G.tail(e);
     70        for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
     71          NodeIt w=G.tail(e);
    7272          if (!reached.get(w)) {
    7373            bfs_queue.push(w);
    … …  
    8181
    8282
    83     int dist(node_iterator v) {
     83    int dist(NodeIt v) {
    8484      return distance.get(v);
    8585    }
Note: See TracChangeset for help on using the changeset viewer.