COIN-OR::LEMON - Graph Library

Changeset 70:851ca9a60e90 in lemon-0.x


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

.

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • doc/etikol.texi

    r29 r70  
    11\input texinfo   @c -*-texinfo-*-
    2 @comment $Id: etikol.texi,v 1.4 2004/01/21 08:39:33 alpar Exp $
     2@comment $Id: etikol.texi,v 1.5 2004/02/10 13:29:15 alpar Exp $
    33@comment %**start of header
    44@setfilename etikol.info
     
    3636@comment %**end of header
    3737
    38 @c @copying
    39 @c This manual is for GNU ETIL-OL Optimization Library
    40 @c (version @value{VERSION}, @value{UPDATED}).
     38@copying
     39This manual is for GNU ETIL-OL Optimization Library
     40(version @value{VERSION}, @value{UPDATED}).
    4141
    42 @c Copyright @copyright{} 2003 ETIK.
     42Copyright @copyright{} 2003 ETIK.
    4343
    44 @c @quotation
    45 @c Permission is granted to copy, distribute and/or modify this document
    46 @c under the terms of the GNU Free Documentation License, Version 1.1 or
    47 @c any later version published by the Free Software Foundation; with no
    48 @c Invariant Sections, with the Front-Cover Texts being ``A GNU Manual,''
    49 @c and with the Back-Cover Texts as in (a) below.  A copy of the
    50 @c license is included in the section entitled ``GNU Free Documentation
    51 @c License.''
     44@quotation
     45Permission is granted to copy, distribute and/or modify this document
     46under the terms of the GNU Free Documentation License, Version 1.1 or
     47any later version published by the Free Software Foundation; with no
     48Invariant Sections, with the Front-Cover Texts being ``A GNU Manual,''
     49and with the Back-Cover Texts as in (a) below.  A copy of the
     50license is included in the section entitled ``GNU Free Documentation
     51License.''
    5252
    53 @c (a) The FSF's Back-Cover Text is: ``You have freedom to copy and modify
    54 @c this GNU Manual, like GNU software.  Copies published by the Free
    55 @c Software Foundation raise funds for GNU development.''
    56 @c @end quotation
    57 @c @end copying
     53(a) The FSF's Back-Cover Text is: ``You have freedom to copy and modify
     54this GNU Manual, like GNU software.  Copies published by the Free
     55Software Foundation raise funds for GNU development.''
     56@end quotation
     57@end copying
    5858
    5959@dircategory Texinfo documentation system
  • doc/flf-graph.texi

    r26 r70  
    2828
    2929@anchor{Graph-NodeIterator}
    30 @deftp {Type} Graph::NodePoint
     30@deftp {Type} Graph::NodeIt
    3131@deftpx {Type} Graph::NodeIterator
    3232These types points a node uniquely. The difference between the
    33 @code{NodePoint} and the @code{NodeIterator} is that @code{NodePoint}
     33@code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt}
    3434requires the graph structure itself for most of the operations.
    3535For examples using iterators you can go through all nodes as follows.
     
    3838Graph G;
    3939int nodenum=0;
    40 for(Graph::NodeIterator n(G);n.Valid();++n) ++nodenum;
     40for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum;
    4141@end verbatim
    4242@end quotation
    43 Using @code{NodePoint} the last line looks like this.
     43Using @code{NodeIt} the last line looks like this.
    4444@quotation
    4545@verbatim
    46 for(MyGraph::NodePoint n(G);n.Valid();n=G.Next(n)) ++nodenum;
     46for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum;
    4747@end verbatim
    4848@end quotation
     
    5050@quotation
    5151@verbatim
    52 MyGraph::NodePoint n;
    53 for(G.GetFirst(n);G.Valid(n);G.GoNext(n)) ++nodenum;
     52MyGraph::NodeIt n;
     53for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum;
    5454@end verbatim
    5555@end quotation
    5656@end deftp
    5757
    58 @deftp {Type} Graph::EdgePoint
    59 @deftpx {Type} Graph::InEdgePoint
    60 @deftpx {Type} Graph::OutEdgePoint
    61 @deftpx {Type} Graph::BiEdgePoint
    62 @deftpx {Type} Graph::SymEdgePoint
     58@deftp {Type} Graph::EdgeIt
     59@deftpx {Type} Graph::InEdgeIt
     60@deftpx {Type} Graph::OutEdgeIt
     61@deftpx {Type} Graph::BiEdgeIt
     62@deftpx {Type} Graph::SymEdgeIt
    6363Each of these types points an edge uniquely. The difference between the
    64 @code{EdgePoint} and the
     64@code{EdgeIt} and the
    6565@c @mref{Graph-NodeIterator,@code{EdgeIterator}}
    6666@mref{Graph-NodeIterator , EdgeIterator}
    6767series is that
    68 @code{EdgePoint} requires the graph structure itself for most of the
     68@code{EdgeIt} requires the graph structure itself for most of the
    6969operations.
    7070@end deftp
     
    7676@deftpx {Type} Graph::BiEdgeIterator
    7777@deftpx {Type} Graph::SymEdgeIterator
    78 @deftpx {Type} Graph::AllEdgeIterator
     78@deftpx {Type} Graph::EachEdgeIterator
    7979Each of these types points an edge uniquely. The difference between the
    80 @code{EdgePoint} and the @code{EdgeIterator} series is that
    81 @code{EdgePoint} requires the graph structure itself for most of the
     80@code{EdgeIt} and the @code{EdgeIterator} series is that
     81@code{EdgeIt} requires the graph structure itself for most of the
    8282operations.
    8383
     
    108108@subsubsection Graph Maintenence Operations
    109109
    110 @deftypefun NodeIterator Graph::AddNode ()
     110@deftypefun NodeIterator Graph::addNode ()
    111111Adds a new node to the graph and returns a @code{NodeIterator} pointing to it.
    112112@end deftypefun
    113113
    114 @deftypefun EdgeIterator Graph::AddEdge (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIterator} @var{to}})
     114@deftypefun EdgeIterator Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIterator} @var{to}})
    115115Adds a new edge with tail @var{from} and head @var{to} to the graph
    116116and returns an @code{EdgeIterator} pointing to it.
    117117@end deftypefun
    118118
    119 @deftypefun void Graph::Delete (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{n}})
     119@deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{n}})
    120120Deletes the node @var{n}. It also deletes the adjacent edges.
    121121@end deftypefun
    122122
    123 @deftypefun void Graph::Delete (@w{const @mref{Graph-EdgeIterator,EdgeIterator} @var{e}})
     123@deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIterator} @var{e}})
    124124Deletes the edge @var{n}.
    125125@end deftypefun
    126126
    127 @deftypefun void Graph::Clean ()
     127@deftypefun void Graph::clean ()
    128128Deletes all edges and nodes from the graph.
    129129@end deftypefun
    130130
    131 @deftypefun int Graph::NodeNum ()
     131@deftypefun int Graph::nodeNum ()
    132132Returns the number of the nodes in the graph.
    133133@end deftypefun
    134134
    135 @subsubsection NodePoint Operations
    136 
    137 @deftypefun NodePoint Graph::GetFirst (NodePoint &@var{n})
    138 @deftypefunx NodePoint Graph::Next (const NodePoint @var{n})
    139 @deftypefunx {NodePoint &} Graph::GoNext (NodePoint &@var{n})
     135@subsubsection NodeIt Operations
     136
     137@deftypefun NodeIt Graph::getFirst (NodeIt &@var{n})
     138@deftypefunx NodeIt Graph::next (const NodeIt @var{n})
     139@deftypefunx {NodeIt &} Graph::goNext (NodeIt &@var{n})
    140140The nodes in the graph forms a list. @code{GetFirst(n)} sets @var{n} to
    141 be the first node. @code{Next(n)} gives back the subsequent
     141be the first node. @code{next(n)} gives back the subsequent
    142142node. @code{Next(n)} is equivalent to @code{n=Next(n)}, though it
    143143might be faster.  ??? What should be the return value ???
    144144@end deftypefun
    145145
    146 @deftypefun bool Graph::Valid (NodePoint &@var{e})
    147 @deftypefunx bool NodePoint::Valid ()
    148 These functions check if and NodePoint is valid or not.
     146@deftypefun bool Graph::valid (NodeIt &@var{e})
     147@deftypefunx bool NodeIt::valid ()
     148These functions check if and NodeIt is valid or not.
    149149??? Which one should be implemented ???
    150150@end deftypefun
    151151
    152 @subsubsection EdgePoint Operations
    153 
    154 @deftypefun AllEdgePoint Graph::GetFirst (const AllEdgePoint & @var{e})
    155 @deftypefunx AllEdgePoint Graph::Next (const AllEdgePoint @var{n})
    156 @deftypefunx {AllEdgePoint &} Graph::GoNext (AllEdgePoint &@var{n})
     152@subsubsection EdgeIt Operations
     153
     154@deftypefun EachEdgeIt Graph::getFirst (const EachEdgeIt & @var{e})
     155@deftypefunx EachEdgeIt Graph::next (const EachEdgeIt @var{n})
     156@deftypefunx {EachEdgeIt &} Graph::goNext (EachEdgeIt &@var{n})
    157157With these functions you can go though all the edges of the graph.
    158158??? What should be the return value ???
    159159@end deftypefun
    160160
    161 @deftypefun InEdgePoint Graph::GetFirst (const InEdgePoint & @var{e}, const NodePoint @var{n})
    162 @deftypefunx OutEdgePoint Graph::GetFirst (const OutEdgePoint & @var{e}, const NodePoint @var{n})
    163 @deftypefunx SymEdgePoint Graph::GetFirst (const SymEdgePoint & @var{e}, const NodePoint @var{n})
     161@deftypefun InEdgeIt Graph::getFirst (const InEdgeIt & @var{e}, const NodeIt @var{n})
     162@deftypefunx OutEdgeIt Graph::getFirst (const OutEdgeIt & @var{e}, const NodeIt @var{n})
     163@deftypefunx SymEdgeIt Graph::getFirst (const SymEdgeIt & @var{e}, const NodeIt @var{n})
    164164The edges leaving from, arriving at or adjacent with a node forms a
    165165list.  These functions give back the first elements of these
    166166lists. The exact behavior depends on the type of @var{e}.
    167167
    168 If @var{e} is an @code{InEdgePoint} or an @code{OutEdgePoint} then
    169 @code{GetFirst} sets @var{e} to be the first incoming or outgoing edge
     168If @var{e} is an @code{InEdgeIt} or an @code{OutEdgeIt} then
     169@code{getFirst} sets @var{e} to be the first incoming or outgoing edge
    170170of the node @var{n}, respectively.
    171171
    172 If @var{e} is a @code{SymEdgePoint} then
    173 @code{GetFirst} sets @var{e} to be the first incoming if there exists one
     172If @var{e} is a @code{SymEdgeIt} then
     173@code{getFirst} sets @var{e} to be the first incoming if there exists one
    174174otherwise the first outgoing edge.
    175175
     
    178178@end deftypefun
    179179
    180 @deftypefun InEdgePoint Graph::Next (const InEdgePoint @var{e})
    181 @deftypefunx OutEdgePoint Graph::Next (const OutEdgePoint @var{e})
    182 @deftypefunx SymEdgePoint Graph::Next (const SymEdgePoint @var{e})
     180@deftypefun InEdgeIt Graph::next (const InEdgeIt @var{e})
     181@deftypefunx OutEdgeIt Graph::next (const OutEdgeIt @var{e})
     182@deftypefunx SymEdgeIt Graph::next (const SymEdgeIt @var{e})
    183183These functions give back the edge that follows @var{e}
    184184@end deftypefun
    185185
    186 @deftypefun {InEdgePoint &} Graph::GoNext (InEdgePoint &@var{e})
    187 @deftypefunx {OutEdgePoint &} Graph::GoNext (OutEdgePoint &@var{e})
    188 @deftypefunx {SymEdgePoint &} Graph::GoNext (SymEdgePoint &@var{e})
    189 @code{G.GoNext(e)} is equivalent to @code{e=G.Next(e)}, though it
     186@deftypefun {InEdgeIt &} Graph::goNext (InEdgeIt &@var{e})
     187@deftypefunx {OutEdgeIt &} Graph::goNext (OutEdgeIt &@var{e})
     188@deftypefunx {SymEdgeIt &} Graph::goNext (SymEdgeIt &@var{e})
     189@code{G.goNext(e)} is equivalent to @code{e=G.next(e)}, though it
    190190might be faster.
    191191??? What should be the return value ???
    192192@end deftypefun
    193193
    194 @deftypefun bool Graph::Valid (EdgePoint &@var{e})
    195 @deftypefunx bool EdgePoint::Valid ()
    196 These functions check if and EdgePoint is valid or not.
     194@deftypefun bool Graph::valid (EdgeIt &@var{e})
     195@deftypefunx bool EdgeIt::valid ()
     196These functions check if and EdgeIt is valid or not.
    197197??? Which one should be implemented ???
    198198@end deftypefun
    199199
    200 @deftypefun NodePoint Graph::From (const EdgePoint @var{e})
    201 @deftypefunx NodePoint Graph::To (const EdgePoint @var{e})
    202 @deftypefunx NodePoint Graph::ANode (const InEdgePoint @var{e})
    203 @deftypefunx NodePoint Graph::ANode (const OutEdgePoint @var{e})
    204 @deftypefunx NodePoint Graph::ANode (const SymEdgePoint @var{e})
    205 @deftypefunx NodePoint Graph::BNode (const InEdgePoint @var{e})
    206 @deftypefunx NodePoint Graph::BNode (const OutEdgePoint @var{e})
    207 @deftypefunx NodePoint Graph::BNode (const SymEdgePoint @var{e})
     200@deftypefun NodeIt Graph::tail (const EdgeIt @var{e})
     201@deftypefunx NodeIt Graph::head (const EdgeIt @var{e})
     202@deftypefunx NodeIt Graph::aNode (const InEdgeIt @var{e})
     203@deftypefunx NodeIt Graph::aNode (const OutEdgeIt @var{e})
     204@deftypefunx NodeIt Graph::aNode (const SymEdgeIt @var{e})
     205@deftypefunx NodeIt Graph::bNode (const InEdgeIt @var{e})
     206@deftypefunx NodeIt Graph::bNode (const OutEdgeIt @var{e})
     207@deftypefunx NodeIt Graph::bNode (const SymEdgeIt @var{e})
    208208There queries give back the two endpoints of the edge @var{e}.  For a
    209 directed edge @var{e}, @code{From(e)} and @code{To(e)} is its tail and
     209directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and
    210210its head, respectively. For an undirected @var{e}, they are two
    211211endpoints, but you should not rely on which end is which.
    212212
    213 @code{ANode(e)} is the node which @var{e} is bounded to, i.e. it is
    214 equal to @code{From(e)} if @var{e} is an @code{OutEdgePoint} and
    215 @code{To(e)} if @var{e} is an @code{InEdgePoint}. If @var{e} is a
    216 @code{SymEdgePoint} and it or its first preceding edge was created by
    217 @code{GetFirst(e,n)}, then @code{ANode(e)} is equal to @var{n}.
    218 
    219 @code{BNode(e)} is the other end of the edge.
    220 
    221 ???It it implemented in an other way now. (Member function <-> Graph global)???
     213@code{aNode(e)} is the node which @var{e} is bounded to, i.e. it is
     214equal to @code{tail(e)} if @var{e} is an @code{OutEdgeIt} and
     215@code{head(e)} if @var{e} is an @code{InEdgeIt}. If @var{e} is a
     216@code{SymEdgeIt} and it or its first preceding edge was created by
     217@code{getFirst(e,n)}, then @code{aNode(e)} is equal to @var{n}.
     218
     219@code{bNode(e)} is the other end of the edge.
     220
     221???It is implemented in an other way now. (Member function <-> Graph global)???
    222222@end deftypefun
    223223
  • 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
  • src/work/alpar/gwrapper.h

    r65 r70  
    8484  NodeIt tail(const EdgeIt &e);
    8585  { return graph->head(e); }
     86 
     87  template<typename I> NodeIt aNode(const I e);
     88  { return graph->aNode(e); }
     89  template<typename I> NodeIt bNode(const I e);
     90  { return graph->bNode(e); }
     91 
     92  template<typename I> bool valid(const I i);
     93  { return graph->valid(i); }
     94 
     95  template<typename I> void setInvalid(const I &i);
     96  { return graph->setInvalid(i); }
     97 
     98  NodeIt addNode(); { return graph->addNode(); }
     99  EdgeIt addEdge(const NodeIt from,const NodeIt to);
     100  { return graph->addEdge(to,from); }
     101 
     102  template<I> void delete(I i); { graph->delete(i); }
     103 
     104  void clean();  { graph->clean(); }
     105 
     106  template<class T> class NodeMap : public typename G::NodeMap<T>;
     107  template<class T> class EdgeMap : public typename G::EdgeMap<T>;
     108 
     109  void SetG(G &g) {graph = &g;}
     110 
     111  RevGraphWrapper() {graph = NULL;}
     112  RevGraphWrapper(G &g) {graph = &g;}
     113};
     114
     115template<typename G>
     116class SymGraphWrapper
     117{
     118  G *graph;
     119 
     120public:
     121  typedef G BaseGraph;
     122
     123  typedef typename G::EdgeIt EdgeIt;
     124 
     125  typedef typename G::InEdgeIt SymEdgeIt;
     126  typedef typename G::OutEdgeIt SymEdgeIt;
     127  typedef typename G::SymEdgeIt SymEdgeIt;
     128  typedef typename G::EachEdgeIt EachEdgeIt;
     129
     130  typedef typename G::NodeIt NodeIt;
     131   
     132  template<typename I> I &getFirst(I &i); { return graph->getFirst(i); }
     133  template<typename I,typename P> I &getFirst(I &i,const P &p);
     134  { return graph->getFirst(i,p); }
     135  template<typename I> I next(const I i); { return graph->goNext(i); }
     136  template<typename I> I &goNext(I &i); { return graph->goNext(i); }
     137
     138  NodeIt head(const EdgeIt &e);
     139  { return graph->head(e); }
     140  NodeIt tail(const EdgeIt &e);
     141  { return graph->tail(e); }
     142 
     143  template<typename I> NodeIt aNode(const I e);
     144  { return graph->aNode(e); }
     145  template<typename I> NodeIt bNode(const I e);
     146  { return graph->bNode(e); }
     147 
     148  template<typename I> bool valid(const I i);
     149  { return graph->valid(i); }
     150 
     151  template<typename I> void setInvalid(const I &i);
     152  { return graph->setInvalid(i); }
     153 
     154  NodeIt addNode(); { return graph->addNode(); }
     155  EdgeIt addEdge(const NodeIt from,const NodeIt to);
     156  { return graph->addEdge(to,from); }
     157 
     158  template<I> void delete(I i); { graph->delete(i); }
     159 
     160  void clean();  { graph->clean(); }
     161 
     162  template<class T> class NodeMap : public typename G::NodeMap<T>;
     163  template<class T> class EdgeMap : public typename G::EdgeMap<T>;
     164 
     165  void SetG(G &g) {graph = &g;}
     166 
     167  RevGraphWrapper() {graph = NULL;}
     168  RevGraphWrapper(G &g) {graph = &g;}
     169};
     170
     171
     172// FIXME: comparison should be made better!!!
     173template<typename G, typename lomap, typename fmap, typename himap>
     174class ResGraphWrapper
     175{
     176  G *graph;
     177 
     178public:
     179  typedef G BaseGraph;
     180
     181  typedef typename G::EdgeIt EdgeIt;
     182 
     183  class InEdgeIt
     184  {
     185  public:
     186    G::NodeIt n;
     187    G::InEdgeIt i;   
     188    G::OutEdgeIt o;
     189  }
     190  class OutEdgeIt
     191  {
     192  public:
     193    G::NodeIt n;
     194    G::InEdgeIt i;   
     195    G::OutEdgeIt o;
     196  }
     197  typedef typename G::SymEdgeIt SymEdgeIt;
     198  typedef typename G::EachEdgeIt EachEdgeIt;
     199
     200  typedef typename G::NodeIt NodeIt;
     201   
     202  NodeIt &getFirst(NodeIt &n); { return graph->getFirst(n); }
     203
     204  // EachEdge and SymEdge  is missing!!!!
     205  // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
     206
     207  InEdgeIt &getFirst(InEdgeIt &e,const NodeIt &n)
     208  {
     209    e.n=n;
     210    graph->getFirst(e.i,n);
     211    while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
     212      graph->goNext(e.i);
     213    if(!graph->valid(e.i)) {
     214      graph->getFirst(e.o,n);
     215      while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
     216        graph->goNext(e.o);
     217    }
     218    return e;
     219  }
     220  InEdgeIt &goNext(InEdgeIt &e)
     221  {
     222    if(graph->valid(e.i)) {
     223      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
     224        graph->goNext(e.i);
     225      if(graph->valid(e.i)) return e;
     226      else graph->getFirst(e.o,e.n);
     227    }
     228    else {
     229      while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
     230        graph->goNext(e.o);
     231      return e;
     232    }
     233  }
     234  InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
     235  bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
     236
     237  OutEdgeIt &getFirst(OutEdgeIt &e,const NodeIt &n)
     238  {
     239    e.n=n;
     240    graph->getFirst(e.o,n);
     241    while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
     242      graph->goNext(e.o);
     243    if(!graph->valid(e.o)) {
     244      graph->getFirst(e.i,n);
     245      while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
     246        graph->goNext(e.i);
     247    }
     248    return e;
     249  }
     250  OutEdgeIt &goNext(OutEdgeIt &e)
     251  {
     252    if(graph->valid(e.o)) {
     253      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
     254        graph->goNext(e.o);
     255      if(graph->valid(e.o)) return e;
     256      else graph->getFirst(e.i,e.n);
     257    }
     258    else {
     259      while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
     260        graph->goNext(e.i);
     261      return e;
     262    }
     263  }
     264  OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
     265  bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
     266
     267  template<typename I> I &goNext(I &i); { return graph->goNext(i); }
     268  template<typename I> I next(const I i); { return graph->goNext(i); }
     269
     270  NodeIt head(const EdgeIt &e);
     271  { return graph->head(e); }
     272  NodeIt tail(const EdgeIt &e);
     273  { return graph->tail(e); }
    86274 
    87275  template<typename I> NodeIt aNode(const I e);
Note: See TracChangeset for help on using the changeset viewer.