COIN-OR::LEMON - Graph Library

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

correction to 0.2

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.