Changeset 70:851ca9a60e90 in lemon0.x
 Timestamp:
 02/10/04 14:29:15 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@86
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

doc/etikol.texi
r29 r70 1 1 \input texinfo @c *texinfo* 2 @comment $Id: etikol.texi,v 1. 4 2004/01/21 08:39:33alpar Exp $2 @comment $Id: etikol.texi,v 1.5 2004/02/10 13:29:15 alpar Exp $ 3 3 @comment %**start of header 4 4 @setfilename etikol.info … … 36 36 @comment %**end of header 37 37 38 @c @copying39 @cThis manual is for GNU ETILOL Optimization Library40 @c(version @value{VERSION}, @value{UPDATED}).38 @copying 39 This manual is for GNU ETILOL Optimization Library 40 (version @value{VERSION}, @value{UPDATED}). 41 41 42 @cCopyright @copyright{} 2003 ETIK.42 Copyright @copyright{} 2003 ETIK. 43 43 44 @ c @quotation45 @cPermission is granted to copy, distribute and/or modify this document46 @cunder the terms of the GNU Free Documentation License, Version 1.1 or47 @cany later version published by the Free Software Foundation; with no48 @cInvariant Sections, with the FrontCover Texts being ``A GNU Manual,''49 @cand with the BackCover Texts as in (a) below. A copy of the50 @clicense is included in the section entitled ``GNU Free Documentation51 @cLicense.''44 @quotation 45 Permission is granted to copy, distribute and/or modify this document 46 under the terms of the GNU Free Documentation License, Version 1.1 or 47 any later version published by the Free Software Foundation; with no 48 Invariant Sections, with the FrontCover Texts being ``A GNU Manual,'' 49 and with the BackCover Texts as in (a) below. A copy of the 50 license is included in the section entitled ``GNU Free Documentation 51 License.'' 52 52 53 @c(a) The FSF's BackCover Text is: ``You have freedom to copy and modify54 @cthis GNU Manual, like GNU software. Copies published by the Free55 @cSoftware Foundation raise funds for GNU development.''56 @ c @end quotation57 @ c @end copying53 (a) The FSF's BackCover Text is: ``You have freedom to copy and modify 54 this GNU Manual, like GNU software. Copies published by the Free 55 Software Foundation raise funds for GNU development.'' 56 @end quotation 57 @end copying 58 58 59 59 @dircategory Texinfo documentation system 
doc/flfgraph.texi
r26 r70 28 28 29 29 @anchor{GraphNodeIterator} 30 @deftp {Type} Graph::Node Point30 @deftp {Type} Graph::NodeIt 31 31 @deftpx {Type} Graph::NodeIterator 32 32 These types points a node uniquely. The difference between the 33 @code{Node Point} and the @code{NodeIterator} is that @code{NodePoint}33 @code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt} 34 34 requires the graph structure itself for most of the operations. 35 35 For examples using iterators you can go through all nodes as follows. … … 38 38 Graph G; 39 39 int nodenum=0; 40 for(Graph::NodeIterator n(G);n. Valid();++n) ++nodenum;40 for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum; 41 41 @end verbatim 42 42 @end quotation 43 Using @code{Node Point} the last line looks like this.43 Using @code{NodeIt} the last line looks like this. 44 44 @quotation 45 45 @verbatim 46 for( MyGraph::NodePoint n(G);n.Valid();n=G.Next(n)) ++nodenum;46 for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum; 47 47 @end verbatim 48 48 @end quotation … … 50 50 @quotation 51 51 @verbatim 52 MyGraph::Node Point n;53 for(G. GetFirst(n);G.Valid(n);G.GoNext(n)) ++nodenum;52 MyGraph::NodeIt n; 53 for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum; 54 54 @end verbatim 55 55 @end quotation 56 56 @end deftp 57 57 58 @deftp {Type} Graph::Edge Point59 @deftpx {Type} Graph::InEdge Point60 @deftpx {Type} Graph::OutEdge Point61 @deftpx {Type} Graph::BiEdge Point62 @deftpx {Type} Graph::SymEdge Point58 @deftp {Type} Graph::EdgeIt 59 @deftpx {Type} Graph::InEdgeIt 60 @deftpx {Type} Graph::OutEdgeIt 61 @deftpx {Type} Graph::BiEdgeIt 62 @deftpx {Type} Graph::SymEdgeIt 63 63 Each of these types points an edge uniquely. The difference between the 64 @code{Edge Point} and the64 @code{EdgeIt} and the 65 65 @c @mref{GraphNodeIterator,@code{EdgeIterator}} 66 66 @mref{GraphNodeIterator , EdgeIterator} 67 67 series is that 68 @code{Edge Point} requires the graph structure itself for most of the68 @code{EdgeIt} requires the graph structure itself for most of the 69 69 operations. 70 70 @end deftp … … 76 76 @deftpx {Type} Graph::BiEdgeIterator 77 77 @deftpx {Type} Graph::SymEdgeIterator 78 @deftpx {Type} Graph:: AllEdgeIterator78 @deftpx {Type} Graph::EachEdgeIterator 79 79 Each of these types points an edge uniquely. The difference between the 80 @code{Edge Point} and the @code{EdgeIterator} series is that81 @code{Edge Point} requires the graph structure itself for most of the80 @code{EdgeIt} and the @code{EdgeIterator} series is that 81 @code{EdgeIt} requires the graph structure itself for most of the 82 82 operations. 83 83 … … 108 108 @subsubsection Graph Maintenence Operations 109 109 110 @deftypefun NodeIterator Graph:: AddNode ()110 @deftypefun NodeIterator Graph::addNode () 111 111 Adds a new node to the graph and returns a @code{NodeIterator} pointing to it. 112 112 @end deftypefun 113 113 114 @deftypefun EdgeIterator Graph:: AddEdge (@w{const @mref{GraphNodeIterator,NodeIterator} @var{from}}, @w{const @mref{GraphNodeIterator,NodeIterator} @var{to}})114 @deftypefun EdgeIterator Graph::addEdge (@w{const @mref{GraphNodeIterator,NodeIterator} @var{from}}, @w{const @mref{GraphNodeIterator,NodeIterator} @var{to}}) 115 115 Adds a new edge with tail @var{from} and head @var{to} to the graph 116 116 and returns an @code{EdgeIterator} pointing to it. 117 117 @end deftypefun 118 118 119 @deftypefun void Graph:: Delete (@w{const @mref{GraphNodeIterator,NodeIterator} @var{n}})119 @deftypefun void Graph::delete (@w{const @mref{GraphNodeIterator,NodeIterator} @var{n}}) 120 120 Deletes the node @var{n}. It also deletes the adjacent edges. 121 121 @end deftypefun 122 122 123 @deftypefun void Graph:: Delete (@w{const @mref{GraphEdgeIterator,EdgeIterator} @var{e}})123 @deftypefun void Graph::delete (@w{const @mref{GraphEdgeIterator,EdgeIterator} @var{e}}) 124 124 Deletes the edge @var{n}. 125 125 @end deftypefun 126 126 127 @deftypefun void Graph:: Clean ()127 @deftypefun void Graph::clean () 128 128 Deletes all edges and nodes from the graph. 129 129 @end deftypefun 130 130 131 @deftypefun int Graph:: NodeNum ()131 @deftypefun int Graph::nodeNum () 132 132 Returns the number of the nodes in the graph. 133 133 @end deftypefun 134 134 135 @subsubsection Node Point Operations136 137 @deftypefun Node Point Graph::GetFirst (NodePoint &@var{n})138 @deftypefunx Node Point Graph::Next (const NodePoint @var{n})139 @deftypefunx {Node Point &} 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}) 140 140 The 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 subsequent141 be the first node. @code{next(n)} gives back the subsequent 142 142 node. @code{Next(n)} is equivalent to @code{n=Next(n)}, though it 143 143 might be faster. ??? What should be the return value ??? 144 144 @end deftypefun 145 145 146 @deftypefun bool Graph:: Valid (NodePoint &@var{e})147 @deftypefunx bool Node Point::Valid ()148 These functions check if and Node Point is valid or not.146 @deftypefun bool Graph::valid (NodeIt &@var{e}) 147 @deftypefunx bool NodeIt::valid () 148 These functions check if and NodeIt is valid or not. 149 149 ??? Which one should be implemented ??? 150 150 @end deftypefun 151 151 152 @subsubsection Edge Point Operations153 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}) 157 157 With these functions you can go though all the edges of the graph. 158 158 ??? What should be the return value ??? 159 159 @end deftypefun 160 160 161 @deftypefun InEdge Point Graph::GetFirst (const InEdgePoint & @var{e}, const NodePoint @var{n})162 @deftypefunx OutEdge Point Graph::GetFirst (const OutEdgePoint & @var{e}, const NodePoint @var{n})163 @deftypefunx SymEdge Point 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}) 164 164 The edges leaving from, arriving at or adjacent with a node forms a 165 165 list. These functions give back the first elements of these 166 166 lists. The exact behavior depends on the type of @var{e}. 167 167 168 If @var{e} is an @code{InEdge Point} or an @code{OutEdgePoint} then169 @code{ GetFirst} sets @var{e} to be the first incoming or outgoing edge168 If @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 170 170 of the node @var{n}, respectively. 171 171 172 If @var{e} is a @code{SymEdge Point} then173 @code{ GetFirst} sets @var{e} to be the first incoming if there exists one172 If @var{e} is a @code{SymEdgeIt} then 173 @code{getFirst} sets @var{e} to be the first incoming if there exists one 174 174 otherwise the first outgoing edge. 175 175 … … 178 178 @end deftypefun 179 179 180 @deftypefun InEdge Point Graph::Next (const InEdgePoint @var{e})181 @deftypefunx OutEdge Point Graph::Next (const OutEdgePoint @var{e})182 @deftypefunx SymEdge Point 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}) 183 183 These functions give back the edge that follows @var{e} 184 184 @end deftypefun 185 185 186 @deftypefun {InEdge Point &} Graph::GoNext (InEdgePoint &@var{e})187 @deftypefunx {OutEdge Point &} Graph::GoNext (OutEdgePoint &@var{e})188 @deftypefunx {SymEdge Point &} Graph::GoNext (SymEdgePoint &@var{e})189 @code{G. GoNext(e)} is equivalent to @code{e=G.Next(e)}, though it186 @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 190 190 might be faster. 191 191 ??? What should be the return value ??? 192 192 @end deftypefun 193 193 194 @deftypefun bool Graph:: Valid (EdgePoint &@var{e})195 @deftypefunx bool Edge Point::Valid ()196 These functions check if and Edge Point is valid or not.194 @deftypefun bool Graph::valid (EdgeIt &@var{e}) 195 @deftypefunx bool EdgeIt::valid () 196 These functions check if and EdgeIt is valid or not. 197 197 ??? Which one should be implemented ??? 198 198 @end deftypefun 199 199 200 @deftypefun Node Point Graph::From (const EdgePoint @var{e})201 @deftypefunx Node Point Graph::To (const EdgePoint @var{e})202 @deftypefunx Node Point Graph::ANode (const InEdgePoint @var{e})203 @deftypefunx Node Point Graph::ANode (const OutEdgePoint @var{e})204 @deftypefunx Node Point Graph::ANode (const SymEdgePoint @var{e})205 @deftypefunx Node Point Graph::BNode (const InEdgePoint @var{e})206 @deftypefunx Node Point Graph::BNode (const OutEdgePoint @var{e})207 @deftypefunx Node Point 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}) 208 208 There 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 and209 directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and 210 210 its head, respectively. For an undirected @var{e}, they are two 211 211 endpoints, but you should not rely on which end is which. 212 212 213 @code{ ANode(e)} is the node which @var{e} is bounded to, i.e. it is214 equal to @code{ From(e)} if @var{e} is an @code{OutEdgePoint} and215 @code{ To(e)} if @var{e} is an @code{InEdgePoint}. If @var{e} is a216 @code{SymEdge Point} and it or its first preceding edge was created by217 @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 i timplemented 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 214 equal 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)??? 222 222 @end deftypefun 223 223 
src/include/graph.h
r8 r70 19 19 typedef N NodeType; 20 20 21 class Edge Point21 class EdgeIt 22 22 { 23 23 public: 24 24 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; 34 36 35 37 class NodeIterator; … … 50 52 friend class BiEdgeIterator; 51 53 friend class SymEdgeIterator; 52 friend class AllEdgeIterator;54 friend class EachEdgeIterator; 53 55 54 56 class NodeIterator … … 63 65 NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;} 64 66 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();} 68 70 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; } 71 73 72 74 N &operator*() const { return G>Data(n); } … … 76 78 bool operator!=(const NodeIterator &i) const {return n!=i.n;} 77 79 78 int Index() const { return n; } //If the nodes are indexable80 int index() const { return n; } //If the nodes are indexable 79 81 friend class Graph; 80 82 friend class EdgeIterator; … … 83 85 friend class BiEdgeIterator; 84 86 friend class SymEdgeIterator; 85 friend class AllEdgeIterator;87 friend class EachEdgeIterator; 86 88 friend class FirstAnythingTypeNode; 87 89 … … 97 99 // Meg a From() es To() miatt!!!!!!!!!! 98 100 99 NEGRO::Edge Point e;101 NEGRO::EdgeIt e; 100 102 101 103 public: … … 105 107 // Lehet, hogy ez a ketto nem kell!!! 106 108 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;} 111 115 E &operator*() const { return G>Data(e); } 112 116 E *operator>() const { return &G>Data(e); } … … 120 124 bool operator!=(const EdgeIterator &i) const {return e!=i.e;} 121 125 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;} 123 127 //If the edges are indexable 124 128 … … 128 132 friend class BiEdgeIterator; 129 133 friend class SymEdgeIterator; 130 friend class AllEdgeIterator;134 friend class EachEdgeIterator; 131 135 }; 132 136 … … 134 138 { 135 139 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();} 140 144 141 145 operator InEdgeIterator () … … 153 157 public: 154 158 InEdgeIterator() {} 155 InEdgeIterator( constGraph<N,E> &Gr,const NodeIterator &n)159 InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n) 156 160 { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);} 157 161 … … 181 185 { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);} 182 186 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();} 186 190 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();} 191 195 192 196 operator const InEdgeIterator () … … 205 209 public: 206 210 SymEdgeIterator() {} 207 SymEdgeIterator( constGraph<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();} 213 217 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();} 218 222 219 223 operator const InEdgeIterator () … … 227 231 }; 228 232 229 class AllEdgeIterator : public EdgeIterator233 class EachEdgeIterator : public EdgeIterator 230 234 { 231 235 NodeIterator n; // Itt ketszer van a G 232 236 233 237 public: 234 AllEdgeIterator() {}235 AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)238 EachEdgeIterator() {} 239 EachEdgeIterator(Graph<N,E> &Gr) : n(Gr) 236 240 { 237 e=n. isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;241 e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL; 238 242 } 239 243 240 AllEdgeIterator &GoNext()244 EachEdgeIterator &goNext() 241 245 { 242 246 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); 244 248 return *this; 245 249 } 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;} 255 261 operator const InEdgeIterator () 256 262 {InEdgeIterator i; i.G=G;i.e=e;return i;} … … 270 276 typedef SymEdgeIterator DeletingSymEdgeIterator; 271 277 272 const NodeIterator FirstNode()278 const NodeIterator firstNode() 273 279 { 274 280 NodeIterator i; … … 277 283 } 278 284 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) 282 288 { p=OldGraph<N,E>::FirstIn(n); } 283 void GetFirst(OutEdgePoint &p,const NodePoint &n)289 void getFirst(OutEdgeIt &p,const NodeIt &n) 284 290 { p=OldGraph<N,E>::FirstOut(n); } 285 void GetFirst(SymEdgePoint &p,const NodePoint &n)291 void getFirst(SymEdgeIt &p,const NodeIt &n) 286 292 { p=OldGraph<N,E>::FirstEdge(n); } 287 void GetFirst(EdgePoint &p) //Vegigmegy mindenen288 { 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) 293 299 { 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) 295 301 { 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>::First Sym(n.n); }298 void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen302 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 299 305 { 300 306 i.G=this; 301 GetFirst(i.n);307 getFirst(i.n); 302 308 i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL; 303 309 } … … 306 312 307 313 //Vagy beginnode()? 308 const DeletingEdgeIterator FirstOut(const NodeIterator &n)314 const DeletingEdgeIterator firstOut(const NodeIterator &n) 309 315 { 310 316 EdgeIterator i; … … 312 318 return i; 313 319 } 314 const DeletingEdgeIterator FirstIn(const NodeIterator &n)320 const DeletingEdgeIterator firstIn(const NodeIterator &n) 315 321 { 316 322 EdgeIterator i; … … 318 324 return i; 319 325 } 320 const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)326 const DeletingSymEdgeIterator firstSym(const NodeIterator &n) 321 327 { 322 328 EdgeIterator i; … … 342 348 {SymEdgeIterator i; n.G>GetFirst(i,n);return i;} 343 349 344 operator const InEdge Point () const345 {InEdge Point i; n.G>GetFirst(i,n);return i;}346 operator const OutEdge Point () const347 {OutEdge Point i; n.G>GetFirst(i,n);return i;}348 operator const SymEdge Point () const349 {SymEdge Point 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;} 350 356 }; 351 357 … … 356 362 FirstAnythingType(Graph<N,E> *gg) : G(gg) {} 357 363 358 operator const AllEdgeIterator () const359 { AllEdgeIterator i; G>GetFirst(i);return i;}360 operator const Edge Point () const361 {Edge Point 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;} 362 368 operator const NodeIterator () const 363 369 {NodeIterator i; G>GetFirst(i);return i;} 364 operator const Node Point () const365 {Node Point i; G>GetFirst(i);return i;}370 operator const NodeIt () const 371 {NodeIt i; G>GetFirst(i);return i;} 366 372 } _FST; 367 373 368 374 // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;} 369 FirstAnythingTypeNode First(NodeIterator &i)375 FirstAnythingTypeNode first(NodeIterator &i) 370 376 {FirstAnythingTypeNode t(i); return t;} 371 const FirstAnythingType & First() {return _FST;}377 const FirstAnythingType &first() {return _FST;} 372 378 373 379 // LastNode() vagy endnode() stb. Nem kell? 374 380 375 DeletingNodeIterator AddNode()381 DeletingNodeIterator addNode() 376 382 { 377 383 DeletingNodeIterator i; … … 380 386 } 381 387 DeletingEdgeIterator 382 AddEdge(const NodeIterator from,const NodeIterator to)388 addEdge(const NodeIterator from,const NodeIterator to) 383 389 { 384 390 DeletingEdgeIterator i; … … 389 395 void Delete(DeletingEdgeIterator e) {e.G>OldGraph<N,E>::Delete(e.e);} 390 396 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(); } 393 399 394 400 Graph() : _FST(this) {} … … 402 408 public: 403 409 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()];} 406 412 T operator[](NodeIterator i) {return map[i.Index()];} 407 413 … … 409 415 410 416 NodeMap() {} 411 void SetG(Graph<N,E> &Gr) { G=&Gr; update();}417 void setG(Graph<N,E> &Gr) { G=&Gr; update();} 412 418 }; 413 419 … … 419 425 public: 420 426 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()];} 424 430 425 431 void update() … … 427 433 428 434 EdgeMap() {} 429 void SetG(Graph<N,E> &Gr)435 void setG(Graph<N,E> &Gr) 430 436 { G=&Gr ;update();} 431 437 … … 433 439 434 440 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 graphtype 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[n1]?path[n1].tail():path[n1].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()); } 438 483 }; 439 484 … … 444 489 mcmn 445 490 */ 446 447 } 491 }; 448 492 449 493 #endif 
src/work/alpar/gwrapper.h
r65 r70 84 84 NodeIt tail(const EdgeIt &e); 85 85 { 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 115 template<typename G> 116 class SymGraphWrapper 117 { 118 G *graph; 119 120 public: 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!!! 173 template<typename G, typename lomap, typename fmap, typename himap> 174 class ResGraphWrapper 175 { 176 G *graph; 177 178 public: 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); } 86 274 87 275 template<typename I> NodeIt aNode(const I e);
Note: See TracChangeset
for help on using the changeset viewer.