# HG changeset patch # User alpar # Date 1076419755 0 # Node ID 851ca9a60e90d77de633bafe07caf1b9441a8f54 # Parent 24c2c2989e0f738ef256ed93f4d7e40f194c2b47 . diff -r 24c2c2989e0f -r 851ca9a60e90 doc/etikol.texi --- a/doc/etikol.texi Mon Feb 09 13:11:10 2004 +0000 +++ b/doc/etikol.texi Tue Feb 10 13:29:15 2004 +0000 @@ -1,5 +1,5 @@ \input texinfo @c -*-texinfo-*- -@comment $Id: etikol.texi,v 1.4 2004/01/21 08:39:33 alpar Exp $ +@comment $Id: etikol.texi,v 1.5 2004/02/10 13:29:15 alpar Exp $ @comment %**start of header @setfilename etikol.info @include version.texi @@ -35,26 +35,26 @@ @comment %**end of header -@c @copying -@c This manual is for GNU ETIL-OL Optimization Library -@c (version @value{VERSION}, @value{UPDATED}). +@copying +This manual is for GNU ETIL-OL Optimization Library +(version @value{VERSION}, @value{UPDATED}). -@c Copyright @copyright{} 2003 ETIK. +Copyright @copyright{} 2003 ETIK. -@c @quotation -@c Permission is granted to copy, distribute and/or modify this document -@c under the terms of the GNU Free Documentation License, Version 1.1 or -@c any later version published by the Free Software Foundation; with no -@c Invariant Sections, with the Front-Cover Texts being ``A GNU Manual,'' -@c and with the Back-Cover Texts as in (a) below. A copy of the -@c license is included in the section entitled ``GNU Free Documentation -@c License.'' +@quotation +Permission is granted to copy, distribute and/or modify this document +under the terms of the GNU Free Documentation License, Version 1.1 or +any later version published by the Free Software Foundation; with no +Invariant Sections, with the Front-Cover Texts being ``A GNU Manual,'' +and with the Back-Cover Texts as in (a) below. A copy of the +license is included in the section entitled ``GNU Free Documentation +License.'' -@c (a) The FSF's Back-Cover Text is: ``You have freedom to copy and modify -@c this GNU Manual, like GNU software. Copies published by the Free -@c Software Foundation raise funds for GNU development.'' -@c @end quotation -@c @end copying +(a) The FSF's Back-Cover Text is: ``You have freedom to copy and modify +this GNU Manual, like GNU software. Copies published by the Free +Software Foundation raise funds for GNU development.'' +@end quotation +@end copying @dircategory Texinfo documentation system @direntry diff -r 24c2c2989e0f -r 851ca9a60e90 doc/flf-graph.texi --- a/doc/flf-graph.texi Mon Feb 09 13:11:10 2004 +0000 +++ b/doc/flf-graph.texi Tue Feb 10 13:29:15 2004 +0000 @@ -27,45 +27,45 @@ @end deftp @anchor{Graph-NodeIterator} -@deftp {Type} Graph::NodePoint +@deftp {Type} Graph::NodeIt @deftpx {Type} Graph::NodeIterator These types points a node uniquely. The difference between the -@code{NodePoint} and the @code{NodeIterator} is that @code{NodePoint} +@code{NodeIt} and the @code{NodeIterator} is that @code{NodeIt} requires the graph structure itself for most of the operations. For examples using iterators you can go through all nodes as follows. @quotation @verbatim Graph G; int nodenum=0; -for(Graph::NodeIterator n(G);n.Valid();++n) ++nodenum; +for(Graph::NodeIterator n(G);n.valid();++n) ++nodenum; @end verbatim @end quotation -Using @code{NodePoint} the last line looks like this. +Using @code{NodeIt} the last line looks like this. @quotation @verbatim -for(MyGraph::NodePoint n(G);n.Valid();n=G.Next(n)) ++nodenum; +for(Graph::NodeIt n(G);n.valid();n=G.next(n)) ++nodenum; @end verbatim @end quotation or @quotation @verbatim -MyGraph::NodePoint n; -for(G.GetFirst(n);G.Valid(n);G.GoNext(n)) ++nodenum; +MyGraph::NodeIt n; +for(G.getFirst(n);G.valid(n);G.goNext(n)) ++nodenum; @end verbatim @end quotation @end deftp -@deftp {Type} Graph::EdgePoint -@deftpx {Type} Graph::InEdgePoint -@deftpx {Type} Graph::OutEdgePoint -@deftpx {Type} Graph::BiEdgePoint -@deftpx {Type} Graph::SymEdgePoint +@deftp {Type} Graph::EdgeIt +@deftpx {Type} Graph::InEdgeIt +@deftpx {Type} Graph::OutEdgeIt +@deftpx {Type} Graph::BiEdgeIt +@deftpx {Type} Graph::SymEdgeIt Each of these types points an edge uniquely. The difference between the -@code{EdgePoint} and the +@code{EdgeIt} and the @c @mref{Graph-NodeIterator,@code{EdgeIterator}} @mref{Graph-NodeIterator , EdgeIterator} series is that -@code{EdgePoint} requires the graph structure itself for most of the +@code{EdgeIt} requires the graph structure itself for most of the operations. @end deftp @@ -75,10 +75,10 @@ @deftpx {Type} Graph::OutEdgeIterator @deftpx {Type} Graph::BiEdgeIterator @deftpx {Type} Graph::SymEdgeIterator -@deftpx {Type} Graph::AllEdgeIterator +@deftpx {Type} Graph::EachEdgeIterator Each of these types points an edge uniquely. The difference between the -@code{EdgePoint} and the @code{EdgeIterator} series is that -@code{EdgePoint} requires the graph structure itself for most of the +@code{EdgeIt} and the @code{EdgeIterator} series is that +@code{EdgeIt} requires the graph structure itself for most of the operations. For the @code{EdgeIterator} types you can use operator @code{++} @@ -107,118 +107,118 @@ @subsubsection Graph Maintenence Operations -@deftypefun NodeIterator Graph::AddNode () +@deftypefun NodeIterator Graph::addNode () Adds a new node to the graph and returns a @code{NodeIterator} pointing to it. @end deftypefun -@deftypefun EdgeIterator Graph::AddEdge (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIterator} @var{to}}) +@deftypefun EdgeIterator Graph::addEdge (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{from}}, @w{const @mref{Graph-NodeIterator,NodeIterator} @var{to}}) Adds a new edge with tail @var{from} and head @var{to} to the graph and returns an @code{EdgeIterator} pointing to it. @end deftypefun -@deftypefun void Graph::Delete (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{n}}) +@deftypefun void Graph::delete (@w{const @mref{Graph-NodeIterator,NodeIterator} @var{n}}) Deletes the node @var{n}. It also deletes the adjacent edges. @end deftypefun -@deftypefun void Graph::Delete (@w{const @mref{Graph-EdgeIterator,EdgeIterator} @var{e}}) +@deftypefun void Graph::delete (@w{const @mref{Graph-EdgeIterator,EdgeIterator} @var{e}}) Deletes the edge @var{n}. @end deftypefun -@deftypefun void Graph::Clean () +@deftypefun void Graph::clean () Deletes all edges and nodes from the graph. @end deftypefun -@deftypefun int Graph::NodeNum () +@deftypefun int Graph::nodeNum () Returns the number of the nodes in the graph. @end deftypefun -@subsubsection NodePoint Operations +@subsubsection NodeIt Operations -@deftypefun NodePoint Graph::GetFirst (NodePoint &@var{n}) -@deftypefunx NodePoint Graph::Next (const NodePoint @var{n}) -@deftypefunx {NodePoint &} Graph::GoNext (NodePoint &@var{n}) +@deftypefun NodeIt Graph::getFirst (NodeIt &@var{n}) +@deftypefunx NodeIt Graph::next (const NodeIt @var{n}) +@deftypefunx {NodeIt &} Graph::goNext (NodeIt &@var{n}) The nodes in the graph forms a list. @code{GetFirst(n)} sets @var{n} to -be the first node. @code{Next(n)} gives back the subsequent +be the first node. @code{next(n)} gives back the subsequent node. @code{Next(n)} is equivalent to @code{n=Next(n)}, though it might be faster. ??? What should be the return value ??? @end deftypefun -@deftypefun bool Graph::Valid (NodePoint &@var{e}) -@deftypefunx bool NodePoint::Valid () -These functions check if and NodePoint is valid or not. +@deftypefun bool Graph::valid (NodeIt &@var{e}) +@deftypefunx bool NodeIt::valid () +These functions check if and NodeIt is valid or not. ??? Which one should be implemented ??? @end deftypefun -@subsubsection EdgePoint Operations +@subsubsection EdgeIt Operations -@deftypefun AllEdgePoint Graph::GetFirst (const AllEdgePoint & @var{e}) -@deftypefunx AllEdgePoint Graph::Next (const AllEdgePoint @var{n}) -@deftypefunx {AllEdgePoint &} Graph::GoNext (AllEdgePoint &@var{n}) +@deftypefun EachEdgeIt Graph::getFirst (const EachEdgeIt & @var{e}) +@deftypefunx EachEdgeIt Graph::next (const EachEdgeIt @var{n}) +@deftypefunx {EachEdgeIt &} Graph::goNext (EachEdgeIt &@var{n}) With these functions you can go though all the edges of the graph. ??? What should be the return value ??? @end deftypefun -@deftypefun InEdgePoint Graph::GetFirst (const InEdgePoint & @var{e}, const NodePoint @var{n}) -@deftypefunx OutEdgePoint Graph::GetFirst (const OutEdgePoint & @var{e}, const NodePoint @var{n}) -@deftypefunx SymEdgePoint Graph::GetFirst (const SymEdgePoint & @var{e}, const NodePoint @var{n}) +@deftypefun InEdgeIt Graph::getFirst (const InEdgeIt & @var{e}, const NodeIt @var{n}) +@deftypefunx OutEdgeIt Graph::getFirst (const OutEdgeIt & @var{e}, const NodeIt @var{n}) +@deftypefunx SymEdgeIt Graph::getFirst (const SymEdgeIt & @var{e}, const NodeIt @var{n}) The edges leaving from, arriving at or adjacent with a node forms a list. These functions give back the first elements of these lists. The exact behavior depends on the type of @var{e}. -If @var{e} is an @code{InEdgePoint} or an @code{OutEdgePoint} then -@code{GetFirst} sets @var{e} to be the first incoming or outgoing edge +If @var{e} is an @code{InEdgeIt} or an @code{OutEdgeIt} then +@code{getFirst} sets @var{e} to be the first incoming or outgoing edge of the node @var{n}, respectively. -If @var{e} is a @code{SymEdgePoint} then -@code{GetFirst} sets @var{e} to be the first incoming if there exists one +If @var{e} is a @code{SymEdgeIt} then +@code{getFirst} sets @var{e} to be the first incoming if there exists one otherwise the first outgoing edge. If there are no such edges, @var{e} will be invalid. @end deftypefun -@deftypefun InEdgePoint Graph::Next (const InEdgePoint @var{e}) -@deftypefunx OutEdgePoint Graph::Next (const OutEdgePoint @var{e}) -@deftypefunx SymEdgePoint Graph::Next (const SymEdgePoint @var{e}) +@deftypefun InEdgeIt Graph::next (const InEdgeIt @var{e}) +@deftypefunx OutEdgeIt Graph::next (const OutEdgeIt @var{e}) +@deftypefunx SymEdgeIt Graph::next (const SymEdgeIt @var{e}) These functions give back the edge that follows @var{e} @end deftypefun -@deftypefun {InEdgePoint &} Graph::GoNext (InEdgePoint &@var{e}) -@deftypefunx {OutEdgePoint &} Graph::GoNext (OutEdgePoint &@var{e}) -@deftypefunx {SymEdgePoint &} Graph::GoNext (SymEdgePoint &@var{e}) -@code{G.GoNext(e)} is equivalent to @code{e=G.Next(e)}, though it +@deftypefun {InEdgeIt &} Graph::goNext (InEdgeIt &@var{e}) +@deftypefunx {OutEdgeIt &} Graph::goNext (OutEdgeIt &@var{e}) +@deftypefunx {SymEdgeIt &} Graph::goNext (SymEdgeIt &@var{e}) +@code{G.goNext(e)} is equivalent to @code{e=G.next(e)}, though it might be faster. ??? What should be the return value ??? @end deftypefun -@deftypefun bool Graph::Valid (EdgePoint &@var{e}) -@deftypefunx bool EdgePoint::Valid () -These functions check if and EdgePoint is valid or not. +@deftypefun bool Graph::valid (EdgeIt &@var{e}) +@deftypefunx bool EdgeIt::valid () +These functions check if and EdgeIt is valid or not. ??? Which one should be implemented ??? @end deftypefun -@deftypefun NodePoint Graph::From (const EdgePoint @var{e}) -@deftypefunx NodePoint Graph::To (const EdgePoint @var{e}) -@deftypefunx NodePoint Graph::ANode (const InEdgePoint @var{e}) -@deftypefunx NodePoint Graph::ANode (const OutEdgePoint @var{e}) -@deftypefunx NodePoint Graph::ANode (const SymEdgePoint @var{e}) -@deftypefunx NodePoint Graph::BNode (const InEdgePoint @var{e}) -@deftypefunx NodePoint Graph::BNode (const OutEdgePoint @var{e}) -@deftypefunx NodePoint Graph::BNode (const SymEdgePoint @var{e}) +@deftypefun NodeIt Graph::tail (const EdgeIt @var{e}) +@deftypefunx NodeIt Graph::head (const EdgeIt @var{e}) +@deftypefunx NodeIt Graph::aNode (const InEdgeIt @var{e}) +@deftypefunx NodeIt Graph::aNode (const OutEdgeIt @var{e}) +@deftypefunx NodeIt Graph::aNode (const SymEdgeIt @var{e}) +@deftypefunx NodeIt Graph::bNode (const InEdgeIt @var{e}) +@deftypefunx NodeIt Graph::bNode (const OutEdgeIt @var{e}) +@deftypefunx NodeIt Graph::bNode (const SymEdgeIt @var{e}) There queries give back the two endpoints of the edge @var{e}. For a -directed edge @var{e}, @code{From(e)} and @code{To(e)} is its tail and +directed edge @var{e}, @code{tail(e)} and @code{head(e)} is its tail and its head, respectively. For an undirected @var{e}, they are two endpoints, but you should not rely on which end is which. -@code{ANode(e)} is the node which @var{e} is bounded to, i.e. it is -equal to @code{From(e)} if @var{e} is an @code{OutEdgePoint} and -@code{To(e)} if @var{e} is an @code{InEdgePoint}. If @var{e} is a -@code{SymEdgePoint} and it or its first preceding edge was created by -@code{GetFirst(e,n)}, then @code{ANode(e)} is equal to @var{n}. +@code{aNode(e)} is the node which @var{e} is bounded to, i.e. it is +equal to @code{tail(e)} if @var{e} is an @code{OutEdgeIt} and +@code{head(e)} if @var{e} is an @code{InEdgeIt}. If @var{e} is a +@code{SymEdgeIt} and it or its first preceding edge was created by +@code{getFirst(e,n)}, then @code{aNode(e)} is equal to @var{n}. -@code{BNode(e)} is the other end of the edge. +@code{bNode(e)} is the other end of the edge. -???It it implemented in an other way now. (Member function <-> Graph global)??? +???It is implemented in an other way now. (Member function <-> Graph global)??? @end deftypefun diff -r 24c2c2989e0f -r 851ca9a60e90 src/include/graph.h --- a/src/include/graph.h Mon Feb 09 13:11:10 2004 +0000 +++ b/src/include/graph.h Tue Feb 10 13:29:15 2004 +0000 @@ -18,19 +18,21 @@ typedef E EdgeType; typedef N NodeType; - class EdgePoint + class EdgeIt { public: NEGRO::EdgePoint e; - bool isValid() { return e; } + bool valid() { return e; } }; - class InEdgePoint : public EdgePoint {}; - class OutEdgePoint : public EdgePoint {}; - class BiEdgePoint : public EdgePoint {}; - class SymEdgePoint : public EdgePoint {}; + class InEdgeIt : public EdgeIt {}; + class OutEdgeIt : public EdgeIt {}; + class BiEdgeIt : public EdgeIt {}; + class SymEdgeIt : public EdgeIt {}; - typedef int NodePoint; + typedef int NodeIt; + + typedef NodeIt EachNodeIt; class NodeIterator; @@ -49,7 +51,7 @@ friend class OutEdgeIterator; friend class BiEdgeIterator; friend class SymEdgeIterator; - friend class AllEdgeIterator; + friend class EachEdgeIterator; class NodeIterator { @@ -62,12 +64,12 @@ {G=&Gr;n=Gr.OldGraph::FirstNode();} NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;} - NodeIterator &GoNext() { n=G->NextNode(n); return *this;} - NodeIterator Next() const { return NodeIterator(*this).GoNext();} - NodeIterator &operator++() { return GoNext();} + NodeIterator &goNext() { n=G->NextNode(n); return *this;} + NodeIterator next() const { return NodeIterator(*this).goNext();} + NodeIterator &operator++() { return goNext();} NodeIterator operator++(int) - {NodeIterator tmp(*this); GoNext(); return tmp;} - bool isValid() { return n!=INVALID; } + {NodeIterator tmp(*this); goNext(); return tmp;} + bool valid() { return n!=INVALID; } N &operator*() const { return G->Data(n); } N *operator->() const { return &G->Data(n); } @@ -75,14 +77,14 @@ bool operator==(const NodeIterator &i) const {return n==i.n;} bool operator!=(const NodeIterator &i) const {return n!=i.n;} - int Index() const { return n; } //If the nodes are indexable + int index() const { return n; } //If the nodes are indexable friend class Graph; friend class EdgeIterator; friend class InEdgeIterator; friend class OutEdgeIterator; friend class BiEdgeIterator; friend class SymEdgeIterator; - friend class AllEdgeIterator; + friend class EachEdgeIterator; friend class FirstAnythingTypeNode; //Nem kellene egy: @@ -96,7 +98,7 @@ //Ez csak kicsit baj, de: // Meg a From() es To() miatt!!!!!!!!!! - NEGRO::EdgePoint e; + NEGRO::EdgeIt e; public: EdgeIterator() {;} //Kell inicializalni? (Nem) @@ -104,10 +106,12 @@ // Lehet, hogy ez a ketto nem kell!!! - NodeIterator From() const {NodeIterator i;i.G=G;i.n=e->From();return i;} - NodeIterator To() const {NodeIterator i;i.G=G;i.n=e->To();return i;} + NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;} + NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;} + NodeIterator opposite(const NodeIterator &n) const + {return n==tail()?head():tail();} - bool isValid() {return e;} + bool valid() {return e;} E &operator*() const { return G->Data(e); } E *operator->() const { return &G->Data(e); } @@ -119,7 +123,7 @@ bool operator==(const EdgeIterator &i) const {return e==i.e;} bool operator!=(const EdgeIterator &i) const {return e!=i.e;} - int Index() const { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; } + int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;} //If the edges are indexable friend class Graph; @@ -127,16 +131,16 @@ friend class OutEdgeIterator; friend class BiEdgeIterator; friend class SymEdgeIterator; - friend class AllEdgeIterator; + friend class EachEdgeIterator; }; class BiEdgeIterator : public EdgeIterator { public: - BiEdgeIterator &GoNextIn() { e=e->NextIn(); return *this;} - BiEdgeIterator &GoNextOut() { e=e->NextOut(); return *this;} - BiEdgeIterator NextIn() const {return BiEdgeIterator(*this).GoNextIn();} - BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();} + BiEdgeIterator &goNextIn() { e=e->NextIn(); return *this;} + BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;} + BiEdgeIterator nextIn() const {return BiEdgeIterator(*this).goNextIn();} + BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();} operator InEdgeIterator () {InEdgeIterator i; i.G=G;i.e=e;return i;} @@ -152,7 +156,7 @@ { public: InEdgeIterator() {} - InEdgeIterator(const Graph &Gr,const NodeIterator &n) + InEdgeIterator(Graph &Gr,const NodeIterator &n) { G=&Gr; e=Gr.OldGraph::FirstIn(n.n);} InEdgeIterator &GoNext() { e=e->NextIn(); return *this;} @@ -180,14 +184,14 @@ OutEdgeIterator(Graph &Gr,const NodeIterator &n) { G=&Gr; e=Gr.OldGraph::FirstOut(n.n);} - OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;} - OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();} - OutEdgeIterator &operator++() { return GoNext();} + OutEdgeIterator &goNext() { e=e->NextOut(); return *this;} + OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();} + OutEdgeIterator &operator++() { return goNext();} OutEdgeIterator operator++(int) - {OutEdgeIterator tmp(*this); GoNext(); return tmp;} + {OutEdgeIterator tmp(*this); goNext(); return tmp;} - NodeIterator Anode() const {return From();} - NodeIterator Bnode() const {return To();} + NodeIterator aNode() const {return tail();} + NodeIterator bNode() const {return head();} operator const InEdgeIterator () {InEdgeIterator i; i.G=G;i.e=e;return i;} @@ -204,17 +208,17 @@ public: SymEdgeIterator() {} - SymEdgeIterator(const Graph &Gr,const NodeIterator &nn) - { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); } + SymEdgeIterator(Graph &Gr,const NodeIterator &nn) + { G=&Gr; n=nn; e=Gr.OldGraph::FirstEdge(nn.n); } - SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;} - SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();} - SymEdgeIterator &operator++() { return GoNext();} + SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;} + SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();} + SymEdgeIterator &operator++() { return goNext();} SymEdgeIterator operator++(int) - {SymEdgeIterator tmp(*this); GoNext(); return tmp;} + {SymEdgeIterator tmp(*this); goNext(); return tmp;} - NodeIterator Anode() const {return n;} - NodeIterator Bnode() const {return n.n==From().n?To():From();} + NodeIterator aNode() const {return n;} + NodeIterator bNode() const {return n.n==tail().n?head():tail();} operator const InEdgeIterator () {InEdgeIterator i; i.G=G;i.e=e;return i;} @@ -226,32 +230,34 @@ friend class Graph; }; - class AllEdgeIterator : public EdgeIterator + class EachEdgeIterator : public EdgeIterator { NodeIterator n; // Itt ketszer van a G public: - AllEdgeIterator() {} - AllEdgeIterator(Graph &Gr) : n(Gr) + EachEdgeIterator() {} + EachEdgeIterator(Graph &Gr) : n(Gr) { - e=n.isValid()?Gr.OldGraph::FirstOut(n.n):NULL; + e=n.valid()?Gr.OldGraph::FirstOut(n.n):NULL; } - AllEdgeIterator &GoNext() + EachEdgeIterator &goNext() { e=e->NextOut(); - if(!e && (++n).isValid()) e=G->OldGraph::FirstOut(n.n); + if(!e && (++n).valid()) e=G->OldGraph::FirstOut(n.n); return *this; } - AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();} - AllEdgeIterator &operator++() { return GoNext();} - AllEdgeIterator operator++(int) - {AllEdgeIterator tmp(*this); GoNext(); return tmp;} + EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();} + EachEdgeIterator &operator++() { return goNext();} + EachEdgeIterator operator++(int) + {EachEdgeIterator tmp(*this); goNext(); return tmp;} - NodeIterator Anode() const {return n;} - NodeIterator Bnode() const {return n.n==From().n?To():From();} + NodeIterator aNode() const {return n;} + NodeIterator bNode() const {return n.n==tail().n?head():tail();} + operator const EdgeIterator () + {EdgeIterator i; i.G=G;i.e=e;return i;} operator const InEdgeIterator () {InEdgeIterator i; i.G=G;i.e=e;return i;} operator const OutEdgeIterator () @@ -269,55 +275,55 @@ typedef InEdgeIterator DeletingInEdgeIterator; typedef SymEdgeIterator DeletingSymEdgeIterator; - const NodeIterator FirstNode() + const NodeIterator firstNode() { NodeIterator i; i.G=this;i.n=OldGraph::FirstNode(); return i; } - void GetFirst(NodePoint &p) { p=OldGraph::FirstNode(); } + void getFirst(NodeIt &p) { p=OldGraph::FirstNode(); } - void GetFirst(InEdgePoint &p,const NodePoint &n) + void getFirst(InEdgeIt &p,const NodeIt &n) { p=OldGraph::FirstIn(n); } - void GetFirst(OutEdgePoint &p,const NodePoint &n) + void getFirst(OutEdgeIt &p,const NodeIt &n) { p=OldGraph::FirstOut(n); } - void GetFirst(SymEdgePoint &p,const NodePoint &n) + void getFirst(SymEdgeIt &p,const NodeIt &n) { p=OldGraph::FirstEdge(n); } - void GetFirst(EdgePoint &p) //Vegigmegy mindenen - { p.e=NodeNum()?OldGraph::FirstOut(OldGraph::FirstNode()):NULL;} + void getFirst(EdgeIt &p) //Vegigmegy mindenen + { p.e=nodeNum()?OldGraph::FirstOut(OldGraph::FirstNode()):NULL;} - void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph::FirstNode();} + void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph::FirstNode();} - void GetFirst(InEdgeIterator &i,const NodeIterator &n) + void getFirst(InEdgeIterator &i,const NodeIterator &n) { i.G=this;i.e=OldGraph::FirstIn(n.n); } - void GetFirst(OutEdgeIterator &i,const NodeIterator &n) + void getFirst(OutEdgeIterator &i,const NodeIterator &n) { i.G=this;i.e=OldGraph::FirstOut(n.n); } - void GetFirst(SymEdgeIterator &i,const NodeIterator &n) - { i.G=this;i.e=OldGraph::FirstSym(n.n); } - void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen + void getFirst(SymEdgeIterator &i,const NodeIterator &n) + { i.G=this;i.e=OldGraph::FirstEdge(n.n); } + void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen { i.G=this; - GetFirst(i.n); + getFirst(i.n); i.e=OldGraph::NodeNum()?OldGraph::FirstOut(i.n.n):NULL; } //Vagy beginnode()? - const DeletingEdgeIterator FirstOut(const NodeIterator &n) + const DeletingEdgeIterator firstOut(const NodeIterator &n) { EdgeIterator i; i.G=n.G;i.edge=n.G->OldGraph::FirstOut(n.n); return i; } - const DeletingEdgeIterator FirstIn(const NodeIterator &n) + const DeletingEdgeIterator firstIn(const NodeIterator &n) { EdgeIterator i; i.G=n.G;i.edge=n.G->OldGraph::FirstIn(n.n); return i; } - const DeletingSymEdgeIterator FirstSym(const NodeIterator &n) + const DeletingSymEdgeIterator firstSym(const NodeIterator &n) { EdgeIterator i; i.G=n.G;i.n=n.n; @@ -341,12 +347,12 @@ operator const SymEdgeIterator () const {SymEdgeIterator i; n.G->GetFirst(i,n);return i;} - operator const InEdgePoint () const - {InEdgePoint i; n.G->GetFirst(i,n);return i;} - operator const OutEdgePoint () const - {OutEdgePoint i; n.G->GetFirst(i,n);return i;} - operator const SymEdgePoint () const - {SymEdgePoint i; n.G->GetFirst(i,n);return i;} + operator const InEdgeIt () const + {InEdgeIt i; n.G->GetFirst(i,n);return i;} + operator const OutEdgeIt () const + {OutEdgeIt i; n.G->GetFirst(i,n);return i;} + operator const SymEdgeIt () const + {SymEdgeIt i; n.G->GetFirst(i,n);return i;} }; class FirstAnythingType @@ -355,31 +361,31 @@ public: FirstAnythingType(Graph *gg) : G(gg) {} - operator const AllEdgeIterator () const - {AllEdgeIterator i; G->GetFirst(i);return i;} - operator const EdgePoint () const - {EdgePoint i; G->GetFirst(i);return i;} + operator const EachEdgeIterator () const + {EachEdgeIterator i; G->GetFirst(i);return i;} + operator const EdgeIt () const + {EdgeIt i; G->GetFirst(i);return i;} operator const NodeIterator () const {NodeIterator i; G->GetFirst(i);return i;} - operator const NodePoint () const - {NodePoint i; G->GetFirst(i);return i;} + operator const NodeIt () const + {NodeIt i; G->GetFirst(i);return i;} } _FST; // const NodeIterator First() {NodeIterator i;GetFirst(i); return i;} - FirstAnythingTypeNode First(NodeIterator &i) + FirstAnythingTypeNode first(NodeIterator &i) {FirstAnythingTypeNode t(i); return t;} - const FirstAnythingType &First() {return _FST;} + const FirstAnythingType &first() {return _FST;} // LastNode() vagy endnode() stb. Nem kell? - DeletingNodeIterator AddNode() + DeletingNodeIterator addNode() { DeletingNodeIterator i; i.G=this; i.n=OldGraph::AddNode(); return i; } DeletingEdgeIterator - AddEdge(const NodeIterator from,const NodeIterator to) + addEdge(const NodeIterator from,const NodeIterator to) { DeletingEdgeIterator i; i.G=this;i.e=OldGraph::AddEdge(from.n,to.n);return i; @@ -388,8 +394,8 @@ void Delete(DeletingNodeIterator n) {n.G->OldGraph::Delete(n.n);} void Delete(DeletingEdgeIterator e) {e.G->OldGraph::Delete(e.e);} - int NodeNum() { OldGraph::NodeNum(); } - void Clean() { OldGraph::Clean(); } + int nodeNum() { OldGraph::NodeNum(); } + void clean() { OldGraph::Clean(); } Graph() : _FST(this) {} @@ -401,14 +407,14 @@ public: typedef T value_type; - void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;} - T Get(const NodeIterator i) const {return map[i.Index()];} + void put(const NodeIterator i, const T &t) {map[i.Index()]=t;} + T get(const NodeIterator i) const {return map[i.Index()];} T operator[](NodeIterator i) {return map[i.Index()];} void update() { map.resize(G->MaxNode());} NodeMap() {} - void SetG(Graph &Gr) { G=&Gr; update();} + void setG(Graph &Gr) { G=&Gr; update();} }; template class EdgeMap @@ -418,32 +424,70 @@ public: typedef T value_type; - void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;} - T &Get(const NodeIterator i) {return map[i.Index()];} - T &operator[](NodeIterator i) {return map[i.Index()];} + void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;} + T get(const EdgeIterator i) const {return map[i.Index()];} + T &operator[](EdgeIterator i) {return map[i.Index()];} void update() { map.resize(G->MaxEdge());} EdgeMap() {} - void SetG(Graph &Gr) + void setG(Graph &Gr) { G=&Gr ;update();} }; - int MaxNode() { return OldGraph::MaxNode();} - int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;} + int maxNode() { return OldGraph::MaxNode();} + int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;} }; + template //G is a graph-type + class Path + { + public: + typedef G Graph; + typedef typename G::NodeIterator NodeIterator; + typedef typename G::EdgeIterator EdgeIterator; + typedef typename G::SymEdgeIterator SymEdgeIterator; + + private: + std::vector path; + std::vector reversed; + + public: + void setLength(int n) { path.resize(n);reversed.resize(n);} + int getLength() { return path.size(); } + EdgeIterator &operator[](int n) {return path[n];} + NodeIterator GetNode(int n) // What about path of length 1? + { + return n? + reversed[n-1]?path[n-1].tail():path[n-1].head(): + reversed[0]?path[0].head():path[0].tail(); + } + void setRevert(int n,bool r=true) {reversed[n]=r;} + void setEdge(int n,SymEdgeIterator i) + { + path[n]=i; + reversed[n] = i.head()==i.aNode(); + } + void setEdge(int n,EdgeIterator i,bool r) + { + path[n]=i; + reversed[n] = r; + } + + NodeIterator tail() { return getNode(0); } + NodeIterator head() { return getNode(getLength()); } + }; + /* Ez itt a fiam kommentje: +class SymGraphWrapper +{ + G *graph; + +public: + typedef G BaseGraph; + + typedef typename G::EdgeIt EdgeIt; + + typedef typename G::InEdgeIt SymEdgeIt; + typedef typename G::OutEdgeIt SymEdgeIt; + typedef typename G::SymEdgeIt SymEdgeIt; + typedef typename G::EachEdgeIt EachEdgeIt; + + typedef typename G::NodeIt NodeIt; + + template I &getFirst(I &i); { return graph->getFirst(i); } + template I &getFirst(I &i,const P &p); + { return graph->getFirst(i,p); } + template I next(const I i); { return graph->goNext(i); } + template I &goNext(I &i); { return graph->goNext(i); } + + NodeIt head(const EdgeIt &e); + { return graph->head(e); } + NodeIt tail(const EdgeIt &e); + { return graph->tail(e); } + + template NodeIt aNode(const I e); + { return graph->aNode(e); } + template NodeIt bNode(const I e); + { return graph->bNode(e); } + + template bool valid(const I i); + { return graph->valid(i); } + + template void setInvalid(const I &i); + { return graph->setInvalid(i); } + + NodeIt addNode(); { return graph->addNode(); } + EdgeIt addEdge(const NodeIt from,const NodeIt to); + { return graph->addEdge(to,from); } + + template void delete(I i); { graph->delete(i); } + + void clean(); { graph->clean(); } + + template class NodeMap : public typename G::NodeMap; + template class EdgeMap : public typename G::EdgeMap; + + void SetG(G &g) {graph = &g;} + + RevGraphWrapper() {graph = NULL;} + RevGraphWrapper(G &g) {graph = &g;} +}; + + +// FIXME: comparison should be made better!!! +template +class ResGraphWrapper +{ + G *graph; + +public: + typedef G BaseGraph; + + typedef typename G::EdgeIt EdgeIt; + + class InEdgeIt + { + public: + G::NodeIt n; + G::InEdgeIt i; + G::OutEdgeIt o; + } + class OutEdgeIt + { + public: + G::NodeIt n; + G::InEdgeIt i; + G::OutEdgeIt o; + } + typedef typename G::SymEdgeIt SymEdgeIt; + typedef typename G::EachEdgeIt EachEdgeIt; + + typedef typename G::NodeIt NodeIt; + + NodeIt &getFirst(NodeIt &n); { return graph->getFirst(n); } + + // EachEdge and SymEdge is missing!!!! + // EdgeIt <-> In/OutEdgeIt conversion is missing!!!! + + InEdgeIt &getFirst(InEdgeIt &e,const NodeIt &n) + { + e.n=n; + graph->getFirst(e.i,n); + while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) + graph->goNext(e.i); + if(!graph->valid(e.i)) { + graph->getFirst(e.o,n); + while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) + graph->goNext(e.o); + } + return e; + } + InEdgeIt &goNext(InEdgeIt &e) + { + if(graph->valid(e.i)) { + while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) + graph->goNext(e.i); + if(graph->valid(e.i)) return e; + else graph->getFirst(e.o,e.n); + } + else { + while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) + graph->goNext(e.o); + return e; + } + } + InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);} + bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);} + + OutEdgeIt &getFirst(OutEdgeIt &e,const NodeIt &n) + { + e.n=n; + graph->getFirst(e.o,n); + while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) + graph->goNext(e.o); + if(!graph->valid(e.o)) { + graph->getFirst(e.i,n); + while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) + graph->goNext(e.i); + } + return e; + } + OutEdgeIt &goNext(OutEdgeIt &e) + { + if(graph->valid(e.o)) { + while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) + graph->goNext(e.o); + if(graph->valid(e.o)) return e; + else graph->getFirst(e.i,e.n); + } + else { + while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) + graph->goNext(e.i); + return e; + } + } + OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);} + bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);} + + template I &goNext(I &i); { return graph->goNext(i); } + template I next(const I i); { return graph->goNext(i); } + + NodeIt head(const EdgeIt &e); + { return graph->head(e); } + NodeIt tail(const EdgeIt &e); + { return graph->tail(e); } + + template NodeIt aNode(const I e); + { return graph->aNode(e); } + template NodeIt bNode(const I e); + { return graph->bNode(e); } + + template bool valid(const I i); + { return graph->valid(i); } + + template void setInvalid(const I &i); + { return graph->setInvalid(i); } + + NodeIt addNode(); { return graph->addNode(); } + EdgeIt addEdge(const NodeIt from,const NodeIt to); + { return graph->addEdge(to,from); } + + template void delete(I i); { graph->delete(i); } + + void clean(); { graph->clean(); } + + template class NodeMap : public typename G::NodeMap; + template class EdgeMap : public typename G::EdgeMap; + + void SetG(G &g) {graph = &g;} + + RevGraphWrapper() {graph = NULL;} + RevGraphWrapper(G &g) {graph = &g;} +}; + // NodeIt &getFirst(NodeIt &n) { return graph->getFirst(n); }