COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 70:851ca9a60e90 in lemon-0.x for src/include


Ignore:
Timestamp:
02/10/04 14:29:15 (21 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@86
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/include/graph.h

    r8 r70  
    1919    typedef N NodeType;
    2020   
    21     class EdgePoint
     21    class EdgeIt
    2222    {
    2323    public:
    2424      NEGRO::EdgePoint e;
    25       bool isValid() { return e; }
    26     };
    27    
    28     class InEdgePoint : public EdgePoint {};
    29     class OutEdgePoint : public EdgePoint {};
    30     class BiEdgePoint : public EdgePoint {};
    31     class SymEdgePoint : public EdgePoint {};
    32    
    33     typedef int NodePoint;
     25      bool valid() { return e; }
     26    };
     27   
     28    class InEdgeIt : public EdgeIt {};
     29    class OutEdgeIt : public EdgeIt {};
     30    class BiEdgeIt : public EdgeIt {};
     31    class SymEdgeIt : public EdgeIt {};
     32   
     33    typedef int NodeIt;
     34   
     35    typedef NodeIt EachNodeIt;
    3436   
    3537    class NodeIterator;
    … …  
    5052    friend class BiEdgeIterator;
    5153    friend class SymEdgeIterator;
    52     friend class AllEdgeIterator;
     54    friend class EachEdgeIterator;
    5355   
    5456    class NodeIterator
    … …  
    6365      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
    6466     
    65       NodeIterator &GoNext() { n=G->NextNode(n); return *this;}
    66       NodeIterator Next() const { return NodeIterator(*this).GoNext();}
    67       NodeIterator &operator++() { return GoNext();}
     67      NodeIterator &goNext() { n=G->NextNode(n); return *this;}
     68      NodeIterator next() const { return NodeIterator(*this).goNext();}
     69      NodeIterator &operator++() { return goNext();}
    6870      NodeIterator operator++(int)
    69       {NodeIterator tmp(*this); GoNext(); return tmp;}
    70       bool isValid() { return n!=INVALID; }
     71      {NodeIterator tmp(*this); goNext(); return tmp;}
     72      bool valid() { return n!=INVALID; }
    7173     
    7274      N &operator*() const { return G->Data(n); }
    … …  
    7678      bool operator!=(const NodeIterator &i) const {return n!=i.n;}
    7779     
    78       int Index() const { return n; } //If the nodes are indexable
     80      int index() const { return n; } //If the nodes are indexable
    7981      friend class Graph;
    8082      friend class EdgeIterator;
    … …  
    8385      friend class BiEdgeIterator;
    8486      friend class SymEdgeIterator;
    85       friend class AllEdgeIterator;
     87      friend class EachEdgeIterator;
    8688      friend class FirstAnythingTypeNode;
    8789
    … …  
    9799      // Meg a From() es To() miatt!!!!!!!!!!
    98100     
    99       NEGRO::EdgePoint e;
     101      NEGRO::EdgeIt e;
    100102     
    101103    public:
    … …  
    105107      // Lehet, hogy ez a ketto nem kell!!!
    106108     
    107       NodeIterator From() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
    108       NodeIterator To() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
    109      
    110       bool isValid() {return e;}
     109      NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
     110      NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
     111      NodeIterator opposite(const NodeIterator &n) const
     112      {return n==tail()?head():tail();}
     113     
     114      bool valid() {return e;}
    111115      E &operator*() const { return G->Data(e); }
    112116      E *operator->() const { return &G->Data(e); }
    … …  
    120124      bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
    121125       
    122       int Index() const { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
     126      int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
    123127      //If the edges are indexable
    124128
    … …  
    128132      friend class BiEdgeIterator;
    129133      friend class SymEdgeIterator;
    130       friend class AllEdgeIterator;
     134      friend class EachEdgeIterator;
    131135    };
    132136   
    … …  
    134138    {
    135139    public:
    136       BiEdgeIterator &GoNextIn()  { e=e->NextIn(); return *this;}
    137       BiEdgeIterator &GoNextOut() { e=e->NextOut(); return *this;}
    138       BiEdgeIterator NextIn() const  {return BiEdgeIterator(*this).GoNextIn();}
    139       BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();}
     140      BiEdgeIterator &goNextIn()  { e=e->NextIn(); return *this;}
     141      BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}
     142      BiEdgeIterator nextIn() const  {return BiEdgeIterator(*this).goNextIn();}
     143      BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}
    140144     
    141145      operator InEdgeIterator ()
    … …  
    153157    public:
    154158      InEdgeIterator() {}
    155       InEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &n)
     159      InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
    156160      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
    157161
    … …  
    181185      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
    182186
    183       OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}
    184       OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}
    185       OutEdgeIterator &operator++() { return GoNext();}
     187      OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
     188      OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
     189      OutEdgeIterator &operator++() { return goNext();}
    186190      OutEdgeIterator operator++(int)
    187       {OutEdgeIterator tmp(*this); GoNext(); return tmp;}
    188      
    189       NodeIterator Anode() const {return From();}
    190       NodeIterator Bnode() const {return To();}
     191      {OutEdgeIterator tmp(*this); goNext(); return tmp;}
     192     
     193      NodeIterator aNode() const {return tail();}
     194      NodeIterator bNode() const {return head();}
    191195     
    192196      operator const InEdgeIterator ()
    … …  
    205209    public:
    206210      SymEdgeIterator() {}
    207       SymEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &nn)
    208       { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }
    209 
    210       SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}
    211       SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}
    212       SymEdgeIterator &operator++() { return GoNext();}
     211      SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
     212      { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }
     213
     214      SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
     215      SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
     216      SymEdgeIterator &operator++() { return goNext();}
    213217      SymEdgeIterator operator++(int)
    214       {SymEdgeIterator tmp(*this); GoNext(); return tmp;}
    215      
    216       NodeIterator Anode() const {return n;}
    217       NodeIterator Bnode() const {return n.n==From().n?To():From();}
     218      {SymEdgeIterator tmp(*this); goNext(); return tmp;}
     219     
     220      NodeIterator aNode() const {return n;}
     221      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
    218222     
    219223      operator const InEdgeIterator ()
    … …  
    227231    };
    228232   
    229     class AllEdgeIterator : public EdgeIterator
     233    class EachEdgeIterator : public EdgeIterator
    230234    {
    231235      NodeIterator n;  // Itt ketszer van a G
    232236     
    233237    public:
    234       AllEdgeIterator() {}
    235       AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)
     238      EachEdgeIterator() {}
     239      EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
    236240      {
    237         e=n.isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
     241        e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
    238242      } 
    239243
    240       AllEdgeIterator &GoNext()
     244      EachEdgeIterator &goNext()
    241245      {
    242246        e=e->NextOut();
    243         if(!e && (++n).isValid()) e=G->OldGraph<N,E>::FirstOut(n.n);
     247        if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
    244248        return *this;
    245249      }
    246       AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();}
    247       AllEdgeIterator &operator++() { return GoNext();}
    248       AllEdgeIterator operator++(int)
    249         {AllEdgeIterator tmp(*this); GoNext(); return tmp;}
    250      
    251      
    252       NodeIterator Anode() const {return n;}
    253       NodeIterator Bnode() const {return n.n==From().n?To():From();}
    254      
     250      EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
     251      EachEdgeIterator &operator++() { return goNext();}
     252      EachEdgeIterator operator++(int)
     253        {EachEdgeIterator tmp(*this); goNext(); return tmp;}
     254     
     255     
     256      NodeIterator aNode() const {return n;}
     257      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
     258     
     259      operator const EdgeIterator ()
     260      {EdgeIterator i; i.G=G;i.e=e;return i;}
    255261      operator const InEdgeIterator ()
    256262      {InEdgeIterator i; i.G=G;i.e=e;return i;}
    … …  
    270276    typedef SymEdgeIterator DeletingSymEdgeIterator;
    271277   
    272     const NodeIterator FirstNode()
     278    const NodeIterator firstNode()
    273279    {
    274280      NodeIterator i;
    … …  
    277283    }
    278284   
    279     void GetFirst(NodePoint &p)   { p=OldGraph<N,E>::FirstNode(); }
    280    
    281     void GetFirst(InEdgePoint &p,const NodePoint &n)
     285    void getFirst(NodeIt &p)   { p=OldGraph<N,E>::FirstNode(); }
     286   
     287    void getFirst(InEdgeIt &p,const NodeIt &n)
    282288    { p=OldGraph<N,E>::FirstIn(n); }
    283     void GetFirst(OutEdgePoint &p,const NodePoint &n)
     289    void getFirst(OutEdgeIt &p,const NodeIt &n)
    284290    { p=OldGraph<N,E>::FirstOut(n); }
    285     void GetFirst(SymEdgePoint &p,const NodePoint &n)
     291    void getFirst(SymEdgeIt &p,const NodeIt &n)
    286292    { p=OldGraph<N,E>::FirstEdge(n); }
    287     void GetFirst(EdgePoint &p) //Vegigmegy mindenen
    288     { p.e=NodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
    289 
    290     void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
    291    
    292     void GetFirst(InEdgeIterator &i,const NodeIterator &n)
     293    void getFirst(EdgeIt &p) //Vegigmegy mindenen
     294    { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
     295
     296    void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
     297   
     298    void getFirst(InEdgeIterator &i,const NodeIterator &n)
    293299    { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
    294     void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
     300    void getFirst(OutEdgeIterator &i,const NodeIterator &n)
    295301    { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
    296     void GetFirst(SymEdgeIterator &i,const NodeIterator &n)
    297     { i.G=this;i.e=OldGraph<N,E>::FirstSym(n.n); }
    298     void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen
     302    void getFirst(SymEdgeIterator &i,const NodeIterator &n)
     303    { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }
     304    void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen
    299305    {
    300306      i.G=this;
    301       GetFirst(i.n);
     307      getFirst(i.n);
    302308      i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
    303309    } 
    … …  
    306312   
    307313    //Vagy beginnode()?
    308     const DeletingEdgeIterator FirstOut(const NodeIterator &n)
     314    const DeletingEdgeIterator firstOut(const NodeIterator &n)
    309315    {
    310316      EdgeIterator i;
    … …  
    312318      return i;
    313319    }
    314     const DeletingEdgeIterator FirstIn(const NodeIterator &n)
     320    const DeletingEdgeIterator firstIn(const NodeIterator &n)
    315321    {
    316322      EdgeIterator i;
    … …  
    318324      return i;
    319325    }
    320     const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)
     326    const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
    321327    {
    322328      EdgeIterator i;
    … …  
    342348      {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
    343349 
    344       operator const InEdgePoint () const
    345       {InEdgePoint i; n.G->GetFirst(i,n);return i;}
    346       operator const OutEdgePoint () const
    347       {OutEdgePoint i; n.G->GetFirst(i,n);return i;}
    348       operator const SymEdgePoint () const
    349       {SymEdgePoint i; n.G->GetFirst(i,n);return i;}
     350      operator const InEdgeIt () const
     351      {InEdgeIt i; n.G->GetFirst(i,n);return i;}
     352      operator const OutEdgeIt () const
     353      {OutEdgeIt i; n.G->GetFirst(i,n);return i;}
     354      operator const SymEdgeIt () const
     355      {SymEdgeIt i; n.G->GetFirst(i,n);return i;}
    350356    };
    351357   
    … …  
    356362      FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
    357363
    358       operator const AllEdgeIterator () const
    359       {AllEdgeIterator i; G->GetFirst(i);return i;} 
    360       operator const EdgePoint () const
    361       {EdgePoint i; G->GetFirst(i);return i;}
     364      operator const EachEdgeIterator () const
     365      {EachEdgeIterator i; G->GetFirst(i);return i;} 
     366      operator const EdgeIt () const
     367      {EdgeIt i; G->GetFirst(i);return i;}
    362368      operator const NodeIterator () const
    363369      {NodeIterator i; G->GetFirst(i);return i;} 
    364       operator const NodePoint () const
    365       {NodePoint i; G->GetFirst(i);return i;}
     370      operator const NodeIt () const
     371      {NodeIt i; G->GetFirst(i);return i;}
    366372    } _FST;
    367373   
    368374    //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
    369     FirstAnythingTypeNode First(NodeIterator &i)
     375    FirstAnythingTypeNode first(NodeIterator &i)
    370376    {FirstAnythingTypeNode t(i); return t;}
    371     const FirstAnythingType &First() {return _FST;}
     377    const FirstAnythingType &first() {return _FST;}
    372378   
    373379    // LastNode() vagy endnode() stb. Nem kell?
    374380   
    375     DeletingNodeIterator AddNode()
     381    DeletingNodeIterator addNode()
    376382    {
    377383      DeletingNodeIterator i;
    … …  
    380386    }
    381387    DeletingEdgeIterator
    382     AddEdge(const NodeIterator from,const NodeIterator to)
     388    addEdge(const NodeIterator from,const NodeIterator to)
    383389    {
    384390      DeletingEdgeIterator i;
    … …  
    389395    void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
    390396   
    391     int NodeNum() { OldGraph<N,E>::NodeNum(); }
    392     void Clean() { OldGraph<N,E>::Clean(); }
     397    int nodeNum() { OldGraph<N,E>::NodeNum(); }
     398    void clean() { OldGraph<N,E>::Clean(); }
    393399
    394400    Graph() : _FST(this) {}
    … …  
    402408    public:
    403409      typedef T value_type;
    404       void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
    405       T Get(const NodeIterator i) const {return map[i.Index()];}
     410      void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
     411      T get(const NodeIterator i) const {return map[i.Index()];}
    406412      T operator[](NodeIterator i) {return map[i.Index()];}
    407413
    … …  
    409415
    410416      NodeMap() {}
    411       void SetG(Graph<N,E> &Gr) { G=&Gr; update();}     
     417      void setG(Graph<N,E> &Gr) { G=&Gr; update();}     
    412418    };
    413419
    … …  
    419425    public:
    420426      typedef T value_type;
    421       void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
    422       T &Get(const NodeIterator i) {return map[i.Index()];}
    423       T &operator[](NodeIterator i) {return map[i.Index()];}
     427      void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}
     428      T get(const EdgeIterator i) const {return map[i.Index()];}
     429      T &operator[](EdgeIterator i) {return map[i.Index()];}
    424430     
    425431      void update()
    … …  
    427433     
    428434      EdgeMap() {}
    429       void SetG(Graph<N,E> &Gr)
     435      void setG(Graph<N,E> &Gr)
    430436      { G=&Gr ;update();}
    431437     
    … …  
    433439   
    434440
    435     int MaxNode() { return OldGraph<N,E>::MaxNode();}
    436     int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
    437    
     441    int maxNode() { return OldGraph<N,E>::MaxNode();}
     442    int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
     443   
     444  };
     445 
     446  template <class G> //G is a graph-type
     447  class Path
     448  {
     449  public:
     450    typedef G Graph;
     451    typedef typename G::NodeIterator NodeIterator;
     452    typedef typename G::EdgeIterator EdgeIterator;
     453    typedef typename G::SymEdgeIterator SymEdgeIterator;
     454   
     455  private:
     456    std::vector<EdgeIterator> path;
     457    std::vector<bool> reversed;
     458
     459  public:
     460    void setLength(int n) { path.resize(n);reversed.resize(n);}
     461    int getLength() { return path.size(); }
     462    EdgeIterator &operator[](int n) {return path[n];}
     463    NodeIterator GetNode(int n) // What about path of length 1?
     464    {
     465      return n?
     466        reversed[n-1]?path[n-1].tail():path[n-1].head():
     467        reversed[0]?path[0].head():path[0].tail();
     468    }
     469    void setRevert(int n,bool r=true) {reversed[n]=r;}
     470    void setEdge(int n,SymEdgeIterator i)
     471    {
     472      path[n]=i;
     473      reversed[n] = i.head()==i.aNode();
     474    }
     475    void setEdge(int n,EdgeIterator i,bool r)
     476    {
     477      path[n]=i;
     478      reversed[n] = r;
     479    }
     480
     481    NodeIterator tail() { return getNode(0); }
     482    NodeIterator head() { return getNode(getLength()); }
    438483  };
    439484 
    … …  
    444489       mcmn   
    445490  */
    446  
    447 }
     491};
    448492
    449493#endif
Note: See TracChangeset for help on using the changeset viewer.