COIN-OR::LEMON - Graph Library

Changeset 19:3151a1026db9 in lemon-0.x for src


Ignore:
Timestamp:
01/20/04 18:39:13 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@32
Message:

* empty log message *

Location:
src/work
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci_bfs.hh

    r11 r19  
    44#include <queue>
    55
    6 #include <marci_graph_traits.hh>
    76#include <marci_property_vector.hh>
    87
     
    1110  template <typename graph_type>
    1211  struct bfs {
    13     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    14     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    15     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    16     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    17 
     12    typedef typename graph_type::node_iterator node_iterator;
     13    typedef typename graph_type::edge_iterator edge_iterator;
     14    typedef typename graph_type::each_node_iterator each_node_iterator;
     15    typedef typename graph_type::out_edge_iterator out_edge_iterator;
    1816    graph_type& G;
    1917    node_iterator s;
     
    2422    bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
    2523      bfs_queue.push(s);
    26       for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
     24      for(each_node_iterator i=G.first_node(); i.valid(); ++i)
    2725        reached.put(i, false);
    2826      reached.put(s, true);
     
    3533        out_edge_iterator e=G.first_out_edge(v);
    3634        bfs_queue.pop();
    37         for( ; e.is_valid(); ++e) {
     35        for( ; e.valid(); ++e) {
    3836          node_iterator w=G.head(e);
    3937          std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
     
    5452  template <typename graph_type>
    5553  struct bfs_visitor {
    56     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    57     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    58     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    59     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
     54    typedef typename graph_type::node_iterator node_iterator;
     55    typedef typename graph_type::edge_iterator edge_iterator;
     56    typedef typename graph_type::out_edge_iterator out_edge_iterator;
    6057    graph_type& G;
    6158    bfs_visitor(graph_type& _G) : G(_G) { }
     
    7471  template <typename graph_type, typename reached_type, typename visitor_type>
    7572  struct bfs_iterator {
    76     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    77     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    78     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    79     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    80 
     73    typedef typename graph_type::node_iterator node_iterator;
     74    typedef typename graph_type::edge_iterator edge_iterator;
     75    typedef typename graph_type::out_edge_iterator out_edge_iterator;
    8176    graph_type& G;
    8277    std::queue<out_edge_iterator>& bfs_queue;
     
    8479    visitor_type& visitor;
    8580    void process() {
    86       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     81      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    8782      if (bfs_queue.empty()) return;
    8883      out_edge_iterator e=bfs_queue.front();
     
    9893    }
    9994    bfs_iterator(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
    100       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
    101       is_valid();
     95      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
     96      valid();
    10297    }
    10398    bfs_iterator<graph_type, reached_type, visitor_type>& operator++() {
    104       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     99      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    105100      //if (bfs_queue.empty()) return *this;
    106       if (!is_valid()) return *this;
     101      if (!valid()) return *this;
    107102      ++(bfs_queue.front());
    108       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
    109       is_valid();
     103      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
     104      valid();
    110105      return *this;
    111106    }
    112107    //void next() {
    113     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     108    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    114109    //  if (bfs_queue.empty()) return;
    115110    //  ++(bfs_queue.front());
    116     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     111    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    117112    //}
    118     bool is_valid() {
    119       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     113    bool valid() {
     114      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    120115      if (bfs_queue.empty()) return false; else return true;
    121116    }
    122117    //bool finished() {
    123     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     118    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    124119    //  if (bfs_queue.empty()) return true; else return false;
    125120    //}
     
    130125  template <typename graph_type, typename reached_type>
    131126  struct bfs_iterator1 {
    132     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    133     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    134     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    135     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    136 
     127    typedef typename graph_type::node_iterator node_iterator;
     128    typedef typename graph_type::edge_iterator edge_iterator;
     129    typedef typename graph_type::out_edge_iterator out_edge_iterator;
    137130    graph_type& G;
    138131    std::queue<out_edge_iterator>& bfs_queue;
    139132    reached_type& reached;
    140     bool newly_reached;
     133    bool _newly_reached;
    141134    bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
    142       is_valid();
    143       if (!bfs_queue.empty() && bfs_queue.front().is_valid()) {
     135      valid();
     136      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
    144137        out_edge_iterator e=bfs_queue.front();
    145138        node_iterator w=G.head(e);
     
    147140          bfs_queue.push(G.first_out_edge(w));
    148141          reached.put(w, true);
    149           newly_reached=true;
     142          _newly_reached=true;
    150143        } else {
    151           newly_reached=false;
     144          _newly_reached=false;
    152145        }
    153146      }
    154147    }
    155148    bfs_iterator1<graph_type, reached_type>& operator++() {
    156       if (!is_valid()) return *this;
     149      if (!valid()) return *this;
    157150      ++(bfs_queue.front());
    158       is_valid();
    159       if (!bfs_queue.empty() && bfs_queue.front().is_valid()) {
     151      valid();
     152      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
    160153        out_edge_iterator e=bfs_queue.front();
    161154        node_iterator w=G.head(e);
     
    163156          bfs_queue.push(G.first_out_edge(w));
    164157          reached.put(w, true);
    165           newly_reached=true;
     158          _newly_reached=true;
    166159        } else {
    167           newly_reached=false;
     160          _newly_reached=false;
    168161        }
    169162      }
    170163      return *this;
    171164    }
    172     bool is_valid() {
    173       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     165    bool valid() {
     166      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    174167      if (bfs_queue.empty()) return false; else return true;
    175168    }
    176169    operator edge_iterator () { return bfs_queue.front(); }
    177     bool is_newly_reached() { return newly_reached; }
     170    bool newly_reached() { return _newly_reached; }
    178171
    179172  };
  • src/work/marci_graph_concept.txt

    r15 r19  
    1717marci_bfs.hh          //bfs, tejesen kiserleti
    1818marci_graph_demo.cc  //peldaprogi a lisas graf hasznalatahoz
    19 marci_graph_traits.hh //alapertelmezett graph_traits
    2019marci_list_graph.hh  //list_graph megvalositas
    2120marci_max_flow.hh     //folyam, kiserleti
     
    132131node_iterator metodusai:
    133132node_iterator();
    134 bool is_valid();
     133bool valid();
    135134void make_invalid();
    136135ezek nem tagfuggvenyek:
     
    145144edge_iterator metodusai:
    146145edge_iterator();
    147 bool is_valid();
     146bool valid();
    148147void make_invalid();
    149148ezek nem tagfvek:
     
    193192
    194193node_property_vector(graph_type&);
    195 void put(graph_traits<graph_type>::node_iterator, const T&);
    196 T get(graph_traits<graph_type>::node_iterator);
     194void put(graph_type::node_iterator, const T&);
     195T get(graph_type::node_iterator);
    197196
    198197Ugyanez edge_property_array-okkal
     
    202201
    203202edge_property_vector(graph_type&);
    204 void put(graph_traits<graph_type>::edge_iterator, const T&);
    205 get(graph_traits<graph_type>::edge_iterator);
     203void put(graph_type::edge_iterator, const T&);
     204get(graph_type::edge_iterator);
    206205
    207206 Ennyi nem javasolas utan, meg nehany szo.
  • src/work/marci_graph_demo.cc

    r12 r19  
    44
    55#include <marci_list_graph.hh>
    6 #include <marci_graph_traits.hh>
    76#include <marci_property_vector.hh>
    87#include <marci_bfs.hh>
     
    1312int main (int, char*[])
    1413{
    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;
    22 
     14  typedef list_graph::node_iterator node_iterator;
     15  typedef list_graph::edge_iterator edge_iterator;
     16  typedef list_graph::each_node_iterator each_node_iterator;
     17  typedef list_graph::each_edge_iterator each_edge_iterator;
     18  typedef list_graph::out_edge_iterator out_edge_iterator;
     19  typedef list_graph::in_edge_iterator in_edge_iterator;
     20  typedef list_graph::sym_edge_iterator sym_edge_iterator;
    2321  list_graph G;
    2422  std::vector<node_iterator> vector_of_node_iterators;
     
    3230  std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl;
    3331
    34   for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
     32  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
    3533    std::cout << "node " << G.id(i) << std::endl;
    3634    std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " ";
    37     for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) {
     35    for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
    3836      std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
    3937    }
     
    4139
    4240    std::cout<< " ";
    43     for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) {
     41    for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
    4442      std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
    4543    std::cout<<std::endl;
    4644
    4745    std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " ";
    48     for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
     46    for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
    4947      std::cout << j << " "; }
    5048    std::cout << std::endl;
    5149
    5250    std::cout<< " ";
    53     for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
     51    for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
    5452      std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
    5553    std::cout<<std::endl;
    5654
    5755    std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " ";
    58     for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) {
     56    for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
    5957      std::cout << j << " "; }
    6058    std::cout<<std::endl;
    6159
    6260    std::cout<< " ";
    63     for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) {
     61    for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
    6462      std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
    6563    std::cout<<std::endl;
     
    6765
    6866  std::cout << "all edges: ";
    69   for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {
     67  for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
    7068    std::cout << i << " ";
    7169  }
     
    8381  my_property_vector.put(vector_of_node_iterators[7], 1978);
    8482  std::cout << "some node property values..." << std::endl;
    85   for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
     83  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
    8684    std::cout << my_property_vector.get(i) << std::endl;
    8785  }
     
    8987  int _ii=1;
    9088  edge_property_vector<list_graph, int> my_edge_property(G);
    91   for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {
     89  for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
    9290    my_edge_property.put(i, _i);
    9391    _i*=_ii; ++_ii;
     
    9593
    9694  std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
    97   for(each_edge_iterator j=G.first_edge(); j.is_valid(); ++j) {
     95  for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) {
    9896    std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
    9997  }
     
    102100  //std::cout << "the same for inedges of the nodes..." << std::endl;
    103101  //k=0;
    104   //for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
    105   //  for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
     102  //for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
     103  //  for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
    106104  //    std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " ";
    107105  //  }
     
    113111  bfs_test.run();
    114112  std::cout << "reached: ";
    115   for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
     113  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
    116114    std::cout << bfs_test.reached.get(i) << " ";
    117115  }
    118116  std::cout<<std::endl;
    119117  std::cout << "dist: ";
    120   for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
     118  for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
    121119    std::cout << bfs_test.dist.get(i) << " ";
    122120  }
     
    168166  std::cout << "on directed graph graph" << std::endl; //<< flow_test;
    169167  std::cout << "names and capacity values" << std::endl;
    170   for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) {
     168  for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
    171169    std::cout << node_name.get(i) << ": ";
    172170    std::cout << "out edges: ";
    173     for(out_edge_iterator j=flow_test.first_out_edge(i); j.is_valid(); ++j)
     171    for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
    174172      std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
    175173    std::cout << "in edges: ";
    176     for(in_edge_iterator j=flow_test.first_in_edge(i); j.is_valid(); ++j)
     174    for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
    177175      std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
    178176    std::cout << std::endl;
     
    180178
    181179 
    182   //for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) {
     180  //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
    183181  //  std::cout << i << " ";
    184182  //}
  • src/work/marci_list_graph.hh

    r16 r19  
    2020    int node_id;
    2121    int edge_id;
     22    int _node_num;
     23    int _edge_num;
    2224
    2325    node_item* _first_node;
     
    8183      _last_node=p;
    8284      if (!_first_node) _first_node=p;
     85      ++_node_num;
    8386      return p;
    8487    }
     
    99102      _head->_last_in_edge=e;
    100103      if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
     104      ++_edge_num;
    101105      return e;
    102106    }
     
    106110    /* default constructor */
    107111
    108     list_graph() : node_id(0), edge_id(0), _first_node(0), _last_node(0) { }
    109    
     112    list_graph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
     113   
     114    int node_num() { return _node_num; }
     115    int edge_num() { return _edge_num; }
     116
    110117    /* functions to construct iterators from the graph, or from each other */
    111118
     
    210217      node_iterator() : node(0) { }
    211218      node_iterator(node_item* _node) : node(_node) { }
    212       bool is_valid() { return (node!=0); }
     219      bool valid() { return (node!=0); }
    213220      void make_invalid() { node=0; }
    214221      friend bool operator==(const node_iterator& u, const node_iterator& v) {
     
    240247      edge_iterator() : edge(0) { }
    241248      edge_iterator(edge_item* _edge) : edge(_edge) { }
    242       bool is_valid() { return (edge!=0); }
     249      bool valid() { return (edge!=0); }
    243250      void make_invalid() { edge=0; }
    244251      friend bool operator==(const edge_iterator& u, const edge_iterator& v) {
  • src/work/marci_makefile

    r9 r19  
    1 CCFLAGS = -Wall -ansi
    2 CC = /opt/experimental/bin/g++
     1CXXFLAGS = -Wall -ansi -I.
     2CXX = g++-3.0
    33
    4 marci_graph_demo: marci_graph_demo.cc marci_graph_traits.hh marci_list_graph.hh marci_property_vector.hh marci_bfs.hh marci_max_flow.hh
    5         $(CC) $(CCFLAGS) -I. marci_graph_demo.cc -o marci_graph_demo
     4marci_graph_demo: marci_graph_demo.cc marci_list_graph.hh marci_property_vector.hh marci_bfs.hh marci_max_flow.hh
     5        $(CXX) $(CXXFLAGS) marci_graph_demo.cc -o marci_graph_demo
  • src/work/marci_max_flow.hh

    r17 r19  
    44#include <algorithm>
    55
    6 #include <marci_graph_traits.hh>
    76#include <marci_property_vector.hh>
    87#include <marci_bfs.hh>
     
    1211  template<typename graph_type, typename T>
    1312  class res_graph_type {
    14     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    15     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    16     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    17     typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
    18 
     13    typedef typename graph_type::node_iterator node_iterator;
     14    typedef typename graph_type::each_node_iterator each_node_iterator;
     15    typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator;
    1916    graph_type& G;
    2017    edge_property_vector<graph_type, T>& flow;
     
    2320    res_graph_type(graph_type& _G, edge_property_vector<graph_type, T>& _flow, edge_property_vector<graph_type, T>& _capacity) : G(_G), flow(_flow), capacity(_capacity) { }
    2421
    25     class res_edge_it {
     22    class edge_iterator {
    2623      friend class res_graph_type<graph_type, T>;
    2724    protected:
    2825      res_graph_type<graph_type, T>* resG;
    29       sym_edge_iterator sym;
     26      old_sym_edge_iterator sym;
    3027    public:
    31       res_edge_it() { }
     28      edge_iterator() { }
    3229      //bool is_free() { 
    3330      //if (resG->G.a_node(sym)==resG->G.tail(sym)) {
     
    4441        }
    4542      }
    46       bool is_valid() { return sym.is_valid(); }
     43      bool valid() { return sym.valid(); }
    4744      void make_invalid() { sym.make_invalid(); }
    4845      void augment(T a) {
     
    5552    };
    5653
    57     class res_out_edge_it : public res_edge_it {
     54    class out_edge_iterator : public edge_iterator {
    5855    public:
    59       res_out_edge_it() { }
    60       res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
     56      out_edge_iterator() { }
     57      out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
    6158        resG=&_resG;
    6259        sym=resG->G.first_sym_edge(v);
    63         while( sym.is_valid() && !(free()>0) ) { ++sym; }
     60        while( sym.valid() && !(free()>0) ) { ++sym; }
    6461      }
    65       res_out_edge_it& operator++() {
     62      out_edge_iterator& operator++() {
    6663        ++sym;
    67         while( sym.is_valid() && !(free()>0) ) { ++sym; }
     64        while( sym.valid() && !(free()>0) ) { ++sym; }
    6865        return *this;
    6966      }
    7067    };
    7168
    72     res_out_edge_it first_out_edge(const node_iterator& v) {
    73       return res_out_edge_it(*this, v);
     69    out_edge_iterator first_out_edge(const node_iterator& v) {
     70      return out_edge_iterator(*this, v);
    7471    }
    7572
     
    7875    }
    7976
    80     node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
    81     node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
     77    node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); }
     78    node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); }
    8279
    8380    int id(const node_iterator& v) { return G.id(v); }
    8481
    8582    //node_iterator invalid_node() { return G.invalid_node(); }
    86     //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
    87    
    88   };
    89 
    90   template <typename graph_type, typename T>
    91   struct graph_traits< res_graph_type<graph_type, T> > {
    92     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    93     typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
    94     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    95     typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
     83    //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
    9684  };
    9785
    9886  template <typename graph_type, typename T>
    9987  struct max_flow_type {
    100    
    101     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    102     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    103     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    104     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    105     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
    106 
     88    typedef typename graph_type::node_iterator node_iterator;
     89    typedef typename graph_type::edge_iterator edge_iterator;
     90    typedef typename graph_type::each_node_iterator each_node_iterator;
     91    typedef typename graph_type::out_edge_iterator out_edge_iterator;
     92    typedef typename graph_type::in_edge_iterator in_edge_iterator;
    10793    graph_type& G;
    10894    node_iterator s;
     
    11298
    11399    max_flow_type(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) {
    114       for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
    115         for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)
     100      for(each_node_iterator i=G.first_node(); i.valid(); ++i)
     101        for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
    116102          flow.put(j, 0);
    117103    }
     
    124110        augment=false;
    125111
    126         typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
     112        typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type;
    127113        bfs_queue_type bfs_queue;
    128114        bfs_queue.push(res_graph.first_out_edge(s));
     
    135121        res_bfs(res_graph, bfs_queue, reached);
    136122
    137         typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
     123        typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type;
    138124        pred_type pred(res_graph);
    139         graph_traits<aug_graph_type>::edge_iterator a;
     125        aug_graph_type::edge_iterator a;
    140126        a.make_invalid();
    141127        pred.put(s, a);
     
    145131       
    146132        //searching for augmenting path
    147         while ( res_bfs.is_valid() ) {
     133        while ( res_bfs.valid() ) {
    148134          //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
    149           if (res_bfs.is_newly_reached()) {
    150             graph_traits<aug_graph_type>::edge_iterator e;
     135          if (res_bfs.newly_reached()) {
     136            aug_graph_type::edge_iterator e;
    151137            e=res_bfs;
    152138            node_iterator v=res_graph.tail(e);
     
    154140            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
    155141            pred.put(w, e);
    156             if (pred.get(v).is_valid()) {
     142            if (pred.get(v).valid()) {
    157143              free.put(w, std::min(free.get(v), e.free()));
    158144              //std::cout <<" nem elso csucs: ";
     
    174160          T augment_value=free.get(t);
    175161          std::cout<<"augmentation: ";
    176           while (pred.get(n).is_valid()) {
    177             graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
     162          while (pred.get(n).valid()) {
     163            aug_graph_type::edge_iterator e=pred.get(n);
    178164            e.augment(augment_value);
    179165            std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
     
    184170
    185171        std::cout << "actual flow: "<< std::endl;
    186         for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
     172        for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) {
    187173          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    188174        }
  • src/work/marci_property_vector.hh

    r9 r19  
    33
    44#include <vector>
    5 
    6 #include <marci_graph_traits.hh>
    75
    86namespace marci {
     
    119  int number_of(iterator _it) {
    1210    int i=0;
    13     for( ; _it.is_valid(); ++_it) { ++i; }
     11    for( ; _it.valid(); ++_it) { ++i; }
    1412    return i;
    1513  }
     
    1715  template <typename graph_type, typename T>
    1816  class node_property_vector {
    19     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    20     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
     17    typedef typename list_graph::node_iterator node_iterator;
     18    typedef typename list_graph::each_node_iterator each_node_iterator;
    2119    graph_type& G;
    2220    std::vector<T> container;
     
    2422    node_property_vector(graph_type& _G) : G(_G) {
    2523      int i=0;
    26       for(each_node_iterator it=G.first_node(); it.is_valid(); ++it) ++i;
     24      for(each_node_iterator it=G.first_node(); it.valid(); ++it) ++i;
    2725      container.resize(i);
    2826    }
    2927    node_property_vector(graph_type& _G, T a) : G(_G) {
    30       for(each_node_iterator it=G.first_node(); it.is_valid(); ++it) { container.push_back(a); }
     28      for(each_node_iterator it=G.first_node(); it.valid(); ++it) { container.push_back(a); }
    3129    }
    3230    void put(node_iterator nit, const T& a) { container[G.id(nit)]=a; }
     
    3634  template <typename graph_type, typename T>
    3735  class edge_property_vector {
    38     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    39     typedef typename graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
     36    typedef typename graph_type::edge_iterator edge_iterator;
     37    typedef typename graph_type::each_edge_iterator each_edge_iterator;
    4038    graph_type& G;
    4139    std::vector<T> container;
     
    4341    edge_property_vector(graph_type& _G) : G(_G) {
    4442      int i=0;
    45       for(each_edge_iterator it=G.first_edge(); it.is_valid(); ++it) ++i;
     43      for(each_edge_iterator it=G.first_edge(); it.valid(); ++it) ++i;
    4644      container.resize(i);
    4745    }
    4846    edge_property_vector(graph_type& _G, T a) : G(_G) {
    49       for(each_edge_iterator it=G.first_edge(); it.is_valid(); ++it) {
     47      for(each_edge_iterator it=G.first_edge(); it.valid(); ++it) {
    5048        container.push_back(a);
    5149      }
Note: See TracChangeset for help on using the changeset viewer.