1.1 --- a/src/include/dijkstra.h Thu Apr 15 20:50:03 2004 +0000
1.2 +++ b/src/include/dijkstra.h Fri Apr 16 08:26:00 2004 +0000
1.3 @@ -186,7 +186,9 @@
1.4 heap.pop();
1.5 distance.set(v, oldvalue);
1.6
1.7 - for(OutEdgeIt e = G.template first<OutEdgeIt>(v);
1.8 + { //FIXME this bracket is for e to be local
1.9 + OutEdgeIt e;
1.10 + for(G.first(e, v);
1.11 G.valid(e); G.next(e)) {
1.12 Node w=G.head(e);
1.13
1.14 @@ -207,6 +209,7 @@
1.15 break;
1.16 }
1.17 }
1.18 + } //FIXME tis bracket
1.19 }
1.20 }
1.21
2.1 --- a/src/work/list_graph.h Thu Apr 15 20:50:03 2004 +0000
2.2 +++ b/src/work/list_graph.h Fri Apr 16 08:26:00 2004 +0000
2.3 @@ -294,19 +294,19 @@
2.4 //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
2.5 //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
2.6
2.7 - template< typename It >
2.8 - It first() const {
2.9 - It e;
2.10 - first(e);
2.11 - return e;
2.12 - }
2.13 +// template< typename It >
2.14 +// It first() const {
2.15 +// It e;
2.16 +// first(e);
2.17 +// return e;
2.18 +// }
2.19
2.20 - template< typename It >
2.21 - It first(Node v) const {
2.22 - It e;
2.23 - first(e, v);
2.24 - return e;
2.25 - }
2.26 +// template< typename It >
2.27 +// It first(Node v) const {
2.28 +// It e;
2.29 +// first(e, v);
2.30 +// return e;
2.31 +// }
2.32
2.33 bool valid(Node n) const { return n.valid(); }
2.34 bool valid(Edge e) const { return e.valid(); }
2.35 @@ -352,7 +352,9 @@
2.36 void erase(Edge e) { _delete_edge(e.edge); }
2.37
2.38 void clear() {
2.39 - while (first<NodeIt>().valid()) erase(first<NodeIt>());
2.40 + NodeIt e;
2.41 + while (this->valid(first(e))) erase(e);
2.42 + //while (first<NodeIt>().valid()) erase(first<NodeIt>());
2.43 }
2.44
2.45 void setTail(Edge e, Node tail) {
3.1 --- a/src/work/marci/graph_wrapper.h Thu Apr 15 20:50:03 2004 +0000
3.2 +++ b/src/work/marci/graph_wrapper.h Fri Apr 16 08:26:00 2004 +0000
3.3 @@ -6,6 +6,63 @@
3.4
3.5 namespace hugo {
3.6
3.7 + /// Graph wrappers
3.8 +
3.9 + /// The main parts of HUGOlib are the different graph structures,
3.10 + /// generic graph algorithms, graph concepts which couple these, and
3.11 + /// graph wrappers. While the previous ones are more or less clear, the
3.12 + /// latter notion needs further explanation.
3.13 + /// Graph wrappers are graph classes which serve for considering graph
3.14 + /// structures in different ways. A short example makes the notion much more
3.15 + /// clear.
3.16 + /// Suppose that we have an instance \code g \endcode of a directed graph
3.17 + /// type say \code ListGraph \endcode and an algorithm
3.18 + /// \code template<typename Graph> int algorithm(const Graph&); \endcode
3.19 + /// is needed to run on the reversed oriented graph.
3.20 + /// It can be expensive (in time or in memory usage) to copy
3.21 + /// \code g \endcode with the reversed orientation.
3.22 + /// Thus, a wrapper class
3.23 + /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
3.24 + /// The code looks as follows
3.25 + /// \code
3.26 + /// ListGraph g;
3.27 + /// RevGraphWrapper<ListGraph> rgw(g);
3.28 + /// int result=algorithm(rgw);
3.29 + /// \endcode
3.30 + /// After running the algorithm, the original graph \code g \endcode
3.31 + /// is untouched. Thus the above used graph wrapper is to consider the
3.32 + /// original graph with reversed orientation.
3.33 + /// This techniques gives rise to an elegant code, and
3.34 + /// based on stable graph wrappers, complex algorithms can be
3.35 + /// implemented easily.
3.36 + /// In flow, circulation and bipartite matching problems, the residual
3.37 + /// graph is of particualar significance. Combining a wrapper impleneting
3.38 + /// this, shortest path algorithms and mimimum mean cycle algorithms,
3.39 + /// a range of weighted and cardinality optimization algorithms can be
3.40 + /// obtained. For lack of space, for other examples,
3.41 + /// the interested user is referred to the detailed domumentation of graph
3.42 + /// wrappers.
3.43 + /// The behavior of graph wrappers are very different. Some of them keep
3.44 + /// capabilities of the original graph while in other cases this would be
3.45 + /// meaningless. This means that the concepts that they are model of depend
3.46 + /// on the graph wrapper, and the wrapped graph(s).
3.47 + /// If an edge of \code rgw \endcode is deleted, this is carried out by
3.48 + /// deleting the corresponding edge of \code g \endcode. But for a residual
3.49 + /// graph, this operation has no sense.
3.50 + /// Let we stand one more example here to simplify your work.
3.51 + /// wrapper class
3.52 + /// \code template<typename Graph> class RevGraphWrapper; \endcode
3.53 + /// has constructor
3.54 + /// \code RevGraphWrapper(Graph& _g); \endcode.
3.55 + /// This means that in a situation,
3.56 + /// when a \code const ListGraph& \endcode reference to a graph is given,
3.57 + /// then it have to be instatiated with Graph=const ListGraph.
3.58 + /// \code
3.59 + /// int algorithm1(const ListGraph& g) {
3.60 + /// RevGraphWrapper<const ListGraph> rgw(g);
3.61 + /// return algorithm2(rgw);
3.62 + /// }
3.63 + /// \endcode
3.64 template<typename Graph>
3.65 class GraphWrapper {
3.66 protected:
3.67 @@ -109,11 +166,11 @@
3.68 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
3.69 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
3.70 // template<typename I> I& next(I &i) const { graph->next(i); return i; }
3.71 - template< typename It > It first() const {
3.72 - It e; this->first(e); return e; }
3.73 +// template< typename It > It first() const {
3.74 +// It e; this->first(e); return e; }
3.75
3.76 - template< typename It > It first(const Node& v) const {
3.77 - It e; this->first(e, v); return e; }
3.78 +// template< typename It > It first(const Node& v) const {
3.79 +// It e; this->first(e, v); return e; }
3.80
3.81 Node head(const Edge& e) const {
3.82 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
3.83 @@ -274,7 +331,12 @@
3.84 { return GraphWrapper<Graph>::head(e); }
3.85 };
3.86
3.87 - //Subgraph on the same node-set and partial edge-set
3.88 + /// Wrapper for hiding nodes and edges from a graph.
3.89 +
3.90 + /// This wrapper shows a graph with filtered node-set and
3.91 + /// edge-set. The quick brown fox iterators jumps over
3.92 + /// the lazy dog nodes or edges if the values for them are false
3.93 + /// in the bool maps.
3.94 template<typename Graph, typename NodeFilterMap,
3.95 typename EdgeFilterMap>
3.96 class SubGraphWrapper : public GraphWrapper<Graph> {
3.97 @@ -483,11 +545,11 @@
3.98 bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
3.99 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
3.100
3.101 - template< typename It > It first() const {
3.102 - It e; this->first(e); return e; }
3.103 +// template< typename It > It first() const {
3.104 +// It e; this->first(e); return e; }
3.105
3.106 - template< typename It > It first(const Node& v) const {
3.107 - It e; this->first(e, v); return e; }
3.108 +// template< typename It > It first(const Node& v) const {
3.109 +// It e; this->first(e, v); return e; }
3.110 };
3.111
3.112 // //Subgraph on the same node-set and partial edge-set
3.113 @@ -742,9 +804,9 @@
3.114 i=EdgeIt(*this); return i;
3.115 }
3.116
3.117 - template<typename I> I& first(I& i) const { graph->first(i); return i; }
3.118 - template<typename I, typename P> I& first(I& i, const P& p) const {
3.119 - graph->first(i, p); return i; }
3.120 +// template<typename I> I& first(I& i) const { graph->first(i); return i; }
3.121 +// template<typename I, typename P> I& first(I& i, const P& p) const {
3.122 +// graph->first(i, p); return i; }
3.123
3.124 NodeIt& next(NodeIt& n) const {
3.125 GraphWrapper<Graph>::next(n);
3.126 @@ -768,11 +830,11 @@
3.127 }
3.128
3.129 // template<typename I> I& next(I &i) const { graph->next(i); return i; }
3.130 - template< typename It > It first() const {
3.131 - It e; this->first(e); return e; }
3.132 +// template< typename It > It first() const {
3.133 +// It e; this->first(e); return e; }
3.134
3.135 - template< typename It > It first(const Node& v) const {
3.136 - It e; this->first(e, v); return e; }
3.137 +// template< typename It > It first(const Node& v) const {
3.138 +// It e; this->first(e, v); return e; }
3.139
3.140 // Node head(const Edge& e) const { return gw.head(e); }
3.141 // Node tail(const Edge& e) const { return gw.tail(e); }
3.142 @@ -1251,19 +1313,19 @@
3.143 // }
3.144
3.145
3.146 - template< typename It >
3.147 - It first() const {
3.148 - It e;
3.149 - first(e);
3.150 - return e;
3.151 - }
3.152 +// template< typename It >
3.153 +// It first() const {
3.154 +// It e;
3.155 +// first(e);
3.156 +// return e;
3.157 +// }
3.158
3.159 - template< typename It >
3.160 - It first(Node v) const {
3.161 - It e;
3.162 - first(e, v);
3.163 - return e;
3.164 - }
3.165 +// template< typename It >
3.166 +// It first(Node v) const {
3.167 +// It e;
3.168 +// first(e, v);
3.169 +// return e;
3.170 +// }
3.171
3.172 Node tail(Edge e) const {
3.173 return ((e.forward) ? graph->tail(e) : graph->head(e)); }
3.174 @@ -1800,11 +1862,11 @@
3.175 // return i;
3.176 // }
3.177
3.178 - template< typename It > It first() const {
3.179 - It e; this->first(e); return e; }
3.180 +// template< typename It > It first() const {
3.181 +// It e; this->first(e); return e; }
3.182
3.183 - template< typename It > It first(const Node& v) const {
3.184 - It e; this->first(e, v); return e; }
3.185 +// template< typename It > It first(const Node& v) const {
3.186 +// It e; this->first(e, v); return e; }
3.187
3.188 void erase(const OutEdgeIt& e) const {
3.189 OutEdgeIt f=e;