COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 510:72143568cadc in lemon-0.x


Ignore:
Timestamp:
05/03/04 12:04:27 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@670
Message:

matching, flows

Location:
src/work
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed

  • src/work/jacint/max_flow.h

    r488 r510  
    8989    //typename Graph::template NodeMap<int> level;   
    9090    typename Graph::template NodeMap<Num> excess;
     91//   protected:
     92//     MaxFlow() { }
     93//     void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
     94//           FlowMap& _flow)
     95//       {
     96//      g=&_G;
     97//      s=_s;
     98//      t=_t;
     99//      capacity=&_capacity;
     100//      flow=&_flow;
     101//      n=_G.nodeNum;
     102//      level.set (_G); //kellene vmi ilyesmi fv
     103//      excess(_G,0); //itt is
     104//       }
    91105
    92106  public:

  • src/work/marci/bipartite_graph_wrapper.h

    r502 r510  
    311311//invalid, 3, invalid)
    312312    template <typename T> class NodeMap;
    313     template <typename T, typename Parent> class EdgeMap;
     313    template <typename T> class EdgeMap;
    314314
    315315//    template <typename T> friend class NodeMap;
    … …  
    386386      friend class GraphWrapper<Graph>;
    387387      friend class stGraphWrapper<Graph>;
    388       template <typename T, typename Parent> friend class EdgeMap;
     388      template <typename T> friend class EdgeMap;
    389389      int spec;
    390390      typename Graph::Node n;
    … …  
    413413      friend std::ostream& operator<< (std::ostream& os, const Edge& i);
    414414      int getSpec() const { return spec; }
     415      typename Graph::Node getNode() const { return n; }
    415416    };
    416417
    … …  
    703704    template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
    704705      typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
     706    protected:
    705707      T s_value, t_value;
    706708    public:
    … …  
    715717        case 0:
    716718          return Parent::operator[](n);
    717           break;
    718719        case 1:
    719720          return s_value;
    720           break;
    721721        case 2:
    722722        default:
    723723          return t_value;
    724           break;
    725724        }
    726725      }
    … …  
    741740    };
    742741
    743     template<typename T,
    744              typename Parent=
    745              typename GraphWrapper<Graph>::template EdgeMap<T> >
    746     class EdgeMap : public Parent {
    747       //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
     742    /// This class is to wrap a node-map of \c Graph and two variables
     743    /// storing values for \c S_NODE and \c T_NODE to a node-map of
     744    /// stGraphWrapper<Graph>.
     745    template<typename NM> class NodeMapWrapper {
     746    public:
     747      typedef Node KeyType;
     748      typedef typename NM::ValueType ValueType;
     749    protected:
     750      NM* nm;
     751      ValueType* s_value, t_value;
     752    public:
     753      NodeMapWrapper(NM& _nm, ValueType& _s_value, ValueType& _t_value) :
     754        nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }
     755      ValueType operator[](const Node& n) const {
     756        switch (n.getSpec()) {
     757        case 0:
     758          return (*nm)[n];
     759        case 1:
     760          return *s_value;
     761        case 2:
     762        default:
     763          return *t_value;
     764        }
     765      }
     766      void set(const Node& n, ValueType t) {
     767        switch (n.getSpec()) {
     768        case 0:
     769          nm->set(n, t);
     770          break;
     771        case 1:
     772          *s_value=t;
     773          break;
     774        case 2:
     775        default:
     776          *t_value=t;
     777          break;
     778        }
     779      }
     780    };
     781
     782    template<typename T>
     783    class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
     784      typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
     785    protected:
    748786      typename GraphWrapper<Graph>::template NodeMap<T> node_value;
    749787    public:
    … …  
    756794        case 0:
    757795          return Parent::operator[](e);
    758           break;
    759796        case 1:
    760797          return node_value[e.n];
    761           break;
    762798        case 2:
    763799        default:
    764800          return node_value[e.n];
    765           break;
    766801        }
    767802      }
    … …  
    782817    };
    783818
    784 //     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
    785 //       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
    786 //       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
    787 //     public:
    788 //       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
    789 //                                               node_value(_G) { }
    790 //       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
    791 //                                                    node_value(_G, a) { }
    792 //       T operator[](const Edge& e) const {
    793 //      switch (e.spec) {
    794 //      case 0:
    795 //        return Parent::operator[](e);
    796 //        break;
    797 //      case 1:
    798 //        return node_value[e.n];
    799 //        break;
    800 //      case 2:
    801 //      default:
    802 //        return node_value[e.n];
    803 //        break;
    804 //      }
    805 //       }
    806 //       void set(const Edge& e, T t) {
    807 //      switch (e.spec) {
    808 //      case 0:
    809 //        GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
    810 //        break;
    811 //      case 1:
    812 //        node_value.set(e.n, t);
    813 //        break;
    814 //      case 2:
    815 //      default:
    816 //        node_value.set(e.n, t);
    817 //        break;
    818 //      }
    819 //       }
    820 //     };
     819    /// This class is to wrap an edge-map and a node-map of \c Graph
     820    /// to an edge-map of stGraphWrapper<Graph>.
     821    template<typename EM, typename NM>
     822    class EdgeMapWrapper {
     823    public:
     824      typedef Edge KeyType;
     825      typedef typename EM::ValueType ValueType;
     826    protected:
     827      EM* em;
     828      NM* nm;
     829    public:
     830      EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }
     831      ValueType operator[](const Edge& e) const {
     832        switch (e.getSpec()) {
     833        case 0:
     834          return (*em)[e];
     835        case 1:
     836          return (*nm)[e.getNode()];
     837        case 2:
     838        default:
     839          return (*nm)[e.getNode()];
     840        }
     841      }
     842      void set(const Edge& e, ValueType t) {
     843        switch (e.getSpec()) {
     844        case 0:
     845          em->set(e, t);
     846          break;
     847        case 1:
     848          nm->set(e.getNode(), t);
     849          break;
     850        case 2:
     851        default:
     852          nm->set(e.getNode(), t);
     853          break;
     854        }
     855      }
     856    };
     857
    821858
    822859//  template<typename G>
    … …  
    841878
    842879
    843 #endif //HUGO_GRAPH_WRAPPER_H
    844 
     880#endif //HUGO_BIPARTITE_GRAPH_WRAPPER_H
     881

  • src/work/marci/bipartite_matching_try_2.cc

    r501 r510  
    7373  }
    7474
    75   std::cout << "Edges of the bipartite graph:" << std::endl;
    76   FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
    77   std::cout << std::endl;
     75//   std::cout << "Edges of the bipartite graph:" << std::endl;
     76//   FOR_EACH_LOC(EdgeIt, e, g) std::cout << e << " ";
     77//   std::cout << std::endl;
    7878
    79   std::cout << "Nodes:" << std::endl;
    80   FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
    81   std::cout << std::endl;
    82   std::cout << "Nodes in T:" << std::endl;
    83   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
    84   std::cout << std::endl;
    85   std::cout << "Nodes in S:" << std::endl;
    86   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
    87   std::cout << std::endl;
     79//   std::cout << "Nodes:" << std::endl;
     80//   FOR_EACH_LOC(Graph::NodeIt, v, g) std::cout << v << " ";
     81//   std::cout << std::endl;
     82//   std::cout << "Nodes in T:" << std::endl;
     83//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
     84//   std::cout << std::endl;
     85//   std::cout << "Nodes in S:" << std::endl;
     86//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
     87//   std::cout << std::endl;
    8888
    89   std::cout << "Erasing the first node..." << std::endl;
    90   NodeIt n;
    91   g.first(n);
    92   g.erase(n);
    93   std::cout << "Nodes of the bipartite graph:" << std::endl;
    94   FOR_EACH_GLOB(n, g) std::cout << n << " ";
    95   std::cout << std::endl;
     89//   std::cout << "Erasing the first node..." << std::endl;
     90//   NodeIt n;
     91//   g.first(n);
     92//   g.erase(n);
     93//   std::cout << "Nodes of the bipartite graph:" << std::endl;
     94//   FOR_EACH_GLOB(n, g) std::cout << n << " ";
     95//   std::cout << std::endl;
    9696
    97   std::cout << "Nodes in T:" << std::endl;
    98   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
    99   std::cout << std::endl;
    100   std::cout << "Nodes in S:" << std::endl;
    101   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
    102   std::cout << std::endl;
     97//   std::cout << "Nodes in T:" << std::endl;
     98//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::T_CLASS) std::cout << v << " ";
     99//   std::cout << std::endl;
     100//   std::cout << "Nodes in S:" << std::endl;
     101//   FOR_EACH_INC_LOC(Graph::ClassNodeIt, v, g, Graph::S_CLASS) std::cout << v << " ";
     102//   std::cout << std::endl;
    103103
    104104  typedef stGraphWrapper<Graph> stGW;
    … …  
    120120  std::cout << "max flow value: " << max_flow_test.flowValue() << std::endl;
    121121  std::cout << "elapsed time: " << ts << std::endl;
    122   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
    123     if (flow[e]) std::cout << e << std::endl;
    124   }
    125   std::cout << std::endl;
     122//   FOR_EACH_LOC(stGW::EdgeIt, e, stgw) {
     123//     if (flow[e]) std::cout << e << std::endl;
     124//   }
     125//   std::cout << std::endl;
    126126
    127127  return 0;

  • src/work/marci/makefile

    r498 r510  
    55
    66LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    7 BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_2
     7BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_2 bipartite_matching_try_3
    88#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
    99
Note: See TracChangeset for help on using the changeset viewer.