COIN-OR::LEMON - Graph Library

Changeset 59:41c7f9c09a12 in lemon-0.x for src


Ignore:
Timestamp:
02/04/04 13:46:33 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@74
Message:

.

Location:
src/work
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.hh

    r43 r59  
    1 #ifndef MARCI_MAX_FLOW_HH
    2 #define MARCI_MAX_FLOW_HH
     1#ifndef EDMONDS_KARP_HH
     2#define EDMONDS_KARP_HH
    33
    44#include <algorithm>
     
    88namespace marci {
    99
    10   template<typename Graph, typename T>
     10  template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
    1111  class ResGraph {
    1212    typedef typename Graph::NodeIt NodeIt;
     
    1414    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
    1515    const Graph& G;
    16     typename Graph::EdgeMap<T>& flow;
    17     const typename Graph::EdgeMap<T>& capacity;
     16    FlowMap& flow;
     17    const CapacityMap& capacity;
    1818  public:
    19     ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow,
    20              const typename Graph::EdgeMap<T>& _capacity) :
     19    ResGraph(const Graph& _G, FlowMap& _flow,
     20             const CapacityMap& _capacity) :
    2121      G(_G), flow(_flow), capacity(_capacity) { }
    2222
     
    2727
    2828    class EdgeIt {
    29       friend class ResGraph<Graph, T>;
     29      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
    3030    protected:
    31       const ResGraph<Graph, T>* resG;
     31      const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
    3232      OldSymEdgeIt sym;
    3333    public:
     
    5252
    5353    class OutEdgeIt : public EdgeIt {
    54       friend class ResGraph<Graph, T>;
     54      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
    5555    public:
    5656      OutEdgeIt() { }
    5757      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
    5858    private:
    59       OutEdgeIt(const ResGraph<Graph, T>& _resG, const NodeIt v) {
     59      OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, const NodeIt v) {
    6060        resG=&_resG;
    6161        sym=resG->G.template first<OldSymEdgeIt>(v);
     
    9999    template <typename ValueType>
    100100    class NodeMap {
    101       //const ResGraph<Graph, T>& G;
    102101      typename Graph::NodeMap<ValueType> node_map;
    103102    public:
    104       NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { }
    105       NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { }
     103      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
     104      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { }
    106105      void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
    107106      ValueType get(const NodeIt nit) const { return node_map.get(nit); }
     
    110109  };
    111110
    112   template <typename Graph, typename T>
    113   struct max_flow_type {
     111  template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
     112  class MaxFlow {
    114113    typedef typename Graph::NodeIt NodeIt;
    115114    typedef typename Graph::EdgeIt EdgeIt;
     
    118117    typedef typename Graph::InEdgeIt InEdgeIt;
    119118    const Graph& G;
    120     NodeIt s;
    121     NodeIt t;
    122     typename Graph::EdgeMap<T> flow;
    123     const typename Graph::EdgeMap<T>& capacity;
    124 
    125     max_flow_type(const Graph& _G, NodeIt _s, NodeIt _t, const typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
     119    const NodeIt s;
     120    const NodeIt t;
     121    FlowMap& flow;
     122    const CapacityMap& capacity;
     123    typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
     124    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     125    typedef typename AugGraph::EdgeIt AugEdgeIt;
     126  public:
     127    MaxFlow(const Graph& _G, const NodeIt _s, const NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
     128    bool augment() {
     129      AugGraph res_graph(G, flow, capacity);
     130      bool _augment=false;
     131     
     132      typedef typename AugGraph::NodeMap<bool> ReachedMap;
     133      BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     134      res_bfs.pushAndSetReached(s);
     135       
     136      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
     137      //filled with invalid iterators
     138     
     139      typename AugGraph::NodeMap<int> free(res_graph);
     140       
     141      //searching for augmenting path
     142      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;
     154        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        //}
     160        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
     161          NodeIt v=res_graph.tail(e);
     162          NodeIt w=res_graph.head(e);
     163          //std::cout<<v<<"->"<<w<<std::endl;
     164          pred.set(w, e);
     165          if (pred.get(v).valid()) {
     166            free.set(w, std::min(free.get(v), e.free()));
     167          } else {
     168            free.set(w, e.free());
     169          }
     170          if (res_graph.head(e)==t) { _augment=true; break; }
     171        }
     172       
     173        ++res_bfs;
     174      } //end of searching augmenting path
     175
     176      if (_augment) {
     177        NodeIt n=t;
     178        T augment_value=free.get(t);
     179        //std::cout<<"augmentation: ";
     180        while (pred.get(n).valid()) {
     181          AugEdgeIt e=pred.get(n);
     182          e.augment(augment_value);
     183          //std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
     184          n=res_graph.tail(e);
     185        }
     186        //std::cout<<std::endl;
     187      }
     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;
     193
     194      return _augment;
     195    }
    126196    void run() {
    127       typedef ResGraph<Graph, T> AugGraph;
    128       AugGraph res_graph(G, flow, capacity);
    129 
    130       bool augment;
    131       do {
    132         augment=false;
    133 
    134         typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    135         typedef typename AugGraph::EdgeIt AugEdgeIt;
    136         typedef std::queue<AugOutEdgeIt> BfsQueue;
    137         BfsQueue bfs_queue;
    138         bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s));
    139 
    140         typedef typename AugGraph::NodeMap<bool> ReachedMap;
    141         ReachedMap reached(res_graph, false);
    142         reached.set(s, true);
    143        
    144         bfs_iterator1< AugGraph, ReachedMap >
    145         res_bfs(res_graph, bfs_queue, reached);
    146 
    147         typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap;
    148         PredMap pred(res_graph);
    149         //typename AugGraph::EdgeIt a; //invalid
    150         //a.makeInvalid();
    151         //pred.set(s, a);
    152 
    153         typedef typename AugGraph::NodeMap<int> FreeMap;
    154         FreeMap free(res_graph);
    155        
    156         //searching for augmenting path
    157         while ( res_bfs.valid() ) {
    158           //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
    159           if (res_bfs.newly_reached()) {
    160             AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
    161             NodeIt v=res_graph.tail(e);
    162             NodeIt w=res_graph.head(e);
    163             //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
    164             pred.set(w, e);
    165             if (pred.get(v).valid()) {
    166               free.set(w, std::min(free.get(v), e.free()));
    167               //std::cout <<" nem elso csucs: ";
    168               //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
    169             } else {
    170               free.set(w, e.free());
    171               //std::cout <<" elso csucs: ";
    172               //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
    173             }
    174             //std::cout<<std::endl;
    175           }
    176        
    177           if (res_graph.head(res_bfs)==t) break;
    178           ++res_bfs;
    179         } //end searching augmenting path
    180         if (reached.get(t)) {
    181           augment=true;
    182           NodeIt n=t;
    183           T augment_value=free.get(t);
    184           std::cout<<"augmentation: ";
    185           while (pred.get(n).valid()) {
    186             AugEdgeIt e=pred.get(n);
    187             e.augment(augment_value);
    188             std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
    189             n=res_graph.tail(e);
    190           }
    191           std::cout<<std::endl;
    192         }
    193 
    194         std::cout << "actual flow: "<< std::endl;
    195         for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
    196           std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    197         }
    198         std::cout<<std::endl;
    199 
    200       } while (augment);
     197      while (augment()) { }
    201198    }
    202199  };
     
    204201} // namespace marci
    205202
    206 #endif //MARCI_MAX_FLOW_HH
     203#endif //EDMONDS_KARP_HH
  • src/work/iterator_bfs_dfs_demo.cc

    r45 r59  
    182182  }
    183183 
     184  {
     185    std::cout << "iterator bfs demo 2 ..." << std::endl;
     186    //ListGraph::NodeMap<bool> reached(G, false);
     187    //reached.set(s, true);
     188    //std::queue<ListGraph::OutEdgeIt> bfs_queue;
     189    //bfs_queue.push(G.first<OutEdgeIt>(s));
     190    BfsIterator2< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
     191    bfs.pushAndSetReached(s);
     192    while (!bfs.finished()) {
     193      if (OutEdgeIt(bfs).valid()) {
     194        std::cout << "OutEdgeIt: " << bfs;
     195        std::cout << " aNode: " << G.aNode(bfs);
     196        std::cout << " bNode: " << G.bNode(bfs) << " ";
     197      } else {
     198        std::cout << "OutEdgeIt: " << "invalid";
     199        std::cout << " aNode: " << G.aNode(bfs);
     200        std::cout << " bNode: " << "invalid" << " ";
     201      }
     202      if (bfs.isBNodeNewlyReached()) {
     203        std::cout << "bNodeIsNewlyReached ";
     204      } else {
     205        std::cout << "bNodeIsNotNewlyReached ";
     206      }
     207      if (bfs.isANodeExamined()) {
     208        std::cout << "aNodeIsExamined ";
     209      } else {
     210        std::cout << "aNodeIsNotExamined ";
     211      }
     212      std::cout<<std::endl;
     213      ++bfs;
     214    }
     215  }
     216 
     217
     218
    184219
    185220  {
  • src/work/list_graph.hh

    r46 r59  
    1 #ifndef MARCI_LIST_GRAPH_HH
    2 #define MARCI_LIST_GRAPH_HH
     1#ifndef LIST_GRAPH_HH
     2#define LIST_GRAPH_HH
    33
    44#include <iostream>
    55
    66namespace marci {
    7 
    8   template <typename It>
    9   int number_of(It _it) {
    10     int i=0;
    11     for( ; _it.valid(); ++_it) { ++i; }
    12     return i;
    13   }
    147
    158  template <typename It>
     
    2114
    2215  class ListGraph {
     16
    2317    class node_item;
    2418    class edge_item;
     19
    2520  public:
     21
    2622    class NodeIt;
    2723    class EachNodeIt;
     
    3127    class InEdgeIt;
    3228    class SymEdgeIt;
    33 
    34     template <typename T>
     29    template <typename ValueType> class NodeMap;
     30    template <typename ValueType> class EdgeMap;
     31   
     32  private:
     33   
     34    template <typename ValueType> friend class NodeMap;
     35    template <typename ValueType> friend class EdgeMap;
     36
     37    template <typename ValueType>
    3538    class NodeMap {
    36       //typedef typename Graph::NodeIt NodeIt;
    37       //typedef typename Graph::EachNodeIt EachNodeIt;
    3839      const ListGraph& G;
    39       std::vector<T> container;
    40     public:
    41       NodeMap(const ListGraph& _G) : G(_G) {
    42         int i=0;
    43         for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) ++i;
    44         container.resize(i);
    45       }
    46       NodeMap(const ListGraph& _G, const T a) : G(_G) {
    47         for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) {
    48           container.push_back(a);
    49         }
    50       }
    51       void set(const NodeIt nit, const T a) { container[G.id(nit)]=a; }
    52       T get(const NodeIt nit) const { return container[G.id(nit)]; }
    53     };
    54 
    55     template <typename T>
     40      std::vector<ValueType> container;
     41    public:
     42      NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { }
     43      NodeMap(const ListGraph& _G, const ValueType a) :
     44        G(_G), container(_G.node_id, a) { }
     45      void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; }
     46      ValueType get(const NodeIt nit) const { return container[G.id(nit)]; }
     47    };
     48
     49    template <typename ValueType>
    5650    class EdgeMap {
    57       //typedef typename Graph::EdgeIt EdgeIt;
    58       //typedef typename Graph::EachEdgeIt EachEdgeIt;
    5951      const ListGraph& G;
    60       std::vector<T> container;
    61     public:
    62       EdgeMap(const ListGraph& _G) : G(_G) {
    63         int i=0;
    64         for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) ++i;
    65         container.resize(i);
    66       }
    67       EdgeMap(const ListGraph& _G, const T a) : G(_G) {
    68         for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) {
    69           container.push_back(a);
    70         }
    71       }
    72       void set(const EdgeIt eit, const T a) { container[G.id(eit)]=a; }
    73       T get(const EdgeIt eit) const { return container[G.id(eit)]; }
    74     };
    75 
    76     //typedef template<typename T> NodePropertyVector<ListGraph, T> NodeMap;
    77     //template <typename T>
    78     //typedef NodePropertyVector<ListGraph, T> NodeMap;
    79     //template <typename T>
    80     //typedef typename NodePropertyVector<ListGraph, T> NodeMap;
    81     //template <typename T>
    82     //typedef NodePropertyVector<typename ListGraph, T> NodeMap;
    83     //template <typename T>
    84     //typedef typename NodePropertyVector<typename ListGraph, T> NodeMap;
    85     //template <typename T>
    86     //typedef template NodePropertyVector<ListGraph, T> NodeMap;
    87     //template <typename T>
    88     //typedef template typename NodePropertyVector<ListGraph, T> NodeMap;
    89     //template <typename T>
    90     //typedef template NodePropertyVector<typename ListGraph, T> NodeMap;
    91     //template <typename T>
    92     //typedef template typename NodePropertyVector<typename ListGraph, T> NodeMap;
    93     //template <typename T>
    94     //typedef EdgePropertyVector<ListGraph, T> EdgeMap;
    95 
    96   private:
     52      std::vector<ValueType> container;
     53    public:
     54      EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { }
     55      EdgeMap(const ListGraph& _G, const ValueType a) :
     56        G(_G), container(_G.edge_id, a) { }
     57      void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; }
     58      ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; }
     59    };
     60
    9761    int node_id;
    9862    int edge_id;
     
    11478      friend std::ostream& operator<<(std::ostream& os, const NodeIt& i);
    11579      friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
    116       ListGraph* G;
     80      //ListGraph* G;
    11781      int id;
    11882      edge_item* _first_out_edge;
     
    136100      friend class SymEdgeIt;
    137101      friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
    138       ListGraph* G;
     102      //ListGraph* G;
    139103      int id;
    140104      node_item* _tail;
     
    257221    /* functions to construct iterators from the graph, or from each other */
    258222
    259     EachNodeIt firstNode() const { return EachNodeIt(_first_node); }
    260     EachEdgeIt firstEdge() const {
    261       node_item* v=_first_node;
    262       edge_item* edge=v->_first_out_edge;
    263       while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
    264       return EachEdgeIt(v, edge);
    265     }
     223    //EachNodeIt firstNode() const { return EachNodeIt(*this); }
     224    //EachEdgeIt firstEdge() const { return EachEdgeIt(*this); }
    266225   
    267226    //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); }
    268     InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
    269     SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
     227    //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
     228    //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
    270229    NodeIt tail(const EdgeIt e) const { return e.tailNode(); }
    271230    NodeIt head(const EdgeIt e) const { return e.headNode(); }
     
    288247    /* for experimental purpose */
    289248
    290     void getFirst(EachNodeIt& v) const { v=EachNodeIt(_first_node); }
    291     void getFirst(EachEdgeIt& e) const { e=firstEdge(); }
     249    void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
     250    void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
    292251    void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); }
    293252    void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); }
     
    387346    class EachNodeIt : public NodeIt {
    388347      friend class ListGraph;
     348    protected:
     349      EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
    389350    public:
    390351      EachNodeIt() : NodeIt() { }
    391352      EachNodeIt(node_item* v) : NodeIt(v) { }
    392       EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
    393353      EachNodeIt& operator++() { node=node->_next_node; return *this; }
    394354    };
     
    423383    class EachEdgeIt : public EdgeIt {
    424384      friend class ListGraph;
    425       node_item* v;
    426     public:
    427       EachEdgeIt() : EdgeIt(), v(0) { }
    428       EachEdgeIt(node_item* _v, edge_item* _e) : EdgeIt(_e), v(_v) { }
     385    protected:
    429386      EachEdgeIt(const ListGraph& G) {
    430         v=G._first_node;
    431         edge=v->_first_out_edge;
     387        node_item* v=G._first_node;
     388        if (v) edge=v->_first_out_edge; else edge=0;
    432389        while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
    433390      }
     391    public:
     392      EachEdgeIt() : EdgeIt() { }
     393      EachEdgeIt(edge_item* _e) : EdgeIt(_e) { }
    434394      EachEdgeIt& operator++() {
     395        node_item* v=edge->_tail;
    435396        edge=edge->_next_out;
    436397        while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
     
    442403      friend class ListGraph;
    443404      node_item* v;
     405    protected:
     406      OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
    444407    public:
    445408      OutEdgeIt() : EdgeIt(), v(0) { }
    446     protected:
    447       OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
    448     public:
    449409      OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
    450410      OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
     
    458418      friend class ListGraph;
    459419      node_item* v;
     420    protected:
     421      InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; }
    460422    public:
    461423      InEdgeIt() : EdgeIt(), v(0) { }
    462     protected:
    463       InEdgeIt(const NodeIt& _v) : v(_v.node) {
    464         edge=v->_first_in_edge;
    465       }
    466     public:
    467424      InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
    468425      InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
     
    477434      bool out_or_in; //1 iff out, 0 iff in
    478435      node_item* v;
    479     public:
    480       SymEdgeIt() : EdgeIt(), v(0) { }
    481436    protected:
    482437      SymEdgeIt(const NodeIt& _v) : v(_v.node) {
     
    486441      }
    487442    public:
     443      SymEdgeIt() : EdgeIt(), v(0) { }
    488444      SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) {
    489445        out_or_in=1;
     
    550506} //namespace marci
    551507
    552 #endif //MARCI_LIST_GRAPH_HH
     508#endif //LIST_GRAPH_HH
Note: See TracChangeset for help on using the changeset viewer.