COIN-OR::LEMON - Graph Library

Changeset 69:24c2c2989e0f in lemon-0.x


Ignore:
Timestamp:
02/09/04 14:11:10 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@85
Message:

.

Location:
src/work
Files:
7 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.hh

    r64 r69  
    9797    int id(NodeIt v) const { return G.id(v); }
    9898
    99     template <typename ValueType>
     99    template <typename S>
    100100    class NodeMap {
    101       typename Graph::NodeMap<ValueType> node_map;
     101      typename Graph::NodeMap<S> node_map;
    102102    public:
    103103      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
    104       NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, ValueType a) : node_map(_G.G, a) { }
    105       void set(NodeIt nit, ValueType a) { node_map.set(nit, a); }
    106       ValueType get(NodeIt nit) const { return node_map.get(nit); }
     104      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
     105      void set(NodeIt nit, S a) { node_map.set(nit, a); }
     106      S get(NodeIt nit) const { return node_map.get(nit); }
    107107    };
    108108
     
    141141      //searching for augmenting path
    142142      while ( !res_bfs.finished() ) {
    143         //std::queue<AugOutEdgeIt> bfs_copy(res_bfs.getBfsQueue());
    144         //while (!bfs_copy.empty()) {
    145         //  AugOutEdgeIt e=bfs_copy.front();
    146         //  bfs_copy.pop();
    147         //  if (e.valid()) {
    148         //    std::cout<<"queue:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<" ";
    149         //  } else {
    150         //    std::cout<<"queue:"<<res_graph.aNode(e)<<"->"<<" ";
    151         //  }
    152         //}
    153         //std::cout<<std::endl;
    154143        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
    155         //if (e.valid()) {
    156         //  std::cout<<"actual:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<std::endl;
    157         //} else {
    158         //  std::cout<<"actual:"<<res_graph.aNode(e)<<"->"<<std::endl;
    159         //}
    160144        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
    161145          NodeIt v=res_graph.tail(e);
    162146          NodeIt w=res_graph.head(e);
    163           //std::cout<<v<<"->"<<w<<std::endl;
    164147          pred.set(w, e);
    165148          if (pred.get(v).valid()) {
     
    177160        NodeIt n=t;
    178161        T augment_value=free.get(t);
    179         //std::cout<<"augmentation: ";
    180162        while (pred.get(n).valid()) {
    181163          AugEdgeIt e=pred.get(n);
    182164          e.augment(augment_value);
    183           //std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
    184165          n=res_graph.tail(e);
    185166        }
    186         //std::cout<<std::endl;
    187167      }
    188       //std::cout << "actual flow: "<< std::endl;
    189       //for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
    190       //std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    191       //}
    192       //std::cout<<std::endl;
    193168
    194169      return _augment;
     
    197172      while (augment()) { }
    198173    }
     174    T flowValue() {
     175      T a=0;
     176      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
     177        a+=flow.get(i);
     178      }
     179      return a;
     180    }
    199181  };
    200182
  • src/work/list_graph.hh

    r67 r69  
    2727    class InEdgeIt;
    2828    class SymEdgeIt;
    29     template <typename ValueType> class NodeMap;
    30     template <typename ValueType> class EdgeMap;
     29    template <typename T> class NodeMap;
     30    template <typename T> class EdgeMap;
    3131   
    3232  private:
    3333   
    34     template <typename ValueType> friend class NodeMap;
    35     template <typename ValueType> friend class EdgeMap;
    36 
    37     template <typename ValueType>
     34    template <typename T> friend class NodeMap;
     35    template <typename T> friend class EdgeMap;
     36
     37    template <typename T>
    3838    class NodeMap {
    3939      const ListGraph& G;
    40       std::vector<ValueType> container;
    41     public:
    42       NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { }
    43       NodeMap(const ListGraph& _G, ValueType a) :
    44         G(_G), container(_G.node_id, a) { }
    45       void set(NodeIt nit, ValueType a) { container[G.id(nit)]=a; }
    46       ValueType get(NodeIt nit) const { return container[G.id(nit)]; }
    47     };
    48 
    49     template <typename ValueType>
     40      std::vector<T> container;
     41    public:
     42      typedef T ValueType;
     43      typedef NodeIt KeyType;
     44      NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { }
     45      NodeMap(const ListGraph& _G, T a) :
     46        G(_G), container(G.node_id, a) { }
     47      void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
     48      T get(NodeIt nit) const { return container[G.id(nit)]; }
     49      void resize() { container.resize(G.node_id); }
     50      void resize(T a) { container.resize(G.node_id, a); }
     51    };
     52
     53    template <typename T>
    5054    class EdgeMap {
    5155      const ListGraph& G;
    52       std::vector<ValueType> container;
    53     public:
    54       EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { }
    55       EdgeMap(const ListGraph& _G, ValueType a) :
    56         G(_G), container(_G.edge_id, a) { }
    57       void set(EdgeIt eit, ValueType a) { container[G.id(eit)]=a; }
    58       ValueType get(EdgeIt eit) const { return container[G.id(eit)]; }
     56      std::vector<T> container;
     57    public:
     58      typedef T ValueType;
     59      typedef EdgeIt KeyType;
     60      EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { }
     61      EdgeMap(const ListGraph& _G, T a) :
     62        G(_G), container(G.edge_id, a) { }
     63      void set(EdgeIt eit, T a) { container[G.id(eit)]=a; }
     64      T get(EdgeIt eit) const { return container[G.id(eit)]; }
     65      void resize() { container.resize(G.edge_id); }
     66      void resize(T a) { container.resize(G.edge_id, a); }
    5967    };
    6068
     
    302310    void erase(EdgeIt e) { _delete_edge(e.edge); }
    303311
     312    void clear() {
     313      while (first<EachNodeIt>().valid()) erase(first<EachNodeIt>());
     314    }
     315
    304316    void setTail(EdgeIt e, NodeIt tail) {
    305317      _set_tail(e.edge, tail.node);
  • src/work/marci_graph_demo.cc

    r60 r69  
    232232  }
    233233  std::cout<<std::endl;
     234  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    234235
    235236  return 0;
Note: See TracChangeset for help on using the changeset viewer.