COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 105:a3c73e9b9b2e in lemon-0.x for src/work/alpar


Ignore:
Timestamp:
02/20/04 22:45:07 (21 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/alpar
Files:
2 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
Note: See TracChangeset for help on using the changeset viewer.