1.1 --- a/configure.ac Wed Aug 25 18:55:57 2004 +0000
1.2 +++ b/configure.ac Mon Aug 30 12:01:47 2004 +0000
1.3 @@ -1,5 +1,5 @@
1.4 dnl Process this file with autoconf to produce a configure script.
1.5 -AC_INIT([HugoLib], [0.1], [etik-ol@cs.elte.hu], [hugo])
1.6 +AC_INIT([HugoLib], [0.2], [etik-ol@cs.elte.hu], [hugo])
1.7 AC_CONFIG_AUX_DIR([config])
1.8 AM_INIT_AUTOMAKE(1.7)
1.9 AC_CONFIG_SRCDIR([src/hugo/invalid.h])
1.10 @@ -14,7 +14,7 @@
1.11 dnl Checks for libraries.
1.12
1.13 dnl Checks for header files.
1.14 -AC_CHECK_HEADERS(limits.h sys/time.h unistd.h)
1.15 +AC_CHECK_HEADERS(limits.h sys/time.h sys/times.h unistd.h)
1.16
1.17 dnl Checks for typedefs, structures, and compiler characteristics.
1.18 AC_C_CONST
2.1 --- a/doc/groups.dox Wed Aug 25 18:55:57 2004 +0000
2.2 +++ b/doc/groups.dox Mon Aug 30 12:01:47 2004 +0000
2.3 @@ -8,14 +8,14 @@
2.4 @ingroup datas
2.5 \brief Graph structures implemented in Hugo.
2.6
2.7 -Hugolib provides several data structures to meet the diversing requirements
2.8 +Hugolib provides several data structures to meet the diverging requirements
2.9 of the possible users.
2.10 In order to save on running time or on memory usage, some structures may
2.11 fail to provide
2.12 some graph features like edge or node deletion.
2.13
2.14 Hugolib also offers special graphs that cannot be used alone but only
2.15 -in conjunktion with other graph representation. The examples for this are
2.16 +in conjunction with other graph representation. The examples for this are
2.17 \ref EdgeSet, \ref NodeSet, and the large variety of graph wrappers.
2.18
2.19 You are free to use the graph structure that fit your requirements
3.1 --- a/src/benchmark/bfs-bench.cc Wed Aug 25 18:55:57 2004 +0000
3.2 +++ b/src/benchmark/bfs-bench.cc Mon Aug 30 12:01:47 2004 +0000
3.3 @@ -48,7 +48,7 @@
3.4 Node n(Q.front());
3.5 Node m;
3.6 Q.pop();
3.7 - for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
3.8 + for(OutEdgeIt e(G,n);e!=INVALID;++e)
3.9 if(!visited[m=G.head(e)]) {
3.10 Q.push(m);
3.11 visited.set(m,true);
3.12 @@ -76,7 +76,7 @@
3.13 do {
3.14 Node m;
3.15 Node n=Q[Qt++];
3.16 - for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
3.17 + for(OutEdgeIt e(G,n);e!=INVALID;++e)
3.18 if(!visited[m=G.head(e)]) {
3.19 Q[Qh++]=m;
3.20 visited.set(m,true);
3.21 @@ -91,8 +91,8 @@
3.22
3.23 int i=0;
3.24
3.25 - for(NodeIt n(G);G.valid(n);G.next(n))
3.26 - for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
3.27 + for(NodeIt n(G);n!=INVALID;++n)
3.28 + for(OutEdgeIt e(G,n);e!=INVALID;++e)
3.29 i++;
3.30 }
3.31
4.1 --- a/src/hugo/Makefile.am Wed Aug 25 18:55:57 2004 +0000
4.2 +++ b/src/hugo/Makefile.am Mon Aug 30 12:01:47 2004 +0000
4.3 @@ -1,4 +1,5 @@
4.4 pkginclude_HEADERS = \
4.5 + bfs.h \
4.6 bin_heap.h \
4.7 dijkstra.h \
4.8 dimacs.h \
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/hugo/bfs.h Mon Aug 30 12:01:47 2004 +0000
5.3 @@ -0,0 +1,298 @@
5.4 +// -*- C++ -*-
5.5 +#ifndef HUGO_BFS_H
5.6 +#define HUGO_BFS_H
5.7 +
5.8 +///\ingroup flowalgs
5.9 +///\file
5.10 +///\brief Bfs algorithm.
5.11 +///
5.12 +///\todo Revise Manual.
5.13 +
5.14 +#include <hugo/bin_heap.h>
5.15 +#include <hugo/invalid.h>
5.16 +
5.17 +namespace hugo {
5.18 +
5.19 +/// \addtogroup flowalgs
5.20 +/// @{
5.21 +
5.22 + ///%Bfs algorithm class.
5.23 +
5.24 + ///This class provides an efficient implementation of %Bfs algorithm.
5.25 + ///The edge lengths are passed to the algorithm using a
5.26 + ///\ref ReadMapSkeleton "readable map",
5.27 + ///so it is easy to change it to any kind of length.
5.28 + ///
5.29 + ///The type of the length is determined by the \c ValueType of the length map.
5.30 + ///
5.31 + ///It is also possible to change the underlying priority heap.
5.32 + ///
5.33 + ///\param GR The graph type the algorithm runs on.
5.34 + ///\param LM This read-only
5.35 + ///EdgeMap
5.36 + ///determines the
5.37 + ///lengths of the edges. It is read once for each edge, so the map
5.38 + ///may involve in relatively time consuming process to compute the edge
5.39 + ///length if it is necessary. The default map type is
5.40 + ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
5.41 + ///\param Heap The heap type used by the %Bfs
5.42 + ///algorithm. The default
5.43 + ///is using \ref BinHeap "binary heap".
5.44 + ///
5.45 + ///\author Jacint Szabo and Alpar Juttner
5.46 + ///\todo We need a typedef-names should be standardized. (-:
5.47 + ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
5.48 + ///should not be fixed. (Problematic to solve).
5.49 +
5.50 +#ifdef DOXYGEN
5.51 + template <typename GR>
5.52 +#else
5.53 + template <typename GR>
5.54 +#endif
5.55 + class Bfs{
5.56 + public:
5.57 + ///The type of the underlying graph.
5.58 + typedef GR Graph;
5.59 + typedef typename Graph::Node Node;
5.60 + typedef typename Graph::NodeIt NodeIt;
5.61 + typedef typename Graph::Edge Edge;
5.62 + typedef typename Graph::OutEdgeIt OutEdgeIt;
5.63 +
5.64 + ///\brief The type of the map that stores the last
5.65 + ///edges of the shortest paths.
5.66 + typedef typename Graph::template NodeMap<Edge> PredMap;
5.67 + ///\brief The type of the map that stores the last but one
5.68 + ///nodes of the shortest paths.
5.69 + typedef typename Graph::template NodeMap<Node> PredNodeMap;
5.70 + ///The type of the map that stores the dists of the nodes.
5.71 + typedef typename Graph::template NodeMap<int> DistMap;
5.72 +
5.73 + private:
5.74 + const Graph *G;
5.75 + PredMap *predecessor;
5.76 + bool local_predecessor;
5.77 + PredNodeMap *pred_node;
5.78 + bool local_pred_node;
5.79 + DistMap *distance;
5.80 + bool local_distance;
5.81 +
5.82 + //The source node of the last execution.
5.83 + Node source;
5.84 +
5.85 +
5.86 + ///Initialize maps.
5.87 +
5.88 + ///\todo Error if \c G or are \c NULL.
5.89 + ///\todo Better memory allocation (instead of new).
5.90 + void init_maps()
5.91 + {
5.92 +// if(!length) {
5.93 +// local_length = true;
5.94 +// length = new LM(G);
5.95 +// }
5.96 + if(!predecessor) {
5.97 + local_predecessor = true;
5.98 + predecessor = new PredMap(*G);
5.99 + }
5.100 + if(!pred_node) {
5.101 + local_pred_node = true;
5.102 + pred_node = new PredNodeMap(*G);
5.103 + }
5.104 + if(!distance) {
5.105 + local_distance = true;
5.106 + distance = new DistMap(*G);
5.107 + }
5.108 + }
5.109 +
5.110 + public :
5.111 + Bfs(const Graph& _G) :
5.112 + G(&_G),
5.113 + predecessor(NULL), local_predecessor(false),
5.114 + pred_node(NULL), local_pred_node(false),
5.115 + distance(NULL), local_distance(false)
5.116 + { }
5.117 +
5.118 + ~Bfs()
5.119 + {
5.120 + // if(local_length) delete length;
5.121 + if(local_predecessor) delete predecessor;
5.122 + if(local_pred_node) delete pred_node;
5.123 + if(local_distance) delete distance;
5.124 + }
5.125 +
5.126 + ///Sets the graph the algorithm will run on.
5.127 +
5.128 + ///Sets the graph the algorithm will run on.
5.129 + ///\return <tt> (*this) </tt>
5.130 + Bfs &setGraph(const Graph &_G)
5.131 + {
5.132 + G = &_G;
5.133 + return *this;
5.134 + }
5.135 + ///Sets the length map.
5.136 +
5.137 + ///Sets the map storing the predecessor edges.
5.138 +
5.139 + ///Sets the map storing the predecessor edges.
5.140 + ///If you don't use this function before calling \ref run(),
5.141 + ///it will allocate one. The destuctor deallocates this
5.142 + ///automatically allocated map, of course.
5.143 + ///\return <tt> (*this) </tt>
5.144 + Bfs &setPredMap(PredMap &m)
5.145 + {
5.146 + if(local_predecessor) {
5.147 + delete predecessor;
5.148 + local_predecessor=false;
5.149 + }
5.150 + predecessor = &m;
5.151 + return *this;
5.152 + }
5.153 +
5.154 + ///Sets the map storing the predecessor nodes.
5.155 +
5.156 + ///Sets the map storing the predecessor nodes.
5.157 + ///If you don't use this function before calling \ref run(),
5.158 + ///it will allocate one. The destuctor deallocates this
5.159 + ///automatically allocated map, of course.
5.160 + ///\return <tt> (*this) </tt>
5.161 + Bfs &setPredNodeMap(PredNodeMap &m)
5.162 + {
5.163 + if(local_pred_node) {
5.164 + delete pred_node;
5.165 + local_pred_node=false;
5.166 + }
5.167 + pred_node = &m;
5.168 + return *this;
5.169 + }
5.170 +
5.171 + ///Sets the map storing the distances calculated by the algorithm.
5.172 +
5.173 + ///Sets the map storing the distances calculated by the algorithm.
5.174 + ///If you don't use this function before calling \ref run(),
5.175 + ///it will allocate one. The destuctor deallocates this
5.176 + ///automatically allocated map, of course.
5.177 + ///\return <tt> (*this) </tt>
5.178 + Bfs &setDistMap(DistMap &m)
5.179 + {
5.180 + if(local_distance) {
5.181 + delete distance;
5.182 + local_distance=false;
5.183 + }
5.184 + distance = &m;
5.185 + return *this;
5.186 + }
5.187 +
5.188 + ///Runs %BFS algorithm from node \c s.
5.189 +
5.190 + ///This method runs the %BFS algorithm from a root node \c s
5.191 + ///in order to
5.192 + ///compute the
5.193 + ///shortest path to each node. The algorithm computes
5.194 + ///- The shortest path tree.
5.195 + ///- The distance of each node from the root.
5.196 +
5.197 + void run(Node s) {
5.198 +
5.199 + init_maps();
5.200 +
5.201 + source = s;
5.202 +
5.203 + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
5.204 + predecessor->set(u,INVALID);
5.205 + pred_node->set(u,INVALID);
5.206 + }
5.207 +
5.208 + int N=G->nodeNum();
5.209 + std::vector<typename Graph::Node> Q(N);
5.210 + int Qh=0;
5.211 + int Qt=0;
5.212 +
5.213 + Q[Qh++]=source;
5.214 + distance->set(s, 0);
5.215 + do {
5.216 + Node m;
5.217 + Node n=Q[Qt++];
5.218 + int d= (*distance)[n]+1;
5.219 +
5.220 + for(OutEdgeIt e(*G,n);e!=INVALID;++e)
5.221 + if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) {
5.222 + Q[Qh++]=m;
5.223 + predecessor->set(m,e);
5.224 + pred_node->set(m,n);
5.225 + distance->set(m,d);
5.226 + }
5.227 + } while(Qt!=Qh);
5.228 + }
5.229 +
5.230 + ///The distance of a node from the root.
5.231 +
5.232 + ///Returns the distance of a node from the root.
5.233 + ///\pre \ref run() must be called before using this function.
5.234 + ///\warning If node \c v in unreachable from the root the return value
5.235 + ///of this funcion is undefined.
5.236 + int dist(Node v) const { return (*distance)[v]; }
5.237 +
5.238 + ///Returns the 'previous edge' of the shortest path tree.
5.239 +
5.240 + ///For a node \c v it returns the 'previous edge' of the shortest path tree,
5.241 + ///i.e. it returns the last edge from a shortest path from the root to \c
5.242 + ///v. It is \ref INVALID
5.243 + ///if \c v is unreachable from the root or if \c v=s. The
5.244 + ///shortest path tree used here is equal to the shortest path tree used in
5.245 + ///\ref predNode(Node v). \pre \ref run() must be called before using
5.246 + ///this function.
5.247 + Edge pred(Node v) const { return (*predecessor)[v]; }
5.248 +
5.249 + ///Returns the 'previous node' of the shortest path tree.
5.250 +
5.251 + ///For a node \c v it returns the 'previous node' of the shortest path tree,
5.252 + ///i.e. it returns the last but one node from a shortest path from the
5.253 + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
5.254 + ///\c v=s. The shortest path tree used here is equal to the shortest path
5.255 + ///tree used in \ref pred(Node v). \pre \ref run() must be called before
5.256 + ///using this function.
5.257 + Node predNode(Node v) const { return (*pred_node)[v]; }
5.258 +
5.259 + ///Returns a reference to the NodeMap of distances.
5.260 +
5.261 + ///Returns a reference to the NodeMap of distances. \pre \ref run() must
5.262 + ///be called before using this function.
5.263 + const DistMap &distMap() const { return *distance;}
5.264 +
5.265 + ///Returns a reference to the shortest path tree map.
5.266 +
5.267 + ///Returns a reference to the NodeMap of the edges of the
5.268 + ///shortest path tree.
5.269 + ///\pre \ref run() must be called before using this function.
5.270 + const PredMap &predMap() const { return *predecessor;}
5.271 +
5.272 + ///Returns a reference to the map of nodes of shortest paths.
5.273 +
5.274 + ///Returns a reference to the NodeMap of the last but one nodes of the
5.275 + ///shortest path tree.
5.276 + ///\pre \ref run() must be called before using this function.
5.277 + const PredNodeMap &predNodeMap() const { return *pred_node;}
5.278 +
5.279 + ///Checks if a node is reachable from the root.
5.280 +
5.281 + ///Returns \c true if \c v is reachable from the root.
5.282 + ///\warning The root node is reported to be reached!
5.283 + ///
5.284 + ///\pre \ref run() must be called before using this function.
5.285 + ///
5.286 + bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
5.287 +
5.288 + };
5.289 +
5.290 +
5.291 + // **********************************************************************
5.292 + // IMPLEMENTATIONS
5.293 + // **********************************************************************
5.294 +
5.295 +/// @}
5.296 +
5.297 +} //END OF NAMESPACE HUGO
5.298 +
5.299 +#endif
5.300 +
5.301 +
6.1 --- a/src/hugo/dijkstra.h Wed Aug 25 18:55:57 2004 +0000
6.2 +++ b/src/hugo/dijkstra.h Mon Aug 30 12:01:47 2004 +0000
6.3 @@ -84,6 +84,9 @@
6.4 DistMap *distance;
6.5 bool local_distance;
6.6
6.7 + //The source node of the last execution.
6.8 + Node source;
6.9 +
6.10 ///Initialize maps
6.11
6.12 ///\todo Error if \c G or are \c NULL. What about \c length?
6.13 @@ -212,7 +215,9 @@
6.14
6.15 init_maps();
6.16
6.17 - for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
6.18 + source = s;
6.19 +
6.20 + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
6.21 predecessor->set(u,INVALID);
6.22 pred_node->set(u,INVALID);
6.23 }
6.24 @@ -235,8 +240,8 @@
6.25 distance->set(v, oldvalue);
6.26
6.27
6.28 - for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
6.29 - Node w=G->bNode(e);
6.30 + for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
6.31 + Node w=G->head(e);
6.32
6.33 switch(heap.state(w)) {
6.34 case HeapType::PRE_HEAP:
6.35 @@ -310,11 +315,10 @@
6.36 ///Checks if a node is reachable from the root.
6.37
6.38 ///Returns \c true if \c v is reachable from the root.
6.39 - ///\warning the root node is reported to be unreached!
6.40 - ///\todo Is this what we want?
6.41 + ///\warning the root node is reported to be reached!
6.42 ///\pre \ref run() must be called before using this function.
6.43 ///
6.44 - bool reached(Node v) { return G->valid((*predecessor)[v]); }
6.45 + bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
6.46
6.47 };
6.48
7.1 --- a/src/hugo/full_graph.h Wed Aug 25 18:55:57 2004 +0000
7.2 +++ b/src/hugo/full_graph.h Mon Aug 30 12:01:47 2004 +0000
7.3 @@ -63,12 +63,6 @@
7.4 Node tail(Edge e) const { return e.n%NodeNum; }
7.5 Node head(Edge e) const { return e.n/NodeNum; }
7.6
7.7 - Node aNode(OutEdgeIt e) const { return tail(e); }
7.8 - Node aNode(InEdgeIt e) const { return head(e); }
7.9 -
7.10 - Node bNode(OutEdgeIt e) const { return head(e); }
7.11 - Node bNode(InEdgeIt e) const { return tail(e); }
7.12 -
7.13 NodeIt& first(NodeIt& v) const {
7.14 v=NodeIt(*this); return v; }
7.15 EdgeIt& first(EdgeIt& e) const {
7.16 @@ -78,25 +72,23 @@
7.17 InEdgeIt& first(InEdgeIt& e, const Node v) const {
7.18 e=InEdgeIt(*this,v); return e; }
7.19
7.20 - static bool valid(Edge e) { return e.n!=-1; }
7.21 - static bool valid(Node n) { return n.n!=-1; }
7.22 -
7.23 - template <typename It> It getNext(It it) const
7.24 - { It tmp(it); return next(tmp); }
7.25 -
7.26 - NodeIt& next(NodeIt& it) const {
7.27 - it.n=(it.n+2)%(NodeNum+1)-1;
7.28 - return it;
7.29 - }
7.30 - OutEdgeIt& next(OutEdgeIt& it) const
7.31 - { it.n+=NodeNum; if(it.n>=EdgeNum) it.n=-1; return it; }
7.32 - InEdgeIt& next(InEdgeIt& it) const
7.33 - { if(!((++it.n)%NodeNum)) it.n=-1; return it; }
7.34 - static EdgeIt& next(EdgeIt& it) { --it.n; return it; }
7.35 -
7.36 static int id(Node v) { return v.n; }
7.37 static int id(Edge e) { return e.n; }
7.38
7.39 + /// Finds an edge between two nodes.
7.40 +
7.41 + /// Finds an edge from node \c u to node \c v.
7.42 + ///
7.43 + /// If \c prev is \ref INVALID (this is the default value), then
7.44 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
7.45 + /// the next edge from \c u to \c v after \c prev.
7.46 + /// \return The found edge or INVALID if there is no such an edge.
7.47 + Edge findEdge(Node u,Node v, Edge prev = INVALID)
7.48 + {
7.49 + return prev.n==-1?Edge(*this,u.n,v.n):INVALID;
7.50 + }
7.51 +
7.52 +
7.53 class Node {
7.54 friend class FullGraph;
7.55 template <typename T> friend class NodeMap;
7.56 @@ -119,13 +111,15 @@
7.57 };
7.58
7.59 class NodeIt : public Node {
7.60 + const FullGraph *G;
7.61 friend class FullGraph;
7.62 public:
7.63 NodeIt() : Node() { }
7.64 + NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
7.65 NodeIt(Invalid i) : Node(i) { }
7.66 - NodeIt(const FullGraph& G) : Node(G.NodeNum?0:-1) { }
7.67 + NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
7.68 ///\todo Undocumented conversion Node -\> NodeIt.
7.69 - NodeIt(const FullGraph& G, const Node &n) : Node(n) { }
7.70 + NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
7.71 };
7.72
7.73 class Edge {
7.74 @@ -138,7 +132,8 @@
7.75 int n; //NodeNum*head+tail;
7.76 friend int FullGraph::id(Edge e);
7.77
7.78 - Edge(int nn) {n=nn;}
7.79 + Edge(int nn) : n(nn) {}
7.80 + Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
7.81 public:
7.82 Edge() { }
7.83 Edge (Invalid) { n=-1; }
7.84 @@ -154,30 +149,42 @@
7.85 class EdgeIt : public Edge {
7.86 friend class FullGraph;
7.87 public:
7.88 - EdgeIt(const FullGraph& G) : Edge(G.EdgeNum-1) { }
7.89 + EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
7.90 + EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
7.91 EdgeIt (Invalid i) : Edge(i) { }
7.92 EdgeIt() : Edge() { }
7.93 + EdgeIt& operator++() { --n; return *this; }
7.94 +
7.95 ///\bug This is a workaround until somebody tells me how to
7.96 ///make class \c SymFullGraph::SymEdgeMap friend of Edge
7.97 int &idref() {return n;}
7.98 };
7.99
7.100 class OutEdgeIt : public Edge {
7.101 + const FullGraph *G;
7.102 friend class FullGraph;
7.103 public:
7.104 OutEdgeIt() : Edge() { }
7.105 + OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
7.106 OutEdgeIt (Invalid i) : Edge(i) { }
7.107
7.108 - OutEdgeIt(const FullGraph& G,const Node v)
7.109 - : Edge(v.n) {}
7.110 + OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
7.111 +
7.112 + OutEdgeIt& operator++()
7.113 + { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
7.114 +
7.115 };
7.116
7.117 class InEdgeIt : public Edge {
7.118 + const FullGraph *G;
7.119 friend class FullGraph;
7.120 public:
7.121 InEdgeIt() : Edge() { }
7.122 + InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
7.123 InEdgeIt (Invalid i) : Edge(i) { }
7.124 - InEdgeIt(const FullGraph& G,Node v) :Edge(v.n*G.NodeNum){}
7.125 + InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
7.126 + InEdgeIt& operator++()
7.127 + { if(!((++n)%G->NodeNum)) n=-1; return *this; }
7.128 };
7.129
7.130 template <typename T> class NodeMap
7.131 @@ -279,7 +286,7 @@
7.132 std::copy(m.container.begin(), m.container.end(), container.begin());
7.133 return *this;
7.134 }
7.135 -
7.136 +
7.137 void update() {}
7.138 void update(T a) {}
7.139 };
8.1 --- a/src/hugo/graph_wrapper.h Wed Aug 25 18:55:57 2004 +0000
8.2 +++ b/src/hugo/graph_wrapper.h Mon Aug 30 12:01:47 2004 +0000
8.3 @@ -12,7 +12,7 @@
8.4
8.5 #include <hugo/invalid.h>
8.6 #include <hugo/maps.h>
8.7 -//#include <iter_map.h>
8.8 +#include <iostream>
8.9
8.10 namespace hugo {
8.11
8.12 @@ -96,70 +96,97 @@
8.13 typedef Graph ParentGraph;
8.14
8.15 GraphWrapper(Graph& _graph) : graph(&_graph) { }
8.16 + GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
8.17 // Graph& getGraph() const { return *graph; }
8.18
8.19 -// typedef typename Graph::Node Node;
8.20 - class Node : public Graph::Node {
8.21 + typedef typename Graph::Node Node;
8.22 +// class Node : public Graph::Node {
8.23 +// friend class GraphWrapper<Graph>;
8.24 +// public:
8.25 +// Node() { }
8.26 +// Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
8.27 +// // /// \bug construction throughrthr multiple levels should be
8.28 +// // /// handled better
8.29 +// // Node(const typename ParentGraph::ParentGraph::Node& _n) :
8.30 +// // Graph::Node(_n) { }
8.31 +// Node(const Invalid& i) : Graph::Node(i) { }
8.32 +// };
8.33 + class NodeIt : public Node {
8.34 + const GraphWrapper<Graph>* gw;
8.35 friend class GraphWrapper<Graph>;
8.36 - public:
8.37 - Node() { }
8.38 - Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
8.39 - // /// \bug construction throughrthr multiple levels should be
8.40 - // /// handled better
8.41 - // Node(const typename ParentGraph::ParentGraph::Node& _n) :
8.42 - // Graph::Node(_n) { }
8.43 - Node(const Invalid& i) : Graph::Node(i) { }
8.44 - };
8.45 - class NodeIt {
8.46 - friend class GraphWrapper<Graph>;
8.47 - typename Graph::NodeIt n;
8.48 public:
8.49 NodeIt() { }
8.50 - NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
8.51 - NodeIt(const Invalid& i) : n(i) { }
8.52 - NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
8.53 - operator Node() const { return Node(typename Graph::Node(n)); }
8.54 + // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
8.55 + NodeIt(Invalid i) : Node(i) { }
8.56 + NodeIt(const GraphWrapper<Graph>& _gw) :
8.57 + Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
8.58 + NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
8.59 + Node(n), gw(&_gw) { }
8.60 + NodeIt& operator++() {
8.61 + *(static_cast<Node*>(this))=
8.62 + ++(typename Graph::NodeIt(*(gw->graph), *this));
8.63 + return *this;
8.64 + }
8.65 };
8.66 -// typedef typename Graph::Edge Edge;
8.67 - class Edge : public Graph::Edge {
8.68 + typedef typename Graph::Edge Edge;
8.69 +// class Edge : public Graph::Edge {
8.70 +// friend class GraphWrapper<Graph>;
8.71 +// public:
8.72 +// Edge() { }
8.73 +// Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
8.74 +// Edge(const Invalid& i) : Graph::Edge(i) { }
8.75 +// };
8.76 + class OutEdgeIt : public Edge {
8.77 + const GraphWrapper<Graph>* gw;
8.78 friend class GraphWrapper<Graph>;
8.79 - public:
8.80 - Edge() { }
8.81 - Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
8.82 - Edge(const Invalid& i) : Graph::Edge(i) { }
8.83 + public:
8.84 + OutEdgeIt() { }
8.85 + //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
8.86 + OutEdgeIt(Invalid i) : Edge(i) { }
8.87 + OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
8.88 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
8.89 + OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
8.90 + Edge(e), gw(&_gw) { }
8.91 + OutEdgeIt& operator++() {
8.92 + *(static_cast<Edge*>(this))=
8.93 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
8.94 + return *this;
8.95 + }
8.96 };
8.97 - class OutEdgeIt {
8.98 + class InEdgeIt : public Edge {
8.99 + const GraphWrapper<Graph>* gw;
8.100 friend class GraphWrapper<Graph>;
8.101 - typename Graph::OutEdgeIt e;
8.102 - public:
8.103 - OutEdgeIt() { }
8.104 - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
8.105 - OutEdgeIt(const Invalid& i) : e(i) { }
8.106 - OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
8.107 - e(*(_G.graph), typename Graph::Node(_n)) { }
8.108 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
8.109 - };
8.110 - class InEdgeIt {
8.111 - friend class GraphWrapper<Graph>;
8.112 - typename Graph::InEdgeIt e;
8.113 - public:
8.114 + public:
8.115 InEdgeIt() { }
8.116 - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
8.117 - InEdgeIt(const Invalid& i) : e(i) { }
8.118 - InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
8.119 - e(*(_G.graph), typename Graph::Node(_n)) { }
8.120 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
8.121 + //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
8.122 + InEdgeIt(Invalid i) : Edge(i) { }
8.123 + InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
8.124 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
8.125 + InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
8.126 + Edge(e), gw(&_gw) { }
8.127 + InEdgeIt& operator++() {
8.128 + *(static_cast<Edge*>(this))=
8.129 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
8.130 + return *this;
8.131 + }
8.132 };
8.133 //typedef typename Graph::SymEdgeIt SymEdgeIt;
8.134 - class EdgeIt {
8.135 + class EdgeIt : public Edge {
8.136 + const GraphWrapper<Graph>* gw;
8.137 friend class GraphWrapper<Graph>;
8.138 - typename Graph::EdgeIt e;
8.139 - public:
8.140 + public:
8.141 EdgeIt() { }
8.142 - EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
8.143 - EdgeIt(const Invalid& i) : e(i) { }
8.144 - EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
8.145 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
8.146 + //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
8.147 + EdgeIt(Invalid i) : Edge(i) { }
8.148 + EdgeIt(const GraphWrapper<Graph>& _gw) :
8.149 + Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
8.150 + EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) :
8.151 + Edge(w), gw(&_gw) { }
8.152 + EdgeIt& operator++() {
8.153 + *(static_cast<Edge*>(this))=
8.154 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
8.155 + return *this;
8.156 + }
8.157 };
8.158
8.159 NodeIt& first(NodeIt& i) const {
8.160 @@ -175,28 +202,28 @@
8.161 i=EdgeIt(*this); return i;
8.162 }
8.163
8.164 - NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
8.165 - OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
8.166 - InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
8.167 - EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
8.168 +// NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
8.169 +// OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
8.170 +// InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
8.171 +// EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
8.172
8.173 Node tail(const Edge& e) const {
8.174 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
8.175 Node head(const Edge& e) const {
8.176 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
8.177
8.178 - bool valid(const Node& n) const {
8.179 - return graph->valid(static_cast<typename Graph::Node>(n)); }
8.180 - bool valid(const Edge& e) const {
8.181 - return graph->valid(static_cast<typename Graph::Edge>(e)); }
8.182 +// bool valid(const Node& n) const {
8.183 +// return graph->valid(static_cast<typename Graph::Node>(n)); }
8.184 +// bool valid(const Edge& e) const {
8.185 +// return graph->valid(static_cast<typename Graph::Edge>(e)); }
8.186
8.187 int nodeNum() const { return graph->nodeNum(); }
8.188 int edgeNum() const { return graph->edgeNum(); }
8.189
8.190 - Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
8.191 - Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
8.192 - Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
8.193 - Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
8.194 +// Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
8.195 +// Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
8.196 +// Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
8.197 +// Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
8.198
8.199 Node addNode() const { return Node(graph->addNode()); }
8.200 Edge addEdge(const Node& tail, const Node& head) const {
8.201 @@ -218,15 +245,15 @@
8.202 template<typename T> class NodeMap : public Graph::template NodeMap<T> {
8.203 typedef typename Graph::template NodeMap<T> Parent;
8.204 public:
8.205 - NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
8.206 - NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
8.207 + NodeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }
8.208 + NodeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
8.209 };
8.210
8.211 template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
8.212 typedef typename Graph::template EdgeMap<T> Parent;
8.213 public:
8.214 - EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
8.215 - EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
8.216 + EdgeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }
8.217 + EdgeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
8.218 };
8.219 };
8.220
8.221 @@ -246,6 +273,7 @@
8.222 RevGraphWrapper() : GraphWrapper<Graph>() { }
8.223 public:
8.224 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
8.225 + RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
8.226
8.227 typedef typename GraphWrapper<Graph>::Node Node;
8.228 typedef typename GraphWrapper<Graph>::Edge Edge;
8.229 @@ -256,29 +284,39 @@
8.230 //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
8.231 //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
8.232
8.233 - class OutEdgeIt {
8.234 + class OutEdgeIt : public Edge {
8.235 + const RevGraphWrapper<Graph>* gw;
8.236 friend class GraphWrapper<Graph>;
8.237 - friend class RevGraphWrapper<Graph>;
8.238 - typename Graph::InEdgeIt e;
8.239 - public:
8.240 + public:
8.241 OutEdgeIt() { }
8.242 - OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
8.243 - OutEdgeIt(const Invalid& i) : e(i) { }
8.244 - OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
8.245 - e(*(_G.graph), typename Graph::Node(_n)) { }
8.246 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
8.247 + //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
8.248 + OutEdgeIt(Invalid i) : Edge(i) { }
8.249 + OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
8.250 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
8.251 + OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
8.252 + Edge(e), gw(&_gw) { }
8.253 + OutEdgeIt& operator++() {
8.254 + *(static_cast<Edge*>(this))=
8.255 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
8.256 + return *this;
8.257 + }
8.258 };
8.259 - class InEdgeIt {
8.260 + class InEdgeIt : public Edge {
8.261 + const RevGraphWrapper<Graph>* gw;
8.262 friend class GraphWrapper<Graph>;
8.263 - friend class RevGraphWrapper<Graph>;
8.264 - typename Graph::OutEdgeIt e;
8.265 - public:
8.266 + public:
8.267 InEdgeIt() { }
8.268 - InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
8.269 - InEdgeIt(const Invalid& i) : e(i) { }
8.270 - InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
8.271 - e(*(_G.graph), typename Graph::Node(_n)) { }
8.272 - operator Edge() const { return Edge(typename Graph::Edge(e)); }
8.273 + //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
8.274 + InEdgeIt(Invalid i) : Edge(i) { }
8.275 + InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
8.276 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
8.277 + InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
8.278 + Edge(e), gw(&_gw) { }
8.279 + InEdgeIt& operator++() {
8.280 + *(static_cast<Edge*>(this))=
8.281 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
8.282 + return *this;
8.283 + }
8.284 };
8.285
8.286 using GraphWrapper<Graph>::first;
8.287 @@ -289,18 +327,18 @@
8.288 i=InEdgeIt(*this, p); return i;
8.289 }
8.290
8.291 - using GraphWrapper<Graph>::next;
8.292 - OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
8.293 - InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
8.294 +// using GraphWrapper<Graph>::next;
8.295 +// OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
8.296 +// InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
8.297
8.298 - Node aNode(const OutEdgeIt& e) const {
8.299 - return Node(this->graph->aNode(e.e)); }
8.300 - Node aNode(const InEdgeIt& e) const {
8.301 - return Node(this->graph->aNode(e.e)); }
8.302 - Node bNode(const OutEdgeIt& e) const {
8.303 - return Node(this->graph->bNode(e.e)); }
8.304 - Node bNode(const InEdgeIt& e) const {
8.305 - return Node(this->graph->bNode(e.e)); }
8.306 +// Node aNode(const OutEdgeIt& e) const {
8.307 +// return Node(this->graph->aNode(e.e)); }
8.308 +// Node aNode(const InEdgeIt& e) const {
8.309 +// return Node(this->graph->aNode(e.e)); }
8.310 +// Node bNode(const OutEdgeIt& e) const {
8.311 +// return Node(this->graph->bNode(e.e)); }
8.312 +// Node bNode(const InEdgeIt& e) const {
8.313 +// return Node(this->graph->bNode(e.e)); }
8.314
8.315 Node tail(const Edge& e) const {
8.316 return GraphWrapper<Graph>::head(e); }
8.317 @@ -309,8 +347,6 @@
8.318
8.319 };
8.320
8.321 -
8.322 -
8.323 /// A graph wrapper for hiding nodes and edges from a graph.
8.324
8.325 /// This wrapper shows a graph with filtered node-set and
8.326 @@ -626,9 +662,6 @@
8.327 public:
8.328 typedef GraphWrapper<Graph> Parent;
8.329 protected:
8.330 - //const CapacityMap* capacity;
8.331 - //FlowMap* flow;
8.332 -
8.333 ForwardFilterMap* forward_filter;
8.334 BackwardFilterMap* backward_filter;
8.335
8.336 @@ -647,6 +680,11 @@
8.337 BackwardFilterMap& _backward_filter) :
8.338 GraphWrapper<Graph>(_graph),
8.339 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
8.340 + SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
8.341 + ForwardFilterMap, BackwardFilterMap>& gw) :
8.342 + Parent(gw),
8.343 + forward_filter(gw.forward_filter),
8.344 + backward_filter(gw.backward_filter) { }
8.345
8.346 class Edge;
8.347 class OutEdgeIt;
8.348 @@ -657,8 +695,9 @@
8.349 template<typename T> class EdgeMap;
8.350
8.351 typedef typename GraphWrapper<Graph>::Node Node;
8.352 - typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
8.353 + //typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
8.354
8.355 + typedef typename Graph::Edge GraphEdge;
8.356 class Edge : public Graph::Edge {
8.357 friend class SubBidirGraphWrapper<Graph,
8.358 ForwardFilterMap, BackwardFilterMap>;
8.359 @@ -671,116 +710,196 @@
8.360 public:
8.361 Edge() { }
8.362 ///\bug =false kell-e? zsoltnak kell az addEdge miatt
8.363 - Edge(const typename Graph::Edge& _e, bool _backward=false) :
8.364 - Graph::Edge(_e), backward(_backward) { }
8.365 - Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
8.366 + Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
8.367 + Graph::Edge(e), backward(_backward) { }
8.368 + Edge(Invalid i) : Graph::Edge(i), backward(true) { }
8.369 //the unique invalid iterator
8.370 - friend bool operator==(const Edge& u, const Edge& v) {
8.371 - return (v.backward==u.backward &&
8.372 - static_cast<typename Graph::Edge>(u)==
8.373 +// friend bool operator==(const Edge& u, const Edge& v) {
8.374 +// return (u.backward==v.backward &&
8.375 +// static_cast<typename Graph::Edge>(u)==
8.376 +// static_cast<typename Graph::Edge>(v));
8.377 +// }
8.378 +// friend bool operator!=(const Edge& u, const Edge& v) {
8.379 +// return (u.backward!=v.backward ||
8.380 +// static_cast<typename Graph::Edge>(u)!=
8.381 +// static_cast<typename Graph::Edge>(v));
8.382 +// }
8.383 + bool operator==(const Edge& v) const {
8.384 + return (this->backward==v.backward &&
8.385 + static_cast<typename Graph::Edge>(*this)==
8.386 static_cast<typename Graph::Edge>(v));
8.387 }
8.388 - friend bool operator!=(const Edge& u, const Edge& v) {
8.389 - return (v.backward!=u.backward ||
8.390 - static_cast<typename Graph::Edge>(u)!=
8.391 + bool operator!=(const Edge& v) const {
8.392 + return (this->backward!=v.backward ||
8.393 + static_cast<typename Graph::Edge>(*this)!=
8.394 static_cast<typename Graph::Edge>(v));
8.395 - }
8.396 + }
8.397 };
8.398
8.399 - class OutEdgeIt {
8.400 + class OutEdgeIt : public Edge {
8.401 friend class SubBidirGraphWrapper<Graph,
8.402 ForwardFilterMap, BackwardFilterMap>;
8.403 protected:
8.404 - typename Graph::OutEdgeIt out;
8.405 - typename Graph::InEdgeIt in;
8.406 - bool backward;
8.407 + const SubBidirGraphWrapper<Graph,
8.408 + ForwardFilterMap, BackwardFilterMap>* gw;
8.409 public:
8.410 OutEdgeIt() { }
8.411 - //FIXME
8.412 -// OutEdgeIt(const Edge& e) : Edge(e) { }
8.413 - OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
8.414 + OutEdgeIt(Invalid i) : Edge(i) { }
8.415 //the unique invalid iterator
8.416 OutEdgeIt(const SubBidirGraphWrapper<Graph,
8.417 - ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
8.418 - backward=false;
8.419 - _G.graph->first(out, v);
8.420 - while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); }
8.421 - if (!_G.graph->valid(out)) {
8.422 - backward=true;
8.423 - _G.graph->first(in, v);
8.424 - while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }
8.425 + ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
8.426 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
8.427 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.428 + !(*(gw->forward_filter))[*this])
8.429 + *(static_cast<GraphEdge*>(this))=
8.430 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
8.431 + if (*static_cast<GraphEdge*>(this)==INVALID)
8.432 + *static_cast<Edge*>(this)=
8.433 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
8.434 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.435 + !(*(gw->backward_filter))[*this])
8.436 + *(static_cast<GraphEdge*>(this))=
8.437 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
8.438 + }
8.439 + OutEdgeIt(const SubBidirGraphWrapper<Graph,
8.440 + ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
8.441 + Edge(e), gw(&_gw) { }
8.442 + OutEdgeIt& operator++() {
8.443 + if (!this->backward) {
8.444 + Node n=gw->tail(*this);
8.445 + *(static_cast<GraphEdge*>(this))=
8.446 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
8.447 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.448 + !(*(gw->forward_filter))[*this])
8.449 + *(static_cast<GraphEdge*>(this))=
8.450 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
8.451 + if (*static_cast<GraphEdge*>(this)==INVALID)
8.452 + *static_cast<Edge*>(this)=
8.453 + Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
8.454 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.455 + !(*(gw->backward_filter))[*this])
8.456 + *(static_cast<GraphEdge*>(this))=
8.457 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
8.458 + } else {
8.459 + *(static_cast<GraphEdge*>(this))=
8.460 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
8.461 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.462 + !(*(gw->backward_filter))[*this])
8.463 + *(static_cast<GraphEdge*>(this))=
8.464 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
8.465 }
8.466 - }
8.467 - operator Edge() const {
8.468 -// Edge e;
8.469 -// e.forward=this->forward;
8.470 -// if (this->forward) e=out; else e=in;
8.471 -// return e;
8.472 - if (this->backward)
8.473 - return Edge(in, this->backward);
8.474 - else
8.475 - return Edge(out, this->backward);
8.476 + return *this;
8.477 }
8.478 };
8.479
8.480 - class InEdgeIt {
8.481 + class InEdgeIt : public Edge {
8.482 friend class SubBidirGraphWrapper<Graph,
8.483 ForwardFilterMap, BackwardFilterMap>;
8.484 protected:
8.485 - typename Graph::OutEdgeIt out;
8.486 - typename Graph::InEdgeIt in;
8.487 - bool backward;
8.488 + const SubBidirGraphWrapper<Graph,
8.489 + ForwardFilterMap, BackwardFilterMap>* gw;
8.490 public:
8.491 InEdgeIt() { }
8.492 - //FIXME
8.493 -// OutEdgeIt(const Edge& e) : Edge(e) { }
8.494 - InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
8.495 + InEdgeIt(Invalid i) : Edge(i) { }
8.496 //the unique invalid iterator
8.497 InEdgeIt(const SubBidirGraphWrapper<Graph,
8.498 - ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
8.499 - backward=false;
8.500 - _G.graph->first(in, v);
8.501 - while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); }
8.502 - if (!_G.graph->valid(in)) {
8.503 - backward=true;
8.504 - _G.graph->first(out, v);
8.505 - while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }
8.506 + ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
8.507 + Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
8.508 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.509 + !(*(gw->forward_filter))[*this])
8.510 + *(static_cast<GraphEdge*>(this))=
8.511 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
8.512 + if (*static_cast<GraphEdge*>(this)==INVALID)
8.513 + *static_cast<Edge*>(this)=
8.514 + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
8.515 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.516 + !(*(gw->backward_filter))[*this])
8.517 + *(static_cast<GraphEdge*>(this))=
8.518 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
8.519 + }
8.520 + InEdgeIt(const SubBidirGraphWrapper<Graph,
8.521 + ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
8.522 + Edge(e), gw(&_gw) { }
8.523 + InEdgeIt& operator++() {
8.524 + if (!this->backward) {
8.525 + Node n=gw->head(*this);
8.526 + *(static_cast<GraphEdge*>(this))=
8.527 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
8.528 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.529 + !(*(gw->forward_filter))[*this])
8.530 + *(static_cast<GraphEdge*>(this))=
8.531 + ++(typename Graph::InEdgeIt(*(gw->graph), *this));
8.532 + if (*static_cast<GraphEdge*>(this)==INVALID)
8.533 + *static_cast<Edge*>(this)=
8.534 + Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
8.535 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.536 + !(*(gw->backward_filter))[*this])
8.537 + *(static_cast<GraphEdge*>(this))=
8.538 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
8.539 + } else {
8.540 + *(static_cast<GraphEdge*>(this))=
8.541 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
8.542 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.543 + !(*(gw->backward_filter))[*this])
8.544 + *(static_cast<GraphEdge*>(this))=
8.545 + ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
8.546 }
8.547 - }
8.548 - operator Edge() const {
8.549 -// Edge e;
8.550 -// e.forward=this->forward;
8.551 -// if (this->forward) e=out; else e=in;
8.552 -// return e;
8.553 - if (this->backward)
8.554 - return Edge(out, this->backward);
8.555 - else
8.556 - return Edge(in, this->backward);
8.557 + return *this;
8.558 }
8.559 };
8.560
8.561 - class EdgeIt {
8.562 + class EdgeIt : public Edge {
8.563 friend class SubBidirGraphWrapper<Graph,
8.564 ForwardFilterMap, BackwardFilterMap>;
8.565 protected:
8.566 - typename Graph::EdgeIt e;
8.567 - bool backward;
8.568 + const SubBidirGraphWrapper<Graph,
8.569 + ForwardFilterMap, BackwardFilterMap>* gw;
8.570 public:
8.571 EdgeIt() { }
8.572 - EdgeIt(const Invalid& i) : e(i), backward(true) { }
8.573 + EdgeIt(Invalid i) : Edge(i) { }
8.574 +//the unique invalid iterator
8.575 EdgeIt(const SubBidirGraphWrapper<Graph,
8.576 - ForwardFilterMap, BackwardFilterMap>& _G) {
8.577 - backward=false;
8.578 - _G.graph->first(e);
8.579 - while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e);
8.580 - if (!_G.graph->valid(e)) {
8.581 - backward=true;
8.582 - _G.graph->first(e);
8.583 - while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);
8.584 + ForwardFilterMap, BackwardFilterMap>& _gw) :
8.585 + Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
8.586 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.587 + !(*(gw->forward_filter))[*this])
8.588 + *(static_cast<GraphEdge*>(this))=
8.589 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
8.590 + if (*static_cast<GraphEdge*>(this)==INVALID)
8.591 + *static_cast<Edge*>(this)=
8.592 + Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
8.593 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.594 + !(*(gw->backward_filter))[*this])
8.595 + *(static_cast<GraphEdge*>(this))=
8.596 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
8.597 + }
8.598 + EdgeIt(const SubBidirGraphWrapper<Graph,
8.599 + ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
8.600 + Edge(e), gw(&_gw) { }
8.601 + EdgeIt& operator++() {
8.602 + if (!this->backward) {
8.603 + *(static_cast<GraphEdge*>(this))=
8.604 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
8.605 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.606 + !(*(gw->forward_filter))[*this])
8.607 + *(static_cast<GraphEdge*>(this))=
8.608 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
8.609 + if (*static_cast<GraphEdge*>(this)==INVALID)
8.610 + *static_cast<Edge*>(this)=
8.611 + Edge(typename Graph::EdgeIt(*(gw->graph)), true);
8.612 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.613 + !(*(gw->backward_filter))[*this])
8.614 + *(static_cast<GraphEdge*>(this))=
8.615 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
8.616 + } else {
8.617 + *(static_cast<GraphEdge*>(this))=
8.618 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
8.619 + while (*static_cast<GraphEdge*>(this)!=INVALID &&
8.620 + !(*(gw->backward_filter))[*this])
8.621 + *(static_cast<GraphEdge*>(this))=
8.622 + ++(typename Graph::EdgeIt(*(gw->graph), *this));
8.623 }
8.624 - }
8.625 - operator Edge() const {
8.626 - return Edge(e, this->backward);
8.627 + return *this;
8.628 }
8.629 };
8.630
8.631 @@ -799,84 +918,84 @@
8.632 i=EdgeIt(*this); return i;
8.633 }
8.634
8.635 - using GraphWrapper<Graph>::next;
8.636 -// NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
8.637 - OutEdgeIt& next(OutEdgeIt& e) const {
8.638 - if (!e.backward) {
8.639 - Node v=this->graph->aNode(e.out);
8.640 - this->graph->next(e.out);
8.641 - while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
8.642 - this->graph->next(e.out); }
8.643 - if (!this->graph->valid(e.out)) {
8.644 - e.backward=true;
8.645 - this->graph->first(e.in, v);
8.646 - while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
8.647 - this->graph->next(e.in); }
8.648 - }
8.649 - } else {
8.650 - this->graph->next(e.in);
8.651 - while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
8.652 - this->graph->next(e.in); }
8.653 - }
8.654 - return e;
8.655 - }
8.656 -// FIXME Not tested
8.657 - InEdgeIt& next(InEdgeIt& e) const {
8.658 - if (!e.backward) {
8.659 - Node v=this->graph->aNode(e.in);
8.660 - this->graph->next(e.in);
8.661 - while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
8.662 - this->graph->next(e.in); }
8.663 - if (!this->graph->valid(e.in)) {
8.664 - e.backward=true;
8.665 - this->graph->first(e.out, v);
8.666 - while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
8.667 - this->graph->next(e.out); }
8.668 - }
8.669 - } else {
8.670 - this->graph->next(e.out);
8.671 - while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
8.672 - this->graph->next(e.out); }
8.673 - }
8.674 - return e;
8.675 - }
8.676 - EdgeIt& next(EdgeIt& e) const {
8.677 - if (!e.backward) {
8.678 - this->graph->next(e.e);
8.679 - while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
8.680 - this->graph->next(e.e); }
8.681 - if (!this->graph->valid(e.e)) {
8.682 - e.backward=true;
8.683 - this->graph->first(e.e);
8.684 - while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
8.685 - this->graph->next(e.e); }
8.686 - }
8.687 - } else {
8.688 - this->graph->next(e.e);
8.689 - while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
8.690 - this->graph->next(e.e); }
8.691 - }
8.692 - return e;
8.693 - }
8.694 +// using GraphWrapper<Graph>::next;
8.695 +// // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
8.696 +// OutEdgeIt& next(OutEdgeIt& e) const {
8.697 +// if (!e.backward) {
8.698 +// Node v=this->graph->aNode(e.out);
8.699 +// this->graph->next(e.out);
8.700 +// while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
8.701 +// this->graph->next(e.out); }
8.702 +// if (!this->graph->valid(e.out)) {
8.703 +// e.backward=true;
8.704 +// this->graph->first(e.in, v);
8.705 +// while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
8.706 +// this->graph->next(e.in); }
8.707 +// }
8.708 +// } else {
8.709 +// this->graph->next(e.in);
8.710 +// while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
8.711 +// this->graph->next(e.in); }
8.712 +// }
8.713 +// return e;
8.714 +// }
8.715 +// // FIXME Not tested
8.716 +// InEdgeIt& next(InEdgeIt& e) const {
8.717 +// if (!e.backward) {
8.718 +// Node v=this->graph->aNode(e.in);
8.719 +// this->graph->next(e.in);
8.720 +// while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
8.721 +// this->graph->next(e.in); }
8.722 +// if (!this->graph->valid(e.in)) {
8.723 +// e.backward=true;
8.724 +// this->graph->first(e.out, v);
8.725 +// while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
8.726 +// this->graph->next(e.out); }
8.727 +// }
8.728 +// } else {
8.729 +// this->graph->next(e.out);
8.730 +// while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
8.731 +// this->graph->next(e.out); }
8.732 +// }
8.733 +// return e;
8.734 +// }
8.735 +// EdgeIt& next(EdgeIt& e) const {
8.736 +// if (!e.backward) {
8.737 +// this->graph->next(e.e);
8.738 +// while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
8.739 +// this->graph->next(e.e); }
8.740 +// if (!this->graph->valid(e.e)) {
8.741 +// e.backward=true;
8.742 +// this->graph->first(e.e);
8.743 +// while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
8.744 +// this->graph->next(e.e); }
8.745 +// }
8.746 +// } else {
8.747 +// this->graph->next(e.e);
8.748 +// while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
8.749 +// this->graph->next(e.e); }
8.750 +// }
8.751 +// return e;
8.752 +// }
8.753
8.754 Node tail(Edge e) const {
8.755 return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
8.756 Node head(Edge e) const {
8.757 return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
8.758
8.759 - Node aNode(OutEdgeIt e) const {
8.760 - return ((!e.backward) ? this->graph->aNode(e.out) :
8.761 - this->graph->aNode(e.in)); }
8.762 - Node bNode(OutEdgeIt e) const {
8.763 - return ((!e.backward) ? this->graph->bNode(e.out) :
8.764 - this->graph->bNode(e.in)); }
8.765 +// Node aNode(OutEdgeIt e) const {
8.766 +// return ((!e.backward) ? this->graph->aNode(e.out) :
8.767 +// this->graph->aNode(e.in)); }
8.768 +// Node bNode(OutEdgeIt e) const {
8.769 +// return ((!e.backward) ? this->graph->bNode(e.out) :
8.770 +// this->graph->bNode(e.in)); }
8.771
8.772 - Node aNode(InEdgeIt e) const {
8.773 - return ((!e.backward) ? this->graph->aNode(e.in) :
8.774 - this->graph->aNode(e.out)); }
8.775 - Node bNode(InEdgeIt e) const {
8.776 - return ((!e.backward) ? this->graph->bNode(e.in) :
8.777 - this->graph->bNode(e.out)); }
8.778 +// Node aNode(InEdgeIt e) const {
8.779 +// return ((!e.backward) ? this->graph->aNode(e.in) :
8.780 +// this->graph->aNode(e.out)); }
8.781 +// Node bNode(InEdgeIt e) const {
8.782 +// return ((!e.backward) ? this->graph->bNode(e.in) :
8.783 +// this->graph->bNode(e.out)); }
8.784
8.785 /// Gives back the opposite edge.
8.786 Edge opposite(const Edge& e) const {
8.787 @@ -893,11 +1012,11 @@
8.788
8.789 // int id(Node v) const { return graph->id(v); }
8.790
8.791 - bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
8.792 - bool valid(Edge e) const {
8.793 - return this->graph->valid(e);
8.794 - //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
8.795 - }
8.796 +// bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
8.797 +// bool valid(Edge e) const {
8.798 +// return this->graph->valid(e);
8.799 +// //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
8.800 +// }
8.801
8.802 bool forward(const Edge& e) const { return !e.backward; }
8.803 bool backward(const Edge& e) const { return e.backward; }
8.804 @@ -939,11 +1058,11 @@
8.805 typedef T ValueType;
8.806 typedef Edge KeyType;
8.807 EdgeMap(const SubBidirGraphWrapper<Graph,
8.808 - ForwardFilterMap, BackwardFilterMap>& _G) :
8.809 - forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
8.810 + ForwardFilterMap, BackwardFilterMap>& g) :
8.811 + forward_map(*(g.graph)), backward_map(*(g.graph)) { }
8.812 EdgeMap(const SubBidirGraphWrapper<Graph,
8.813 - ForwardFilterMap, BackwardFilterMap>& _G, T a) :
8.814 - forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
8.815 + ForwardFilterMap, BackwardFilterMap>& g, T a) :
8.816 + forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
8.817 void set(Edge e, T a) {
8.818 if (!e.backward)
8.819 forward_map.set(e/*.out*/, a);
9.1 --- a/src/hugo/list_graph.h Wed Aug 25 18:55:57 2004 +0000
9.2 +++ b/src/hugo/list_graph.h Mon Aug 30 12:01:47 2004 +0000
9.3 @@ -131,12 +131,6 @@
9.4 Node tail(Edge e) const { return edges[e.n].tail; }
9.5 Node head(Edge e) const { return edges[e.n].head; }
9.6
9.7 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
9.8 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
9.9 -
9.10 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
9.11 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
9.12 -
9.13 NodeIt& first(NodeIt& v) const {
9.14 v=NodeIt(*this); return v; }
9.15 EdgeIt& first(EdgeIt& e) const {
9.16 @@ -146,43 +140,6 @@
9.17 InEdgeIt& first(InEdgeIt& e, const Node v) const {
9.18 e=InEdgeIt(*this,v); return e; }
9.19
9.20 -// template< typename It >
9.21 -// It first() const { It e; first(e); return e; }
9.22 -
9.23 -// template< typename It >
9.24 -// It first(Node v) const { It e; first(e,v); return e; }
9.25 -
9.26 - static bool valid(Edge e) { return e.n!=-1; }
9.27 - static bool valid(Node n) { return n.n!=-1; }
9.28 -
9.29 - static void setInvalid(Edge &e) { e.n=-1; }
9.30 - static void setInvalid(Node &n) { n.n=-1; }
9.31 -
9.32 - template <typename It> static It getNext(It it)
9.33 - { It tmp(it); return next(tmp); }
9.34 -
9.35 - NodeIt& next(NodeIt& it) const {
9.36 - it.n=nodes[it.n].next;
9.37 - return it;
9.38 - }
9.39 - OutEdgeIt& next(OutEdgeIt& it) const
9.40 - { it.n=edges[it.n].next_out; return it; }
9.41 - InEdgeIt& next(InEdgeIt& it) const
9.42 - { it.n=edges[it.n].next_in; return it; }
9.43 - EdgeIt& next(EdgeIt& it) const {
9.44 - if(edges[it.n].next_in!=-1) {
9.45 - it.n=edges[it.n].next_in;
9.46 - }
9.47 - else {
9.48 - int n;
9.49 - for(n=nodes[edges[it.n].head].next;
9.50 - n!=-1 && nodes[n].first_in == -1;
9.51 - n = nodes[n].next) ;
9.52 - it.n = (n==-1)?-1:nodes[n].first_in;
9.53 - }
9.54 - return it;
9.55 - }
9.56 -
9.57 static int id(Node v) { return v.n; }
9.58 static int id(Edge e) { return e.n; }
9.59
9.60 @@ -250,7 +207,23 @@
9.61
9.62 return e;
9.63 }
9.64 +
9.65 + /// Finds an edge between two nodes.
9.66
9.67 + /// Finds an edge from node \c u to node \c v.
9.68 + ///
9.69 + /// If \c prev is \ref INVALID (this is the default value), then
9.70 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
9.71 + /// the next edge from \c u to \c v after \c prev.
9.72 + /// \return The found edge or INVALID if there is no such an edge.
9.73 + Edge findEdge(Node u,Node v, Edge prev = INVALID)
9.74 + {
9.75 + int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
9.76 + while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
9.77 + prev.n=e;
9.78 + return prev;
9.79 + }
9.80 +
9.81 private:
9.82 void eraseEdge(int n) {
9.83
9.84 @@ -324,16 +297,25 @@
9.85 bool operator==(const Node i) const {return n==i.n;}
9.86 bool operator!=(const Node i) const {return n!=i.n;}
9.87 bool operator<(const Node i) const {return n<i.n;}
9.88 + // ///Validity check
9.89 + // operator bool() { return n!=-1; }
9.90 };
9.91
9.92 class NodeIt : public Node {
9.93 + const ListGraph *G;
9.94 friend class ListGraph;
9.95 public:
9.96 NodeIt() : Node() { }
9.97 NodeIt(Invalid i) : Node(i) { }
9.98 - NodeIt(const ListGraph& G) : Node(G.first_node) { }
9.99 + NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
9.100 ///\todo Undocumented conversion Node -\> NodeIt.
9.101 - NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
9.102 + NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
9.103 + NodeIt &operator++() {
9.104 + n=G->nodes[n].next;
9.105 + return *this;
9.106 + }
9.107 + // ///Validity check
9.108 + // operator bool() { return Node::operator bool(); }
9.109 };
9.110
9.111 class Edge {
9.112 @@ -364,41 +346,69 @@
9.113 ///\bug This is a workaround until somebody tells me how to
9.114 ///make class \c SymListGraph::SymEdgeMap friend of Edge
9.115 int &idref() {return n;}
9.116 - const int &idref() const {return n;}
9.117 - };
9.118 + const int &idref() const {return n;}
9.119 + // ///Validity check
9.120 + // operator bool() { return n!=-1; }
9.121 + };
9.122
9.123 class EdgeIt : public Edge {
9.124 + const ListGraph *G;
9.125 friend class ListGraph;
9.126 public:
9.127 - EdgeIt(const ListGraph& G) : Edge() {
9.128 + EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
9.129 int m;
9.130 - for(m=G.first_node;
9.131 - m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
9.132 - n = (m==-1)?-1:G.nodes[m].first_in;
9.133 + for(m=_G.first_node;
9.134 + m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
9.135 + n = (m==-1)?-1:_G.nodes[m].first_in;
9.136 }
9.137 EdgeIt (Invalid i) : Edge(i) { }
9.138 + EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
9.139 EdgeIt() : Edge() { }
9.140 ///\bug This is a workaround until somebody tells me how to
9.141 ///make class \c SymListGraph::SymEdgeMap friend of Edge
9.142 int &idref() {return n;}
9.143 + EdgeIt &operator++() {
9.144 + if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
9.145 + else {
9.146 + int nn;
9.147 + for(nn=G->nodes[G->edges[n].head].next;
9.148 + nn!=-1 && G->nodes[nn].first_in == -1;
9.149 + nn = G->nodes[nn].next) ;
9.150 + n = (nn==-1)?-1:G->nodes[nn].first_in;
9.151 + }
9.152 + return *this;
9.153 + }
9.154 + // ///Validity check
9.155 + // operator bool() { return Edge::operator bool(); }
9.156 };
9.157
9.158 class OutEdgeIt : public Edge {
9.159 + const ListGraph *G;
9.160 friend class ListGraph;
9.161 public:
9.162 OutEdgeIt() : Edge() { }
9.163 + OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
9.164 OutEdgeIt (Invalid i) : Edge(i) { }
9.165
9.166 - OutEdgeIt(const ListGraph& G,const Node v)
9.167 - : Edge(G.nodes[v.n].first_out) {}
9.168 + OutEdgeIt(const ListGraph& _G,const Node v)
9.169 + : Edge(_G.nodes[v.n].first_out), G(&_G) {}
9.170 + OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
9.171 + // ///Validity check
9.172 + // operator bool() { return Edge::operator bool(); }
9.173 };
9.174
9.175 class InEdgeIt : public Edge {
9.176 + const ListGraph *G;
9.177 friend class ListGraph;
9.178 public:
9.179 InEdgeIt() : Edge() { }
9.180 + InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
9.181 InEdgeIt (Invalid i) : Edge(i) { }
9.182 - InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
9.183 + InEdgeIt(const ListGraph& _G,Node v)
9.184 + : Edge(_G.nodes[v.n].first_in), G(&_G) { }
9.185 + InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
9.186 + // ///Validity check
9.187 + // operator bool() { return Edge::operator bool(); }
9.188 };
9.189
9.190 template <typename T> class NodeMap : public DynMapBase<Node>
9.191 @@ -838,12 +848,6 @@
9.192 Node tail(Edge e) const { return INVALID; }
9.193 Node head(Edge e) const { return INVALID; }
9.194
9.195 - Node aNode(OutEdgeIt e) const { return INVALID; }
9.196 - Node aNode(InEdgeIt e) const { return INVALID; }
9.197 -
9.198 - Node bNode(OutEdgeIt e) const { return INVALID; }
9.199 - Node bNode(InEdgeIt e) const { return INVALID; }
9.200 -
9.201 NodeIt& first(NodeIt& v) const {
9.202 v=NodeIt(*this); return v; }
9.203 EdgeIt& first(EdgeIt& e) const {
9.204 @@ -853,29 +857,6 @@
9.205 InEdgeIt& first(InEdgeIt& e, const Node v) const {
9.206 e=InEdgeIt(*this,v); return e; }
9.207
9.208 -// template< typename It >
9.209 -// It first() const { It e; first(e); return e; }
9.210 -
9.211 -// template< typename It >
9.212 -// It first(Node v) const { It e; first(e,v); return e; }
9.213 -
9.214 - bool valid(Edge e) const { return false; }
9.215 - bool valid(Node n) const { return n.n!=-1; }
9.216 -
9.217 - void setInvalid(Edge &e) { }
9.218 - void setInvalid(Node &n) { n.n=-1; }
9.219 -
9.220 - template <typename It> It getNext(It it) const
9.221 - { It tmp(it); return next(tmp); }
9.222 -
9.223 - NodeIt& next(NodeIt& it) const {
9.224 - it.n=nodes[it.n].next;
9.225 - return it;
9.226 - }
9.227 - OutEdgeIt& next(OutEdgeIt& it) const { return it; }
9.228 - InEdgeIt& next(InEdgeIt& it) const { return it; }
9.229 - EdgeIt& next(EdgeIt& it) const { return it; }
9.230 -
9.231 int id(Node v) const { return v.n; }
9.232 int id(Edge e) const { return -1; }
9.233
9.234 @@ -927,6 +908,12 @@
9.235 i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
9.236 }
9.237
9.238 +
9.239 + Edge findEdge(Node u,Node v, Edge prev = INVALID)
9.240 + {
9.241 + return INVALID;
9.242 + }
9.243 +
9.244 ///\bug Dynamic maps must be updated!
9.245 ///
9.246 void clear() {
9.247 @@ -955,14 +942,17 @@
9.248 };
9.249
9.250 class NodeIt : public Node {
9.251 + const NodeSet *G;
9.252 friend class NodeSet;
9.253 public:
9.254 NodeIt() : Node() { }
9.255 + NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
9.256 NodeIt(Invalid i) : Node(i) { }
9.257 - NodeIt(const NodeSet& G) : Node(G.first_node) { }
9.258 - ///\todo Undocumented conversion Node -\> NodeIt.
9.259 - NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
9.260 -
9.261 + NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
9.262 + NodeIt &operator++() {
9.263 + n=G->nodes[n].next;
9.264 + return *this;
9.265 + }
9.266 };
9.267
9.268 class Edge {
9.269 @@ -993,27 +983,33 @@
9.270 //friend class NodeSet;
9.271 public:
9.272 EdgeIt(const NodeSet& G) : Edge() { }
9.273 + EdgeIt(const NodeSet&, Edge) : Edge() { }
9.274 EdgeIt (Invalid i) : Edge(i) { }
9.275 EdgeIt() : Edge() { }
9.276 ///\bug This is a workaround until somebody tells me how to
9.277 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
9.278 // int idref() {return -1;}
9.279 + EdgeIt operator++() { return INVALID; }
9.280 };
9.281
9.282 class OutEdgeIt : public Edge {
9.283 friend class NodeSet;
9.284 public:
9.285 OutEdgeIt() : Edge() { }
9.286 + OutEdgeIt(const NodeSet&, Edge) : Edge() { }
9.287 OutEdgeIt (Invalid i) : Edge(i) { }
9.288 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
9.289 + OutEdgeIt operator++() { return INVALID; }
9.290 };
9.291
9.292 class InEdgeIt : public Edge {
9.293 friend class NodeSet;
9.294 public:
9.295 InEdgeIt() : Edge() { }
9.296 + InEdgeIt(const NodeSet&, Edge) : Edge() { }
9.297 InEdgeIt (Invalid i) : Edge(i) { }
9.298 InEdgeIt(const NodeSet& G,Node v) :Edge() {}
9.299 + InEdgeIt operator++() { return INVALID; }
9.300 };
9.301
9.302 template <typename T> class NodeMap : public DynMapBase<Node>
9.303 @@ -1199,15 +1195,15 @@
9.304 friend class EdgeSet;
9.305 public:
9.306 NodeIt() : NodeGraphType::NodeIt() { }
9.307 + NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
9.308 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
9.309 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
9.310 NodeIt(const typename NodeGraphType::NodeIt &n)
9.311 : NodeGraphType::NodeIt(n) {}
9.312 - ///\todo Undocumented conversion Node -\> NodeIt.
9.313 - NodeIt(const EdgeSet& _G, const Node &n)
9.314 - : NodeGraphType::NodeIt(_G.G,n) { }
9.315
9.316 operator Node() { return Node(*this);}
9.317 + NodeIt &operator++()
9.318 + { this->NodeGraphType::NodeIt::operator++(); return *this;}
9.319 };
9.320
9.321 private:
9.322 @@ -1311,12 +1307,6 @@
9.323 Node tail(Edge e) const { return edges[e.n].tail; }
9.324 Node head(Edge e) const { return edges[e.n].head; }
9.325
9.326 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
9.327 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
9.328 -
9.329 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
9.330 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
9.331 -
9.332 NodeIt& first(NodeIt& v) const {
9.333 v=NodeIt(*this); return v; }
9.334 EdgeIt& first(EdgeIt& e) const {
9.335 @@ -1326,40 +1316,6 @@
9.336 InEdgeIt& first(InEdgeIt& e, const Node v) const {
9.337 e=InEdgeIt(*this,v); return e; }
9.338
9.339 -// template< typename It >
9.340 -// It first() const { It e; first(e); return e; }
9.341 -
9.342 -// template< typename It >
9.343 -// It first(Node v) const { It e; first(e,v); return e; }
9.344 -
9.345 - bool valid(Edge e) const { return e.n!=-1; }
9.346 - bool valid(Node n) const { return G.valid(n); }
9.347 -
9.348 - void setInvalid(Edge &e) { e.n=-1; }
9.349 - void setInvalid(Node &n) { G.setInvalid(n); }
9.350 -
9.351 - template <typename It> It getNext(It it) const
9.352 - { It tmp(it); return next(tmp); }
9.353 -
9.354 - NodeIt& next(NodeIt& it) const { G.next(it); return it; }
9.355 - OutEdgeIt& next(OutEdgeIt& it) const
9.356 - { it.n=edges[it.n].next_out; return it; }
9.357 - InEdgeIt& next(InEdgeIt& it) const
9.358 - { it.n=edges[it.n].next_in; return it; }
9.359 - EdgeIt& next(EdgeIt& it) const {
9.360 - if(edges[it.n].next_in!=-1) {
9.361 - it.n=edges[it.n].next_in;
9.362 - }
9.363 - else {
9.364 - NodeIt n(*this,edges[it.n].head);
9.365 - for(n=next(n);
9.366 - valid(n) && nodes[n].first_in == -1;
9.367 - next(n)) ;
9.368 - it.n = (valid(n))?-1:nodes[n].first_in;
9.369 - }
9.370 - return it;
9.371 - }
9.372 -
9.373 int id(Edge e) const { return e.n; }
9.374
9.375 /// Adds a new node to the graph.
9.376 @@ -1398,6 +1354,22 @@
9.377 return e;
9.378 }
9.379
9.380 + /// Finds an edge between two nodes.
9.381 +
9.382 + /// Finds an edge from node \c u to node \c v.
9.383 + ///
9.384 + /// If \c prev is \ref INVALID (this is the default value), then
9.385 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
9.386 + /// the next edge from \c u to \c v after \c prev.
9.387 + /// \return The found edge or INVALID if there is no such an edge.
9.388 + Edge findEdge(Node u,Node v, Edge prev = INVALID)
9.389 + {
9.390 + int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
9.391 + while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
9.392 + prev.n=e;
9.393 + return prev;
9.394 + }
9.395 +
9.396 private:
9.397 void eraseEdge(int n) {
9.398
9.399 @@ -1460,7 +1432,7 @@
9.400 friend class Node;
9.401 friend class NodeIt;
9.402 public:
9.403 - ///\bug It shoud be at least protected
9.404 + ///\bug It should be at least protected
9.405 ///
9.406 int n;
9.407 protected:
9.408 @@ -1483,38 +1455,54 @@
9.409 friend class EdgeSet;
9.410 template <typename T> friend class EdgeMap;
9.411
9.412 -
9.413 + const EdgeSet *G;
9.414 public:
9.415 - EdgeIt(const EdgeSet& G) : Edge() {
9.416 + EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
9.417 // typename NodeGraphType::Node m;
9.418 NodeIt m;
9.419 - for(G.first(m);
9.420 - G.valid(m) && G.nodes[m].first_in == -1; G.next(m));
9.421 - //AJJAJ! This is a non sense!!!!!!!
9.422 - this->n = G.valid(m)?-1:G.nodes[m].first_in;
9.423 + for(G->first(m);
9.424 + m!=INVALID && G->nodes[m].first_in == -1; ++m);
9.425 + ///\bug AJJAJ! This is a non sense!!!!!!!
9.426 + this->n = m!=INVALID?-1:G->nodes[m].first_in;
9.427 }
9.428 + EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
9.429 EdgeIt (Invalid i) : Edge(i) { }
9.430 EdgeIt() : Edge() { }
9.431 - ///\bug This is a workaround until somebody tells me how to
9.432 + ///.
9.433 +
9.434 + ///\bug UNIMPLEMENTED!!!!!
9.435 + //
9.436 + EdgeIt &operator++() {
9.437 + return *this;
9.438 + }
9.439 + ///\bug This is a workaround until somebody tells me how to
9.440 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
9.441 int &idref() {return this->n;}
9.442 };
9.443
9.444 class OutEdgeIt : public Edge {
9.445 + const EdgeSet *G;
9.446 friend class EdgeSet;
9.447 public:
9.448 OutEdgeIt() : Edge() { }
9.449 OutEdgeIt (Invalid i) : Edge(i) { }
9.450 + OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
9.451
9.452 - OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
9.453 + OutEdgeIt(const EdgeSet& _G,const Node v) :
9.454 + Edge(_G.nodes[v].first_out), G(&_G) { }
9.455 + OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
9.456 };
9.457
9.458 class InEdgeIt : public Edge {
9.459 + const EdgeSet *G;
9.460 friend class EdgeSet;
9.461 public:
9.462 InEdgeIt() : Edge() { }
9.463 InEdgeIt (Invalid i) : Edge(i) { }
9.464 - InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
9.465 + InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
9.466 + InEdgeIt(const EdgeSet& _G,Node v)
9.467 + : Edge(_G.nodes[v].first_in), G(&_G) { }
9.468 + InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
9.469 };
9.470
9.471 template <typename T> class NodeMap :
9.472 @@ -1554,17 +1542,17 @@
9.473 {
9.474 //FIXME: What if there are empty Id's?
9.475 //FIXME: Can I use 'this' in a constructor?
9.476 - G->dyn_edge_maps.push_back(this);
9.477 + this->G->dyn_edge_maps.push_back(this);
9.478 }
9.479 EdgeMap(const EdgeSet &_G,const T &t) :
9.480 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
9.481 {
9.482 - G->dyn_edge_maps.push_back(this);
9.483 + this->G->dyn_edge_maps.push_back(this);
9.484 }
9.485 EdgeMap(const EdgeMap<T> &m) :
9.486 DynMapBase<Edge>(*m.G), container(m.container)
9.487 {
9.488 - G->dyn_edge_maps.push_back(this);
9.489 + this->G->dyn_edge_maps.push_back(this);
9.490 }
9.491
9.492 ///\todo It can copy between different types.
9.493 @@ -1572,7 +1560,7 @@
9.494 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
9.495 DynMapBase<Edge>(*m.G), container(m.container.size())
9.496 {
9.497 - G->dyn_edge_maps.push_back(this);
9.498 + this->G->dyn_edge_maps.push_back(this);
9.499 typename std::vector<TT>::const_iterator i;
9.500 for(typename std::vector<TT>::const_iterator i=m.container.begin();
9.501 i!=m.container.end();
9.502 @@ -1581,15 +1569,15 @@
9.503 }
9.504 ~EdgeMap()
9.505 {
9.506 - if(G) {
9.507 + if(this->G) {
9.508 typename std::vector<DynMapBase<Edge>* >::iterator i;
9.509 - for(i=G->dyn_edge_maps.begin();
9.510 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
9.511 + for(i=this->G->dyn_edge_maps.begin();
9.512 + i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ;
9.513 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
9.514 //A better way to do that: (Is this really important?)
9.515 if(*i==this) {
9.516 - *i=G->dyn_edge_maps.back();
9.517 - G->dyn_edge_maps.pop_back();
9.518 + *i=this->G->dyn_edge_maps.back();
9.519 + this->G->dyn_edge_maps.pop_back();
9.520 }
9.521 }
9.522 }
9.523 @@ -1602,16 +1590,16 @@
9.524
9.525 ///\bug This doesn't work. Why?
9.526 /// void set(Edge n, T a) { container[n.n]=a; }
9.527 - void set(Edge n, T a) { container[G->id(n)]=a; }
9.528 + void set(Edge n, T a) { container[this->G->id(n)]=a; }
9.529 //T get(Edge n) const { return container[n.n]; }
9.530 typename std::vector<T>::reference
9.531 ///\bug This doesn't work. Why?
9.532 /// operator[](Edge n) { return container[n.n]; }
9.533 - operator[](Edge n) { return container[G->id(n)]; }
9.534 + operator[](Edge n) { return container[this->G->id(n)]; }
9.535 typename std::vector<T>::const_reference
9.536 ///\bug This doesn't work. Why?
9.537 /// operator[](Edge n) const { return container[n.n]; }
9.538 - operator[](Edge n) const { return container[G->id(n)]; }
9.539 + operator[](Edge n) const { return container[this->G->id(n)]; }
9.540
9.541 ///\warning There is no safety check at all!
9.542 ///Using operator = between maps attached to different graph may
10.1 --- a/src/hugo/max_flow.h Wed Aug 25 18:55:57 2004 +0000
10.2 +++ b/src/hugo/max_flow.h Mon Aug 30 12:01:47 2004 +0000
10.3 @@ -5,7 +5,7 @@
10.4 #include <vector>
10.5 #include <queue>
10.6
10.7 -#include <hugo/graph_wrapper.h>
10.8 +//#include <hugo/graph_wrapper.h>
10.9 #include <hugo/invalid.h>
10.10 #include <hugo/maps.h>
10.11
10.12 @@ -62,10 +62,10 @@
10.13 const CapMap* capacity;
10.14 FlowMap* flow;
10.15 int n; //the number of nodes of G
10.16 - typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
10.17 + // typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
10.18 //typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
10.19 - typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
10.20 - typedef typename ResGW::Edge ResGWEdge;
10.21 + // typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
10.22 + // typedef typename ResGW::Edge ResGWEdge;
10.23 typedef typename Graph::template NodeMap<int> ReachedMap;
10.24
10.25
10.26 @@ -112,27 +112,27 @@
10.27 /// Do not needle this flag only if necessary.
10.28 StatusEnum status;
10.29
10.30 -// int number_of_augmentations;
10.31 + // int number_of_augmentations;
10.32
10.33
10.34 -// template<typename IntMap>
10.35 -// class TrickyReachedMap {
10.36 -// protected:
10.37 -// IntMap* map;
10.38 -// int* number_of_augmentations;
10.39 -// public:
10.40 -// TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
10.41 -// map(&_map), number_of_augmentations(&_number_of_augmentations) { }
10.42 -// void set(const Node& n, bool b) {
10.43 -// if (b)
10.44 -// map->set(n, *number_of_augmentations);
10.45 -// else
10.46 -// map->set(n, *number_of_augmentations-1);
10.47 -// }
10.48 -// bool operator[](const Node& n) const {
10.49 -// return (*map)[n]==*number_of_augmentations;
10.50 -// }
10.51 -// };
10.52 + // template<typename IntMap>
10.53 + // class TrickyReachedMap {
10.54 + // protected:
10.55 + // IntMap* map;
10.56 + // int* number_of_augmentations;
10.57 + // public:
10.58 + // TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
10.59 + // map(&_map), number_of_augmentations(&_number_of_augmentations) { }
10.60 + // void set(const Node& n, bool b) {
10.61 + // if (b)
10.62 + // map->set(n, *number_of_augmentations);
10.63 + // else
10.64 + // map->set(n, *number_of_augmentations-1);
10.65 + // }
10.66 + // bool operator[](const Node& n) const {
10.67 + // return (*map)[n]==*number_of_augmentations;
10.68 + // }
10.69 + // };
10.70
10.71 ///Constructor
10.72
10.73 @@ -234,7 +234,7 @@
10.74 } else break;
10.75 }
10.76
10.77 - if ( !g->valid(first[b]) ) --b;
10.78 + if ( first[b]==INVALID ) --b;
10.79 else {
10.80 end=false;
10.81 Node w=first[b];
10.82 @@ -289,8 +289,7 @@
10.83 bfs_queue.pop();
10.84 int l=level[v]+1;
10.85
10.86 - InEdgeIt e;
10.87 - for(g->first(e,v); g->valid(e); g->next(e)) {
10.88 + for(InEdgeIt e(*g,v); e!=INVALID; ++e) {
10.89 if ( (*capacity)[e] <= (*flow)[e] ) continue;
10.90 Node u=g->tail(e);
10.91 if ( level[u] >= n ) {
10.92 @@ -303,10 +302,9 @@
10.93 }
10.94 }
10.95
10.96 - OutEdgeIt f;
10.97 - for(g->first(f,v); g->valid(f); g->next(f)) {
10.98 - if ( 0 >= (*flow)[f] ) continue;
10.99 - Node u=g->head(f);
10.100 + for(OutEdgeIt e(*g,v); e!=INVALID; ++e) {
10.101 + if ( 0 >= (*flow)[e] ) continue;
10.102 + Node u=g->head(e);
10.103 if ( level[u] >= n ) {
10.104 bfs_queue.push(u);
10.105 level.set(u, l);
10.106 @@ -323,7 +321,7 @@
10.107
10.108 if ( b == 0 ) break;
10.109
10.110 - if ( !g->valid(first[b]) ) --b;
10.111 + if ( first[b]==INVALID ) --b;
10.112 else {
10.113
10.114 Node w=first[b];
10.115 @@ -351,10 +349,10 @@
10.116 /// the maximum flow.
10.117 /// It can be called already after running \ref preflowPhase1.
10.118 Num flowValue() const {
10.119 -// Num a=0;
10.120 -// for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
10.121 -// for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
10.122 -// return a;
10.123 + // Num a=0;
10.124 + // for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
10.125 + // for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
10.126 + // return a;
10.127 return excess[t];
10.128 //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
10.129 }
10.130 @@ -374,10 +372,9 @@
10.131 /// for MinCut computation
10.132 template<typename _CutMap>
10.133 void actMinCut(_CutMap& M) const {
10.134 - NodeIt v;
10.135 switch (status) {
10.136 - case AFTER_PRE_FLOW_PHASE_1:
10.137 - for(g->first(v); g->valid(v); g->next(v)) {
10.138 + case AFTER_PRE_FLOW_PHASE_1:
10.139 + for(NodeIt v(*g); v!=INVALID; ++v) {
10.140 if (level[v] < n) {
10.141 M.set(v, false);
10.142 } else {
10.143 @@ -385,10 +382,10 @@
10.144 }
10.145 }
10.146 break;
10.147 - case AFTER_PRE_FLOW_PHASE_2:
10.148 - case AFTER_NOTHING:
10.149 - case AFTER_AUGMENTING:
10.150 - case AFTER_FAST_AUGMENTING:
10.151 + case AFTER_PRE_FLOW_PHASE_2:
10.152 + case AFTER_NOTHING:
10.153 + case AFTER_AUGMENTING:
10.154 + case AFTER_FAST_AUGMENTING:
10.155 minMinCut(M);
10.156 break;
10.157 }
10.158 @@ -412,8 +409,7 @@
10.159 Node w=queue.front();
10.160 queue.pop();
10.161
10.162 - OutEdgeIt e;
10.163 - for(g->first(e,w) ; g->valid(e); g->next(e)) {
10.164 + for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
10.165 Node v=g->head(e);
10.166 if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
10.167 queue.push(v);
10.168 @@ -421,10 +417,9 @@
10.169 }
10.170 }
10.171
10.172 - InEdgeIt f;
10.173 - for(g->first(f,w) ; g->valid(f); g->next(f)) {
10.174 - Node v=g->tail(f);
10.175 - if (!M[v] && (*flow)[f] > 0 ) {
10.176 + for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
10.177 + Node v=g->tail(e);
10.178 + if (!M[v] && (*flow)[e] > 0 ) {
10.179 queue.push(v);
10.180 M.set(v, true);
10.181 }
10.182 @@ -442,10 +437,7 @@
10.183 template<typename _CutMap>
10.184 void maxMinCut(_CutMap& M) const {
10.185
10.186 - NodeIt v;
10.187 - for(g->first(v) ; g->valid(v); g->next(v)) {
10.188 - M.set(v, true);
10.189 - }
10.190 + for(NodeIt v(*g) ; v!=INVALID; ++v) M.set(v, true);
10.191
10.192 std::queue<Node> queue;
10.193
10.194 @@ -456,8 +448,7 @@
10.195 Node w=queue.front();
10.196 queue.pop();
10.197
10.198 - InEdgeIt e;
10.199 - for(g->first(e,w) ; g->valid(e); g->next(e)) {
10.200 + for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
10.201 Node v=g->tail(e);
10.202 if (M[v] && (*flow)[e] < (*capacity)[e] ) {
10.203 queue.push(v);
10.204 @@ -465,10 +456,9 @@
10.205 }
10.206 }
10.207
10.208 - OutEdgeIt f;
10.209 - for(g->first(f,w) ; g->valid(f); g->next(f)) {
10.210 - Node v=g->head(f);
10.211 - if (M[v] && (*flow)[f] > 0 ) {
10.212 + for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
10.213 + Node v=g->head(e);
10.214 + if (M[v] && (*flow)[e] > 0 ) {
10.215 queue.push(v);
10.216 M.set(v, false);
10.217 }
10.218 @@ -518,14 +508,12 @@
10.219 Num exc=excess[w];
10.220 int newlevel=n; //bound on the next level of w
10.221
10.222 - OutEdgeIt e;
10.223 - for(g->first(e,w); g->valid(e); g->next(e)) {
10.224 -
10.225 + for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
10.226 if ( (*flow)[e] >= (*capacity)[e] ) continue;
10.227 Node v=g->head(e);
10.228
10.229 if( lev > level[v] ) { //Push is allowed now
10.230 -
10.231 +
10.232 if ( excess[v]<=0 && v!=t && v!=s ) {
10.233 next.set(v,first[level[v]]);
10.234 first[level[v]]=v;
10.235 @@ -534,9 +522,9 @@
10.236 Num cap=(*capacity)[e];
10.237 Num flo=(*flow)[e];
10.238 Num remcap=cap-flo;
10.239 -
10.240 +
10.241 if ( remcap >= exc ) { //A nonsaturating push.
10.242 -
10.243 +
10.244 flow->set(e, flo+exc);
10.245 excess.set(v, excess[v]+exc);
10.246 exc=0;
10.247 @@ -551,9 +539,8 @@
10.248 } //for out edges wv
10.249
10.250 if ( exc > 0 ) {
10.251 - InEdgeIt e;
10.252 - for(g->first(e,w); g->valid(e); g->next(e)) {
10.253 -
10.254 + for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
10.255 +
10.256 if( (*flow)[e] <= 0 ) continue;
10.257 Node v=g->tail(e);
10.258
10.259 @@ -584,49 +571,37 @@
10.260 } // if w still has excess after the out edge for cycle
10.261
10.262 excess.set(w, exc);
10.263 -
10.264 +
10.265 return newlevel;
10.266 }
10.267 -
10.268 -
10.269 -
10.270 +
10.271 +
10.272 +
10.273 void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first,
10.274 VecNode& level_list, NNMap& left, NNMap& right)
10.275 {
10.276 - switch (fe) { //setting excess
10.277 + switch (fe) { //setting excess
10.278 case NO_FLOW:
10.279 + for(EdgeIt e(*g); e!=INVALID; ++e) flow->set(e,0);
10.280 + for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
10.281 + break;
10.282 + case ZERO_FLOW:
10.283 + for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
10.284 + break;
10.285 + case GEN_FLOW:
10.286 + for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
10.287 {
10.288 - EdgeIt e;
10.289 - for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
10.290 -
10.291 - NodeIt v;
10.292 - for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
10.293 - break;
10.294 + Num exc=0;
10.295 + for(InEdgeIt e(*g,t) ; e!=INVALID; ++e) exc+=(*flow)[e];
10.296 + for(OutEdgeIt e(*g,t) ; e!=INVALID; ++e) exc-=(*flow)[e];
10.297 + excess.set(t,exc);
10.298 }
10.299 - case ZERO_FLOW:
10.300 - {
10.301 - NodeIt v;
10.302 - for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
10.303 - break;
10.304 - }
10.305 - case GEN_FLOW:
10.306 - {
10.307 - NodeIt v;
10.308 - for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
10.309 -
10.310 - Num exc=0;
10.311 - InEdgeIt e;
10.312 - for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
10.313 - OutEdgeIt f;
10.314 - for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
10.315 - excess.set(t,exc);
10.316 - break;
10.317 - }
10.318 - default: break;
10.319 + break;
10.320 + default:
10.321 + break;
10.322 }
10.323 -
10.324 - NodeIt v;
10.325 - for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
10.326 +
10.327 + for(NodeIt v(*g); v!=INVALID; ++v) level.set(v,n);
10.328 //setting each node to level n
10.329
10.330 std::queue<Node> bfs_queue;
10.331 @@ -635,219 +610,197 @@
10.332 switch (fe) {
10.333 case NO_FLOW: //flow is already set to const zero
10.334 case ZERO_FLOW:
10.335 - {
10.336 - //Reverse_bfs from t, to find the starting level.
10.337 - level.set(t,0);
10.338 - bfs_queue.push(t);
10.339 -
10.340 - while (!bfs_queue.empty()) {
10.341 -
10.342 - Node v=bfs_queue.front();
10.343 - bfs_queue.pop();
10.344 - int l=level[v]+1;
10.345 -
10.346 - InEdgeIt e;
10.347 - for(g->first(e,v); g->valid(e); g->next(e)) {
10.348 - Node w=g->tail(e);
10.349 - if ( level[w] == n && w != s ) {
10.350 - bfs_queue.push(w);
10.351 - Node z=level_list[l];
10.352 - if ( g->valid(z) ) left.set(z,w);
10.353 - right.set(w,z);
10.354 - level_list[l]=w;
10.355 - level.set(w, l);
10.356 - }
10.357 + //Reverse_bfs from t, to find the starting level.
10.358 + level.set(t,0);
10.359 + bfs_queue.push(t);
10.360 +
10.361 + while (!bfs_queue.empty()) {
10.362 +
10.363 + Node v=bfs_queue.front();
10.364 + bfs_queue.pop();
10.365 + int l=level[v]+1;
10.366 +
10.367 + for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
10.368 + Node w=g->tail(e);
10.369 + if ( level[w] == n && w != s ) {
10.370 + bfs_queue.push(w);
10.371 + Node z=level_list[l];
10.372 + if ( z!=INVALID ) left.set(z,w);
10.373 + right.set(w,z);
10.374 + level_list[l]=w;
10.375 + level.set(w, l);
10.376 }
10.377 }
10.378 -
10.379 - //the starting flow
10.380 - OutEdgeIt e;
10.381 - for(g->first(e,s); g->valid(e); g->next(e))
10.382 - {
10.383 - Num c=(*capacity)[e];
10.384 - if ( c <= 0 ) continue;
10.385 - Node w=g->head(e);
10.386 - if ( level[w] < n ) {
10.387 - if ( excess[w] <= 0 && w!=t ) //putting into the stack
10.388 - {
10.389 - next.set(w,first[level[w]]);
10.390 - first[level[w]]=w;
10.391 - }
10.392 - flow->set(e, c);
10.393 - excess.set(w, excess[w]+c);
10.394 - }
10.395 - }
10.396 - break;
10.397 }
10.398 -
10.399 - case GEN_FLOW:
10.400 - {
10.401 - //Reverse_bfs from t in the residual graph,
10.402 - //to find the starting level.
10.403 - level.set(t,0);
10.404 - bfs_queue.push(t);
10.405 -
10.406 - while (!bfs_queue.empty()) {
10.407 -
10.408 - Node v=bfs_queue.front();
10.409 - bfs_queue.pop();
10.410 - int l=level[v]+1;
10.411 -
10.412 - InEdgeIt e;
10.413 - for(g->first(e,v); g->valid(e); g->next(e)) {
10.414 - if ( (*capacity)[e] <= (*flow)[e] ) continue;
10.415 - Node w=g->tail(e);
10.416 - if ( level[w] == n && w != s ) {
10.417 - bfs_queue.push(w);
10.418 - Node z=level_list[l];
10.419 - if ( g->valid(z) ) left.set(z,w);
10.420 - right.set(w,z);
10.421 - level_list[l]=w;
10.422 - level.set(w, l);
10.423 - }
10.424 - }
10.425 -
10.426 - OutEdgeIt f;
10.427 - for(g->first(f,v); g->valid(f); g->next(f)) {
10.428 - if ( 0 >= (*flow)[f] ) continue;
10.429 - Node w=g->head(f);
10.430 - if ( level[w] == n && w != s ) {
10.431 - bfs_queue.push(w);
10.432 - Node z=level_list[l];
10.433 - if ( g->valid(z) ) left.set(z,w);
10.434 - right.set(w,z);
10.435 - level_list[l]=w;
10.436 - level.set(w, l);
10.437 - }
10.438 +
10.439 + //the starting flow
10.440 + for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e)
10.441 + {
10.442 + Num c=(*capacity)[e];
10.443 + if ( c <= 0 ) continue;
10.444 + Node w=g->head(e);
10.445 + if ( level[w] < n ) {
10.446 + if ( excess[w] <= 0 && w!=t ) //putting into the stack
10.447 + {
10.448 + next.set(w,first[level[w]]);
10.449 + first[level[w]]=w;
10.450 + }
10.451 + flow->set(e, c);
10.452 + excess.set(w, excess[w]+c);
10.453 }
10.454 }
10.455 -
10.456 - //the starting flow
10.457 - OutEdgeIt e;
10.458 - for(g->first(e,s); g->valid(e); g->next(e))
10.459 - {
10.460 - Num rem=(*capacity)[e]-(*flow)[e];
10.461 - if ( rem <= 0 ) continue;
10.462 - Node w=g->head(e);
10.463 - if ( level[w] < n ) {
10.464 - if ( excess[w] <= 0 && w!=t ) //putting into the stack
10.465 - {
10.466 - next.set(w,first[level[w]]);
10.467 - first[level[w]]=w;
10.468 - }
10.469 - flow->set(e, (*capacity)[e]);
10.470 - excess.set(w, excess[w]+rem);
10.471 - }
10.472 - }
10.473 -
10.474 - InEdgeIt f;
10.475 - for(g->first(f,s); g->valid(f); g->next(f))
10.476 - {
10.477 - if ( (*flow)[f] <= 0 ) continue;
10.478 - Node w=g->tail(f);
10.479 - if ( level[w] < n ) {
10.480 - if ( excess[w] <= 0 && w!=t )
10.481 - {
10.482 - next.set(w,first[level[w]]);
10.483 - first[level[w]]=w;
10.484 - }
10.485 - excess.set(w, excess[w]+(*flow)[f]);
10.486 - flow->set(f, 0);
10.487 - }
10.488 - }
10.489 - break;
10.490 - } //case GEN_FLOW
10.491 -
10.492 - case PRE_FLOW:
10.493 - {
10.494 - //Reverse_bfs from t in the residual graph,
10.495 - //to find the starting level.
10.496 - level.set(t,0);
10.497 - bfs_queue.push(t);
10.498 -
10.499 - while (!bfs_queue.empty()) {
10.500 -
10.501 - Node v=bfs_queue.front();
10.502 - bfs_queue.pop();
10.503 - int l=level[v]+1;
10.504 -
10.505 - InEdgeIt e;
10.506 - for(g->first(e,v); g->valid(e); g->next(e)) {
10.507 - if ( (*capacity)[e] <= (*flow)[e] ) continue;
10.508 - Node w=g->tail(e);
10.509 - if ( level[w] == n && w != s ) {
10.510 - bfs_queue.push(w);
10.511 - Node z=level_list[l];
10.512 - if ( g->valid(z) ) left.set(z,w);
10.513 - right.set(w,z);
10.514 - level_list[l]=w;
10.515 - level.set(w, l);
10.516 - }
10.517 - }
10.518 -
10.519 - OutEdgeIt f;
10.520 - for(g->first(f,v); g->valid(f); g->next(f)) {
10.521 - if ( 0 >= (*flow)[f] ) continue;
10.522 - Node w=g->head(f);
10.523 - if ( level[w] == n && w != s ) {
10.524 - bfs_queue.push(w);
10.525 - Node z=level_list[l];
10.526 - if ( g->valid(z) ) left.set(z,w);
10.527 - right.set(w,z);
10.528 - level_list[l]=w;
10.529 - level.set(w, l);
10.530 - }
10.531 + break;
10.532 + case GEN_FLOW:
10.533 + //Reverse_bfs from t in the residual graph,
10.534 + //to find the starting level.
10.535 + level.set(t,0);
10.536 + bfs_queue.push(t);
10.537 +
10.538 + while (!bfs_queue.empty()) {
10.539 +
10.540 + Node v=bfs_queue.front();
10.541 + bfs_queue.pop();
10.542 + int l=level[v]+1;
10.543 +
10.544 + for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
10.545 + if ( (*capacity)[e] <= (*flow)[e] ) continue;
10.546 + Node w=g->tail(e);
10.547 + if ( level[w] == n && w != s ) {
10.548 + bfs_queue.push(w);
10.549 + Node z=level_list[l];
10.550 + if ( z!=INVALID ) left.set(z,w);
10.551 + right.set(w,z);
10.552 + level_list[l]=w;
10.553 + level.set(w, l);
10.554 }
10.555 }
10.556 -
10.557 -
10.558 - //the starting flow
10.559 - OutEdgeIt e;
10.560 - for(g->first(e,s); g->valid(e); g->next(e))
10.561 +
10.562 + for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
10.563 + if ( 0 >= (*flow)[e] ) continue;
10.564 + Node w=g->head(e);
10.565 + if ( level[w] == n && w != s ) {
10.566 + bfs_queue.push(w);
10.567 + Node z=level_list[l];
10.568 + if ( z!=INVALID ) left.set(z,w);
10.569 + right.set(w,z);
10.570 + level_list[l]=w;
10.571 + level.set(w, l);
10.572 + }
10.573 + }
10.574 + }
10.575 +
10.576 + //the starting flow
10.577 + for(OutEdgeIt e(*g,s); e!=INVALID; ++e)
10.578 + {
10.579 + Num rem=(*capacity)[e]-(*flow)[e];
10.580 + if ( rem <= 0 ) continue;
10.581 + Node w=g->head(e);
10.582 + if ( level[w] < n ) {
10.583 + if ( excess[w] <= 0 && w!=t ) //putting into the stack
10.584 + {
10.585 + next.set(w,first[level[w]]);
10.586 + first[level[w]]=w;
10.587 + }
10.588 + flow->set(e, (*capacity)[e]);
10.589 + excess.set(w, excess[w]+rem);
10.590 + }
10.591 + }
10.592 +
10.593 + for(InEdgeIt e(*g,s); e!=INVALID; ++e)
10.594 + {
10.595 + if ( (*flow)[e] <= 0 ) continue;
10.596 + Node w=g->tail(e);
10.597 + if ( level[w] < n ) {
10.598 + if ( excess[w] <= 0 && w!=t )
10.599 + {
10.600 + next.set(w,first[level[w]]);
10.601 + first[level[w]]=w;
10.602 + }
10.603 + excess.set(w, excess[w]+(*flow)[e]);
10.604 + flow->set(e, 0);
10.605 + }
10.606 + }
10.607 + break;
10.608 + case PRE_FLOW:
10.609 + //Reverse_bfs from t in the residual graph,
10.610 + //to find the starting level.
10.611 + level.set(t,0);
10.612 + bfs_queue.push(t);
10.613 +
10.614 + while (!bfs_queue.empty()) {
10.615 +
10.616 + Node v=bfs_queue.front();
10.617 + bfs_queue.pop();
10.618 + int l=level[v]+1;
10.619 +
10.620 + for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
10.621 + if ( (*capacity)[e] <= (*flow)[e] ) continue;
10.622 + Node w=g->tail(e);
10.623 + if ( level[w] == n && w != s ) {
10.624 + bfs_queue.push(w);
10.625 + Node z=level_list[l];
10.626 + if ( z!=INVALID ) left.set(z,w);
10.627 + right.set(w,z);
10.628 + level_list[l]=w;
10.629 + level.set(w, l);
10.630 + }
10.631 + }
10.632 +
10.633 + for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
10.634 + if ( 0 >= (*flow)[e] ) continue;
10.635 + Node w=g->head(e);
10.636 + if ( level[w] == n && w != s ) {
10.637 + bfs_queue.push(w);
10.638 + Node z=level_list[l];
10.639 + if ( z!=INVALID ) left.set(z,w);
10.640 + right.set(w,z);
10.641 + level_list[l]=w;
10.642 + level.set(w, l);
10.643 + }
10.644 + }
10.645 + }
10.646 +
10.647 +
10.648 + //the starting flow
10.649 + for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) {
10.650 + Num rem=(*capacity)[e]-(*flow)[e];
10.651 + if ( rem <= 0 ) continue;
10.652 + Node w=g->head(e);
10.653 + if ( level[w] < n ) {
10.654 + flow->set(e, (*capacity)[e]);
10.655 + excess.set(w, excess[w]+rem);
10.656 + }
10.657 + }
10.658 +
10.659 + for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) {
10.660 + if ( (*flow)[e] <= 0 ) continue;
10.661 + Node w=g->tail(e);
10.662 + if ( level[w] < n ) {
10.663 + excess.set(w, excess[w]+(*flow)[e]);
10.664 + flow->set(e, 0);
10.665 + }
10.666 + }
10.667 +
10.668 + //computing the excess
10.669 + for(NodeIt w(*g); w!=INVALID; ++w) {
10.670 + Num exc=0;
10.671 +
10.672 + for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) exc+=(*flow)[e];
10.673 + for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) exc-=(*flow)[e];
10.674 +
10.675 + excess.set(w,exc);
10.676 +
10.677 + //putting the active nodes into the stack
10.678 + int lev=level[w];
10.679 + if ( exc > 0 && lev < n && Node(w) != t )
10.680 + ///\bug if ( exc > 0 && lev < n && w != t ) temporarily for working with wrappers.
10.681 {
10.682 - Num rem=(*capacity)[e]-(*flow)[e];
10.683 - if ( rem <= 0 ) continue;
10.684 - Node w=g->head(e);
10.685 - if ( level[w] < n ) {
10.686 - flow->set(e, (*capacity)[e]);
10.687 - excess.set(w, excess[w]+rem);
10.688 - }
10.689 + next.set(w,first[lev]);
10.690 + first[lev]=w;
10.691 }
10.692 -
10.693 - InEdgeIt f;
10.694 - for(g->first(f,s); g->valid(f); g->next(f))
10.695 - {
10.696 - if ( (*flow)[f] <= 0 ) continue;
10.697 - Node w=g->tail(f);
10.698 - if ( level[w] < n ) {
10.699 - excess.set(w, excess[w]+(*flow)[f]);
10.700 - flow->set(f, 0);
10.701 - }
10.702 - }
10.703 -
10.704 - NodeIt w; //computing the excess
10.705 - for(g->first(w); g->valid(w); g->next(w)) {
10.706 - Num exc=0;
10.707 -
10.708 - InEdgeIt e;
10.709 - for(g->first(e,w); g->valid(e); g->next(e)) exc+=(*flow)[e];
10.710 - OutEdgeIt f;
10.711 - for(g->first(f,w); g->valid(f); g->next(f)) exc-=(*flow)[f];
10.712 -
10.713 - excess.set(w,exc);
10.714 -
10.715 - //putting the active nodes into the stack
10.716 - int lev=level[w];
10.717 - if ( exc > 0 && lev < n && Node(w) != t )
10.718 -///\bug if ( exc > 0 && lev < n && w != t ) tempararily for working with wrappers. in hugo 0.2 it will work. Amugy mukodik sage_graph-fal, de smart_graph-fal nem, azt hozzatennem.
10.719 - {
10.720 - next.set(w,first[lev]);
10.721 - first[lev]=w;
10.722 - }
10.723 - }
10.724 - break;
10.725 - } //case PRE_FLOW
10.726 - }
10.727 + }
10.728 + break;
10.729 + } //switch
10.730 } //preflowPreproc
10.731
10.732
10.733 @@ -862,8 +815,8 @@
10.734 Node left_n=left[w];
10.735
10.736 //unlacing starts
10.737 - if ( g->valid(right_n) ) {
10.738 - if ( g->valid(left_n) ) {
10.739 + if ( right_n!=INVALID ) {
10.740 + if ( left_n!=INVALID ) {
10.741 right.set(left_n, right_n);
10.742 left.set(right_n, left_n);
10.743 } else {
10.744 @@ -871,7 +824,7 @@
10.745 left.set(right_n, INVALID);
10.746 }
10.747 } else {
10.748 - if ( g->valid(left_n) ) {
10.749 + if ( left_n!=INVALID ) {
10.750 right.set(left_n, INVALID);
10.751 } else {
10.752 level_list[lev]=INVALID;
10.753 @@ -879,12 +832,12 @@
10.754 }
10.755 //unlacing ends
10.756
10.757 - if ( !g->valid(level_list[lev]) ) {
10.758 + if ( level_list[lev]==INVALID ) {
10.759
10.760 //gapping starts
10.761 for (int i=lev; i!=k ; ) {
10.762 Node v=level_list[++i];
10.763 - while ( g->valid(v) ) {
10.764 + while ( v!=INVALID ) {
10.765 level.set(v,n);
10.766 v=right[v];
10.767 }
10.768 @@ -907,7 +860,7 @@
10.769 if ( what_heur ) b=newlevel;
10.770 if ( k < newlevel ) ++k; //now k=newlevel
10.771 Node z=level_list[newlevel];
10.772 - if ( g->valid(z) ) left.set(z,w);
10.773 + if ( z!=INVALID ) left.set(z,w);
10.774 right.set(w,z);
10.775 left.set(w,INVALID);
10.776 level_list[newlevel]=w;
10.777 @@ -918,26 +871,23 @@
10.778 void printexcess() {////
10.779 std::cout << "Excesses:" <<std::endl;
10.780
10.781 - NodeIt v;
10.782 - for(g->first(v); g->valid(v); g->next(v)) {
10.783 + for(NodeIt v(*g); v!=INVALID ; ++v) {
10.784 std::cout << 1+(g->id(v)) << ":" << excess[v]<<std::endl;
10.785 }
10.786 }
10.787
10.788 - void printlevel() {////
10.789 + void printlevel() {////
10.790 std::cout << "Levels:" <<std::endl;
10.791
10.792 - NodeIt v;
10.793 - for(g->first(v); g->valid(v); g->next(v)) {
10.794 + for(NodeIt v(*g); v!=INVALID ; ++v) {
10.795 std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
10.796 }
10.797 }
10.798
10.799 -void printactive() {////
10.800 + void printactive() {////
10.801 std::cout << "Levels:" <<std::endl;
10.802
10.803 - NodeIt v;
10.804 - for(g->first(v); g->valid(v); g->next(v)) {
10.805 + for(NodeIt v(*g); v!=INVALID ; ++v) {
10.806 std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
10.807 }
10.808 }
11.1 --- a/src/hugo/skeletons/graph.h Wed Aug 25 18:55:57 2004 +0000
11.2 +++ b/src/hugo/skeletons/graph.h Mon Aug 30 12:01:47 2004 +0000
11.3 @@ -34,30 +34,32 @@
11.4 {
11.5 public:
11.6 /// Defalult constructor.
11.7 - StaticGraphSkeleton() {}
11.8 + StaticGraphSkeleton() { }
11.9 ///Copy consructor.
11.10
11.11 ///\todo It is not clear, what we expect from a copy constructor.
11.12 ///E.g. How to assign the nodes/edges to each other? What about maps?
11.13 - StaticGraphSkeleton(const StaticGraphSkeleton &G) {}
11.14 + StaticGraphSkeleton(const StaticGraphSkeleton& g) { }
11.15
11.16 - /// The base type of the node iterators.
11.17 + /// The base type of node iterators,
11.18 + /// or in other words, the trivial node iterator.
11.19
11.20 - /// This is the base type of each node iterators,
11.21 - /// thus each kind of node iterator will convert to this.
11.22 + /// This is the base type of each node iterator,
11.23 + /// thus each kind of node iterator converts to this.
11.24 + /// More precisely each kind of node iterator have to be inherited
11.25 + /// from the trivial node iterator.
11.26 class Node {
11.27 public:
11.28 /// @warning The default constructor sets the iterator
11.29 /// to an undefined value.
11.30 - Node() {} //FIXME
11.31 + Node() { }
11.32 + /// Copy constructor.
11.33 + Node(const Node&) { }
11.34 /// Invalid constructor \& conversion.
11.35
11.36 /// This constructor initializes the iterator to be invalid.
11.37 /// \sa Invalid for more details.
11.38 -
11.39 - Node(Invalid) {}
11.40 - //Node(const Node &) {}
11.41 -
11.42 + Node(Invalid) { }
11.43 /// Two iterators are equal if and only if they point to the
11.44 /// same object or both are invalid.
11.45 bool operator==(Node) const { return true; }
11.46 @@ -73,26 +75,31 @@
11.47
11.48 /// This iterator goes through each node.
11.49 /// Its usage is quite simple, for example you can count the number
11.50 - /// of nodes in graph \c G of type \c Graph like this:
11.51 + /// of nodes in graph \c g of type \c Graph like this:
11.52 /// \code
11.53 - ///int count=0;
11.54 - ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
11.55 + /// int count=0;
11.56 + /// for (Graph::NodeIt n(g); g.valid(n); ++n) ++count;
11.57 /// \endcode
11.58 class NodeIt : public Node {
11.59 public:
11.60 /// @warning The default constructor sets the iterator
11.61 /// to an undefined value.
11.62 - NodeIt() {} //FIXME
11.63 + NodeIt() { }
11.64 + /// Copy constructor.
11.65 + NodeIt(const NodeIt&) { }
11.66 /// Invalid constructor \& conversion.
11.67
11.68 - /// Initialize the iterator to be invalid
11.69 + /// Initialize the iterator to be invalid.
11.70 /// \sa Invalid for more details.
11.71 - NodeIt(Invalid) {}
11.72 - /// Sets the iterator to the first node of \c G.
11.73 - NodeIt(const StaticGraphSkeleton &) {}
11.74 - /// @warning The default constructor sets the iterator
11.75 - /// to an undefined value.
11.76 - NodeIt(const NodeIt &n) : Node(n) {}
11.77 + NodeIt(Invalid) { }
11.78 + /// Sets the iterator to the first node of \c g.
11.79 + NodeIt(const StaticGraphSkeleton& g) { }
11.80 + /// Sets the iterator to the node of \c g pointed by the trivial
11.81 + /// iterator n. This feature necessitates that each time we
11.82 + /// iterate the node-set, the iteration order is the same.
11.83 + NodeIt(const StaticGraphSkeleton& g, const Node& n) { }
11.84 + /// Assign the iterator to the next node.
11.85 + NodeIt& operator++() { return *this; }
11.86 };
11.87
11.88
11.89 @@ -101,9 +108,11 @@
11.90 public:
11.91 /// @warning The default constructor sets the iterator
11.92 /// to an undefined value.
11.93 - Edge() {} //FIXME
11.94 - /// Initialize the iterator to be invalid
11.95 - Edge(Invalid) {}
11.96 + Edge() { }
11.97 + /// Copy constructor.
11.98 + Edge(const Edge&) { }
11.99 + /// Initialize the iterator to be invalid.
11.100 + Edge(Invalid) { }
11.101 /// Two iterators are equal if and only if they point to the
11.102 /// same object or both are invalid.
11.103 bool operator==(Edge) const { return true; }
11.104 @@ -117,26 +126,34 @@
11.105 /// of a graph.
11.106 /// Its usage is quite simple, for example you can count the number
11.107 /// of outgoing edges of a node \c n
11.108 - /// in graph \c G of type \c Graph as follows.
11.109 + /// in graph \c g of type \c Graph as follows.
11.110 /// \code
11.111 - ///int count=0;
11.112 - ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
11.113 + /// int count=0;
11.114 + /// for (Graph::OutEdgeIt e(g, n); g.valid(e); ++e) ++count;
11.115 /// \endcode
11.116
11.117 class OutEdgeIt : public Edge {
11.118 public:
11.119 /// @warning The default constructor sets the iterator
11.120 /// to an undefined value.
11.121 - OutEdgeIt() {}
11.122 - /// Initialize the iterator to be invalid
11.123 - OutEdgeIt(Invalid) {}
11.124 + OutEdgeIt() { }
11.125 + /// Copy constructor.
11.126 + OutEdgeIt(const OutEdgeIt&) { }
11.127 + /// Initialize the iterator to be invalid.
11.128 + OutEdgeIt(Invalid) { }
11.129 /// This constructor sets the iterator to first outgoing edge.
11.130
11.131 /// This constructor set the iterator to the first outgoing edge of
11.132 /// node
11.133 ///@param n the node
11.134 - ///@param G the graph
11.135 - OutEdgeIt(const StaticGraphSkeleton &, Node) {}
11.136 + ///@param g the graph
11.137 + OutEdgeIt(const StaticGraphSkeleton& g, const Node& n) { }
11.138 + /// Sets the iterator to the value of the trivial iterator \c e.
11.139 + /// This feature necessitates that each time we
11.140 + /// iterate the edge-set, the iteration order is the same.
11.141 + OutEdgeIt(const StaticGraphSkeleton& g, const Edge& e) { }
11.142 + /// Assign the iterator to the next outedge of the corresponding node.
11.143 + OutEdgeIt& operator++() { return *this; }
11.144 };
11.145
11.146 /// This iterator goes trough the incoming edges of a node.
11.147 @@ -145,20 +162,27 @@
11.148 /// of a graph.
11.149 /// Its usage is quite simple, for example you can count the number
11.150 /// of outgoing edges of a node \c n
11.151 - /// in graph \c G of type \c Graph as follows.
11.152 + /// in graph \c g of type \c Graph as follows.
11.153 /// \code
11.154 - ///int count=0;
11.155 - ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
11.156 + /// int count=0;
11.157 + /// for(Graph::InEdgeIt e(g, n); g.valid(e); ++) ++count;
11.158 /// \endcode
11.159
11.160 class InEdgeIt : public Edge {
11.161 public:
11.162 /// @warning The default constructor sets the iterator
11.163 /// to an undefined value.
11.164 - InEdgeIt() {}
11.165 - /// Initialize the iterator to be invalid
11.166 - InEdgeIt(Invalid) {}
11.167 - InEdgeIt(const StaticGraphSkeleton &, Node) {}
11.168 + InEdgeIt() { }
11.169 + /// Copy constructor.
11.170 + InEdgeIt(const InEdgeIt&) { }
11.171 + /// Initialize the iterator to be invalid.
11.172 + InEdgeIt(Invalid) { }
11.173 + /// .
11.174 + InEdgeIt(const StaticGraphSkeleton&, const Node&) { }
11.175 + /// .
11.176 + InEdgeIt(const StaticGraphSkeleton&, const Edge&) { }
11.177 + /// Assign the iterator to the next inedge of the corresponding node.
11.178 + InEdgeIt& operator++() { return *this; }
11.179 };
11.180 // class SymEdgeIt : public Edge {};
11.181
11.182 @@ -166,19 +190,25 @@
11.183
11.184 /// This iterator goes through each edge of a graph.
11.185 /// Its usage is quite simple, for example you can count the number
11.186 - /// of edges in a graph \c G of type \c Graph as follows:
11.187 + /// of edges in a graph \c g of type \c Graph as follows:
11.188 /// \code
11.189 - ///int count=0;
11.190 - ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
11.191 + /// int count=0;
11.192 + /// for(Graph::EdgeIt e(g); g.valid(e); ++e) ++count;
11.193 /// \endcode
11.194 class EdgeIt : public Edge {
11.195 public:
11.196 /// @warning The default constructor sets the iterator
11.197 /// to an undefined value.
11.198 - EdgeIt() {}
11.199 - /// Initialize the iterator to be invalid
11.200 - EdgeIt(Invalid) {}
11.201 - EdgeIt(const StaticGraphSkeleton &) {}
11.202 + EdgeIt() { }
11.203 + /// Copy constructor.
11.204 + EdgeIt(const EdgeIt&) { }
11.205 + /// Initialize the iterator to be invalid.
11.206 + EdgeIt(Invalid) { }
11.207 + /// .
11.208 + EdgeIt(const StaticGraphSkeleton&) { }
11.209 + /// .
11.210 + EdgeIt(const StaticGraphSkeleton&, const Edge&) { }
11.211 + EdgeIt& operator++() { return *this; }
11.212 };
11.213
11.214 /// First node of the graph.
11.215 @@ -186,15 +216,15 @@
11.216 /// \retval i the first node.
11.217 /// \return the first node.
11.218 ///
11.219 - NodeIt &first(NodeIt &i) const { return i;}
11.220 + NodeIt& first(NodeIt& i) const { return i; }
11.221
11.222 /// The first incoming edge.
11.223 - InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
11.224 + InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
11.225 /// The first outgoing edge.
11.226 - OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
11.227 - // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
11.228 + OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
11.229 + // SymEdgeIt& first(SymEdgeIt&, Node) const { return i; }
11.230 /// The first edge of the Graph.
11.231 - EdgeIt &first(EdgeIt &i) const { return i;}
11.232 + EdgeIt& first(EdgeIt& i) const { return i; }
11.233
11.234 // Node getNext(Node) const {}
11.235 // InEdgeIt getNext(InEdgeIt) const {}
11.236 @@ -203,14 +233,14 @@
11.237 // EdgeIt getNext(EdgeIt) const {}
11.238
11.239 /// Go to the next node.
11.240 - NodeIt &next(NodeIt &i) const { return i;}
11.241 + NodeIt& next(NodeIt& i) const { return i; }
11.242 /// Go to the next incoming edge.
11.243 - InEdgeIt &next(InEdgeIt &i) const { return i;}
11.244 + InEdgeIt& next(InEdgeIt& i) const { return i; }
11.245 /// Go to the next outgoing edge.
11.246 - OutEdgeIt &next(OutEdgeIt &i) const { return i;}
11.247 - //SymEdgeIt &next(SymEdgeIt &) const {}
11.248 + OutEdgeIt& next(OutEdgeIt& i) const { return i; }
11.249 + //SymEdgeIt& next(SymEdgeIt&) const { }
11.250 /// Go to the next edge.
11.251 - EdgeIt &next(EdgeIt &i) const { return i;}
11.252 + EdgeIt& next(EdgeIt& i) const { return i; }
11.253
11.254 ///Gives back the head node of an edge.
11.255 Node head(Edge) const { return INVALID; }
11.256 @@ -229,33 +259,32 @@
11.257
11.258 ///\todo Maybe, it would be better if iterator converted to
11.259 ///bool directly, as Jacint prefers.
11.260 - bool valid(const Node&) const { return true;}
11.261 + bool valid(const Node&) const { return true; }
11.262 /// Checks if an edge iterator is valid
11.263
11.264 ///\todo Maybe, it would be better if iterator converted to
11.265 ///bool directly, as Jacint prefers.
11.266 - bool valid(const Edge&) const { return true;}
11.267 + bool valid(const Edge&) const { return true; }
11.268
11.269 ///Gives back the \e id of a node.
11.270
11.271 ///\warning Not all graph structures provide this feature.
11.272 ///
11.273 - int id(const Node&) const { return 0;}
11.274 + int id(const Node&) const { return 0; }
11.275 ///Gives back the \e id of an edge.
11.276
11.277 ///\warning Not all graph structures provide this feature.
11.278 ///
11.279 - int id(const Edge&) const { return 0;}
11.280 + int id(const Edge&) const { return 0; }
11.281
11.282 /// Resets the graph.
11.283
11.284 /// This function deletes all edges and nodes of the graph.
11.285 /// It also frees the memory allocated to store them.
11.286 - void clear() {}
11.287 + void clear() { }
11.288
11.289 - int nodeNum() const { return 0;}
11.290 - int edgeNum() const { return 0;}
11.291 -
11.292 + int nodeNum() const { return 0; }
11.293 + int edgeNum() const { return 0; }
11.294
11.295
11.296 ///Reference map of the nodes to type \c T.
11.297 @@ -270,16 +299,14 @@
11.298 {
11.299 public:
11.300
11.301 - class ReferenceMap<Node,T>;
11.302 -
11.303 - NodeMap(const StaticGraphSkeleton &) {}
11.304 - NodeMap(const StaticGraphSkeleton &, T) {}
11.305 + NodeMap(const StaticGraphSkeleton&) { }
11.306 + NodeMap(const StaticGraphSkeleton&, T) { }
11.307
11.308 ///Copy constructor
11.309 - template<typename TT> NodeMap(const NodeMap<TT> &) {}
11.310 + template<typename TT> NodeMap(const NodeMap<TT>&) { }
11.311 ///Assignment operator
11.312 - template<typename TT> NodeMap &operator=(const NodeMap<TT> &)
11.313 - {return *this;}
11.314 + template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
11.315 + { return *this; }
11.316 };
11.317
11.318 ///Reference map of the edges to type \c T.
11.319 @@ -295,14 +322,14 @@
11.320 typedef T ValueType;
11.321 typedef Edge KeyType;
11.322
11.323 - EdgeMap(const StaticGraphSkeleton &) {}
11.324 - EdgeMap(const StaticGraphSkeleton &, T ) {}
11.325 + EdgeMap(const StaticGraphSkeleton&) { }
11.326 + EdgeMap(const StaticGraphSkeleton&, T) { }
11.327
11.328 ///Copy constructor
11.329 - template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
11.330 + template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
11.331 ///Assignment operator
11.332 - template<typename TT> EdgeMap &operator=(const EdgeMap<TT> &)
11.333 - {return *this;}
11.334 + template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
11.335 + { return *this; }
11.336 };
11.337 };
11.338
11.339 @@ -317,31 +344,31 @@
11.340 {
11.341 public:
11.342 /// Defalult constructor.
11.343 - GraphSkeleton() {}
11.344 + GraphSkeleton() { }
11.345 ///Copy consructor.
11.346
11.347 ///\todo It is not clear, what we expect from a copy constructor.
11.348 ///E.g. How to assign the nodes/edges to each other? What about maps?
11.349 - GraphSkeleton(const GraphSkeleton &G) {}
11.350 + GraphSkeleton(const GraphSkeleton&) { }
11.351
11.352 ///Add a new node to the graph.
11.353
11.354 /// \return the new node.
11.355 ///
11.356 - Node addNode() { return INVALID;}
11.357 + Node addNode() { return INVALID; }
11.358 ///Add a new edge to the graph.
11.359
11.360 ///Add a new edge to the graph with tail node \c tail
11.361 ///and head node \c head.
11.362 ///\return the new edge.
11.363 - Edge addEdge(Node, Node) { return INVALID;}
11.364 + Edge addEdge(Node, Node) { return INVALID; }
11.365
11.366 /// Resets the graph.
11.367
11.368 /// This function deletes all edges and nodes of the graph.
11.369 /// It also frees the memory allocated to store them.
11.370 /// \todo It might belong to \c EraseableGraphSkeleton.
11.371 - void clear() {}
11.372 + void clear() { }
11.373 };
11.374
11.375 /// An empty eraseable graph class.
11.376 @@ -352,14 +379,14 @@
11.377 {
11.378 public:
11.379 /// Deletes a node.
11.380 - void erase(Node n) {}
11.381 + void erase(Node n) { }
11.382 /// Deletes an edge.
11.383 - void erase(Edge e) {}
11.384 + void erase(Edge e) { }
11.385
11.386 /// Defalult constructor.
11.387 - EraseableGraphSkeleton() {}
11.388 + EraseableGraphSkeleton() { }
11.389 ///Copy consructor.
11.390 - EraseableGraphSkeleton(const GraphSkeleton &G) {}
11.391 + EraseableGraphSkeleton(const GraphSkeleton&) { }
11.392 };
11.393
11.394 // @}
12.1 --- a/src/hugo/smart_graph.h Wed Aug 25 18:55:57 2004 +0000
12.2 +++ b/src/hugo/smart_graph.h Mon Aug 30 12:01:47 2004 +0000
12.3 @@ -121,12 +121,6 @@
12.4 Node tail(Edge e) const { return edges[e.n].tail; }
12.5 Node head(Edge e) const { return edges[e.n].head; }
12.6
12.7 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
12.8 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
12.9 -
12.10 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
12.11 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
12.12 -
12.13 NodeIt& first(NodeIt& v) const {
12.14 v=NodeIt(*this); return v; }
12.15 EdgeIt& first(EdgeIt& e) const {
12.16 @@ -136,41 +130,6 @@
12.17 InEdgeIt& first(InEdgeIt& e, const Node v) const {
12.18 e=InEdgeIt(*this,v); return e; }
12.19
12.20 -// template< typename It >
12.21 -// It first() const { It e; first(e); return e; }
12.22 -
12.23 -// template< typename It >
12.24 -// It first(Node v) const { It e; first(e,v); return e; }
12.25 -
12.26 - static bool valid(Edge e) { return e.n!=-1; }
12.27 - static bool valid(Node n) { return n.n!=-1; }
12.28 -
12.29 - ///\deprecated Use
12.30 - ///\code
12.31 - /// e=INVALID;
12.32 - ///\endcode
12.33 - ///instead.
12.34 - static void setInvalid(Edge &e) { e.n=-1; }
12.35 - ///\deprecated Use
12.36 - ///\code
12.37 - /// e=INVALID;
12.38 - ///\endcode
12.39 - ///instead.
12.40 - static void setInvalid(Node &n) { n.n=-1; }
12.41 -
12.42 - template <typename It> It getNext(It it) const
12.43 - { It tmp(it); return next(tmp); }
12.44 -
12.45 - NodeIt& next(NodeIt& it) const {
12.46 - it.n=(it.n+2)%(nodes.size()+1)-1;
12.47 - return it;
12.48 - }
12.49 - OutEdgeIt& next(OutEdgeIt& it) const
12.50 - { it.n=edges[it.n].next_out; return it; }
12.51 - InEdgeIt& next(InEdgeIt& it) const
12.52 - { it.n=edges[it.n].next_in; return it; }
12.53 - EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
12.54 -
12.55 static int id(Node v) { return v.n; }
12.56 static int id(Edge e) { return e.n; }
12.57
12.58 @@ -197,6 +156,22 @@
12.59 return e;
12.60 }
12.61
12.62 + /// Finds an edge between two nodes.
12.63 +
12.64 + /// Finds an edge from node \c u to node \c v.
12.65 + ///
12.66 + /// If \c prev is \ref INVALID (this is the default value), then
12.67 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
12.68 + /// the next edge from \c u to \c v after \c prev.
12.69 + /// \return The found edge or INVALID if there is no such an edge.
12.70 + Edge findEdge(Node u,Node v, Edge prev = INVALID)
12.71 + {
12.72 + int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
12.73 + while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
12.74 + prev.n=e;
12.75 + return prev;
12.76 + }
12.77 +
12.78 void clear() {nodes.clear();edges.clear();}
12.79
12.80 class Node {
12.81 @@ -218,16 +193,24 @@
12.82 bool operator==(const Node i) const {return n==i.n;}
12.83 bool operator!=(const Node i) const {return n!=i.n;}
12.84 bool operator<(const Node i) const {return n<i.n;}
12.85 + // ///Validity check
12.86 + // operator bool() { return n!=-1; }
12.87 };
12.88
12.89 class NodeIt : public Node {
12.90 + const SmartGraph *G;
12.91 friend class SmartGraph;
12.92 public:
12.93 NodeIt() : Node() { }
12.94 + NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }
12.95 NodeIt(Invalid i) : Node(i) { }
12.96 - NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
12.97 - ///\todo Undocumented conversion Node -\> NodeIt.
12.98 - NodeIt(const SmartGraph& G, const Node &n) : Node(n) { }
12.99 + NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }
12.100 + NodeIt &operator++() {
12.101 + n=(n+2)%(G->nodes.size()+1)-1;
12.102 + return *this;
12.103 + }
12.104 +// ///Validity check
12.105 +// operator bool() { return Node::operator bool(); }
12.106 };
12.107
12.108 class Edge {
12.109 @@ -257,36 +240,54 @@
12.110 ///\bug This is a workaround until somebody tells me how to
12.111 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
12.112 int &idref() {return n;}
12.113 - const int &idref() const {return n;}
12.114 - };
12.115 + const int &idref() const {return n;}
12.116 +// ///Validity check
12.117 +// operator bool() { return n!=-1; }
12.118 + };
12.119
12.120 class EdgeIt : public Edge {
12.121 + const SmartGraph *G;
12.122 friend class SmartGraph;
12.123 public:
12.124 - EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
12.125 + EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
12.126 + EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
12.127 EdgeIt (Invalid i) : Edge(i) { }
12.128 EdgeIt() : Edge() { }
12.129 ///\bug This is a workaround until somebody tells me how to
12.130 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
12.131 int &idref() {return n;}
12.132 + EdgeIt &operator++() { --n; return *this; }
12.133 +// ///Validity check
12.134 +// operator bool() { return Edge::operator bool(); }
12.135 };
12.136
12.137 class OutEdgeIt : public Edge {
12.138 + const SmartGraph *G;
12.139 friend class SmartGraph;
12.140 public:
12.141 OutEdgeIt() : Edge() { }
12.142 + OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
12.143 OutEdgeIt (Invalid i) : Edge(i) { }
12.144
12.145 - OutEdgeIt(const SmartGraph& G,const Node v)
12.146 - : Edge(G.nodes[v.n].first_out) {}
12.147 + OutEdgeIt(const SmartGraph& _G,const Node v)
12.148 + : Edge(_G.nodes[v.n].first_out), G(&_G) {}
12.149 + OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
12.150 +// ///Validity check
12.151 +// operator bool() { return Edge::operator bool(); }
12.152 };
12.153
12.154 class InEdgeIt : public Edge {
12.155 + const SmartGraph *G;
12.156 friend class SmartGraph;
12.157 public:
12.158 InEdgeIt() : Edge() { }
12.159 + InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
12.160 InEdgeIt (Invalid i) : Edge(i) { }
12.161 - InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
12.162 + InEdgeIt(const SmartGraph& _G,Node v)
12.163 + : Edge(_G.nodes[v.n].first_in), G(&_G) { }
12.164 + InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
12.165 +// ///Validity check
12.166 +// operator bool() { return Edge::operator bool(); }
12.167 };
12.168
12.169 template <typename T> class NodeMap : public DynMapBase<Node>
13.1 --- a/src/hugo/unionfind.h Wed Aug 25 18:55:57 2004 +0000
13.2 +++ b/src/hugo/unionfind.h Mon Aug 30 12:01:47 2004 +0000
13.3 @@ -5,6 +5,9 @@
13.4 //!\ingroup auxdat
13.5 //!\file
13.6 //!\brief Union-Find data structures.
13.7 +//!
13.8 +//!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but
13.9 +//!fails to run (Segmentation fault).
13.10
13.11
13.12 #include <vector>
14.1 --- a/src/test/Makefile.am Wed Aug 25 18:55:57 2004 +0000
14.2 +++ b/src/test/Makefile.am Mon Aug 30 12:01:47 2004 +0000
14.3 @@ -2,14 +2,17 @@
14.4
14.5 noinst_HEADERS = test_tools.h
14.6
14.7 -check_PROGRAMS = graph_test dijkstra_test time_measure_test error_test xy_test \
14.8 - test_tools_pass test_tools_fail
14.9 +check_PROGRAMS = graph_test dijkstra_test bfs_test time_measure_test \
14.10 + error_test xy_test \
14.11 + unionfind_test test_tools_pass test_tools_fail
14.12
14.13 TESTS = $(check_PROGRAMS)
14.14 XFAIL_TESTS = test_tools_fail
14.15
14.16 graph_test_SOURCES = graph_test.cc
14.17 dijkstra_test_SOURCES = dijkstra_test.cc
14.18 +bfs_test_SOURCES = bfs_test.cc
14.19 +unionfind_test_SOURCES = unionfind_test.cc
14.20 time_measure_test_SOURCES = time_measure_test.cc
14.21 error_test_SOURCES = error_test.cc
14.22 xy_test_SOURCES = xy_test.cc
15.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
15.2 +++ b/src/test/bfs_test.cc Mon Aug 30 12:01:47 2004 +0000
15.3 @@ -0,0 +1,89 @@
15.4 +#include "test_tools.h"
15.5 +#include <hugo/smart_graph.h>
15.6 +#include <hugo/bfs.h>
15.7 +
15.8 +using namespace hugo;
15.9 +
15.10 +const int PET_SIZE =5;
15.11 +
15.12 +
15.13 +void check_Bfs_SmartGraph_Compile()
15.14 +{
15.15 + typedef int VType;
15.16 + typedef SmartGraph Graph;
15.17 +
15.18 + typedef Graph::Edge Edge;
15.19 + typedef Graph::Node Node;
15.20 + typedef Graph::EdgeIt EdgeIt;
15.21 + typedef Graph::NodeIt NodeIt;
15.22 + typedef Graph::EdgeMap<VType> LengthMap;
15.23 +
15.24 + typedef Bfs<Graph> BType;
15.25 +
15.26 + Graph G;
15.27 + Node n;
15.28 + Edge e;
15.29 + VType l;
15.30 + bool b;
15.31 + BType::DistMap d(G);
15.32 + BType::PredMap p(G);
15.33 + BType::PredNodeMap pn(G);
15.34 + LengthMap cap(G);
15.35 +
15.36 + BType bfs_test(G);
15.37 +
15.38 + bfs_test.run(n);
15.39 +
15.40 + l = bfs_test.dist(n);
15.41 + e = bfs_test.pred(n);
15.42 + n = bfs_test.predNode(n);
15.43 + d = bfs_test.distMap();
15.44 + p = bfs_test.predMap();
15.45 + pn = bfs_test.predNodeMap();
15.46 + b = bfs_test.reached(n);
15.47 +
15.48 +}
15.49 +
15.50 +int main()
15.51 +{
15.52 +
15.53 + typedef SmartGraph Graph;
15.54 +
15.55 + typedef Graph::Edge Edge;
15.56 + typedef Graph::Node Node;
15.57 + typedef Graph::EdgeIt EdgeIt;
15.58 + typedef Graph::NodeIt NodeIt;
15.59 + typedef Graph::EdgeMap<int> LengthMap;
15.60 +
15.61 + Graph G;
15.62 + Node s, t;
15.63 + PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
15.64 +
15.65 + s=ps.outer[2];
15.66 + t=ps.inner[0];
15.67 +
15.68 + Bfs<Graph> bfs_test(G);
15.69 + bfs_test.run(s);
15.70 +
15.71 + check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
15.72 +
15.73 +
15.74 + for(EdgeIt e(G); e==INVALID; ++e) {
15.75 + Node u=G.tail(e);
15.76 + Node v=G.head(e);
15.77 + check( !bfs_test.reached(u) ||
15.78 + (bfs_test.dist(v) > bfs_test.dist(u)+1),
15.79 + "Wrong output.");
15.80 + }
15.81 +
15.82 + ///\bug This works only for integer lengths
15.83 + for(NodeIt v(G); v==INVALID; ++v)
15.84 + if ( bfs_test.reached(v) ) {
15.85 + Edge e=bfs_test.pred(v);
15.86 + Node u=G.tail(e);
15.87 + check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
15.88 + "Bad shortest path tree edge! Difference: "
15.89 + << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
15.90 + - 1));
15.91 + }
15.92 +}
16.1 --- a/src/test/dijkstra_test.cc Wed Aug 25 18:55:57 2004 +0000
16.2 +++ b/src/test/dijkstra_test.cc Mon Aug 30 12:01:47 2004 +0000
16.3 @@ -75,7 +75,7 @@
16.4 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
16.5
16.6
16.7 - for(EdgeIt e(G); G.valid(e); G.next(e)) {
16.8 + for(EdgeIt e(G); e==INVALID; ++e) {
16.9 Node u=G.tail(e);
16.10 Node v=G.head(e);
16.11 check( !dijkstra_test.reached(u) ||
16.12 @@ -86,7 +86,7 @@
16.13 }
16.14
16.15 ///\bug This works only for integer lengths
16.16 - for(NodeIt v(G); G.valid(v); G.next(v))
16.17 + for(NodeIt v(G); v==INVALID; ++v)
16.18 if ( dijkstra_test.reached(v) ) {
16.19 Edge e=dijkstra_test.pred(v);
16.20 Node u=G.tail(e);
17.1 --- a/src/test/graph_test.cc Wed Aug 25 18:55:57 2004 +0000
17.2 +++ b/src/test/graph_test.cc Mon Aug 30 12:01:47 2004 +0000
17.3 @@ -6,12 +6,15 @@
17.4
17.5 #include"test_tools.h"
17.6
17.7 -/*
17.8 +/**
17.9 +\file
17.10 This test makes consistency checks of list graph structures.
17.11
17.12 -G.addNode(), G.addEdge(), G.valid(), G.tail(), G.head()
17.13 +G.addNode(), G.addEdge(), G.tail(), G.head()
17.14
17.15 \todo Checks for empty graphs and isolated points.
17.16 +\todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt}
17.17 +conversion.
17.18 */
17.19
17.20 using namespace hugo;
17.21 @@ -29,82 +32,100 @@
17.22 {
17.23 Node i; Node j(i); Node k(INVALID);
17.24 i=j;
17.25 - bool b=G.valid(i); b=b;
17.26 + // bool b=G.valid(i); b=b;
17.27 + bool b; b=b;
17.28 + b=(i==INVALID); b=(i!=INVALID);
17.29 b=(i==j); b=(i!=j); b=(i<j);
17.30 }
17.31 {
17.32 NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
17.33 i=j;
17.34 j=G.first(i);
17.35 - j=G.next(i);
17.36 - bool b=G.valid(i); b=b;
17.37 + j=++i;
17.38 + // bool b=G.valid(i); b=b;
17.39 + bool b; b=b;
17.40 + b=(i==INVALID); b=(i!=INVALID);
17.41 Node n(i);
17.42 n=i;
17.43 b=(i==j); b=(i!=j); b=(i<j);
17.44 + //Node ->NodeIt conversion
17.45 + NodeIt ni(G,n);
17.46 }
17.47 {
17.48 Edge i; Edge j(i); Edge k(INVALID);
17.49 i=j;
17.50 - bool b=G.valid(i); b=b;
17.51 + // bool b=G.valid(i); b=b;
17.52 + bool b; b=b;
17.53 + b=(i==INVALID); b=(i!=INVALID);
17.54 b=(i==j); b=(i!=j); b=(i<j);
17.55 }
17.56 {
17.57 EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
17.58 i=j;
17.59 j=G.first(i);
17.60 - j=G.next(i);
17.61 - bool b=G.valid(i); b=b;
17.62 + j=++i;
17.63 + // bool b=G.valid(i); b=b;
17.64 + bool b; b=b;
17.65 + b=(i==INVALID); b=(i!=INVALID);
17.66 Edge e(i);
17.67 e=i;
17.68 b=(i==j); b=(i!=j); b=(i<j);
17.69 + //Edge ->EdgeIt conversion
17.70 + EdgeIt ei(G,e);
17.71 }
17.72 {
17.73 Node n;
17.74 InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
17.75 i=j;
17.76 j=G.first(i,n);
17.77 - j=G.next(i);
17.78 - bool b=G.valid(i); b=b;
17.79 + j=++i;
17.80 + // bool b=G.valid(i); b=b;
17.81 + bool b; b=b;
17.82 + b=(i==INVALID); b=(i!=INVALID);
17.83 Edge e(i);
17.84 e=i;
17.85 b=(i==j); b=(i!=j); b=(i<j);
17.86 + //Edge ->InEdgeIt conversion
17.87 + InEdgeIt ei(G,e);
17.88 }
17.89 {
17.90 Node n;
17.91 OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
17.92 i=j;
17.93 j=G.first(i,n);
17.94 - j=G.next(i);
17.95 - bool b=G.valid(i); b=b;
17.96 + j=++i;
17.97 + // bool b=G.valid(i); b=b;
17.98 + bool b; b=b;
17.99 + b=(i==INVALID); b=(i!=INVALID);
17.100 Edge e(i);
17.101 e=i;
17.102 b=(i==j); b=(i!=j); b=(i<j);
17.103 + //Edge ->OutEdgeIt conversion
17.104 + OutEdgeIt ei(G,e);
17.105 }
17.106 -
17.107 - Node n,m;
17.108 - n=m=INVALID;
17.109 - Edge e;
17.110 - e=INVALID;
17.111 - n=G.tail(e);
17.112 - n=G.head(e);
17.113 -
17.114 - //aNode, bNode ?
17.115 -
17.116 + {
17.117 + Node n,m;
17.118 + n=m=INVALID;
17.119 + Edge e;
17.120 + e=INVALID;
17.121 + n=G.tail(e);
17.122 + n=G.head(e);
17.123 + }
17.124 // id tests
17.125 - { int i=G.id(n); i=i; }
17.126 - { int i=G.id(e); i=i; }
17.127 -
17.128 - // G.clear();
17.129 -
17.130 + { Node n; int i=G.id(n); i=i; }
17.131 + { Edge e; int i=G.id(e); i=i; }
17.132 //NodeMap tests
17.133 {
17.134 Node k;
17.135 typename Graph::template NodeMap<int> m(G);
17.136 - typename Graph::template NodeMap<int> const &cm = m; //Const map
17.137 + //Const map
17.138 + typename Graph::template NodeMap<int> const &cm = m;
17.139 //Inicialize with default value
17.140 typename Graph::template NodeMap<int> mdef(G,12);
17.141 - typename Graph::template NodeMap<int> mm(cm); //Copy
17.142 - typename Graph::template NodeMap<double> dm(cm); //Copy from another type
17.143 + //Copy
17.144 + typename Graph::template NodeMap<int> mm(cm);
17.145 + //Copy from another type
17.146 + typename Graph::template NodeMap<double> dm(cm);
17.147 int v;
17.148 v=m[k]; m[k]=v; m.set(k,v);
17.149 v=cm[k];
17.150 @@ -160,7 +181,6 @@
17.151 dm=cm; //Copy from another type
17.152 m=dm; //Copy to another type
17.153 }
17.154 -
17.155 }
17.156
17.157 template<class Graph> void checkCompile(Graph &G)
17.158 @@ -177,8 +197,36 @@
17.159 Node n,m;
17.160 n=G.addNode();
17.161 m=G.addNode();
17.162 + Edge e;
17.163 + e=G.addEdge(n,m);
17.164
17.165 - G.addEdge(n,m);
17.166 + // G.clear();
17.167 +}
17.168 +
17.169 +template<class Graph> void checkCompileErase(Graph &G)
17.170 +{
17.171 + typedef typename Graph::Node Node;
17.172 + typedef typename Graph::Edge Edge;
17.173 + Node n;
17.174 + Edge e;
17.175 + G.erase(n);
17.176 + G.erase(e);
17.177 +}
17.178 +
17.179 +template<class Graph> void checkCompileEraseEdge(Graph &G)
17.180 +{
17.181 + typedef typename Graph::Edge Edge;
17.182 + Edge e;
17.183 + G.erase(e);
17.184 +}
17.185 +
17.186 +template<class Graph> void checkCompileFindEdge(Graph &G)
17.187 +{
17.188 + typedef typename Graph::NodeIt Node;
17.189 + typedef typename Graph::NodeIt NodeIt;
17.190 +
17.191 + G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
17.192 + G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));
17.193 }
17.194
17.195
17.196 @@ -186,10 +234,10 @@
17.197 {
17.198 typename Graph::NodeIt n(G);
17.199 for(int i=0;i<nn;i++) {
17.200 - check(G.valid(n),"Wrong Node list linking.");
17.201 - G.next(n);
17.202 + check(n!=INVALID,"Wrong Node list linking.");
17.203 + ++n;
17.204 }
17.205 - check(!G.valid(n),"Wrong Node list linking.");
17.206 + check(n==INVALID,"Wrong Node list linking.");
17.207 }
17.208
17.209 template<class Graph> void checkEdgeList(Graph &G, int nn)
17.210 @@ -198,10 +246,10 @@
17.211
17.212 EdgeIt e(G);
17.213 for(int i=0;i<nn;i++) {
17.214 - check(G.valid(e),"Wrong Edge list linking.");
17.215 - G.next(e);
17.216 + check(e!=INVALID,"Wrong Edge list linking.");
17.217 + ++e;
17.218 }
17.219 - check(!G.valid(e),"Wrong Edge list linking.");
17.220 + check(e==INVALID,"Wrong Edge list linking.");
17.221 }
17.222
17.223 template<class Graph> void checkOutEdgeList(Graph &G,
17.224 @@ -210,25 +258,27 @@
17.225 {
17.226 typename Graph::OutEdgeIt e(G,n);
17.227 for(int i=0;i<nn;i++) {
17.228 - check(G.valid(e),"Wrong OutEdge list linking.");
17.229 - G.next(e);
17.230 + check(e!=INVALID,"Wrong OutEdge list linking.");
17.231 + ++e;
17.232 }
17.233 - check(!G.valid(e),"Wrong OutEdge list linking.");
17.234 + check(e==INVALID,"Wrong OutEdge list linking.");
17.235 }
17.236
17.237 template<class Graph> void checkInEdgeList(Graph &G,
17.238 - typename Graph::Node n,
17.239 - int nn)
17.240 + typename Graph::Node n,
17.241 + int nn)
17.242 {
17.243 typename Graph::InEdgeIt e(G,n);
17.244 for(int i=0;i<nn;i++) {
17.245 - check(G.valid(e),"Wrong InEdge list linking.");
17.246 - G.next(e);
17.247 + check(e!=INVALID,"Wrong InEdge list linking.");
17.248 + ++e;
17.249 }
17.250 - check(!G.valid(e),"Wrong InEdge list linking.");
17.251 + check(e==INVALID,"Wrong InEdge list linking.");
17.252 }
17.253
17.254 -//Checks head(), tail() as well;
17.255 +///\file
17.256 +///\todo Checks head(), tail() as well;
17.257 +
17.258 template<class Graph> void bidirPetersen(Graph &G)
17.259 {
17.260 typedef typename Graph::Edge Edge;
17.261 @@ -238,7 +288,7 @@
17.262
17.263 std::vector<Edge> ee;
17.264
17.265 - for(EdgeIt e(G);G.valid(e);G.next(e)) ee.push_back(e);
17.266 + for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
17.267
17.268 for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
17.269 G.addEdge(G.head(*p),G.tail(*p));
17.270 @@ -254,25 +304,52 @@
17.271 checkNodeList(G,10);
17.272 checkEdgeList(G,30);
17.273
17.274 - for(NodeIt n(G);G.valid(n);G.next(n)) {
17.275 + for(NodeIt n(G);n!=INVALID;++n) {
17.276 checkInEdgeList(G,n,3);
17.277 checkOutEdgeList(G,n,3);
17.278 - G.next(n);
17.279 + ++n;
17.280 }
17.281 }
17.282
17.283 -template
17.284 +//Compile GraphSkeleton
17.285 +template
17.286 void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);
17.287 template void checkCompile<GraphSkeleton>(GraphSkeleton &);
17.288 +template
17.289 +void checkCompileErase<EraseableGraphSkeleton>(EraseableGraphSkeleton &);
17.290
17.291 +//Compile SmartGraph
17.292 template void checkCompile<SmartGraph>(SmartGraph &);
17.293 +//Compile SymSmartGraph
17.294 template void checkCompile<SymSmartGraph>(SymSmartGraph &);
17.295 +
17.296 +//Compile ListGraph
17.297 template void checkCompile<ListGraph>(ListGraph &);
17.298 +template void checkCompileErase<ListGraph>(ListGraph &);
17.299 +template void checkCompileFindEdge<ListGraph>(ListGraph &);
17.300 +
17.301 +//Compile SymListGraph
17.302 template void checkCompile<SymListGraph>(SymListGraph &);
17.303 +template void checkCompileErase<SymListGraph>(SymListGraph &);
17.304 +template void checkCompileFindEdge<SymListGraph>(SymListGraph &);
17.305 +
17.306 +//Compile FullGraph
17.307 template void checkCompileStaticGraph<FullGraph>(FullGraph &);
17.308 +template void checkCompileFindEdge<FullGraph>(FullGraph &);
17.309
17.310 +//Compile EdgeSet <ListGraph>
17.311 template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
17.312 +template
17.313 +void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
17.314 +template
17.315 +void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
17.316 +
17.317 +//Compile EdgeSet <NodeSet>
17.318 template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
17.319 +template
17.320 +void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
17.321 +template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
17.322 +
17.323
17.324 int main()
17.325 {
17.326 @@ -299,8 +376,9 @@
17.327 checkPetersen(G);
17.328 }
17.329
17.330 - //\todo map tests.
17.331 - //\todo copy constr tests.
17.332 + ///\file
17.333 + ///\todo map tests.
17.334 + ///\todo copy constr tests.
17.335
17.336 std::cout << __FILE__ ": All tests passed.\n";
17.337
18.1 --- a/src/test/test_tools.h Wed Aug 25 18:55:57 2004 +0000
18.2 +++ b/src/test/test_tools.h Mon Aug 30 12:01:47 2004 +0000
18.3 @@ -20,6 +20,8 @@
18.4 ///\code check(0==1,"This is obviously false.");\endcode will
18.5 ///print this (and then exits).
18.6 ///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim
18.7 +///
18.8 +///\todo It should be in \c error.h
18.9 #define check(rc, msg) \
18.10 if(!(rc)) { \
18.11 std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
19.1 --- a/src/test/unionfind_test.cc Wed Aug 25 18:55:57 2004 +0000
19.2 +++ b/src/test/unionfind_test.cc Mon Aug 30 12:01:47 2004 +0000
19.3 @@ -2,19 +2,11 @@
19.4
19.5 #include <hugo/maps.h>
19.6 #include <hugo/unionfind.h>
19.7 +#include "test_tools.h"
19.8
19.9 using namespace hugo;
19.10 using namespace std;
19.11
19.12 -bool passed = true;
19.13 -
19.14 -void check(bool rc) {
19.15 - passed = passed && rc;
19.16 - if(!rc) {
19.17 - cout << "Test failed!" << endl;
19.18 - }
19.19 -}
19.20 -
19.21 template <typename T>
19.22 class BaseMap : public StdMap<int,T> {};
19.23
19.24 @@ -22,7 +14,7 @@
19.25
19.26 void print(UFE const &ufe) {
19.27 UFE::ClassIt cit;
19.28 - cout << "printing the classes of the structure:" << endl;
19.29 + cout << "Print the classes of the structure:" << endl;
19.30 int i = 1;
19.31 for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
19.32 cout << " " << i << " (" << cit << "):" << flush;
19.33 @@ -41,165 +33,160 @@
19.34 UFE::MapType base;
19.35 UFE U(base);
19.36
19.37 - print(U);
19.38 +// print(U);
19.39
19.40 - cout << "Inserting 1..." << endl;
19.41 + cout << "Insert 1..." << endl;
19.42 U.insert(1);
19.43 - print(U);
19.44 +// print(U);
19.45
19.46 - cout << "Inserting 2..." << endl;
19.47 + cout << "Insert 2..." << endl;
19.48 U.insert(2);
19.49 - print(U);
19.50 +// print(U);
19.51
19.52 - cout << "Joining 1 and 2..." << endl;
19.53 - check(U.join(1,2));
19.54 - print(U);
19.55 + cout << "Join 1 and 2..." << endl;
19.56 + check(U.join(1,2),"Test failed.");
19.57 +// print(U);
19.58
19.59 - cout << "Inserting 3, 4, 5, 6, 7..." << endl;
19.60 + cout << "Insert 3, 4, 5, 6, 7..." << endl;
19.61 U.insert(3);
19.62 U.insert(4);
19.63 U.insert(5);
19.64 U.insert(6);
19.65 U.insert(7);
19.66 - print (U);
19.67 +// print (U);
19.68
19.69 - cout << "Joining 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
19.70 - check(U.join(1,4));
19.71 - check(!U.join(2,4));
19.72 - check(U.join(3,5));
19.73 - print(U);
19.74 + cout << "Join 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
19.75 + check(U.join(1,4),"Test failed.");
19.76 + check(!U.join(2,4),"Test failed.");
19.77 + check(U.join(3,5),"Test failed.");
19.78 +// print(U);
19.79
19.80 - cout << "Inserting 8 to the component of 5 ..." << endl;
19.81 + cout << "Insert 8 to the component of 5 ..." << endl;
19.82 U.insert(8,5);
19.83 - print(U);
19.84 +// print(U);
19.85
19.86 - cout << "size of the class of 4: " << U.size(4) << endl;
19.87 - check(U.size(4) == 3);
19.88 - cout << "size of the class of 5: " << U.size(5) << endl;
19.89 - check(U.size(5) == 3);
19.90 - cout << "size of the class of 6: " << U.size(6) << endl;
19.91 - check(U.size(6) == 1);
19.92 - cout << "size of the class of 2: " << U.size(2) << endl;
19.93 - check(U.size(2) == 3);
19.94 + cout << "Size of the class of 4: " << U.size(4) << endl;
19.95 + check(U.size(4) == 3,"Test failed.");
19.96 + cout << "Size of the class of 5: " << U.size(5) << endl;
19.97 + check(U.size(5) == 3,"Test failed.");
19.98 + cout << "Size of the class of 6: " << U.size(6) << endl;
19.99 + check(U.size(6) == 1,"Test failed.");
19.100 + cout << "Size of the class of 2: " << U.size(2) << endl;
19.101 + check(U.size(2) == 3,"Test failed.");
19.102
19.103 - cout << "Inserting 9 ..." << endl;
19.104 + cout << "Insert 9 ..." << endl;
19.105 U.insert(9);
19.106 - print(U);
19.107 - cout << "Inserting 10 to the component of 9 ..." << endl;
19.108 +// print(U);
19.109 + cout << "Insert 10 to the component of 9 ..." << endl;
19.110 U.insert(10,9);
19.111 - print(U);
19.112 +// print(U);
19.113
19.114 - cout << "Joining 8 and 10..." << endl;
19.115 - check(U.join(8,10));
19.116 - print(U);
19.117 + cout << "Join 8 and 10..." << endl;
19.118 + check(U.join(8,10),"Test failed.");
19.119 +// print(U);
19.120
19.121 cout << "Move 9 to the class of 4 ..." << endl;
19.122 - check(U.move(9,4));
19.123 - print(U);
19.124 + check(U.move(9,4),"Test failed.");
19.125 +// print(U);
19.126
19.127 cout << "Move 9 to the class of 2 ..." << endl;
19.128 - check(!U.move(9,2));
19.129 - print(U);
19.130 + check(!U.move(9,2),"Test failed.");
19.131 +// print(U);
19.132
19.133 - cout << "size of the class of 4: " << U.size(4) << endl;
19.134 - check(U.size(4) == 4);
19.135 - cout << "size of the class of 9: " << U.size(9) << endl;
19.136 - check(U.size(9) == 4);
19.137 + cout << "Size of the class of 4: " << U.size(4) << endl;
19.138 + check(U.size(4) == 4,"Test failed.");
19.139 + cout << "Size of the class of 9: " << U.size(9) << endl;
19.140 + check(U.size(9) == 4,"Test failed.");
19.141
19.142 cout << "Move 5 to the class of 6 ..." << endl;
19.143 - check(U.move(5,6));
19.144 - print(U);
19.145 + check(U.move(5,6),"Test failed.");
19.146 +// print(U);
19.147
19.148 - cout << "size of the class of 5: " << U.size(5) << endl;
19.149 - check(U.size(5) == 2);
19.150 - cout << "size of the class of 8: " << U.size(8) << endl;
19.151 - check(U.size(8) == 3);
19.152 + cout << "Size of the class of 5: " << U.size(5) << endl;
19.153 + check(U.size(5) == 2,"Test failed.");
19.154 + cout << "Size of the class of 8: " << U.size(8) << endl;
19.155 + check(U.size(8) == 3,"Test failed.");
19.156
19.157 cout << "Move 7 to the class of 10 ..." << endl;
19.158 - check(U.move(7,10));
19.159 - print(U);
19.160 + check(U.move(7,10),"Test failed.");
19.161 +// print(U);
19.162
19.163 - cout << "size of the class of 7: " << U.size(7) << endl;
19.164 - check(U.size(7) == 4);
19.165 + cout << "Size of the class of 7: " << U.size(7) << endl;
19.166 + check(U.size(7) == 4,"Test failed.");
19.167
19.168 - cout <<"erase 9: " << endl;
19.169 + cout <<"Erase 9... " << endl;
19.170 U.erase(9);
19.171 - print(U);
19.172 +// print(U);
19.173
19.174 - cout <<"erase 1: " << endl;
19.175 + cout <<"Erase 1... " << endl;
19.176 U.erase(1);
19.177 - print(U);
19.178 +// print(U);
19.179
19.180 - cout << "size of the class of 4: " << U.size(4) << endl;
19.181 - check(U.size(4) == 2);
19.182 - cout << "size of the class of 2: " << U.size(2) << endl;
19.183 - check(U.size(2) == 2);
19.184 + cout << "Size of the class of 4: " << U.size(4) << endl;
19.185 + check(U.size(4) == 2,"Test failed.");
19.186 + cout << "Size of the class of 2: " << U.size(2) << endl;
19.187 + check(U.size(2) == 2,"Test failed.");
19.188
19.189
19.190 - cout <<"erase 1: " << endl;
19.191 + cout <<"Erase 1... " << endl;
19.192 U.erase(1);
19.193 - print(U);
19.194 +// print(U);
19.195
19.196 - cout <<"erase 6: " << endl;
19.197 + cout <<"Erase 6... " << endl;
19.198 U.erase(6);
19.199 - print(U);
19.200 +// print(U);
19.201
19.202 - cout << "split the class of 8: " << endl;
19.203 + cout << "Split the class of 8... " << endl;
19.204 U.split(8);
19.205 - print(U);
19.206 +// print(U);
19.207
19.208
19.209 - cout << "size of the class of 4: " << U.size(4) << endl;
19.210 - check(U.size(4) == 2);
19.211 - cout << "size of the class of 3: " << U.size(3) << endl;
19.212 - check(U.size(3) == 1);
19.213 - cout << "size of the class of 2: " << U.size(2) << endl;
19.214 - check(U.size(2) == 2);
19.215 + cout << "Size of the class of 4: " << U.size(4) << endl;
19.216 + check(U.size(4) == 2,"Test failed.");
19.217 + cout << "Size of the class of 3: " << U.size(3) << endl;
19.218 + check(U.size(3) == 1,"Test failed.");
19.219 + cout << "Size of the class of 2: " << U.size(2) << endl;
19.220 + check(U.size(2) == 2,"Test failed.");
19.221
19.222
19.223 - cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
19.224 - check(U.join(3,4));
19.225 - check(!U.join(2,4));
19.226 - print(U);
19.227 + cout << "Join 3 - 4 and 2 - 4 ..." << endl;
19.228 + check(U.join(3,4),"Test failed.");
19.229 + check(!U.join(2,4),"Test failed.");
19.230 +// print(U);
19.231
19.232
19.233 - cout << "size of the class of 4: " << U.size(4) << endl;
19.234 - check(U.size(4) == 3);
19.235 - cout << "size of the class of 3: " << U.size(3) << endl;
19.236 - check(U.size(3) == 3);
19.237 - cout << "size of the class of 2: " << U.size(2) << endl;
19.238 - check(U.size(2) == 3);
19.239 + cout << "Size of the class of 4: " << U.size(4) << endl;
19.240 + check(U.size(4) == 3,"Test failed.");
19.241 + cout << "Size of the class of 3: " << U.size(3) << endl;
19.242 + check(U.size(3) == 3,"Test failed.");
19.243 + cout << "Size of the class of 2: " << U.size(2) << endl;
19.244 + check(U.size(2) == 3,"Test failed.");
19.245
19.246 - cout << "makeRep(4)" << endl;
19.247 + cout << "makeRep(4)..." << endl;
19.248 U.makeRep(4);
19.249 - print(U);
19.250 - cout << "makeRep(3)" << endl;
19.251 +// print(U);
19.252 + cout << "makeRep(3)..." << endl;
19.253 U.makeRep(3);
19.254 - print(U);
19.255 - cout << "makeRep(2)" << endl;
19.256 +// print(U);
19.257 + cout << "makeRep(2)..." << endl;
19.258 U.makeRep(2);
19.259 - print(U);
19.260 +// print(U);
19.261
19.262 - cout << "size of the class of 4: " << U.size(4) << endl;
19.263 - check(U.size(4) == 3);
19.264 - cout << "size of the class of 3: " << U.size(3) << endl;
19.265 - check(U.size(3) == 3);
19.266 - cout << "size of the class of 2: " << U.size(2) << endl;
19.267 - check(U.size(2) == 3);
19.268 + cout << "Size of the class of 4: " << U.size(4) << endl;
19.269 + check(U.size(4) == 3,"Test failed.");
19.270 + cout << "Size of the class of 3: " << U.size(3) << endl;
19.271 + check(U.size(3) == 3,"Test failed.");
19.272 + cout << "Size of the class of 2: " << U.size(2) << endl;
19.273 + check(U.size(2) == 3,"Test failed.");
19.274
19.275
19.276 cout << "eraseClass 4 ..." << endl;
19.277 U.eraseClass(4);
19.278 - print(U);
19.279 +// print(U);
19.280
19.281 cout << "eraseClass 7 ..." << endl;
19.282 U.eraseClass(7);
19.283 - print(U);
19.284 +// print(U);
19.285
19.286 - cout << "done" << endl;
19.287 -
19.288 - cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
19.289 - << endl;
19.290 -
19.291 - return passed ? 0 : 1;
19.292 + cout << "done." << endl;
19.293 }
20.1 --- a/src/test/xy_test.cc Wed Aug 25 18:55:57 2004 +0000
20.2 +++ b/src/test/xy_test.cc Mon Aug 30 12:01:47 2004 +0000
20.3 @@ -7,7 +7,7 @@
20.4 int main()
20.5 {
20.6
20.7 - cout << "Testing classes xy and boundingbox." << endl;
20.8 + cout << "Testing classes `xy' and `boundingbox'." << endl;
20.9
20.10 typedef xy<int> XY;
20.11
20.12 @@ -33,10 +33,10 @@
20.13
20.14 typedef BoundingBox<int> BB;
20.15 BB doboz1;
20.16 - check(doboz1.empty(), "empty? Should be.");
20.17 + check(doboz1.empty(), "It should be empty.");
20.18
20.19 doboz1 += a;
20.20 - check(!doboz1.empty(), "empty? Should not be.");
20.21 + check(!doboz1.empty(), "It should not be empty.");
20.22 doboz1 += b;
20.23
20.24 check(doboz1.bottomLeft().x==1 &&
20.25 @@ -46,19 +46,19 @@
20.26 "added points to box");
20.27
20.28 seged.x=2;seged.y=3;
20.29 - check(doboz1.inside(seged),"Inside? It should be.");
20.30 + check(doboz1.inside(seged),"It should be inside.");
20.31
20.32 seged.x=1;seged.y=3;
20.33 - check(doboz1.inside(seged),"Inside? It should be.");
20.34 + check(doboz1.inside(seged),"It should be inside.");
20.35
20.36 seged.x=0;seged.y=3;
20.37 - check(!doboz1.inside(seged),"Inside? It should not be.");
20.38 + check(!doboz1.inside(seged),"It should not be inside.");
20.39
20.40 BB doboz2(seged);
20.41 check(!doboz2.empty(),
20.42 - "empty? Should not be. Constructed from 1 point.");
20.43 + "It should not be empty. Constructed from 1 point.");
20.44
20.45 doboz2 += doboz1;
20.46 check(doboz2.inside(seged),
20.47 - "Not inside? It should be. Incremented a box with an other.");
20.48 + "It should be inside. Incremented a box with an other.");
20.49 }
21.1 --- a/src/work/marci/bfs_dfs.h Wed Aug 25 18:55:57 2004 +0000
21.2 +++ b/src/work/marci/bfs_dfs.h Mon Aug 30 12:01:47 2004 +0000
21.3 @@ -60,8 +60,8 @@
21.4 if (bfs_queue.empty()) {
21.5 bfs_queue.push(s);
21.6 graph->first(actual_edge, s);
21.7 - if (graph->valid(actual_edge)) {
21.8 - Node w=graph->bNode(actual_edge);
21.9 + if (actual_edge!=INVALID) {
21.10 + Node w=graph->head(actual_edge);
21.11 if (!reached[w]) {
21.12 bfs_queue.push(w);
21.13 reached.set(w, true);
21.14 @@ -78,10 +78,10 @@
21.15 /// its \c operator++() iterates on the edges in a bfs order.
21.16 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
21.17 operator++() {
21.18 - if (graph->valid(actual_edge)) {
21.19 - graph->next(actual_edge);
21.20 - if (graph->valid(actual_edge)) {
21.21 - Node w=graph->bNode(actual_edge);
21.22 + if (actual_edge!=INVALID) {
21.23 + ++actual_edge;
21.24 + if (actual_edge!=INVALID) {
21.25 + Node w=graph->head(actual_edge);
21.26 if (!reached[w]) {
21.27 bfs_queue.push(w);
21.28 reached.set(w, true);
21.29 @@ -94,8 +94,8 @@
21.30 bfs_queue.pop();
21.31 if (!bfs_queue.empty()) {
21.32 graph->first(actual_edge, bfs_queue.front());
21.33 - if (graph->valid(actual_edge)) {
21.34 - Node w=graph->bNode(actual_edge);
21.35 + if (actual_edge!=INVALID) {
21.36 + Node w=graph->head(actual_edge);
21.37 if (!reached[w]) {
21.38 bfs_queue.push(w);
21.39 reached.set(w, true);
21.40 @@ -117,7 +117,7 @@
21.41 /// Returns if b-node has been reached just now.
21.42 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
21.43 /// Returns if a-node is examined.
21.44 - bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
21.45 + bool isANodeExamined() const { return actual_edge==INVALID; }
21.46 /// Returns a-node of the actual edge, so does if the edge is invalid.
21.47 Node aNode() const { return bfs_queue.front(); }
21.48 /// \pre The actual edge have to be valid.
21.49 @@ -237,8 +237,8 @@
21.50 operator++() {
21.51 actual_edge=dfs_stack.top();
21.52 //actual_node=G.aNode(actual_edge);
21.53 - if (graph->valid(actual_edge)/*.valid()*/) {
21.54 - Node w=graph->bNode(actual_edge);
21.55 + if (actual_edge!=INVALID/*.valid()*/) {
21.56 + Node w=graph->head(actual_edge);
21.57 actual_node=w;
21.58 if (!reached[w]) {
21.59 OutEdgeIt e;
21.60 @@ -247,8 +247,8 @@
21.61 reached.set(w, true);
21.62 b_node_newly_reached=true;
21.63 } else {
21.64 - actual_node=graph->aNode(actual_edge);
21.65 - graph->next(dfs_stack.top());
21.66 + actual_node=graph->tail(actual_edge);
21.67 + ++dfs_stack.top();
21.68 b_node_newly_reached=false;
21.69 }
21.70 } else {
21.71 @@ -266,7 +266,7 @@
21.72 /// Returns if b-node has been reached just now.
21.73 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
21.74 /// Returns if a-node is examined.
21.75 - bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
21.76 + bool isANodeExamined() const { return actual_edge==INVALID; }
21.77 /// Returns a-node of the actual edge, so does if the edge is invalid.
21.78 Node aNode() const { return actual_node; /*FIXME*/}
21.79 /// Returns b-node of the actual edge.
22.1 --- a/src/work/marci/iterator_bfs_demo.cc Wed Aug 25 18:55:57 2004 +0000
22.2 +++ b/src/work/marci/iterator_bfs_demo.cc Mon Aug 30 12:01:47 2004 +0000
22.3 @@ -4,7 +4,7 @@
22.4 #include <string>
22.5
22.6 #include <sage_graph.h>
22.7 -//#include <smart_graph.h>
22.8 +#include <hugo/smart_graph.h>
22.9 #include <bfs_dfs.h>
22.10 #include <hugo/graph_wrapper.h>
22.11
22.12 @@ -28,8 +28,8 @@
22.13
22.14 int main (int, char*[])
22.15 {
22.16 - //typedef SmartGraph Graph;
22.17 - typedef SageGraph Graph;
22.18 + typedef SmartGraph Graph;
22.19 + //typedef SageGraph Graph;
22.20
22.21 typedef Graph::Node Node;
22.22 typedef Graph::Edge Edge;
22.23 @@ -91,13 +91,13 @@
22.24 EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
22.25
22.26 cout << "bfs and dfs iterator demo on the directed graph" << endl;
22.27 - for(Graph::NodeIt n(G); G.valid(n); G.next(n)) {
22.28 + for(Graph::NodeIt n(G); n!=INVALID; ++n) {
22.29 cout << node_name[n] << ": ";
22.30 cout << "out edges: ";
22.31 - for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e))
22.32 + for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e)
22.33 cout << edge_name[e] << " ";
22.34 cout << "in edges: ";
22.35 - for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e))
22.36 + for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e)
22.37 cout << edge_name[e] << " ";
22.38 cout << endl;
22.39 }
22.40 @@ -107,11 +107,11 @@
22.41 bfs.pushAndSetReached(s);
22.42 while (!bfs.finished()) {
22.43 //cout << "edge: ";
22.44 - if (G.valid(bfs)) {
22.45 + if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) {
22.46 cout << edge_name[bfs] << /*endl*/", " <<
22.47 - node_name[G.aNode(bfs)] <<
22.48 + node_name[G.tail(bfs)] <<
22.49 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.50 - node_name[G.bNode(bfs)] <<
22.51 + node_name[G.head(bfs)] <<
22.52 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
22.53 ": is not newly reached.");
22.54 } else {
22.55 @@ -141,11 +141,11 @@
22.56 while (!dfs.finished()) {
22.57 ++dfs;
22.58 //cout << "edge: ";
22.59 - if (G.valid(dfs)) {
22.60 + if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) {
22.61 cout << edge_name[dfs] << /*endl*/", " <<
22.62 - node_name[G.aNode(dfs)] <<
22.63 + node_name[G.tail(dfs)] <<
22.64 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.65 - node_name[G.bNode(dfs)] <<
22.66 + node_name[G.head(dfs)] <<
22.67 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
22.68 ": is not newly reached.");
22.69 } else {
22.70 @@ -167,13 +167,13 @@
22.71 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
22.72
22.73 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
22.74 - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
22.75 + for(GW::NodeIt n(gw); n!=INVALID; ++n) {
22.76 cout << node_name[GW::Node(n)] << ": ";
22.77 cout << "out edges: ";
22.78 - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
22.79 + for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
22.80 cout << edge_name[e] << " ";
22.81 cout << "in edges: ";
22.82 - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
22.83 + for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
22.84 cout << edge_name[e] << " ";
22.85 cout << endl;
22.86 }
22.87 @@ -183,11 +183,11 @@
22.88 bfs.pushAndSetReached(t);
22.89 while (!bfs.finished()) {
22.90 //cout << "edge: ";
22.91 - if (gw.valid(GW::OutEdgeIt(bfs))) {
22.92 + if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) {
22.93 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
22.94 - node_name[gw.aNode(bfs)] <<
22.95 + node_name[gw.tail(bfs)] <<
22.96 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.97 - node_name[gw.bNode(bfs)] <<
22.98 + node_name[gw.head(bfs)] <<
22.99 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
22.100 ": is not newly reached.");
22.101 } else {
22.102 @@ -217,11 +217,11 @@
22.103 while (!dfs.finished()) {
22.104 ++dfs;
22.105 //cout << "edge: ";
22.106 - if (gw.valid(GW::OutEdgeIt(dfs))) {
22.107 + if (GW::OutEdgeIt(dfs)!=INVALID) {
22.108 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
22.109 - node_name[gw.aNode(dfs)] <<
22.110 + node_name[gw.tail(dfs)] <<
22.111 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.112 - node_name[gw.bNode(dfs)] <<
22.113 + node_name[gw.head(dfs)] <<
22.114 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
22.115 ": is not newly reached.");
22.116 } else {
22.117 @@ -235,20 +235,104 @@
22.118 }
22.119 }
22.120
22.121 +// {
22.122 +// typedef UndirGraphWrapper<const Graph> GW;
22.123 +// GW gw(G);
22.124 +
22.125 +// EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
22.126 +
22.127 +// cout << "bfs and dfs iterator demo on the undirected graph" << endl;
22.128 +// for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
22.129 +// cout << node_name[GW::Node(n)] << ": ";
22.130 +// cout << "out edges: ";
22.131 +// for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
22.132 +// cout << edge_name[e] << " ";
22.133 +// cout << "in edges: ";
22.134 +// for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
22.135 +// cout << edge_name[e] << " ";
22.136 +// cout << endl;
22.137 +// }
22.138 +// // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
22.139 +// // cout << edge_name.get(e) << " ";
22.140 +// // }
22.141 +// // cout << endl;
22.142 +
22.143 +// cout << "bfs from t ..." << endl;
22.144 +// BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
22.145 +// bfs.pushAndSetReached(t);
22.146 +// while (!bfs.finished()) {
22.147 +// //cout << "edge: ";
22.148 +// if (gw.valid(GW::OutEdgeIt(bfs))) {
22.149 +// cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
22.150 +// node_name[gw.aNode(bfs)] <<
22.151 +// (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.152 +// node_name[gw.bNode(bfs)] <<
22.153 +// (bfs.isBNodeNewlyReached() ? ": is newly reached." :
22.154 +// ": is not newly reached.");
22.155 +// } else {
22.156 +// cout << "invalid" << /*endl*/", " <<
22.157 +// node_name[bfs.aNode()] <<
22.158 +// (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.159 +
22.160 +// "invalid.";
22.161 +// }
22.162 +// cout << endl;
22.163 +// ++bfs;
22.164 +// }
22.165 +
22.166 +// cout << " /--> -------------> "<< endl;
22.167 +// cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
22.168 +// cout << " / | | / /-> \\ "<< endl;
22.169 +// cout << " / | | / | ^ \\ "<< endl;
22.170 +// cout << "s | | / | | \\-> t "<< endl;
22.171 +// cout << " \\ | | / | | /-> "<< endl;
22.172 +// cout << " \\ | --/ / | | / "<< endl;
22.173 +// cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
22.174 +// cout << " \\--> -------------> "<< endl;
22.175 +
22.176 +// cout << "dfs from t ..." << endl;
22.177 +// DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
22.178 +// dfs.pushAndSetReached(t);
22.179 +// while (!dfs.finished()) {
22.180 +// ++dfs;
22.181 +// //cout << "edge: ";
22.182 +// if (gw.valid(GW::OutEdgeIt(dfs))) {
22.183 +// cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
22.184 +// node_name[gw.aNode(dfs)] <<
22.185 +// (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.186 +// node_name[gw.bNode(dfs)] <<
22.187 +// (dfs.isBNodeNewlyReached() ? ": is newly reached." :
22.188 +// ": is not newly reached.");
22.189 +// } else {
22.190 +// cout << "invalid" << /*endl*/", " <<
22.191 +// node_name[dfs.aNode()] <<
22.192 +// (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.193 +
22.194 +// "invalid.";
22.195 +// }
22.196 +// cout << endl;
22.197 +// }
22.198 +// }
22.199 +
22.200 +
22.201 +
22.202 {
22.203 - typedef UndirGraphWrapper<const Graph> GW;
22.204 + typedef BidirGraphWrapper<const Graph> GW;
22.205 GW gw(G);
22.206
22.207 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
22.208
22.209 - cout << "bfs and dfs iterator demo on the undirected graph" << endl;
22.210 - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
22.211 + cout << "bfs and dfs iterator demo on the bidirected graph" << endl;
22.212 +// for(GW::EdgeIt e(gw); e!=INVALID; ++e) {
22.213 +// cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " ";
22.214 +// }
22.215 + for(GW::NodeIt n(gw); n!=INVALID; ++n) {
22.216 cout << node_name[GW::Node(n)] << ": ";
22.217 cout << "out edges: ";
22.218 - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
22.219 + for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
22.220 cout << edge_name[e] << " ";
22.221 cout << "in edges: ";
22.222 - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
22.223 + for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
22.224 cout << edge_name[e] << " ";
22.225 cout << endl;
22.226 }
22.227 @@ -262,11 +346,11 @@
22.228 bfs.pushAndSetReached(t);
22.229 while (!bfs.finished()) {
22.230 //cout << "edge: ";
22.231 - if (gw.valid(GW::OutEdgeIt(bfs))) {
22.232 + if (GW::OutEdgeIt(bfs)!=INVALID) {
22.233 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
22.234 - node_name[gw.aNode(bfs)] <<
22.235 + node_name[gw.tail(bfs)] <<
22.236 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.237 - node_name[gw.bNode(bfs)] <<
22.238 + node_name[gw.head(bfs)] <<
22.239 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
22.240 ": is not newly reached.");
22.241 } else {
22.242 @@ -296,11 +380,11 @@
22.243 while (!dfs.finished()) {
22.244 ++dfs;
22.245 //cout << "edge: ";
22.246 - if (gw.valid(GW::OutEdgeIt(dfs))) {
22.247 + if (GW::OutEdgeIt(dfs)!=INVALID) {
22.248 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
22.249 - node_name[gw.aNode(dfs)] <<
22.250 + node_name[gw.tail(dfs)] <<
22.251 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.252 - node_name[gw.bNode(dfs)] <<
22.253 + node_name[gw.head(dfs)] <<
22.254 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
22.255 ": is not newly reached.");
22.256 } else {
22.257 @@ -314,88 +398,5 @@
22.258 }
22.259 }
22.260
22.261 -
22.262 -
22.263 - {
22.264 - typedef BidirGraphWrapper<const Graph> GW;
22.265 - GW gw(G);
22.266 -
22.267 - EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
22.268 -
22.269 - cout << "bfs and dfs iterator demo on the undirected graph" << endl;
22.270 - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
22.271 - cout << node_name[GW::Node(n)] << ": ";
22.272 - cout << "out edges: ";
22.273 - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
22.274 - cout << edge_name[e] << " ";
22.275 - cout << "in edges: ";
22.276 - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
22.277 - cout << edge_name[e] << " ";
22.278 - cout << endl;
22.279 - }
22.280 -// for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
22.281 -// cout << edge_name.get(e) << " ";
22.282 -// }
22.283 -// cout << endl;
22.284 -
22.285 - cout << "bfs from t ..." << endl;
22.286 - BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
22.287 - bfs.pushAndSetReached(t);
22.288 - while (!bfs.finished()) {
22.289 - //cout << "edge: ";
22.290 - if (gw.valid(GW::OutEdgeIt(bfs))) {
22.291 - cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
22.292 - node_name[gw.aNode(bfs)] <<
22.293 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.294 - node_name[gw.bNode(bfs)] <<
22.295 - (bfs.isBNodeNewlyReached() ? ": is newly reached." :
22.296 - ": is not newly reached.");
22.297 - } else {
22.298 - cout << "invalid" << /*endl*/", " <<
22.299 - node_name[bfs.aNode()] <<
22.300 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.301 -
22.302 - "invalid.";
22.303 - }
22.304 - cout << endl;
22.305 - ++bfs;
22.306 - }
22.307 -
22.308 - cout << " /--> -------------> "<< endl;
22.309 - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
22.310 - cout << " / | | / /-> \\ "<< endl;
22.311 - cout << " / | | / | ^ \\ "<< endl;
22.312 - cout << "s | | / | | \\-> t "<< endl;
22.313 - cout << " \\ | | / | | /-> "<< endl;
22.314 - cout << " \\ | --/ / | | / "<< endl;
22.315 - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
22.316 - cout << " \\--> -------------> "<< endl;
22.317 -
22.318 - cout << "dfs from t ..." << endl;
22.319 - DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
22.320 - dfs.pushAndSetReached(t);
22.321 - while (!dfs.finished()) {
22.322 - ++dfs;
22.323 - //cout << "edge: ";
22.324 - if (gw.valid(GW::OutEdgeIt(dfs))) {
22.325 - cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
22.326 - node_name[gw.aNode(dfs)] <<
22.327 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.328 - node_name[gw.bNode(dfs)] <<
22.329 - (dfs.isBNodeNewlyReached() ? ": is newly reached." :
22.330 - ": is not newly reached.");
22.331 - } else {
22.332 - cout << "invalid" << /*endl*/", " <<
22.333 - node_name[dfs.aNode()] <<
22.334 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
22.335 -
22.336 - "invalid.";
22.337 - }
22.338 - cout << endl;
22.339 - }
22.340 - }
22.341 -
22.342 -
22.343 -
22.344 return 0;
22.345 }
23.1 --- a/src/work/sage_graph.h Wed Aug 25 18:55:57 2004 +0000
23.2 +++ b/src/work/sage_graph.h Mon Aug 30 12:01:47 2004 +0000
23.3 @@ -9,12 +9,12 @@
23.4
23.5 namespace hugo {
23.6
23.7 - template <typename It>
23.8 - int count(It it) {
23.9 - int i=0;
23.10 - for( ; it.valid(); ++it) { ++i; }
23.11 - return i;
23.12 - }
23.13 +// template <typename It>
23.14 +// int count(It it) {
23.15 +// int i=0;
23.16 +// for( ; it.valid(); ++it) { ++i; }
23.17 +// return i;
23.18 +// }
23.19
23.20 class SageGraph {
23.21 struct node_item;
23.22 @@ -385,11 +385,13 @@
23.23 //protected:
23.24 public: //for everybody but marci
23.25 NodeIt(const SageGraph& G) : Node(G._first_node) { }
23.26 + NodeIt(const SageGraph& G, const Node& n) : Node(n) { }
23.27 public:
23.28 NodeIt() : Node() { }
23.29 NodeIt(const Invalid& i) : Node(i) { }
23.30 protected:
23.31 NodeIt(node_item* v) : Node(v) { }
23.32 + public:
23.33 NodeIt& operator++() { node=node->_next_node; return *this; }
23.34 //FIXME::
23.35 // NodeIt& operator=(const Node& e)
23.36 @@ -425,18 +427,18 @@
23.37
23.38 class EdgeIt : public Edge {
23.39 friend class SageGraph;
23.40 - //protected:
23.41 - public: //for alpar
23.42 + public:
23.43 + EdgeIt() : Edge() { }
23.44 + EdgeIt(const Invalid& i) : Edge(i) { }
23.45 EdgeIt(const SageGraph& G) {
23.46 node_item* v=G._first_node;
23.47 if (v) edge=v->_first_out_edge; else edge=0;
23.48 while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
23.49 }
23.50 + EdgeIt(const SageGraph& G, const Edge& e) : Edge(e) { }
23.51 +// protected:
23.52 +// EdgeIt(edge_item* _e) : Edge(_e) { }
23.53 public:
23.54 - EdgeIt() : Edge() { }
23.55 - EdgeIt(const Invalid& i) : Edge(i) { }
23.56 - protected:
23.57 - EdgeIt(edge_item* _e) : Edge(_e) { }
23.58 EdgeIt& operator++() {
23.59 node_item* v=edge->_tail;
23.60 edge=edge->_next_out;
23.61 @@ -447,15 +449,11 @@
23.62
23.63 class OutEdgeIt : public Edge {
23.64 friend class SageGraph;
23.65 - //node_item* v;
23.66 - //protected:
23.67 - protected: //for alpar
23.68 - OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
23.69 public:
23.70 - OutEdgeIt() : Edge()/*, v(0)*/ { }
23.71 + OutEdgeIt() : Edge() { }
23.72 OutEdgeIt(const Invalid& i) : Edge(i) { }
23.73 - OutEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
23.74 - protected:
23.75 + OutEdgeIt(const SageGraph&, Node _v) : Edge(_v.node->_first_out_edge) { }
23.76 + OutEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { }
23.77 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
23.78 protected:
23.79 Node aNode() const { return Node(edge->_tail); }
23.80 @@ -464,15 +462,11 @@
23.81
23.82 class InEdgeIt : public Edge {
23.83 friend class SageGraph;
23.84 - //node_item* v;
23.85 - //protected:
23.86 - protected: //for alpar
23.87 - InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
23.88 public:
23.89 - InEdgeIt() : Edge()/*, v(0)*/ { }
23.90 - InEdgeIt(const Invalid& i) : Edge(i) { }
23.91 - InEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
23.92 - protected:
23.93 + InEdgeIt() : Edge() { }
23.94 + InEdgeIt(Invalid i) : Edge(i) { }
23.95 + InEdgeIt(const SageGraph&, Node _v) : Edge(_v.node->_first_in_edge) { }
23.96 + InEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { }
23.97 InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
23.98 protected:
23.99 Node aNode() const { return Node(edge->_head); }