COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 902:309d81806228 in lemon-0.x for src/work


Ignore:
Timestamp:
09/22/04 14:25:50 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1210
Message:

correction to 0.2

Location:
src/work/marci
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/bipartite_graph_wrapper.h

    r768 r902  
    7272    class InEdgeIt;
    7373    friend class InEdgeIt;
    74     class ClassNodeIt {
     74    class ClassNodeIt : public Node {
    7575      friend class BipartiteGraphWrapper<Graph>;
    7676    protected:
    77       Node n;
     77      const BipartiteGraphWrapper<Graph>* gw;
    7878    public:
    7979      ClassNodeIt() { }
    80       ClassNodeIt(const Invalid& i) : n(i) { }
    81       ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
    82         _G.s_false_t_true_map->first(n, _class);
     80      ClassNodeIt(Invalid i) : Node(i) { }
     81      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, bool _class) :
     82        Node(), gw(&_gw) {
     83        _gw.s_false_t_true_map->first(*this, _class);
    8384      }
    8485      //FIXME needed in new concept, important here
    85       ClassNodeIt(const Node& _n) : n(_n) { }
    86       operator Node() const { return n; }
     86      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, const Node& n) :
     87        Node(n), gw(&_gw) { }
     88      ClassNodeIt& operator++() {
     89        gw->s_false_t_true_map->next(*this);
     90        return *this;
     91      }
    8792    };
    8893//     class SNodeIt {
    … …  
    106111//       operator Node() const { return n; }
    107112//     };
    108     class OutEdgeIt {
    109       friend class BipartiteGraphWrapper<Graph>;
    110     protected:
    111       typename Graph::OutEdgeIt e;
    112     public:
    113       OutEdgeIt() { }
    114       OutEdgeIt(const Invalid& i) : e(i) { }
    115       OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
    116         if (!(*(_G.s_false_t_true_map))[_n])
    117           e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
    118         else
    119           e=INVALID;
    120       }
    121       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    122     };
    123     class InEdgeIt {
    124       friend class BipartiteGraphWrapper<Graph>;
    125     protected:
    126       typename Graph::InEdgeIt e;
    127     public:
    128       InEdgeIt() { }
    129       InEdgeIt(const Invalid& i) : e(i) { }
    130       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
    131         if ((*(_G.s_false_t_true_map))[_n])
    132           e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
    133         else
    134           e=INVALID;
    135       }
    136       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    137     };
     113//     class OutEdgeIt {
     114//       friend class BipartiteGraphWrapper<Graph>;
     115//     protected:
     116//       typename Graph::OutEdgeIt e;
     117//     public:
     118//       OutEdgeIt() { }
     119//       OutEdgeIt(const Invalid& i) : e(i) { }
     120//       OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
     121//      if (!(*(_G.s_false_t_true_map))[_n])
     122//        e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
     123//      else
     124//        e=INVALID;
     125//       }
     126//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
     127//     };
     128//     class InEdgeIt {
     129//       friend class BipartiteGraphWrapper<Graph>;
     130//     protected:
     131//       typename Graph::InEdgeIt e;
     132//     public:
     133//       InEdgeIt() { }
     134//       InEdgeIt(const Invalid& i) : e(i) { }
     135//       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
     136//      if ((*(_G.s_false_t_true_map))[_n])
     137//        e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
     138//      else
     139//        e=INVALID;
     140//       }
     141//       operator Edge() const { return Edge(typename Graph::Edge(e)); }
     142//     };
    138143
    139144    using GraphWrapper<Graph>::first;
    140145    ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
    141       n=ClassNodeIt(*this, _class) ; return n; }
     146      n=ClassNodeIt(*this, _class); return n;
     147    }
    142148//    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
    143149//    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
    144     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    145       i=OutEdgeIt(*this, p); return i;
    146     }
    147     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    148       i=InEdgeIt(*this, p); return i;
    149     }
    150 
    151     using GraphWrapper<Graph>::next;
    152     ClassNodeIt& next(ClassNodeIt& n) const {
    153       this->s_false_t_true_map->next(n.n); return n;
    154     }
     150//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     151//       i=OutEdgeIt(*this, p); return i;
     152//     }
     153//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     154//       i=InEdgeIt(*this, p); return i;
     155//     }
     156
     157//     using GraphWrapper<Graph>::next;
     158//     ClassNodeIt& next(ClassNodeIt& n) const {
     159//       this->s_false_t_true_map->next(n.n); return n;
     160//     }
    155161//     SNodeIt& next(SNodeIt& n) const {
    156162//       this->s_false_t_true_map->next(n); return n;
    … …  
    159165//       this->s_false_t_true_map->next(n); return n;
    160166//     }
    161     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    162     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    163 
    164     Node tail(const Edge& e) {
    165       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
    166         return Node(this->graph->tail(e));
    167       else
    168         return Node(this->graph->head(e));     
    169     }
    170     Node head(const Edge& e) {
    171       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
    172         return Node(this->graph->head(e));
    173       else
    174         return Node(this->graph->tail(e));     
    175     }
    176 
    177     Node aNode(const OutEdgeIt& e) const {
    178       return Node(this->graph->aNode(e.e));
    179     }
    180     Node aNode(const InEdgeIt& e) const {
    181       return Node(this->graph->aNode(e.e));
    182     }
    183     Node bNode(const OutEdgeIt& e) const {
    184       return Node(this->graph->bNode(e.e));
    185     }
    186     Node bNode(const InEdgeIt& e) const {
    187       return Node(this->graph->bNode(e.e));
    188     }
     167//     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
     168//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
     169
     170//     Node tail(const Edge& e) {
     171//       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
     172//      return Node(this->graph->tail(e));
     173//       else
     174//      return Node(this->graph->head(e));     
     175//     }
     176//     Node head(const Edge& e) {
     177//       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
     178//      return Node(this->graph->head(e));
     179//       else
     180//      return Node(this->graph->tail(e));     
     181//     }
     182
     183//     Node aNode(const OutEdgeIt& e) const {
     184//       return Node(this->graph->aNode(e.e));
     185//     }
     186//     Node aNode(const InEdgeIt& e) const {
     187//       return Node(this->graph->aNode(e.e));
     188//     }
     189//     Node bNode(const OutEdgeIt& e) const {
     190//       return Node(this->graph->bNode(e.e));
     191//     }
     192//     Node bNode(const InEdgeIt& e) const {
     193//       return Node(this->graph->bNode(e.e));
     194//     }
    189195
    190196    /// Returns true iff \c n is in S.

  • src/work/marci/bipartite_graph_wrapper_test.cc

    r768 r902  
    44#include <vector>
    55
    6 #include <sage_graph.h>
    7 //#include <smart_graph.h>
     6//#include <sage_graph.h>
     7#include <hugo/smart_graph.h>
    88//#include <dimacs.h>
    99#include <hugo/time_measure.h>
    10 #include <for_each_macros.h>
     10//#include <for_each_macros.h>
    1111#include <bfs_dfs.h>
    1212#include <hugo/graph_wrapper.h>
    1313#include <bipartite_graph_wrapper.h>
    1414#include <hugo/maps.h>
    15 #include <hugo/max_flow.h>
     15#include <hugo/preflow.h>
    1616#include <augmenting_flow.h>
     17
     18using std::cout;
     19using std::endl;
    1720
    1821using namespace hugo;
    1922
    2023int main() {
    21   typedef UndirSageGraph Graph;
     24  //typedef UndirSageGraph Graph;
     25  typedef SmartGraph Graph;
    2226  typedef Graph::Node Node;
    2327  typedef Graph::NodeIt NodeIt;
    … …  
    5357
    5458  Graph::Node u;
    55   std::cout << "These nodes will be in S:\n";
     59  cout << "These nodes will be in S:" << endl;
    5660  //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen
    5761  //irni 1etlen FOR_EACH-csel.
    58   for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u))
    59     std::cout << u << " ";
    60   std::cout << "\n";
    61   std::cout << "These nodes will be in T:\n";
    62   for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u))
    63     std::cout << u << " ";
    64   std::cout << "\n";
     62  for (bipartite_map.first(u, false); u!=INVALID; bipartite_map.next(u))
     63    cout << g.id(u) << " ";
     64  cout << endl;
     65  cout << "These nodes will be in T:" << endl;
     66  for (bipartite_map.first(u, true); u!=INVALID; bipartite_map.next(u))
     67    cout << g.id(u) << " ";
     68  cout << endl;
    6569
    6670  typedef BipartiteGraphWrapper<Graph> BGW;
    6771  BGW bgw(g, bipartite_map);
    6872
    69   std::cout << "Nodes by NodeIt:\n";
    70   FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
    71     std::cout << n << " ";
    72   }
    73   std::cout << "\n";
    74   std::cout << "Nodes in S by ClassNodeIt:\n";
    75   FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
    76     std::cout << n << " ";
    77   }
    78   std::cout << "\n";
    79   std::cout << "Nodes in T by ClassNodeIt:\n";
    80   FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
    81     std::cout << n << " ";
    82   }
    83   std::cout << "\n";
    84   std::cout << "Edges of the bipartite graph:\n";
    85   FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
    86     std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
    87   }
     73  cout << "Nodes by NodeIt:" << endl;
     74  for (BGW::NodeIt n(bgw); n!=INVALID; ++n)
     75    cout << g.id(n) << " ";
     76  cout << endl;
     77
     78  cout << "Nodes in S by ClassNodeIt:" << endl;
     79  for (BGW::ClassNodeIt n(bgw, bgw.S_CLASS); n!=INVALID; ++n)
     80    cout << g.id(n) << " ";
     81  cout << endl;
     82
     83  cout << "Nodes in T by ClassNodeIt:" << endl;
     84  for (BGW::ClassNodeIt n(bgw, bgw.T_CLASS); n!=INVALID; ++n)
     85    cout << g.id(n) << " ";
     86  cout << endl;
     87
     88  cout << "Edges of the bipartite graph:" << endl;
     89  for (BGW::EdgeIt e(bgw); e!=INVALID; ++e)
     90    cout << g.id(bgw.tail(e)) << "->" << g.id(bgw.head(e)) << endl;
    8891
    8992  BGW::NodeMap<int> dbyj(bgw);
    9093  BGW::EdgeMap<int> dbyxcj(bgw);
    9194
    92   typedef stBipartiteGraphWrapper<BGW> stGW;
    93   stGW stgw(bgw);
    94   ConstMap<stGW::Edge, int> const1map(1);
    95   stGW::NodeMap<int> ize(stgw);
    96   stGW::EdgeMap<int> flow(stgw);
     95//   typedef stBipartiteGraphWrapper<BGW> stGW;
     96//   stGW stgw(bgw);
     97//   ConstMap<stGW::Edge, int> const1map(1);
     98//   stGW::NodeMap<int> ize(stgw);
     99//   stGW::EdgeMap<int> flow(stgw);
    97100
    98   BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
    99   Graph::NodeIt si;
    100   Graph::Node s;
    101   s=g.first(si);
    102   bfs.pushAndSetReached(BGW::Node(s));
    103   while (!bfs.finished()) { ++bfs; }
     101//   BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
     102//   Graph::NodeIt si;
     103//   Graph::Node s;
     104//   s=g.first(si);
     105//   bfs.pushAndSetReached(BGW::Node(s));
     106//   while (!bfs.finished()) { ++bfs; }
    104107
    105   FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
    106     std::cout << "out-edges of " << n << ":\n";
    107     FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
    108       std::cout << " " << e << "\n";
    109       std::cout << " aNode: " << stgw.aNode(e) << "\n";
    110       std::cout << " bNode: " << stgw.bNode(e) << "\n";     
    111     }
    112     std::cout << "in-edges of " << n << ":\n";
    113     FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
    114       std::cout << " " << e << "\n";
    115       std::cout << " aNode: " << stgw.aNode(e) << "\n";
    116       std::cout << " bNode: " << stgw.bNode(e) << "\n";     
    117     }
    118   }
    119   std::cout << "Edges of the stGraphWrapper:\n";
    120   FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
    121     std::cout << " " << n << "\n";
    122   }
     108//   FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
     109//     cout << "out-edges of " << n << ":" << endl;
     110//     FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) {
     111//       cout << " " << e << endl;
     112//       cout << " aNode: " << stgw.aNode(e) << endl;
     113//       cout << " bNode: " << stgw.bNode(e) << endl;     
     114//     }
     115//     cout << "in-edges of " << n << ":" << endl;
     116//     FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) {
     117//       cout << " " << e << endl;
     118//       cout << " aNode: " << stgw.aNode(e) << endl;
     119//       cout << " bNode: " << stgw.bNode(e) << endl;     
     120//     }
     121//   }
     122//   cout << "Edges of the stGraphWrapper:" << endl;
     123//   FOR_EACH_LOC(stGW::EdgeIt, n, stgw) {
     124//     cout << " " << n << endl;
     125//   }
    123126
    124   stGW::NodeMap<bool> b(stgw);
    125   FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
    126     std::cout << n << ": " << b[n] <<"\n";
    127   }
     127//   stGW::NodeMap<bool> b(stgw);
     128//   FOR_EACH_LOC(stGW::NodeIt, n, stgw) {
     129//     cout << n << ": " << b[n] << endl;
     130//   }
    128131
    129   std::cout << "Bfs from s: \n";
    130   BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
    131   bfs_stgw.pushAndSetReached(stgw.S_NODE);
    132   while (!bfs_stgw.finished()) {
    133     std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
    134     ++bfs_stgw;
    135   }
     132//   cout << "Bfs from s:" << endl;
     133//   BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
     134//   bfs_stgw.pushAndSetReached(stgw.S_NODE);
     135//   while (!bfs_stgw.finished()) {
     136//     cout << " " << stGW::OutEdgeIt(bfs_stgw) << endl;
     137//     ++bfs_stgw;
     138//   }
    136139 
    137   AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
    138     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
    139   while (max_flow_test.augmentOnShortestPath()) { }
     140//   AugmentingFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
     141//     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
     142//   while (max_flow_test.augmentOnShortestPath()) { }
    140143
    141   std::cout << max_flow_test.flowValue() << std::endl;
     144//   cout << max_flow_test.flowValue() << std::endl;
    142145
    143146  return 0;
Note: See TracChangeset for help on using the changeset viewer.