COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 334:63703ea7d02f in lemon-0.x for src/work/marci


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

brrr

Location:
src/work/marci
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/graph_concept.h

    r333 r334  
    110110    };
    111111   
    112     /// This iterator goes trough the outgoing edges of a node.
    113 
    114     /// This iterator goes trough the \e outgoing edges of a certain node
    115     /// of a graph.
    116     /// Its usage is quite simple, for example you can count the number
    117     /// of outgoing edges of a node \c n
    118     /// in graph \c G of type \c Graph as follows.
    119     /// \code
    120     ///int count=0;
    121     ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
    122     /// \endcode
    123    
    124     class OutEdgeIt : public Edge {
    125     public:
    126       /// @warning The default constructor sets the iterator
    127       /// to an undefined value.
    128       OutEdgeIt() {}
    129       /// Initialize the iterator to be invalid
    130       OutEdgeIt(Invalid) {}
    131       /// This constructor sets the iterator to first outgoing edge.
    132    
    133       /// This constructor set the iterator to the first outgoing edge of
    134       /// node
    135       ///@param n the node
    136       ///@param G the graph
    137       OutEdgeIt(const GraphSkeleturo & G, Node n) {}
    138     };
    139 
    140     /// This iterator goes trough the incoming edges of a node.
    141 
    142     /// This iterator goes trough the \e incoming edges of a certain node
    143     /// of a graph.
    144     /// Its usage is quite simple, for example you can count the number
    145     /// of outgoing edges of a node \c n
    146     /// in graph \c G of type \c Graph as follows.
    147     /// \code
    148     ///int count=0;
    149     ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
    150     /// \endcode
    151 
    152     class InEdgeIt : public Edge {
    153     public:
    154       /// @warning The default constructor sets the iterator
    155       /// to an undefined value.
    156       InEdgeIt() {}
    157       /// Initialize the iterator to be invalid
    158       InEdgeIt(Invalid) {}
    159       InEdgeIt(const GraphSkeleturo &, Node) {}   
    160     };
    161112    //  class SymEdgeIt : public Edge {};
    162113
    … …  
    365316  };
    366317
     318  /// An empty out-edge-iterable graph class.
     319 
     320  /// An empty graph class which provides a function to
     321  /// iterate on out-edges of any node.
     322  class OutEdgeIterableGraphSkeleturo : public GraphSkeleturo
     323  {
     324  public:
     325
     326    /// This iterator goes trough the outgoing edges of a node.
     327
     328    /// This iterator goes trough the \e outgoing edges of a certain node
     329    /// of a graph.
     330    /// Its usage is quite simple, for example you can count the number
     331    /// of outgoing edges of a node \c n
     332    /// in graph \c G of type \c Graph as follows.
     333    /// \code
     334    ///int count=0;
     335    ///for(Graph::OutEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;
     336    /// \endcode
     337    class OutEdgeIt : public Edge {
     338    public:
     339      /// @warning The default constructor sets the iterator
     340      /// to an undefined value.
     341      OutEdgeIt() {}
     342      /// Initialize the iterator to be invalid
     343      OutEdgeIt(Invalid) {}
     344      /// This constructor sets the iterator to first outgoing edge.
     345   
     346      /// This constructor set the iterator to the first outgoing edge of
     347      /// node
     348      ///@param n the node
     349      ///@param G the graph
     350      OutEdgeIt(const GraphSkeleturo & G, Node n) {}
     351    };
     352  };
     353
     354  /// An empty in-edge-iterable graph class.
     355 
     356  /// An empty graph class which provides a function to
     357  /// iterate on in-edges of any node.
     358  class InEdgeIterableGraphSkeleturo : public GraphSkeleturo
     359  {
     360  public:
     361
     362    /// This iterator goes trough the incoming edges of a node.
     363
     364    /// This iterator goes trough the \e incoming edges of a certain node
     365    /// of a graph.
     366    /// Its usage is quite simple, for example you can count the number
     367    /// of incoming edges of a node \c n
     368    /// in graph \c G of type \c Graph as follows.
     369    /// \code
     370    ///int count=0;
     371    ///for(Graph::InEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;
     372    /// \endcode
     373    class InEdgeIt : public Edge {
     374    public:
     375      /// @warning The default constructor sets the iterator
     376      /// to an undefined value.
     377      InEdgeIt() {}
     378      /// Initialize the iterator to be invalid
     379      InEdgeIt(Invalid) {}
     380      /// This constructor sets the iterator to first incomig edge.
     381   
     382      /// This constructor set the iterator to the first incomig edge of
     383      /// node
     384      ///@param n the node
     385      ///@param G the graph
     386      InEdgeIt(const GraphSkeleturo & G, Node n) {}
     387    };
     388  };
     389
     390
    367391  /// An empty node-eraseable graph class.
    368392 

  • src/work/marci/lg_vs_sg.cc

    r174 r334  
    88#include <dimacs.h>
    99#include <edmonds_karp.h>
     10#include <preflow.h>
    1011#include <time_measure.h>
    11 #include <graph_wrapper.h>
     12#include <for_each_macros.h>
    1213
    1314using namespace hugo;
    … …  
    3233    readDimacsMaxFlow(ins, G, s, t, cap);
    3334
     35    Timer ts;
     36    Graph::EdgeMap<int> flow(G); //0 flow
     37    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     38      pre_flow_test(G, s, t, cap, flow);
     39    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     40      max_flow_test(G, s, t, cap, flow);
     41
     42    std::cout << "ListGraph ..." << std::endl;
     43
    3444    {
    35       std::cout << "ListGraph..." << std::endl;
    36       std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
    37       Graph::EdgeMap<int> flow(G); //0 flow
     45      std::cout << "preflow ..." << std::endl;
     46      ts.reset();
     47      pre_flow_test.run();
     48      std::cout << "elapsed time: " << ts << std::endl;
     49      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     50    }
    3851
    39       Timer ts;
     52    {
     53      std::cout << "physical blocking flow augmentation ..." << std::endl;
     54      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    4055      ts.reset();
    41 
    42       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    4356      int i=0;
    4457      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    45 
    4658      std::cout << "elapsed time: " << ts << std::endl;
    4759      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    5062
    5163    {
    52       std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    53       Graph::EdgeMap<int> flow(G); //0 flow
    54 
    55       Timer ts;
     64      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     65      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    5666      ts.reset();
    57 
    58       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    5967      int i=0;
    60       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
    61 
     68      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    6269      std::cout << "elapsed time: " << ts << std::endl;
    6370      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    6673
    6774    {
    68       std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
    69       Graph::EdgeMap<int> flow(G); //0 flow
     75      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
     76      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     77      ts.reset();
     78      int i=0;
     79      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
     80      std::cout << "elapsed time: " << ts << std::endl;
     81      std::cout << "number of augmentation phases: " << i << std::endl;
     82      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     83    }
    7084
    71       Timer ts;
     85    {
     86      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
     87      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    7288      ts.reset();
    73 
    74       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    7589      int i=0;
    7690      while (max_flow_test.augmentOnShortestPath()) { ++i; }
    77 
    7891      std::cout << "elapsed time: " << ts << std::endl;
    7992      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    94107    readDimacsMaxFlow(ins, G, s, t, cap);
    95108
     109    Timer ts;
     110    Graph::EdgeMap<int> flow(G); //0 flow
     111    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     112      pre_flow_test(G, s, t, cap, flow);
     113    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     114      max_flow_test(G, s, t, cap, flow);
     115
     116    std::cout << "SmatrGraph ..." << std::endl;
     117
    96118    {
    97       std::cout << "SmartGraph..." << std::endl;
    98       std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
    99       Graph::EdgeMap<int> flow(G); //0 flow
     119      std::cout << "preflow ..." << std::endl;
     120      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     121      ts.reset();
     122      pre_flow_test.run();
     123      std::cout << "elapsed time: " << ts << std::endl;
     124      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     125    }
    100126
    101       Timer ts;
     127    {
     128      std::cout << "physical blocking flow augmentation ..." << std::endl;
     129      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    102130      ts.reset();
    103 
    104       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    105131      int i=0;
    106132      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    107 
    108133      std::cout << "elapsed time: " << ts << std::endl;
    109134      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    112137
    113138    {
    114       std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    115       Graph::EdgeMap<int> flow(G); //0 flow
    116 
    117       Timer ts;
     139      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     140      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    118141      ts.reset();
    119 
    120       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    121142      int i=0;
    122       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
    123 
     143      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    124144      std::cout << "elapsed time: " << ts << std::endl;
    125145      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    128148
    129149    {
    130       std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
    131       Graph::EdgeMap<int> flow(G); //0 flow
     150      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
     151      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     152      ts.reset();
     153      int i=0;
     154      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
     155      std::cout << "elapsed time: " << ts << std::endl;
     156      std::cout << "number of augmentation phases: " << i << std::endl;
     157      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     158    }
    132159
    133       Timer ts;
     160    {
     161      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
     162      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    134163      ts.reset();
    135 
    136       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    137164      int i=0;
    138165      while (max_flow_test.augmentOnShortestPath()) { ++i; }
    139 
    140166      std::cout << "elapsed time: " << ts << std::endl;
    141167      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    144170  }
    145171
     172
     173
     174
    146175  return 0;
    147176}

  • src/work/marci/makefile

    r330 r334  
    1212CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
    1313
    14 LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    15 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test
     14LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
     15BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg
    1616#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
    1717
Note: See TracChangeset for help on using the changeset viewer.