COIN-OR::LEMON - Graph Library

Changeset 642:e812963087f0 in lemon-0.x for src


Ignore:
Timestamp:
05/14/04 20:28:57 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@840
Message:

To avoid confusion my old ListGraph? is can be used under name SageGraph?, work/sage_graph.h contains it.

Location:
src/work
Files:
1 added
1 deleted
11 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/bfsit_vs_byhand.cc

    r640 r642  
    33#include <fstream>
    44
    5 #include <list_graph.h>
     5#include <sage_graph.h>
    66//#include <smart_graph.h>
    77#include <hugo/dimacs.h>
     
    1313
    1414int main() {
    15   typedef ListGraph Graph;
     15  typedef SageGraph Graph;
    1616  typedef Graph::Node Node;
    1717  typedef Graph::NodeIt NodeIt;
  • src/work/marci/bipartite_graph_wrapper_test.cc

    r640 r642  
    44#include <vector>
    55
    6 #include <list_graph.h>
     6#include <sage_graph.h>
    77//#include <smart_graph.h>
    88//#include <dimacs.h>
     
    1818
    1919int main() {
    20   typedef UndirListGraph Graph;
     20  typedef UndirSageGraph Graph;
    2121  typedef Graph::Node Node;
    2222  typedef Graph::NodeIt NodeIt;
  • src/work/marci/bipartite_matching_try.cc

    r640 r642  
    55#include <cstdlib>
    66
    7 #include <list_graph.h>
     7#include <sage_graph.h>
    88//#include <smart_graph.h>
    99//#include <dimacs.h>
     
    4141
    4242int main() {
    43   typedef UndirListGraph Graph;
     43  typedef UndirSageGraph Graph;
    4444  typedef Graph::Node Node;
    4545  typedef Graph::NodeIt NodeIt;
     
    167167    max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, max_flow);
    168168//  while (max_flow_test.augmentOnShortestPath()) { }
    169   typedef ListGraph MutableGraph;
     169  typedef SageGraph MutableGraph;
    170170//  while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
    171171  while (max_flow_test.augmentOnBlockingFlow2()) {
  • src/work/marci/bipartite_matching_try_3.cc

    r640 r642  
    44#include <vector>
    55
    6 #include <list_graph.h>
     6#include <sage_graph.h>
    77//#include <smart_graph.h>
    88//#include <dimacs.h>
     
    2020int main() {
    2121  //typedef UndirListGraph Graph;
    22   typedef BipartiteGraph<ListGraph> Graph;
     22  typedef BipartiteGraph<SageGraph> Graph;
    2323 
    2424  typedef Graph::Node Node;
  • src/work/marci/iterator_bfs_demo.cc

    r602 r642  
    44#include <string>
    55
    6 #include <list_graph.h>
     6#include <sage_graph.h>
    77//#include <smart_graph.h>
    88#include <bfs_dfs.h>
     
    3030{
    3131  //typedef SmartGraph Graph;
    32   typedef ListGraph Graph;
     32  typedef SageGraph Graph;
    3333
    3434  typedef Graph::Node Node;
  • src/work/marci/lg_vs_sg.cc

    r640 r642  
    44#include <string>
    55
    6 #include <list_graph.h>
     6#include <sage_graph.h>
     7#include <hugo/list_graph.h>
    78#include <hugo/smart_graph.h>
    89#include <hugo/dimacs.h>
     
    1920
    2021  std::string in=argv[1];
    21   typedef ListGraph MutableGraph;
     22  typedef SageGraph MutableGraph;
    2223
    2324  {
    24     typedef ListGraph Graph;
     25    typedef SageGraph Graph;
    2526    typedef Graph::Node Node;
    2627    typedef Graph::EdgeIt EdgeIt;
     
    3839      max_flow_test(g, s, t, cap, flow/*, true*/);
    3940
    40     std::cout << "ListGraph ..." << std::endl;
     41    std::cout << "SageGraph ..." << std::endl;
    4142
    4243    {
     
    9394  }
    9495
    95 
    9696  {
    9797    typedef SmartGraph Graph;
     
    113113    //  max_flow_test(g, s, t, cap, flow);
    114114
    115     std::cout << "SmatrGraph ..." << std::endl;
     115    std::cout << "SmartGraph ..." << std::endl;
    116116
    117117    {
     
    169169  }
    170170
     171  {
     172    typedef ListGraph Graph;
     173    typedef Graph::Node Node;
     174    typedef Graph::EdgeIt EdgeIt;
     175
     176    Graph g;
     177    Node s, t;
     178    Graph::EdgeMap<int> cap(g);
     179    std::ifstream ins(in.c_str());
     180    //readDimacsMaxFlow(ins, g, s, t, cap);
     181    readDimacs(ins, g, cap, s, t);
     182
     183    Timer ts;
     184    Graph::EdgeMap<int> flow(g); //0 flow
     185    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     186      max_flow_test(g, s, t, cap, flow/*, true*/);
     187    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     188    //  max_flow_test(g, s, t, cap, flow);
     189
     190    std::cout << "ListGraph ..." << std::endl;
     191
     192    {
     193      std::cout << "preflow ..." << std::endl;
     194      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     195      ts.reset();
     196      max_flow_test.run();
     197      std::cout << "elapsed time: " << ts << std::endl;
     198      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     199    }
     200
     201    {
     202      std::cout << "physical blocking flow augmentation ..." << std::endl;
     203      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     204      ts.reset();
     205      int i=0;
     206      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
     207      std::cout << "elapsed time: " << ts << std::endl;
     208      std::cout << "number of augmentation phases: " << i << std::endl;
     209      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     210    }
     211
     212//     {
     213//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     214//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     215//       ts.reset();
     216//       int i=0;
     217//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
     218//       std::cout << "elapsed time: " << ts << std::endl;
     219//       std::cout << "number of augmentation phases: " << i << std::endl;
     220//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     221//     }
     222
     223    {
     224      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
     225      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     226      ts.reset();
     227      int i=0;
     228      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
     229      std::cout << "elapsed time: " << ts << std::endl;
     230      std::cout << "number of augmentation phases: " << i << std::endl;
     231      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     232    }
     233
     234    {
     235      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
     236      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
     237      ts.reset();
     238      int i=0;
     239      while (max_flow_test.augmentOnShortestPath()) { ++i; }
     240      std::cout << "elapsed time: " << ts << std::endl;
     241      std::cout << "number of augmentation phases: " << i << std::endl;
     242      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     243    }
     244  }
     245
    171246
    172247
  • src/work/marci/macro_test.cc

    r640 r642  
    33#include <fstream>
    44
    5 #include <list_graph.h>
     5#include <sage_graph.h>
    66#include <hugo/for_each_macros.h>
    77
     
    1010int main()
    1111{
    12   typedef ListGraph Graph;
     12  typedef SageGraph Graph;
    1313  Graph g;
    1414  Graph::Node n1=g.addNode();
  • src/work/marci/max_bipartite_matching_demo.cc

    r198 r642  
    1010
    1111#include <leda_graph_wrapper.h>
    12 #include <list_graph.h>
     12#include <sage_graph.h>
    1313#include <dimacs.h>
    1414#include <time_measure.h>
  • src/work/marci/max_flow_1.cc

    r640 r642  
    33#include <fstream>
    44
    5 #include <list_graph.h>
     5#include <sage_graph.h>
    66#include <hugo/smart_graph.h>
    77#include <hugo/dimacs.h>
     
    2020int main(int, char **) {
    2121
    22   typedef ListGraph MutableGraph;
     22  typedef SageGraph MutableGraph;
    2323
    2424  typedef SmartGraph Graph;
  • src/work/marci/max_flow_demo.cc

    r640 r642  
    33#include <fstream>
    44
    5 #include <list_graph.h>
     5#include <sage_graph.h>
    66#include <hugo/smart_graph.h>
    77#include <hugo/dimacs.h>
     
    3535int main(int, char **) {
    3636
    37   typedef ListGraph MutableGraph;
     37  typedef SageGraph MutableGraph;
    3838
    3939  typedef SmartGraph Graph;
    40   //  typedef ListGraph Graph;
     40  //  typedef SageGraph Graph;
    4141  typedef Graph::Node Node;
    4242  typedef Graph::EdgeIt EdgeIt;
  • src/work/marci/top_sort_test.cc

    r640 r642  
    66#include <hugo/dimacs.h>
    77#include <bfs_dfs_misc.h>
    8 #include <list_graph.h>
     8#include <sage_graph.h>
    99#include <hugo/graph_wrapper.h>
    1010#include <hugo/maps.h>
     
    1717
    1818int main() {
    19   typedef ListGraph Graph;
     19  typedef SageGraph Graph;
    2020  Graph g;
    2121  readDimacs(std::cin, g);
Note: See TracChangeset for help on using the changeset viewer.