COIN-OR::LEMON - Graph Library

Changeset 105:a3c73e9b9b2e in lemon-0.x


Ignore:
Timestamp:
02/20/04 22:45:07 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@140
Message:

marci -> hugo replacements
resize -> update replacements

Location:
src/work
Files:
23 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/gwrapper.h

    r103 r105  
    33#define GRAPH_WRAPPER_H
    44
    5 namespace marci {
     5namespace hugo {
    66
    77template<typename G>
  • src/work/alpar/smart_graph.h

    r104 r105  
     1// -*- mode:C++ -*-
     2
    13#ifndef SMART_GRAPH_H
    24#define SMART_GRAPH_H
     
    57#include <vector>
    68
    7 namespace marci {
     9namespace hugo {
    810
    911  class SmartGraph {
     
    3638    class InEdgeIt;
    3739   
    38 //      class NodeIt { int n; };
    39 //     class EachNodeIt : public NodeIt { };
    40 //     class EdgeIt { int n; };
    41 //     class EachEdgeIt : public EdgeIt {};
    42 //     class OutEdgeIt : public EdgeIt {};
    43 //     class InEdgeIt : public EdgeIt {};
     40    //      class NodeIt { int n; };
     41    //     class EachNodeIt : public NodeIt { };
     42    //     class EdgeIt { int n; };
     43    //     class EachEdgeIt : public EdgeIt {};
     44    //     class OutEdgeIt : public EdgeIt {};
     45    //     class InEdgeIt : public EdgeIt {};
    4446    //    class SymEdgeIt;
    45    
    46  template <typename T> class NodeMap;
     47    
     48    template <typename T> class NodeMap;
    4749    template <typename T> class EdgeMap;
    4850   
    49   private:
    50    
    51     template <typename T> friend class NodeMap;
    52     template <typename T> friend class EdgeMap;
     51  public:
     52
     53    /* default constructor */
     54
     55    SmartGraph() : nodes(), edges() { }
     56   
     57    ~SmartGraph() {}
     58
     59    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
     60    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
     61
     62    NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
     63    NodeIt head(EdgeIt e) const { return edges[e.n].head; }
     64
     65    NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
     66    NodeIt aNode(const InEdgeIt& e) const { return head(e); }
     67    //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
     68
     69    NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
     70    NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
     71    //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
     72
     73    EachNodeIt& getFirst(EachNodeIt& v) const {
     74      v=EachNodeIt(*this); return v; }
     75    EachEdgeIt& getFirst(EachEdgeIt& e) const {
     76      e=EachEdgeIt(*this); return e; }
     77    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const {
     78      e=OutEdgeIt(*this,v); return e; }
     79    InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const {
     80      e=InEdgeIt(*this,v); return e; }
     81
     82    template< typename It >
     83    It first() const {
     84      It e;
     85      getFirst(e);
     86      return e;
     87    }
     88
     89    template< typename It >
     90    It first(NodeIt v) const {
     91      It e;
     92      getFirst(e, v);
     93      return e;
     94    }
     95
     96    bool valid(EdgeIt e) const { return e.n!=INVALID; }
     97    bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
     98    bool valid(NodeIt n) const { return n.n<int(nodes.size()); }
     99   
     100    template <typename It> It next(It it) const
     101      //    { It tmp(it); return goNext(tmp); }
     102    { It tmp; tmp.n=it.n+1; return tmp; }
     103
     104    NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }
     105    OutEdgeIt& goNext(OutEdgeIt& it) const
     106    { it.n=edges[it.n].next_out; return it; }
     107    InEdgeIt& goNext(InEdgeIt& it) const
     108    { it.n=edges[it.n].next_in; return it; }
     109    EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }
     110
     111    int id(NodeIt v) const { return v.n; }
     112    int id(EdgeIt e) const { return e.n; }
     113
     114    NodeIt addNode() {
     115      NodeIt n; n.n=nodes.size();
     116      nodes.push_back(NodeT()); //FIXME: Hmmm...
     117      return n;
     118    }
     119    EdgeIt addEdge(NodeIt u, NodeIt v) {
     120      EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
     121      edges[e.n].tail=u.n; edges[e.n].head=v.n;
     122      edges[e.n].next_out=nodes[u.n].first_out;
     123      edges[e.n].next_in=nodes[v.n].first_in;
     124      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
     125      return e;
     126    }
     127
     128    void clear() {nodes.clear();edges.clear();}
     129
     130    class NodeIt {
     131      friend class SmartGraph;
     132      template <typename T> friend class NodeMap;
     133     
     134      friend class EdgeIt;
     135      friend class OutEdgeIt;
     136      friend class InEdgeIt;
     137      friend class SymEdgeIt;
     138
     139    protected:
     140      int n;
     141      friend int SmartGraph::id(NodeIt v) const;
     142    public:
     143      NodeIt() {}
     144      NodeIt(int nn) {n=nn;}
     145      bool operator==(const NodeIt i) const {return n==i.n;}
     146      bool operator!=(const NodeIt i) const {return n!=i.n;}
     147    };
     148   
     149    class EachNodeIt : public NodeIt {
     150      friend class SmartGraph;
     151    public:
     152      EachNodeIt(const SmartGraph& G) : NodeIt(0) { }
     153      EachNodeIt() : NodeIt() { }
     154    };
     155
     156    class EdgeIt {
     157      friend class SmartGraph;
     158      template <typename T> friend class EdgeMap;
     159     
     160      friend class NodeIt;
     161      friend class EachNodeIt;
     162    protected:
     163      int n;
     164      friend int SmartGraph::id(EdgeIt e) const;
     165    public:
     166      EdgeIt() { }
     167      EdgeIt(int nn) {n=nn;}
     168      bool operator==(const EdgeIt i) const {return n==i.n;}
     169      bool operator!=(const EdgeIt i) const {return n!=i.n;}
     170    };
     171   
     172    class EachEdgeIt : public EdgeIt {
     173      friend class SmartGraph;
     174    public:
     175      EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }
     176      EachEdgeIt() : EdgeIt() { }
     177    };
     178   
     179    class OutEdgeIt : public EdgeIt {
     180      friend class SmartGraph;
     181    public:
     182      OutEdgeIt() : EdgeIt() { }
     183      OutEdgeIt(const SmartGraph& G,const NodeIt v)
     184        : EdgeIt(G.nodes[v.n].first_out) {}
     185    };
     186   
     187    class InEdgeIt : public EdgeIt {
     188      friend class SmartGraph;
     189    public:
     190      InEdgeIt() : EdgeIt() { }
     191      InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
     192    };
     193
     194    // Map types
    53195
    54196    template <typename T>
     
    66208      T& operator[](NodeIt n) { return container[n.n]; }
    67209      const T& operator[](NodeIt n) const { return container[n.n]; }
    68       void resize() { container.resize(G.nodeNum()); }
    69       void resize(T a) { container.resize(G.nodeNum(), a); }
     210      void update() { container.resize(G.nodeNum()); }
     211      void update(T a) { container.resize(G.nodeNum(), a); }
    70212    };
    71213
     
    84226      T& operator[](EdgeIt e) { return container[e.n]; }
    85227      const T& operator[](EdgeIt e) const { return container[e.n]; }
    86       void resize() { container.resize(G.edgeNum()); }
    87       void resize(T a) { container.resize(G.edgeNum(), a); }
    88     };
    89 
    90   public:
    91 
    92     /* default constructor */
    93 
    94     SmartGraph() : nodes(), edges() { }
    95    
    96     ~SmartGraph() {}
    97 
    98     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
    99     int edgeNum() const { return edges.size(); }  //FIXME: What is this?
    100 
    101     NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
    102     NodeIt head(EdgeIt e) const { return edges[e.n].head; }
    103 
    104     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
    105     NodeIt aNode(const InEdgeIt& e) const { return head(e); }
    106     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
    107 
    108     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
    109     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
    110     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
    111 
    112     EachNodeIt& getFirst(EachNodeIt& v) const {
    113       v=EachNodeIt(*this); return v; }
    114     EachEdgeIt& getFirst(EachEdgeIt& e) const {
    115       e=EachEdgeIt(*this); return e; }
    116     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const {
    117       e=OutEdgeIt(*this,v); return e; }
    118     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const {
    119       e=InEdgeIt(*this,v); return e; }
    120 
    121     template< typename It >
    122     It first() const {
    123       It e;
    124       getFirst(e);
    125       return e;
    126     }
    127 
    128     template< typename It >
    129     It first(NodeIt v) const {
    130       It e;
    131       getFirst(e, v);
    132       return e;
    133     }
    134 
    135     bool valid(EdgeIt e) const { return e.n!=INVALID; }
    136     bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
    137     bool valid(NodeIt n) const { return n.n<int(nodes.size()); }
    138    
    139     template <typename It> It next(It it) const {
    140       It tmp(it); return goNext(it); }
    141 
    142     NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }
    143     OutEdgeIt& goNext(OutEdgeIt& it) const
    144     { it.n=edges[it.n].next_out; return it; }
    145     InEdgeIt& goNext(InEdgeIt& it) const
    146     { it.n=edges[it.n].next_in; return it; }
    147     EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }
    148 
    149     int id(NodeIt v) const { return v.n; }
    150     int id(EdgeIt e) const { return e.n; }
    151 
    152     NodeIt addNode() {
    153       NodeIt n; n.n=nodes.size();
    154       nodes.push_back(NodeT()); //FIXME: Hmmm...
    155       return n;
    156     }
    157     EdgeIt addEdge(NodeIt u, NodeIt v) {
    158       EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
    159       edges[e.n].tail=u.n; edges[e.n].head=v.n;
    160       edges[e.n].next_out=nodes[u.n].first_out;
    161       edges[e.n].next_in=nodes[v.n].first_in;
    162       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
    163       return e;
    164     }
    165 
    166     void clear() {nodes.clear();edges.clear();}
    167 
    168     class NodeIt {
    169       friend class SmartGraph;
    170       template <typename T> friend class NodeMap;
    171      
    172       friend class EdgeIt;
    173       friend class OutEdgeIt;
    174       friend class InEdgeIt;
    175       friend class SymEdgeIt;
    176 
    177     protected:
    178       int n;
    179       friend int SmartGraph::id(NodeIt v) const;
    180     public:
    181       NodeIt() {}
    182       NodeIt(int nn) {n=nn;}
    183       bool operator==(const NodeIt i) const {return n==i.n;}
    184       bool operator!=(const NodeIt i) const {return n!=i.n;}
    185     };
    186    
    187     class EachNodeIt : public NodeIt {
    188       friend class SmartGraph;
    189     public:
    190       EachNodeIt(const SmartGraph& G) : NodeIt(0) { }
    191       EachNodeIt() : NodeIt() { }
    192     };
    193 
    194     class EdgeIt {
    195       friend class SmartGraph;
    196       template <typename T> friend class EdgeMap;
    197      
    198       friend class NodeIt;
    199       friend class EachNodeIt;
    200     protected:
    201       int n;
    202       friend int SmartGraph::id(EdgeIt e) const;
    203     public:
    204       EdgeIt() { }
    205       EdgeIt(int nn) {n=nn;}
    206       bool operator==(const EdgeIt i) const {return n==i.n;}
    207       bool operator!=(const EdgeIt i) const {return n!=i.n;}
    208     };
    209    
    210     class EachEdgeIt : public EdgeIt {
    211       friend class SmartGraph;
    212     public:
    213       EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }
    214       EachEdgeIt() : EdgeIt() { }
    215     };
    216    
    217     class OutEdgeIt : public EdgeIt {
    218       friend class SmartGraph;
    219     public:
    220       OutEdgeIt() : EdgeIt() { }
    221       OutEdgeIt(const SmartGraph& G,const NodeIt v)
    222         : EdgeIt(G.nodes[v.n].first_out) {}
    223     };
    224    
    225     class InEdgeIt : public EdgeIt {
    226       friend class SmartGraph;
    227     public:
    228       InEdgeIt() : EdgeIt() { }
    229       InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
    230     };
     228      void update() { container.resize(G.edgeNum()); }
     229      void update(T a) { container.resize(G.edgeNum(), a); }
     230    };
     231
     232
     233
     234
    231235  };
    232 } //namespace marci
     236} //namespace hugo
    233237
    234238#endif //SMART_GRAPH_H
  • src/work/athos/pf_demo.cc

    r77 r105  
    88#include "preflow_push.hh"
    99
    10 using namespace marci;
     10using namespace hugo;
    1111
    1212
  • src/work/athos/preflow_push.hh

    r77 r105  
    1313using namespace std;
    1414
    15 namespace marci {
     15namespace hugo {
    1616
    1717  template <typename graph_type, typename T>
     
    435435
    436436
    437 }//namespace marci
     437}//namespace hugo
    438438
    439439#endif //PREFLOW_PUSH_HH
  • src/work/athos/reverse_bfs.hh

    r77 r105  
    9797  };
    9898
    99 } // namespace marci
     99} // namespace hugo
    100100
    101101#endif //REVERSE_BFS_HH
  • src/work/bfs_iterator.hh

    r99 r105  
    77#include <graph_wrapper.h>
    88
    9 namespace marci {
     9namespace hugo {
    1010
    1111  template <typename Graph>
     
    756756
    757757
    758 } // namespace marci
     758} // namespace hugo
    759759
    760760#endif //BFS_ITERATOR_HH
  • src/work/bin_heap_demo.cc

    r39 r105  
    44#include <map>
    55
    6 using namespace marci;
     6using namespace hugo;
    77using namespace std;
    88
  • src/work/jacint/dijkstra.hh

    r78 r105  
    5353
    5454namespace std {
    55   namespace marci {
     55  namespace hugo {
    5656
    5757
     
    186186
    187187
    188   } // namespace marci
     188  } // namespace hugo
    189189}
    190190#endif //DIJKSTRA_HH
  • src/work/jacint/flow_test.cc

    r78 r105  
    99//#include <dijkstra.h>
    1010
    11 using namespace marci;
     11using namespace hugo;
    1212
    1313
  • src/work/jacint/preflow_hl2.h

    r101 r105  
    4242#include <queue>
    4343
    44 namespace marci {
     44namespace hugo {
    4545
    4646  template <typename Graph, typename T,
     
    397397
    398398  };
    399 }//namespace marci
     399}//namespace hugo
    400400#endif
    401401
  • src/work/jacint/preflow_hl3.h

    r101 r105  
    4545#include <queue>
    4646
    47 namespace marci {
     47namespace hugo {
    4848
    4949  template <typename Graph, typename T,
     
    465465
    466466  };
    467 }//namespace marci
     467}//namespace hugo
    468468#endif
    469469
  • src/work/jacint/preflow_hl4.h

    r102 r105  
    4545#include <queue>
    4646
    47 namespace marci {
     47namespace hugo {
    4848
    4949  template <typename Graph, typename T,
     
    479479
    480480  };
    481 }//namespace marci
     481}//namespace hugo
    482482#endif
    483483
  • src/work/jacint/preflow_push_hl.h

    r101 r105  
    4444#include <queue>
    4545
    46 namespace marci {
     46namespace hugo {
    4747
    4848  template <typename Graph, typename T,
     
    391391
    392392  };
    393 }//namespace marci
     393}//namespace hugo
    394394#endif
    395395
  • src/work/jacint/preflow_push_hl.hh

    r47 r105  
    3333#include <reverse_bfs.hh>
    3434
    35 namespace marci {
     35namespace hugo {
    3636
    3737  template <typename graph_type, typename T>
     
    313313
    314314  };
    315 }//namespace marci
     315}//namespace hugo
    316316#endif
    317317
  • src/work/jacint/preflow_push_max_flow.h

    r97 r105  
    3434
    3535
    36 namespace marci {
     36namespace hugo {
    3737
    3838  template <typename Graph, typename T, 
     
    288288
    289289  };
    290 }//namespace marci
     290}//namespace hugo
    291291#endif
    292292
  • src/work/jacint/preflow_push_max_flow.hh

    r47 r105  
    3333
    3434
    35 namespace marci {
     35namespace hugo {
    3636
    3737  template <typename graph_type, typename T>
     
    307307
    308308  };
    309 }//namespace marci
     309}//namespace hugo
    310310#endif
    311311
  • src/work/jacint/reverse_bfs.h

    r78 r105  
    8383  };
    8484
    85 } // namespace marci
     85} // namespace hugo
    8686
    8787#endif //REVERSE_BFS_HH
  • src/work/jacint/reverse_bfs.hh

    r78 r105  
    8888  };
    8989
    90 } // namespace marci
     90} // namespace hugo
    9191
    9292#endif //REVERSE_BFS_HH
  • src/work/marci/dimacs.hh

    r69 r105  
    66#include <vector>
    77
    8 namespace marci {
     8namespace hugo {
    99
    1010  template<typename Graph, typename CapacityMap>
     
    5050        getline(is, str);
    5151        typename Graph::EdgeIt e=G.addEdge(nodes[i], nodes[j]);
    52         capacity.resize();
     52        capacity.update();
    5353        capacity.set(e, cap);
    5454        break;
     
    5757  }
    5858 
    59 } //namespace marci
     59} //namespace hugo
    6060
    6161#endif //DIMACS_HH
  • src/work/marci/edmonds_karp_demo.cc

    r100 r105  
    77#include <time_measure.h>
    88
    9 using namespace marci;
     9using namespace hugo;
    1010
    1111// Use a DIMACS max flow file as stdin.
  • src/work/marci/graph_wrapper.h

    r76 r105  
    33#define GRAPH_WRAPPER_H
    44
    5 namespace marci {
     5namespace hugo {
    66
    77  template<typename Graph>
     
    574574
    575575
    576 } //namespace marci
     576} //namespace hugo
    577577
    578578#endif //GRAPH_WRAPPER_H
  • src/work/marci/preflow_demo_athos.cc

    r82 r105  
    77#include <time_measure.h>
    88
    9 using namespace marci;
     9using namespace hugo;
    1010
    1111// Use a DIMACS max flow file as stdin.
  • src/work/marci/preflow_demo_jacint.cc

    r100 r105  
    88#include <time_measure.h>
    99
    10 using namespace marci;
     10using namespace hugo;
    1111
    1212// Use a DIMACS max flow file as stdin.
Note: See TracChangeset for help on using the changeset viewer.