# HG changeset patch # User alpar # Date 1093867307 0 # Node ID 4297098d9677bf99b4329ba014905ac0f18b46be # Parent ce9438c5a82d7495e8f32a95ef45c34f9bc02f55 Merge back the whole branches/hugo++ to trunk. diff -r ce9438c5a82d -r 4297098d9677 configure.ac --- a/configure.ac Wed Aug 25 18:55:57 2004 +0000 +++ b/configure.ac Mon Aug 30 12:01:47 2004 +0000 @@ -1,5 +1,5 @@ dnl Process this file with autoconf to produce a configure script. -AC_INIT([HugoLib], [0.1], [etik-ol@cs.elte.hu], [hugo]) +AC_INIT([HugoLib], [0.2], [etik-ol@cs.elte.hu], [hugo]) AC_CONFIG_AUX_DIR([config]) AM_INIT_AUTOMAKE(1.7) AC_CONFIG_SRCDIR([src/hugo/invalid.h]) @@ -14,7 +14,7 @@ dnl Checks for libraries. dnl Checks for header files. -AC_CHECK_HEADERS(limits.h sys/time.h unistd.h) +AC_CHECK_HEADERS(limits.h sys/time.h sys/times.h unistd.h) dnl Checks for typedefs, structures, and compiler characteristics. AC_C_CONST diff -r ce9438c5a82d -r 4297098d9677 doc/groups.dox --- a/doc/groups.dox Wed Aug 25 18:55:57 2004 +0000 +++ b/doc/groups.dox Mon Aug 30 12:01:47 2004 +0000 @@ -8,14 +8,14 @@ @ingroup datas \brief Graph structures implemented in Hugo. -Hugolib provides several data structures to meet the diversing requirements +Hugolib provides several data structures to meet the diverging requirements of the possible users. In order to save on running time or on memory usage, some structures may fail to provide some graph features like edge or node deletion. Hugolib also offers special graphs that cannot be used alone but only -in conjunktion with other graph representation. The examples for this are +in conjunction with other graph representation. The examples for this are \ref EdgeSet, \ref NodeSet, and the large variety of graph wrappers. You are free to use the graph structure that fit your requirements diff -r ce9438c5a82d -r 4297098d9677 src/benchmark/bfs-bench.cc --- a/src/benchmark/bfs-bench.cc Wed Aug 25 18:55:57 2004 +0000 +++ b/src/benchmark/bfs-bench.cc Mon Aug 30 12:01:47 2004 +0000 @@ -48,7 +48,7 @@ Node n(Q.front()); Node m; Q.pop(); - for(OutEdgeIt e(G,n);G.valid(e);G.next(e)) + for(OutEdgeIt e(G,n);e!=INVALID;++e) if(!visited[m=G.head(e)]) { Q.push(m); visited.set(m,true); @@ -76,7 +76,7 @@ do { Node m; Node n=Q[Qt++]; - for(OutEdgeIt e(G,n);G.valid(e);G.next(e)) + for(OutEdgeIt e(G,n);e!=INVALID;++e) if(!visited[m=G.head(e)]) { Q[Qh++]=m; visited.set(m,true); @@ -91,8 +91,8 @@ int i=0; - for(NodeIt n(G);G.valid(n);G.next(n)) - for(OutEdgeIt e(G,n);G.valid(e);G.next(e)) + for(NodeIt n(G);n!=INVALID;++n) + for(OutEdgeIt e(G,n);e!=INVALID;++e) i++; } diff -r ce9438c5a82d -r 4297098d9677 src/hugo/Makefile.am --- a/src/hugo/Makefile.am Wed Aug 25 18:55:57 2004 +0000 +++ b/src/hugo/Makefile.am Mon Aug 30 12:01:47 2004 +0000 @@ -1,4 +1,5 @@ pkginclude_HEADERS = \ + bfs.h \ bin_heap.h \ dijkstra.h \ dimacs.h \ diff -r ce9438c5a82d -r 4297098d9677 src/hugo/bfs.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/bfs.h Mon Aug 30 12:01:47 2004 +0000 @@ -0,0 +1,298 @@ +// -*- C++ -*- +#ifndef HUGO_BFS_H +#define HUGO_BFS_H + +///\ingroup flowalgs +///\file +///\brief Bfs algorithm. +/// +///\todo Revise Manual. + +#include +#include + +namespace hugo { + +/// \addtogroup flowalgs +/// @{ + + ///%Bfs algorithm class. + + ///This class provides an efficient implementation of %Bfs algorithm. + ///The edge lengths are passed to the algorithm using a + ///\ref ReadMapSkeleton "readable map", + ///so it is easy to change it to any kind of length. + /// + ///The type of the length is determined by the \c ValueType of the length map. + /// + ///It is also possible to change the underlying priority heap. + /// + ///\param GR The graph type the algorithm runs on. + ///\param LM This read-only + ///EdgeMap + ///determines the + ///lengths of the edges. It is read once for each edge, so the map + ///may involve in relatively time consuming process to compute the edge + ///length if it is necessary. The default map type is + ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap" + ///\param Heap The heap type used by the %Bfs + ///algorithm. The default + ///is using \ref BinHeap "binary heap". + /// + ///\author Jacint Szabo and Alpar Juttner + ///\todo We need a typedef-names should be standardized. (-: + ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap + ///should not be fixed. (Problematic to solve). + +#ifdef DOXYGEN + template +#else + template +#endif + class Bfs{ + public: + ///The type of the underlying graph. + typedef GR Graph; + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::OutEdgeIt OutEdgeIt; + + ///\brief The type of the map that stores the last + ///edges of the shortest paths. + typedef typename Graph::template NodeMap PredMap; + ///\brief The type of the map that stores the last but one + ///nodes of the shortest paths. + typedef typename Graph::template NodeMap PredNodeMap; + ///The type of the map that stores the dists of the nodes. + typedef typename Graph::template NodeMap DistMap; + + private: + const Graph *G; + PredMap *predecessor; + bool local_predecessor; + PredNodeMap *pred_node; + bool local_pred_node; + DistMap *distance; + bool local_distance; + + //The source node of the last execution. + Node source; + + + ///Initialize maps. + + ///\todo Error if \c G or are \c NULL. + ///\todo Better memory allocation (instead of new). + void init_maps() + { +// if(!length) { +// local_length = true; +// length = new LM(G); +// } + if(!predecessor) { + local_predecessor = true; + predecessor = new PredMap(*G); + } + if(!pred_node) { + local_pred_node = true; + pred_node = new PredNodeMap(*G); + } + if(!distance) { + local_distance = true; + distance = new DistMap(*G); + } + } + + public : + Bfs(const Graph& _G) : + G(&_G), + predecessor(NULL), local_predecessor(false), + pred_node(NULL), local_pred_node(false), + distance(NULL), local_distance(false) + { } + + ~Bfs() + { + // if(local_length) delete length; + if(local_predecessor) delete predecessor; + if(local_pred_node) delete pred_node; + if(local_distance) delete distance; + } + + ///Sets the graph the algorithm will run on. + + ///Sets the graph the algorithm will run on. + ///\return (*this) + Bfs &setGraph(const Graph &_G) + { + G = &_G; + return *this; + } + ///Sets the length map. + + ///Sets the map storing the predecessor edges. + + ///Sets the map storing the predecessor edges. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Bfs &setPredMap(PredMap &m) + { + if(local_predecessor) { + delete predecessor; + local_predecessor=false; + } + predecessor = &m; + return *this; + } + + ///Sets the map storing the predecessor nodes. + + ///Sets the map storing the predecessor nodes. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Bfs &setPredNodeMap(PredNodeMap &m) + { + if(local_pred_node) { + delete pred_node; + local_pred_node=false; + } + pred_node = &m; + return *this; + } + + ///Sets the map storing the distances calculated by the algorithm. + + ///Sets the map storing the distances calculated by the algorithm. + ///If you don't use this function before calling \ref run(), + ///it will allocate one. The destuctor deallocates this + ///automatically allocated map, of course. + ///\return (*this) + Bfs &setDistMap(DistMap &m) + { + if(local_distance) { + delete distance; + local_distance=false; + } + distance = &m; + return *this; + } + + ///Runs %BFS algorithm from node \c s. + + ///This method runs the %BFS algorithm from a root node \c s + ///in order to + ///compute the + ///shortest path to each node. The algorithm computes + ///- The shortest path tree. + ///- The distance of each node from the root. + + void run(Node s) { + + init_maps(); + + source = s; + + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { + predecessor->set(u,INVALID); + pred_node->set(u,INVALID); + } + + int N=G->nodeNum(); + std::vector Q(N); + int Qh=0; + int Qt=0; + + Q[Qh++]=source; + distance->set(s, 0); + do { + Node m; + Node n=Q[Qt++]; + int d= (*distance)[n]+1; + + for(OutEdgeIt e(*G,n);e!=INVALID;++e) + if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) { + Q[Qh++]=m; + predecessor->set(m,e); + pred_node->set(m,n); + distance->set(m,d); + } + } while(Qt!=Qh); + } + + ///The distance of a node from the root. + + ///Returns the distance of a node from the root. + ///\pre \ref run() must be called before using this function. + ///\warning If node \c v in unreachable from the root the return value + ///of this funcion is undefined. + int dist(Node v) const { return (*distance)[v]; } + + ///Returns the 'previous edge' of the shortest path tree. + + ///For a node \c v it returns the 'previous edge' of the shortest path tree, + ///i.e. it returns the last edge from a shortest path from the root to \c + ///v. It is \ref INVALID + ///if \c v is unreachable from the root or if \c v=s. The + ///shortest path tree used here is equal to the shortest path tree used in + ///\ref predNode(Node v). \pre \ref run() must be called before using + ///this function. + Edge pred(Node v) const { return (*predecessor)[v]; } + + ///Returns the 'previous node' of the shortest path tree. + + ///For a node \c v it returns the 'previous node' of the shortest path tree, + ///i.e. it returns the last but one node from a shortest path from the + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if + ///\c v=s. The shortest path tree used here is equal to the shortest path + ///tree used in \ref pred(Node v). \pre \ref run() must be called before + ///using this function. + Node predNode(Node v) const { return (*pred_node)[v]; } + + ///Returns a reference to the NodeMap of distances. + + ///Returns a reference to the NodeMap of distances. \pre \ref run() must + ///be called before using this function. + const DistMap &distMap() const { return *distance;} + + ///Returns a reference to the shortest path tree map. + + ///Returns a reference to the NodeMap of the edges of the + ///shortest path tree. + ///\pre \ref run() must be called before using this function. + const PredMap &predMap() const { return *predecessor;} + + ///Returns a reference to the map of nodes of shortest paths. + + ///Returns a reference to the NodeMap of the last but one nodes of the + ///shortest path tree. + ///\pre \ref run() must be called before using this function. + const PredNodeMap &predNodeMap() const { return *pred_node;} + + ///Checks if a node is reachable from the root. + + ///Returns \c true if \c v is reachable from the root. + ///\warning The root node is reported to be reached! + /// + ///\pre \ref run() must be called before using this function. + /// + bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; } + + }; + + + // ********************************************************************** + // IMPLEMENTATIONS + // ********************************************************************** + +/// @} + +} //END OF NAMESPACE HUGO + +#endif + + diff -r ce9438c5a82d -r 4297098d9677 src/hugo/dijkstra.h --- a/src/hugo/dijkstra.h Wed Aug 25 18:55:57 2004 +0000 +++ b/src/hugo/dijkstra.h Mon Aug 30 12:01:47 2004 +0000 @@ -84,6 +84,9 @@ DistMap *distance; bool local_distance; + //The source node of the last execution. + Node source; + ///Initialize maps ///\todo Error if \c G or are \c NULL. What about \c length? @@ -212,7 +215,9 @@ init_maps(); - for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) { + source = s; + + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { predecessor->set(u,INVALID); pred_node->set(u,INVALID); } @@ -235,8 +240,8 @@ distance->set(v, oldvalue); - for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) { - Node w=G->bNode(e); + for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { + Node w=G->head(e); switch(heap.state(w)) { case HeapType::PRE_HEAP: @@ -310,11 +315,10 @@ ///Checks if a node is reachable from the root. ///Returns \c true if \c v is reachable from the root. - ///\warning the root node is reported to be unreached! - ///\todo Is this what we want? + ///\warning the root node is reported to be reached! ///\pre \ref run() must be called before using this function. /// - bool reached(Node v) { return G->valid((*predecessor)[v]); } + bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; } }; diff -r ce9438c5a82d -r 4297098d9677 src/hugo/full_graph.h --- a/src/hugo/full_graph.h Wed Aug 25 18:55:57 2004 +0000 +++ b/src/hugo/full_graph.h Mon Aug 30 12:01:47 2004 +0000 @@ -63,12 +63,6 @@ Node tail(Edge e) const { return e.n%NodeNum; } Node head(Edge e) const { return e.n/NodeNum; } - Node aNode(OutEdgeIt e) const { return tail(e); } - Node aNode(InEdgeIt e) const { return head(e); } - - Node bNode(OutEdgeIt e) const { return head(e); } - Node bNode(InEdgeIt e) const { return tail(e); } - NodeIt& first(NodeIt& v) const { v=NodeIt(*this); return v; } EdgeIt& first(EdgeIt& e) const { @@ -78,25 +72,23 @@ InEdgeIt& first(InEdgeIt& e, const Node v) const { e=InEdgeIt(*this,v); return e; } - static bool valid(Edge e) { return e.n!=-1; } - static bool valid(Node n) { return n.n!=-1; } - - template It getNext(It it) const - { It tmp(it); return next(tmp); } - - NodeIt& next(NodeIt& it) const { - it.n=(it.n+2)%(NodeNum+1)-1; - return it; - } - OutEdgeIt& next(OutEdgeIt& it) const - { it.n+=NodeNum; if(it.n>=EdgeNum) it.n=-1; return it; } - InEdgeIt& next(InEdgeIt& it) const - { if(!((++it.n)%NodeNum)) it.n=-1; return it; } - static EdgeIt& next(EdgeIt& it) { --it.n; return it; } - static int id(Node v) { return v.n; } static int id(Edge e) { return e.n; } + /// Finds an edge between two nodes. + + /// Finds an edge from node \c u to node \c v. + /// + /// If \c prev is \ref INVALID (this is the default value), then + /// It finds the first edge from \c u to \c v. Otherwise it looks for + /// the next edge from \c u to \c v after \c prev. + /// \return The found edge or INVALID if there is no such an edge. + Edge findEdge(Node u,Node v, Edge prev = INVALID) + { + return prev.n==-1?Edge(*this,u.n,v.n):INVALID; + } + + class Node { friend class FullGraph; template friend class NodeMap; @@ -119,13 +111,15 @@ }; class NodeIt : public Node { + const FullGraph *G; friend class FullGraph; public: NodeIt() : Node() { } + NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { } NodeIt(Invalid i) : Node(i) { } - NodeIt(const FullGraph& G) : Node(G.NodeNum?0:-1) { } + NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { } ///\todo Undocumented conversion Node -\> NodeIt. - NodeIt(const FullGraph& G, const Node &n) : Node(n) { } + NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; } }; class Edge { @@ -138,7 +132,8 @@ int n; //NodeNum*head+tail; friend int FullGraph::id(Edge e); - Edge(int nn) {n=nn;} + Edge(int nn) : n(nn) {} + Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {} public: Edge() { } Edge (Invalid) { n=-1; } @@ -154,30 +149,42 @@ class EdgeIt : public Edge { friend class FullGraph; public: - EdgeIt(const FullGraph& G) : Edge(G.EdgeNum-1) { } + EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { } + EdgeIt(const FullGraph&, Edge e) : Edge(e) { } EdgeIt (Invalid i) : Edge(i) { } EdgeIt() : Edge() { } + EdgeIt& operator++() { --n; return *this; } + ///\bug This is a workaround until somebody tells me how to ///make class \c SymFullGraph::SymEdgeMap friend of Edge int &idref() {return n;} }; class OutEdgeIt : public Edge { + const FullGraph *G; friend class FullGraph; public: OutEdgeIt() : Edge() { } + OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { } OutEdgeIt (Invalid i) : Edge(i) { } - OutEdgeIt(const FullGraph& G,const Node v) - : Edge(v.n) {} + OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {} + + OutEdgeIt& operator++() + { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; } + }; class InEdgeIt : public Edge { + const FullGraph *G; friend class FullGraph; public: InEdgeIt() : Edge() { } + InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { } InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const FullGraph& G,Node v) :Edge(v.n*G.NodeNum){} + InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {} + InEdgeIt& operator++() + { if(!((++n)%G->NodeNum)) n=-1; return *this; } }; template class NodeMap @@ -279,7 +286,7 @@ std::copy(m.container.begin(), m.container.end(), container.begin()); return *this; } - + void update() {} void update(T a) {} }; diff -r ce9438c5a82d -r 4297098d9677 src/hugo/graph_wrapper.h --- a/src/hugo/graph_wrapper.h Wed Aug 25 18:55:57 2004 +0000 +++ b/src/hugo/graph_wrapper.h Mon Aug 30 12:01:47 2004 +0000 @@ -12,7 +12,7 @@ #include #include -//#include +#include namespace hugo { @@ -96,70 +96,97 @@ typedef Graph ParentGraph; GraphWrapper(Graph& _graph) : graph(&_graph) { } + GraphWrapper(const GraphWrapper& gw) : graph(gw.graph) { } // Graph& getGraph() const { return *graph; } -// typedef typename Graph::Node Node; - class Node : public Graph::Node { + typedef typename Graph::Node Node; +// class Node : public Graph::Node { +// friend class GraphWrapper; +// public: +// Node() { } +// Node(const typename Graph::Node& _n) : Graph::Node(_n) { } +// // /// \bug construction throughrthr multiple levels should be +// // /// handled better +// // Node(const typename ParentGraph::ParentGraph::Node& _n) : +// // Graph::Node(_n) { } +// Node(const Invalid& i) : Graph::Node(i) { } +// }; + class NodeIt : public Node { + const GraphWrapper* gw; friend class GraphWrapper; - public: - Node() { } - Node(const typename Graph::Node& _n) : Graph::Node(_n) { } - // /// \bug construction throughrthr multiple levels should be - // /// handled better - // Node(const typename ParentGraph::ParentGraph::Node& _n) : - // Graph::Node(_n) { } - Node(const Invalid& i) : Graph::Node(i) { } - }; - class NodeIt { - friend class GraphWrapper; - typename Graph::NodeIt n; public: NodeIt() { } - NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } - NodeIt(const Invalid& i) : n(i) { } - NodeIt(const GraphWrapper& _G) : n(*(_G.graph)) { } - operator Node() const { return Node(typename Graph::Node(n)); } + // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { } + NodeIt(Invalid i) : Node(i) { } + NodeIt(const GraphWrapper& _gw) : + Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { } + NodeIt(const GraphWrapper& _gw, const Node& n) : + Node(n), gw(&_gw) { } + NodeIt& operator++() { + *(static_cast(this))= + ++(typename Graph::NodeIt(*(gw->graph), *this)); + return *this; + } }; -// typedef typename Graph::Edge Edge; - class Edge : public Graph::Edge { + typedef typename Graph::Edge Edge; +// class Edge : public Graph::Edge { +// friend class GraphWrapper; +// public: +// Edge() { } +// Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { } +// Edge(const Invalid& i) : Graph::Edge(i) { } +// }; + class OutEdgeIt : public Edge { + const GraphWrapper* gw; friend class GraphWrapper; - public: - Edge() { } - Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { } - Edge(const Invalid& i) : Graph::Edge(i) { } + public: + OutEdgeIt() { } + //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } + OutEdgeIt(Invalid i) : Edge(i) { } + OutEdgeIt(const GraphWrapper& _gw, const Node& n) : + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } + OutEdgeIt(const GraphWrapper& _gw, const Edge& e) : + Edge(e), gw(&_gw) { } + OutEdgeIt& operator++() { + *(static_cast(this))= + ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); + return *this; + } }; - class OutEdgeIt { + class InEdgeIt : public Edge { + const GraphWrapper* gw; friend class GraphWrapper; - typename Graph::OutEdgeIt e; - public: - OutEdgeIt() { } - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } - OutEdgeIt(const Invalid& i) : e(i) { } - OutEdgeIt(const GraphWrapper& _G, const Node& _n) : - e(*(_G.graph), typename Graph::Node(_n)) { } - operator Edge() const { return Edge(typename Graph::Edge(e)); } - }; - class InEdgeIt { - friend class GraphWrapper; - typename Graph::InEdgeIt e; - public: + public: InEdgeIt() { } - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } - InEdgeIt(const Invalid& i) : e(i) { } - InEdgeIt(const GraphWrapper& _G, const Node& _n) : - e(*(_G.graph), typename Graph::Node(_n)) { } - operator Edge() const { return Edge(typename Graph::Edge(e)); } + //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } + InEdgeIt(Invalid i) : Edge(i) { } + InEdgeIt(const GraphWrapper& _gw, const Node& n) : + Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } + InEdgeIt(const GraphWrapper& _gw, const Edge& e) : + Edge(e), gw(&_gw) { } + InEdgeIt& operator++() { + *(static_cast(this))= + ++(typename Graph::InEdgeIt(*(gw->graph), *this)); + return *this; + } }; //typedef typename Graph::SymEdgeIt SymEdgeIt; - class EdgeIt { + class EdgeIt : public Edge { + const GraphWrapper* gw; friend class GraphWrapper; - typename Graph::EdgeIt e; - public: + public: EdgeIt() { } - EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } - EdgeIt(const Invalid& i) : e(i) { } - EdgeIt(const GraphWrapper& _G) : e(*(_G.graph)) { } - operator Edge() const { return Edge(typename Graph::Edge(e)); } + //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { } + EdgeIt(Invalid i) : Edge(i) { } + EdgeIt(const GraphWrapper& _gw) : + Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { } + EdgeIt(const GraphWrapper& _gw, const Edge& e) : + Edge(w), gw(&_gw) { } + EdgeIt& operator++() { + *(static_cast(this))= + ++(typename Graph::EdgeIt(*(gw->graph), *this)); + return *this; + } }; NodeIt& first(NodeIt& i) const { @@ -175,28 +202,28 @@ i=EdgeIt(*this); return i; } - NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } - OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } - InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } - EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } +// NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } +// OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } +// InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } +// EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } Node tail(const Edge& e) const { return Node(graph->tail(static_cast(e))); } Node head(const Edge& e) const { return Node(graph->head(static_cast(e))); } - bool valid(const Node& n) const { - return graph->valid(static_cast(n)); } - bool valid(const Edge& e) const { - return graph->valid(static_cast(e)); } +// bool valid(const Node& n) const { +// return graph->valid(static_cast(n)); } +// bool valid(const Edge& e) const { +// return graph->valid(static_cast(e)); } int nodeNum() const { return graph->nodeNum(); } int edgeNum() const { return graph->edgeNum(); } - Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } - Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } - Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } - Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } +// Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } +// Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } +// Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } +// Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } Node addNode() const { return Node(graph->addNode()); } Edge addEdge(const Node& tail, const Node& head) const { @@ -218,15 +245,15 @@ template class NodeMap : public Graph::template NodeMap { typedef typename Graph::template NodeMap Parent; public: - NodeMap(const GraphWrapper& _G) : Parent(*(_G.graph)) { } - NodeMap(const GraphWrapper& _G, T a) : Parent(*(_G.graph), a) { } + NodeMap(const GraphWrapper& gw) : Parent(*(gw.graph)) { } + NodeMap(const GraphWrapper& gw, T a) : Parent(*(gw.graph), a) { } }; template class EdgeMap : public Graph::template EdgeMap { typedef typename Graph::template EdgeMap Parent; public: - EdgeMap(const GraphWrapper& _G) : Parent(*(_G.graph)) { } - EdgeMap(const GraphWrapper& _G, T a) : Parent(*(_G.graph), a) { } + EdgeMap(const GraphWrapper& gw) : Parent(*(gw.graph)) { } + EdgeMap(const GraphWrapper& gw, T a) : Parent(*(gw.graph), a) { } }; }; @@ -246,6 +273,7 @@ RevGraphWrapper() : GraphWrapper() { } public: RevGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } + RevGraphWrapper(const RevGraphWrapper& gw) : Parent(gw) { } typedef typename GraphWrapper::Node Node; typedef typename GraphWrapper::Edge Edge; @@ -256,29 +284,39 @@ //typedef typename GraphWrapper::OutEdgeIt InEdgeIt; //typedef typename GraphWrapper::InEdgeIt OutEdgeIt; - class OutEdgeIt { + class OutEdgeIt : public Edge { + const RevGraphWrapper* gw; friend class GraphWrapper; - friend class RevGraphWrapper; - typename Graph::InEdgeIt e; - public: + public: OutEdgeIt() { } - OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } - OutEdgeIt(const Invalid& i) : e(i) { } - OutEdgeIt(const RevGraphWrapper& _G, const Node& _n) : - e(*(_G.graph), typename Graph::Node(_n)) { } - operator Edge() const { return Edge(typename Graph::Edge(e)); } + //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } + OutEdgeIt(Invalid i) : Edge(i) { } + OutEdgeIt(const RevGraphWrapper& _gw, const Node& n) : + Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } + OutEdgeIt(const RevGraphWrapper& _gw, const Edge& e) : + Edge(e), gw(&_gw) { } + OutEdgeIt& operator++() { + *(static_cast(this))= + ++(typename Graph::InEdgeIt(*(gw->graph), *this)); + return *this; + } }; - class InEdgeIt { + class InEdgeIt : public Edge { + const RevGraphWrapper* gw; friend class GraphWrapper; - friend class RevGraphWrapper; - typename Graph::OutEdgeIt e; - public: + public: InEdgeIt() { } - InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } - InEdgeIt(const Invalid& i) : e(i) { } - InEdgeIt(const RevGraphWrapper& _G, const Node& _n) : - e(*(_G.graph), typename Graph::Node(_n)) { } - operator Edge() const { return Edge(typename Graph::Edge(e)); } + //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } + InEdgeIt(Invalid i) : Edge(i) { } + InEdgeIt(const RevGraphWrapper& _gw, const Node& n) : + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } + InEdgeIt(const RevGraphWrapper& _gw, const Edge& e) : + Edge(e), gw(&_gw) { } + InEdgeIt& operator++() { + *(static_cast(this))= + ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); + return *this; + } }; using GraphWrapper::first; @@ -289,18 +327,18 @@ i=InEdgeIt(*this, p); return i; } - using GraphWrapper::next; - OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } - InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } +// using GraphWrapper::next; +// OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } +// InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } - Node aNode(const OutEdgeIt& e) const { - return Node(this->graph->aNode(e.e)); } - Node aNode(const InEdgeIt& e) const { - return Node(this->graph->aNode(e.e)); } - Node bNode(const OutEdgeIt& e) const { - return Node(this->graph->bNode(e.e)); } - Node bNode(const InEdgeIt& e) const { - return Node(this->graph->bNode(e.e)); } +// Node aNode(const OutEdgeIt& e) const { +// return Node(this->graph->aNode(e.e)); } +// Node aNode(const InEdgeIt& e) const { +// return Node(this->graph->aNode(e.e)); } +// Node bNode(const OutEdgeIt& e) const { +// return Node(this->graph->bNode(e.e)); } +// Node bNode(const InEdgeIt& e) const { +// return Node(this->graph->bNode(e.e)); } Node tail(const Edge& e) const { return GraphWrapper::head(e); } @@ -309,8 +347,6 @@ }; - - /// A graph wrapper for hiding nodes and edges from a graph. /// This wrapper shows a graph with filtered node-set and @@ -626,9 +662,6 @@ public: typedef GraphWrapper Parent; protected: - //const CapacityMap* capacity; - //FlowMap* flow; - ForwardFilterMap* forward_filter; BackwardFilterMap* backward_filter; @@ -647,6 +680,11 @@ BackwardFilterMap& _backward_filter) : GraphWrapper(_graph), forward_filter(&_forward_filter), backward_filter(&_backward_filter) { } + SubBidirGraphWrapper(const SubBidirGraphWrapper& gw) : + Parent(gw), + forward_filter(gw.forward_filter), + backward_filter(gw.backward_filter) { } class Edge; class OutEdgeIt; @@ -657,8 +695,9 @@ template class EdgeMap; typedef typename GraphWrapper::Node Node; - typedef typename GraphWrapper::NodeIt NodeIt; + //typedef typename GraphWrapper::NodeIt NodeIt; + typedef typename Graph::Edge GraphEdge; class Edge : public Graph::Edge { friend class SubBidirGraphWrapper; @@ -671,116 +710,196 @@ public: Edge() { } ///\bug =false kell-e? zsoltnak kell az addEdge miatt - Edge(const typename Graph::Edge& _e, bool _backward=false) : - Graph::Edge(_e), backward(_backward) { } - Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } + Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : + Graph::Edge(e), backward(_backward) { } + Edge(Invalid i) : Graph::Edge(i), backward(true) { } //the unique invalid iterator - friend bool operator==(const Edge& u, const Edge& v) { - return (v.backward==u.backward && - static_cast(u)== +// friend bool operator==(const Edge& u, const Edge& v) { +// return (u.backward==v.backward && +// static_cast(u)== +// static_cast(v)); +// } +// friend bool operator!=(const Edge& u, const Edge& v) { +// return (u.backward!=v.backward || +// static_cast(u)!= +// static_cast(v)); +// } + bool operator==(const Edge& v) const { + return (this->backward==v.backward && + static_cast(*this)== static_cast(v)); } - friend bool operator!=(const Edge& u, const Edge& v) { - return (v.backward!=u.backward || - static_cast(u)!= + bool operator!=(const Edge& v) const { + return (this->backward!=v.backward || + static_cast(*this)!= static_cast(v)); - } + } }; - class OutEdgeIt { + class OutEdgeIt : public Edge { friend class SubBidirGraphWrapper; protected: - typename Graph::OutEdgeIt out; - typename Graph::InEdgeIt in; - bool backward; + const SubBidirGraphWrapper* gw; public: OutEdgeIt() { } - //FIXME -// OutEdgeIt(const Edge& e) : Edge(e) { } - OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } + OutEdgeIt(Invalid i) : Edge(i) { } //the unique invalid iterator OutEdgeIt(const SubBidirGraphWrapper& _G, Node v) { - backward=false; - _G.graph->first(out, v); - while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); } - if (!_G.graph->valid(out)) { - backward=true; - _G.graph->first(in, v); - while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); } + ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { + while (*static_cast(this)!=INVALID && + !(*(gw->forward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); + if (*static_cast(this)==INVALID) + *static_cast(this)= + Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true); + while (*static_cast(this)!=INVALID && + !(*(gw->backward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::InEdgeIt(*(gw->graph), *this)); + } + OutEdgeIt(const SubBidirGraphWrapper& _gw, const Edge& e) : + Edge(e), gw(&_gw) { } + OutEdgeIt& operator++() { + if (!this->backward) { + Node n=gw->tail(*this); + *(static_cast(this))= + ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); + while (*static_cast(this)!=INVALID && + !(*(gw->forward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); + if (*static_cast(this)==INVALID) + *static_cast(this)= + Edge(typename Graph::InEdgeIt(*(gw->graph), n), true); + while (*static_cast(this)!=INVALID && + !(*(gw->backward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::InEdgeIt(*(gw->graph), *this)); + } else { + *(static_cast(this))= + ++(typename Graph::InEdgeIt(*(gw->graph), *this)); + while (*static_cast(this)!=INVALID && + !(*(gw->backward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::InEdgeIt(*(gw->graph), *this)); } - } - operator Edge() const { -// Edge e; -// e.forward=this->forward; -// if (this->forward) e=out; else e=in; -// return e; - if (this->backward) - return Edge(in, this->backward); - else - return Edge(out, this->backward); + return *this; } }; - class InEdgeIt { + class InEdgeIt : public Edge { friend class SubBidirGraphWrapper; protected: - typename Graph::OutEdgeIt out; - typename Graph::InEdgeIt in; - bool backward; + const SubBidirGraphWrapper* gw; public: InEdgeIt() { } - //FIXME -// OutEdgeIt(const Edge& e) : Edge(e) { } - InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } + InEdgeIt(Invalid i) : Edge(i) { } //the unique invalid iterator InEdgeIt(const SubBidirGraphWrapper& _G, Node v) { - backward=false; - _G.graph->first(in, v); - while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); } - if (!_G.graph->valid(in)) { - backward=true; - _G.graph->first(out, v); - while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); } + ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : + Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { + while (*static_cast(this)!=INVALID && + !(*(gw->forward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::InEdgeIt(*(gw->graph), *this)); + if (*static_cast(this)==INVALID) + *static_cast(this)= + Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true); + while (*static_cast(this)!=INVALID && + !(*(gw->backward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); + } + InEdgeIt(const SubBidirGraphWrapper& _gw, const Edge& e) : + Edge(e), gw(&_gw) { } + InEdgeIt& operator++() { + if (!this->backward) { + Node n=gw->head(*this); + *(static_cast(this))= + ++(typename Graph::InEdgeIt(*(gw->graph), *this)); + while (*static_cast(this)!=INVALID && + !(*(gw->forward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::InEdgeIt(*(gw->graph), *this)); + if (*static_cast(this)==INVALID) + *static_cast(this)= + Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true); + while (*static_cast(this)!=INVALID && + !(*(gw->backward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); + } else { + *(static_cast(this))= + ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); + while (*static_cast(this)!=INVALID && + !(*(gw->backward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); } - } - operator Edge() const { -// Edge e; -// e.forward=this->forward; -// if (this->forward) e=out; else e=in; -// return e; - if (this->backward) - return Edge(out, this->backward); - else - return Edge(in, this->backward); + return *this; } }; - class EdgeIt { + class EdgeIt : public Edge { friend class SubBidirGraphWrapper; protected: - typename Graph::EdgeIt e; - bool backward; + const SubBidirGraphWrapper* gw; public: EdgeIt() { } - EdgeIt(const Invalid& i) : e(i), backward(true) { } + EdgeIt(Invalid i) : Edge(i) { } +//the unique invalid iterator EdgeIt(const SubBidirGraphWrapper& _G) { - backward=false; - _G.graph->first(e); - while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e); - if (!_G.graph->valid(e)) { - backward=true; - _G.graph->first(e); - while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e); + ForwardFilterMap, BackwardFilterMap>& _gw) : + Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { + while (*static_cast(this)!=INVALID && + !(*(gw->forward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::EdgeIt(*(gw->graph), *this)); + if (*static_cast(this)==INVALID) + *static_cast(this)= + Edge(typename Graph::EdgeIt(*(_gw.graph)), true); + while (*static_cast(this)!=INVALID && + !(*(gw->backward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::EdgeIt(*(gw->graph), *this)); + } + EdgeIt(const SubBidirGraphWrapper& _gw, const Edge& e) : + Edge(e), gw(&_gw) { } + EdgeIt& operator++() { + if (!this->backward) { + *(static_cast(this))= + ++(typename Graph::EdgeIt(*(gw->graph), *this)); + while (*static_cast(this)!=INVALID && + !(*(gw->forward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::EdgeIt(*(gw->graph), *this)); + if (*static_cast(this)==INVALID) + *static_cast(this)= + Edge(typename Graph::EdgeIt(*(gw->graph)), true); + while (*static_cast(this)!=INVALID && + !(*(gw->backward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::EdgeIt(*(gw->graph), *this)); + } else { + *(static_cast(this))= + ++(typename Graph::EdgeIt(*(gw->graph), *this)); + while (*static_cast(this)!=INVALID && + !(*(gw->backward_filter))[*this]) + *(static_cast(this))= + ++(typename Graph::EdgeIt(*(gw->graph), *this)); } - } - operator Edge() const { - return Edge(e, this->backward); + return *this; } }; @@ -799,84 +918,84 @@ i=EdgeIt(*this); return i; } - using GraphWrapper::next; -// NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } - OutEdgeIt& next(OutEdgeIt& e) const { - if (!e.backward) { - Node v=this->graph->aNode(e.out); - this->graph->next(e.out); - while(this->graph->valid(e.out) && !(*forward_filter)[e]) { - this->graph->next(e.out); } - if (!this->graph->valid(e.out)) { - e.backward=true; - this->graph->first(e.in, v); - while(this->graph->valid(e.in) && !(*backward_filter)[e]) { - this->graph->next(e.in); } - } - } else { - this->graph->next(e.in); - while(this->graph->valid(e.in) && !(*backward_filter)[e]) { - this->graph->next(e.in); } - } - return e; - } -// FIXME Not tested - InEdgeIt& next(InEdgeIt& e) const { - if (!e.backward) { - Node v=this->graph->aNode(e.in); - this->graph->next(e.in); - while(this->graph->valid(e.in) && !(*forward_filter)[e]) { - this->graph->next(e.in); } - if (!this->graph->valid(e.in)) { - e.backward=true; - this->graph->first(e.out, v); - while(this->graph->valid(e.out) && !(*backward_filter)[e]) { - this->graph->next(e.out); } - } - } else { - this->graph->next(e.out); - while(this->graph->valid(e.out) && !(*backward_filter)[e]) { - this->graph->next(e.out); } - } - return e; - } - EdgeIt& next(EdgeIt& e) const { - if (!e.backward) { - this->graph->next(e.e); - while(this->graph->valid(e.e) && !(*forward_filter)[e]) { - this->graph->next(e.e); } - if (!this->graph->valid(e.e)) { - e.backward=true; - this->graph->first(e.e); - while(this->graph->valid(e.e) && !(*backward_filter)[e]) { - this->graph->next(e.e); } - } - } else { - this->graph->next(e.e); - while(this->graph->valid(e.e) && !(*backward_filter)[e]) { - this->graph->next(e.e); } - } - return e; - } +// using GraphWrapper::next; +// // NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } +// OutEdgeIt& next(OutEdgeIt& e) const { +// if (!e.backward) { +// Node v=this->graph->aNode(e.out); +// this->graph->next(e.out); +// while(this->graph->valid(e.out) && !(*forward_filter)[e]) { +// this->graph->next(e.out); } +// if (!this->graph->valid(e.out)) { +// e.backward=true; +// this->graph->first(e.in, v); +// while(this->graph->valid(e.in) && !(*backward_filter)[e]) { +// this->graph->next(e.in); } +// } +// } else { +// this->graph->next(e.in); +// while(this->graph->valid(e.in) && !(*backward_filter)[e]) { +// this->graph->next(e.in); } +// } +// return e; +// } +// // FIXME Not tested +// InEdgeIt& next(InEdgeIt& e) const { +// if (!e.backward) { +// Node v=this->graph->aNode(e.in); +// this->graph->next(e.in); +// while(this->graph->valid(e.in) && !(*forward_filter)[e]) { +// this->graph->next(e.in); } +// if (!this->graph->valid(e.in)) { +// e.backward=true; +// this->graph->first(e.out, v); +// while(this->graph->valid(e.out) && !(*backward_filter)[e]) { +// this->graph->next(e.out); } +// } +// } else { +// this->graph->next(e.out); +// while(this->graph->valid(e.out) && !(*backward_filter)[e]) { +// this->graph->next(e.out); } +// } +// return e; +// } +// EdgeIt& next(EdgeIt& e) const { +// if (!e.backward) { +// this->graph->next(e.e); +// while(this->graph->valid(e.e) && !(*forward_filter)[e]) { +// this->graph->next(e.e); } +// if (!this->graph->valid(e.e)) { +// e.backward=true; +// this->graph->first(e.e); +// while(this->graph->valid(e.e) && !(*backward_filter)[e]) { +// this->graph->next(e.e); } +// } +// } else { +// this->graph->next(e.e); +// while(this->graph->valid(e.e) && !(*backward_filter)[e]) { +// this->graph->next(e.e); } +// } +// return e; +// } Node tail(Edge e) const { return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } Node head(Edge e) const { return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } - Node aNode(OutEdgeIt e) const { - return ((!e.backward) ? this->graph->aNode(e.out) : - this->graph->aNode(e.in)); } - Node bNode(OutEdgeIt e) const { - return ((!e.backward) ? this->graph->bNode(e.out) : - this->graph->bNode(e.in)); } +// Node aNode(OutEdgeIt e) const { +// return ((!e.backward) ? this->graph->aNode(e.out) : +// this->graph->aNode(e.in)); } +// Node bNode(OutEdgeIt e) const { +// return ((!e.backward) ? this->graph->bNode(e.out) : +// this->graph->bNode(e.in)); } - Node aNode(InEdgeIt e) const { - return ((!e.backward) ? this->graph->aNode(e.in) : - this->graph->aNode(e.out)); } - Node bNode(InEdgeIt e) const { - return ((!e.backward) ? this->graph->bNode(e.in) : - this->graph->bNode(e.out)); } +// Node aNode(InEdgeIt e) const { +// return ((!e.backward) ? this->graph->aNode(e.in) : +// this->graph->aNode(e.out)); } +// Node bNode(InEdgeIt e) const { +// return ((!e.backward) ? this->graph->bNode(e.in) : +// this->graph->bNode(e.out)); } /// Gives back the opposite edge. Edge opposite(const Edge& e) const { @@ -893,11 +1012,11 @@ // int id(Node v) const { return graph->id(v); } - bool valid(Node n) const { return GraphWrapper::valid(n); } - bool valid(Edge e) const { - return this->graph->valid(e); - //return e.forward ? graph->valid(e.out) : graph->valid(e.in); - } +// bool valid(Node n) const { return GraphWrapper::valid(n); } +// bool valid(Edge e) const { +// return this->graph->valid(e); +// //return e.forward ? graph->valid(e.out) : graph->valid(e.in); +// } bool forward(const Edge& e) const { return !e.backward; } bool backward(const Edge& e) const { return e.backward; } @@ -939,11 +1058,11 @@ typedef T ValueType; typedef Edge KeyType; EdgeMap(const SubBidirGraphWrapper& _G) : - forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } + ForwardFilterMap, BackwardFilterMap>& g) : + forward_map(*(g.graph)), backward_map(*(g.graph)) { } EdgeMap(const SubBidirGraphWrapper& _G, T a) : - forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } + ForwardFilterMap, BackwardFilterMap>& g, T a) : + forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } void set(Edge e, T a) { if (!e.backward) forward_map.set(e/*.out*/, a); diff -r ce9438c5a82d -r 4297098d9677 src/hugo/list_graph.h --- a/src/hugo/list_graph.h Wed Aug 25 18:55:57 2004 +0000 +++ b/src/hugo/list_graph.h Mon Aug 30 12:01:47 2004 +0000 @@ -131,12 +131,6 @@ Node tail(Edge e) const { return edges[e.n].tail; } Node head(Edge e) const { return edges[e.n].head; } - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } - Node aNode(InEdgeIt e) const { return edges[e.n].head; } - - Node bNode(OutEdgeIt e) const { return edges[e.n].head; } - Node bNode(InEdgeIt e) const { return edges[e.n].tail; } - NodeIt& first(NodeIt& v) const { v=NodeIt(*this); return v; } EdgeIt& first(EdgeIt& e) const { @@ -146,43 +140,6 @@ InEdgeIt& first(InEdgeIt& e, const Node v) const { e=InEdgeIt(*this,v); return e; } -// template< typename It > -// It first() const { It e; first(e); return e; } - -// template< typename It > -// It first(Node v) const { It e; first(e,v); return e; } - - static bool valid(Edge e) { return e.n!=-1; } - static bool valid(Node n) { return n.n!=-1; } - - static void setInvalid(Edge &e) { e.n=-1; } - static void setInvalid(Node &n) { n.n=-1; } - - template static It getNext(It it) - { It tmp(it); return next(tmp); } - - NodeIt& next(NodeIt& it) const { - it.n=nodes[it.n].next; - return it; - } - OutEdgeIt& next(OutEdgeIt& it) const - { it.n=edges[it.n].next_out; return it; } - InEdgeIt& next(InEdgeIt& it) const - { it.n=edges[it.n].next_in; return it; } - EdgeIt& next(EdgeIt& it) const { - if(edges[it.n].next_in!=-1) { - it.n=edges[it.n].next_in; - } - else { - int n; - for(n=nodes[edges[it.n].head].next; - n!=-1 && nodes[n].first_in == -1; - n = nodes[n].next) ; - it.n = (n==-1)?-1:nodes[n].first_in; - } - return it; - } - static int id(Node v) { return v.n; } static int id(Edge e) { return e.n; } @@ -250,7 +207,23 @@ return e; } + + /// Finds an edge between two nodes. + /// Finds an edge from node \c u to node \c v. + /// + /// If \c prev is \ref INVALID (this is the default value), then + /// It finds the first edge from \c u to \c v. Otherwise it looks for + /// the next edge from \c u to \c v after \c prev. + /// \return The found edge or INVALID if there is no such an edge. + Edge findEdge(Node u,Node v, Edge prev = INVALID) + { + int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; + while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; + prev.n=e; + return prev; + } + private: void eraseEdge(int n) { @@ -324,16 +297,25 @@ bool operator==(const Node i) const {return n==i.n;} bool operator!=(const Node i) const {return n!=i.n;} bool operator<(const Node i) const {return n NodeIt. - NodeIt(const ListGraph& G, const Node &n) : Node(n) { } + NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { } + NodeIt &operator++() { + n=G->nodes[n].next; + return *this; + } + // ///Validity check + // operator bool() { return Node::operator bool(); } }; class Edge { @@ -364,41 +346,69 @@ ///\bug This is a workaround until somebody tells me how to ///make class \c SymListGraph::SymEdgeMap friend of Edge int &idref() {return n;} - const int &idref() const {return n;} - }; + const int &idref() const {return n;} + // ///Validity check + // operator bool() { return n!=-1; } + }; class EdgeIt : public Edge { + const ListGraph *G; friend class ListGraph; public: - EdgeIt(const ListGraph& G) : Edge() { + EdgeIt(const ListGraph& _G) : Edge(), G(&_G) { int m; - for(m=G.first_node; - m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next); - n = (m==-1)?-1:G.nodes[m].first_in; + for(m=_G.first_node; + m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next); + n = (m==-1)?-1:_G.nodes[m].first_in; } EdgeIt (Invalid i) : Edge(i) { } + EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } EdgeIt() : Edge() { } ///\bug This is a workaround until somebody tells me how to ///make class \c SymListGraph::SymEdgeMap friend of Edge int &idref() {return n;} + EdgeIt &operator++() { + if(G->edges[n].next_in!=-1) n=G->edges[n].next_in; + else { + int nn; + for(nn=G->nodes[G->edges[n].head].next; + nn!=-1 && G->nodes[nn].first_in == -1; + nn = G->nodes[nn].next) ; + n = (nn==-1)?-1:G->nodes[nn].first_in; + } + return *this; + } + // ///Validity check + // operator bool() { return Edge::operator bool(); } }; class OutEdgeIt : public Edge { + const ListGraph *G; friend class ListGraph; public: OutEdgeIt() : Edge() { } + OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } OutEdgeIt (Invalid i) : Edge(i) { } - OutEdgeIt(const ListGraph& G,const Node v) - : Edge(G.nodes[v.n].first_out) {} + OutEdgeIt(const ListGraph& _G,const Node v) + : Edge(_G.nodes[v.n].first_out), G(&_G) {} + OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; } + // ///Validity check + // operator bool() { return Edge::operator bool(); } }; class InEdgeIt : public Edge { + const ListGraph *G; friend class ListGraph; public: InEdgeIt() : Edge() { } + InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { } InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {} + InEdgeIt(const ListGraph& _G,Node v) + : Edge(_G.nodes[v.n].first_in), G(&_G) { } + InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } + // ///Validity check + // operator bool() { return Edge::operator bool(); } }; template class NodeMap : public DynMapBase @@ -838,12 +848,6 @@ Node tail(Edge e) const { return INVALID; } Node head(Edge e) const { return INVALID; } - Node aNode(OutEdgeIt e) const { return INVALID; } - Node aNode(InEdgeIt e) const { return INVALID; } - - Node bNode(OutEdgeIt e) const { return INVALID; } - Node bNode(InEdgeIt e) const { return INVALID; } - NodeIt& first(NodeIt& v) const { v=NodeIt(*this); return v; } EdgeIt& first(EdgeIt& e) const { @@ -853,29 +857,6 @@ InEdgeIt& first(InEdgeIt& e, const Node v) const { e=InEdgeIt(*this,v); return e; } -// template< typename It > -// It first() const { It e; first(e); return e; } - -// template< typename It > -// It first(Node v) const { It e; first(e,v); return e; } - - bool valid(Edge e) const { return false; } - bool valid(Node n) const { return n.n!=-1; } - - void setInvalid(Edge &e) { } - void setInvalid(Node &n) { n.n=-1; } - - template It getNext(It it) const - { It tmp(it); return next(tmp); } - - NodeIt& next(NodeIt& it) const { - it.n=nodes[it.n].next; - return it; - } - OutEdgeIt& next(OutEdgeIt& it) const { return it; } - InEdgeIt& next(InEdgeIt& it) const { return it; } - EdgeIt& next(EdgeIt& it) const { return it; } - int id(Node v) const { return v.n; } int id(Edge e) const { return -1; } @@ -927,6 +908,12 @@ i!=dyn_node_maps.end(); ++i) (**i).erase(nn); } + + Edge findEdge(Node u,Node v, Edge prev = INVALID) + { + return INVALID; + } + ///\bug Dynamic maps must be updated! /// void clear() { @@ -955,14 +942,17 @@ }; class NodeIt : public Node { + const NodeSet *G; friend class NodeSet; public: NodeIt() : Node() { } + NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { } NodeIt(Invalid i) : Node(i) { } - NodeIt(const NodeSet& G) : Node(G.first_node) { } - ///\todo Undocumented conversion Node -\> NodeIt. - NodeIt(const NodeSet& G, const Node &n) : Node(n) { } - + NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { } + NodeIt &operator++() { + n=G->nodes[n].next; + return *this; + } }; class Edge { @@ -993,27 +983,33 @@ //friend class NodeSet; public: EdgeIt(const NodeSet& G) : Edge() { } + EdgeIt(const NodeSet&, Edge) : Edge() { } EdgeIt (Invalid i) : Edge(i) { } EdgeIt() : Edge() { } ///\bug This is a workaround until somebody tells me how to ///make class \c SymNodeSet::SymEdgeMap friend of Edge // int idref() {return -1;} + EdgeIt operator++() { return INVALID; } }; class OutEdgeIt : public Edge { friend class NodeSet; public: OutEdgeIt() : Edge() { } + OutEdgeIt(const NodeSet&, Edge) : Edge() { } OutEdgeIt (Invalid i) : Edge(i) { } OutEdgeIt(const NodeSet& G,const Node v) : Edge() {} + OutEdgeIt operator++() { return INVALID; } }; class InEdgeIt : public Edge { friend class NodeSet; public: InEdgeIt() : Edge() { } + InEdgeIt(const NodeSet&, Edge) : Edge() { } InEdgeIt (Invalid i) : Edge(i) { } InEdgeIt(const NodeSet& G,Node v) :Edge() {} + InEdgeIt operator++() { return INVALID; } }; template class NodeMap : public DynMapBase @@ -1199,15 +1195,15 @@ friend class EdgeSet; public: NodeIt() : NodeGraphType::NodeIt() { } + NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { } NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {} NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { } NodeIt(const typename NodeGraphType::NodeIt &n) : NodeGraphType::NodeIt(n) {} - ///\todo Undocumented conversion Node -\> NodeIt. - NodeIt(const EdgeSet& _G, const Node &n) - : NodeGraphType::NodeIt(_G.G,n) { } operator Node() { return Node(*this);} + NodeIt &operator++() + { this->NodeGraphType::NodeIt::operator++(); return *this;} }; private: @@ -1311,12 +1307,6 @@ Node tail(Edge e) const { return edges[e.n].tail; } Node head(Edge e) const { return edges[e.n].head; } - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } - Node aNode(InEdgeIt e) const { return edges[e.n].head; } - - Node bNode(OutEdgeIt e) const { return edges[e.n].head; } - Node bNode(InEdgeIt e) const { return edges[e.n].tail; } - NodeIt& first(NodeIt& v) const { v=NodeIt(*this); return v; } EdgeIt& first(EdgeIt& e) const { @@ -1326,40 +1316,6 @@ InEdgeIt& first(InEdgeIt& e, const Node v) const { e=InEdgeIt(*this,v); return e; } -// template< typename It > -// It first() const { It e; first(e); return e; } - -// template< typename It > -// It first(Node v) const { It e; first(e,v); return e; } - - bool valid(Edge e) const { return e.n!=-1; } - bool valid(Node n) const { return G.valid(n); } - - void setInvalid(Edge &e) { e.n=-1; } - void setInvalid(Node &n) { G.setInvalid(n); } - - template It getNext(It it) const - { It tmp(it); return next(tmp); } - - NodeIt& next(NodeIt& it) const { G.next(it); return it; } - OutEdgeIt& next(OutEdgeIt& it) const - { it.n=edges[it.n].next_out; return it; } - InEdgeIt& next(InEdgeIt& it) const - { it.n=edges[it.n].next_in; return it; } - EdgeIt& next(EdgeIt& it) const { - if(edges[it.n].next_in!=-1) { - it.n=edges[it.n].next_in; - } - else { - NodeIt n(*this,edges[it.n].head); - for(n=next(n); - valid(n) && nodes[n].first_in == -1; - next(n)) ; - it.n = (valid(n))?-1:nodes[n].first_in; - } - return it; - } - int id(Edge e) const { return e.n; } /// Adds a new node to the graph. @@ -1398,6 +1354,22 @@ return e; } + /// Finds an edge between two nodes. + + /// Finds an edge from node \c u to node \c v. + /// + /// If \c prev is \ref INVALID (this is the default value), then + /// It finds the first edge from \c u to \c v. Otherwise it looks for + /// the next edge from \c u to \c v after \c prev. + /// \return The found edge or INVALID if there is no such an edge. + Edge findEdge(Node u,Node v, Edge prev = INVALID) + { + int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out; + while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out; + prev.n=e; + return prev; + } + private: void eraseEdge(int n) { @@ -1460,7 +1432,7 @@ friend class Node; friend class NodeIt; public: - ///\bug It shoud be at least protected + ///\bug It should be at least protected /// int n; protected: @@ -1483,38 +1455,54 @@ friend class EdgeSet; template friend class EdgeMap; - + const EdgeSet *G; public: - EdgeIt(const EdgeSet& G) : Edge() { + EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) { // typename NodeGraphType::Node m; NodeIt m; - for(G.first(m); - G.valid(m) && G.nodes[m].first_in == -1; G.next(m)); - //AJJAJ! This is a non sense!!!!!!! - this->n = G.valid(m)?-1:G.nodes[m].first_in; + for(G->first(m); + m!=INVALID && G->nodes[m].first_in == -1; ++m); + ///\bug AJJAJ! This is a non sense!!!!!!! + this->n = m!=INVALID?-1:G->nodes[m].first_in; } + EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } EdgeIt (Invalid i) : Edge(i) { } EdgeIt() : Edge() { } - ///\bug This is a workaround until somebody tells me how to + ///. + + ///\bug UNIMPLEMENTED!!!!! + // + EdgeIt &operator++() { + return *this; + } + ///\bug This is a workaround until somebody tells me how to ///make class \c SymEdgeSet::SymEdgeMap friend of Edge int &idref() {return this->n;} }; class OutEdgeIt : public Edge { + const EdgeSet *G; friend class EdgeSet; public: OutEdgeIt() : Edge() { } OutEdgeIt (Invalid i) : Edge(i) { } + OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } - OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { } + OutEdgeIt(const EdgeSet& _G,const Node v) : + Edge(_G.nodes[v].first_out), G(&_G) { } + OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; } }; class InEdgeIt : public Edge { + const EdgeSet *G; friend class EdgeSet; public: InEdgeIt() : Edge() { } InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { } + InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { } + InEdgeIt(const EdgeSet& _G,Node v) + : Edge(_G.nodes[v].first_in), G(&_G) { } + InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } }; template class NodeMap : @@ -1554,17 +1542,17 @@ { //FIXME: What if there are empty Id's? //FIXME: Can I use 'this' in a constructor? - G->dyn_edge_maps.push_back(this); + this->G->dyn_edge_maps.push_back(this); } EdgeMap(const EdgeSet &_G,const T &t) : DynMapBase(_G), container(_G.maxEdgeId(),t) { - G->dyn_edge_maps.push_back(this); + this->G->dyn_edge_maps.push_back(this); } EdgeMap(const EdgeMap &m) : DynMapBase(*m.G), container(m.container) { - G->dyn_edge_maps.push_back(this); + this->G->dyn_edge_maps.push_back(this); } ///\todo It can copy between different types. @@ -1572,7 +1560,7 @@ template EdgeMap(const EdgeMap &m) : DynMapBase(*m.G), container(m.container.size()) { - G->dyn_edge_maps.push_back(this); + this->G->dyn_edge_maps.push_back(this); typename std::vector::const_iterator i; for(typename std::vector::const_iterator i=m.container.begin(); i!=m.container.end(); @@ -1581,15 +1569,15 @@ } ~EdgeMap() { - if(G) { + if(this->G) { typename std::vector* >::iterator i; - for(i=G->dyn_edge_maps.begin(); - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; + for(i=this->G->dyn_edge_maps.begin(); + i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ; //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... //A better way to do that: (Is this really important?) if(*i==this) { - *i=G->dyn_edge_maps.back(); - G->dyn_edge_maps.pop_back(); + *i=this->G->dyn_edge_maps.back(); + this->G->dyn_edge_maps.pop_back(); } } } @@ -1602,16 +1590,16 @@ ///\bug This doesn't work. Why? /// void set(Edge n, T a) { container[n.n]=a; } - void set(Edge n, T a) { container[G->id(n)]=a; } + void set(Edge n, T a) { container[this->G->id(n)]=a; } //T get(Edge n) const { return container[n.n]; } typename std::vector::reference ///\bug This doesn't work. Why? /// operator[](Edge n) { return container[n.n]; } - operator[](Edge n) { return container[G->id(n)]; } + operator[](Edge n) { return container[this->G->id(n)]; } typename std::vector::const_reference ///\bug This doesn't work. Why? /// operator[](Edge n) const { return container[n.n]; } - operator[](Edge n) const { return container[G->id(n)]; } + operator[](Edge n) const { return container[this->G->id(n)]; } ///\warning There is no safety check at all! ///Using operator = between maps attached to different graph may diff -r ce9438c5a82d -r 4297098d9677 src/hugo/max_flow.h --- a/src/hugo/max_flow.h Wed Aug 25 18:55:57 2004 +0000 +++ b/src/hugo/max_flow.h Mon Aug 30 12:01:47 2004 +0000 @@ -5,7 +5,7 @@ #include #include -#include +//#include #include #include @@ -62,10 +62,10 @@ const CapMap* capacity; FlowMap* flow; int n; //the number of nodes of G - typedef ResGraphWrapper ResGW; + // typedef ResGraphWrapper ResGW; //typedef ExpResGraphWrapper ResGW; - typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; - typedef typename ResGW::Edge ResGWEdge; + // typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; + // typedef typename ResGW::Edge ResGWEdge; typedef typename Graph::template NodeMap ReachedMap; @@ -112,27 +112,27 @@ /// Do not needle this flag only if necessary. StatusEnum status; -// int number_of_augmentations; + // int number_of_augmentations; -// template -// class TrickyReachedMap { -// protected: -// IntMap* map; -// int* number_of_augmentations; -// public: -// TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) : -// map(&_map), number_of_augmentations(&_number_of_augmentations) { } -// void set(const Node& n, bool b) { -// if (b) -// map->set(n, *number_of_augmentations); -// else -// map->set(n, *number_of_augmentations-1); -// } -// bool operator[](const Node& n) const { -// return (*map)[n]==*number_of_augmentations; -// } -// }; + // template + // class TrickyReachedMap { + // protected: + // IntMap* map; + // int* number_of_augmentations; + // public: + // TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) : + // map(&_map), number_of_augmentations(&_number_of_augmentations) { } + // void set(const Node& n, bool b) { + // if (b) + // map->set(n, *number_of_augmentations); + // else + // map->set(n, *number_of_augmentations-1); + // } + // bool operator[](const Node& n) const { + // return (*map)[n]==*number_of_augmentations; + // } + // }; ///Constructor @@ -234,7 +234,7 @@ } else break; } - if ( !g->valid(first[b]) ) --b; + if ( first[b]==INVALID ) --b; else { end=false; Node w=first[b]; @@ -289,8 +289,7 @@ bfs_queue.pop(); int l=level[v]+1; - InEdgeIt e; - for(g->first(e,v); g->valid(e); g->next(e)) { + for(InEdgeIt e(*g,v); e!=INVALID; ++e) { if ( (*capacity)[e] <= (*flow)[e] ) continue; Node u=g->tail(e); if ( level[u] >= n ) { @@ -303,10 +302,9 @@ } } - OutEdgeIt f; - for(g->first(f,v); g->valid(f); g->next(f)) { - if ( 0 >= (*flow)[f] ) continue; - Node u=g->head(f); + for(OutEdgeIt e(*g,v); e!=INVALID; ++e) { + if ( 0 >= (*flow)[e] ) continue; + Node u=g->head(e); if ( level[u] >= n ) { bfs_queue.push(u); level.set(u, l); @@ -323,7 +321,7 @@ if ( b == 0 ) break; - if ( !g->valid(first[b]) ) --b; + if ( first[b]==INVALID ) --b; else { Node w=first[b]; @@ -351,10 +349,10 @@ /// the maximum flow. /// It can be called already after running \ref preflowPhase1. Num flowValue() const { -// Num a=0; -// for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e]; -// for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e]; -// return a; + // Num a=0; + // for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e]; + // for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e]; + // return a; return excess[t]; //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan } @@ -374,10 +372,9 @@ /// for MinCut computation template void actMinCut(_CutMap& M) const { - NodeIt v; switch (status) { - case AFTER_PRE_FLOW_PHASE_1: - for(g->first(v); g->valid(v); g->next(v)) { + case AFTER_PRE_FLOW_PHASE_1: + for(NodeIt v(*g); v!=INVALID; ++v) { if (level[v] < n) { M.set(v, false); } else { @@ -385,10 +382,10 @@ } } break; - case AFTER_PRE_FLOW_PHASE_2: - case AFTER_NOTHING: - case AFTER_AUGMENTING: - case AFTER_FAST_AUGMENTING: + case AFTER_PRE_FLOW_PHASE_2: + case AFTER_NOTHING: + case AFTER_AUGMENTING: + case AFTER_FAST_AUGMENTING: minMinCut(M); break; } @@ -412,8 +409,7 @@ Node w=queue.front(); queue.pop(); - OutEdgeIt e; - for(g->first(e,w) ; g->valid(e); g->next(e)) { + for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { Node v=g->head(e); if (!M[v] && (*flow)[e] < (*capacity)[e] ) { queue.push(v); @@ -421,10 +417,9 @@ } } - InEdgeIt f; - for(g->first(f,w) ; g->valid(f); g->next(f)) { - Node v=g->tail(f); - if (!M[v] && (*flow)[f] > 0 ) { + for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { + Node v=g->tail(e); + if (!M[v] && (*flow)[e] > 0 ) { queue.push(v); M.set(v, true); } @@ -442,10 +437,7 @@ template void maxMinCut(_CutMap& M) const { - NodeIt v; - for(g->first(v) ; g->valid(v); g->next(v)) { - M.set(v, true); - } + for(NodeIt v(*g) ; v!=INVALID; ++v) M.set(v, true); std::queue queue; @@ -456,8 +448,7 @@ Node w=queue.front(); queue.pop(); - InEdgeIt e; - for(g->first(e,w) ; g->valid(e); g->next(e)) { + for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { Node v=g->tail(e); if (M[v] && (*flow)[e] < (*capacity)[e] ) { queue.push(v); @@ -465,10 +456,9 @@ } } - OutEdgeIt f; - for(g->first(f,w) ; g->valid(f); g->next(f)) { - Node v=g->head(f); - if (M[v] && (*flow)[f] > 0 ) { + for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { + Node v=g->head(e); + if (M[v] && (*flow)[e] > 0 ) { queue.push(v); M.set(v, false); } @@ -518,14 +508,12 @@ Num exc=excess[w]; int newlevel=n; //bound on the next level of w - OutEdgeIt e; - for(g->first(e,w); g->valid(e); g->next(e)) { - + for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { if ( (*flow)[e] >= (*capacity)[e] ) continue; Node v=g->head(e); if( lev > level[v] ) { //Push is allowed now - + if ( excess[v]<=0 && v!=t && v!=s ) { next.set(v,first[level[v]]); first[level[v]]=v; @@ -534,9 +522,9 @@ Num cap=(*capacity)[e]; Num flo=(*flow)[e]; Num remcap=cap-flo; - + if ( remcap >= exc ) { //A nonsaturating push. - + flow->set(e, flo+exc); excess.set(v, excess[v]+exc); exc=0; @@ -551,9 +539,8 @@ } //for out edges wv if ( exc > 0 ) { - InEdgeIt e; - for(g->first(e,w); g->valid(e); g->next(e)) { - + for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { + if( (*flow)[e] <= 0 ) continue; Node v=g->tail(e); @@ -584,49 +571,37 @@ } // if w still has excess after the out edge for cycle excess.set(w, exc); - + return newlevel; } - - - + + + void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first, VecNode& level_list, NNMap& left, NNMap& right) { - switch (fe) { //setting excess + switch (fe) { //setting excess case NO_FLOW: + for(EdgeIt e(*g); e!=INVALID; ++e) flow->set(e,0); + for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0); + break; + case ZERO_FLOW: + for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0); + break; + case GEN_FLOW: + for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0); { - EdgeIt e; - for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0); - - NodeIt v; - for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0); - break; + Num exc=0; + for(InEdgeIt e(*g,t) ; e!=INVALID; ++e) exc+=(*flow)[e]; + for(OutEdgeIt e(*g,t) ; e!=INVALID; ++e) exc-=(*flow)[e]; + excess.set(t,exc); } - case ZERO_FLOW: - { - NodeIt v; - for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0); - break; - } - case GEN_FLOW: - { - NodeIt v; - for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0); - - Num exc=0; - InEdgeIt e; - for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e]; - OutEdgeIt f; - for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f]; - excess.set(t,exc); - break; - } - default: break; + break; + default: + break; } - - NodeIt v; - for(g->first(v); g->valid(v); g->next(v)) level.set(v,n); + + for(NodeIt v(*g); v!=INVALID; ++v) level.set(v,n); //setting each node to level n std::queue bfs_queue; @@ -635,219 +610,197 @@ switch (fe) { case NO_FLOW: //flow is already set to const zero case ZERO_FLOW: - { - //Reverse_bfs from t, to find the starting level. - level.set(t,0); - bfs_queue.push(t); - - while (!bfs_queue.empty()) { - - Node v=bfs_queue.front(); - bfs_queue.pop(); - int l=level[v]+1; - - InEdgeIt e; - for(g->first(e,v); g->valid(e); g->next(e)) { - Node w=g->tail(e); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( g->valid(z) ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } + //Reverse_bfs from t, to find the starting level. + level.set(t,0); + bfs_queue.push(t); + + while (!bfs_queue.empty()) { + + Node v=bfs_queue.front(); + bfs_queue.pop(); + int l=level[v]+1; + + for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { + Node w=g->tail(e); + if ( level[w] == n && w != s ) { + bfs_queue.push(w); + Node z=level_list[l]; + if ( z!=INVALID ) left.set(z,w); + right.set(w,z); + level_list[l]=w; + level.set(w, l); } } - - //the starting flow - OutEdgeIt e; - for(g->first(e,s); g->valid(e); g->next(e)) - { - Num c=(*capacity)[e]; - if ( c <= 0 ) continue; - Node w=g->head(e); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) //putting into the stack - { - next.set(w,first[level[w]]); - first[level[w]]=w; - } - flow->set(e, c); - excess.set(w, excess[w]+c); - } - } - break; } - - case GEN_FLOW: - { - //Reverse_bfs from t in the residual graph, - //to find the starting level. - level.set(t,0); - bfs_queue.push(t); - - while (!bfs_queue.empty()) { - - Node v=bfs_queue.front(); - bfs_queue.pop(); - int l=level[v]+1; - - InEdgeIt e; - for(g->first(e,v); g->valid(e); g->next(e)) { - if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node w=g->tail(e); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( g->valid(z) ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } - } - - OutEdgeIt f; - for(g->first(f,v); g->valid(f); g->next(f)) { - if ( 0 >= (*flow)[f] ) continue; - Node w=g->head(f); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( g->valid(z) ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } + + //the starting flow + for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) + { + Num c=(*capacity)[e]; + if ( c <= 0 ) continue; + Node w=g->head(e); + if ( level[w] < n ) { + if ( excess[w] <= 0 && w!=t ) //putting into the stack + { + next.set(w,first[level[w]]); + first[level[w]]=w; + } + flow->set(e, c); + excess.set(w, excess[w]+c); } } - - //the starting flow - OutEdgeIt e; - for(g->first(e,s); g->valid(e); g->next(e)) - { - Num rem=(*capacity)[e]-(*flow)[e]; - if ( rem <= 0 ) continue; - Node w=g->head(e); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) //putting into the stack - { - next.set(w,first[level[w]]); - first[level[w]]=w; - } - flow->set(e, (*capacity)[e]); - excess.set(w, excess[w]+rem); - } - } - - InEdgeIt f; - for(g->first(f,s); g->valid(f); g->next(f)) - { - if ( (*flow)[f] <= 0 ) continue; - Node w=g->tail(f); - if ( level[w] < n ) { - if ( excess[w] <= 0 && w!=t ) - { - next.set(w,first[level[w]]); - first[level[w]]=w; - } - excess.set(w, excess[w]+(*flow)[f]); - flow->set(f, 0); - } - } - break; - } //case GEN_FLOW - - case PRE_FLOW: - { - //Reverse_bfs from t in the residual graph, - //to find the starting level. - level.set(t,0); - bfs_queue.push(t); - - while (!bfs_queue.empty()) { - - Node v=bfs_queue.front(); - bfs_queue.pop(); - int l=level[v]+1; - - InEdgeIt e; - for(g->first(e,v); g->valid(e); g->next(e)) { - if ( (*capacity)[e] <= (*flow)[e] ) continue; - Node w=g->tail(e); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( g->valid(z) ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } - } - - OutEdgeIt f; - for(g->first(f,v); g->valid(f); g->next(f)) { - if ( 0 >= (*flow)[f] ) continue; - Node w=g->head(f); - if ( level[w] == n && w != s ) { - bfs_queue.push(w); - Node z=level_list[l]; - if ( g->valid(z) ) left.set(z,w); - right.set(w,z); - level_list[l]=w; - level.set(w, l); - } + break; + case GEN_FLOW: + //Reverse_bfs from t in the residual graph, + //to find the starting level. + level.set(t,0); + bfs_queue.push(t); + + while (!bfs_queue.empty()) { + + Node v=bfs_queue.front(); + bfs_queue.pop(); + int l=level[v]+1; + + for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { + if ( (*capacity)[e] <= (*flow)[e] ) continue; + Node w=g->tail(e); + if ( level[w] == n && w != s ) { + bfs_queue.push(w); + Node z=level_list[l]; + if ( z!=INVALID ) left.set(z,w); + right.set(w,z); + level_list[l]=w; + level.set(w, l); } } - - - //the starting flow - OutEdgeIt e; - for(g->first(e,s); g->valid(e); g->next(e)) + + for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) { + if ( 0 >= (*flow)[e] ) continue; + Node w=g->head(e); + if ( level[w] == n && w != s ) { + bfs_queue.push(w); + Node z=level_list[l]; + if ( z!=INVALID ) left.set(z,w); + right.set(w,z); + level_list[l]=w; + level.set(w, l); + } + } + } + + //the starting flow + for(OutEdgeIt e(*g,s); e!=INVALID; ++e) + { + Num rem=(*capacity)[e]-(*flow)[e]; + if ( rem <= 0 ) continue; + Node w=g->head(e); + if ( level[w] < n ) { + if ( excess[w] <= 0 && w!=t ) //putting into the stack + { + next.set(w,first[level[w]]); + first[level[w]]=w; + } + flow->set(e, (*capacity)[e]); + excess.set(w, excess[w]+rem); + } + } + + for(InEdgeIt e(*g,s); e!=INVALID; ++e) + { + if ( (*flow)[e] <= 0 ) continue; + Node w=g->tail(e); + if ( level[w] < n ) { + if ( excess[w] <= 0 && w!=t ) + { + next.set(w,first[level[w]]); + first[level[w]]=w; + } + excess.set(w, excess[w]+(*flow)[e]); + flow->set(e, 0); + } + } + break; + case PRE_FLOW: + //Reverse_bfs from t in the residual graph, + //to find the starting level. + level.set(t,0); + bfs_queue.push(t); + + while (!bfs_queue.empty()) { + + Node v=bfs_queue.front(); + bfs_queue.pop(); + int l=level[v]+1; + + for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { + if ( (*capacity)[e] <= (*flow)[e] ) continue; + Node w=g->tail(e); + if ( level[w] == n && w != s ) { + bfs_queue.push(w); + Node z=level_list[l]; + if ( z!=INVALID ) left.set(z,w); + right.set(w,z); + level_list[l]=w; + level.set(w, l); + } + } + + for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) { + if ( 0 >= (*flow)[e] ) continue; + Node w=g->head(e); + if ( level[w] == n && w != s ) { + bfs_queue.push(w); + Node z=level_list[l]; + if ( z!=INVALID ) left.set(z,w); + right.set(w,z); + level_list[l]=w; + level.set(w, l); + } + } + } + + + //the starting flow + for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { + Num rem=(*capacity)[e]-(*flow)[e]; + if ( rem <= 0 ) continue; + Node w=g->head(e); + if ( level[w] < n ) { + flow->set(e, (*capacity)[e]); + excess.set(w, excess[w]+rem); + } + } + + for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) { + if ( (*flow)[e] <= 0 ) continue; + Node w=g->tail(e); + if ( level[w] < n ) { + excess.set(w, excess[w]+(*flow)[e]); + flow->set(e, 0); + } + } + + //computing the excess + for(NodeIt w(*g); w!=INVALID; ++w) { + Num exc=0; + + for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) exc+=(*flow)[e]; + for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) exc-=(*flow)[e]; + + excess.set(w,exc); + + //putting the active nodes into the stack + int lev=level[w]; + if ( exc > 0 && lev < n && Node(w) != t ) + ///\bug if ( exc > 0 && lev < n && w != t ) temporarily for working with wrappers. { - Num rem=(*capacity)[e]-(*flow)[e]; - if ( rem <= 0 ) continue; - Node w=g->head(e); - if ( level[w] < n ) { - flow->set(e, (*capacity)[e]); - excess.set(w, excess[w]+rem); - } + next.set(w,first[lev]); + first[lev]=w; } - - InEdgeIt f; - for(g->first(f,s); g->valid(f); g->next(f)) - { - if ( (*flow)[f] <= 0 ) continue; - Node w=g->tail(f); - if ( level[w] < n ) { - excess.set(w, excess[w]+(*flow)[f]); - flow->set(f, 0); - } - } - - NodeIt w; //computing the excess - for(g->first(w); g->valid(w); g->next(w)) { - Num exc=0; - - InEdgeIt e; - for(g->first(e,w); g->valid(e); g->next(e)) exc+=(*flow)[e]; - OutEdgeIt f; - for(g->first(f,w); g->valid(f); g->next(f)) exc-=(*flow)[f]; - - excess.set(w,exc); - - //putting the active nodes into the stack - int lev=level[w]; - if ( exc > 0 && lev < n && Node(w) != t ) -///\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. - { - next.set(w,first[lev]); - first[lev]=w; - } - } - break; - } //case PRE_FLOW - } + } + break; + } //switch } //preflowPreproc @@ -862,8 +815,8 @@ Node left_n=left[w]; //unlacing starts - if ( g->valid(right_n) ) { - if ( g->valid(left_n) ) { + if ( right_n!=INVALID ) { + if ( left_n!=INVALID ) { right.set(left_n, right_n); left.set(right_n, left_n); } else { @@ -871,7 +824,7 @@ left.set(right_n, INVALID); } } else { - if ( g->valid(left_n) ) { + if ( left_n!=INVALID ) { right.set(left_n, INVALID); } else { level_list[lev]=INVALID; @@ -879,12 +832,12 @@ } //unlacing ends - if ( !g->valid(level_list[lev]) ) { + if ( level_list[lev]==INVALID ) { //gapping starts for (int i=lev; i!=k ; ) { Node v=level_list[++i]; - while ( g->valid(v) ) { + while ( v!=INVALID ) { level.set(v,n); v=right[v]; } @@ -907,7 +860,7 @@ if ( what_heur ) b=newlevel; if ( k < newlevel ) ++k; //now k=newlevel Node z=level_list[newlevel]; - if ( g->valid(z) ) left.set(z,w); + if ( z!=INVALID ) left.set(z,w); right.set(w,z); left.set(w,INVALID); level_list[newlevel]=w; @@ -918,26 +871,23 @@ void printexcess() {//// std::cout << "Excesses:" <first(v); g->valid(v); g->next(v)) { + for(NodeIt v(*g); v!=INVALID ; ++v) { std::cout << 1+(g->id(v)) << ":" << excess[v]<first(v); g->valid(v); g->next(v)) { + for(NodeIt v(*g); v!=INVALID ; ++v) { std::cout << 1+(g->id(v)) << ":" << level[v]<first(v); g->valid(v); g->next(v)) { + for(NodeIt v(*g); v!=INVALID ; ++v) { std::cout << 1+(g->id(v)) << ":" << level[v]<; - - NodeMap(const StaticGraphSkeleton &) {} - NodeMap(const StaticGraphSkeleton &, T) {} + NodeMap(const StaticGraphSkeleton&) { } + NodeMap(const StaticGraphSkeleton&, T) { } ///Copy constructor - template NodeMap(const NodeMap &) {} + template NodeMap(const NodeMap&) { } ///Assignment operator - template NodeMap &operator=(const NodeMap &) - {return *this;} + template NodeMap& operator=(const NodeMap&) + { return *this; } }; ///Reference map of the edges to type \c T. @@ -295,14 +322,14 @@ typedef T ValueType; typedef Edge KeyType; - EdgeMap(const StaticGraphSkeleton &) {} - EdgeMap(const StaticGraphSkeleton &, T ) {} + EdgeMap(const StaticGraphSkeleton&) { } + EdgeMap(const StaticGraphSkeleton&, T) { } ///Copy constructor - template EdgeMap(const EdgeMap &) {} + template EdgeMap(const EdgeMap&) { } ///Assignment operator - template EdgeMap &operator=(const EdgeMap &) - {return *this;} + template EdgeMap &operator=(const EdgeMap&) + { return *this; } }; }; @@ -317,31 +344,31 @@ { public: /// Defalult constructor. - GraphSkeleton() {} + GraphSkeleton() { } ///Copy consructor. ///\todo It is not clear, what we expect from a copy constructor. ///E.g. How to assign the nodes/edges to each other? What about maps? - GraphSkeleton(const GraphSkeleton &G) {} + GraphSkeleton(const GraphSkeleton&) { } ///Add a new node to the graph. /// \return the new node. /// - Node addNode() { return INVALID;} + Node addNode() { return INVALID; } ///Add a new edge to the graph. ///Add a new edge to the graph with tail node \c tail ///and head node \c head. ///\return the new edge. - Edge addEdge(Node, Node) { return INVALID;} + Edge addEdge(Node, Node) { return INVALID; } /// Resets the graph. /// This function deletes all edges and nodes of the graph. /// It also frees the memory allocated to store them. /// \todo It might belong to \c EraseableGraphSkeleton. - void clear() {} + void clear() { } }; /// An empty eraseable graph class. @@ -352,14 +379,14 @@ { public: /// Deletes a node. - void erase(Node n) {} + void erase(Node n) { } /// Deletes an edge. - void erase(Edge e) {} + void erase(Edge e) { } /// Defalult constructor. - EraseableGraphSkeleton() {} + EraseableGraphSkeleton() { } ///Copy consructor. - EraseableGraphSkeleton(const GraphSkeleton &G) {} + EraseableGraphSkeleton(const GraphSkeleton&) { } }; // @} diff -r ce9438c5a82d -r 4297098d9677 src/hugo/smart_graph.h --- a/src/hugo/smart_graph.h Wed Aug 25 18:55:57 2004 +0000 +++ b/src/hugo/smart_graph.h Mon Aug 30 12:01:47 2004 +0000 @@ -121,12 +121,6 @@ Node tail(Edge e) const { return edges[e.n].tail; } Node head(Edge e) const { return edges[e.n].head; } - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } - Node aNode(InEdgeIt e) const { return edges[e.n].head; } - - Node bNode(OutEdgeIt e) const { return edges[e.n].head; } - Node bNode(InEdgeIt e) const { return edges[e.n].tail; } - NodeIt& first(NodeIt& v) const { v=NodeIt(*this); return v; } EdgeIt& first(EdgeIt& e) const { @@ -136,41 +130,6 @@ InEdgeIt& first(InEdgeIt& e, const Node v) const { e=InEdgeIt(*this,v); return e; } -// template< typename It > -// It first() const { It e; first(e); return e; } - -// template< typename It > -// It first(Node v) const { It e; first(e,v); return e; } - - static bool valid(Edge e) { return e.n!=-1; } - static bool valid(Node n) { return n.n!=-1; } - - ///\deprecated Use - ///\code - /// e=INVALID; - ///\endcode - ///instead. - static void setInvalid(Edge &e) { e.n=-1; } - ///\deprecated Use - ///\code - /// e=INVALID; - ///\endcode - ///instead. - static void setInvalid(Node &n) { n.n=-1; } - - template It getNext(It it) const - { It tmp(it); return next(tmp); } - - NodeIt& next(NodeIt& it) const { - it.n=(it.n+2)%(nodes.size()+1)-1; - return it; - } - OutEdgeIt& next(OutEdgeIt& it) const - { it.n=edges[it.n].next_out; return it; } - InEdgeIt& next(InEdgeIt& it) const - { it.n=edges[it.n].next_in; return it; } - EdgeIt& next(EdgeIt& it) const { --it.n; return it; } - static int id(Node v) { return v.n; } static int id(Edge e) { return e.n; } @@ -197,6 +156,22 @@ return e; } + /// Finds an edge between two nodes. + + /// Finds an edge from node \c u to node \c v. + /// + /// If \c prev is \ref INVALID (this is the default value), then + /// It finds the first edge from \c u to \c v. Otherwise it looks for + /// the next edge from \c u to \c v after \c prev. + /// \return The found edge or INVALID if there is no such an edge. + Edge findEdge(Node u,Node v, Edge prev = INVALID) + { + int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; + while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; + prev.n=e; + return prev; + } + void clear() {nodes.clear();edges.clear();} class Node { @@ -218,16 +193,24 @@ bool operator==(const Node i) const {return n==i.n;} bool operator!=(const Node i) const {return n!=i.n;} bool operator<(const Node i) const {return n NodeIt. - NodeIt(const SmartGraph& G, const Node &n) : Node(n) { } + NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { } + NodeIt &operator++() { + n=(n+2)%(G->nodes.size()+1)-1; + return *this; + } +// ///Validity check +// operator bool() { return Node::operator bool(); } }; class Edge { @@ -257,36 +240,54 @@ ///\bug This is a workaround until somebody tells me how to ///make class \c SymSmartGraph::SymEdgeMap friend of Edge int &idref() {return n;} - const int &idref() const {return n;} - }; + const int &idref() const {return n;} +// ///Validity check +// operator bool() { return n!=-1; } + }; class EdgeIt : public Edge { + const SmartGraph *G; friend class SmartGraph; public: - EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { } + EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { } + EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { } EdgeIt (Invalid i) : Edge(i) { } EdgeIt() : Edge() { } ///\bug This is a workaround until somebody tells me how to ///make class \c SymSmartGraph::SymEdgeMap friend of Edge int &idref() {return n;} + EdgeIt &operator++() { --n; return *this; } +// ///Validity check +// operator bool() { return Edge::operator bool(); } }; class OutEdgeIt : public Edge { + const SmartGraph *G; friend class SmartGraph; public: OutEdgeIt() : Edge() { } + OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { } OutEdgeIt (Invalid i) : Edge(i) { } - OutEdgeIt(const SmartGraph& G,const Node v) - : Edge(G.nodes[v.n].first_out) {} + OutEdgeIt(const SmartGraph& _G,const Node v) + : Edge(_G.nodes[v.n].first_out), G(&_G) {} + OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; } +// ///Validity check +// operator bool() { return Edge::operator bool(); } }; class InEdgeIt : public Edge { + const SmartGraph *G; friend class SmartGraph; public: InEdgeIt() : Edge() { } + InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { } InEdgeIt (Invalid i) : Edge(i) { } - InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){} + InEdgeIt(const SmartGraph& _G,Node v) + : Edge(_G.nodes[v.n].first_in), G(&_G) { } + InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } +// ///Validity check +// operator bool() { return Edge::operator bool(); } }; template class NodeMap : public DynMapBase diff -r ce9438c5a82d -r 4297098d9677 src/hugo/unionfind.h --- a/src/hugo/unionfind.h Wed Aug 25 18:55:57 2004 +0000 +++ b/src/hugo/unionfind.h Mon Aug 30 12:01:47 2004 +0000 @@ -5,6 +5,9 @@ //!\ingroup auxdat //!\file //!\brief Union-Find data structures. +//! +//!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but +//!fails to run (Segmentation fault). #include diff -r ce9438c5a82d -r 4297098d9677 src/test/Makefile.am --- a/src/test/Makefile.am Wed Aug 25 18:55:57 2004 +0000 +++ b/src/test/Makefile.am Mon Aug 30 12:01:47 2004 +0000 @@ -2,14 +2,17 @@ noinst_HEADERS = test_tools.h -check_PROGRAMS = graph_test dijkstra_test time_measure_test error_test xy_test \ - test_tools_pass test_tools_fail +check_PROGRAMS = graph_test dijkstra_test bfs_test time_measure_test \ + error_test xy_test \ + unionfind_test test_tools_pass test_tools_fail TESTS = $(check_PROGRAMS) XFAIL_TESTS = test_tools_fail graph_test_SOURCES = graph_test.cc dijkstra_test_SOURCES = dijkstra_test.cc +bfs_test_SOURCES = bfs_test.cc +unionfind_test_SOURCES = unionfind_test.cc time_measure_test_SOURCES = time_measure_test.cc error_test_SOURCES = error_test.cc xy_test_SOURCES = xy_test.cc diff -r ce9438c5a82d -r 4297098d9677 src/test/bfs_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/test/bfs_test.cc Mon Aug 30 12:01:47 2004 +0000 @@ -0,0 +1,89 @@ +#include "test_tools.h" +#include +#include + +using namespace hugo; + +const int PET_SIZE =5; + + +void check_Bfs_SmartGraph_Compile() +{ + typedef int VType; + typedef SmartGraph Graph; + + typedef Graph::Edge Edge; + typedef Graph::Node Node; + typedef Graph::EdgeIt EdgeIt; + typedef Graph::NodeIt NodeIt; + typedef Graph::EdgeMap LengthMap; + + typedef Bfs BType; + + Graph G; + Node n; + Edge e; + VType l; + bool b; + BType::DistMap d(G); + BType::PredMap p(G); + BType::PredNodeMap pn(G); + LengthMap cap(G); + + BType bfs_test(G); + + bfs_test.run(n); + + l = bfs_test.dist(n); + e = bfs_test.pred(n); + n = bfs_test.predNode(n); + d = bfs_test.distMap(); + p = bfs_test.predMap(); + pn = bfs_test.predNodeMap(); + b = bfs_test.reached(n); + +} + +int main() +{ + + typedef SmartGraph Graph; + + typedef Graph::Edge Edge; + typedef Graph::Node Node; + typedef Graph::EdgeIt EdgeIt; + typedef Graph::NodeIt NodeIt; + typedef Graph::EdgeMap LengthMap; + + Graph G; + Node s, t; + PetStruct ps = addPetersen(G,PET_SIZE); + + s=ps.outer[2]; + t=ps.inner[0]; + + Bfs bfs_test(G); + bfs_test.run(s); + + check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t)); + + + for(EdgeIt e(G); e==INVALID; ++e) { + Node u=G.tail(e); + Node v=G.head(e); + check( !bfs_test.reached(u) || + (bfs_test.dist(v) > bfs_test.dist(u)+1), + "Wrong output."); + } + + ///\bug This works only for integer lengths + for(NodeIt v(G); v==INVALID; ++v) + if ( bfs_test.reached(v) ) { + Edge e=bfs_test.pred(v); + Node u=G.tail(e); + check(bfs_test.dist(v) - bfs_test.dist(u) == 1, + "Bad shortest path tree edge! Difference: " + << std::abs(bfs_test.dist(v) - bfs_test.dist(u) + - 1)); + } +} diff -r ce9438c5a82d -r 4297098d9677 src/test/dijkstra_test.cc --- a/src/test/dijkstra_test.cc Wed Aug 25 18:55:57 2004 +0000 +++ b/src/test/dijkstra_test.cc Mon Aug 30 12:01:47 2004 +0000 @@ -75,7 +75,7 @@ check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path."); - for(EdgeIt e(G); G.valid(e); G.next(e)) { + for(EdgeIt e(G); e==INVALID; ++e) { Node u=G.tail(e); Node v=G.head(e); check( !dijkstra_test.reached(u) || @@ -86,7 +86,7 @@ } ///\bug This works only for integer lengths - for(NodeIt v(G); G.valid(v); G.next(v)) + for(NodeIt v(G); v==INVALID; ++v) if ( dijkstra_test.reached(v) ) { Edge e=dijkstra_test.pred(v); Node u=G.tail(e); diff -r ce9438c5a82d -r 4297098d9677 src/test/graph_test.cc --- a/src/test/graph_test.cc Wed Aug 25 18:55:57 2004 +0000 +++ b/src/test/graph_test.cc Mon Aug 30 12:01:47 2004 +0000 @@ -6,12 +6,15 @@ #include"test_tools.h" -/* +/** +\file This test makes consistency checks of list graph structures. -G.addNode(), G.addEdge(), G.valid(), G.tail(), G.head() +G.addNode(), G.addEdge(), G.tail(), G.head() \todo Checks for empty graphs and isolated points. +\todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt} +conversion. */ using namespace hugo; @@ -29,82 +32,100 @@ { Node i; Node j(i); Node k(INVALID); i=j; - bool b=G.valid(i); b=b; + // bool b=G.valid(i); b=b; + bool b; b=b; + b=(i==INVALID); b=(i!=INVALID); b=(i==j); b=(i!=j); b=(iNodeIt conversion + NodeIt ni(G,n); } { Edge i; Edge j(i); Edge k(INVALID); i=j; - bool b=G.valid(i); b=b; + // bool b=G.valid(i); b=b; + bool b; b=b; + b=(i==INVALID); b=(i!=INVALID); b=(i==j); b=(i!=j); b=(iEdgeIt conversion + EdgeIt ei(G,e); } { Node n; InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); i=j; j=G.first(i,n); - j=G.next(i); - bool b=G.valid(i); b=b; + j=++i; + // bool b=G.valid(i); b=b; + bool b; b=b; + b=(i==INVALID); b=(i!=INVALID); Edge e(i); e=i; b=(i==j); b=(i!=j); b=(iInEdgeIt conversion + InEdgeIt ei(G,e); } { Node n; OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); i=j; j=G.first(i,n); - j=G.next(i); - bool b=G.valid(i); b=b; + j=++i; + // bool b=G.valid(i); b=b; + bool b; b=b; + b=(i==INVALID); b=(i!=INVALID); Edge e(i); e=i; b=(i==j); b=(i!=j); b=(iOutEdgeIt conversion + OutEdgeIt ei(G,e); } - - Node n,m; - n=m=INVALID; - Edge e; - e=INVALID; - n=G.tail(e); - n=G.head(e); - - //aNode, bNode ? - + { + Node n,m; + n=m=INVALID; + Edge e; + e=INVALID; + n=G.tail(e); + n=G.head(e); + } // id tests - { int i=G.id(n); i=i; } - { int i=G.id(e); i=i; } - - // G.clear(); - + { Node n; int i=G.id(n); i=i; } + { Edge e; int i=G.id(e); i=i; } //NodeMap tests { Node k; typename Graph::template NodeMap m(G); - typename Graph::template NodeMap const &cm = m; //Const map + //Const map + typename Graph::template NodeMap const &cm = m; //Inicialize with default value typename Graph::template NodeMap mdef(G,12); - typename Graph::template NodeMap mm(cm); //Copy - typename Graph::template NodeMap dm(cm); //Copy from another type + //Copy + typename Graph::template NodeMap mm(cm); + //Copy from another type + typename Graph::template NodeMap dm(cm); int v; v=m[k]; m[k]=v; m.set(k,v); v=cm[k]; @@ -160,7 +181,6 @@ dm=cm; //Copy from another type m=dm; //Copy to another type } - } template void checkCompile(Graph &G) @@ -177,8 +197,36 @@ Node n,m; n=G.addNode(); m=G.addNode(); + Edge e; + e=G.addEdge(n,m); - G.addEdge(n,m); + // G.clear(); +} + +template void checkCompileErase(Graph &G) +{ + typedef typename Graph::Node Node; + typedef typename Graph::Edge Edge; + Node n; + Edge e; + G.erase(n); + G.erase(e); +} + +template void checkCompileEraseEdge(Graph &G) +{ + typedef typename Graph::Edge Edge; + Edge e; + G.erase(e); +} + +template void checkCompileFindEdge(Graph &G) +{ + typedef typename Graph::NodeIt Node; + typedef typename Graph::NodeIt NodeIt; + + G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); + G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); } @@ -186,10 +234,10 @@ { typename Graph::NodeIt n(G); for(int i=0;i void checkEdgeList(Graph &G, int nn) @@ -198,10 +246,10 @@ EdgeIt e(G); for(int i=0;i void checkOutEdgeList(Graph &G, @@ -210,25 +258,27 @@ { typename Graph::OutEdgeIt e(G,n); for(int i=0;i void checkInEdgeList(Graph &G, - typename Graph::Node n, - int nn) + typename Graph::Node n, + int nn) { typename Graph::InEdgeIt e(G,n); for(int i=0;i void bidirPetersen(Graph &G) { typedef typename Graph::Edge Edge; @@ -238,7 +288,7 @@ std::vector ee; - for(EdgeIt e(G);G.valid(e);G.next(e)) ee.push_back(e); + for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e); for(typename std::vector::iterator p=ee.begin();p!=ee.end();p++) G.addEdge(G.head(*p),G.tail(*p)); @@ -254,25 +304,52 @@ checkNodeList(G,10); checkEdgeList(G,30); - for(NodeIt n(G);G.valid(n);G.next(n)) { + for(NodeIt n(G);n!=INVALID;++n) { checkInEdgeList(G,n,3); checkOutEdgeList(G,n,3); - G.next(n); + ++n; } } -template +//Compile GraphSkeleton +template void checkCompileStaticGraph(StaticGraphSkeleton &); template void checkCompile(GraphSkeleton &); +template +void checkCompileErase(EraseableGraphSkeleton &); +//Compile SmartGraph template void checkCompile(SmartGraph &); +//Compile SymSmartGraph template void checkCompile(SymSmartGraph &); + +//Compile ListGraph template void checkCompile(ListGraph &); +template void checkCompileErase(ListGraph &); +template void checkCompileFindEdge(ListGraph &); + +//Compile SymListGraph template void checkCompile(SymListGraph &); +template void checkCompileErase(SymListGraph &); +template void checkCompileFindEdge(SymListGraph &); + +//Compile FullGraph template void checkCompileStaticGraph(FullGraph &); +template void checkCompileFindEdge(FullGraph &); +//Compile EdgeSet template void checkCompile >(EdgeSet &); +template +void checkCompileEraseEdge >(EdgeSet &); +template +void checkCompileFindEdge >(EdgeSet &); + +//Compile EdgeSet template void checkCompile >(EdgeSet &); +template +void checkCompileEraseEdge >(EdgeSet &); +template void checkCompileFindEdge >(EdgeSet &); + int main() { @@ -299,8 +376,9 @@ checkPetersen(G); } - //\todo map tests. - //\todo copy constr tests. + ///\file + ///\todo map tests. + ///\todo copy constr tests. std::cout << __FILE__ ": All tests passed.\n"; diff -r ce9438c5a82d -r 4297098d9677 src/test/test_tools.h --- a/src/test/test_tools.h Wed Aug 25 18:55:57 2004 +0000 +++ b/src/test/test_tools.h Mon Aug 30 12:01:47 2004 +0000 @@ -20,6 +20,8 @@ ///\code check(0==1,"This is obviously false.");\endcode will ///print this (and then exits). ///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim +/// +///\todo It should be in \c error.h #define check(rc, msg) \ if(!(rc)) { \ std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \ diff -r ce9438c5a82d -r 4297098d9677 src/test/unionfind_test.cc --- a/src/test/unionfind_test.cc Wed Aug 25 18:55:57 2004 +0000 +++ b/src/test/unionfind_test.cc Mon Aug 30 12:01:47 2004 +0000 @@ -2,19 +2,11 @@ #include #include +#include "test_tools.h" using namespace hugo; using namespace std; -bool passed = true; - -void check(bool rc) { - passed = passed && rc; - if(!rc) { - cout << "Test failed!" << endl; - } -} - template class BaseMap : public StdMap {}; @@ -22,7 +14,7 @@ void print(UFE const &ufe) { UFE::ClassIt cit; - cout << "printing the classes of the structure:" << endl; + cout << "Print the classes of the structure:" << endl; int i = 1; for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) { cout << " " << i << " (" << cit << "):" << flush; @@ -41,165 +33,160 @@ UFE::MapType base; UFE U(base); - print(U); +// print(U); - cout << "Inserting 1..." << endl; + cout << "Insert 1..." << endl; U.insert(1); - print(U); +// print(U); - cout << "Inserting 2..." << endl; + cout << "Insert 2..." << endl; U.insert(2); - print(U); +// print(U); - cout << "Joining 1 and 2..." << endl; - check(U.join(1,2)); - print(U); + cout << "Join 1 and 2..." << endl; + check(U.join(1,2),"Test failed."); +// print(U); - cout << "Inserting 3, 4, 5, 6, 7..." << endl; + cout << "Insert 3, 4, 5, 6, 7..." << endl; U.insert(3); U.insert(4); U.insert(5); U.insert(6); U.insert(7); - print (U); +// print (U); - cout << "Joining 1 - 4, 2 - 4 and 3 - 5 ..." << endl; - check(U.join(1,4)); - check(!U.join(2,4)); - check(U.join(3,5)); - print(U); + cout << "Join 1 - 4, 2 - 4 and 3 - 5 ..." << endl; + check(U.join(1,4),"Test failed."); + check(!U.join(2,4),"Test failed."); + check(U.join(3,5),"Test failed."); +// print(U); - cout << "Inserting 8 to the component of 5 ..." << endl; + cout << "Insert 8 to the component of 5 ..." << endl; U.insert(8,5); - print(U); +// print(U); - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 3); - cout << "size of the class of 5: " << U.size(5) << endl; - check(U.size(5) == 3); - cout << "size of the class of 6: " << U.size(6) << endl; - check(U.size(6) == 1); - cout << "size of the class of 2: " << U.size(2) << endl; - check(U.size(2) == 3); + cout << "Size of the class of 4: " << U.size(4) << endl; + check(U.size(4) == 3,"Test failed."); + cout << "Size of the class of 5: " << U.size(5) << endl; + check(U.size(5) == 3,"Test failed."); + cout << "Size of the class of 6: " << U.size(6) << endl; + check(U.size(6) == 1,"Test failed."); + cout << "Size of the class of 2: " << U.size(2) << endl; + check(U.size(2) == 3,"Test failed."); - cout << "Inserting 9 ..." << endl; + cout << "Insert 9 ..." << endl; U.insert(9); - print(U); - cout << "Inserting 10 to the component of 9 ..." << endl; +// print(U); + cout << "Insert 10 to the component of 9 ..." << endl; U.insert(10,9); - print(U); +// print(U); - cout << "Joining 8 and 10..." << endl; - check(U.join(8,10)); - print(U); + cout << "Join 8 and 10..." << endl; + check(U.join(8,10),"Test failed."); +// print(U); cout << "Move 9 to the class of 4 ..." << endl; - check(U.move(9,4)); - print(U); + check(U.move(9,4),"Test failed."); +// print(U); cout << "Move 9 to the class of 2 ..." << endl; - check(!U.move(9,2)); - print(U); + check(!U.move(9,2),"Test failed."); +// print(U); - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 4); - cout << "size of the class of 9: " << U.size(9) << endl; - check(U.size(9) == 4); + cout << "Size of the class of 4: " << U.size(4) << endl; + check(U.size(4) == 4,"Test failed."); + cout << "Size of the class of 9: " << U.size(9) << endl; + check(U.size(9) == 4,"Test failed."); cout << "Move 5 to the class of 6 ..." << endl; - check(U.move(5,6)); - print(U); + check(U.move(5,6),"Test failed."); +// print(U); - cout << "size of the class of 5: " << U.size(5) << endl; - check(U.size(5) == 2); - cout << "size of the class of 8: " << U.size(8) << endl; - check(U.size(8) == 3); + cout << "Size of the class of 5: " << U.size(5) << endl; + check(U.size(5) == 2,"Test failed."); + cout << "Size of the class of 8: " << U.size(8) << endl; + check(U.size(8) == 3,"Test failed."); cout << "Move 7 to the class of 10 ..." << endl; - check(U.move(7,10)); - print(U); + check(U.move(7,10),"Test failed."); +// print(U); - cout << "size of the class of 7: " << U.size(7) << endl; - check(U.size(7) == 4); + cout << "Size of the class of 7: " << U.size(7) << endl; + check(U.size(7) == 4,"Test failed."); - cout <<"erase 9: " << endl; + cout <<"Erase 9... " << endl; U.erase(9); - print(U); +// print(U); - cout <<"erase 1: " << endl; + cout <<"Erase 1... " << endl; U.erase(1); - print(U); +// print(U); - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 2); - cout << "size of the class of 2: " << U.size(2) << endl; - check(U.size(2) == 2); + cout << "Size of the class of 4: " << U.size(4) << endl; + check(U.size(4) == 2,"Test failed."); + cout << "Size of the class of 2: " << U.size(2) << endl; + check(U.size(2) == 2,"Test failed."); - cout <<"erase 1: " << endl; + cout <<"Erase 1... " << endl; U.erase(1); - print(U); +// print(U); - cout <<"erase 6: " << endl; + cout <<"Erase 6... " << endl; U.erase(6); - print(U); +// print(U); - cout << "split the class of 8: " << endl; + cout << "Split the class of 8... " << endl; U.split(8); - print(U); +// print(U); - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 2); - cout << "size of the class of 3: " << U.size(3) << endl; - check(U.size(3) == 1); - cout << "size of the class of 2: " << U.size(2) << endl; - check(U.size(2) == 2); + cout << "Size of the class of 4: " << U.size(4) << endl; + check(U.size(4) == 2,"Test failed."); + cout << "Size of the class of 3: " << U.size(3) << endl; + check(U.size(3) == 1,"Test failed."); + cout << "Size of the class of 2: " << U.size(2) << endl; + check(U.size(2) == 2,"Test failed."); - cout << "Joining 3 - 4 and 2 - 4 ..." << endl; - check(U.join(3,4)); - check(!U.join(2,4)); - print(U); + cout << "Join 3 - 4 and 2 - 4 ..." << endl; + check(U.join(3,4),"Test failed."); + check(!U.join(2,4),"Test failed."); +// print(U); - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 3); - cout << "size of the class of 3: " << U.size(3) << endl; - check(U.size(3) == 3); - cout << "size of the class of 2: " << U.size(2) << endl; - check(U.size(2) == 3); + cout << "Size of the class of 4: " << U.size(4) << endl; + check(U.size(4) == 3,"Test failed."); + cout << "Size of the class of 3: " << U.size(3) << endl; + check(U.size(3) == 3,"Test failed."); + cout << "Size of the class of 2: " << U.size(2) << endl; + check(U.size(2) == 3,"Test failed."); - cout << "makeRep(4)" << endl; + cout << "makeRep(4)..." << endl; U.makeRep(4); - print(U); - cout << "makeRep(3)" << endl; +// print(U); + cout << "makeRep(3)..." << endl; U.makeRep(3); - print(U); - cout << "makeRep(2)" << endl; +// print(U); + cout << "makeRep(2)..." << endl; U.makeRep(2); - print(U); +// print(U); - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 3); - cout << "size of the class of 3: " << U.size(3) << endl; - check(U.size(3) == 3); - cout << "size of the class of 2: " << U.size(2) << endl; - check(U.size(2) == 3); + cout << "Size of the class of 4: " << U.size(4) << endl; + check(U.size(4) == 3,"Test failed."); + cout << "Size of the class of 3: " << U.size(3) << endl; + check(U.size(3) == 3,"Test failed."); + cout << "Size of the class of 2: " << U.size(2) << endl; + check(U.size(2) == 3,"Test failed."); cout << "eraseClass 4 ..." << endl; U.eraseClass(4); - print(U); +// print(U); cout << "eraseClass 7 ..." << endl; U.eraseClass(7); - print(U); +// print(U); - cout << "done" << endl; - - cout << (passed ? "All tests passed." : "Some of the tests failed!!!") - << endl; - - return passed ? 0 : 1; + cout << "done." << endl; } diff -r ce9438c5a82d -r 4297098d9677 src/test/xy_test.cc --- a/src/test/xy_test.cc Wed Aug 25 18:55:57 2004 +0000 +++ b/src/test/xy_test.cc Mon Aug 30 12:01:47 2004 +0000 @@ -7,7 +7,7 @@ int main() { - cout << "Testing classes xy and boundingbox." << endl; + cout << "Testing classes `xy' and `boundingbox'." << endl; typedef xy XY; @@ -33,10 +33,10 @@ typedef BoundingBox BB; BB doboz1; - check(doboz1.empty(), "empty? Should be."); + check(doboz1.empty(), "It should be empty."); doboz1 += a; - check(!doboz1.empty(), "empty? Should not be."); + check(!doboz1.empty(), "It should not be empty."); doboz1 += b; check(doboz1.bottomLeft().x==1 && @@ -46,19 +46,19 @@ "added points to box"); seged.x=2;seged.y=3; - check(doboz1.inside(seged),"Inside? It should be."); + check(doboz1.inside(seged),"It should be inside."); seged.x=1;seged.y=3; - check(doboz1.inside(seged),"Inside? It should be."); + check(doboz1.inside(seged),"It should be inside."); seged.x=0;seged.y=3; - check(!doboz1.inside(seged),"Inside? It should not be."); + check(!doboz1.inside(seged),"It should not be inside."); BB doboz2(seged); check(!doboz2.empty(), - "empty? Should not be. Constructed from 1 point."); + "It should not be empty. Constructed from 1 point."); doboz2 += doboz1; check(doboz2.inside(seged), - "Not inside? It should be. Incremented a box with an other."); + "It should be inside. Incremented a box with an other."); } diff -r ce9438c5a82d -r 4297098d9677 src/work/marci/bfs_dfs.h --- a/src/work/marci/bfs_dfs.h Wed Aug 25 18:55:57 2004 +0000 +++ b/src/work/marci/bfs_dfs.h Mon Aug 30 12:01:47 2004 +0000 @@ -60,8 +60,8 @@ if (bfs_queue.empty()) { bfs_queue.push(s); graph->first(actual_edge, s); - if (graph->valid(actual_edge)) { - Node w=graph->bNode(actual_edge); + if (actual_edge!=INVALID) { + Node w=graph->head(actual_edge); if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); @@ -78,10 +78,10 @@ /// its \c operator++() iterates on the edges in a bfs order. BfsIterator& operator++() { - if (graph->valid(actual_edge)) { - graph->next(actual_edge); - if (graph->valid(actual_edge)) { - Node w=graph->bNode(actual_edge); + if (actual_edge!=INVALID) { + ++actual_edge; + if (actual_edge!=INVALID) { + Node w=graph->head(actual_edge); if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); @@ -94,8 +94,8 @@ bfs_queue.pop(); if (!bfs_queue.empty()) { graph->first(actual_edge, bfs_queue.front()); - if (graph->valid(actual_edge)) { - Node w=graph->bNode(actual_edge); + if (actual_edge!=INVALID) { + Node w=graph->head(actual_edge); if (!reached[w]) { bfs_queue.push(w); reached.set(w, true); @@ -117,7 +117,7 @@ /// Returns if b-node has been reached just now. bool isBNodeNewlyReached() const { return b_node_newly_reached; } /// Returns if a-node is examined. - bool isANodeExamined() const { return !(graph->valid(actual_edge)); } + bool isANodeExamined() const { return actual_edge==INVALID; } /// Returns a-node of the actual edge, so does if the edge is invalid. Node aNode() const { return bfs_queue.front(); } /// \pre The actual edge have to be valid. @@ -237,8 +237,8 @@ operator++() { actual_edge=dfs_stack.top(); //actual_node=G.aNode(actual_edge); - if (graph->valid(actual_edge)/*.valid()*/) { - Node w=graph->bNode(actual_edge); + if (actual_edge!=INVALID/*.valid()*/) { + Node w=graph->head(actual_edge); actual_node=w; if (!reached[w]) { OutEdgeIt e; @@ -247,8 +247,8 @@ reached.set(w, true); b_node_newly_reached=true; } else { - actual_node=graph->aNode(actual_edge); - graph->next(dfs_stack.top()); + actual_node=graph->tail(actual_edge); + ++dfs_stack.top(); b_node_newly_reached=false; } } else { @@ -266,7 +266,7 @@ /// Returns if b-node has been reached just now. bool isBNodeNewlyReached() const { return b_node_newly_reached; } /// Returns if a-node is examined. - bool isANodeExamined() const { return !(graph->valid(actual_edge)); } + bool isANodeExamined() const { return actual_edge==INVALID; } /// Returns a-node of the actual edge, so does if the edge is invalid. Node aNode() const { return actual_node; /*FIXME*/} /// Returns b-node of the actual edge. diff -r ce9438c5a82d -r 4297098d9677 src/work/marci/iterator_bfs_demo.cc --- a/src/work/marci/iterator_bfs_demo.cc Wed Aug 25 18:55:57 2004 +0000 +++ b/src/work/marci/iterator_bfs_demo.cc Mon Aug 30 12:01:47 2004 +0000 @@ -4,7 +4,7 @@ #include #include -//#include +#include #include #include @@ -28,8 +28,8 @@ int main (int, char*[]) { - //typedef SmartGraph Graph; - typedef SageGraph Graph; + typedef SmartGraph Graph; + //typedef SageGraph Graph; typedef Graph::Node Node; typedef Graph::Edge Edge; @@ -91,13 +91,13 @@ EdgeNameMap< Graph, Graph::NodeMap > edge_name(G, node_name); cout << "bfs and dfs iterator demo on the directed graph" << endl; - for(Graph::NodeIt n(G); G.valid(n); G.next(n)) { + for(Graph::NodeIt n(G); n!=INVALID; ++n) { cout << node_name[n] << ": "; cout << "out edges: "; - for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e)) + for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e) cout << edge_name[e] << " "; cout << "in edges: "; - for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e)) + for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e) cout << edge_name[e] << " "; cout << endl; } @@ -107,11 +107,11 @@ bfs.pushAndSetReached(s); while (!bfs.finished()) { //cout << "edge: "; - if (G.valid(bfs)) { + if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) { cout << edge_name[bfs] << /*endl*/", " << - node_name[G.aNode(bfs)] << + node_name[G.tail(bfs)] << (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[G.bNode(bfs)] << + node_name[G.head(bfs)] << (bfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { @@ -141,11 +141,11 @@ while (!dfs.finished()) { ++dfs; //cout << "edge: "; - if (G.valid(dfs)) { + if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) { cout << edge_name[dfs] << /*endl*/", " << - node_name[G.aNode(dfs)] << + node_name[G.tail(dfs)] << (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[G.bNode(dfs)] << + node_name[G.head(dfs)] << (dfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { @@ -167,13 +167,13 @@ EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { + for(GW::NodeIt n(gw); n!=INVALID; ++n) { cout << node_name[GW::Node(n)] << ": "; cout << "out edges: "; - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) + for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) cout << edge_name[e] << " "; cout << "in edges: "; - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) + for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e) cout << edge_name[e] << " "; cout << endl; } @@ -183,11 +183,11 @@ bfs.pushAndSetReached(t); while (!bfs.finished()) { //cout << "edge: "; - if (gw.valid(GW::OutEdgeIt(bfs))) { + if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) { cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << - node_name[gw.aNode(bfs)] << + node_name[gw.tail(bfs)] << (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[gw.bNode(bfs)] << + node_name[gw.head(bfs)] << (bfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { @@ -217,11 +217,11 @@ while (!dfs.finished()) { ++dfs; //cout << "edge: "; - if (gw.valid(GW::OutEdgeIt(dfs))) { + if (GW::OutEdgeIt(dfs)!=INVALID) { cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << - node_name[gw.aNode(dfs)] << + node_name[gw.tail(dfs)] << (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[gw.bNode(dfs)] << + node_name[gw.head(dfs)] << (dfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { @@ -235,20 +235,104 @@ } } +// { +// typedef UndirGraphWrapper GW; +// GW gw(G); + +// EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); + +// cout << "bfs and dfs iterator demo on the undirected graph" << endl; +// for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { +// cout << node_name[GW::Node(n)] << ": "; +// cout << "out edges: "; +// for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) +// cout << edge_name[e] << " "; +// cout << "in edges: "; +// for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) +// cout << edge_name[e] << " "; +// cout << endl; +// } +// // for(GW::EdgeIt e=gw.first(); gw.valid(e); gw.next(e)) { +// // cout << edge_name.get(e) << " "; +// // } +// // cout << endl; + +// cout << "bfs from t ..." << endl; +// BfsIterator< GW, GW::NodeMap > bfs(gw); +// bfs.pushAndSetReached(t); +// while (!bfs.finished()) { +// //cout << "edge: "; +// if (gw.valid(GW::OutEdgeIt(bfs))) { +// cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << +// node_name[gw.aNode(bfs)] << +// (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << +// node_name[gw.bNode(bfs)] << +// (bfs.isBNodeNewlyReached() ? ": is newly reached." : +// ": is not newly reached."); +// } else { +// cout << "invalid" << /*endl*/", " << +// node_name[bfs.aNode()] << +// (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + +// "invalid."; +// } +// cout << endl; +// ++bfs; +// } + +// cout << " /--> -------------> "<< endl; +// cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; +// cout << " / | | / /-> \\ "<< endl; +// cout << " / | | / | ^ \\ "<< endl; +// cout << "s | | / | | \\-> t "<< endl; +// cout << " \\ | | / | | /-> "<< endl; +// cout << " \\ | --/ / | | / "<< endl; +// cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; +// cout << " \\--> -------------> "<< endl; + +// cout << "dfs from t ..." << endl; +// DfsIterator< GW, GW::NodeMap > dfs(gw); +// dfs.pushAndSetReached(t); +// while (!dfs.finished()) { +// ++dfs; +// //cout << "edge: "; +// if (gw.valid(GW::OutEdgeIt(dfs))) { +// cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << +// node_name[gw.aNode(dfs)] << +// (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << +// node_name[gw.bNode(dfs)] << +// (dfs.isBNodeNewlyReached() ? ": is newly reached." : +// ": is not newly reached."); +// } else { +// cout << "invalid" << /*endl*/", " << +// node_name[dfs.aNode()] << +// (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << + +// "invalid."; +// } +// cout << endl; +// } +// } + + + { - typedef UndirGraphWrapper GW; + typedef BidirGraphWrapper GW; GW gw(G); EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); - cout << "bfs and dfs iterator demo on the undirected graph" << endl; - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { + cout << "bfs and dfs iterator demo on the bidirected graph" << endl; +// for(GW::EdgeIt e(gw); e!=INVALID; ++e) { +// cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " "; +// } + for(GW::NodeIt n(gw); n!=INVALID; ++n) { cout << node_name[GW::Node(n)] << ": "; cout << "out edges: "; - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) + for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) cout << edge_name[e] << " "; cout << "in edges: "; - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) + for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e) cout << edge_name[e] << " "; cout << endl; } @@ -262,11 +346,11 @@ bfs.pushAndSetReached(t); while (!bfs.finished()) { //cout << "edge: "; - if (gw.valid(GW::OutEdgeIt(bfs))) { + if (GW::OutEdgeIt(bfs)!=INVALID) { cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << - node_name[gw.aNode(bfs)] << + node_name[gw.tail(bfs)] << (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[gw.bNode(bfs)] << + node_name[gw.head(bfs)] << (bfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { @@ -296,11 +380,11 @@ while (!dfs.finished()) { ++dfs; //cout << "edge: "; - if (gw.valid(GW::OutEdgeIt(dfs))) { + if (GW::OutEdgeIt(dfs)!=INVALID) { cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << - node_name[gw.aNode(dfs)] << + node_name[gw.tail(dfs)] << (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[gw.bNode(dfs)] << + node_name[gw.head(dfs)] << (dfs.isBNodeNewlyReached() ? ": is newly reached." : ": is not newly reached."); } else { @@ -314,88 +398,5 @@ } } - - - { - typedef BidirGraphWrapper GW; - GW gw(G); - - EdgeNameMap< GW, Graph::NodeMap > edge_name(gw, node_name); - - cout << "bfs and dfs iterator demo on the undirected graph" << endl; - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { - cout << node_name[GW::Node(n)] << ": "; - cout << "out edges: "; - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) - cout << edge_name[e] << " "; - cout << "in edges: "; - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) - cout << edge_name[e] << " "; - cout << endl; - } -// for(GW::EdgeIt e=gw.first(); gw.valid(e); gw.next(e)) { -// cout << edge_name.get(e) << " "; -// } -// cout << endl; - - cout << "bfs from t ..." << endl; - BfsIterator< GW, GW::NodeMap > bfs(gw); - bfs.pushAndSetReached(t); - while (!bfs.finished()) { - //cout << "edge: "; - if (gw.valid(GW::OutEdgeIt(bfs))) { - cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << - node_name[gw.aNode(bfs)] << - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[gw.bNode(bfs)] << - (bfs.isBNodeNewlyReached() ? ": is newly reached." : - ": is not newly reached."); - } else { - cout << "invalid" << /*endl*/", " << - node_name[bfs.aNode()] << - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - - "invalid."; - } - cout << endl; - ++bfs; - } - - cout << " /--> -------------> "<< endl; - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; - cout << " / | | / /-> \\ "<< endl; - cout << " / | | / | ^ \\ "<< endl; - cout << "s | | / | | \\-> t "<< endl; - cout << " \\ | | / | | /-> "<< endl; - cout << " \\ | --/ / | | / "<< endl; - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; - cout << " \\--> -------------> "<< endl; - - cout << "dfs from t ..." << endl; - DfsIterator< GW, GW::NodeMap > dfs(gw); - dfs.pushAndSetReached(t); - while (!dfs.finished()) { - ++dfs; - //cout << "edge: "; - if (gw.valid(GW::OutEdgeIt(dfs))) { - cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << - node_name[gw.aNode(dfs)] << - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - node_name[gw.bNode(dfs)] << - (dfs.isBNodeNewlyReached() ? ": is newly reached." : - ": is not newly reached."); - } else { - cout << "invalid" << /*endl*/", " << - node_name[dfs.aNode()] << - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << - - "invalid."; - } - cout << endl; - } - } - - - return 0; } diff -r ce9438c5a82d -r 4297098d9677 src/work/sage_graph.h --- a/src/work/sage_graph.h Wed Aug 25 18:55:57 2004 +0000 +++ b/src/work/sage_graph.h Mon Aug 30 12:01:47 2004 +0000 @@ -9,12 +9,12 @@ namespace hugo { - template - int count(It it) { - int i=0; - for( ; it.valid(); ++it) { ++i; } - return i; - } +// template +// int count(It it) { +// int i=0; +// for( ; it.valid(); ++it) { ++i; } +// return i; +// } class SageGraph { struct node_item; @@ -385,11 +385,13 @@ //protected: public: //for everybody but marci NodeIt(const SageGraph& G) : Node(G._first_node) { } + NodeIt(const SageGraph& G, const Node& n) : Node(n) { } public: NodeIt() : Node() { } NodeIt(const Invalid& i) : Node(i) { } protected: NodeIt(node_item* v) : Node(v) { } + public: NodeIt& operator++() { node=node->_next_node; return *this; } //FIXME:: // NodeIt& operator=(const Node& e) @@ -425,18 +427,18 @@ class EdgeIt : public Edge { friend class SageGraph; - //protected: - public: //for alpar + public: + EdgeIt() : Edge() { } + EdgeIt(const Invalid& i) : Edge(i) { } EdgeIt(const SageGraph& G) { node_item* v=G._first_node; if (v) edge=v->_first_out_edge; else edge=0; while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } } + EdgeIt(const SageGraph& G, const Edge& e) : Edge(e) { } +// protected: +// EdgeIt(edge_item* _e) : Edge(_e) { } public: - EdgeIt() : Edge() { } - EdgeIt(const Invalid& i) : Edge(i) { } - protected: - EdgeIt(edge_item* _e) : Edge(_e) { } EdgeIt& operator++() { node_item* v=edge->_tail; edge=edge->_next_out; @@ -447,15 +449,11 @@ class OutEdgeIt : public Edge { friend class SageGraph; - //node_item* v; - //protected: - protected: //for alpar - OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; } public: - OutEdgeIt() : Edge()/*, v(0)*/ { } + OutEdgeIt() : Edge() { } OutEdgeIt(const Invalid& i) : Edge(i) { } - OutEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; } - protected: + OutEdgeIt(const SageGraph&, Node _v) : Edge(_v.node->_first_out_edge) { } + OutEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { } OutEdgeIt& operator++() { edge=edge->_next_out; return *this; } protected: Node aNode() const { return Node(edge->_tail); } @@ -464,15 +462,11 @@ class InEdgeIt : public Edge { friend class SageGraph; - //node_item* v; - //protected: - protected: //for alpar - InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; } public: - InEdgeIt() : Edge()/*, v(0)*/ { } - InEdgeIt(const Invalid& i) : Edge(i) { } - InEdgeIt(const SageGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; } - protected: + InEdgeIt() : Edge() { } + InEdgeIt(Invalid i) : Edge(i) { } + InEdgeIt(const SageGraph&, Node _v) : Edge(_v.node->_first_in_edge) { } + InEdgeIt(const SageGraph&, const Edge& e) : Edge(e) { } InEdgeIt& operator++() { edge=edge->_next_in; return *this; } protected: Node aNode() const { return Node(edge->_head); }