1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/bin_heap.h Thu May 06 13:21:24 2004 +0000
1.3 @@ -0,0 +1,246 @@
1.4 +// -*- C++ -*- //
1.5 +
1.6 +/* FIXME: Copyright ...
1.7 + *
1.8 + * This implementation is heavily based on STL's heap functions and
1.9 + * the similar class by Alpar Juttner in IKTA...
1.10 + */
1.11 +
1.12 +/******
1.13 + *
1.14 + * BinHeap<ItemType, PrioType, ItemIntMap, [PrioCompare]>
1.15 + *
1.16 + * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot
1.17 + * valosit meg.
1.18 + * A kupacban legfolul mindig az a par talalhato, amiben a prioritas a
1.19 + * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
1.20 + * lett keszitve...)
1.21 + *
1.22 + * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni,
1.23 + * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata
1.24 + * miatt, megprobaltunk valami semleges elnevezeseket kitalalni.
1.25 + *
1.26 + * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
1.27 + * az itemekhez egy int-et tud tarolni (ezzel tudom megkeresni az illeto
1.28 + * elemet a kupacban a csokkentes es hasonlo muveletekhez).
1.29 + * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
1.30 + * is elnie kell. (???)
1.31 + *
1.32 + * Ketfele modon hasznalhato:
1.33 + * Lusta mod:
1.34 + * set(Item, Prio) metodussal pakolunk a kupacba,
1.35 + * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
1.36 + * csokkentettunk-e rajta, vagy noveltunk.
1.37 + * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
1.38 + * minden szobajovo kulcs ertekre, -1 -es ertekkel!
1.39 + * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
1.40 + * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
1.41 + * mar kikerult a kupacbol POST_HEAP=-2).
1.42 + * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
1.43 + * meg meg tudja mondani a "legkisebb" prioritasu elemet. De csak nagyjabol,
1.44 + * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
1.45 + *
1.46 + * Kozvetlen mod:
1.47 + * push(Item, Prio) metodussal belerakunk a kupacba (ha az illeto kulcs mar
1.48 + * benn volt, akkor gaz).
1.49 + * increase/decrease(Item i, Prio new_prio) metodusokkal lehet
1.50 + * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt
1.51 + * megbenne a kupacban az illeto elem, vagy nem abba az iranyba valtoztattad
1.52 + * az erteket, amerre mondtad -- gaz).
1.53 + *
1.54 + * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
1.55 + * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
1.56 + * hasznal. :-))
1.57 + *
1.58 + *
1.59 + * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
1.60 + *
1.61 + */
1.62 +
1.63 +
1.64 +#ifndef BIN_HEAP_HH
1.65 +#define BIN_HEAP_HH
1.66 +
1.67 +///\ingroup auxdat
1.68 +///\file
1.69 +///\brief Binary Heap implementation.
1.70 +
1.71 +#include <vector>
1.72 +#include <utility>
1.73 +#include <functional>
1.74 +
1.75 +namespace hugo {
1.76 +
1.77 + /// \addtogroup auxdat
1.78 + /// @{
1.79 +
1.80 + /// A Binary Heap implementation.
1.81 + template <typename Item, typename Prio, typename ItemIntMap,
1.82 + typename Compare = std::less<Prio> >
1.83 + class BinHeap {
1.84 +
1.85 + public:
1.86 + typedef Item ItemType;
1.87 + // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
1.88 + typedef Prio PrioType;
1.89 + typedef std::pair<ItemType,PrioType> PairType;
1.90 + typedef ItemIntMap ItemIntMapType;
1.91 + typedef Compare PrioCompare;
1.92 +
1.93 + /**
1.94 + * Each Item element have a state associated to it. It may be "in heap",
1.95 + * "pre heap" or "post heap". The later two are indifferent from the
1.96 + * heap's point of view, but may be useful to the user.
1.97 + *
1.98 + * The ItemIntMap _should_ be initialized in such way, that it maps
1.99 + * PRE_HEAP (-1) to any element to be put in the heap...
1.100 + */
1.101 + ///\todo it is used nowhere
1.102 + ///
1.103 + enum state_enum {
1.104 + IN_HEAP = 0,
1.105 + PRE_HEAP = -1,
1.106 + POST_HEAP = -2
1.107 + };
1.108 +
1.109 + private:
1.110 + std::vector<PairType> data;
1.111 + Compare comp;
1.112 + // FIXME: jo ez igy???
1.113 + ItemIntMap &iim;
1.114 +
1.115 + public:
1.116 + BinHeap(ItemIntMap &_iim) : iim(_iim) {}
1.117 + BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
1.118 +
1.119 +
1.120 + int size() const { return data.size(); }
1.121 + bool empty() const { return data.empty(); }
1.122 +
1.123 + private:
1.124 + static int parent(int i) { return (i-1)/2; }
1.125 + static int second_child(int i) { return 2*i+2; }
1.126 + bool less(const PairType &p1, const PairType &p2) const {
1.127 + return comp(p1.second, p2.second);
1.128 + }
1.129 +
1.130 + int bubble_up(int hole, PairType p);
1.131 + int bubble_down(int hole, PairType p, int length);
1.132 +
1.133 + void move(const PairType &p, int i) {
1.134 + data[i] = p;
1.135 + iim.set(p.first, i);
1.136 + }
1.137 +
1.138 + void rmidx(int h) {
1.139 + int n = data.size()-1;
1.140 + if( h>=0 && h<=n ) {
1.141 + iim.set(data[h].first, POST_HEAP);
1.142 + if ( h<n ) {
1.143 + bubble_down(h, data[n], n);
1.144 + }
1.145 + data.pop_back();
1.146 + }
1.147 + }
1.148 +
1.149 + public:
1.150 + void push(const PairType &p) {
1.151 + int n = data.size();
1.152 + data.resize(n+1);
1.153 + bubble_up(n, p);
1.154 + }
1.155 + void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
1.156 +
1.157 + Item top() const {
1.158 + return data[0].first;
1.159 + }
1.160 + /// Returns the prio of the top element of the heap.
1.161 + Prio prio() const {
1.162 + return data[0].second;
1.163 + }
1.164 +
1.165 + void pop() {
1.166 + rmidx(0);
1.167 + }
1.168 +
1.169 + void erase(const Item &i) {
1.170 + rmidx(iim[i]);
1.171 + }
1.172 +
1.173 + Prio operator[](const Item &i) const {
1.174 + int idx = iim[i];
1.175 + return data[idx].second;
1.176 + }
1.177 +
1.178 + void set(const Item &i, const Prio &p) {
1.179 + int idx = iim[i];
1.180 + if( idx < 0 ) {
1.181 + push(i,p);
1.182 + }
1.183 + else if( comp(p, data[idx].second) ) {
1.184 + bubble_up(idx, PairType(i,p));
1.185 + }
1.186 + else {
1.187 + bubble_down(idx, PairType(i,p), data.size());
1.188 + }
1.189 + }
1.190 +
1.191 + void decrease(const Item &i, const Prio &p) {
1.192 + int idx = iim[i];
1.193 + bubble_up(idx, PairType(i,p));
1.194 + }
1.195 + void increase(const Item &i, const Prio &p) {
1.196 + int idx = iim[i];
1.197 + bubble_down(idx, PairType(i,p), data.size());
1.198 + }
1.199 +
1.200 + state_enum state(const Item &i) const {
1.201 + int s = iim[i];
1.202 + if( s>=0 )
1.203 + s=0;
1.204 + return state_enum(s);
1.205 + }
1.206 +
1.207 + }; // class BinHeap
1.208 +
1.209 +
1.210 + template <typename K, typename V, typename M, typename C>
1.211 + int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
1.212 + int par = parent(hole);
1.213 + while( hole>0 && less(p,data[par]) ) {
1.214 + move(data[par],hole);
1.215 + hole = par;
1.216 + par = parent(hole);
1.217 + }
1.218 + move(p, hole);
1.219 + return hole;
1.220 + }
1.221 +
1.222 + template <typename K, typename V, typename M, typename C>
1.223 + int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
1.224 + int child = second_child(hole);
1.225 + while(child < length) {
1.226 + if( less(data[child-1], data[child]) ) {
1.227 + --child;
1.228 + }
1.229 + if( !less(data[child], p) )
1.230 + goto ok;
1.231 + move(data[child], hole);
1.232 + hole = child;
1.233 + child = second_child(hole);
1.234 + }
1.235 + child--;
1.236 + if( child<length && less(data[child], p) ) {
1.237 + move(data[child], hole);
1.238 + hole=child;
1.239 + }
1.240 + ok:
1.241 + move(p, hole);
1.242 + return hole;
1.243 + }
1.244 +
1.245 + ///@}
1.246 +
1.247 +} // namespace hugo
1.248 +
1.249 +#endif // BIN_HEAP_HH
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/hugo/dijkstra.h Thu May 06 13:21:24 2004 +0000
2.3 @@ -0,0 +1,208 @@
2.4 +// -*- C++ -*-
2.5 +#ifndef HUGO_DIJKSTRA_H
2.6 +#define HUGO_DIJKSTRA_H
2.7 +
2.8 +///\ingroup galgs
2.9 +///\file
2.10 +///\brief Dijkstra algorithm.
2.11 +
2.12 +#include <bin_heap.h>
2.13 +#include <invalid.h>
2.14 +
2.15 +namespace hugo {
2.16 +
2.17 +/// \addtogroup galgs
2.18 +/// @{
2.19 +
2.20 + ///%Dijkstra algorithm class.
2.21 +
2.22 + ///This class provides an efficient implementation of %Dijkstra algorithm.
2.23 + ///The edge lengths are passed to the algorithm using a
2.24 + ///\ref ReadMapSkeleton "readable map",
2.25 + ///so it is easy to change it to any kind of length.
2.26 + ///
2.27 + ///The type of the length is determined by the \c ValueType of the length map.
2.28 + ///
2.29 + ///It is also possible to change the underlying priority heap.
2.30 + ///
2.31 + ///\param Graph The graph type the algorithm runs on.
2.32 + ///\param LengthMap This read-only
2.33 + ///EdgeMap
2.34 + ///determines the
2.35 + ///lengths of the edges. It is read once for each edge, so the map
2.36 + ///may involve in relatively time consuming process to compute the edge
2.37 + ///length if it is necessary. The default map type is
2.38 + ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
2.39 + ///\param Heap The heap type used by the %Dijkstra
2.40 + ///algorithm. The default
2.41 + ///is using \ref BinHeap "binary heap".
2.42 + ///
2.43 + ///\author Jacint Szabo
2.44 +#ifdef DOXYGEN
2.45 + template <typename Graph,
2.46 + typename LengthMap,
2.47 + typename Heap>
2.48 +#else
2.49 + template <typename Graph,
2.50 + typename LengthMap=typename Graph::template EdgeMap<int>,
2.51 + template <class,class,class,class> class Heap = BinHeap >
2.52 +#endif
2.53 + class Dijkstra{
2.54 + public:
2.55 + typedef typename Graph::Node Node;
2.56 + typedef typename Graph::NodeIt NodeIt;
2.57 + typedef typename Graph::Edge Edge;
2.58 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.59 +
2.60 + typedef typename LengthMap::ValueType ValueType;
2.61 + typedef typename Graph::template NodeMap<Edge> PredMap;
2.62 + typedef typename Graph::template NodeMap<Node> PredNodeMap;
2.63 + typedef typename Graph::template NodeMap<ValueType> DistMap;
2.64 +
2.65 + private:
2.66 + const Graph& G;
2.67 + const LengthMap& length;
2.68 + PredMap predecessor;
2.69 + PredNodeMap pred_node;
2.70 + DistMap distance;
2.71 +
2.72 + public :
2.73 +
2.74 + Dijkstra(const Graph& _G, const LengthMap& _length) :
2.75 + G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
2.76 +
2.77 + void run(Node s);
2.78 +
2.79 + ///The distance of a node from the root.
2.80 +
2.81 + ///Returns the distance of a node from the root.
2.82 + ///\pre \ref run() must be called before using this function.
2.83 + ///\warning If node \c v in unreachable from the root the return value
2.84 + ///of this funcion is undefined.
2.85 + ValueType dist(Node v) const { return distance[v]; }
2.86 +
2.87 + ///Returns the previous edge of the shortest path tree.
2.88 +
2.89 + ///For a node \c v it returns the previous edge of the shortest path tree,
2.90 + ///i.e. it returns the last edge from a shortest path from the root to \c
2.91 + ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
2.92 + ///shortest path tree used here is equal to the shortest path tree used in
2.93 + ///\ref predNode(Node v). \pre \ref run() must be called before using
2.94 + ///this function.
2.95 + Edge pred(Node v) const { return predecessor[v]; }
2.96 +
2.97 + ///Returns the previous node of the shortest path tree.
2.98 +
2.99 + ///For a node \c v it returns the previous node of the shortest path tree,
2.100 + ///i.e. it returns the last but one node from a shortest path from the
2.101 + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
2.102 + ///\c v=s. The shortest path tree used here is equal to the shortest path
2.103 + ///tree used in \ref pred(Node v). \pre \ref run() must be called before
2.104 + ///using this function.
2.105 + Node predNode(Node v) const { return pred_node[v]; }
2.106 +
2.107 + ///Returns a reference to the NodeMap of distances.
2.108 +
2.109 + ///Returns a reference to the NodeMap of distances. \pre \ref run() must
2.110 + ///be called before using this function.
2.111 + const DistMap &distMap() const { return distance;}
2.112 +
2.113 + ///Returns a reference to the shortest path tree map.
2.114 +
2.115 + ///Returns a reference to the NodeMap of the edges of the
2.116 + ///shortest path tree.
2.117 + ///\pre \ref run() must be called before using this function.
2.118 + const PredMap &predMap() const { return predecessor;}
2.119 +
2.120 + ///Returns a reference to the map of nodes of shortest paths.
2.121 +
2.122 + ///Returns a reference to the NodeMap of the last but one nodes of the
2.123 + ///shortest path tree.
2.124 + ///\pre \ref run() must be called before using this function.
2.125 + const PredNodeMap &predNodeMap() const { return pred_node;}
2.126 +
2.127 + ///Checks if a node is reachable from the root.
2.128 +
2.129 + ///Returns \c true if \c v is reachable from the root.
2.130 + ///\warning the root node is reported to be unreached!
2.131 + ///\todo Is this what we want?
2.132 + ///\pre \ref run() must be called before using this function.
2.133 + ///
2.134 + bool reached(Node v) { return G.valid(predecessor[v]); }
2.135 +
2.136 + };
2.137 +
2.138 +
2.139 + // **********************************************************************
2.140 + // IMPLEMENTATIONS
2.141 + // **********************************************************************
2.142 +
2.143 + ///Runs %Dijkstra algorithm from node the root.
2.144 +
2.145 + ///This method runs the %Dijkstra algorithm from a root node \c s
2.146 + ///in order to
2.147 + ///compute the
2.148 + ///shortest path to each node. The algorithm computes
2.149 + ///- The shortest path tree.
2.150 + ///- The distance of each node from the root.
2.151 + template <typename Graph, typename LengthMap,
2.152 + template<class,class,class,class> class Heap >
2.153 + void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
2.154 +
2.155 + NodeIt u;
2.156 + for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
2.157 + predecessor.set(u,INVALID);
2.158 + pred_node.set(u,INVALID);
2.159 + }
2.160 +
2.161 + typename Graph::template NodeMap<int> heap_map(G,-1);
2.162 +
2.163 + typedef Heap<Node, ValueType, typename Graph::template NodeMap<int>,
2.164 + std::less<ValueType> >
2.165 + HeapType;
2.166 +
2.167 + HeapType heap(heap_map);
2.168 +
2.169 + heap.push(s,0);
2.170 +
2.171 + while ( !heap.empty() ) {
2.172 +
2.173 + Node v=heap.top();
2.174 + ValueType oldvalue=heap[v];
2.175 + heap.pop();
2.176 + distance.set(v, oldvalue);
2.177 +
2.178 + { //FIXME this bracket is for e to be local
2.179 + OutEdgeIt e;
2.180 + for(G.first(e, v);
2.181 + G.valid(e); G.next(e)) {
2.182 + Node w=G.bNode(e);
2.183 +
2.184 + switch(heap.state(w)) {
2.185 + case HeapType::PRE_HEAP:
2.186 + heap.push(w,oldvalue+length[e]);
2.187 + predecessor.set(w,e);
2.188 + pred_node.set(w,v);
2.189 + break;
2.190 + case HeapType::IN_HEAP:
2.191 + if ( oldvalue+length[e] < heap[w] ) {
2.192 + heap.decrease(w, oldvalue+length[e]);
2.193 + predecessor.set(w,e);
2.194 + pred_node.set(w,v);
2.195 + }
2.196 + break;
2.197 + case HeapType::POST_HEAP:
2.198 + break;
2.199 + }
2.200 + }
2.201 + } //FIXME tis bracket
2.202 + }
2.203 + }
2.204 +
2.205 +/// @}
2.206 +
2.207 +} //END OF NAMESPACE HUGO
2.208 +
2.209 +#endif
2.210 +
2.211 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/hugo/dimacs.h Thu May 06 13:21:24 2004 +0000
3.3 @@ -0,0 +1,206 @@
3.4 +// -*- c++ -*-
3.5 +#ifndef HUGO_DIMACS_H
3.6 +#define HUGO_DIMACS_H
3.7 +
3.8 +#include <iostream>
3.9 +#include <string>
3.10 +#include <vector>
3.11 +#include <maps.h>
3.12 +
3.13 +/// \file
3.14 +/// \brief Dimacs file format reader.
3.15 +
3.16 +namespace hugo {
3.17 +
3.18 + /// Dimacs flow file format reader function.
3.19 +
3.20 + /// This function reads a flow instance from dimacs flow format.
3.21 + /// At the beginning \c g is cleared by \c g.clear().
3.22 + /// If the data coming from \c is is a max flow problem instance, then
3.23 + /// \c s and \c t will be respectively the source and target nodes
3.24 + /// and \c capacity will contain the edge capacities.
3.25 + /// If the data is a shortest path problem instance then \c s will be the
3.26 + /// source node and \c capacity will contain the edge lengths.
3.27 + ///
3.28 + ///\author Marton Makai
3.29 + template<typename Graph, typename CapacityMap>
3.30 + void readDimacsMaxFlow(std::istream& is, Graph &g,
3.31 + typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
3.32 + g.clear();
3.33 + int cap;
3.34 + char d;
3.35 + std::string problem;
3.36 + char c;
3.37 + int i, j;
3.38 + std::string str;
3.39 + int n, m;
3.40 + typename Graph::Edge e;
3.41 + std::vector<typename Graph::Node> nodes;
3.42 + while (is>>c) {
3.43 + switch (c) {
3.44 + case 'c': //comment
3.45 + getline(is, str);
3.46 + break;
3.47 + case 'p': //problem definition
3.48 + is >> problem >> n >> m;
3.49 + getline(is, str);
3.50 + nodes.resize(n+1);
3.51 + for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
3.52 + break;
3.53 + case 'n': //node definition
3.54 + if (problem=="sp") { //shortest path problem
3.55 + is >> i;
3.56 + getline(is, str);
3.57 + s=nodes[i];
3.58 + }
3.59 + if (problem=="max") { //max flow problem
3.60 + is >> i >> d;
3.61 + getline(is, str);
3.62 + if (d=='s') s=nodes[i];
3.63 + if (d=='t') t=nodes[i];
3.64 + }
3.65 + break;
3.66 + case 'a':
3.67 + is >> i >> j >> cap;
3.68 + getline(is, str);
3.69 + e=g.addEdge(nodes[i], nodes[j]);
3.70 + capacity.update();
3.71 + capacity.set(e, cap);
3.72 + break;
3.73 + }
3.74 + }
3.75 + }
3.76 +
3.77 + /// matching problem
3.78 + template<typename Graph>
3.79 + void readDimacs(std::istream& is, Graph &g) {
3.80 + typename Graph::Node u;
3.81 + NullMap<typename Graph::Edge, int> n;
3.82 + readDimacs(is, g, n, u, u, n);
3.83 + std::cout<<"igen en.";
3.84 + }
3.85 +
3.86 + /// sg problem
3.87 + template<typename Graph, typename CapacityMap>
3.88 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
3.89 + typename Graph::Node u;
3.90 + NullMap<typename Graph::Edge, int> n;
3.91 + readDimacs(is, g, capacity, u, u, n);
3.92 + }
3.93 +
3.94 + /// shortest path problem
3.95 + template<typename Graph, typename CapacityMap>
3.96 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
3.97 + typename Graph::Node &s) {
3.98 + NullMap<typename Graph::Edge, int> n;
3.99 + readDimacs(is, g, capacity, s, s, n);
3.100 + }
3.101 +
3.102 + /// max flow problem
3.103 + template<typename Graph, typename CapacityMap>
3.104 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
3.105 + typename Graph::Node &s, typename Graph::Node &t) {
3.106 + NullMap<typename Graph::Edge, int> n;
3.107 + readDimacs(is, g, capacity, s, t, n);
3.108 + }
3.109 +
3.110 + /// min cost flow problem
3.111 + template<typename Graph, typename CapacityMap, typename CostMap>
3.112 + void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
3.113 + typename Graph::Node &s, typename Graph::Node &t,
3.114 + CostMap& cost) {
3.115 + g.clear();
3.116 + typename CapacityMap::ValueType _cap;
3.117 + typename CostMap::ValueType _cost;
3.118 + char d;
3.119 + std::string problem;
3.120 + char c;
3.121 + int i, j;
3.122 + std::string str;
3.123 + int n, m;
3.124 + typename Graph::Edge e;
3.125 + std::vector<typename Graph::Node> nodes;
3.126 + while (is>>c) {
3.127 + switch (c) {
3.128 + case 'c': //comment
3.129 + getline(is, str);
3.130 + break;
3.131 + case 'p': //problem definition
3.132 + is >> problem >> n >> m;
3.133 + getline(is, str);
3.134 + nodes.resize(n+1);
3.135 + for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
3.136 + break;
3.137 + case 'n': //node definition
3.138 + if (problem=="sp") { //shortest path problem
3.139 + is >> i;
3.140 + getline(is, str);
3.141 + s=nodes[i];
3.142 + }
3.143 + if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
3.144 + is >> i >> d;
3.145 + getline(is, str);
3.146 + if (d=='s') s=nodes[i];
3.147 + if (d=='t') t=nodes[i];
3.148 + }
3.149 + break;
3.150 + case 'a':
3.151 + if ( problem == "mat" ) {
3.152 + is >> i >> j;
3.153 + getline(is, str);
3.154 + g.addEdge(nodes[i], nodes[j]);
3.155 + }
3.156 + if ( problem == "max" || problem == "sp") {
3.157 + is >> i >> j >> _cap;
3.158 + getline(is, str);
3.159 + e=g.addEdge(nodes[i], nodes[j]);
3.160 + capacity.update();
3.161 + capacity.set(e, _cap);
3.162 + }
3.163 + if ( problem == "min" ) {
3.164 + is >> i >> j >> _cap >> _cost;
3.165 + getline(is, str);
3.166 + e=g.addEdge(nodes[i], nodes[j]);
3.167 + capacity.update();
3.168 + capacity.set(e, _cap);
3.169 + cost.update();
3.170 + cost.set(e, _cost);
3.171 + }
3.172 + break;
3.173 + }
3.174 + }
3.175 + }
3.176 +
3.177 +
3.178 +
3.179 + /// write matching problem
3.180 + template<typename Graph>
3.181 + void writeDimacs(std::ostream& os, const Graph &g) {
3.182 + typedef typename Graph::NodeIt NodeIt;
3.183 + typedef typename Graph::EdgeIt EdgeIt;
3.184 +
3.185 + typename Graph::template NodeMap<int> nodes(g);
3.186 +
3.187 + os << "c matching problem" << std::endl;
3.188 +
3.189 + int i=1;
3.190 + NodeIt v;
3.191 + for(g.first(v); g.valid(v); g.next(v)) {
3.192 + nodes.set(v, i);
3.193 + ++i;
3.194 + }
3.195 +
3.196 + os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
3.197 +
3.198 + EdgeIt e;
3.199 + for(g.first(e); g.valid(e); g.next(e)) {
3.200 + os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
3.201 + }
3.202 +
3.203 + }
3.204 +
3.205 +
3.206 +
3.207 +} //namespace hugo
3.208 +
3.209 +#endif //HUGO_DIMACS_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/hugo/error.h Thu May 06 13:21:24 2004 +0000
4.3 @@ -0,0 +1,68 @@
4.4 +// -*- C++ -*- //
4.5 +
4.6 +#ifndef HUGO_ERROR_H
4.7 +#define HUGO_ERROR_H
4.8 +
4.9 +//! \ingroup misc
4.10 +//! \file
4.11 +//! \brief Basic error handling (signaling) routines.
4.12 +
4.13 +#include <exception>
4.14 +#include <string>
4.15 +#include <sstream>
4.16 +
4.17 +
4.18 +namespace hugo {
4.19 +
4.20 + /**
4.21 + * \brief Generic exception class.
4.22 + *
4.23 + * \todo Do we need this?
4.24 + *
4.25 + * \todo Don't we need different kind of exceptions for different kind
4.26 + * of errors?
4.27 + * Shouldn't we use \<stdexcept\> instead?
4.28 + */
4.29 + class Exception : public std::exception {
4.30 + protected:
4.31 + std::ostringstream buf;
4.32 + public:
4.33 + Exception() {}
4.34 + explicit Exception(const std::string &s) { buf << s; }
4.35 + Exception(const Exception &e) : std::exception() {
4.36 + buf << e.buf.str();
4.37 + }
4.38 + virtual ~Exception() throw() {}
4.39 +
4.40 + virtual const char* what() const throw() {
4.41 + return buf.str().c_str();
4.42 + }
4.43 +
4.44 + Exception& operator<<(std::string const& s) { buf << s; return *this; }
4.45 + Exception& operator<<(char const *s) { buf << s; return *this; }
4.46 + Exception& operator<<(int i) { buf << i; return *this; }
4.47 + };
4.48 +
4.49 + /**
4.50 + * \brief Generic error signaling function.
4.51 + *
4.52 + * \todo Do we really need this? Is it helpful?
4.53 + */
4.54 + inline void fault(const std::string &msg) {
4.55 + throw Exception(msg);
4.56 + }
4.57 +
4.58 + /**
4.59 + * \brief Macro for mark not yet implemented features.
4.60 + *
4.61 + * \todo Is this the right place for this? It should be used only in
4.62 + * modules under development.
4.63 + */
4.64 +
4.65 +# define FIXME(msg) \
4.66 + do { throw ::hugo::Exception() << "FIXME: " msg " (in: " \
4.67 + __FILE__ ", " << __LINE__ << ")"; \
4.68 + } while(false)
4.69 +
4.70 +}
4.71 +#endif // HUGO_ERROR_H
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/hugo/fib_heap.h Thu May 06 13:21:24 2004 +0000
5.3 @@ -0,0 +1,500 @@
5.4 +// -*- C++ -*-
5.5 +
5.6 +#ifndef HUGO_FIB_HEAP_H
5.7 +#define HUGO_FIB_HEAP_H
5.8 +
5.9 +///\ingroup auxdat
5.10 +///\file
5.11 +///\brief Fibonacci Heap implementation.
5.12 +
5.13 +#include <vector>
5.14 +#include <functional>
5.15 +#include <math.h>
5.16 +
5.17 +namespace hugo {
5.18 +
5.19 + /// \addtogroup auxdat
5.20 + /// @{
5.21 +
5.22 + /// An implementation of the Fibonacci Heap.
5.23 +
5.24 + /**
5.25 + This class implements the \e Fibonacci \e heap data structure. A \e heap
5.26 + is a data structure for storing items with specified values called \e
5.27 + priorities, such that finding the item with minimum priority with respect
5.28 + to \e Compare is efficient. In a heap one can change the priority of an
5.29 + item, add or erase an item, etc.
5.30 +
5.31 + The methods \ref increase and \ref erase are not efficient in a Fibonacci
5.32 + heap. In case of many calls to these operations, it is better to use a
5.33 + \e binary \e heap.
5.34 +
5.35 + \param Item The type of the items to be stored.
5.36 + \param Prio The type of the priority of the items.
5.37 + \param ItemIntMap A read and writable Item int map, for the usage of
5.38 + the heap.
5.39 + \param Compare A class for the comparison of the priorities. The
5.40 + default is \c std::less<Prio>.
5.41 +
5.42 + */
5.43 +
5.44 +#ifdef DOXYGEN
5.45 + template <typename Item,
5.46 + typename Prio,
5.47 + typename ItemIntMap,
5.48 + typename Compare>
5.49 +#else
5.50 + template <typename Item,
5.51 + typename Prio,
5.52 + typename ItemIntMap,
5.53 + typename Compare = std::less<Prio> >
5.54 +#endif
5.55 + class FibHeap {
5.56 + public:
5.57 + typedef Prio PrioType;
5.58 +
5.59 + private:
5.60 + class store;
5.61 +
5.62 + std::vector<store> container;
5.63 + int minimum;
5.64 + ItemIntMap &iimap;
5.65 + Compare comp;
5.66 + int num_items;
5.67 +
5.68 + public:
5.69 + enum state_enum {
5.70 + IN_HEAP = 0,
5.71 + PRE_HEAP = -1,
5.72 + POST_HEAP = -2
5.73 + };
5.74 +
5.75 + FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
5.76 + FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
5.77 + iimap(_iimap), comp(_comp), num_items() {}
5.78 +
5.79 + ///The number of items stored in the heap.
5.80 +
5.81 + /**
5.82 + Returns the number of items stored in the heap.
5.83 + */
5.84 + int size() const { return num_items; }
5.85 +
5.86 + ///Checks if the heap stores no items.
5.87 +
5.88 + /**
5.89 + Returns \c true iff the heap stores no items.
5.90 + */
5.91 + bool empty() const { return num_items==0; }
5.92 +
5.93 + ///\c item gets to the heap with priority \c value independently if \c item was already there.
5.94 +
5.95 + /**
5.96 + This method calls \ref push(\c item, \c value) if \c item is not
5.97 + stored in the heap and it calls \ref decrease(\c item, \c value) or
5.98 + \ref increase(\c item, \c value) otherwise.
5.99 + */
5.100 + void set (Item const item, PrioType const value);
5.101 +
5.102 + ///Adds \c item to the heap with priority \c value.
5.103 +
5.104 + /**
5.105 + Adds \c item to the heap with priority \c value.
5.106 + \pre \c item must not be stored in the heap.
5.107 + */
5.108 + void push (Item const item, PrioType const value);
5.109 +
5.110 +
5.111 + ///Returns the item having the minimum priority w.r.t. Compare.
5.112 +
5.113 + /**
5.114 + This method returns the item having the minimum priority w.r.t. Compare.
5.115 + \pre The heap must be nonempty.
5.116 + */
5.117 + Item top() const { return container[minimum].name; }
5.118 +
5.119 +
5.120 + ///Returns the minimum priority w.r.t. Compare.
5.121 +
5.122 + /**
5.123 + It returns the minimum priority w.r.t. Compare.
5.124 + \pre The heap must be nonempty.
5.125 + */
5.126 + PrioType prio() const { return container[minimum].prio; }
5.127 +
5.128 +
5.129 + ///Returns the priority of \c item.
5.130 +
5.131 + /**
5.132 + It returns the priority of \c item.
5.133 + \pre \c item must be in the heap.
5.134 + */
5.135 + PrioType& operator[](const Item& item) {
5.136 + return container[iimap[item]].prio;
5.137 + }
5.138 +
5.139 + ///Returns the priority of \c item.
5.140 +
5.141 + /**
5.142 + It returns the priority of \c item.
5.143 + \pre \c item must be in the heap.
5.144 + */
5.145 + const PrioType& operator[](const Item& item) const {
5.146 + return container[iimap[item]].prio;
5.147 + }
5.148 +
5.149 +
5.150 + ///Deletes the item with minimum priority w.r.t. Compare.
5.151 +
5.152 + /**
5.153 + This method deletes the item with minimum priority w.r.t.
5.154 + Compare from the heap.
5.155 + \pre The heap must be non-empty.
5.156 + */
5.157 + void pop();
5.158 +
5.159 + ///Deletes \c item from the heap.
5.160 +
5.161 + /**
5.162 + This method deletes \c item from the heap, if \c item was already
5.163 + stored in the heap. It is quite inefficient in Fibonacci heaps.
5.164 + */
5.165 + void erase (const Item& item);
5.166 +
5.167 + ///Decreases the priority of \c item to \c value.
5.168 +
5.169 + /**
5.170 + This method decreases the priority of \c item to \c value.
5.171 + \pre \c item must be stored in the heap with priority at least \c
5.172 + value w.r.t. Compare.
5.173 + */
5.174 + void decrease (Item item, PrioType const value);
5.175 +
5.176 +
5.177 + ///Increases the priority of \c item to \c value.
5.178 +
5.179 + /**
5.180 + This method sets the priority of \c item to \c value. Though
5.181 + there is no precondition on the priority of \c item, this
5.182 + method should be used only if there is a need to really \e increase
5.183 + (w.r.t. Compare) the priority of \c item, because this
5.184 + method is inefficient.
5.185 + */
5.186 + void increase (Item item, PrioType const value) {
5.187 + erase(item);
5.188 + push(item, value);
5.189 + }
5.190 +
5.191 +
5.192 + ///Tells if \c item is in, was already in, or has never been in the heap.
5.193 +
5.194 + /**
5.195 + This method returns PRE_HEAP if \c item has never been in the
5.196 + heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
5.197 + otherwise. In the latter case it is possible that \c item will
5.198 + get back to the heap again.
5.199 + */
5.200 + state_enum state(const Item &item) const {
5.201 + int i=iimap[item];
5.202 + if( i>=0 ) {
5.203 + if ( container[i].in ) i=0;
5.204 + else i=-2;
5.205 + }
5.206 + return state_enum(i);
5.207 + }
5.208 +
5.209 + private:
5.210 +
5.211 + void balance();
5.212 + void makeroot(int c);
5.213 + void cut(int a, int b);
5.214 + void cascade(int a);
5.215 + void fuse(int a, int b);
5.216 + void unlace(int a);
5.217 +
5.218 +
5.219 + class store {
5.220 + friend class FibHeap;
5.221 +
5.222 + Item name;
5.223 + int parent;
5.224 + int left_neighbor;
5.225 + int right_neighbor;
5.226 + int child;
5.227 + int degree;
5.228 + bool marked;
5.229 + bool in;
5.230 + PrioType prio;
5.231 +
5.232 + store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
5.233 + };
5.234 + };
5.235 +
5.236 +
5.237 +
5.238 + // **********************************************************************
5.239 + // IMPLEMENTATIONS
5.240 + // **********************************************************************
5.241 +
5.242 + template <typename Item, typename Prio, typename ItemIntMap,
5.243 + typename Compare>
5.244 + void FibHeap<Item, Prio, ItemIntMap, Compare>::set
5.245 + (Item const item, PrioType const value)
5.246 + {
5.247 + int i=iimap[item];
5.248 + if ( i >= 0 && container[i].in ) {
5.249 + if ( comp(value, container[i].prio) ) decrease(item, value);
5.250 + if ( comp(container[i].prio, value) ) increase(item, value);
5.251 + } else push(item, value);
5.252 + }
5.253 +
5.254 + template <typename Item, typename Prio, typename ItemIntMap,
5.255 + typename Compare>
5.256 + void FibHeap<Item, Prio, ItemIntMap, Compare>::push
5.257 + (Item const item, PrioType const value) {
5.258 + int i=iimap[item];
5.259 + if ( i < 0 ) {
5.260 + int s=container.size();
5.261 + iimap.set( item, s );
5.262 + store st;
5.263 + st.name=item;
5.264 + container.push_back(st);
5.265 + i=s;
5.266 + } else {
5.267 + container[i].parent=container[i].child=-1;
5.268 + container[i].degree=0;
5.269 + container[i].in=true;
5.270 + container[i].marked=false;
5.271 + }
5.272 +
5.273 + if ( num_items ) {
5.274 + container[container[minimum].right_neighbor].left_neighbor=i;
5.275 + container[i].right_neighbor=container[minimum].right_neighbor;
5.276 + container[minimum].right_neighbor=i;
5.277 + container[i].left_neighbor=minimum;
5.278 + if ( comp( value, container[minimum].prio) ) minimum=i;
5.279 + } else {
5.280 + container[i].right_neighbor=container[i].left_neighbor=i;
5.281 + minimum=i;
5.282 + }
5.283 + container[i].prio=value;
5.284 + ++num_items;
5.285 + }
5.286 +
5.287 + template <typename Item, typename Prio, typename ItemIntMap,
5.288 + typename Compare>
5.289 + void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
5.290 + /*The first case is that there are only one root.*/
5.291 + if ( container[minimum].left_neighbor==minimum ) {
5.292 + container[minimum].in=false;
5.293 + if ( container[minimum].degree!=0 ) {
5.294 + makeroot(container[minimum].child);
5.295 + minimum=container[minimum].child;
5.296 + balance();
5.297 + }
5.298 + } else {
5.299 + int right=container[minimum].right_neighbor;
5.300 + unlace(minimum);
5.301 + container[minimum].in=false;
5.302 + if ( container[minimum].degree > 0 ) {
5.303 + int left=container[minimum].left_neighbor;
5.304 + int child=container[minimum].child;
5.305 + int last_child=container[child].left_neighbor;
5.306 +
5.307 + makeroot(child);
5.308 +
5.309 + container[left].right_neighbor=child;
5.310 + container[child].left_neighbor=left;
5.311 + container[right].left_neighbor=last_child;
5.312 + container[last_child].right_neighbor=right;
5.313 + }
5.314 + minimum=right;
5.315 + balance();
5.316 + } // the case where there are more roots
5.317 + --num_items;
5.318 + }
5.319 +
5.320 +
5.321 + template <typename Item, typename Prio, typename ItemIntMap,
5.322 + typename Compare>
5.323 + void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
5.324 + (const Item& item) {
5.325 + int i=iimap[item];
5.326 +
5.327 + if ( i >= 0 && container[i].in ) {
5.328 + if ( container[i].parent!=-1 ) {
5.329 + int p=container[i].parent;
5.330 + cut(i,p);
5.331 + cascade(p);
5.332 + }
5.333 + minimum=i; //As if its prio would be -infinity
5.334 + pop();
5.335 + }
5.336 + }
5.337 +
5.338 + template <typename Item, typename Prio, typename ItemIntMap,
5.339 + typename Compare>
5.340 + void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
5.341 + (Item item, PrioType const value) {
5.342 + int i=iimap[item];
5.343 + container[i].prio=value;
5.344 + int p=container[i].parent;
5.345 +
5.346 + if ( p!=-1 && comp(value, container[p].prio) ) {
5.347 + cut(i,p);
5.348 + cascade(p);
5.349 + }
5.350 + if ( comp(value, container[minimum].prio) ) minimum=i;
5.351 + }
5.352 +
5.353 +
5.354 + template <typename Item, typename Prio, typename ItemIntMap,
5.355 + typename Compare>
5.356 + void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
5.357 +
5.358 + int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
5.359 +
5.360 + std::vector<int> A(maxdeg,-1);
5.361 +
5.362 + /*
5.363 + *Recall that now minimum does not point to the minimum prio element.
5.364 + *We set minimum to this during balance().
5.365 + */
5.366 + int anchor=container[minimum].left_neighbor;
5.367 + int next=minimum;
5.368 + bool end=false;
5.369 +
5.370 + do {
5.371 + int active=next;
5.372 + if ( anchor==active ) end=true;
5.373 + int d=container[active].degree;
5.374 + next=container[active].right_neighbor;
5.375 +
5.376 + while (A[d]!=-1) {
5.377 + if( comp(container[active].prio, container[A[d]].prio) ) {
5.378 + fuse(active,A[d]);
5.379 + } else {
5.380 + fuse(A[d],active);
5.381 + active=A[d];
5.382 + }
5.383 + A[d]=-1;
5.384 + ++d;
5.385 + }
5.386 + A[d]=active;
5.387 + } while ( !end );
5.388 +
5.389 +
5.390 + while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
5.391 + int s=minimum;
5.392 + int m=minimum;
5.393 + do {
5.394 + if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
5.395 + s=container[s].right_neighbor;
5.396 + } while ( s != m );
5.397 + }
5.398 +
5.399 + template <typename Item, typename Prio, typename ItemIntMap,
5.400 + typename Compare>
5.401 + void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
5.402 + (int c) {
5.403 + int s=c;
5.404 + do {
5.405 + container[s].parent=-1;
5.406 + s=container[s].right_neighbor;
5.407 + } while ( s != c );
5.408 + }
5.409 +
5.410 +
5.411 + template <typename Item, typename Prio, typename ItemIntMap,
5.412 + typename Compare>
5.413 + void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
5.414 + (int a, int b) {
5.415 + /*
5.416 + *Replacing a from the children of b.
5.417 + */
5.418 + --container[b].degree;
5.419 +
5.420 + if ( container[b].degree !=0 ) {
5.421 + int child=container[b].child;
5.422 + if ( child==a )
5.423 + container[b].child=container[child].right_neighbor;
5.424 + unlace(a);
5.425 + }
5.426 +
5.427 +
5.428 + /*Lacing a to the roots.*/
5.429 + int right=container[minimum].right_neighbor;
5.430 + container[minimum].right_neighbor=a;
5.431 + container[a].left_neighbor=minimum;
5.432 + container[a].right_neighbor=right;
5.433 + container[right].left_neighbor=a;
5.434 +
5.435 + container[a].parent=-1;
5.436 + container[a].marked=false;
5.437 + }
5.438 +
5.439 +
5.440 + template <typename Item, typename Prio, typename ItemIntMap,
5.441 + typename Compare>
5.442 + void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
5.443 + (int a)
5.444 + {
5.445 + if ( container[a].parent!=-1 ) {
5.446 + int p=container[a].parent;
5.447 +
5.448 + if ( container[a].marked==false ) container[a].marked=true;
5.449 + else {
5.450 + cut(a,p);
5.451 + cascade(p);
5.452 + }
5.453 + }
5.454 + }
5.455 +
5.456 +
5.457 + template <typename Item, typename Prio, typename ItemIntMap,
5.458 + typename Compare>
5.459 + void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
5.460 + (int a, int b) {
5.461 + unlace(b);
5.462 +
5.463 + /*Lacing b under a.*/
5.464 + container[b].parent=a;
5.465 +
5.466 + if (container[a].degree==0) {
5.467 + container[b].left_neighbor=b;
5.468 + container[b].right_neighbor=b;
5.469 + container[a].child=b;
5.470 + } else {
5.471 + int child=container[a].child;
5.472 + int last_child=container[child].left_neighbor;
5.473 + container[child].left_neighbor=b;
5.474 + container[b].right_neighbor=child;
5.475 + container[last_child].right_neighbor=b;
5.476 + container[b].left_neighbor=last_child;
5.477 + }
5.478 +
5.479 + ++container[a].degree;
5.480 +
5.481 + container[b].marked=false;
5.482 + }
5.483 +
5.484 +
5.485 + /*
5.486 + *It is invoked only if a has siblings.
5.487 + */
5.488 + template <typename Item, typename Prio, typename ItemIntMap,
5.489 + typename Compare>
5.490 + void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
5.491 + (int a) {
5.492 + int leftn=container[a].left_neighbor;
5.493 + int rightn=container[a].right_neighbor;
5.494 + container[leftn].right_neighbor=rightn;
5.495 + container[rightn].left_neighbor=leftn;
5.496 + }
5.497 +
5.498 + ///@}
5.499 +
5.500 +} //namespace hugo
5.501 +
5.502 +#endif //HUGO_FIB_HEAP_H
5.503 +
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/hugo/invalid.h Thu May 06 13:21:24 2004 +0000
6.3 @@ -0,0 +1,38 @@
6.4 +// -*- mode:C++ -*-
6.5 +
6.6 +#ifndef HUGO_INVALID_H
6.7 +#define HUGO_INVALID_H
6.8 +
6.9 +///\file
6.10 +///\brief Definition of INVALID.
6.11 +
6.12 +namespace hugo {
6.13 +
6.14 + /// Dummy type to make it easier to make invalid iterators.
6.15 +
6.16 + /// See \ref INVALID, how to use it.
6.17 +
6.18 + struct Invalid {
6.19 + public:
6.20 + bool operator==(Invalid) { return true; }
6.21 + bool operator!=(Invalid) { return false; }
6.22 + bool operator< (Invalid) { return false; }
6.23 + };
6.24 +
6.25 + /// Invalid iterators.
6.26 +
6.27 + /// \ref Invalid is a global type that converts to each iterator
6.28 + /// in such a way that the value of the target iterator will be invalid.
6.29 +
6.30 + // It is also used to convert the \c INVALID constant to the
6.31 + // node iterator that makes is possible to write
6.32 +
6.33 + //extern Invalid INVALID;
6.34 +
6.35 + //const Invalid &INVALID = *(Invalid *)0;
6.36 + const Invalid INVALID = Invalid();
6.37 +
6.38 +} //namespace hugo
6.39 +
6.40 +#endif
6.41 +
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/hugo/maps.h Thu May 06 13:21:24 2004 +0000
7.3 @@ -0,0 +1,129 @@
7.4 +// -*- C++ -*- //
7.5 +#ifndef HUGO_MAPS_H
7.6 +#define HUGO_MAPS_H
7.7 +
7.8 +///\file
7.9 +///\brief Miscellaneous property maps
7.10 +///
7.11 +///\todo This file has the same name as the concept file in skeletons,
7.12 +/// and this is not easily detectable in docs...
7.13 +
7.14 +#include <map>
7.15 +
7.16 +namespace hugo {
7.17 +
7.18 + /// Null map. (aka DoNothingMap)
7.19 +
7.20 + /// If you have to provide a map only for its type definitions,
7.21 + /// or if you have to provide a writable map, but will not use the
7.22 + /// data written to it...
7.23 + template<typename K, typename T>
7.24 + class NullMap
7.25 + {
7.26 + public:
7.27 + typedef K KeyType;
7.28 + typedef T ValueType;
7.29 +
7.30 + T operator[](const K&) const { return T(); }
7.31 + void set(const K&, const T&) {}
7.32 + ///\bug when update is removed from map concepts by being dynamic
7.33 + ///stuffs, this line have to be removed.
7.34 + void update() { }
7.35 + };
7.36 +
7.37 +
7.38 + /// Constant map.
7.39 +
7.40 + /// This is a readable map which assignes a specified value to each key.
7.41 + /// In other aspects it is equivalent to the \ref NullMap
7.42 + template<typename K, typename T>
7.43 + class ConstMap
7.44 + {
7.45 + T v;
7.46 + public:
7.47 + typedef K KeyType;
7.48 + typedef T ValueType;
7.49 +
7.50 + ConstMap() {}
7.51 + ConstMap(const T &_v) : v(_v) {}
7.52 +
7.53 + T operator[](const K&) const { return v; }
7.54 + void set(const K&, const T&) {}
7.55 +
7.56 + template<typename T1>
7.57 + struct rebind {
7.58 + typedef ConstMap<K,T1> other;
7.59 + };
7.60 +
7.61 + template<typename T1>
7.62 + ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {}
7.63 + };
7.64 +
7.65 +
7.66 +
7.67 + /// \c std::map wrapper
7.68 +
7.69 + /// This is essentially a wrapper for \c std::map. With addition that
7.70 + /// you can specify a default value different from \c ValueType() .
7.71 + ///
7.72 + /// \todo Provide allocator parameter...
7.73 + template <typename Key, typename T, typename Compare = std::less<Key> >
7.74 + class StdMap : public std::map<Key,T,Compare> {
7.75 + typedef std::map<Key,T,Compare> parent;
7.76 + T v;
7.77 + typedef typename parent::value_type PairType;
7.78 +
7.79 + public:
7.80 + typedef Key KeyType;
7.81 + typedef T ValueType;
7.82 + typedef T& ReferenceType;
7.83 + typedef const T& ConstReferenceType;
7.84 +
7.85 +
7.86 + StdMap() : v() {}
7.87 + /// Constructor with specified default value
7.88 + StdMap(const T& _v) : v(_v) {}
7.89 +
7.90 + /// \brief Constructs the map from an appropriate std::map.
7.91 + ///
7.92 + /// \warning Inefficient: copies the content of \c m !
7.93 + StdMap(const parent &m) : parent(m) {}
7.94 + /// \brief Constructs the map from an appropriate std::map, and explicitly
7.95 + /// specifies a default value.
7.96 + ///
7.97 + /// \warning Inefficient: copies the content of \c m !
7.98 + StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
7.99 +
7.100 + template<typename T1, typename Comp1>
7.101 + StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) {
7.102 + //FIXME;
7.103 + }
7.104 +
7.105 + ReferenceType operator[](const Key &k) {
7.106 + return insert(PairType(k,v)).first -> second;
7.107 + }
7.108 + ConstReferenceType operator[](const Key &k) const {
7.109 + typename parent::iterator i = lower_bound(k);
7.110 + if (i == parent::end() || parent::key_comp()(k, (*i).first))
7.111 + return v;
7.112 + return (*i).second;
7.113 + }
7.114 + void set(const Key &k, const T &t) {
7.115 + parent::operator[](k) = t;
7.116 + }
7.117 +
7.118 + /// Changes the default value of the map.
7.119 + /// \return Returns the previous default value.
7.120 + ///
7.121 + /// \warning The value of some keys (which has alredy been queried, but
7.122 + /// the value has been unchanged from the default) may change!
7.123 + T setDefault(const T &_v) { T old=v; v=_v; return old; }
7.124 +
7.125 + template<typename T1>
7.126 + struct rebind {
7.127 + typedef StdMap<Key,T1,Compare> other;
7.128 + };
7.129 + };
7.130 +
7.131 +}
7.132 +#endif // HUGO_MAPS_H
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/src/hugo/skeletons/graph.h Thu May 06 13:21:24 2004 +0000
8.3 @@ -0,0 +1,399 @@
8.4 +// -*- c++ -*-
8.5 +#ifndef HUGO_SKELETON_GRAPH_H
8.6 +#define HUGO_SKELETON_GRAPH_H
8.7 +
8.8 +///\file
8.9 +///\brief Declaration of GraphSkeleton.
8.10 +
8.11 +#include <invalid.h>
8.12 +
8.13 +/// The namespace of HugoLib
8.14 +namespace hugo {
8.15 +
8.16 + // @defgroup empty_graph The GraphSkeleton class
8.17 + // @{
8.18 +
8.19 + /// An empty graph class.
8.20 +
8.21 + /// This class provides all the common features of a graph structure,
8.22 + /// however completely without implementations and real data structures
8.23 + /// behind the interface.
8.24 + /// All graph algorithms should compile with this class, but it will not
8.25 + /// run properly, of course.
8.26 + ///
8.27 + /// It can be used for checking the interface compatibility,
8.28 + /// or it can serve as a skeleton of a new graph structure.
8.29 + ///
8.30 + /// Also, you will find here the full documentation of a certain graph
8.31 + /// feature, the documentation of a real graph imlementation
8.32 + /// like @ref ListGraph or
8.33 + /// @ref SmartGraph will just refer to this structure.
8.34 + class GraphSkeleton
8.35 + {
8.36 + public:
8.37 + /// Defalult constructor.
8.38 + GraphSkeleton() {}
8.39 + ///Copy consructor.
8.40 +
8.41 + ///\todo It is not clear, what we expect from a copy constructor.
8.42 + ///E.g. How to assign the nodes/edges to each other? What about maps?
8.43 + GraphSkeleton(const GraphSkeleton &G) {}
8.44 +
8.45 + /// The base type of the node iterators.
8.46 +
8.47 + /// This is the base type of each node iterators,
8.48 + /// thus each kind of node iterator will convert to this.
8.49 + class Node {
8.50 + public:
8.51 + /// @warning The default constructor sets the iterator
8.52 + /// to an undefined value.
8.53 + Node() {} //FIXME
8.54 + /// Invalid constructor \& conversion.
8.55 +
8.56 + /// This constructor initializes the iterator to be invalid.
8.57 + /// \sa Invalid for more details.
8.58 +
8.59 + Node(Invalid) {}
8.60 + //Node(const Node &) {}
8.61 +
8.62 + /// Two iterators are equal if and only if they point to the
8.63 + /// same object or both are invalid.
8.64 + bool operator==(Node) const { return true; }
8.65 +
8.66 + /// \sa \ref operator==(Node n)
8.67 + ///
8.68 + bool operator!=(Node) const { return true; }
8.69 +
8.70 + bool operator<(Node) const { return true; }
8.71 + };
8.72 +
8.73 + /// This iterator goes through each node.
8.74 +
8.75 + /// This iterator goes through each node.
8.76 + /// Its usage is quite simple, for example you can count the number
8.77 + /// of nodes in graph \c G of type \c Graph like this:
8.78 + /// \code
8.79 + ///int count=0;
8.80 + ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
8.81 + /// \endcode
8.82 + class NodeIt : public Node {
8.83 + public:
8.84 + /// @warning The default constructor sets the iterator
8.85 + /// to an undefined value.
8.86 + NodeIt() {} //FIXME
8.87 + /// Invalid constructor \& conversion.
8.88 +
8.89 + /// Initialize the iterator to be invalid
8.90 + /// \sa Invalid for more details.
8.91 + NodeIt(Invalid) {}
8.92 + /// Sets the iterator to the first node of \c G.
8.93 + NodeIt(const GraphSkeleton &) {}
8.94 + /// @warning The default constructor sets the iterator
8.95 + /// to an undefined value.
8.96 + NodeIt(const NodeIt &n) : Node(n) {}
8.97 + };
8.98 +
8.99 +
8.100 + /// The base type of the edge iterators.
8.101 + class Edge {
8.102 + public:
8.103 + /// @warning The default constructor sets the iterator
8.104 + /// to an undefined value.
8.105 + Edge() {} //FIXME
8.106 + /// Initialize the iterator to be invalid
8.107 + Edge(Invalid) {}
8.108 + /// Two iterators are equal if and only if they point to the
8.109 + /// same object or both are invalid.
8.110 + bool operator==(Edge) const { return true; }
8.111 + bool operator!=(Edge) const { return true; }
8.112 + bool operator<(Edge) const { return true; }
8.113 + };
8.114 +
8.115 + /// This iterator goes trough the outgoing edges of a node.
8.116 +
8.117 + /// This iterator goes trough the \e outgoing edges of a certain node
8.118 + /// of a graph.
8.119 + /// Its usage is quite simple, for example you can count the number
8.120 + /// of outgoing edges of a node \c n
8.121 + /// in graph \c G of type \c Graph as follows.
8.122 + /// \code
8.123 + ///int count=0;
8.124 + ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
8.125 + /// \endcode
8.126 +
8.127 + class OutEdgeIt : public Edge {
8.128 + public:
8.129 + /// @warning The default constructor sets the iterator
8.130 + /// to an undefined value.
8.131 + OutEdgeIt() {}
8.132 + /// Initialize the iterator to be invalid
8.133 + OutEdgeIt(Invalid) {}
8.134 + /// This constructor sets the iterator to first outgoing edge.
8.135 +
8.136 + /// This constructor set the iterator to the first outgoing edge of
8.137 + /// node
8.138 + ///@param n the node
8.139 + ///@param G the graph
8.140 + OutEdgeIt(const GraphSkeleton &, Node) {}
8.141 + };
8.142 +
8.143 + /// This iterator goes trough the incoming edges of a node.
8.144 +
8.145 + /// This iterator goes trough the \e incoming edges of a certain node
8.146 + /// of a graph.
8.147 + /// Its usage is quite simple, for example you can count the number
8.148 + /// of outgoing edges of a node \c n
8.149 + /// in graph \c G of type \c Graph as follows.
8.150 + /// \code
8.151 + ///int count=0;
8.152 + ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
8.153 + /// \endcode
8.154 +
8.155 + class InEdgeIt : public Edge {
8.156 + public:
8.157 + /// @warning The default constructor sets the iterator
8.158 + /// to an undefined value.
8.159 + InEdgeIt() {}
8.160 + /// Initialize the iterator to be invalid
8.161 + InEdgeIt(Invalid) {}
8.162 + InEdgeIt(const GraphSkeleton &, Node) {}
8.163 + };
8.164 + // class SymEdgeIt : public Edge {};
8.165 +
8.166 + /// This iterator goes through each edge.
8.167 +
8.168 + /// This iterator goes through each edge of a graph.
8.169 + /// Its usage is quite simple, for example you can count the number
8.170 + /// of edges in a graph \c G of type \c Graph as follows:
8.171 + /// \code
8.172 + ///int count=0;
8.173 + ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
8.174 + /// \endcode
8.175 + class EdgeIt : public Edge {
8.176 + public:
8.177 + /// @warning The default constructor sets the iterator
8.178 + /// to an undefined value.
8.179 + EdgeIt() {}
8.180 + /// Initialize the iterator to be invalid
8.181 + EdgeIt(Invalid) {}
8.182 + EdgeIt(const GraphSkeleton &) {}
8.183 + };
8.184 +
8.185 + /// First node of the graph.
8.186 +
8.187 + /// \retval i the first node.
8.188 + /// \return the first node.
8.189 + ///
8.190 + NodeIt &first(NodeIt &i) const { return i;}
8.191 +
8.192 + /// The first incoming edge.
8.193 + InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
8.194 + /// The first outgoing edge.
8.195 + OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
8.196 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
8.197 + /// The first edge of the Graph.
8.198 + EdgeIt &first(EdgeIt &i) const { return i;}
8.199 +
8.200 +// Node getNext(Node) const {}
8.201 +// InEdgeIt getNext(InEdgeIt) const {}
8.202 +// OutEdgeIt getNext(OutEdgeIt) const {}
8.203 +// //SymEdgeIt getNext(SymEdgeIt) const {}
8.204 +// EdgeIt getNext(EdgeIt) const {}
8.205 +
8.206 + /// Go to the next node.
8.207 + NodeIt &next(NodeIt &i) const { return i;}
8.208 + /// Go to the next incoming edge.
8.209 + InEdgeIt &next(InEdgeIt &i) const { return i;}
8.210 + /// Go to the next outgoing edge.
8.211 + OutEdgeIt &next(OutEdgeIt &i) const { return i;}
8.212 + //SymEdgeIt &next(SymEdgeIt &) const {}
8.213 + /// Go to the next edge.
8.214 + EdgeIt &next(EdgeIt &i) const { return i;}
8.215 +
8.216 + ///Gives back the head node of an edge.
8.217 + Node head(Edge) const { return INVALID; }
8.218 + ///Gives back the tail node of an edge.
8.219 + Node tail(Edge) const { return INVALID; }
8.220 +
8.221 + // Node aNode(InEdgeIt) const {}
8.222 + // Node aNode(OutEdgeIt) const {}
8.223 + // Node aNode(SymEdgeIt) const {}
8.224 +
8.225 + // Node bNode(InEdgeIt) const {}
8.226 + // Node bNode(OutEdgeIt) const {}
8.227 + // Node bNode(SymEdgeIt) const {}
8.228 +
8.229 + /// Checks if a node iterator is valid
8.230 +
8.231 + ///\todo Maybe, it would be better if iterator converted to
8.232 + ///bool directly, as Jacint prefers.
8.233 + bool valid(const Node&) const { return true;}
8.234 + /// Checks if an edge iterator is valid
8.235 +
8.236 + ///\todo Maybe, it would be better if iterator converted to
8.237 + ///bool directly, as Jacint prefers.
8.238 + bool valid(const Edge&) const { return true;}
8.239 +
8.240 + ///Gives back the \e id of a node.
8.241 +
8.242 + ///\warning Not all graph structures provide this feature.
8.243 + ///
8.244 + int id(const Node&) const { return 0;}
8.245 + ///Gives back the \e id of an edge.
8.246 +
8.247 + ///\warning Not all graph structures provide this feature.
8.248 + ///
8.249 + int id(const Edge&) const { return 0;}
8.250 +
8.251 + //void setInvalid(Node &) const {};
8.252 + //void setInvalid(Edge &) const {};
8.253 +
8.254 + ///Add a new node to the graph.
8.255 +
8.256 + /// \return the new node.
8.257 + ///
8.258 + Node addNode() { return INVALID;}
8.259 + ///Add a new edge to the graph.
8.260 +
8.261 + ///Add a new edge to the graph with tail node \c tail
8.262 + ///and head node \c head.
8.263 + ///\return the new edge.
8.264 + Edge addEdge(Node, Node) { return INVALID;}
8.265 +
8.266 + /// Resets the graph.
8.267 +
8.268 + /// This function deletes all edges and nodes of the graph.
8.269 + /// It also frees the memory allocated to store them.
8.270 + void clear() {}
8.271 +
8.272 + int nodeNum() const { return 0;}
8.273 + int edgeNum() const { return 0;}
8.274 +
8.275 + ///Read/write/reference map of the nodes to type \c T.
8.276 +
8.277 + ///Read/write/reference map of the nodes to type \c T.
8.278 + /// \sa MemoryMapSkeleton
8.279 + /// \todo We may need copy constructor
8.280 + /// \todo We may need conversion from other nodetype
8.281 + /// \todo We may need operator=
8.282 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
8.283 + /// needs extra attention!
8.284 +
8.285 + template<class T> class NodeMap
8.286 + {
8.287 + public:
8.288 + typedef T ValueType;
8.289 + typedef Node KeyType;
8.290 +
8.291 + NodeMap(const GraphSkeleton &) {}
8.292 + NodeMap(const GraphSkeleton &, T) {}
8.293 +
8.294 + template<typename TT> NodeMap(const NodeMap<TT> &) {}
8.295 +
8.296 + /// Sets the value of a node.
8.297 +
8.298 + /// Sets the value associated with node \c i to the value \c t.
8.299 + ///
8.300 + void set(Node, T) {}
8.301 + // Gets the value of a node.
8.302 + //T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary?
8.303 + T &operator[](Node) {return *(T*)0;}
8.304 + const T &operator[](Node) const {return *(T*)0;}
8.305 +
8.306 + /// Updates the map if the graph has been changed
8.307 +
8.308 + /// \todo Do we need this?
8.309 + ///
8.310 + void update() {}
8.311 + void update(T a) {} //FIXME: Is it necessary
8.312 + };
8.313 +
8.314 + ///Read/write/reference map of the edges to type \c T.
8.315 +
8.316 + ///Read/write/reference map of the edges to type \c T.
8.317 + ///It behaves exactly in the same way as \ref NodeMap.
8.318 + /// \sa NodeMap
8.319 + /// \sa MemoryMapSkeleton
8.320 + /// \todo We may need copy constructor
8.321 + /// \todo We may need conversion from other edgetype
8.322 + /// \todo We may need operator=
8.323 + template<class T> class EdgeMap
8.324 + {
8.325 + public:
8.326 + typedef T ValueType;
8.327 + typedef Edge KeyType;
8.328 +
8.329 + EdgeMap(const GraphSkeleton &) {}
8.330 + EdgeMap(const GraphSkeleton &, T ) {}
8.331 +
8.332 + ///\todo It can copy between different types.
8.333 + ///
8.334 + template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
8.335 +
8.336 + void set(Edge, T) {}
8.337 + //T get(Edge) const {return *(T*)0;}
8.338 + T &operator[](Edge) {return *(T*)0;}
8.339 + const T &operator[](Edge) const {return *(T*)0;}
8.340 +
8.341 + void update() {}
8.342 + void update(T a) {} //FIXME: Is it necessary
8.343 + };
8.344 + };
8.345 +
8.346 + /// An empty eraseable graph class.
8.347 +
8.348 + /// This class provides all the common features of an \e eraseable graph
8.349 + /// structure,
8.350 + /// however completely without implementations and real data structures
8.351 + /// behind the interface.
8.352 + /// All graph algorithms should compile with this class, but it will not
8.353 + /// run properly, of course.
8.354 + ///
8.355 + /// \todo This blabla could be replaced by a sepatate description about
8.356 + /// Skeletons.
8.357 + ///
8.358 + /// It can be used for checking the interface compatibility,
8.359 + /// or it can serve as a skeleton of a new graph structure.
8.360 + ///
8.361 + /// Also, you will find here the full documentation of a certain graph
8.362 + /// feature, the documentation of a real graph imlementation
8.363 + /// like @ref ListGraph or
8.364 + /// @ref SmartGraph will just refer to this structure.
8.365 + class EraseableGraphSkeleton : public GraphSkeleton
8.366 + {
8.367 + public:
8.368 + /// Deletes a node.
8.369 + void erase(Node n) {}
8.370 + /// Deletes an edge.
8.371 + void erase(Edge e) {}
8.372 +
8.373 + /// Defalult constructor.
8.374 + EraseableGraphSkeleton() {}
8.375 + ///Copy consructor.
8.376 + EraseableGraphSkeleton(const GraphSkeleton &G) {}
8.377 + };
8.378 +
8.379 +
8.380 + // @}
8.381 +
8.382 +} //namespace hugo
8.383 +
8.384 +
8.385 +
8.386 +// class EmptyBipGraph : public Graph Skeleton
8.387 +// {
8.388 +// class ANode {};
8.389 +// class BNode {};
8.390 +
8.391 +// ANode &next(ANode &) {}
8.392 +// BNode &next(BNode &) {}
8.393 +
8.394 +// ANode &getFirst(ANode &) const {}
8.395 +// BNode &getFirst(BNode &) const {}
8.396 +
8.397 +// enum NodeClass { A = 0, B = 1 };
8.398 +// NodeClass getClass(Node n) {}
8.399 +
8.400 +// }
8.401 +
8.402 +#endif // HUGO_SKELETON_GRAPH_H
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/src/hugo/skeletons/maps.h Thu May 06 13:21:24 2004 +0000
9.3 @@ -0,0 +1,130 @@
9.4 +// -*- c++ -*-
9.5 +#ifndef HUGO_MAPSKELETON_H
9.6 +#define HUGO_MAPSKELETON_H
9.7 +
9.8 +///\file
9.9 +///\brief Map concepts checking classes for testing and documenting.
9.10 +
9.11 +namespace hugo {
9.12 +
9.13 + /// The namespace of HUGOlib concepts and concept checking classes
9.14 + namespace skeleton {
9.15 +
9.16 + /// Readable map concept
9.17 + template<typename K, typename T>
9.18 + class ReadableMap
9.19 + {
9.20 + public:
9.21 + /// Map's key type.
9.22 + typedef K KeyType;
9.23 + /// Map's value type. (The type of objects associated with the keys).
9.24 + typedef T ValueType;
9.25 +
9.26 + /// Returns the value associated with a key.
9.27 + ValueType operator[](const KeyType &k) const {return ValueType();}
9.28 +
9.29 + /// Copy contsructor. (optional)
9.30 + ReadableMap(const ReadableMap&) {}
9.31 + /// Assignment operator. (optional)
9.32 + ReadableMap& operator=(const ReadableMap&) {return *this;}
9.33 +
9.34 + ReadableMap() {}
9.35 + };
9.36 +
9.37 +
9.38 + /// Writable map concept
9.39 + template<typename K, typename T>
9.40 + class WritableMap
9.41 + {
9.42 + public:
9.43 + /// Map's key type.
9.44 + typedef K KeyType;
9.45 + /// Map's value type. (The type of objects associated with the keys).
9.46 + typedef T ValueType;
9.47 +
9.48 + /// Sets the value associated with a key.
9.49 + void set(const KeyType &k,const ValueType &t) {}
9.50 +
9.51 + WritableMap() {}
9.52 + };
9.53 +
9.54 + ///Read/Writeable map concept
9.55 + template<typename K, typename T>
9.56 + class ReadWritableMap : public ReadableMap<K,T>,
9.57 + public WritableMap<K,T>
9.58 + {
9.59 + public:
9.60 + /// Map's key type.
9.61 + typedef K KeyType;
9.62 + /// Map's value type. (The type of objects associated with the keys).
9.63 + typedef T ValueType;
9.64 +
9.65 + /// Returns the value associated with a key.
9.66 + ValueType operator[](const KeyType &k) const {return ValueType();}
9.67 + /// Sets the value associated with a key.
9.68 + void set(const KeyType &k,const ValueType &t) {}
9.69 +
9.70 + /// Copy contsructor. (optional)
9.71 + ReadWritableMap(const ReadWritableMap&) {}
9.72 + /// Assignment operator. (optional)
9.73 + ReadWritableMap& operator=(const ReadWritableMap&) {return *this;}
9.74 +
9.75 + /// Facility to define a map with an other value type (optional)
9.76 + template<typename T1>
9.77 + struct rebind {
9.78 + /// The type of a map with the given value type
9.79 + typedef ReadWritableMap<K,T1> other;
9.80 + };
9.81 + /// @brief Constructor that copies all keys from the other map and
9.82 + /// assigns to them a default value (optional)
9.83 + template<typename T1>
9.84 + ReadWritableMap(const ReadWritableMap<K,T1> &map, const ValueType &v) {}
9.85 +
9.86 + ReadWritableMap() {}
9.87 + };
9.88 +
9.89 +
9.90 + ///Dereferable map concept
9.91 + template<typename K, typename T>
9.92 + class DereferableMap : public ReadWritableMap<K,T>
9.93 + {
9.94 + public:
9.95 + /// Map's key type.
9.96 + typedef K KeyType;
9.97 + /// Map's value type. (The type of objects associated with the keys).
9.98 + typedef T ValueType;
9.99 + /// Map's reference type. (Reference to an object associated with a key)
9.100 + typedef ValueType& ReferenceType;
9.101 + /// Map's const reference type.
9.102 + typedef const ValueType& ConstReferenceType;
9.103 +
9.104 + ///Returns a reference to the value associated to a key.
9.105 + ReferenceType operator[](const KeyType &i);
9.106 + ///Returns a const reference to the value associated to a key.
9.107 + ConstReferenceType operator[](const KeyType &i) const;
9.108 + /// Sets the value associated with a key.
9.109 + void set(const KeyType &k,const ValueType &t) { operator[](k)=t; }
9.110 +
9.111 + /// Copy contsructor. (optional)
9.112 + DereferableMap(const DereferableMap&) {}
9.113 + /// Assignment operator. (optional)
9.114 + DereferableMap& operator=(const DereferableMap&) {return *this;}
9.115 +
9.116 + /// Facility to define a map with an other value type (optional)
9.117 + template<typename T1>
9.118 + struct rebind {
9.119 + /// The type of a map with the given value type
9.120 + typedef DereferableMap<K,T1> other;
9.121 + };
9.122 + /// @brief Constructor that copies all keys from the other map and
9.123 + /// assigns to them a default value (optional)
9.124 + template<typename T1>
9.125 + DereferableMap(const DereferableMap<K,T1> &map, const ValueType &v) {}
9.126 +
9.127 + DereferableMap() {}
9.128 + };
9.129 +
9.130 +
9.131 + }
9.132 +}
9.133 +#endif // HUGO_MAPSKELETON_H
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/src/hugo/smart_graph.h Thu May 06 13:21:24 2004 +0000
10.3 @@ -0,0 +1,614 @@
10.4 +// -*- mode:C++ -*-
10.5 +
10.6 +#ifndef HUGO_SMART_GRAPH_H
10.7 +#define HUGO_SMART_GRAPH_H
10.8 +
10.9 +///\ingroup graphs
10.10 +///\file
10.11 +///\brief SmartGraph and SymSmartGraph classes.
10.12 +
10.13 +#include <vector>
10.14 +#include <limits.h>
10.15 +
10.16 +#include "invalid.h"
10.17 +
10.18 +namespace hugo {
10.19 +
10.20 +/// \addtogroup graphs
10.21 +/// @{
10.22 + class SymSmartGraph;
10.23 +
10.24 + ///A smart graph class.
10.25 +
10.26 + ///This is a simple and fast graph implementation.
10.27 + ///It is also quite memory efficient, but at the price
10.28 + ///that <b> it does not support node and edge deletion</b>.
10.29 + ///It conforms to the graph interface documented under
10.30 + ///the description of \ref GraphSkeleton.
10.31 + ///\sa \ref GraphSkeleton.
10.32 + ///
10.33 + ///\todo Some member functions could be \c static.
10.34 + ///\author Alpar Juttner
10.35 + class SmartGraph {
10.36 +
10.37 + struct NodeT
10.38 + {
10.39 + int first_in,first_out;
10.40 + NodeT() : first_in(-1), first_out(-1) {}
10.41 + };
10.42 + struct EdgeT
10.43 + {
10.44 + int head, tail, next_in, next_out;
10.45 + //FIXME: is this necessary?
10.46 + EdgeT() : next_in(-1), next_out(-1) {}
10.47 + };
10.48 +
10.49 + std::vector<NodeT> nodes;
10.50 +
10.51 + std::vector<EdgeT> edges;
10.52 +
10.53 + protected:
10.54 +
10.55 + template <typename Key> class DynMapBase
10.56 + {
10.57 + protected:
10.58 + const SmartGraph* G;
10.59 + public:
10.60 + virtual void add(const Key k) = 0;
10.61 + virtual void erase(const Key k) = 0;
10.62 + DynMapBase(const SmartGraph &_G) : G(&_G) {}
10.63 + virtual ~DynMapBase() {}
10.64 + friend class SmartGraph;
10.65 + };
10.66 +
10.67 + public:
10.68 + template <typename T> class EdgeMap;
10.69 + template <typename T> class EdgeMap;
10.70 +
10.71 + class Node;
10.72 + class Edge;
10.73 +
10.74 + // protected:
10.75 + // HELPME:
10.76 + protected:
10.77 + ///\bug It must be public because of SymEdgeMap.
10.78 + ///
10.79 + mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
10.80 + ///\bug It must be public because of SymEdgeMap.
10.81 + ///
10.82 + mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
10.83 +
10.84 + public:
10.85 +
10.86 +
10.87 + class NodeIt;
10.88 + class EdgeIt;
10.89 + class OutEdgeIt;
10.90 + class InEdgeIt;
10.91 +
10.92 + template <typename T> class NodeMap;
10.93 + template <typename T> class EdgeMap;
10.94 +
10.95 + public:
10.96 +
10.97 + SmartGraph() : nodes(), edges() { }
10.98 + SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
10.99 +
10.100 + ~SmartGraph()
10.101 + {
10.102 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
10.103 + i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
10.104 + for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
10.105 + i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
10.106 + }
10.107 +
10.108 + int nodeNum() const { return nodes.size(); } //FIXME: What is this?
10.109 + int edgeNum() const { return edges.size(); } //FIXME: What is this?
10.110 +
10.111 + ///\bug This function does something different than
10.112 + ///its name would suggests...
10.113 + int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
10.114 + ///\bug This function does something different than
10.115 + ///its name would suggests...
10.116 + int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
10.117 +
10.118 + Node tail(Edge e) const { return edges[e.n].tail; }
10.119 + Node head(Edge e) const { return edges[e.n].head; }
10.120 +
10.121 + Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
10.122 + Node aNode(InEdgeIt e) const { return edges[e.n].head; }
10.123 +
10.124 + Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
10.125 + Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
10.126 +
10.127 + NodeIt& first(NodeIt& v) const {
10.128 + v=NodeIt(*this); return v; }
10.129 + EdgeIt& first(EdgeIt& e) const {
10.130 + e=EdgeIt(*this); return e; }
10.131 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
10.132 + e=OutEdgeIt(*this,v); return e; }
10.133 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
10.134 + e=InEdgeIt(*this,v); return e; }
10.135 +
10.136 +// template< typename It >
10.137 +// It first() const { It e; first(e); return e; }
10.138 +
10.139 +// template< typename It >
10.140 +// It first(Node v) const { It e; first(e,v); return e; }
10.141 +
10.142 + bool valid(Edge e) const { return e.n!=-1; }
10.143 + bool valid(Node n) const { return n.n!=-1; }
10.144 +
10.145 + ///\deprecated Use
10.146 + ///\code
10.147 + /// e=INVALID;
10.148 + ///\endcode
10.149 + ///instead.
10.150 + void setInvalid(Edge &e) { e.n=-1; }
10.151 + ///\deprecated Use
10.152 + ///\code
10.153 + /// e=INVALID;
10.154 + ///\endcode
10.155 + ///instead.
10.156 + void setInvalid(Node &n) { n.n=-1; }
10.157 +
10.158 + template <typename It> It getNext(It it) const
10.159 + { It tmp(it); return next(tmp); }
10.160 +
10.161 + NodeIt& next(NodeIt& it) const {
10.162 + it.n=(it.n+2)%(nodes.size()+1)-1;
10.163 + return it;
10.164 + }
10.165 + OutEdgeIt& next(OutEdgeIt& it) const
10.166 + { it.n=edges[it.n].next_out; return it; }
10.167 + InEdgeIt& next(InEdgeIt& it) const
10.168 + { it.n=edges[it.n].next_in; return it; }
10.169 + EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
10.170 +
10.171 + int id(Node v) const { return v.n; }
10.172 + int id(Edge e) const { return e.n; }
10.173 +
10.174 + Node addNode() {
10.175 + Node n; n.n=nodes.size();
10.176 + nodes.push_back(NodeT()); //FIXME: Hmmm...
10.177 +
10.178 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
10.179 + i!=dyn_node_maps.end(); ++i) (**i).add(n);
10.180 +
10.181 + return n;
10.182 + }
10.183 +
10.184 + Edge addEdge(Node u, Node v) {
10.185 + Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
10.186 + edges[e.n].tail=u.n; edges[e.n].head=v.n;
10.187 + edges[e.n].next_out=nodes[u.n].first_out;
10.188 + edges[e.n].next_in=nodes[v.n].first_in;
10.189 + nodes[u.n].first_out=nodes[v.n].first_in=e.n;
10.190 +
10.191 + for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
10.192 + i!=dyn_edge_maps.end(); ++i) (**i).add(e);
10.193 +
10.194 + return e;
10.195 + }
10.196 +
10.197 + void clear() {nodes.clear();edges.clear();}
10.198 +
10.199 + class Node {
10.200 + friend class SmartGraph;
10.201 + template <typename T> friend class NodeMap;
10.202 +
10.203 + friend class Edge;
10.204 + friend class OutEdgeIt;
10.205 + friend class InEdgeIt;
10.206 + friend class SymEdge;
10.207 +
10.208 + protected:
10.209 + int n;
10.210 + friend int SmartGraph::id(Node v) const;
10.211 + Node(int nn) {n=nn;}
10.212 + public:
10.213 + Node() {}
10.214 + Node (Invalid) { n=-1; }
10.215 + bool operator==(const Node i) const {return n==i.n;}
10.216 + bool operator!=(const Node i) const {return n!=i.n;}
10.217 + bool operator<(const Node i) const {return n<i.n;}
10.218 + };
10.219 +
10.220 + class NodeIt : public Node {
10.221 + friend class SmartGraph;
10.222 + public:
10.223 + NodeIt() : Node() { }
10.224 + NodeIt(Invalid i) : Node(i) { }
10.225 + NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
10.226 + };
10.227 +
10.228 + class Edge {
10.229 + friend class SmartGraph;
10.230 + template <typename T> friend class EdgeMap;
10.231 +
10.232 + //template <typename T> friend class SymSmartGraph::SymEdgeMap;
10.233 + //friend Edge SymSmartGraph::opposite(Edge) const;
10.234 +
10.235 + friend class Node;
10.236 + friend class NodeIt;
10.237 + protected:
10.238 + int n;
10.239 + friend int SmartGraph::id(Edge e) const;
10.240 +
10.241 + Edge(int nn) {n=nn;}
10.242 + public:
10.243 + Edge() { }
10.244 + Edge (Invalid) { n=-1; }
10.245 + bool operator==(const Edge i) const {return n==i.n;}
10.246 + bool operator!=(const Edge i) const {return n!=i.n;}
10.247 + bool operator<(const Edge i) const {return n<i.n;}
10.248 + ///\bug This is a workaround until somebody tells me how to
10.249 + ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
10.250 + int &idref() {return n;}
10.251 + const int &idref() const {return n;}
10.252 + };
10.253 +
10.254 + class EdgeIt : public Edge {
10.255 + friend class SmartGraph;
10.256 + public:
10.257 + EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
10.258 + EdgeIt (Invalid i) : Edge(i) { }
10.259 + EdgeIt() : Edge() { }
10.260 + ///\bug This is a workaround until somebody tells me how to
10.261 + ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
10.262 + int &idref() {return n;}
10.263 + };
10.264 +
10.265 + class OutEdgeIt : public Edge {
10.266 + friend class SmartGraph;
10.267 + public:
10.268 + OutEdgeIt() : Edge() { }
10.269 + OutEdgeIt (Invalid i) : Edge(i) { }
10.270 +
10.271 + OutEdgeIt(const SmartGraph& G,const Node v)
10.272 + : Edge(G.nodes[v.n].first_out) {}
10.273 + };
10.274 +
10.275 + class InEdgeIt : public Edge {
10.276 + friend class SmartGraph;
10.277 + public:
10.278 + InEdgeIt() : Edge() { }
10.279 + InEdgeIt (Invalid i) : Edge(i) { }
10.280 + InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
10.281 + };
10.282 +
10.283 + template <typename T> class NodeMap : public DynMapBase<Node>
10.284 + {
10.285 + std::vector<T> container;
10.286 +
10.287 + public:
10.288 + typedef T ValueType;
10.289 + typedef Node KeyType;
10.290 +
10.291 + NodeMap(const SmartGraph &_G) :
10.292 + DynMapBase<Node>(_G), container(_G.maxNodeId())
10.293 + {
10.294 + G->dyn_node_maps.push_back(this);
10.295 + }
10.296 + NodeMap(const SmartGraph &_G,const T &t) :
10.297 + DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
10.298 + {
10.299 + G->dyn_node_maps.push_back(this);
10.300 + }
10.301 +
10.302 + NodeMap(const NodeMap<T> &m) :
10.303 + DynMapBase<Node>(*m.G), container(m.container)
10.304 + {
10.305 + G->dyn_node_maps.push_back(this);
10.306 + }
10.307 +
10.308 + template<typename TT> friend class NodeMap;
10.309 +
10.310 + ///\todo It can copy between different types.
10.311 + ///
10.312 + template<typename TT> NodeMap(const NodeMap<TT> &m) :
10.313 + DynMapBase<Node>(*m.G)
10.314 + {
10.315 + G->dyn_node_maps.push_back(this);
10.316 + typename std::vector<TT>::const_iterator i;
10.317 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
10.318 + i!=m.container.end();
10.319 + i++)
10.320 + container.push_back(*i);
10.321 + }
10.322 + ~NodeMap()
10.323 + {
10.324 + if(G) {
10.325 + std::vector<DynMapBase<Node>* >::iterator i;
10.326 + for(i=G->dyn_node_maps.begin();
10.327 + i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
10.328 + //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
10.329 + //A better way to do that: (Is this really important?)
10.330 + if(*i==this) {
10.331 + *i=G->dyn_node_maps.back();
10.332 + G->dyn_node_maps.pop_back();
10.333 + }
10.334 + }
10.335 + }
10.336 +
10.337 + void add(const Node k)
10.338 + {
10.339 + if(k.n>=int(container.size())) container.resize(k.n+1);
10.340 + }
10.341 +
10.342 + void erase(const Node) { }
10.343 +
10.344 + void set(Node n, T a) { container[n.n]=a; }
10.345 + //'T& operator[](Node n)' would be wrong here
10.346 + typename std::vector<T>::reference
10.347 + operator[](Node n) { return container[n.n]; }
10.348 + //'const T& operator[](Node n)' would be wrong here
10.349 + typename std::vector<T>::const_reference
10.350 + operator[](Node n) const { return container[n.n]; }
10.351 +
10.352 + ///\warning There is no safety check at all!
10.353 + ///Using operator = between maps attached to different graph may
10.354 + ///cause serious problem.
10.355 + ///\todo Is this really so?
10.356 + ///\todo It can copy between different types.
10.357 + const NodeMap<T>& operator=(const NodeMap<T> &m)
10.358 + {
10.359 + container = m.container;
10.360 + return *this;
10.361 + }
10.362 + template<typename TT>
10.363 + const NodeMap<T>& operator=(const NodeMap<TT> &m)
10.364 + {
10.365 + std::copy(m.container.begin(), m.container.end(), container.begin());
10.366 + return *this;
10.367 + }
10.368 +
10.369 + void update() {} //Useless for Dynamic Maps
10.370 + void update(T a) {} //Useless for Dynamic Maps
10.371 + };
10.372 +
10.373 + template <typename T> class EdgeMap : public DynMapBase<Edge>
10.374 + {
10.375 + std::vector<T> container;
10.376 +
10.377 + public:
10.378 + typedef T ValueType;
10.379 + typedef Edge KeyType;
10.380 +
10.381 + EdgeMap(const SmartGraph &_G) :
10.382 + DynMapBase<Edge>(_G), container(_G.maxEdgeId())
10.383 + {
10.384 + //FIXME: What if there are empty Id's?
10.385 + //FIXME: Can I use 'this' in a constructor?
10.386 + G->dyn_edge_maps.push_back(this);
10.387 + }
10.388 + EdgeMap(const SmartGraph &_G,const T &t) :
10.389 + DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
10.390 + {
10.391 + G->dyn_edge_maps.push_back(this);
10.392 + }
10.393 + EdgeMap(const EdgeMap<T> &m) :
10.394 + DynMapBase<Edge>(*m.G), container(m.container)
10.395 + {
10.396 + G->dyn_edge_maps.push_back(this);
10.397 + }
10.398 +
10.399 + template<typename TT> friend class EdgeMap;
10.400 +
10.401 + ///\todo It can copy between different types.
10.402 + ///
10.403 + template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
10.404 + DynMapBase<Edge>(*m.G)
10.405 + {
10.406 + G->dyn_edge_maps.push_back(this);
10.407 + typename std::vector<TT>::const_iterator i;
10.408 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
10.409 + i!=m.container.end();
10.410 + i++)
10.411 + container.push_back(*i);
10.412 + }
10.413 + ~EdgeMap()
10.414 + {
10.415 + if(G) {
10.416 + std::vector<DynMapBase<Edge>* >::iterator i;
10.417 + for(i=G->dyn_edge_maps.begin();
10.418 + i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
10.419 + //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
10.420 + //A better way to do that: (Is this really important?)
10.421 + if(*i==this) {
10.422 + *i=G->dyn_edge_maps.back();
10.423 + G->dyn_edge_maps.pop_back();
10.424 + }
10.425 + }
10.426 + }
10.427 +
10.428 + void add(const Edge k)
10.429 + {
10.430 + if(k.n>=int(container.size())) container.resize(k.n+1);
10.431 + }
10.432 + void erase(const Edge) { }
10.433 +
10.434 + void set(Edge n, T a) { container[n.n]=a; }
10.435 + //T get(Edge n) const { return container[n.n]; }
10.436 + typename std::vector<T>::reference
10.437 + operator[](Edge n) { return container[n.n]; }
10.438 + typename std::vector<T>::const_reference
10.439 + operator[](Edge n) const { return container[n.n]; }
10.440 +
10.441 + ///\warning There is no safety check at all!
10.442 + ///Using operator = between maps attached to different graph may
10.443 + ///cause serious problem.
10.444 + ///\todo Is this really so?
10.445 + ///\todo It can copy between different types.
10.446 + const EdgeMap<T>& operator=(const EdgeMap<T> &m)
10.447 + {
10.448 + container = m.container;
10.449 + return *this;
10.450 + }
10.451 + template<typename TT>
10.452 + const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
10.453 + {
10.454 + std::copy(m.container.begin(), m.container.end(), container.begin());
10.455 + return *this;
10.456 + }
10.457 +
10.458 + void update() {} //Useless for DynMaps
10.459 + void update(T a) {} //Useless for DynMaps
10.460 + };
10.461 +
10.462 + };
10.463 +
10.464 + ///Graph for bidirectional edges.
10.465 +
10.466 + ///The purpose of this graph structure is to handle graphs
10.467 + ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
10.468 + ///of oppositely directed edges.
10.469 + ///There is a new edge map type called
10.470 + ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
10.471 + ///that complements this
10.472 + ///feature by
10.473 + ///storing shared values for the edge pairs. The usual
10.474 + ///\ref GraphSkeleton::EdgeMap "EdgeMap"
10.475 + ///can be used
10.476 + ///as well.
10.477 + ///
10.478 + ///The oppositely directed edge can also be obtained easily
10.479 + ///using \ref opposite.
10.480 + ///\warning It shares the similarity with \ref SmartGraph that
10.481 + ///it is not possible to delete edges or nodes from the graph.
10.482 + //\sa \ref SmartGraph.
10.483 +
10.484 + class SymSmartGraph : public SmartGraph
10.485 + {
10.486 + public:
10.487 + template<typename T> class SymEdgeMap;
10.488 + template<typename T> friend class SymEdgeMap;
10.489 +
10.490 + SymSmartGraph() : SmartGraph() { }
10.491 + SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
10.492 + ///Adds a pair of oppositely directed edges to the graph.
10.493 + Edge addEdge(Node u, Node v)
10.494 + {
10.495 + Edge e = SmartGraph::addEdge(u,v);
10.496 + SmartGraph::addEdge(v,u);
10.497 + return e;
10.498 + }
10.499 +
10.500 + ///The oppositely directed edge.
10.501 +
10.502 + ///Returns the oppositely directed
10.503 + ///pair of the edge \c e.
10.504 + Edge opposite(Edge e) const
10.505 + {
10.506 + Edge f;
10.507 + f.idref() = e.idref() - 2*(e.idref()%2) + 1;
10.508 + return f;
10.509 + }
10.510 +
10.511 + ///Common data storage for the edge pairs.
10.512 +
10.513 + ///This map makes it possible to store data shared by the oppositely
10.514 + ///directed pairs of edges.
10.515 + template <typename T> class SymEdgeMap : public DynMapBase<Edge>
10.516 + {
10.517 + std::vector<T> container;
10.518 +
10.519 + public:
10.520 + typedef T ValueType;
10.521 + typedef Edge KeyType;
10.522 +
10.523 + SymEdgeMap(const SymSmartGraph &_G) :
10.524 + DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
10.525 + {
10.526 + static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
10.527 + }
10.528 + SymEdgeMap(const SymSmartGraph &_G,const T &t) :
10.529 + DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
10.530 + {
10.531 + G->dyn_edge_maps.push_back(this);
10.532 + }
10.533 +
10.534 + SymEdgeMap(const SymEdgeMap<T> &m) :
10.535 + DynMapBase<SymEdge>(*m.G), container(m.container)
10.536 + {
10.537 + G->dyn_node_maps.push_back(this);
10.538 + }
10.539 +
10.540 + // template<typename TT> friend class SymEdgeMap;
10.541 +
10.542 + ///\todo It can copy between different types.
10.543 + ///
10.544 +
10.545 + template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
10.546 + DynMapBase<SymEdge>(*m.G)
10.547 + {
10.548 + G->dyn_node_maps.push_back(this);
10.549 + typename std::vector<TT>::const_iterator i;
10.550 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
10.551 + i!=m.container.end();
10.552 + i++)
10.553 + container.push_back(*i);
10.554 + }
10.555 +
10.556 + ~SymEdgeMap()
10.557 + {
10.558 + if(G) {
10.559 + std::vector<DynMapBase<Edge>* >::iterator i;
10.560 + for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
10.561 + i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
10.562 + && *i!=this; ++i) ;
10.563 + //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
10.564 + //A better way to do that: (Is this really important?)
10.565 + if(*i==this) {
10.566 + *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
10.567 + static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
10.568 + }
10.569 + }
10.570 + }
10.571 +
10.572 + void add(const Edge k)
10.573 + {
10.574 + if(!k.idref()%2&&k.idref()/2>=int(container.size()))
10.575 + container.resize(k.idref()/2+1);
10.576 + }
10.577 + void erase(const Edge k) { }
10.578 +
10.579 + void set(Edge n, T a) { container[n.idref()/2]=a; }
10.580 + //T get(Edge n) const { return container[n.idref()/2]; }
10.581 + typename std::vector<T>::reference
10.582 + operator[](Edge n) { return container[n.idref()/2]; }
10.583 + typename std::vector<T>::const_reference
10.584 + operator[](Edge n) const { return container[n.idref()/2]; }
10.585 +
10.586 + ///\warning There is no safety check at all!
10.587 + ///Using operator = between maps attached to different graph may
10.588 + ///cause serious problem.
10.589 + ///\todo Is this really so?
10.590 + ///\todo It can copy between different types.
10.591 + const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
10.592 + {
10.593 + container = m.container;
10.594 + return *this;
10.595 + }
10.596 + template<typename TT>
10.597 + const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
10.598 + {
10.599 + std::copy(m.container.begin(), m.container.end(), container.begin());
10.600 + return *this;
10.601 + }
10.602 +
10.603 + void update() {} //Useless for DynMaps
10.604 + void update(T a) {} //Useless for DynMaps
10.605 +
10.606 + };
10.607 +
10.608 + };
10.609 +
10.610 + /// @}
10.611 +
10.612 +} //namespace hugo
10.613 +
10.614 +
10.615 +
10.616 +
10.617 +#endif //SMART_GRAPH_H
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
11.2 +++ b/src/hugo/time_measure.h Thu May 06 13:21:24 2004 +0000
11.3 @@ -0,0 +1,208 @@
11.4 +// -*- c++ -*-
11.5 +#ifndef HUGO_TIME_MEASURE_H
11.6 +#define HUGO_TIME_MEASURE_H
11.7 +
11.8 +///\ingroup misc
11.9 +///\file
11.10 +///\brief Tools for measuring cpu usage
11.11 +
11.12 +#include <sys/time.h>
11.13 +#include <sys/times.h>
11.14 +#include <fstream>
11.15 +#include <iostream>
11.16 +#include <unistd.h>
11.17 +
11.18 +namespace hugo {
11.19 +
11.20 + /// \addtogroup misc
11.21 + /// @{
11.22 +
11.23 + /// A class to store (cpu)time instances.
11.24 +
11.25 + /// This class stores five time values.
11.26 + /// - a real time
11.27 + /// - a user cpu time
11.28 + /// - a system cpu time
11.29 + /// - a user cpu time of children
11.30 + /// - a system cpu time of children
11.31 + ///
11.32 + /// TimeStamp's can be added to or substracted from each other and
11.33 + /// they can be pushed to a stream.
11.34 + ///
11.35 + /// In most cases, perhaps \ref Timer class is what you want to use instead.
11.36 + ///
11.37 + ///\author Alpar Juttner
11.38 +
11.39 + class TimeStamp
11.40 + {
11.41 + tms ts;
11.42 + double real_time;
11.43 +
11.44 + public:
11.45 +
11.46 + tms &getTms() {return ts;}
11.47 + const tms &getTms() const {return ts;}
11.48 + ///Read the current time values of the process
11.49 + void stamp()
11.50 + {
11.51 + timeval tv;
11.52 + times(&ts);
11.53 + gettimeofday(&tv, 0);real_time=tv.tv_sec+double(tv.tv_usec)/1e6;
11.54 + }
11.55 +
11.56 + /// Constructor initializing with zero
11.57 + TimeStamp()
11.58 + { ts.tms_utime=ts.tms_stime=ts.tms_cutime=ts.tms_cstime=0; real_time=0;}
11.59 + ///Constructor initializing with the current time values of the process
11.60 + TimeStamp(void *) { stamp();}
11.61 +
11.62 + ///
11.63 + TimeStamp &operator+=(const TimeStamp &b)
11.64 + {
11.65 + ts.tms_utime+=b.ts.tms_utime;
11.66 + ts.tms_stime+=b.ts.tms_stime;
11.67 + ts.tms_cutime+=b.ts.tms_cutime;
11.68 + ts.tms_cstime+=b.ts.tms_cstime;
11.69 + real_time+=b.real_time;
11.70 + return *this;
11.71 + }
11.72 + ///
11.73 + TimeStamp operator+(const TimeStamp &b) const
11.74 + {
11.75 + TimeStamp t(*this);
11.76 + return t+=b;
11.77 + }
11.78 + ///
11.79 + TimeStamp &operator-=(const TimeStamp &b)
11.80 + {
11.81 + ts.tms_utime-=b.ts.tms_utime;
11.82 + ts.tms_stime-=b.ts.tms_stime;
11.83 + ts.tms_cutime-=b.ts.tms_cutime;
11.84 + ts.tms_cstime-=b.ts.tms_cstime;
11.85 + real_time-=b.real_time;
11.86 + return *this;
11.87 + }
11.88 + ///
11.89 + TimeStamp operator-(const TimeStamp &b) const
11.90 + {
11.91 + TimeStamp t(*this);
11.92 + return t-=b;
11.93 + }
11.94 +
11.95 + ///The time ellapsed since the last call of stamp()
11.96 + TimeStamp ellapsed() const
11.97 + {
11.98 + TimeStamp t(NULL);
11.99 + return t-*this;
11.100 + }
11.101 +
11.102 + friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
11.103 +
11.104 + ///Gives back the user time of the process
11.105 + double getUserTime() const
11.106 + {
11.107 + return double(ts.tms_utime)/sysconf(_SC_CLK_TCK);
11.108 + }
11.109 + ///Gives back the system time of the process
11.110 + double getSystemTime() const
11.111 + {
11.112 + return double(ts.tms_stime)/sysconf(_SC_CLK_TCK);
11.113 + }
11.114 + ///Gives back the user time of the process' children
11.115 + double getCUserTime() const
11.116 + {
11.117 + return double(ts.tms_cutime)/sysconf(_SC_CLK_TCK);
11.118 + }
11.119 + ///Gives back the user time of the process' children
11.120 + double getCSystemTime() const
11.121 + {
11.122 + return double(ts.tms_cstime)/sysconf(_SC_CLK_TCK);
11.123 + }
11.124 + ///Gives back the real time of the process
11.125 + double getRealTime() const {return real_time;}
11.126 + };
11.127 +
11.128 + ///Class measuring the cpu time and real time usage of the process
11.129 +
11.130 + ///Class measuring the cpu time and real time usage of the process.
11.131 + ///It is quite easy-to-use, here is a short example.
11.132 + ///\code
11.133 + ///int main()
11.134 + ///{
11.135 + ///
11.136 + /// ...
11.137 + ///
11.138 + /// Timer T();
11.139 + /// doSomething();
11.140 + /// cout << T;
11.141 + /// T.reset();
11.142 + /// doSomethingElse();
11.143 + /// cout << T;
11.144 + ///
11.145 + /// ...
11.146 + ///
11.147 + ///}
11.148 + ///\endcode
11.149 + ///
11.150 + ///\todo This shouldn't be Unix (Linux) specific.
11.151 + ///
11.152 + ///\author Alpar Juttner
11.153 + class Timer
11.154 + {
11.155 + TimeStamp start_time;
11.156 +
11.157 + void _reset() {start_time.stamp();}
11.158 +
11.159 + public:
11.160 + ///Constructor. It starts with zero time counters
11.161 + Timer() {_reset();}
11.162 +
11.163 + ///Computes the ellapsed time
11.164 +
11.165 + ///This conversion computes the ellapsed time
11.166 + ///since the construction of \c t or since
11.167 + ///the last \c t.reset().
11.168 + operator TimeStamp ()
11.169 + {
11.170 + TimeStamp t;
11.171 + t.stamp();
11.172 + return t-start_time;
11.173 + }
11.174 +
11.175 + ///Resets the time counters
11.176 + TimeStamp reset()
11.177 + {
11.178 + TimeStamp t(start_time);
11.179 + _reset();
11.180 + return start_time-t;
11.181 + }
11.182 + };
11.183 +
11.184 + ///Prints the time counters
11.185 +
11.186 + ///Prints the time counters in the following form:
11.187 + ///
11.188 + /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
11.189 + ///
11.190 + /// where the values are the
11.191 + /// \li \c u: user cpu time,
11.192 + /// \li \c s: system cpu time,
11.193 + /// \li \c cu: user cpu time of children,
11.194 + /// \li \c cs: system cpu time of children,
11.195 + /// \li \c real: real time.
11.196 + inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
11.197 + {
11.198 + long cls = sysconf(_SC_CLK_TCK);
11.199 + os << "u: " << double(t.getTms().tms_utime)/cls <<
11.200 + "s, s: " << double(t.getTms().tms_stime)/cls <<
11.201 + "s, cu: " << double(t.getTms().tms_cutime)/cls <<
11.202 + "s, cs: " << double(t.getTms().tms_cstime)/cls <<
11.203 + "s, real: " << t.getRealTime() << "s";
11.204 + return os;
11.205 + }
11.206 +
11.207 + /// @}
11.208 +
11.209 +} //namespace hugo
11.210 +
11.211 +#endif //HUGO_TIME_MEASURE_H
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/src/hugo/unionfind.h Thu May 06 13:21:24 2004 +0000
12.3 @@ -0,0 +1,700 @@
12.4 +// -*- c++ -*- //
12.5 +#ifndef HUGO_UNION_FIND_H
12.6 +#define HUGO_UNION_FIND_H
12.7 +
12.8 +//!\ingroup auxdat
12.9 +//!\file
12.10 +//!\brief Union-Find data structures.
12.11 +
12.12 +
12.13 +#include <vector>
12.14 +#include <list>
12.15 +#include <utility>
12.16 +#include <algorithm>
12.17 +
12.18 +#include <invalid.h>
12.19 +
12.20 +namespace hugo {
12.21 +
12.22 + //! \addtogroup auxdat
12.23 + //! @{
12.24 +
12.25 + /**
12.26 + * \brief A \e Union-Find data structure implementation
12.27 + *
12.28 + * The class implements the \e Union-Find data structure.
12.29 + * The union operation uses rank heuristic, while
12.30 + * the find operation uses path compresson.
12.31 + * This is a very simple but efficient implementation, providing
12.32 + * only four methods: join (union), find, insert and size.
12.33 + * For more features see the \ref UnionFindEnum class.
12.34 + *
12.35 + * \pre The elements are automatically added only if the map
12.36 + * given to the constructor was filled with -1's. Otherwise you
12.37 + * need to add all the elements by the \ref insert() method.
12.38 + */
12.39 +
12.40 + template <typename T, typename TIntMap>
12.41 + class UnionFind {
12.42 +
12.43 + public:
12.44 + typedef T ElementType;
12.45 + typedef std::pair<int,int> PairType;
12.46 +
12.47 + private:
12.48 + std::vector<PairType> data;
12.49 + TIntMap& map;
12.50 +
12.51 + public:
12.52 + UnionFind(TIntMap& m) : map(m) {}
12.53 +
12.54 + /**
12.55 + * \brief Returns the index of the element's component.
12.56 + *
12.57 + * The method returns the index of the element's component.
12.58 + * This is an integer between zero and the number of inserted elements.
12.59 + */
12.60 +
12.61 + int find(T a)
12.62 + {
12.63 + int comp0 = map[a];
12.64 + if (comp0 < 0) {
12.65 + return insert(a);
12.66 + }
12.67 + int comp = comp0;
12.68 + int next;
12.69 + while ( (next = data[comp].first) != comp) {
12.70 + comp = next;
12.71 + }
12.72 + while ( (next = data[comp0].first) != comp) {
12.73 + data[comp0].first = comp;
12.74 + comp0 = next;
12.75 + }
12.76 +
12.77 + return comp;
12.78 + }
12.79 +
12.80 + /**
12.81 + * \brief Insert a new element into the structure.
12.82 + *
12.83 + * This method inserts a new element into the data structure.
12.84 + *
12.85 + * It is not required to use this method:
12.86 + * if the map given to the constructor was filled
12.87 + * with -1's then it is called automatically
12.88 + * on the first \ref find or \ref join.
12.89 + *
12.90 + * The method returns the index of the new component.
12.91 + */
12.92 +
12.93 + int insert(T a)
12.94 + {
12.95 + int n = data.size();
12.96 + data.push_back(std::make_pair(n, 1));
12.97 + map.set(a,n);
12.98 + return n;
12.99 + }
12.100 +
12.101 + /**
12.102 + * \brief Joining the components of element \e a and element \e b.
12.103 + *
12.104 + * This is the \e union operation of the Union-Find structure.
12.105 + * Joins the component of elemenent \e a and component of
12.106 + * element \e b. If \e a and \e b are in the same component then
12.107 + * it returns false otherwise it returns true.
12.108 + */
12.109 +
12.110 + bool join(T a, T b)
12.111 + {
12.112 + int ca = find(a);
12.113 + int cb = find(b);
12.114 +
12.115 + if ( ca == cb )
12.116 + return false;
12.117 +
12.118 + if ( data[ca].second > data[cb].second ) {
12.119 + data[cb].first = ca;
12.120 + data[ca].second += data[cb].second;
12.121 + }
12.122 + else {
12.123 + data[ca].first = cb;
12.124 + data[cb].second += data[ca].second;
12.125 + }
12.126 + return true;
12.127 + }
12.128 +
12.129 + /**
12.130 + * \brief Returns the size of the component of element \e a.
12.131 + *
12.132 + * Returns the size of the component of element \e a.
12.133 + */
12.134 +
12.135 + int size(T a)
12.136 + {
12.137 + int ca = find(a);
12.138 + return data[ca].second;
12.139 + }
12.140 +
12.141 + };
12.142 +
12.143 +
12.144 +
12.145 +
12.146 + /*******************************************************/
12.147 +
12.148 +
12.149 +#ifdef DEVELOPMENT_DOCS
12.150 +
12.151 + /**
12.152 + * \brief The auxiliary class for the \ref UnionFindEnum class.
12.153 + *
12.154 + * In the \ref UnionFindEnum class all components are represented as
12.155 + * a std::list.
12.156 + * Items of these lists are UnionFindEnumItem structures.
12.157 + *
12.158 + * The class has four fields:
12.159 + * - T me - the actual element
12.160 + * - IIter parent - the parent of the element in the union-find structure
12.161 + * - int size - the size of the component of the element.
12.162 + * Only valid if the element
12.163 + * is the leader of the component.
12.164 + * - CIter my_class - pointer into the list of components
12.165 + * pointing to the component of the element.
12.166 + * Only valid if the element is the leader of the component.
12.167 + */
12.168 +
12.169 +#endif
12.170 +
12.171 + template <typename T>
12.172 + struct UnionFindEnumItem {
12.173 +
12.174 + typedef std::list<UnionFindEnumItem> ItemList;
12.175 + typedef std::list<ItemList> ClassList;
12.176 + typedef typename ItemList::iterator IIter;
12.177 + typedef typename ClassList::iterator CIter;
12.178 +
12.179 + T me;
12.180 + IIter parent;
12.181 + int size;
12.182 + CIter my_class;
12.183 +
12.184 + UnionFindEnumItem() {}
12.185 + UnionFindEnumItem(const T &_me, CIter _my_class):
12.186 + me(_me), size(1), my_class(_my_class) {}
12.187 + };
12.188 +
12.189 +
12.190 + /**
12.191 + * \brief A \e Union-Find data structure implementation which
12.192 + * is able to enumerate the components.
12.193 + *
12.194 + * The class implements an \e Union-Find data structure
12.195 + * which is able to enumerate the components and the items in
12.196 + * a component. If you don't need this feature then perhaps it's
12.197 + * better to use the \ref UnionFind class which is more efficient.
12.198 + *
12.199 + * The union operation uses rank heuristic, while
12.200 + * the find operation uses path compresson.
12.201 + *
12.202 + * \pre You
12.203 + * need to add all the elements by the \ref insert() method.
12.204 + */
12.205 +
12.206 +
12.207 + template <typename T, template <typename Item> class Map>
12.208 + class UnionFindEnum {
12.209 +
12.210 + typedef std::list<UnionFindEnumItem<T> > ItemList;
12.211 + typedef std::list<ItemList> ClassList;
12.212 + typedef typename ItemList::iterator IIter;
12.213 + typedef typename ItemList::const_iterator IcIter;
12.214 + typedef typename ClassList::iterator CIter;
12.215 + typedef typename ClassList::const_iterator CcIter;
12.216 +
12.217 + public:
12.218 + typedef T ElementType;
12.219 + typedef UnionFindEnumItem<T> ItemType;
12.220 + typedef Map< IIter > MapType;
12.221 +
12.222 + private:
12.223 + MapType& m;
12.224 + ClassList classes;
12.225 +
12.226 + IIter _find(IIter a) const {
12.227 + IIter comp = a;
12.228 + IIter next;
12.229 + while( (next = comp->parent) != comp ) {
12.230 + comp = next;
12.231 + }
12.232 +
12.233 + IIter comp1 = a;
12.234 + while( (next = comp1->parent) != comp ) {
12.235 + comp1->parent = comp->parent;
12.236 + comp1 = next;
12.237 + }
12.238 + return comp;
12.239 + }
12.240 +
12.241 + public:
12.242 + UnionFindEnum(MapType& _m) : m(_m) {}
12.243 +
12.244 +
12.245 + /**
12.246 + * \brief Insert the given element into a new component.
12.247 + *
12.248 + * This method creates a new component consisting only of the
12.249 + * given element.
12.250 + */
12.251 +
12.252 + void insert(const T &a)
12.253 + {
12.254 +
12.255 +
12.256 + classes.push_back(ItemList());
12.257 + CIter aclass = classes.end();
12.258 + --aclass;
12.259 +
12.260 + ItemList &alist = *aclass;
12.261 + alist.push_back(ItemType(a, aclass));
12.262 + IIter ai = alist.begin();
12.263 +
12.264 + ai->parent = ai;
12.265 + m.set(a, ai);
12.266 +
12.267 + }
12.268 +
12.269 + /**
12.270 + * \brief Insert the given element into the component of the others.
12.271 + *
12.272 + * This methods insert the element \e a into the component of the
12.273 + * element \e comp.
12.274 + */
12.275 +
12.276 + void insert(const T &a, const T &comp) {
12.277 +
12.278 + IIter clit = _find(m[comp]);
12.279 + ItemList &c = *clit->my_class;
12.280 + c.push_back(ItemType(a,0));
12.281 + IIter ai = c.end();
12.282 + --ai;
12.283 + ai->parent = clit;
12.284 + m.set(a, ai);
12.285 + ++clit->size;
12.286 + }
12.287 +
12.288 +
12.289 + /**
12.290 + * \brief Find the leader of the component of the given element.
12.291 + *
12.292 + * The method returns the leader of the component of the given element.
12.293 + */
12.294 +
12.295 + T find(const T &a) const {
12.296 + return _find(m[a])->me;
12.297 + }
12.298 +
12.299 +
12.300 + /**
12.301 + * \brief Joining the component of element \e a and element \e b.
12.302 + *
12.303 + * This is the \e union operation of the Union-Find structure.
12.304 + * Joins the component of elemenent \e a and component of
12.305 + * element \e b. If \e a and \e b are in the same component then
12.306 + * returns false else returns true.
12.307 + */
12.308 +
12.309 + bool join(T a, T b) {
12.310 +
12.311 + IIter ca = _find(m[a]);
12.312 + IIter cb = _find(m[b]);
12.313 +
12.314 + if ( ca == cb ) {
12.315 + return false;
12.316 + }
12.317 +
12.318 + if ( ca->size > cb->size ) {
12.319 +
12.320 + cb->parent = ca->parent;
12.321 + ca->size += cb->size;
12.322 +
12.323 + ItemList &alist = *ca->my_class;
12.324 + alist.splice(alist.end(),*cb->my_class);
12.325 +
12.326 + classes.erase(cb->my_class);
12.327 + cb->my_class = 0;
12.328 + }
12.329 + else {
12.330 +
12.331 + ca->parent = cb->parent;
12.332 + cb->size += ca->size;
12.333 +
12.334 + ItemList &blist = *cb->my_class;
12.335 + blist.splice(blist.end(),*ca->my_class);
12.336 +
12.337 + classes.erase(ca->my_class);
12.338 + ca->my_class = 0;
12.339 + }
12.340 +
12.341 + return true;
12.342 + }
12.343 +
12.344 +
12.345 + /**
12.346 + * \brief Returns the size of the component of element \e a.
12.347 + *
12.348 + * Returns the size of the component of element \e a.
12.349 + */
12.350 +
12.351 + int size(const T &a) const {
12.352 + return _find(m[a])->size;
12.353 + }
12.354 +
12.355 +
12.356 + /**
12.357 + * \brief Split up the component of the element.
12.358 + *
12.359 + * Splitting the component of the element into sigleton
12.360 + * components (component of size one).
12.361 + */
12.362 +
12.363 + void split(const T &a) {
12.364 +
12.365 + IIter ca = _find(m[a]);
12.366 +
12.367 + if ( ca->size == 1 )
12.368 + return;
12.369 +
12.370 + CIter aclass = ca->my_class;
12.371 +
12.372 + for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
12.373 + classes.push_back(ItemList());
12.374 + CIter nl = --classes.end();
12.375 + nl->splice(nl->end(), *aclass, curr);
12.376 +
12.377 + curr->size=1;
12.378 + curr->parent=curr;
12.379 + curr->my_class = nl;
12.380 + }
12.381 +
12.382 + ca->size=1;
12.383 + return;
12.384 + }
12.385 +
12.386 +
12.387 + /**
12.388 + * \brief Set the given element to the leader element of its component.
12.389 + *
12.390 + * Set the given element to the leader element of its component.
12.391 + */
12.392 +
12.393 + void makeRep(const T &a) {
12.394 +
12.395 + IIter ia = m[a];
12.396 + IIter la = _find(ia);
12.397 + if (la == ia) return;
12.398 +
12.399 + ia->my_class = la->my_class;
12.400 + la->my_class = 0;
12.401 +
12.402 + ia->size = la->size;
12.403 +
12.404 + CIter l = ia->my_class;
12.405 + l->splice(l->begin(),*l,ia);
12.406 +
12.407 + ia->parent = ia;
12.408 + la->parent = ia;
12.409 + }
12.410 +
12.411 + /**
12.412 + * \brief Move the given element to an other component.
12.413 + *
12.414 + * This method moves the element \e a from its component
12.415 + * to the component of \e comp.
12.416 + * If \e a and \e comp are in the same component then
12.417 + * it returns false otherwise it returns true.
12.418 + */
12.419 +
12.420 + bool move(const T &a, const T &comp) {
12.421 +
12.422 + IIter ai = m[a];
12.423 + IIter lai = _find(ai);
12.424 + IIter clit = _find(m[comp]);
12.425 +
12.426 + if (lai == clit)
12.427 + return false;
12.428 +
12.429 + ItemList &c = *clit->my_class;
12.430 +
12.431 + bool is_leader = (lai == ai);
12.432 + bool singleton = false;
12.433 +
12.434 + if (is_leader) {
12.435 + ++lai;
12.436 + }
12.437 +
12.438 + c.splice(c.end(), *lai->my_class, ai);
12.439 +
12.440 + if (is_leader) {
12.441 + if (ai->size == 1) {
12.442 + classes.erase(ai->my_class);
12.443 + singleton = true;
12.444 + }
12.445 + else {
12.446 + lai->size = ai->size;
12.447 + lai->my_class = ai->my_class;
12.448 + }
12.449 + }
12.450 + if (!singleton) {
12.451 + for (IIter i = lai; i != lai->my_class->end(); ++i)
12.452 + i->parent = lai;
12.453 + --lai->size;
12.454 + }
12.455 +
12.456 + ai->parent = clit;
12.457 + ai->my_class = 0;
12.458 + ++clit->size;
12.459 +
12.460 + return true;
12.461 + }
12.462 +
12.463 +
12.464 + /**
12.465 + * \brief Remove the given element from the structure.
12.466 + *
12.467 + * Remove the given element from the structure.
12.468 + *
12.469 + * Removes the element from its component and if the component becomes
12.470 + * empty then removes that component from the component list.
12.471 + */
12.472 + void erase(const T &a) {
12.473 +
12.474 + IIter ma = m[a];
12.475 + if (ma == 0) return;
12.476 +
12.477 + IIter la = _find(ma);
12.478 + if (la == ma) {
12.479 + if (ma -> size == 1){
12.480 + classes.erase(ma->my_class);
12.481 + m.set(a,0);
12.482 + return;
12.483 + }
12.484 + ++la;
12.485 + la->size = ma->size;
12.486 + la->my_class = ma->my_class;
12.487 + }
12.488 +
12.489 + for (IIter i = la; i != la->my_class->end(); ++i) {
12.490 + i->parent = la;
12.491 + }
12.492 +
12.493 + la->size--;
12.494 + la->my_class->erase(ma);
12.495 + m.set(a,0);
12.496 + }
12.497 +
12.498 + /**
12.499 + * \brief Removes the component of the given element from the structure.
12.500 + *
12.501 + * Removes the component of the given element from the structure.
12.502 + */
12.503 +
12.504 + void eraseClass(const T &a) {
12.505 + IIter ma = m[a];
12.506 + if (ma == 0) return;
12.507 +# ifdef DEBUG
12.508 + CIter c = _find(ma)->my_class;
12.509 + for (IIter i=c->begin(); i!=c->end(); ++i)
12.510 + m.set(i->me, 0);
12.511 +# endif
12.512 + classes.erase(_find(ma)->my_class);
12.513 + }
12.514 +
12.515 +
12.516 + class ClassIt {
12.517 + friend class UnionFindEnum;
12.518 +
12.519 + CcIter i;
12.520 + public:
12.521 + ClassIt(Invalid): i(0) {}
12.522 + ClassIt() {}
12.523 +
12.524 + operator const T& () const {
12.525 + ItemList const &ll = *i;
12.526 + return (ll.begin())->me; }
12.527 + bool operator == (ClassIt it) const {
12.528 + return (i == it.i);
12.529 + }
12.530 + bool operator != (ClassIt it) const {
12.531 + return (i != it.i);
12.532 + }
12.533 + bool operator < (ClassIt it) const {
12.534 + return (i < it.i);
12.535 + }
12.536 +
12.537 + bool valid() const { return i != 0; }
12.538 + private:
12.539 + void first(const ClassList &l) { i = l.begin(); validate(l); }
12.540 + void next(const ClassList &l) {
12.541 + ++i;
12.542 + validate(l);
12.543 + }
12.544 + void validate(const ClassList &l) {
12.545 + if ( i == l.end() )
12.546 + i = 0;
12.547 + }
12.548 + };
12.549 +
12.550 + /**
12.551 + * \brief Sets the iterator to point to the first component.
12.552 + *
12.553 + * Sets the iterator to point to the first component.
12.554 + *
12.555 + * With the \ref first, \ref valid and \ref next methods you can
12.556 + * iterate through the components. For example:
12.557 + * \code
12.558 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
12.559 + * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
12.560 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
12.561 + * for (U.first(iter); U.valid(iter); U.next(iter)) {
12.562 + * // iter is convertible to Graph::Node
12.563 + * cout << iter << endl;
12.564 + * }
12.565 + * \endcode
12.566 + */
12.567 +
12.568 + ClassIt& first(ClassIt& it) const {
12.569 + it.first(classes);
12.570 + return it;
12.571 + }
12.572 +
12.573 + /**
12.574 + * \brief Returns whether the iterator is valid.
12.575 + *
12.576 + * Returns whether the iterator is valid.
12.577 + *
12.578 + * With the \ref first, \ref valid and \ref next methods you can
12.579 + * iterate through the components. See the example here: \ref first.
12.580 + */
12.581 +
12.582 + bool valid(ClassIt const &it) const {
12.583 + return it.valid();
12.584 + }
12.585 +
12.586 + /**
12.587 + * \brief Steps the iterator to the next component.
12.588 + *
12.589 + * Steps the iterator to the next component.
12.590 + *
12.591 + * With the \ref first, \ref valid and \ref next methods you can
12.592 + * iterate through the components. See the example here: \ref first.
12.593 + */
12.594 +
12.595 + ClassIt& next(ClassIt& it) const {
12.596 + it.next(classes);
12.597 + return it;
12.598 + }
12.599 +
12.600 +
12.601 + class ItemIt {
12.602 + friend class UnionFindEnum;
12.603 +
12.604 + IcIter i;
12.605 + const ItemList *l;
12.606 + public:
12.607 + ItemIt(Invalid): i(0) {}
12.608 + ItemIt() {}
12.609 +
12.610 + operator const T& () const { return i->me; }
12.611 + bool operator == (ItemIt it) const {
12.612 + return (i == it.i);
12.613 + }
12.614 + bool operator != (ItemIt it) const {
12.615 + return (i != it.i);
12.616 + }
12.617 + bool operator < (ItemIt it) const {
12.618 + return (i < it.i);
12.619 + }
12.620 +
12.621 + bool valid() const { return i != 0; }
12.622 + private:
12.623 + void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
12.624 + void next() {
12.625 + ++i;
12.626 + validate();
12.627 + }
12.628 + void validate() {
12.629 + if ( i == l->end() )
12.630 + i = 0;
12.631 + }
12.632 + };
12.633 +
12.634 +
12.635 +
12.636 + /**
12.637 + * \brief Sets the iterator to point to the first element of the component.
12.638 + *
12.639 + * \anchor first2
12.640 + * Sets the iterator to point to the first element of the component.
12.641 + *
12.642 + * With the \ref first2 "first", \ref valid2 "valid"
12.643 + * and \ref next2 "next" methods you can
12.644 + * iterate through the elements of a component. For example
12.645 + * (iterating through the component of the node \e node):
12.646 + * \code
12.647 + * Graph::Node node = ...;
12.648 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
12.649 + * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
12.650 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
12.651 + * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
12.652 + * // iiter is convertible to Graph::Node
12.653 + * cout << iiter << endl;
12.654 + * }
12.655 + * \endcode
12.656 + */
12.657 +
12.658 + ItemIt& first(ItemIt& it, const T& a) const {
12.659 + it.first( * _find(m[a])->my_class );
12.660 + return it;
12.661 + }
12.662 +
12.663 + /**
12.664 + * \brief Returns whether the iterator is valid.
12.665 + *
12.666 + * \anchor valid2
12.667 + * Returns whether the iterator is valid.
12.668 + *
12.669 + * With the \ref first2 "first", \ref valid2 "valid"
12.670 + * and \ref next2 "next" methods you can
12.671 + * iterate through the elements of a component.
12.672 + * See the example here: \ref first2 "first".
12.673 + */
12.674 +
12.675 + bool valid(ItemIt const &it) const {
12.676 + return it.valid();
12.677 + }
12.678 +
12.679 + /**
12.680 + * \brief Steps the iterator to the next component.
12.681 + *
12.682 + * \anchor next2
12.683 + * Steps the iterator to the next component.
12.684 + *
12.685 + * With the \ref first2 "first", \ref valid2 "valid"
12.686 + * and \ref next2 "next" methods you can
12.687 + * iterate through the elements of a component.
12.688 + * See the example here: \ref first2 "first".
12.689 + */
12.690 +
12.691 + ItemIt& next(ItemIt& it) const {
12.692 + it.next();
12.693 + return it;
12.694 + }
12.695 +
12.696 + };
12.697 +
12.698 +
12.699 + //! @}
12.700 +
12.701 +} //namespace hugo
12.702 +
12.703 +#endif //HUGO_UNION_FIND_H
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
13.2 +++ b/src/hugo/xy.h Thu May 06 13:21:24 2004 +0000
13.3 @@ -0,0 +1,227 @@
13.4 +// -*- c++ -*-
13.5 +#ifndef HUGO_XY_H
13.6 +#define HUGO_XY_H
13.7 +
13.8 +#include <iostream>
13.9 +
13.10 +///\ingroup misc
13.11 +///\file
13.12 +///\brief A simple two dimensional vector and a bounding box implementation
13.13 +///
13.14 +/// The class \ref hugo::xy "xy" implements
13.15 +///a two dimensional vector with the usual
13.16 +/// operations.
13.17 +///
13.18 +/// The class \ref hugo::BoundingBox "BoundingBox" can be used to determine
13.19 +/// the rectangular bounding box a set of \ref hugo::xy "xy"'s.
13.20 +///
13.21 +///\author Attila Bernath
13.22 +
13.23 +
13.24 +namespace hugo {
13.25 +
13.26 + /// \addtogroup misc
13.27 + /// @{
13.28 +
13.29 + /// A two dimensional vector (plainvector) implementation
13.30 +
13.31 + /// A two dimensional vector (plainvector) implementation
13.32 + ///with the usual vector
13.33 + /// operators.
13.34 + ///
13.35 + ///\author Attila Bernath
13.36 + template<typename T>
13.37 + class xy {
13.38 +
13.39 + public:
13.40 +
13.41 + T x,y;
13.42 +
13.43 + ///Default constructor: both coordinates become 0
13.44 + xy() : x(0), y(0) {}
13.45 +
13.46 + ///Constructing the instance from coordinates
13.47 + xy(T a, T b) : x(a), y(b) { }
13.48 +
13.49 +
13.50 + ///Gives back the square of the norm of the vector
13.51 + T normSquare(){
13.52 + return x*x+y*y;
13.53 + };
13.54 +
13.55 + ///Increments the left hand side by u
13.56 + xy<T>& operator +=(const xy<T>& u){
13.57 + x += u.x;
13.58 + y += u.y;
13.59 + return *this;
13.60 + };
13.61 +
13.62 + ///Decrements the left hand side by u
13.63 + xy<T>& operator -=(const xy<T>& u){
13.64 + x -= u.x;
13.65 + y -= u.y;
13.66 + return *this;
13.67 + };
13.68 +
13.69 + ///Multiplying the left hand side with a scalar
13.70 + xy<T>& operator *=(const T &u){
13.71 + x *= u;
13.72 + y *= u;
13.73 + return *this;
13.74 + };
13.75 +
13.76 + ///Dividing the left hand side by a scalar
13.77 + xy<T>& operator /=(const T &u){
13.78 + x /= u;
13.79 + y /= u;
13.80 + return *this;
13.81 + };
13.82 +
13.83 + ///Returns the scalar product of two vectors
13.84 + T operator *(const xy<T>& u){
13.85 + return x*u.x+y*u.y;
13.86 + };
13.87 +
13.88 + ///Returns the sum of two vectors
13.89 + xy<T> operator+(const xy<T> &u) const {
13.90 + xy<T> b=*this;
13.91 + return b+=u;
13.92 + };
13.93 +
13.94 + ///Returns the difference of two vectors
13.95 + xy<T> operator-(const xy<T> &u) const {
13.96 + xy<T> b=*this;
13.97 + return b-=u;
13.98 + };
13.99 +
13.100 + ///Returns a vector multiplied by a scalar
13.101 + xy<T> operator*(const T &u) const {
13.102 + xy<T> b=*this;
13.103 + return b*=u;
13.104 + };
13.105 +
13.106 + ///Returns a vector divided by a scalar
13.107 + xy<T> operator/(const T &u) const {
13.108 + xy<T> b=*this;
13.109 + return b/=u;
13.110 + };
13.111 +
13.112 + ///Testing equality
13.113 + bool operator==(const xy<T> &u){
13.114 + return (x==u.x) && (y==u.y);
13.115 + };
13.116 +
13.117 + ///Testing inequality
13.118 + bool operator!=(xy u){
13.119 + return (x!=u.x) || (y!=u.y);
13.120 + };
13.121 +
13.122 + };
13.123 +
13.124 + ///Reading a plainvector from a stream
13.125 + template<typename T>
13.126 + inline
13.127 + std::istream& operator>>(std::istream &is, xy<T> &z)
13.128 + {
13.129 +
13.130 + is >> z.x >> z.y;
13.131 + return is;
13.132 + }
13.133 +
13.134 + ///Outputting a plainvector to a stream
13.135 + template<typename T>
13.136 + inline
13.137 + std::ostream& operator<<(std::ostream &os, xy<T> z)
13.138 + {
13.139 + os << "(" << z.x << ", " << z.y << ")";
13.140 + return os;
13.141 + }
13.142 +
13.143 +
13.144 + /// A class to calculate or store the bounding box of plainvectors.
13.145 +
13.146 + /// A class to calculate or store the bounding box of plainvectors.
13.147 + ///
13.148 + ///\author Attila Bernath
13.149 + template<typename T>
13.150 + class BoundingBox {
13.151 + xy<T> bottom_left, top_right;
13.152 + bool _empty;
13.153 + public:
13.154 +
13.155 + ///Default constructor: an empty bounding box
13.156 + BoundingBox() { _empty = true; }
13.157 +
13.158 + ///Constructing the instance from one point
13.159 + BoundingBox(xy<T> a) { bottom_left=top_right=a; _empty = false; }
13.160 +
13.161 + ///Is there any point added
13.162 + bool empty() const {
13.163 + return _empty;
13.164 + }
13.165 +
13.166 + ///Gives back the bottom left corner (if the bounding box is empty, then the return value is not defined)
13.167 + xy<T> bottomLeft() const {
13.168 + return bottom_left;
13.169 + };
13.170 +
13.171 + ///Gives back the top right corner (if the bounding box is empty, then the return value is not defined)
13.172 + xy<T> topRight() const {
13.173 + return top_right;
13.174 + };
13.175 +
13.176 + ///Checks whether a point is inside a bounding box
13.177 + bool inside(const xy<T>& u){
13.178 + if (_empty)
13.179 + return false;
13.180 + else{
13.181 + return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
13.182 + (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
13.183 + }
13.184 + }
13.185 +
13.186 + ///Increments a bounding box with a point
13.187 + BoundingBox& operator +=(const xy<T>& u){
13.188 + if (_empty){
13.189 + bottom_left=top_right=u;
13.190 + _empty = false;
13.191 + }
13.192 + else{
13.193 + if (bottom_left.x > u.x) bottom_left.x = u.x;
13.194 + if (bottom_left.y > u.y) bottom_left.y = u.y;
13.195 + if (top_right.x < u.x) top_right.x = u.x;
13.196 + if (top_right.y < u.y) top_right.y = u.y;
13.197 + }
13.198 + return *this;
13.199 + };
13.200 +
13.201 + ///Sums a bounding box and a point
13.202 + BoundingBox operator +(const xy<T>& u){
13.203 + BoundingBox b = *this;
13.204 + return b += u;
13.205 + };
13.206 +
13.207 + ///Increments a bounding box with an other bounding box
13.208 + BoundingBox& operator +=(const BoundingBox &u){
13.209 + if ( !u.empty() ){
13.210 + *this += u.bottomLeft();
13.211 + *this += u.topRight();
13.212 + }
13.213 + return *this;
13.214 + };
13.215 +
13.216 + ///Sums two bounding boxes
13.217 + BoundingBox operator +(const BoundingBox& u){
13.218 + BoundingBox b = *this;
13.219 + return b += u;
13.220 + };
13.221 +
13.222 + };//class Boundingbox
13.223 +
13.224 +
13.225 + /// @}
13.226 +
13.227 +
13.228 +} //namespace hugo
13.229 +
13.230 +#endif //HUGO_XY_H
14.1 --- a/src/include/bin_heap.h Thu May 06 09:26:23 2004 +0000
14.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
14.3 @@ -1,246 +0,0 @@
14.4 -// -*- C++ -*- //
14.5 -
14.6 -/* FIXME: Copyright ...
14.7 - *
14.8 - * This implementation is heavily based on STL's heap functions and
14.9 - * the similar class by Alpar Juttner in IKTA...
14.10 - */
14.11 -
14.12 -/******
14.13 - *
14.14 - * BinHeap<ItemType, PrioType, ItemIntMap, [PrioCompare]>
14.15 - *
14.16 - * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot
14.17 - * valosit meg.
14.18 - * A kupacban legfolul mindig az a par talalhato, amiben a prioritas a
14.19 - * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
14.20 - * lett keszitve...)
14.21 - *
14.22 - * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni,
14.23 - * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata
14.24 - * miatt, megprobaltunk valami semleges elnevezeseket kitalalni.
14.25 - *
14.26 - * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
14.27 - * az itemekhez egy int-et tud tarolni (ezzel tudom megkeresni az illeto
14.28 - * elemet a kupacban a csokkentes es hasonlo muveletekhez).
14.29 - * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
14.30 - * is elnie kell. (???)
14.31 - *
14.32 - * Ketfele modon hasznalhato:
14.33 - * Lusta mod:
14.34 - * set(Item, Prio) metodussal pakolunk a kupacba,
14.35 - * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
14.36 - * csokkentettunk-e rajta, vagy noveltunk.
14.37 - * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
14.38 - * minden szobajovo kulcs ertekre, -1 -es ertekkel!
14.39 - * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
14.40 - * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
14.41 - * mar kikerult a kupacbol POST_HEAP=-2).
14.42 - * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
14.43 - * meg meg tudja mondani a "legkisebb" prioritasu elemet. De csak nagyjabol,
14.44 - * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
14.45 - *
14.46 - * Kozvetlen mod:
14.47 - * push(Item, Prio) metodussal belerakunk a kupacba (ha az illeto kulcs mar
14.48 - * benn volt, akkor gaz).
14.49 - * increase/decrease(Item i, Prio new_prio) metodusokkal lehet
14.50 - * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt
14.51 - * megbenne a kupacban az illeto elem, vagy nem abba az iranyba valtoztattad
14.52 - * az erteket, amerre mondtad -- gaz).
14.53 - *
14.54 - * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
14.55 - * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
14.56 - * hasznal. :-))
14.57 - *
14.58 - *
14.59 - * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
14.60 - *
14.61 - */
14.62 -
14.63 -
14.64 -#ifndef BIN_HEAP_HH
14.65 -#define BIN_HEAP_HH
14.66 -
14.67 -///\ingroup auxdat
14.68 -///\file
14.69 -///\brief Binary Heap implementation.
14.70 -
14.71 -#include <vector>
14.72 -#include <utility>
14.73 -#include <functional>
14.74 -
14.75 -namespace hugo {
14.76 -
14.77 - /// \addtogroup auxdat
14.78 - /// @{
14.79 -
14.80 - /// A Binary Heap implementation.
14.81 - template <typename Item, typename Prio, typename ItemIntMap,
14.82 - typename Compare = std::less<Prio> >
14.83 - class BinHeap {
14.84 -
14.85 - public:
14.86 - typedef Item ItemType;
14.87 - // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
14.88 - typedef Prio PrioType;
14.89 - typedef std::pair<ItemType,PrioType> PairType;
14.90 - typedef ItemIntMap ItemIntMapType;
14.91 - typedef Compare PrioCompare;
14.92 -
14.93 - /**
14.94 - * Each Item element have a state associated to it. It may be "in heap",
14.95 - * "pre heap" or "post heap". The later two are indifferent from the
14.96 - * heap's point of view, but may be useful to the user.
14.97 - *
14.98 - * The ItemIntMap _should_ be initialized in such way, that it maps
14.99 - * PRE_HEAP (-1) to any element to be put in the heap...
14.100 - */
14.101 - ///\todo it is used nowhere
14.102 - ///
14.103 - enum state_enum {
14.104 - IN_HEAP = 0,
14.105 - PRE_HEAP = -1,
14.106 - POST_HEAP = -2
14.107 - };
14.108 -
14.109 - private:
14.110 - std::vector<PairType> data;
14.111 - Compare comp;
14.112 - // FIXME: jo ez igy???
14.113 - ItemIntMap &iim;
14.114 -
14.115 - public:
14.116 - BinHeap(ItemIntMap &_iim) : iim(_iim) {}
14.117 - BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
14.118 -
14.119 -
14.120 - int size() const { return data.size(); }
14.121 - bool empty() const { return data.empty(); }
14.122 -
14.123 - private:
14.124 - static int parent(int i) { return (i-1)/2; }
14.125 - static int second_child(int i) { return 2*i+2; }
14.126 - bool less(const PairType &p1, const PairType &p2) const {
14.127 - return comp(p1.second, p2.second);
14.128 - }
14.129 -
14.130 - int bubble_up(int hole, PairType p);
14.131 - int bubble_down(int hole, PairType p, int length);
14.132 -
14.133 - void move(const PairType &p, int i) {
14.134 - data[i] = p;
14.135 - iim.set(p.first, i);
14.136 - }
14.137 -
14.138 - void rmidx(int h) {
14.139 - int n = data.size()-1;
14.140 - if( h>=0 && h<=n ) {
14.141 - iim.set(data[h].first, POST_HEAP);
14.142 - if ( h<n ) {
14.143 - bubble_down(h, data[n], n);
14.144 - }
14.145 - data.pop_back();
14.146 - }
14.147 - }
14.148 -
14.149 - public:
14.150 - void push(const PairType &p) {
14.151 - int n = data.size();
14.152 - data.resize(n+1);
14.153 - bubble_up(n, p);
14.154 - }
14.155 - void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
14.156 -
14.157 - Item top() const {
14.158 - return data[0].first;
14.159 - }
14.160 - /// Returns the prio of the top element of the heap.
14.161 - Prio prio() const {
14.162 - return data[0].second;
14.163 - }
14.164 -
14.165 - void pop() {
14.166 - rmidx(0);
14.167 - }
14.168 -
14.169 - void erase(const Item &i) {
14.170 - rmidx(iim[i]);
14.171 - }
14.172 -
14.173 - Prio operator[](const Item &i) const {
14.174 - int idx = iim[i];
14.175 - return data[idx].second;
14.176 - }
14.177 -
14.178 - void set(const Item &i, const Prio &p) {
14.179 - int idx = iim[i];
14.180 - if( idx < 0 ) {
14.181 - push(i,p);
14.182 - }
14.183 - else if( comp(p, data[idx].second) ) {
14.184 - bubble_up(idx, PairType(i,p));
14.185 - }
14.186 - else {
14.187 - bubble_down(idx, PairType(i,p), data.size());
14.188 - }
14.189 - }
14.190 -
14.191 - void decrease(const Item &i, const Prio &p) {
14.192 - int idx = iim[i];
14.193 - bubble_up(idx, PairType(i,p));
14.194 - }
14.195 - void increase(const Item &i, const Prio &p) {
14.196 - int idx = iim[i];
14.197 - bubble_down(idx, PairType(i,p), data.size());
14.198 - }
14.199 -
14.200 - state_enum state(const Item &i) const {
14.201 - int s = iim[i];
14.202 - if( s>=0 )
14.203 - s=0;
14.204 - return state_enum(s);
14.205 - }
14.206 -
14.207 - }; // class BinHeap
14.208 -
14.209 -
14.210 - template <typename K, typename V, typename M, typename C>
14.211 - int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
14.212 - int par = parent(hole);
14.213 - while( hole>0 && less(p,data[par]) ) {
14.214 - move(data[par],hole);
14.215 - hole = par;
14.216 - par = parent(hole);
14.217 - }
14.218 - move(p, hole);
14.219 - return hole;
14.220 - }
14.221 -
14.222 - template <typename K, typename V, typename M, typename C>
14.223 - int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
14.224 - int child = second_child(hole);
14.225 - while(child < length) {
14.226 - if( less(data[child-1], data[child]) ) {
14.227 - --child;
14.228 - }
14.229 - if( !less(data[child], p) )
14.230 - goto ok;
14.231 - move(data[child], hole);
14.232 - hole = child;
14.233 - child = second_child(hole);
14.234 - }
14.235 - child--;
14.236 - if( child<length && less(data[child], p) ) {
14.237 - move(data[child], hole);
14.238 - hole=child;
14.239 - }
14.240 - ok:
14.241 - move(p, hole);
14.242 - return hole;
14.243 - }
14.244 -
14.245 - ///@}
14.246 -
14.247 -} // namespace hugo
14.248 -
14.249 -#endif // BIN_HEAP_HH
15.1 --- a/src/include/dijkstra.h Thu May 06 09:26:23 2004 +0000
15.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
15.3 @@ -1,208 +0,0 @@
15.4 -// -*- C++ -*-
15.5 -#ifndef HUGO_DIJKSTRA_H
15.6 -#define HUGO_DIJKSTRA_H
15.7 -
15.8 -///\ingroup galgs
15.9 -///\file
15.10 -///\brief Dijkstra algorithm.
15.11 -
15.12 -#include <bin_heap.h>
15.13 -#include <invalid.h>
15.14 -
15.15 -namespace hugo {
15.16 -
15.17 -/// \addtogroup galgs
15.18 -/// @{
15.19 -
15.20 - ///%Dijkstra algorithm class.
15.21 -
15.22 - ///This class provides an efficient implementation of %Dijkstra algorithm.
15.23 - ///The edge lengths are passed to the algorithm using a
15.24 - ///\ref ReadMapSkeleton "readable map",
15.25 - ///so it is easy to change it to any kind of length.
15.26 - ///
15.27 - ///The type of the length is determined by the \c ValueType of the length map.
15.28 - ///
15.29 - ///It is also possible to change the underlying priority heap.
15.30 - ///
15.31 - ///\param Graph The graph type the algorithm runs on.
15.32 - ///\param LengthMap This read-only
15.33 - ///EdgeMap
15.34 - ///determines the
15.35 - ///lengths of the edges. It is read once for each edge, so the map
15.36 - ///may involve in relatively time consuming process to compute the edge
15.37 - ///length if it is necessary. The default map type is
15.38 - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
15.39 - ///\param Heap The heap type used by the %Dijkstra
15.40 - ///algorithm. The default
15.41 - ///is using \ref BinHeap "binary heap".
15.42 - ///
15.43 - ///\author Jacint Szabo
15.44 -#ifdef DOXYGEN
15.45 - template <typename Graph,
15.46 - typename LengthMap,
15.47 - typename Heap>
15.48 -#else
15.49 - template <typename Graph,
15.50 - typename LengthMap=typename Graph::template EdgeMap<int>,
15.51 - template <class,class,class,class> class Heap = BinHeap >
15.52 -#endif
15.53 - class Dijkstra{
15.54 - public:
15.55 - typedef typename Graph::Node Node;
15.56 - typedef typename Graph::NodeIt NodeIt;
15.57 - typedef typename Graph::Edge Edge;
15.58 - typedef typename Graph::OutEdgeIt OutEdgeIt;
15.59 -
15.60 - typedef typename LengthMap::ValueType ValueType;
15.61 - typedef typename Graph::template NodeMap<Edge> PredMap;
15.62 - typedef typename Graph::template NodeMap<Node> PredNodeMap;
15.63 - typedef typename Graph::template NodeMap<ValueType> DistMap;
15.64 -
15.65 - private:
15.66 - const Graph& G;
15.67 - const LengthMap& length;
15.68 - PredMap predecessor;
15.69 - PredNodeMap pred_node;
15.70 - DistMap distance;
15.71 -
15.72 - public :
15.73 -
15.74 - Dijkstra(const Graph& _G, const LengthMap& _length) :
15.75 - G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
15.76 -
15.77 - void run(Node s);
15.78 -
15.79 - ///The distance of a node from the root.
15.80 -
15.81 - ///Returns the distance of a node from the root.
15.82 - ///\pre \ref run() must be called before using this function.
15.83 - ///\warning If node \c v in unreachable from the root the return value
15.84 - ///of this funcion is undefined.
15.85 - ValueType dist(Node v) const { return distance[v]; }
15.86 -
15.87 - ///Returns the previous edge of the shortest path tree.
15.88 -
15.89 - ///For a node \c v it returns the previous edge of the shortest path tree,
15.90 - ///i.e. it returns the last edge from a shortest path from the root to \c
15.91 - ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
15.92 - ///shortest path tree used here is equal to the shortest path tree used in
15.93 - ///\ref predNode(Node v). \pre \ref run() must be called before using
15.94 - ///this function.
15.95 - Edge pred(Node v) const { return predecessor[v]; }
15.96 -
15.97 - ///Returns the previous node of the shortest path tree.
15.98 -
15.99 - ///For a node \c v it returns the previous node of the shortest path tree,
15.100 - ///i.e. it returns the last but one node from a shortest path from the
15.101 - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
15.102 - ///\c v=s. The shortest path tree used here is equal to the shortest path
15.103 - ///tree used in \ref pred(Node v). \pre \ref run() must be called before
15.104 - ///using this function.
15.105 - Node predNode(Node v) const { return pred_node[v]; }
15.106 -
15.107 - ///Returns a reference to the NodeMap of distances.
15.108 -
15.109 - ///Returns a reference to the NodeMap of distances. \pre \ref run() must
15.110 - ///be called before using this function.
15.111 - const DistMap &distMap() const { return distance;}
15.112 -
15.113 - ///Returns a reference to the shortest path tree map.
15.114 -
15.115 - ///Returns a reference to the NodeMap of the edges of the
15.116 - ///shortest path tree.
15.117 - ///\pre \ref run() must be called before using this function.
15.118 - const PredMap &predMap() const { return predecessor;}
15.119 -
15.120 - ///Returns a reference to the map of nodes of shortest paths.
15.121 -
15.122 - ///Returns a reference to the NodeMap of the last but one nodes of the
15.123 - ///shortest path tree.
15.124 - ///\pre \ref run() must be called before using this function.
15.125 - const PredNodeMap &predNodeMap() const { return pred_node;}
15.126 -
15.127 - ///Checks if a node is reachable from the root.
15.128 -
15.129 - ///Returns \c true if \c v is reachable from the root.
15.130 - ///\warning the root node is reported to be unreached!
15.131 - ///\todo Is this what we want?
15.132 - ///\pre \ref run() must be called before using this function.
15.133 - ///
15.134 - bool reached(Node v) { return G.valid(predecessor[v]); }
15.135 -
15.136 - };
15.137 -
15.138 -
15.139 - // **********************************************************************
15.140 - // IMPLEMENTATIONS
15.141 - // **********************************************************************
15.142 -
15.143 - ///Runs %Dijkstra algorithm from node the root.
15.144 -
15.145 - ///This method runs the %Dijkstra algorithm from a root node \c s
15.146 - ///in order to
15.147 - ///compute the
15.148 - ///shortest path to each node. The algorithm computes
15.149 - ///- The shortest path tree.
15.150 - ///- The distance of each node from the root.
15.151 - template <typename Graph, typename LengthMap,
15.152 - template<class,class,class,class> class Heap >
15.153 - void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
15.154 -
15.155 - NodeIt u;
15.156 - for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
15.157 - predecessor.set(u,INVALID);
15.158 - pred_node.set(u,INVALID);
15.159 - }
15.160 -
15.161 - typename Graph::template NodeMap<int> heap_map(G,-1);
15.162 -
15.163 - typedef Heap<Node, ValueType, typename Graph::template NodeMap<int>,
15.164 - std::less<ValueType> >
15.165 - HeapType;
15.166 -
15.167 - HeapType heap(heap_map);
15.168 -
15.169 - heap.push(s,0);
15.170 -
15.171 - while ( !heap.empty() ) {
15.172 -
15.173 - Node v=heap.top();
15.174 - ValueType oldvalue=heap[v];
15.175 - heap.pop();
15.176 - distance.set(v, oldvalue);
15.177 -
15.178 - { //FIXME this bracket is for e to be local
15.179 - OutEdgeIt e;
15.180 - for(G.first(e, v);
15.181 - G.valid(e); G.next(e)) {
15.182 - Node w=G.bNode(e);
15.183 -
15.184 - switch(heap.state(w)) {
15.185 - case HeapType::PRE_HEAP:
15.186 - heap.push(w,oldvalue+length[e]);
15.187 - predecessor.set(w,e);
15.188 - pred_node.set(w,v);
15.189 - break;
15.190 - case HeapType::IN_HEAP:
15.191 - if ( oldvalue+length[e] < heap[w] ) {
15.192 - heap.decrease(w, oldvalue+length[e]);
15.193 - predecessor.set(w,e);
15.194 - pred_node.set(w,v);
15.195 - }
15.196 - break;
15.197 - case HeapType::POST_HEAP:
15.198 - break;
15.199 - }
15.200 - }
15.201 - } //FIXME tis bracket
15.202 - }
15.203 - }
15.204 -
15.205 -/// @}
15.206 -
15.207 -} //END OF NAMESPACE HUGO
15.208 -
15.209 -#endif
15.210 -
15.211 -
16.1 --- a/src/include/dimacs.h Thu May 06 09:26:23 2004 +0000
16.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
16.3 @@ -1,206 +0,0 @@
16.4 -// -*- c++ -*-
16.5 -#ifndef HUGO_DIMACS_H
16.6 -#define HUGO_DIMACS_H
16.7 -
16.8 -#include <iostream>
16.9 -#include <string>
16.10 -#include <vector>
16.11 -#include <maps.h>
16.12 -
16.13 -/// \file
16.14 -/// \brief Dimacs file format reader.
16.15 -
16.16 -namespace hugo {
16.17 -
16.18 - /// Dimacs flow file format reader function.
16.19 -
16.20 - /// This function reads a flow instance from dimacs flow format.
16.21 - /// At the beginning \c g is cleared by \c g.clear().
16.22 - /// If the data coming from \c is is a max flow problem instance, then
16.23 - /// \c s and \c t will be respectively the source and target nodes
16.24 - /// and \c capacity will contain the edge capacities.
16.25 - /// If the data is a shortest path problem instance then \c s will be the
16.26 - /// source node and \c capacity will contain the edge lengths.
16.27 - ///
16.28 - ///\author Marton Makai
16.29 - template<typename Graph, typename CapacityMap>
16.30 - void readDimacsMaxFlow(std::istream& is, Graph &g,
16.31 - typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
16.32 - g.clear();
16.33 - int cap;
16.34 - char d;
16.35 - std::string problem;
16.36 - char c;
16.37 - int i, j;
16.38 - std::string str;
16.39 - int n, m;
16.40 - typename Graph::Edge e;
16.41 - std::vector<typename Graph::Node> nodes;
16.42 - while (is>>c) {
16.43 - switch (c) {
16.44 - case 'c': //comment
16.45 - getline(is, str);
16.46 - break;
16.47 - case 'p': //problem definition
16.48 - is >> problem >> n >> m;
16.49 - getline(is, str);
16.50 - nodes.resize(n+1);
16.51 - for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
16.52 - break;
16.53 - case 'n': //node definition
16.54 - if (problem=="sp") { //shortest path problem
16.55 - is >> i;
16.56 - getline(is, str);
16.57 - s=nodes[i];
16.58 - }
16.59 - if (problem=="max") { //max flow problem
16.60 - is >> i >> d;
16.61 - getline(is, str);
16.62 - if (d=='s') s=nodes[i];
16.63 - if (d=='t') t=nodes[i];
16.64 - }
16.65 - break;
16.66 - case 'a':
16.67 - is >> i >> j >> cap;
16.68 - getline(is, str);
16.69 - e=g.addEdge(nodes[i], nodes[j]);
16.70 - capacity.update();
16.71 - capacity.set(e, cap);
16.72 - break;
16.73 - }
16.74 - }
16.75 - }
16.76 -
16.77 - /// matching problem
16.78 - template<typename Graph>
16.79 - void readDimacs(std::istream& is, Graph &g) {
16.80 - typename Graph::Node u;
16.81 - NullMap<typename Graph::Edge, int> n;
16.82 - readDimacs(is, g, n, u, u, n);
16.83 - std::cout<<"igen en.";
16.84 - }
16.85 -
16.86 - /// sg problem
16.87 - template<typename Graph, typename CapacityMap>
16.88 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
16.89 - typename Graph::Node u;
16.90 - NullMap<typename Graph::Edge, int> n;
16.91 - readDimacs(is, g, capacity, u, u, n);
16.92 - }
16.93 -
16.94 - /// shortest path problem
16.95 - template<typename Graph, typename CapacityMap>
16.96 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
16.97 - typename Graph::Node &s) {
16.98 - NullMap<typename Graph::Edge, int> n;
16.99 - readDimacs(is, g, capacity, s, s, n);
16.100 - }
16.101 -
16.102 - /// max flow problem
16.103 - template<typename Graph, typename CapacityMap>
16.104 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
16.105 - typename Graph::Node &s, typename Graph::Node &t) {
16.106 - NullMap<typename Graph::Edge, int> n;
16.107 - readDimacs(is, g, capacity, s, t, n);
16.108 - }
16.109 -
16.110 - /// min cost flow problem
16.111 - template<typename Graph, typename CapacityMap, typename CostMap>
16.112 - void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity,
16.113 - typename Graph::Node &s, typename Graph::Node &t,
16.114 - CostMap& cost) {
16.115 - g.clear();
16.116 - typename CapacityMap::ValueType _cap;
16.117 - typename CostMap::ValueType _cost;
16.118 - char d;
16.119 - std::string problem;
16.120 - char c;
16.121 - int i, j;
16.122 - std::string str;
16.123 - int n, m;
16.124 - typename Graph::Edge e;
16.125 - std::vector<typename Graph::Node> nodes;
16.126 - while (is>>c) {
16.127 - switch (c) {
16.128 - case 'c': //comment
16.129 - getline(is, str);
16.130 - break;
16.131 - case 'p': //problem definition
16.132 - is >> problem >> n >> m;
16.133 - getline(is, str);
16.134 - nodes.resize(n+1);
16.135 - for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
16.136 - break;
16.137 - case 'n': //node definition
16.138 - if (problem=="sp") { //shortest path problem
16.139 - is >> i;
16.140 - getline(is, str);
16.141 - s=nodes[i];
16.142 - }
16.143 - if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
16.144 - is >> i >> d;
16.145 - getline(is, str);
16.146 - if (d=='s') s=nodes[i];
16.147 - if (d=='t') t=nodes[i];
16.148 - }
16.149 - break;
16.150 - case 'a':
16.151 - if ( problem == "mat" ) {
16.152 - is >> i >> j;
16.153 - getline(is, str);
16.154 - g.addEdge(nodes[i], nodes[j]);
16.155 - }
16.156 - if ( problem == "max" || problem == "sp") {
16.157 - is >> i >> j >> _cap;
16.158 - getline(is, str);
16.159 - e=g.addEdge(nodes[i], nodes[j]);
16.160 - capacity.update();
16.161 - capacity.set(e, _cap);
16.162 - }
16.163 - if ( problem == "min" ) {
16.164 - is >> i >> j >> _cap >> _cost;
16.165 - getline(is, str);
16.166 - e=g.addEdge(nodes[i], nodes[j]);
16.167 - capacity.update();
16.168 - capacity.set(e, _cap);
16.169 - cost.update();
16.170 - cost.set(e, _cost);
16.171 - }
16.172 - break;
16.173 - }
16.174 - }
16.175 - }
16.176 -
16.177 -
16.178 -
16.179 - /// write matching problem
16.180 - template<typename Graph>
16.181 - void writeDimacs(std::ostream& os, const Graph &g) {
16.182 - typedef typename Graph::NodeIt NodeIt;
16.183 - typedef typename Graph::EdgeIt EdgeIt;
16.184 -
16.185 - typename Graph::template NodeMap<int> nodes(g);
16.186 -
16.187 - os << "c matching problem" << std::endl;
16.188 -
16.189 - int i=1;
16.190 - NodeIt v;
16.191 - for(g.first(v); g.valid(v); g.next(v)) {
16.192 - nodes.set(v, i);
16.193 - ++i;
16.194 - }
16.195 -
16.196 - os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
16.197 -
16.198 - EdgeIt e;
16.199 - for(g.first(e); g.valid(e); g.next(e)) {
16.200 - os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl;
16.201 - }
16.202 -
16.203 - }
16.204 -
16.205 -
16.206 -
16.207 -} //namespace hugo
16.208 -
16.209 -#endif //HUGO_DIMACS_H
17.1 --- a/src/include/error.h Thu May 06 09:26:23 2004 +0000
17.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
17.3 @@ -1,68 +0,0 @@
17.4 -// -*- C++ -*- //
17.5 -
17.6 -#ifndef HUGO_ERROR_H
17.7 -#define HUGO_ERROR_H
17.8 -
17.9 -//! \ingroup misc
17.10 -//! \file
17.11 -//! \brief Basic error handling (signaling) routines.
17.12 -
17.13 -#include <exception>
17.14 -#include <string>
17.15 -#include <sstream>
17.16 -
17.17 -
17.18 -namespace hugo {
17.19 -
17.20 - /**
17.21 - * \brief Generic exception class.
17.22 - *
17.23 - * \todo Do we need this?
17.24 - *
17.25 - * \todo Don't we need different kind of exceptions for different kind
17.26 - * of errors?
17.27 - * Shouldn't we use \<stdexcept\> instead?
17.28 - */
17.29 - class Exception : public std::exception {
17.30 - protected:
17.31 - std::ostringstream buf;
17.32 - public:
17.33 - Exception() {}
17.34 - explicit Exception(const std::string &s) { buf << s; }
17.35 - Exception(const Exception &e) : std::exception() {
17.36 - buf << e.buf.str();
17.37 - }
17.38 - virtual ~Exception() throw() {}
17.39 -
17.40 - virtual const char* what() const throw() {
17.41 - return buf.str().c_str();
17.42 - }
17.43 -
17.44 - Exception& operator<<(std::string const& s) { buf << s; return *this; }
17.45 - Exception& operator<<(char const *s) { buf << s; return *this; }
17.46 - Exception& operator<<(int i) { buf << i; return *this; }
17.47 - };
17.48 -
17.49 - /**
17.50 - * \brief Generic error signaling function.
17.51 - *
17.52 - * \todo Do we really need this? Is it helpful?
17.53 - */
17.54 - inline void fault(const std::string &msg) {
17.55 - throw Exception(msg);
17.56 - }
17.57 -
17.58 - /**
17.59 - * \brief Macro for mark not yet implemented features.
17.60 - *
17.61 - * \todo Is this the right place for this? It should be used only in
17.62 - * modules under development.
17.63 - */
17.64 -
17.65 -# define FIXME(msg) \
17.66 - do { throw ::hugo::Exception() << "FIXME: " msg " (in: " \
17.67 - __FILE__ ", " << __LINE__ << ")"; \
17.68 - } while(false)
17.69 -
17.70 -}
17.71 -#endif // HUGO_ERROR_H
18.1 --- a/src/include/fib_heap.h Thu May 06 09:26:23 2004 +0000
18.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
18.3 @@ -1,500 +0,0 @@
18.4 -// -*- C++ -*-
18.5 -
18.6 -#ifndef HUGO_FIB_HEAP_H
18.7 -#define HUGO_FIB_HEAP_H
18.8 -
18.9 -///\ingroup auxdat
18.10 -///\file
18.11 -///\brief Fibonacci Heap implementation.
18.12 -
18.13 -#include <vector>
18.14 -#include <functional>
18.15 -#include <math.h>
18.16 -
18.17 -namespace hugo {
18.18 -
18.19 - /// \addtogroup auxdat
18.20 - /// @{
18.21 -
18.22 - /// An implementation of the Fibonacci Heap.
18.23 -
18.24 - /**
18.25 - This class implements the \e Fibonacci \e heap data structure. A \e heap
18.26 - is a data structure for storing items with specified values called \e
18.27 - priorities, such that finding the item with minimum priority with respect
18.28 - to \e Compare is efficient. In a heap one can change the priority of an
18.29 - item, add or erase an item, etc.
18.30 -
18.31 - The methods \ref increase and \ref erase are not efficient in a Fibonacci
18.32 - heap. In case of many calls to these operations, it is better to use a
18.33 - \e binary \e heap.
18.34 -
18.35 - \param Item The type of the items to be stored.
18.36 - \param Prio The type of the priority of the items.
18.37 - \param ItemIntMap A read and writable Item int map, for the usage of
18.38 - the heap.
18.39 - \param Compare A class for the comparison of the priorities. The
18.40 - default is \c std::less<Prio>.
18.41 -
18.42 - */
18.43 -
18.44 -#ifdef DOXYGEN
18.45 - template <typename Item,
18.46 - typename Prio,
18.47 - typename ItemIntMap,
18.48 - typename Compare>
18.49 -#else
18.50 - template <typename Item,
18.51 - typename Prio,
18.52 - typename ItemIntMap,
18.53 - typename Compare = std::less<Prio> >
18.54 -#endif
18.55 - class FibHeap {
18.56 - public:
18.57 - typedef Prio PrioType;
18.58 -
18.59 - private:
18.60 - class store;
18.61 -
18.62 - std::vector<store> container;
18.63 - int minimum;
18.64 - ItemIntMap &iimap;
18.65 - Compare comp;
18.66 - int num_items;
18.67 -
18.68 - public:
18.69 - enum state_enum {
18.70 - IN_HEAP = 0,
18.71 - PRE_HEAP = -1,
18.72 - POST_HEAP = -2
18.73 - };
18.74 -
18.75 - FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
18.76 - FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
18.77 - iimap(_iimap), comp(_comp), num_items() {}
18.78 -
18.79 - ///The number of items stored in the heap.
18.80 -
18.81 - /**
18.82 - Returns the number of items stored in the heap.
18.83 - */
18.84 - int size() const { return num_items; }
18.85 -
18.86 - ///Checks if the heap stores no items.
18.87 -
18.88 - /**
18.89 - Returns \c true iff the heap stores no items.
18.90 - */
18.91 - bool empty() const { return num_items==0; }
18.92 -
18.93 - ///\c item gets to the heap with priority \c value independently if \c item was already there.
18.94 -
18.95 - /**
18.96 - This method calls \ref push(\c item, \c value) if \c item is not
18.97 - stored in the heap and it calls \ref decrease(\c item, \c value) or
18.98 - \ref increase(\c item, \c value) otherwise.
18.99 - */
18.100 - void set (Item const item, PrioType const value);
18.101 -
18.102 - ///Adds \c item to the heap with priority \c value.
18.103 -
18.104 - /**
18.105 - Adds \c item to the heap with priority \c value.
18.106 - \pre \c item must not be stored in the heap.
18.107 - */
18.108 - void push (Item const item, PrioType const value);
18.109 -
18.110 -
18.111 - ///Returns the item having the minimum priority w.r.t. Compare.
18.112 -
18.113 - /**
18.114 - This method returns the item having the minimum priority w.r.t. Compare.
18.115 - \pre The heap must be nonempty.
18.116 - */
18.117 - Item top() const { return container[minimum].name; }
18.118 -
18.119 -
18.120 - ///Returns the minimum priority w.r.t. Compare.
18.121 -
18.122 - /**
18.123 - It returns the minimum priority w.r.t. Compare.
18.124 - \pre The heap must be nonempty.
18.125 - */
18.126 - PrioType prio() const { return container[minimum].prio; }
18.127 -
18.128 -
18.129 - ///Returns the priority of \c item.
18.130 -
18.131 - /**
18.132 - It returns the priority of \c item.
18.133 - \pre \c item must be in the heap.
18.134 - */
18.135 - PrioType& operator[](const Item& item) {
18.136 - return container[iimap[item]].prio;
18.137 - }
18.138 -
18.139 - ///Returns the priority of \c item.
18.140 -
18.141 - /**
18.142 - It returns the priority of \c item.
18.143 - \pre \c item must be in the heap.
18.144 - */
18.145 - const PrioType& operator[](const Item& item) const {
18.146 - return container[iimap[item]].prio;
18.147 - }
18.148 -
18.149 -
18.150 - ///Deletes the item with minimum priority w.r.t. Compare.
18.151 -
18.152 - /**
18.153 - This method deletes the item with minimum priority w.r.t.
18.154 - Compare from the heap.
18.155 - \pre The heap must be non-empty.
18.156 - */
18.157 - void pop();
18.158 -
18.159 - ///Deletes \c item from the heap.
18.160 -
18.161 - /**
18.162 - This method deletes \c item from the heap, if \c item was already
18.163 - stored in the heap. It is quite inefficient in Fibonacci heaps.
18.164 - */
18.165 - void erase (const Item& item);
18.166 -
18.167 - ///Decreases the priority of \c item to \c value.
18.168 -
18.169 - /**
18.170 - This method decreases the priority of \c item to \c value.
18.171 - \pre \c item must be stored in the heap with priority at least \c
18.172 - value w.r.t. Compare.
18.173 - */
18.174 - void decrease (Item item, PrioType const value);
18.175 -
18.176 -
18.177 - ///Increases the priority of \c item to \c value.
18.178 -
18.179 - /**
18.180 - This method sets the priority of \c item to \c value. Though
18.181 - there is no precondition on the priority of \c item, this
18.182 - method should be used only if there is a need to really \e increase
18.183 - (w.r.t. Compare) the priority of \c item, because this
18.184 - method is inefficient.
18.185 - */
18.186 - void increase (Item item, PrioType const value) {
18.187 - erase(item);
18.188 - push(item, value);
18.189 - }
18.190 -
18.191 -
18.192 - ///Tells if \c item is in, was already in, or has never been in the heap.
18.193 -
18.194 - /**
18.195 - This method returns PRE_HEAP if \c item has never been in the
18.196 - heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
18.197 - otherwise. In the latter case it is possible that \c item will
18.198 - get back to the heap again.
18.199 - */
18.200 - state_enum state(const Item &item) const {
18.201 - int i=iimap[item];
18.202 - if( i>=0 ) {
18.203 - if ( container[i].in ) i=0;
18.204 - else i=-2;
18.205 - }
18.206 - return state_enum(i);
18.207 - }
18.208 -
18.209 - private:
18.210 -
18.211 - void balance();
18.212 - void makeroot(int c);
18.213 - void cut(int a, int b);
18.214 - void cascade(int a);
18.215 - void fuse(int a, int b);
18.216 - void unlace(int a);
18.217 -
18.218 -
18.219 - class store {
18.220 - friend class FibHeap;
18.221 -
18.222 - Item name;
18.223 - int parent;
18.224 - int left_neighbor;
18.225 - int right_neighbor;
18.226 - int child;
18.227 - int degree;
18.228 - bool marked;
18.229 - bool in;
18.230 - PrioType prio;
18.231 -
18.232 - store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
18.233 - };
18.234 - };
18.235 -
18.236 -
18.237 -
18.238 - // **********************************************************************
18.239 - // IMPLEMENTATIONS
18.240 - // **********************************************************************
18.241 -
18.242 - template <typename Item, typename Prio, typename ItemIntMap,
18.243 - typename Compare>
18.244 - void FibHeap<Item, Prio, ItemIntMap, Compare>::set
18.245 - (Item const item, PrioType const value)
18.246 - {
18.247 - int i=iimap[item];
18.248 - if ( i >= 0 && container[i].in ) {
18.249 - if ( comp(value, container[i].prio) ) decrease(item, value);
18.250 - if ( comp(container[i].prio, value) ) increase(item, value);
18.251 - } else push(item, value);
18.252 - }
18.253 -
18.254 - template <typename Item, typename Prio, typename ItemIntMap,
18.255 - typename Compare>
18.256 - void FibHeap<Item, Prio, ItemIntMap, Compare>::push
18.257 - (Item const item, PrioType const value) {
18.258 - int i=iimap[item];
18.259 - if ( i < 0 ) {
18.260 - int s=container.size();
18.261 - iimap.set( item, s );
18.262 - store st;
18.263 - st.name=item;
18.264 - container.push_back(st);
18.265 - i=s;
18.266 - } else {
18.267 - container[i].parent=container[i].child=-1;
18.268 - container[i].degree=0;
18.269 - container[i].in=true;
18.270 - container[i].marked=false;
18.271 - }
18.272 -
18.273 - if ( num_items ) {
18.274 - container[container[minimum].right_neighbor].left_neighbor=i;
18.275 - container[i].right_neighbor=container[minimum].right_neighbor;
18.276 - container[minimum].right_neighbor=i;
18.277 - container[i].left_neighbor=minimum;
18.278 - if ( comp( value, container[minimum].prio) ) minimum=i;
18.279 - } else {
18.280 - container[i].right_neighbor=container[i].left_neighbor=i;
18.281 - minimum=i;
18.282 - }
18.283 - container[i].prio=value;
18.284 - ++num_items;
18.285 - }
18.286 -
18.287 - template <typename Item, typename Prio, typename ItemIntMap,
18.288 - typename Compare>
18.289 - void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
18.290 - /*The first case is that there are only one root.*/
18.291 - if ( container[minimum].left_neighbor==minimum ) {
18.292 - container[minimum].in=false;
18.293 - if ( container[minimum].degree!=0 ) {
18.294 - makeroot(container[minimum].child);
18.295 - minimum=container[minimum].child;
18.296 - balance();
18.297 - }
18.298 - } else {
18.299 - int right=container[minimum].right_neighbor;
18.300 - unlace(minimum);
18.301 - container[minimum].in=false;
18.302 - if ( container[minimum].degree > 0 ) {
18.303 - int left=container[minimum].left_neighbor;
18.304 - int child=container[minimum].child;
18.305 - int last_child=container[child].left_neighbor;
18.306 -
18.307 - makeroot(child);
18.308 -
18.309 - container[left].right_neighbor=child;
18.310 - container[child].left_neighbor=left;
18.311 - container[right].left_neighbor=last_child;
18.312 - container[last_child].right_neighbor=right;
18.313 - }
18.314 - minimum=right;
18.315 - balance();
18.316 - } // the case where there are more roots
18.317 - --num_items;
18.318 - }
18.319 -
18.320 -
18.321 - template <typename Item, typename Prio, typename ItemIntMap,
18.322 - typename Compare>
18.323 - void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
18.324 - (const Item& item) {
18.325 - int i=iimap[item];
18.326 -
18.327 - if ( i >= 0 && container[i].in ) {
18.328 - if ( container[i].parent!=-1 ) {
18.329 - int p=container[i].parent;
18.330 - cut(i,p);
18.331 - cascade(p);
18.332 - }
18.333 - minimum=i; //As if its prio would be -infinity
18.334 - pop();
18.335 - }
18.336 - }
18.337 -
18.338 - template <typename Item, typename Prio, typename ItemIntMap,
18.339 - typename Compare>
18.340 - void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
18.341 - (Item item, PrioType const value) {
18.342 - int i=iimap[item];
18.343 - container[i].prio=value;
18.344 - int p=container[i].parent;
18.345 -
18.346 - if ( p!=-1 && comp(value, container[p].prio) ) {
18.347 - cut(i,p);
18.348 - cascade(p);
18.349 - }
18.350 - if ( comp(value, container[minimum].prio) ) minimum=i;
18.351 - }
18.352 -
18.353 -
18.354 - template <typename Item, typename Prio, typename ItemIntMap,
18.355 - typename Compare>
18.356 - void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
18.357 -
18.358 - int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
18.359 -
18.360 - std::vector<int> A(maxdeg,-1);
18.361 -
18.362 - /*
18.363 - *Recall that now minimum does not point to the minimum prio element.
18.364 - *We set minimum to this during balance().
18.365 - */
18.366 - int anchor=container[minimum].left_neighbor;
18.367 - int next=minimum;
18.368 - bool end=false;
18.369 -
18.370 - do {
18.371 - int active=next;
18.372 - if ( anchor==active ) end=true;
18.373 - int d=container[active].degree;
18.374 - next=container[active].right_neighbor;
18.375 -
18.376 - while (A[d]!=-1) {
18.377 - if( comp(container[active].prio, container[A[d]].prio) ) {
18.378 - fuse(active,A[d]);
18.379 - } else {
18.380 - fuse(A[d],active);
18.381 - active=A[d];
18.382 - }
18.383 - A[d]=-1;
18.384 - ++d;
18.385 - }
18.386 - A[d]=active;
18.387 - } while ( !end );
18.388 -
18.389 -
18.390 - while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
18.391 - int s=minimum;
18.392 - int m=minimum;
18.393 - do {
18.394 - if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
18.395 - s=container[s].right_neighbor;
18.396 - } while ( s != m );
18.397 - }
18.398 -
18.399 - template <typename Item, typename Prio, typename ItemIntMap,
18.400 - typename Compare>
18.401 - void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
18.402 - (int c) {
18.403 - int s=c;
18.404 - do {
18.405 - container[s].parent=-1;
18.406 - s=container[s].right_neighbor;
18.407 - } while ( s != c );
18.408 - }
18.409 -
18.410 -
18.411 - template <typename Item, typename Prio, typename ItemIntMap,
18.412 - typename Compare>
18.413 - void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
18.414 - (int a, int b) {
18.415 - /*
18.416 - *Replacing a from the children of b.
18.417 - */
18.418 - --container[b].degree;
18.419 -
18.420 - if ( container[b].degree !=0 ) {
18.421 - int child=container[b].child;
18.422 - if ( child==a )
18.423 - container[b].child=container[child].right_neighbor;
18.424 - unlace(a);
18.425 - }
18.426 -
18.427 -
18.428 - /*Lacing a to the roots.*/
18.429 - int right=container[minimum].right_neighbor;
18.430 - container[minimum].right_neighbor=a;
18.431 - container[a].left_neighbor=minimum;
18.432 - container[a].right_neighbor=right;
18.433 - container[right].left_neighbor=a;
18.434 -
18.435 - container[a].parent=-1;
18.436 - container[a].marked=false;
18.437 - }
18.438 -
18.439 -
18.440 - template <typename Item, typename Prio, typename ItemIntMap,
18.441 - typename Compare>
18.442 - void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
18.443 - (int a)
18.444 - {
18.445 - if ( container[a].parent!=-1 ) {
18.446 - int p=container[a].parent;
18.447 -
18.448 - if ( container[a].marked==false ) container[a].marked=true;
18.449 - else {
18.450 - cut(a,p);
18.451 - cascade(p);
18.452 - }
18.453 - }
18.454 - }
18.455 -
18.456 -
18.457 - template <typename Item, typename Prio, typename ItemIntMap,
18.458 - typename Compare>
18.459 - void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
18.460 - (int a, int b) {
18.461 - unlace(b);
18.462 -
18.463 - /*Lacing b under a.*/
18.464 - container[b].parent=a;
18.465 -
18.466 - if (container[a].degree==0) {
18.467 - container[b].left_neighbor=b;
18.468 - container[b].right_neighbor=b;
18.469 - container[a].child=b;
18.470 - } else {
18.471 - int child=container[a].child;
18.472 - int last_child=container[child].left_neighbor;
18.473 - container[child].left_neighbor=b;
18.474 - container[b].right_neighbor=child;
18.475 - container[last_child].right_neighbor=b;
18.476 - container[b].left_neighbor=last_child;
18.477 - }
18.478 -
18.479 - ++container[a].degree;
18.480 -
18.481 - container[b].marked=false;
18.482 - }
18.483 -
18.484 -
18.485 - /*
18.486 - *It is invoked only if a has siblings.
18.487 - */
18.488 - template <typename Item, typename Prio, typename ItemIntMap,
18.489 - typename Compare>
18.490 - void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
18.491 - (int a) {
18.492 - int leftn=container[a].left_neighbor;
18.493 - int rightn=container[a].right_neighbor;
18.494 - container[leftn].right_neighbor=rightn;
18.495 - container[rightn].left_neighbor=leftn;
18.496 - }
18.497 -
18.498 - ///@}
18.499 -
18.500 -} //namespace hugo
18.501 -
18.502 -#endif //HUGO_FIB_HEAP_H
18.503 -
19.1 --- a/src/include/invalid.h Thu May 06 09:26:23 2004 +0000
19.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
19.3 @@ -1,38 +0,0 @@
19.4 -// -*- mode:C++ -*-
19.5 -
19.6 -#ifndef HUGO_INVALID_H
19.7 -#define HUGO_INVALID_H
19.8 -
19.9 -///\file
19.10 -///\brief Definition of INVALID.
19.11 -
19.12 -namespace hugo {
19.13 -
19.14 - /// Dummy type to make it easier to make invalid iterators.
19.15 -
19.16 - /// See \ref INVALID, how to use it.
19.17 -
19.18 - struct Invalid {
19.19 - public:
19.20 - bool operator==(Invalid) { return true; }
19.21 - bool operator!=(Invalid) { return false; }
19.22 - bool operator< (Invalid) { return false; }
19.23 - };
19.24 -
19.25 - /// Invalid iterators.
19.26 -
19.27 - /// \ref Invalid is a global type that converts to each iterator
19.28 - /// in such a way that the value of the target iterator will be invalid.
19.29 -
19.30 - // It is also used to convert the \c INVALID constant to the
19.31 - // node iterator that makes is possible to write
19.32 -
19.33 - //extern Invalid INVALID;
19.34 -
19.35 - //const Invalid &INVALID = *(Invalid *)0;
19.36 - const Invalid INVALID = Invalid();
19.37 -
19.38 -} //namespace hugo
19.39 -
19.40 -#endif
19.41 -
20.1 --- a/src/include/maps.h Thu May 06 09:26:23 2004 +0000
20.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
20.3 @@ -1,129 +0,0 @@
20.4 -// -*- C++ -*- //
20.5 -#ifndef HUGO_MAPS_H
20.6 -#define HUGO_MAPS_H
20.7 -
20.8 -///\file
20.9 -///\brief Miscellaneous property maps
20.10 -///
20.11 -///\todo This file has the same name as the concept file in skeletons,
20.12 -/// and this is not easily detectable in docs...
20.13 -
20.14 -#include <map>
20.15 -
20.16 -namespace hugo {
20.17 -
20.18 - /// Null map. (aka DoNothingMap)
20.19 -
20.20 - /// If you have to provide a map only for its type definitions,
20.21 - /// or if you have to provide a writable map, but will not use the
20.22 - /// data written to it...
20.23 - template<typename K, typename T>
20.24 - class NullMap
20.25 - {
20.26 - public:
20.27 - typedef K KeyType;
20.28 - typedef T ValueType;
20.29 -
20.30 - T operator[](const K&) const { return T(); }
20.31 - void set(const K&, const T&) {}
20.32 - ///\bug when update is removed from map concepts by being dynamic
20.33 - ///stuffs, this line have to be removed.
20.34 - void update() { }
20.35 - };
20.36 -
20.37 -
20.38 - /// Constant map.
20.39 -
20.40 - /// This is a readable map which assignes a specified value to each key.
20.41 - /// In other aspects it is equivalent to the \ref NullMap
20.42 - template<typename K, typename T>
20.43 - class ConstMap
20.44 - {
20.45 - T v;
20.46 - public:
20.47 - typedef K KeyType;
20.48 - typedef T ValueType;
20.49 -
20.50 - ConstMap() {}
20.51 - ConstMap(const T &_v) : v(_v) {}
20.52 -
20.53 - T operator[](const K&) const { return v; }
20.54 - void set(const K&, const T&) {}
20.55 -
20.56 - template<typename T1>
20.57 - struct rebind {
20.58 - typedef ConstMap<K,T1> other;
20.59 - };
20.60 -
20.61 - template<typename T1>
20.62 - ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {}
20.63 - };
20.64 -
20.65 -
20.66 -
20.67 - /// \c std::map wrapper
20.68 -
20.69 - /// This is essentially a wrapper for \c std::map. With addition that
20.70 - /// you can specify a default value different from \c ValueType() .
20.71 - ///
20.72 - /// \todo Provide allocator parameter...
20.73 - template <typename Key, typename T, typename Compare = std::less<Key> >
20.74 - class StdMap : public std::map<Key,T,Compare> {
20.75 - typedef std::map<Key,T,Compare> parent;
20.76 - T v;
20.77 - typedef typename parent::value_type PairType;
20.78 -
20.79 - public:
20.80 - typedef Key KeyType;
20.81 - typedef T ValueType;
20.82 - typedef T& ReferenceType;
20.83 - typedef const T& ConstReferenceType;
20.84 -
20.85 -
20.86 - StdMap() : v() {}
20.87 - /// Constructor with specified default value
20.88 - StdMap(const T& _v) : v(_v) {}
20.89 -
20.90 - /// \brief Constructs the map from an appropriate std::map.
20.91 - ///
20.92 - /// \warning Inefficient: copies the content of \c m !
20.93 - StdMap(const parent &m) : parent(m) {}
20.94 - /// \brief Constructs the map from an appropriate std::map, and explicitly
20.95 - /// specifies a default value.
20.96 - ///
20.97 - /// \warning Inefficient: copies the content of \c m !
20.98 - StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
20.99 -
20.100 - template<typename T1, typename Comp1>
20.101 - StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) {
20.102 - //FIXME;
20.103 - }
20.104 -
20.105 - ReferenceType operator[](const Key &k) {
20.106 - return insert(PairType(k,v)).first -> second;
20.107 - }
20.108 - ConstReferenceType operator[](const Key &k) const {
20.109 - typename parent::iterator i = lower_bound(k);
20.110 - if (i == parent::end() || parent::key_comp()(k, (*i).first))
20.111 - return v;
20.112 - return (*i).second;
20.113 - }
20.114 - void set(const Key &k, const T &t) {
20.115 - parent::operator[](k) = t;
20.116 - }
20.117 -
20.118 - /// Changes the default value of the map.
20.119 - /// \return Returns the previous default value.
20.120 - ///
20.121 - /// \warning The value of some keys (which has alredy been queried, but
20.122 - /// the value has been unchanged from the default) may change!
20.123 - T setDefault(const T &_v) { T old=v; v=_v; return old; }
20.124 -
20.125 - template<typename T1>
20.126 - struct rebind {
20.127 - typedef StdMap<Key,T1,Compare> other;
20.128 - };
20.129 - };
20.130 -
20.131 -}
20.132 -#endif // HUGO_MAPS_H
21.1 --- a/src/include/skeletons/graph.h Thu May 06 09:26:23 2004 +0000
21.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
21.3 @@ -1,399 +0,0 @@
21.4 -// -*- c++ -*-
21.5 -#ifndef HUGO_SKELETON_GRAPH_H
21.6 -#define HUGO_SKELETON_GRAPH_H
21.7 -
21.8 -///\file
21.9 -///\brief Declaration of GraphSkeleton.
21.10 -
21.11 -#include <invalid.h>
21.12 -
21.13 -/// The namespace of HugoLib
21.14 -namespace hugo {
21.15 -
21.16 - // @defgroup empty_graph The GraphSkeleton class
21.17 - // @{
21.18 -
21.19 - /// An empty graph class.
21.20 -
21.21 - /// This class provides all the common features of a graph structure,
21.22 - /// however completely without implementations and real data structures
21.23 - /// behind the interface.
21.24 - /// All graph algorithms should compile with this class, but it will not
21.25 - /// run properly, of course.
21.26 - ///
21.27 - /// It can be used for checking the interface compatibility,
21.28 - /// or it can serve as a skeleton of a new graph structure.
21.29 - ///
21.30 - /// Also, you will find here the full documentation of a certain graph
21.31 - /// feature, the documentation of a real graph imlementation
21.32 - /// like @ref ListGraph or
21.33 - /// @ref SmartGraph will just refer to this structure.
21.34 - class GraphSkeleton
21.35 - {
21.36 - public:
21.37 - /// Defalult constructor.
21.38 - GraphSkeleton() {}
21.39 - ///Copy consructor.
21.40 -
21.41 - ///\todo It is not clear, what we expect from a copy constructor.
21.42 - ///E.g. How to assign the nodes/edges to each other? What about maps?
21.43 - GraphSkeleton(const GraphSkeleton &G) {}
21.44 -
21.45 - /// The base type of the node iterators.
21.46 -
21.47 - /// This is the base type of each node iterators,
21.48 - /// thus each kind of node iterator will convert to this.
21.49 - class Node {
21.50 - public:
21.51 - /// @warning The default constructor sets the iterator
21.52 - /// to an undefined value.
21.53 - Node() {} //FIXME
21.54 - /// Invalid constructor \& conversion.
21.55 -
21.56 - /// This constructor initializes the iterator to be invalid.
21.57 - /// \sa Invalid for more details.
21.58 -
21.59 - Node(Invalid) {}
21.60 - //Node(const Node &) {}
21.61 -
21.62 - /// Two iterators are equal if and only if they point to the
21.63 - /// same object or both are invalid.
21.64 - bool operator==(Node) const { return true; }
21.65 -
21.66 - /// \sa \ref operator==(Node n)
21.67 - ///
21.68 - bool operator!=(Node) const { return true; }
21.69 -
21.70 - bool operator<(Node) const { return true; }
21.71 - };
21.72 -
21.73 - /// This iterator goes through each node.
21.74 -
21.75 - /// This iterator goes through each node.
21.76 - /// Its usage is quite simple, for example you can count the number
21.77 - /// of nodes in graph \c G of type \c Graph like this:
21.78 - /// \code
21.79 - ///int count=0;
21.80 - ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
21.81 - /// \endcode
21.82 - class NodeIt : public Node {
21.83 - public:
21.84 - /// @warning The default constructor sets the iterator
21.85 - /// to an undefined value.
21.86 - NodeIt() {} //FIXME
21.87 - /// Invalid constructor \& conversion.
21.88 -
21.89 - /// Initialize the iterator to be invalid
21.90 - /// \sa Invalid for more details.
21.91 - NodeIt(Invalid) {}
21.92 - /// Sets the iterator to the first node of \c G.
21.93 - NodeIt(const GraphSkeleton &) {}
21.94 - /// @warning The default constructor sets the iterator
21.95 - /// to an undefined value.
21.96 - NodeIt(const NodeIt &n) : Node(n) {}
21.97 - };
21.98 -
21.99 -
21.100 - /// The base type of the edge iterators.
21.101 - class Edge {
21.102 - public:
21.103 - /// @warning The default constructor sets the iterator
21.104 - /// to an undefined value.
21.105 - Edge() {} //FIXME
21.106 - /// Initialize the iterator to be invalid
21.107 - Edge(Invalid) {}
21.108 - /// Two iterators are equal if and only if they point to the
21.109 - /// same object or both are invalid.
21.110 - bool operator==(Edge) const { return true; }
21.111 - bool operator!=(Edge) const { return true; }
21.112 - bool operator<(Edge) const { return true; }
21.113 - };
21.114 -
21.115 - /// This iterator goes trough the outgoing edges of a node.
21.116 -
21.117 - /// This iterator goes trough the \e outgoing edges of a certain node
21.118 - /// of a graph.
21.119 - /// Its usage is quite simple, for example you can count the number
21.120 - /// of outgoing edges of a node \c n
21.121 - /// in graph \c G of type \c Graph as follows.
21.122 - /// \code
21.123 - ///int count=0;
21.124 - ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
21.125 - /// \endcode
21.126 -
21.127 - class OutEdgeIt : public Edge {
21.128 - public:
21.129 - /// @warning The default constructor sets the iterator
21.130 - /// to an undefined value.
21.131 - OutEdgeIt() {}
21.132 - /// Initialize the iterator to be invalid
21.133 - OutEdgeIt(Invalid) {}
21.134 - /// This constructor sets the iterator to first outgoing edge.
21.135 -
21.136 - /// This constructor set the iterator to the first outgoing edge of
21.137 - /// node
21.138 - ///@param n the node
21.139 - ///@param G the graph
21.140 - OutEdgeIt(const GraphSkeleton &, Node) {}
21.141 - };
21.142 -
21.143 - /// This iterator goes trough the incoming edges of a node.
21.144 -
21.145 - /// This iterator goes trough the \e incoming edges of a certain node
21.146 - /// of a graph.
21.147 - /// Its usage is quite simple, for example you can count the number
21.148 - /// of outgoing edges of a node \c n
21.149 - /// in graph \c G of type \c Graph as follows.
21.150 - /// \code
21.151 - ///int count=0;
21.152 - ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
21.153 - /// \endcode
21.154 -
21.155 - class InEdgeIt : public Edge {
21.156 - public:
21.157 - /// @warning The default constructor sets the iterator
21.158 - /// to an undefined value.
21.159 - InEdgeIt() {}
21.160 - /// Initialize the iterator to be invalid
21.161 - InEdgeIt(Invalid) {}
21.162 - InEdgeIt(const GraphSkeleton &, Node) {}
21.163 - };
21.164 - // class SymEdgeIt : public Edge {};
21.165 -
21.166 - /// This iterator goes through each edge.
21.167 -
21.168 - /// This iterator goes through each edge of a graph.
21.169 - /// Its usage is quite simple, for example you can count the number
21.170 - /// of edges in a graph \c G of type \c Graph as follows:
21.171 - /// \code
21.172 - ///int count=0;
21.173 - ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
21.174 - /// \endcode
21.175 - class EdgeIt : public Edge {
21.176 - public:
21.177 - /// @warning The default constructor sets the iterator
21.178 - /// to an undefined value.
21.179 - EdgeIt() {}
21.180 - /// Initialize the iterator to be invalid
21.181 - EdgeIt(Invalid) {}
21.182 - EdgeIt(const GraphSkeleton &) {}
21.183 - };
21.184 -
21.185 - /// First node of the graph.
21.186 -
21.187 - /// \retval i the first node.
21.188 - /// \return the first node.
21.189 - ///
21.190 - NodeIt &first(NodeIt &i) const { return i;}
21.191 -
21.192 - /// The first incoming edge.
21.193 - InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
21.194 - /// The first outgoing edge.
21.195 - OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
21.196 - // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
21.197 - /// The first edge of the Graph.
21.198 - EdgeIt &first(EdgeIt &i) const { return i;}
21.199 -
21.200 -// Node getNext(Node) const {}
21.201 -// InEdgeIt getNext(InEdgeIt) const {}
21.202 -// OutEdgeIt getNext(OutEdgeIt) const {}
21.203 -// //SymEdgeIt getNext(SymEdgeIt) const {}
21.204 -// EdgeIt getNext(EdgeIt) const {}
21.205 -
21.206 - /// Go to the next node.
21.207 - NodeIt &next(NodeIt &i) const { return i;}
21.208 - /// Go to the next incoming edge.
21.209 - InEdgeIt &next(InEdgeIt &i) const { return i;}
21.210 - /// Go to the next outgoing edge.
21.211 - OutEdgeIt &next(OutEdgeIt &i) const { return i;}
21.212 - //SymEdgeIt &next(SymEdgeIt &) const {}
21.213 - /// Go to the next edge.
21.214 - EdgeIt &next(EdgeIt &i) const { return i;}
21.215 -
21.216 - ///Gives back the head node of an edge.
21.217 - Node head(Edge) const { return INVALID; }
21.218 - ///Gives back the tail node of an edge.
21.219 - Node tail(Edge) const { return INVALID; }
21.220 -
21.221 - // Node aNode(InEdgeIt) const {}
21.222 - // Node aNode(OutEdgeIt) const {}
21.223 - // Node aNode(SymEdgeIt) const {}
21.224 -
21.225 - // Node bNode(InEdgeIt) const {}
21.226 - // Node bNode(OutEdgeIt) const {}
21.227 - // Node bNode(SymEdgeIt) const {}
21.228 -
21.229 - /// Checks if a node iterator is valid
21.230 -
21.231 - ///\todo Maybe, it would be better if iterator converted to
21.232 - ///bool directly, as Jacint prefers.
21.233 - bool valid(const Node&) const { return true;}
21.234 - /// Checks if an edge iterator is valid
21.235 -
21.236 - ///\todo Maybe, it would be better if iterator converted to
21.237 - ///bool directly, as Jacint prefers.
21.238 - bool valid(const Edge&) const { return true;}
21.239 -
21.240 - ///Gives back the \e id of a node.
21.241 -
21.242 - ///\warning Not all graph structures provide this feature.
21.243 - ///
21.244 - int id(const Node&) const { return 0;}
21.245 - ///Gives back the \e id of an edge.
21.246 -
21.247 - ///\warning Not all graph structures provide this feature.
21.248 - ///
21.249 - int id(const Edge&) const { return 0;}
21.250 -
21.251 - //void setInvalid(Node &) const {};
21.252 - //void setInvalid(Edge &) const {};
21.253 -
21.254 - ///Add a new node to the graph.
21.255 -
21.256 - /// \return the new node.
21.257 - ///
21.258 - Node addNode() { return INVALID;}
21.259 - ///Add a new edge to the graph.
21.260 -
21.261 - ///Add a new edge to the graph with tail node \c tail
21.262 - ///and head node \c head.
21.263 - ///\return the new edge.
21.264 - Edge addEdge(Node, Node) { return INVALID;}
21.265 -
21.266 - /// Resets the graph.
21.267 -
21.268 - /// This function deletes all edges and nodes of the graph.
21.269 - /// It also frees the memory allocated to store them.
21.270 - void clear() {}
21.271 -
21.272 - int nodeNum() const { return 0;}
21.273 - int edgeNum() const { return 0;}
21.274 -
21.275 - ///Read/write/reference map of the nodes to type \c T.
21.276 -
21.277 - ///Read/write/reference map of the nodes to type \c T.
21.278 - /// \sa MemoryMapSkeleton
21.279 - /// \todo We may need copy constructor
21.280 - /// \todo We may need conversion from other nodetype
21.281 - /// \todo We may need operator=
21.282 - /// \warning Making maps that can handle bool type (NodeMap<bool>)
21.283 - /// needs extra attention!
21.284 -
21.285 - template<class T> class NodeMap
21.286 - {
21.287 - public:
21.288 - typedef T ValueType;
21.289 - typedef Node KeyType;
21.290 -
21.291 - NodeMap(const GraphSkeleton &) {}
21.292 - NodeMap(const GraphSkeleton &, T) {}
21.293 -
21.294 - template<typename TT> NodeMap(const NodeMap<TT> &) {}
21.295 -
21.296 - /// Sets the value of a node.
21.297 -
21.298 - /// Sets the value associated with node \c i to the value \c t.
21.299 - ///
21.300 - void set(Node, T) {}
21.301 - // Gets the value of a node.
21.302 - //T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary?
21.303 - T &operator[](Node) {return *(T*)0;}
21.304 - const T &operator[](Node) const {return *(T*)0;}
21.305 -
21.306 - /// Updates the map if the graph has been changed
21.307 -
21.308 - /// \todo Do we need this?
21.309 - ///
21.310 - void update() {}
21.311 - void update(T a) {} //FIXME: Is it necessary
21.312 - };
21.313 -
21.314 - ///Read/write/reference map of the edges to type \c T.
21.315 -
21.316 - ///Read/write/reference map of the edges to type \c T.
21.317 - ///It behaves exactly in the same way as \ref NodeMap.
21.318 - /// \sa NodeMap
21.319 - /// \sa MemoryMapSkeleton
21.320 - /// \todo We may need copy constructor
21.321 - /// \todo We may need conversion from other edgetype
21.322 - /// \todo We may need operator=
21.323 - template<class T> class EdgeMap
21.324 - {
21.325 - public:
21.326 - typedef T ValueType;
21.327 - typedef Edge KeyType;
21.328 -
21.329 - EdgeMap(const GraphSkeleton &) {}
21.330 - EdgeMap(const GraphSkeleton &, T ) {}
21.331 -
21.332 - ///\todo It can copy between different types.
21.333 - ///
21.334 - template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
21.335 -
21.336 - void set(Edge, T) {}
21.337 - //T get(Edge) const {return *(T*)0;}
21.338 - T &operator[](Edge) {return *(T*)0;}
21.339 - const T &operator[](Edge) const {return *(T*)0;}
21.340 -
21.341 - void update() {}
21.342 - void update(T a) {} //FIXME: Is it necessary
21.343 - };
21.344 - };
21.345 -
21.346 - /// An empty eraseable graph class.
21.347 -
21.348 - /// This class provides all the common features of an \e eraseable graph
21.349 - /// structure,
21.350 - /// however completely without implementations and real data structures
21.351 - /// behind the interface.
21.352 - /// All graph algorithms should compile with this class, but it will not
21.353 - /// run properly, of course.
21.354 - ///
21.355 - /// \todo This blabla could be replaced by a sepatate description about
21.356 - /// Skeletons.
21.357 - ///
21.358 - /// It can be used for checking the interface compatibility,
21.359 - /// or it can serve as a skeleton of a new graph structure.
21.360 - ///
21.361 - /// Also, you will find here the full documentation of a certain graph
21.362 - /// feature, the documentation of a real graph imlementation
21.363 - /// like @ref ListGraph or
21.364 - /// @ref SmartGraph will just refer to this structure.
21.365 - class EraseableGraphSkeleton : public GraphSkeleton
21.366 - {
21.367 - public:
21.368 - /// Deletes a node.
21.369 - void erase(Node n) {}
21.370 - /// Deletes an edge.
21.371 - void erase(Edge e) {}
21.372 -
21.373 - /// Defalult constructor.
21.374 - EraseableGraphSkeleton() {}
21.375 - ///Copy consructor.
21.376 - EraseableGraphSkeleton(const GraphSkeleton &G) {}
21.377 - };
21.378 -
21.379 -
21.380 - // @}
21.381 -
21.382 -} //namespace hugo
21.383 -
21.384 -
21.385 -
21.386 -// class EmptyBipGraph : public Graph Skeleton
21.387 -// {
21.388 -// class ANode {};
21.389 -// class BNode {};
21.390 -
21.391 -// ANode &next(ANode &) {}
21.392 -// BNode &next(BNode &) {}
21.393 -
21.394 -// ANode &getFirst(ANode &) const {}
21.395 -// BNode &getFirst(BNode &) const {}
21.396 -
21.397 -// enum NodeClass { A = 0, B = 1 };
21.398 -// NodeClass getClass(Node n) {}
21.399 -
21.400 -// }
21.401 -
21.402 -#endif // HUGO_SKELETON_GRAPH_H
22.1 --- a/src/include/skeletons/maps.h Thu May 06 09:26:23 2004 +0000
22.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
22.3 @@ -1,130 +0,0 @@
22.4 -// -*- c++ -*-
22.5 -#ifndef HUGO_MAPSKELETON_H
22.6 -#define HUGO_MAPSKELETON_H
22.7 -
22.8 -///\file
22.9 -///\brief Map concepts checking classes for testing and documenting.
22.10 -
22.11 -namespace hugo {
22.12 -
22.13 - /// The namespace of HUGOlib concepts and concept checking classes
22.14 - namespace skeleton {
22.15 -
22.16 - /// Readable map concept
22.17 - template<typename K, typename T>
22.18 - class ReadableMap
22.19 - {
22.20 - public:
22.21 - /// Map's key type.
22.22 - typedef K KeyType;
22.23 - /// Map's value type. (The type of objects associated with the keys).
22.24 - typedef T ValueType;
22.25 -
22.26 - /// Returns the value associated with a key.
22.27 - ValueType operator[](const KeyType &k) const {return ValueType();}
22.28 -
22.29 - /// Copy contsructor. (optional)
22.30 - ReadableMap(const ReadableMap&) {}
22.31 - /// Assignment operator. (optional)
22.32 - ReadableMap& operator=(const ReadableMap&) {return *this;}
22.33 -
22.34 - ReadableMap() {}
22.35 - };
22.36 -
22.37 -
22.38 - /// Writable map concept
22.39 - template<typename K, typename T>
22.40 - class WritableMap
22.41 - {
22.42 - public:
22.43 - /// Map's key type.
22.44 - typedef K KeyType;
22.45 - /// Map's value type. (The type of objects associated with the keys).
22.46 - typedef T ValueType;
22.47 -
22.48 - /// Sets the value associated with a key.
22.49 - void set(const KeyType &k,const ValueType &t) {}
22.50 -
22.51 - WritableMap() {}
22.52 - };
22.53 -
22.54 - ///Read/Writeable map concept
22.55 - template<typename K, typename T>
22.56 - class ReadWritableMap : public ReadableMap<K,T>,
22.57 - public WritableMap<K,T>
22.58 - {
22.59 - public:
22.60 - /// Map's key type.
22.61 - typedef K KeyType;
22.62 - /// Map's value type. (The type of objects associated with the keys).
22.63 - typedef T ValueType;
22.64 -
22.65 - /// Returns the value associated with a key.
22.66 - ValueType operator[](const KeyType &k) const {return ValueType();}
22.67 - /// Sets the value associated with a key.
22.68 - void set(const KeyType &k,const ValueType &t) {}
22.69 -
22.70 - /// Copy contsructor. (optional)
22.71 - ReadWritableMap(const ReadWritableMap&) {}
22.72 - /// Assignment operator. (optional)
22.73 - ReadWritableMap& operator=(const ReadWritableMap&) {return *this;}
22.74 -
22.75 - /// Facility to define a map with an other value type (optional)
22.76 - template<typename T1>
22.77 - struct rebind {
22.78 - /// The type of a map with the given value type
22.79 - typedef ReadWritableMap<K,T1> other;
22.80 - };
22.81 - /// @brief Constructor that copies all keys from the other map and
22.82 - /// assigns to them a default value (optional)
22.83 - template<typename T1>
22.84 - ReadWritableMap(const ReadWritableMap<K,T1> &map, const ValueType &v) {}
22.85 -
22.86 - ReadWritableMap() {}
22.87 - };
22.88 -
22.89 -
22.90 - ///Dereferable map concept
22.91 - template<typename K, typename T>
22.92 - class DereferableMap : public ReadWritableMap<K,T>
22.93 - {
22.94 - public:
22.95 - /// Map's key type.
22.96 - typedef K KeyType;
22.97 - /// Map's value type. (The type of objects associated with the keys).
22.98 - typedef T ValueType;
22.99 - /// Map's reference type. (Reference to an object associated with a key)
22.100 - typedef ValueType& ReferenceType;
22.101 - /// Map's const reference type.
22.102 - typedef const ValueType& ConstReferenceType;
22.103 -
22.104 - ///Returns a reference to the value associated to a key.
22.105 - ReferenceType operator[](const KeyType &i);
22.106 - ///Returns a const reference to the value associated to a key.
22.107 - ConstReferenceType operator[](const KeyType &i) const;
22.108 - /// Sets the value associated with a key.
22.109 - void set(const KeyType &k,const ValueType &t) { operator[](k)=t; }
22.110 -
22.111 - /// Copy contsructor. (optional)
22.112 - DereferableMap(const DereferableMap&) {}
22.113 - /// Assignment operator. (optional)
22.114 - DereferableMap& operator=(const DereferableMap&) {return *this;}
22.115 -
22.116 - /// Facility to define a map with an other value type (optional)
22.117 - template<typename T1>
22.118 - struct rebind {
22.119 - /// The type of a map with the given value type
22.120 - typedef DereferableMap<K,T1> other;
22.121 - };
22.122 - /// @brief Constructor that copies all keys from the other map and
22.123 - /// assigns to them a default value (optional)
22.124 - template<typename T1>
22.125 - DereferableMap(const DereferableMap<K,T1> &map, const ValueType &v) {}
22.126 -
22.127 - DereferableMap() {}
22.128 - };
22.129 -
22.130 -
22.131 - }
22.132 -}
22.133 -#endif // HUGO_MAPSKELETON_H
23.1 --- a/src/include/smart_graph.h Thu May 06 09:26:23 2004 +0000
23.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
23.3 @@ -1,614 +0,0 @@
23.4 -// -*- mode:C++ -*-
23.5 -
23.6 -#ifndef HUGO_SMART_GRAPH_H
23.7 -#define HUGO_SMART_GRAPH_H
23.8 -
23.9 -///\ingroup graphs
23.10 -///\file
23.11 -///\brief SmartGraph and SymSmartGraph classes.
23.12 -
23.13 -#include <vector>
23.14 -#include <limits.h>
23.15 -
23.16 -#include "invalid.h"
23.17 -
23.18 -namespace hugo {
23.19 -
23.20 -/// \addtogroup graphs
23.21 -/// @{
23.22 - class SymSmartGraph;
23.23 -
23.24 - ///A smart graph class.
23.25 -
23.26 - ///This is a simple and fast graph implementation.
23.27 - ///It is also quite memory efficient, but at the price
23.28 - ///that <b> it does not support node and edge deletion</b>.
23.29 - ///It conforms to the graph interface documented under
23.30 - ///the description of \ref GraphSkeleton.
23.31 - ///\sa \ref GraphSkeleton.
23.32 - ///
23.33 - ///\todo Some member functions could be \c static.
23.34 - ///\author Alpar Juttner
23.35 - class SmartGraph {
23.36 -
23.37 - struct NodeT
23.38 - {
23.39 - int first_in,first_out;
23.40 - NodeT() : first_in(-1), first_out(-1) {}
23.41 - };
23.42 - struct EdgeT
23.43 - {
23.44 - int head, tail, next_in, next_out;
23.45 - //FIXME: is this necessary?
23.46 - EdgeT() : next_in(-1), next_out(-1) {}
23.47 - };
23.48 -
23.49 - std::vector<NodeT> nodes;
23.50 -
23.51 - std::vector<EdgeT> edges;
23.52 -
23.53 - protected:
23.54 -
23.55 - template <typename Key> class DynMapBase
23.56 - {
23.57 - protected:
23.58 - const SmartGraph* G;
23.59 - public:
23.60 - virtual void add(const Key k) = 0;
23.61 - virtual void erase(const Key k) = 0;
23.62 - DynMapBase(const SmartGraph &_G) : G(&_G) {}
23.63 - virtual ~DynMapBase() {}
23.64 - friend class SmartGraph;
23.65 - };
23.66 -
23.67 - public:
23.68 - template <typename T> class EdgeMap;
23.69 - template <typename T> class EdgeMap;
23.70 -
23.71 - class Node;
23.72 - class Edge;
23.73 -
23.74 - // protected:
23.75 - // HELPME:
23.76 - protected:
23.77 - ///\bug It must be public because of SymEdgeMap.
23.78 - ///
23.79 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
23.80 - ///\bug It must be public because of SymEdgeMap.
23.81 - ///
23.82 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
23.83 -
23.84 - public:
23.85 -
23.86 -
23.87 - class NodeIt;
23.88 - class EdgeIt;
23.89 - class OutEdgeIt;
23.90 - class InEdgeIt;
23.91 -
23.92 - template <typename T> class NodeMap;
23.93 - template <typename T> class EdgeMap;
23.94 -
23.95 - public:
23.96 -
23.97 - SmartGraph() : nodes(), edges() { }
23.98 - SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
23.99 -
23.100 - ~SmartGraph()
23.101 - {
23.102 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
23.103 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
23.104 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
23.105 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
23.106 - }
23.107 -
23.108 - int nodeNum() const { return nodes.size(); } //FIXME: What is this?
23.109 - int edgeNum() const { return edges.size(); } //FIXME: What is this?
23.110 -
23.111 - ///\bug This function does something different than
23.112 - ///its name would suggests...
23.113 - int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
23.114 - ///\bug This function does something different than
23.115 - ///its name would suggests...
23.116 - int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
23.117 -
23.118 - Node tail(Edge e) const { return edges[e.n].tail; }
23.119 - Node head(Edge e) const { return edges[e.n].head; }
23.120 -
23.121 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
23.122 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
23.123 -
23.124 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
23.125 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
23.126 -
23.127 - NodeIt& first(NodeIt& v) const {
23.128 - v=NodeIt(*this); return v; }
23.129 - EdgeIt& first(EdgeIt& e) const {
23.130 - e=EdgeIt(*this); return e; }
23.131 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
23.132 - e=OutEdgeIt(*this,v); return e; }
23.133 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
23.134 - e=InEdgeIt(*this,v); return e; }
23.135 -
23.136 -// template< typename It >
23.137 -// It first() const { It e; first(e); return e; }
23.138 -
23.139 -// template< typename It >
23.140 -// It first(Node v) const { It e; first(e,v); return e; }
23.141 -
23.142 - bool valid(Edge e) const { return e.n!=-1; }
23.143 - bool valid(Node n) const { return n.n!=-1; }
23.144 -
23.145 - ///\deprecated Use
23.146 - ///\code
23.147 - /// e=INVALID;
23.148 - ///\endcode
23.149 - ///instead.
23.150 - void setInvalid(Edge &e) { e.n=-1; }
23.151 - ///\deprecated Use
23.152 - ///\code
23.153 - /// e=INVALID;
23.154 - ///\endcode
23.155 - ///instead.
23.156 - void setInvalid(Node &n) { n.n=-1; }
23.157 -
23.158 - template <typename It> It getNext(It it) const
23.159 - { It tmp(it); return next(tmp); }
23.160 -
23.161 - NodeIt& next(NodeIt& it) const {
23.162 - it.n=(it.n+2)%(nodes.size()+1)-1;
23.163 - return it;
23.164 - }
23.165 - OutEdgeIt& next(OutEdgeIt& it) const
23.166 - { it.n=edges[it.n].next_out; return it; }
23.167 - InEdgeIt& next(InEdgeIt& it) const
23.168 - { it.n=edges[it.n].next_in; return it; }
23.169 - EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
23.170 -
23.171 - int id(Node v) const { return v.n; }
23.172 - int id(Edge e) const { return e.n; }
23.173 -
23.174 - Node addNode() {
23.175 - Node n; n.n=nodes.size();
23.176 - nodes.push_back(NodeT()); //FIXME: Hmmm...
23.177 -
23.178 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
23.179 - i!=dyn_node_maps.end(); ++i) (**i).add(n);
23.180 -
23.181 - return n;
23.182 - }
23.183 -
23.184 - Edge addEdge(Node u, Node v) {
23.185 - Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
23.186 - edges[e.n].tail=u.n; edges[e.n].head=v.n;
23.187 - edges[e.n].next_out=nodes[u.n].first_out;
23.188 - edges[e.n].next_in=nodes[v.n].first_in;
23.189 - nodes[u.n].first_out=nodes[v.n].first_in=e.n;
23.190 -
23.191 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
23.192 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
23.193 -
23.194 - return e;
23.195 - }
23.196 -
23.197 - void clear() {nodes.clear();edges.clear();}
23.198 -
23.199 - class Node {
23.200 - friend class SmartGraph;
23.201 - template <typename T> friend class NodeMap;
23.202 -
23.203 - friend class Edge;
23.204 - friend class OutEdgeIt;
23.205 - friend class InEdgeIt;
23.206 - friend class SymEdge;
23.207 -
23.208 - protected:
23.209 - int n;
23.210 - friend int SmartGraph::id(Node v) const;
23.211 - Node(int nn) {n=nn;}
23.212 - public:
23.213 - Node() {}
23.214 - Node (Invalid) { n=-1; }
23.215 - bool operator==(const Node i) const {return n==i.n;}
23.216 - bool operator!=(const Node i) const {return n!=i.n;}
23.217 - bool operator<(const Node i) const {return n<i.n;}
23.218 - };
23.219 -
23.220 - class NodeIt : public Node {
23.221 - friend class SmartGraph;
23.222 - public:
23.223 - NodeIt() : Node() { }
23.224 - NodeIt(Invalid i) : Node(i) { }
23.225 - NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
23.226 - };
23.227 -
23.228 - class Edge {
23.229 - friend class SmartGraph;
23.230 - template <typename T> friend class EdgeMap;
23.231 -
23.232 - //template <typename T> friend class SymSmartGraph::SymEdgeMap;
23.233 - //friend Edge SymSmartGraph::opposite(Edge) const;
23.234 -
23.235 - friend class Node;
23.236 - friend class NodeIt;
23.237 - protected:
23.238 - int n;
23.239 - friend int SmartGraph::id(Edge e) const;
23.240 -
23.241 - Edge(int nn) {n=nn;}
23.242 - public:
23.243 - Edge() { }
23.244 - Edge (Invalid) { n=-1; }
23.245 - bool operator==(const Edge i) const {return n==i.n;}
23.246 - bool operator!=(const Edge i) const {return n!=i.n;}
23.247 - bool operator<(const Edge i) const {return n<i.n;}
23.248 - ///\bug This is a workaround until somebody tells me how to
23.249 - ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
23.250 - int &idref() {return n;}
23.251 - const int &idref() const {return n;}
23.252 - };
23.253 -
23.254 - class EdgeIt : public Edge {
23.255 - friend class SmartGraph;
23.256 - public:
23.257 - EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
23.258 - EdgeIt (Invalid i) : Edge(i) { }
23.259 - EdgeIt() : Edge() { }
23.260 - ///\bug This is a workaround until somebody tells me how to
23.261 - ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
23.262 - int &idref() {return n;}
23.263 - };
23.264 -
23.265 - class OutEdgeIt : public Edge {
23.266 - friend class SmartGraph;
23.267 - public:
23.268 - OutEdgeIt() : Edge() { }
23.269 - OutEdgeIt (Invalid i) : Edge(i) { }
23.270 -
23.271 - OutEdgeIt(const SmartGraph& G,const Node v)
23.272 - : Edge(G.nodes[v.n].first_out) {}
23.273 - };
23.274 -
23.275 - class InEdgeIt : public Edge {
23.276 - friend class SmartGraph;
23.277 - public:
23.278 - InEdgeIt() : Edge() { }
23.279 - InEdgeIt (Invalid i) : Edge(i) { }
23.280 - InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
23.281 - };
23.282 -
23.283 - template <typename T> class NodeMap : public DynMapBase<Node>
23.284 - {
23.285 - std::vector<T> container;
23.286 -
23.287 - public:
23.288 - typedef T ValueType;
23.289 - typedef Node KeyType;
23.290 -
23.291 - NodeMap(const SmartGraph &_G) :
23.292 - DynMapBase<Node>(_G), container(_G.maxNodeId())
23.293 - {
23.294 - G->dyn_node_maps.push_back(this);
23.295 - }
23.296 - NodeMap(const SmartGraph &_G,const T &t) :
23.297 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
23.298 - {
23.299 - G->dyn_node_maps.push_back(this);
23.300 - }
23.301 -
23.302 - NodeMap(const NodeMap<T> &m) :
23.303 - DynMapBase<Node>(*m.G), container(m.container)
23.304 - {
23.305 - G->dyn_node_maps.push_back(this);
23.306 - }
23.307 -
23.308 - template<typename TT> friend class NodeMap;
23.309 -
23.310 - ///\todo It can copy between different types.
23.311 - ///
23.312 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
23.313 - DynMapBase<Node>(*m.G)
23.314 - {
23.315 - G->dyn_node_maps.push_back(this);
23.316 - typename std::vector<TT>::const_iterator i;
23.317 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
23.318 - i!=m.container.end();
23.319 - i++)
23.320 - container.push_back(*i);
23.321 - }
23.322 - ~NodeMap()
23.323 - {
23.324 - if(G) {
23.325 - std::vector<DynMapBase<Node>* >::iterator i;
23.326 - for(i=G->dyn_node_maps.begin();
23.327 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
23.328 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
23.329 - //A better way to do that: (Is this really important?)
23.330 - if(*i==this) {
23.331 - *i=G->dyn_node_maps.back();
23.332 - G->dyn_node_maps.pop_back();
23.333 - }
23.334 - }
23.335 - }
23.336 -
23.337 - void add(const Node k)
23.338 - {
23.339 - if(k.n>=int(container.size())) container.resize(k.n+1);
23.340 - }
23.341 -
23.342 - void erase(const Node) { }
23.343 -
23.344 - void set(Node n, T a) { container[n.n]=a; }
23.345 - //'T& operator[](Node n)' would be wrong here
23.346 - typename std::vector<T>::reference
23.347 - operator[](Node n) { return container[n.n]; }
23.348 - //'const T& operator[](Node n)' would be wrong here
23.349 - typename std::vector<T>::const_reference
23.350 - operator[](Node n) const { return container[n.n]; }
23.351 -
23.352 - ///\warning There is no safety check at all!
23.353 - ///Using operator = between maps attached to different graph may
23.354 - ///cause serious problem.
23.355 - ///\todo Is this really so?
23.356 - ///\todo It can copy between different types.
23.357 - const NodeMap<T>& operator=(const NodeMap<T> &m)
23.358 - {
23.359 - container = m.container;
23.360 - return *this;
23.361 - }
23.362 - template<typename TT>
23.363 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
23.364 - {
23.365 - std::copy(m.container.begin(), m.container.end(), container.begin());
23.366 - return *this;
23.367 - }
23.368 -
23.369 - void update() {} //Useless for Dynamic Maps
23.370 - void update(T a) {} //Useless for Dynamic Maps
23.371 - };
23.372 -
23.373 - template <typename T> class EdgeMap : public DynMapBase<Edge>
23.374 - {
23.375 - std::vector<T> container;
23.376 -
23.377 - public:
23.378 - typedef T ValueType;
23.379 - typedef Edge KeyType;
23.380 -
23.381 - EdgeMap(const SmartGraph &_G) :
23.382 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
23.383 - {
23.384 - //FIXME: What if there are empty Id's?
23.385 - //FIXME: Can I use 'this' in a constructor?
23.386 - G->dyn_edge_maps.push_back(this);
23.387 - }
23.388 - EdgeMap(const SmartGraph &_G,const T &t) :
23.389 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
23.390 - {
23.391 - G->dyn_edge_maps.push_back(this);
23.392 - }
23.393 - EdgeMap(const EdgeMap<T> &m) :
23.394 - DynMapBase<Edge>(*m.G), container(m.container)
23.395 - {
23.396 - G->dyn_edge_maps.push_back(this);
23.397 - }
23.398 -
23.399 - template<typename TT> friend class EdgeMap;
23.400 -
23.401 - ///\todo It can copy between different types.
23.402 - ///
23.403 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
23.404 - DynMapBase<Edge>(*m.G)
23.405 - {
23.406 - G->dyn_edge_maps.push_back(this);
23.407 - typename std::vector<TT>::const_iterator i;
23.408 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
23.409 - i!=m.container.end();
23.410 - i++)
23.411 - container.push_back(*i);
23.412 - }
23.413 - ~EdgeMap()
23.414 - {
23.415 - if(G) {
23.416 - std::vector<DynMapBase<Edge>* >::iterator i;
23.417 - for(i=G->dyn_edge_maps.begin();
23.418 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
23.419 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
23.420 - //A better way to do that: (Is this really important?)
23.421 - if(*i==this) {
23.422 - *i=G->dyn_edge_maps.back();
23.423 - G->dyn_edge_maps.pop_back();
23.424 - }
23.425 - }
23.426 - }
23.427 -
23.428 - void add(const Edge k)
23.429 - {
23.430 - if(k.n>=int(container.size())) container.resize(k.n+1);
23.431 - }
23.432 - void erase(const Edge) { }
23.433 -
23.434 - void set(Edge n, T a) { container[n.n]=a; }
23.435 - //T get(Edge n) const { return container[n.n]; }
23.436 - typename std::vector<T>::reference
23.437 - operator[](Edge n) { return container[n.n]; }
23.438 - typename std::vector<T>::const_reference
23.439 - operator[](Edge n) const { return container[n.n]; }
23.440 -
23.441 - ///\warning There is no safety check at all!
23.442 - ///Using operator = between maps attached to different graph may
23.443 - ///cause serious problem.
23.444 - ///\todo Is this really so?
23.445 - ///\todo It can copy between different types.
23.446 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
23.447 - {
23.448 - container = m.container;
23.449 - return *this;
23.450 - }
23.451 - template<typename TT>
23.452 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
23.453 - {
23.454 - std::copy(m.container.begin(), m.container.end(), container.begin());
23.455 - return *this;
23.456 - }
23.457 -
23.458 - void update() {} //Useless for DynMaps
23.459 - void update(T a) {} //Useless for DynMaps
23.460 - };
23.461 -
23.462 - };
23.463 -
23.464 - ///Graph for bidirectional edges.
23.465 -
23.466 - ///The purpose of this graph structure is to handle graphs
23.467 - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
23.468 - ///of oppositely directed edges.
23.469 - ///There is a new edge map type called
23.470 - ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
23.471 - ///that complements this
23.472 - ///feature by
23.473 - ///storing shared values for the edge pairs. The usual
23.474 - ///\ref GraphSkeleton::EdgeMap "EdgeMap"
23.475 - ///can be used
23.476 - ///as well.
23.477 - ///
23.478 - ///The oppositely directed edge can also be obtained easily
23.479 - ///using \ref opposite.
23.480 - ///\warning It shares the similarity with \ref SmartGraph that
23.481 - ///it is not possible to delete edges or nodes from the graph.
23.482 - //\sa \ref SmartGraph.
23.483 -
23.484 - class SymSmartGraph : public SmartGraph
23.485 - {
23.486 - public:
23.487 - template<typename T> class SymEdgeMap;
23.488 - template<typename T> friend class SymEdgeMap;
23.489 -
23.490 - SymSmartGraph() : SmartGraph() { }
23.491 - SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
23.492 - ///Adds a pair of oppositely directed edges to the graph.
23.493 - Edge addEdge(Node u, Node v)
23.494 - {
23.495 - Edge e = SmartGraph::addEdge(u,v);
23.496 - SmartGraph::addEdge(v,u);
23.497 - return e;
23.498 - }
23.499 -
23.500 - ///The oppositely directed edge.
23.501 -
23.502 - ///Returns the oppositely directed
23.503 - ///pair of the edge \c e.
23.504 - Edge opposite(Edge e) const
23.505 - {
23.506 - Edge f;
23.507 - f.idref() = e.idref() - 2*(e.idref()%2) + 1;
23.508 - return f;
23.509 - }
23.510 -
23.511 - ///Common data storage for the edge pairs.
23.512 -
23.513 - ///This map makes it possible to store data shared by the oppositely
23.514 - ///directed pairs of edges.
23.515 - template <typename T> class SymEdgeMap : public DynMapBase<Edge>
23.516 - {
23.517 - std::vector<T> container;
23.518 -
23.519 - public:
23.520 - typedef T ValueType;
23.521 - typedef Edge KeyType;
23.522 -
23.523 - SymEdgeMap(const SymSmartGraph &_G) :
23.524 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
23.525 - {
23.526 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
23.527 - }
23.528 - SymEdgeMap(const SymSmartGraph &_G,const T &t) :
23.529 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
23.530 - {
23.531 - G->dyn_edge_maps.push_back(this);
23.532 - }
23.533 -
23.534 - SymEdgeMap(const SymEdgeMap<T> &m) :
23.535 - DynMapBase<SymEdge>(*m.G), container(m.container)
23.536 - {
23.537 - G->dyn_node_maps.push_back(this);
23.538 - }
23.539 -
23.540 - // template<typename TT> friend class SymEdgeMap;
23.541 -
23.542 - ///\todo It can copy between different types.
23.543 - ///
23.544 -
23.545 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
23.546 - DynMapBase<SymEdge>(*m.G)
23.547 - {
23.548 - G->dyn_node_maps.push_back(this);
23.549 - typename std::vector<TT>::const_iterator i;
23.550 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
23.551 - i!=m.container.end();
23.552 - i++)
23.553 - container.push_back(*i);
23.554 - }
23.555 -
23.556 - ~SymEdgeMap()
23.557 - {
23.558 - if(G) {
23.559 - std::vector<DynMapBase<Edge>* >::iterator i;
23.560 - for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
23.561 - i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
23.562 - && *i!=this; ++i) ;
23.563 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
23.564 - //A better way to do that: (Is this really important?)
23.565 - if(*i==this) {
23.566 - *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
23.567 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
23.568 - }
23.569 - }
23.570 - }
23.571 -
23.572 - void add(const Edge k)
23.573 - {
23.574 - if(!k.idref()%2&&k.idref()/2>=int(container.size()))
23.575 - container.resize(k.idref()/2+1);
23.576 - }
23.577 - void erase(const Edge k) { }
23.578 -
23.579 - void set(Edge n, T a) { container[n.idref()/2]=a; }
23.580 - //T get(Edge n) const { return container[n.idref()/2]; }
23.581 - typename std::vector<T>::reference
23.582 - operator[](Edge n) { return container[n.idref()/2]; }
23.583 - typename std::vector<T>::const_reference
23.584 - operator[](Edge n) const { return container[n.idref()/2]; }
23.585 -
23.586 - ///\warning There is no safety check at all!
23.587 - ///Using operator = between maps attached to different graph may
23.588 - ///cause serious problem.
23.589 - ///\todo Is this really so?
23.590 - ///\todo It can copy between different types.
23.591 - const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
23.592 - {
23.593 - container = m.container;
23.594 - return *this;
23.595 - }
23.596 - template<typename TT>
23.597 - const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
23.598 - {
23.599 - std::copy(m.container.begin(), m.container.end(), container.begin());
23.600 - return *this;
23.601 - }
23.602 -
23.603 - void update() {} //Useless for DynMaps
23.604 - void update(T a) {} //Useless for DynMaps
23.605 -
23.606 - };
23.607 -
23.608 - };
23.609 -
23.610 - /// @}
23.611 -
23.612 -} //namespace hugo
23.613 -
23.614 -
23.615 -
23.616 -
23.617 -#endif //SMART_GRAPH_H
24.1 --- a/src/include/time_measure.h Thu May 06 09:26:23 2004 +0000
24.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
24.3 @@ -1,208 +0,0 @@
24.4 -// -*- c++ -*-
24.5 -#ifndef HUGO_TIME_MEASURE_H
24.6 -#define HUGO_TIME_MEASURE_H
24.7 -
24.8 -///\ingroup misc
24.9 -///\file
24.10 -///\brief Tools for measuring cpu usage
24.11 -
24.12 -#include <sys/time.h>
24.13 -#include <sys/times.h>
24.14 -#include <fstream>
24.15 -#include <iostream>
24.16 -#include <unistd.h>
24.17 -
24.18 -namespace hugo {
24.19 -
24.20 - /// \addtogroup misc
24.21 - /// @{
24.22 -
24.23 - /// A class to store (cpu)time instances.
24.24 -
24.25 - /// This class stores five time values.
24.26 - /// - a real time
24.27 - /// - a user cpu time
24.28 - /// - a system cpu time
24.29 - /// - a user cpu time of children
24.30 - /// - a system cpu time of children
24.31 - ///
24.32 - /// TimeStamp's can be added to or substracted from each other and
24.33 - /// they can be pushed to a stream.
24.34 - ///
24.35 - /// In most cases, perhaps \ref Timer class is what you want to use instead.
24.36 - ///
24.37 - ///\author Alpar Juttner
24.38 -
24.39 - class TimeStamp
24.40 - {
24.41 - tms ts;
24.42 - double real_time;
24.43 -
24.44 - public:
24.45 -
24.46 - tms &getTms() {return ts;}
24.47 - const tms &getTms() const {return ts;}
24.48 - ///Read the current time values of the process
24.49 - void stamp()
24.50 - {
24.51 - timeval tv;
24.52 - times(&ts);
24.53 - gettimeofday(&tv, 0);real_time=tv.tv_sec+double(tv.tv_usec)/1e6;
24.54 - }
24.55 -
24.56 - /// Constructor initializing with zero
24.57 - TimeStamp()
24.58 - { ts.tms_utime=ts.tms_stime=ts.tms_cutime=ts.tms_cstime=0; real_time=0;}
24.59 - ///Constructor initializing with the current time values of the process
24.60 - TimeStamp(void *) { stamp();}
24.61 -
24.62 - ///
24.63 - TimeStamp &operator+=(const TimeStamp &b)
24.64 - {
24.65 - ts.tms_utime+=b.ts.tms_utime;
24.66 - ts.tms_stime+=b.ts.tms_stime;
24.67 - ts.tms_cutime+=b.ts.tms_cutime;
24.68 - ts.tms_cstime+=b.ts.tms_cstime;
24.69 - real_time+=b.real_time;
24.70 - return *this;
24.71 - }
24.72 - ///
24.73 - TimeStamp operator+(const TimeStamp &b) const
24.74 - {
24.75 - TimeStamp t(*this);
24.76 - return t+=b;
24.77 - }
24.78 - ///
24.79 - TimeStamp &operator-=(const TimeStamp &b)
24.80 - {
24.81 - ts.tms_utime-=b.ts.tms_utime;
24.82 - ts.tms_stime-=b.ts.tms_stime;
24.83 - ts.tms_cutime-=b.ts.tms_cutime;
24.84 - ts.tms_cstime-=b.ts.tms_cstime;
24.85 - real_time-=b.real_time;
24.86 - return *this;
24.87 - }
24.88 - ///
24.89 - TimeStamp operator-(const TimeStamp &b) const
24.90 - {
24.91 - TimeStamp t(*this);
24.92 - return t-=b;
24.93 - }
24.94 -
24.95 - ///The time ellapsed since the last call of stamp()
24.96 - TimeStamp ellapsed() const
24.97 - {
24.98 - TimeStamp t(NULL);
24.99 - return t-*this;
24.100 - }
24.101 -
24.102 - friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
24.103 -
24.104 - ///Gives back the user time of the process
24.105 - double getUserTime() const
24.106 - {
24.107 - return double(ts.tms_utime)/sysconf(_SC_CLK_TCK);
24.108 - }
24.109 - ///Gives back the system time of the process
24.110 - double getSystemTime() const
24.111 - {
24.112 - return double(ts.tms_stime)/sysconf(_SC_CLK_TCK);
24.113 - }
24.114 - ///Gives back the user time of the process' children
24.115 - double getCUserTime() const
24.116 - {
24.117 - return double(ts.tms_cutime)/sysconf(_SC_CLK_TCK);
24.118 - }
24.119 - ///Gives back the user time of the process' children
24.120 - double getCSystemTime() const
24.121 - {
24.122 - return double(ts.tms_cstime)/sysconf(_SC_CLK_TCK);
24.123 - }
24.124 - ///Gives back the real time of the process
24.125 - double getRealTime() const {return real_time;}
24.126 - };
24.127 -
24.128 - ///Class measuring the cpu time and real time usage of the process
24.129 -
24.130 - ///Class measuring the cpu time and real time usage of the process.
24.131 - ///It is quite easy-to-use, here is a short example.
24.132 - ///\code
24.133 - ///int main()
24.134 - ///{
24.135 - ///
24.136 - /// ...
24.137 - ///
24.138 - /// Timer T();
24.139 - /// doSomething();
24.140 - /// cout << T;
24.141 - /// T.reset();
24.142 - /// doSomethingElse();
24.143 - /// cout << T;
24.144 - ///
24.145 - /// ...
24.146 - ///
24.147 - ///}
24.148 - ///\endcode
24.149 - ///
24.150 - ///\todo This shouldn't be Unix (Linux) specific.
24.151 - ///
24.152 - ///\author Alpar Juttner
24.153 - class Timer
24.154 - {
24.155 - TimeStamp start_time;
24.156 -
24.157 - void _reset() {start_time.stamp();}
24.158 -
24.159 - public:
24.160 - ///Constructor. It starts with zero time counters
24.161 - Timer() {_reset();}
24.162 -
24.163 - ///Computes the ellapsed time
24.164 -
24.165 - ///This conversion computes the ellapsed time
24.166 - ///since the construction of \c t or since
24.167 - ///the last \c t.reset().
24.168 - operator TimeStamp ()
24.169 - {
24.170 - TimeStamp t;
24.171 - t.stamp();
24.172 - return t-start_time;
24.173 - }
24.174 -
24.175 - ///Resets the time counters
24.176 - TimeStamp reset()
24.177 - {
24.178 - TimeStamp t(start_time);
24.179 - _reset();
24.180 - return start_time-t;
24.181 - }
24.182 - };
24.183 -
24.184 - ///Prints the time counters
24.185 -
24.186 - ///Prints the time counters in the following form:
24.187 - ///
24.188 - /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
24.189 - ///
24.190 - /// where the values are the
24.191 - /// \li \c u: user cpu time,
24.192 - /// \li \c s: system cpu time,
24.193 - /// \li \c cu: user cpu time of children,
24.194 - /// \li \c cs: system cpu time of children,
24.195 - /// \li \c real: real time.
24.196 - inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
24.197 - {
24.198 - long cls = sysconf(_SC_CLK_TCK);
24.199 - os << "u: " << double(t.getTms().tms_utime)/cls <<
24.200 - "s, s: " << double(t.getTms().tms_stime)/cls <<
24.201 - "s, cu: " << double(t.getTms().tms_cutime)/cls <<
24.202 - "s, cs: " << double(t.getTms().tms_cstime)/cls <<
24.203 - "s, real: " << t.getRealTime() << "s";
24.204 - return os;
24.205 - }
24.206 -
24.207 - /// @}
24.208 -
24.209 -} //namespace hugo
24.210 -
24.211 -#endif //HUGO_TIME_MEASURE_H
25.1 --- a/src/include/unionfind.h Thu May 06 09:26:23 2004 +0000
25.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
25.3 @@ -1,700 +0,0 @@
25.4 -// -*- c++ -*- //
25.5 -#ifndef HUGO_UNION_FIND_H
25.6 -#define HUGO_UNION_FIND_H
25.7 -
25.8 -//!\ingroup auxdat
25.9 -//!\file
25.10 -//!\brief Union-Find data structures.
25.11 -
25.12 -
25.13 -#include <vector>
25.14 -#include <list>
25.15 -#include <utility>
25.16 -#include <algorithm>
25.17 -
25.18 -#include <invalid.h>
25.19 -
25.20 -namespace hugo {
25.21 -
25.22 - //! \addtogroup auxdat
25.23 - //! @{
25.24 -
25.25 - /**
25.26 - * \brief A \e Union-Find data structure implementation
25.27 - *
25.28 - * The class implements the \e Union-Find data structure.
25.29 - * The union operation uses rank heuristic, while
25.30 - * the find operation uses path compresson.
25.31 - * This is a very simple but efficient implementation, providing
25.32 - * only four methods: join (union), find, insert and size.
25.33 - * For more features see the \ref UnionFindEnum class.
25.34 - *
25.35 - * \pre The elements are automatically added only if the map
25.36 - * given to the constructor was filled with -1's. Otherwise you
25.37 - * need to add all the elements by the \ref insert() method.
25.38 - */
25.39 -
25.40 - template <typename T, typename TIntMap>
25.41 - class UnionFind {
25.42 -
25.43 - public:
25.44 - typedef T ElementType;
25.45 - typedef std::pair<int,int> PairType;
25.46 -
25.47 - private:
25.48 - std::vector<PairType> data;
25.49 - TIntMap& map;
25.50 -
25.51 - public:
25.52 - UnionFind(TIntMap& m) : map(m) {}
25.53 -
25.54 - /**
25.55 - * \brief Returns the index of the element's component.
25.56 - *
25.57 - * The method returns the index of the element's component.
25.58 - * This is an integer between zero and the number of inserted elements.
25.59 - */
25.60 -
25.61 - int find(T a)
25.62 - {
25.63 - int comp0 = map[a];
25.64 - if (comp0 < 0) {
25.65 - return insert(a);
25.66 - }
25.67 - int comp = comp0;
25.68 - int next;
25.69 - while ( (next = data[comp].first) != comp) {
25.70 - comp = next;
25.71 - }
25.72 - while ( (next = data[comp0].first) != comp) {
25.73 - data[comp0].first = comp;
25.74 - comp0 = next;
25.75 - }
25.76 -
25.77 - return comp;
25.78 - }
25.79 -
25.80 - /**
25.81 - * \brief Insert a new element into the structure.
25.82 - *
25.83 - * This method inserts a new element into the data structure.
25.84 - *
25.85 - * It is not required to use this method:
25.86 - * if the map given to the constructor was filled
25.87 - * with -1's then it is called automatically
25.88 - * on the first \ref find or \ref join.
25.89 - *
25.90 - * The method returns the index of the new component.
25.91 - */
25.92 -
25.93 - int insert(T a)
25.94 - {
25.95 - int n = data.size();
25.96 - data.push_back(std::make_pair(n, 1));
25.97 - map.set(a,n);
25.98 - return n;
25.99 - }
25.100 -
25.101 - /**
25.102 - * \brief Joining the components of element \e a and element \e b.
25.103 - *
25.104 - * This is the \e union operation of the Union-Find structure.
25.105 - * Joins the component of elemenent \e a and component of
25.106 - * element \e b. If \e a and \e b are in the same component then
25.107 - * it returns false otherwise it returns true.
25.108 - */
25.109 -
25.110 - bool join(T a, T b)
25.111 - {
25.112 - int ca = find(a);
25.113 - int cb = find(b);
25.114 -
25.115 - if ( ca == cb )
25.116 - return false;
25.117 -
25.118 - if ( data[ca].second > data[cb].second ) {
25.119 - data[cb].first = ca;
25.120 - data[ca].second += data[cb].second;
25.121 - }
25.122 - else {
25.123 - data[ca].first = cb;
25.124 - data[cb].second += data[ca].second;
25.125 - }
25.126 - return true;
25.127 - }
25.128 -
25.129 - /**
25.130 - * \brief Returns the size of the component of element \e a.
25.131 - *
25.132 - * Returns the size of the component of element \e a.
25.133 - */
25.134 -
25.135 - int size(T a)
25.136 - {
25.137 - int ca = find(a);
25.138 - return data[ca].second;
25.139 - }
25.140 -
25.141 - };
25.142 -
25.143 -
25.144 -
25.145 -
25.146 - /*******************************************************/
25.147 -
25.148 -
25.149 -#ifdef DEVELOPMENT_DOCS
25.150 -
25.151 - /**
25.152 - * \brief The auxiliary class for the \ref UnionFindEnum class.
25.153 - *
25.154 - * In the \ref UnionFindEnum class all components are represented as
25.155 - * a std::list.
25.156 - * Items of these lists are UnionFindEnumItem structures.
25.157 - *
25.158 - * The class has four fields:
25.159 - * - T me - the actual element
25.160 - * - IIter parent - the parent of the element in the union-find structure
25.161 - * - int size - the size of the component of the element.
25.162 - * Only valid if the element
25.163 - * is the leader of the component.
25.164 - * - CIter my_class - pointer into the list of components
25.165 - * pointing to the component of the element.
25.166 - * Only valid if the element is the leader of the component.
25.167 - */
25.168 -
25.169 -#endif
25.170 -
25.171 - template <typename T>
25.172 - struct UnionFindEnumItem {
25.173 -
25.174 - typedef std::list<UnionFindEnumItem> ItemList;
25.175 - typedef std::list<ItemList> ClassList;
25.176 - typedef typename ItemList::iterator IIter;
25.177 - typedef typename ClassList::iterator CIter;
25.178 -
25.179 - T me;
25.180 - IIter parent;
25.181 - int size;
25.182 - CIter my_class;
25.183 -
25.184 - UnionFindEnumItem() {}
25.185 - UnionFindEnumItem(const T &_me, CIter _my_class):
25.186 - me(_me), size(1), my_class(_my_class) {}
25.187 - };
25.188 -
25.189 -
25.190 - /**
25.191 - * \brief A \e Union-Find data structure implementation which
25.192 - * is able to enumerate the components.
25.193 - *
25.194 - * The class implements an \e Union-Find data structure
25.195 - * which is able to enumerate the components and the items in
25.196 - * a component. If you don't need this feature then perhaps it's
25.197 - * better to use the \ref UnionFind class which is more efficient.
25.198 - *
25.199 - * The union operation uses rank heuristic, while
25.200 - * the find operation uses path compresson.
25.201 - *
25.202 - * \pre You
25.203 - * need to add all the elements by the \ref insert() method.
25.204 - */
25.205 -
25.206 -
25.207 - template <typename T, template <typename Item> class Map>
25.208 - class UnionFindEnum {
25.209 -
25.210 - typedef std::list<UnionFindEnumItem<T> > ItemList;
25.211 - typedef std::list<ItemList> ClassList;
25.212 - typedef typename ItemList::iterator IIter;
25.213 - typedef typename ItemList::const_iterator IcIter;
25.214 - typedef typename ClassList::iterator CIter;
25.215 - typedef typename ClassList::const_iterator CcIter;
25.216 -
25.217 - public:
25.218 - typedef T ElementType;
25.219 - typedef UnionFindEnumItem<T> ItemType;
25.220 - typedef Map< IIter > MapType;
25.221 -
25.222 - private:
25.223 - MapType& m;
25.224 - ClassList classes;
25.225 -
25.226 - IIter _find(IIter a) const {
25.227 - IIter comp = a;
25.228 - IIter next;
25.229 - while( (next = comp->parent) != comp ) {
25.230 - comp = next;
25.231 - }
25.232 -
25.233 - IIter comp1 = a;
25.234 - while( (next = comp1->parent) != comp ) {
25.235 - comp1->parent = comp->parent;
25.236 - comp1 = next;
25.237 - }
25.238 - return comp;
25.239 - }
25.240 -
25.241 - public:
25.242 - UnionFindEnum(MapType& _m) : m(_m) {}
25.243 -
25.244 -
25.245 - /**
25.246 - * \brief Insert the given element into a new component.
25.247 - *
25.248 - * This method creates a new component consisting only of the
25.249 - * given element.
25.250 - */
25.251 -
25.252 - void insert(const T &a)
25.253 - {
25.254 -
25.255 -
25.256 - classes.push_back(ItemList());
25.257 - CIter aclass = classes.end();
25.258 - --aclass;
25.259 -
25.260 - ItemList &alist = *aclass;
25.261 - alist.push_back(ItemType(a, aclass));
25.262 - IIter ai = alist.begin();
25.263 -
25.264 - ai->parent = ai;
25.265 - m.set(a, ai);
25.266 -
25.267 - }
25.268 -
25.269 - /**
25.270 - * \brief Insert the given element into the component of the others.
25.271 - *
25.272 - * This methods insert the element \e a into the component of the
25.273 - * element \e comp.
25.274 - */
25.275 -
25.276 - void insert(const T &a, const T &comp) {
25.277 -
25.278 - IIter clit = _find(m[comp]);
25.279 - ItemList &c = *clit->my_class;
25.280 - c.push_back(ItemType(a,0));
25.281 - IIter ai = c.end();
25.282 - --ai;
25.283 - ai->parent = clit;
25.284 - m.set(a, ai);
25.285 - ++clit->size;
25.286 - }
25.287 -
25.288 -
25.289 - /**
25.290 - * \brief Find the leader of the component of the given element.
25.291 - *
25.292 - * The method returns the leader of the component of the given element.
25.293 - */
25.294 -
25.295 - T find(const T &a) const {
25.296 - return _find(m[a])->me;
25.297 - }
25.298 -
25.299 -
25.300 - /**
25.301 - * \brief Joining the component of element \e a and element \e b.
25.302 - *
25.303 - * This is the \e union operation of the Union-Find structure.
25.304 - * Joins the component of elemenent \e a and component of
25.305 - * element \e b. If \e a and \e b are in the same component then
25.306 - * returns false else returns true.
25.307 - */
25.308 -
25.309 - bool join(T a, T b) {
25.310 -
25.311 - IIter ca = _find(m[a]);
25.312 - IIter cb = _find(m[b]);
25.313 -
25.314 - if ( ca == cb ) {
25.315 - return false;
25.316 - }
25.317 -
25.318 - if ( ca->size > cb->size ) {
25.319 -
25.320 - cb->parent = ca->parent;
25.321 - ca->size += cb->size;
25.322 -
25.323 - ItemList &alist = *ca->my_class;
25.324 - alist.splice(alist.end(),*cb->my_class);
25.325 -
25.326 - classes.erase(cb->my_class);
25.327 - cb->my_class = 0;
25.328 - }
25.329 - else {
25.330 -
25.331 - ca->parent = cb->parent;
25.332 - cb->size += ca->size;
25.333 -
25.334 - ItemList &blist = *cb->my_class;
25.335 - blist.splice(blist.end(),*ca->my_class);
25.336 -
25.337 - classes.erase(ca->my_class);
25.338 - ca->my_class = 0;
25.339 - }
25.340 -
25.341 - return true;
25.342 - }
25.343 -
25.344 -
25.345 - /**
25.346 - * \brief Returns the size of the component of element \e a.
25.347 - *
25.348 - * Returns the size of the component of element \e a.
25.349 - */
25.350 -
25.351 - int size(const T &a) const {
25.352 - return _find(m[a])->size;
25.353 - }
25.354 -
25.355 -
25.356 - /**
25.357 - * \brief Split up the component of the element.
25.358 - *
25.359 - * Splitting the component of the element into sigleton
25.360 - * components (component of size one).
25.361 - */
25.362 -
25.363 - void split(const T &a) {
25.364 -
25.365 - IIter ca = _find(m[a]);
25.366 -
25.367 - if ( ca->size == 1 )
25.368 - return;
25.369 -
25.370 - CIter aclass = ca->my_class;
25.371 -
25.372 - for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
25.373 - classes.push_back(ItemList());
25.374 - CIter nl = --classes.end();
25.375 - nl->splice(nl->end(), *aclass, curr);
25.376 -
25.377 - curr->size=1;
25.378 - curr->parent=curr;
25.379 - curr->my_class = nl;
25.380 - }
25.381 -
25.382 - ca->size=1;
25.383 - return;
25.384 - }
25.385 -
25.386 -
25.387 - /**
25.388 - * \brief Set the given element to the leader element of its component.
25.389 - *
25.390 - * Set the given element to the leader element of its component.
25.391 - */
25.392 -
25.393 - void makeRep(const T &a) {
25.394 -
25.395 - IIter ia = m[a];
25.396 - IIter la = _find(ia);
25.397 - if (la == ia) return;
25.398 -
25.399 - ia->my_class = la->my_class;
25.400 - la->my_class = 0;
25.401 -
25.402 - ia->size = la->size;
25.403 -
25.404 - CIter l = ia->my_class;
25.405 - l->splice(l->begin(),*l,ia);
25.406 -
25.407 - ia->parent = ia;
25.408 - la->parent = ia;
25.409 - }
25.410 -
25.411 - /**
25.412 - * \brief Move the given element to an other component.
25.413 - *
25.414 - * This method moves the element \e a from its component
25.415 - * to the component of \e comp.
25.416 - * If \e a and \e comp are in the same component then
25.417 - * it returns false otherwise it returns true.
25.418 - */
25.419 -
25.420 - bool move(const T &a, const T &comp) {
25.421 -
25.422 - IIter ai = m[a];
25.423 - IIter lai = _find(ai);
25.424 - IIter clit = _find(m[comp]);
25.425 -
25.426 - if (lai == clit)
25.427 - return false;
25.428 -
25.429 - ItemList &c = *clit->my_class;
25.430 -
25.431 - bool is_leader = (lai == ai);
25.432 - bool singleton = false;
25.433 -
25.434 - if (is_leader) {
25.435 - ++lai;
25.436 - }
25.437 -
25.438 - c.splice(c.end(), *lai->my_class, ai);
25.439 -
25.440 - if (is_leader) {
25.441 - if (ai->size == 1) {
25.442 - classes.erase(ai->my_class);
25.443 - singleton = true;
25.444 - }
25.445 - else {
25.446 - lai->size = ai->size;
25.447 - lai->my_class = ai->my_class;
25.448 - }
25.449 - }
25.450 - if (!singleton) {
25.451 - for (IIter i = lai; i != lai->my_class->end(); ++i)
25.452 - i->parent = lai;
25.453 - --lai->size;
25.454 - }
25.455 -
25.456 - ai->parent = clit;
25.457 - ai->my_class = 0;
25.458 - ++clit->size;
25.459 -
25.460 - return true;
25.461 - }
25.462 -
25.463 -
25.464 - /**
25.465 - * \brief Remove the given element from the structure.
25.466 - *
25.467 - * Remove the given element from the structure.
25.468 - *
25.469 - * Removes the element from its component and if the component becomes
25.470 - * empty then removes that component from the component list.
25.471 - */
25.472 - void erase(const T &a) {
25.473 -
25.474 - IIter ma = m[a];
25.475 - if (ma == 0) return;
25.476 -
25.477 - IIter la = _find(ma);
25.478 - if (la == ma) {
25.479 - if (ma -> size == 1){
25.480 - classes.erase(ma->my_class);
25.481 - m.set(a,0);
25.482 - return;
25.483 - }
25.484 - ++la;
25.485 - la->size = ma->size;
25.486 - la->my_class = ma->my_class;
25.487 - }
25.488 -
25.489 - for (IIter i = la; i != la->my_class->end(); ++i) {
25.490 - i->parent = la;
25.491 - }
25.492 -
25.493 - la->size--;
25.494 - la->my_class->erase(ma);
25.495 - m.set(a,0);
25.496 - }
25.497 -
25.498 - /**
25.499 - * \brief Removes the component of the given element from the structure.
25.500 - *
25.501 - * Removes the component of the given element from the structure.
25.502 - */
25.503 -
25.504 - void eraseClass(const T &a) {
25.505 - IIter ma = m[a];
25.506 - if (ma == 0) return;
25.507 -# ifdef DEBUG
25.508 - CIter c = _find(ma)->my_class;
25.509 - for (IIter i=c->begin(); i!=c->end(); ++i)
25.510 - m.set(i->me, 0);
25.511 -# endif
25.512 - classes.erase(_find(ma)->my_class);
25.513 - }
25.514 -
25.515 -
25.516 - class ClassIt {
25.517 - friend class UnionFindEnum;
25.518 -
25.519 - CcIter i;
25.520 - public:
25.521 - ClassIt(Invalid): i(0) {}
25.522 - ClassIt() {}
25.523 -
25.524 - operator const T& () const {
25.525 - ItemList const &ll = *i;
25.526 - return (ll.begin())->me; }
25.527 - bool operator == (ClassIt it) const {
25.528 - return (i == it.i);
25.529 - }
25.530 - bool operator != (ClassIt it) const {
25.531 - return (i != it.i);
25.532 - }
25.533 - bool operator < (ClassIt it) const {
25.534 - return (i < it.i);
25.535 - }
25.536 -
25.537 - bool valid() const { return i != 0; }
25.538 - private:
25.539 - void first(const ClassList &l) { i = l.begin(); validate(l); }
25.540 - void next(const ClassList &l) {
25.541 - ++i;
25.542 - validate(l);
25.543 - }
25.544 - void validate(const ClassList &l) {
25.545 - if ( i == l.end() )
25.546 - i = 0;
25.547 - }
25.548 - };
25.549 -
25.550 - /**
25.551 - * \brief Sets the iterator to point to the first component.
25.552 - *
25.553 - * Sets the iterator to point to the first component.
25.554 - *
25.555 - * With the \ref first, \ref valid and \ref next methods you can
25.556 - * iterate through the components. For example:
25.557 - * \code
25.558 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
25.559 - * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
25.560 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
25.561 - * for (U.first(iter); U.valid(iter); U.next(iter)) {
25.562 - * // iter is convertible to Graph::Node
25.563 - * cout << iter << endl;
25.564 - * }
25.565 - * \endcode
25.566 - */
25.567 -
25.568 - ClassIt& first(ClassIt& it) const {
25.569 - it.first(classes);
25.570 - return it;
25.571 - }
25.572 -
25.573 - /**
25.574 - * \brief Returns whether the iterator is valid.
25.575 - *
25.576 - * Returns whether the iterator is valid.
25.577 - *
25.578 - * With the \ref first, \ref valid and \ref next methods you can
25.579 - * iterate through the components. See the example here: \ref first.
25.580 - */
25.581 -
25.582 - bool valid(ClassIt const &it) const {
25.583 - return it.valid();
25.584 - }
25.585 -
25.586 - /**
25.587 - * \brief Steps the iterator to the next component.
25.588 - *
25.589 - * Steps the iterator to the next component.
25.590 - *
25.591 - * With the \ref first, \ref valid and \ref next methods you can
25.592 - * iterate through the components. See the example here: \ref first.
25.593 - */
25.594 -
25.595 - ClassIt& next(ClassIt& it) const {
25.596 - it.next(classes);
25.597 - return it;
25.598 - }
25.599 -
25.600 -
25.601 - class ItemIt {
25.602 - friend class UnionFindEnum;
25.603 -
25.604 - IcIter i;
25.605 - const ItemList *l;
25.606 - public:
25.607 - ItemIt(Invalid): i(0) {}
25.608 - ItemIt() {}
25.609 -
25.610 - operator const T& () const { return i->me; }
25.611 - bool operator == (ItemIt it) const {
25.612 - return (i == it.i);
25.613 - }
25.614 - bool operator != (ItemIt it) const {
25.615 - return (i != it.i);
25.616 - }
25.617 - bool operator < (ItemIt it) const {
25.618 - return (i < it.i);
25.619 - }
25.620 -
25.621 - bool valid() const { return i != 0; }
25.622 - private:
25.623 - void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
25.624 - void next() {
25.625 - ++i;
25.626 - validate();
25.627 - }
25.628 - void validate() {
25.629 - if ( i == l->end() )
25.630 - i = 0;
25.631 - }
25.632 - };
25.633 -
25.634 -
25.635 -
25.636 - /**
25.637 - * \brief Sets the iterator to point to the first element of the component.
25.638 - *
25.639 - * \anchor first2
25.640 - * Sets the iterator to point to the first element of the component.
25.641 - *
25.642 - * With the \ref first2 "first", \ref valid2 "valid"
25.643 - * and \ref next2 "next" methods you can
25.644 - * iterate through the elements of a component. For example
25.645 - * (iterating through the component of the node \e node):
25.646 - * \code
25.647 - * Graph::Node node = ...;
25.648 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
25.649 - * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
25.650 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
25.651 - * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
25.652 - * // iiter is convertible to Graph::Node
25.653 - * cout << iiter << endl;
25.654 - * }
25.655 - * \endcode
25.656 - */
25.657 -
25.658 - ItemIt& first(ItemIt& it, const T& a) const {
25.659 - it.first( * _find(m[a])->my_class );
25.660 - return it;
25.661 - }
25.662 -
25.663 - /**
25.664 - * \brief Returns whether the iterator is valid.
25.665 - *
25.666 - * \anchor valid2
25.667 - * Returns whether the iterator is valid.
25.668 - *
25.669 - * With the \ref first2 "first", \ref valid2 "valid"
25.670 - * and \ref next2 "next" methods you can
25.671 - * iterate through the elements of a component.
25.672 - * See the example here: \ref first2 "first".
25.673 - */
25.674 -
25.675 - bool valid(ItemIt const &it) const {
25.676 - return it.valid();
25.677 - }
25.678 -
25.679 - /**
25.680 - * \brief Steps the iterator to the next component.
25.681 - *
25.682 - * \anchor next2
25.683 - * Steps the iterator to the next component.
25.684 - *
25.685 - * With the \ref first2 "first", \ref valid2 "valid"
25.686 - * and \ref next2 "next" methods you can
25.687 - * iterate through the elements of a component.
25.688 - * See the example here: \ref first2 "first".
25.689 - */
25.690 -
25.691 - ItemIt& next(ItemIt& it) const {
25.692 - it.next();
25.693 - return it;
25.694 - }
25.695 -
25.696 - };
25.697 -
25.698 -
25.699 - //! @}
25.700 -
25.701 -} //namespace hugo
25.702 -
25.703 -#endif //HUGO_UNION_FIND_H
26.1 --- a/src/include/xy.h Thu May 06 09:26:23 2004 +0000
26.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
26.3 @@ -1,227 +0,0 @@
26.4 -// -*- c++ -*-
26.5 -#ifndef HUGO_XY_H
26.6 -#define HUGO_XY_H
26.7 -
26.8 -#include <iostream>
26.9 -
26.10 -///\ingroup misc
26.11 -///\file
26.12 -///\brief A simple two dimensional vector and a bounding box implementation
26.13 -///
26.14 -/// The class \ref hugo::xy "xy" implements
26.15 -///a two dimensional vector with the usual
26.16 -/// operations.
26.17 -///
26.18 -/// The class \ref hugo::BoundingBox "BoundingBox" can be used to determine
26.19 -/// the rectangular bounding box a set of \ref hugo::xy "xy"'s.
26.20 -///
26.21 -///\author Attila Bernath
26.22 -
26.23 -
26.24 -namespace hugo {
26.25 -
26.26 - /// \addtogroup misc
26.27 - /// @{
26.28 -
26.29 - /// A two dimensional vector (plainvector) implementation
26.30 -
26.31 - /// A two dimensional vector (plainvector) implementation
26.32 - ///with the usual vector
26.33 - /// operators.
26.34 - ///
26.35 - ///\author Attila Bernath
26.36 - template<typename T>
26.37 - class xy {
26.38 -
26.39 - public:
26.40 -
26.41 - T x,y;
26.42 -
26.43 - ///Default constructor: both coordinates become 0
26.44 - xy() : x(0), y(0) {}
26.45 -
26.46 - ///Constructing the instance from coordinates
26.47 - xy(T a, T b) : x(a), y(b) { }
26.48 -
26.49 -
26.50 - ///Gives back the square of the norm of the vector
26.51 - T normSquare(){
26.52 - return x*x+y*y;
26.53 - };
26.54 -
26.55 - ///Increments the left hand side by u
26.56 - xy<T>& operator +=(const xy<T>& u){
26.57 - x += u.x;
26.58 - y += u.y;
26.59 - return *this;
26.60 - };
26.61 -
26.62 - ///Decrements the left hand side by u
26.63 - xy<T>& operator -=(const xy<T>& u){
26.64 - x -= u.x;
26.65 - y -= u.y;
26.66 - return *this;
26.67 - };
26.68 -
26.69 - ///Multiplying the left hand side with a scalar
26.70 - xy<T>& operator *=(const T &u){
26.71 - x *= u;
26.72 - y *= u;
26.73 - return *this;
26.74 - };
26.75 -
26.76 - ///Dividing the left hand side by a scalar
26.77 - xy<T>& operator /=(const T &u){
26.78 - x /= u;
26.79 - y /= u;
26.80 - return *this;
26.81 - };
26.82 -
26.83 - ///Returns the scalar product of two vectors
26.84 - T operator *(const xy<T>& u){
26.85 - return x*u.x+y*u.y;
26.86 - };
26.87 -
26.88 - ///Returns the sum of two vectors
26.89 - xy<T> operator+(const xy<T> &u) const {
26.90 - xy<T> b=*this;
26.91 - return b+=u;
26.92 - };
26.93 -
26.94 - ///Returns the difference of two vectors
26.95 - xy<T> operator-(const xy<T> &u) const {
26.96 - xy<T> b=*this;
26.97 - return b-=u;
26.98 - };
26.99 -
26.100 - ///Returns a vector multiplied by a scalar
26.101 - xy<T> operator*(const T &u) const {
26.102 - xy<T> b=*this;
26.103 - return b*=u;
26.104 - };
26.105 -
26.106 - ///Returns a vector divided by a scalar
26.107 - xy<T> operator/(const T &u) const {
26.108 - xy<T> b=*this;
26.109 - return b/=u;
26.110 - };
26.111 -
26.112 - ///Testing equality
26.113 - bool operator==(const xy<T> &u){
26.114 - return (x==u.x) && (y==u.y);
26.115 - };
26.116 -
26.117 - ///Testing inequality
26.118 - bool operator!=(xy u){
26.119 - return (x!=u.x) || (y!=u.y);
26.120 - };
26.121 -
26.122 - };
26.123 -
26.124 - ///Reading a plainvector from a stream
26.125 - template<typename T>
26.126 - inline
26.127 - std::istream& operator>>(std::istream &is, xy<T> &z)
26.128 - {
26.129 -
26.130 - is >> z.x >> z.y;
26.131 - return is;
26.132 - }
26.133 -
26.134 - ///Outputting a plainvector to a stream
26.135 - template<typename T>
26.136 - inline
26.137 - std::ostream& operator<<(std::ostream &os, xy<T> z)
26.138 - {
26.139 - os << "(" << z.x << ", " << z.y << ")";
26.140 - return os;
26.141 - }
26.142 -
26.143 -
26.144 - /// A class to calculate or store the bounding box of plainvectors.
26.145 -
26.146 - /// A class to calculate or store the bounding box of plainvectors.
26.147 - ///
26.148 - ///\author Attila Bernath
26.149 - template<typename T>
26.150 - class BoundingBox {
26.151 - xy<T> bottom_left, top_right;
26.152 - bool _empty;
26.153 - public:
26.154 -
26.155 - ///Default constructor: an empty bounding box
26.156 - BoundingBox() { _empty = true; }
26.157 -
26.158 - ///Constructing the instance from one point
26.159 - BoundingBox(xy<T> a) { bottom_left=top_right=a; _empty = false; }
26.160 -
26.161 - ///Is there any point added
26.162 - bool empty() const {
26.163 - return _empty;
26.164 - }
26.165 -
26.166 - ///Gives back the bottom left corner (if the bounding box is empty, then the return value is not defined)
26.167 - xy<T> bottomLeft() const {
26.168 - return bottom_left;
26.169 - };
26.170 -
26.171 - ///Gives back the top right corner (if the bounding box is empty, then the return value is not defined)
26.172 - xy<T> topRight() const {
26.173 - return top_right;
26.174 - };
26.175 -
26.176 - ///Checks whether a point is inside a bounding box
26.177 - bool inside(const xy<T>& u){
26.178 - if (_empty)
26.179 - return false;
26.180 - else{
26.181 - return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
26.182 - (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
26.183 - }
26.184 - }
26.185 -
26.186 - ///Increments a bounding box with a point
26.187 - BoundingBox& operator +=(const xy<T>& u){
26.188 - if (_empty){
26.189 - bottom_left=top_right=u;
26.190 - _empty = false;
26.191 - }
26.192 - else{
26.193 - if (bottom_left.x > u.x) bottom_left.x = u.x;
26.194 - if (bottom_left.y > u.y) bottom_left.y = u.y;
26.195 - if (top_right.x < u.x) top_right.x = u.x;
26.196 - if (top_right.y < u.y) top_right.y = u.y;
26.197 - }
26.198 - return *this;
26.199 - };
26.200 -
26.201 - ///Sums a bounding box and a point
26.202 - BoundingBox operator +(const xy<T>& u){
26.203 - BoundingBox b = *this;
26.204 - return b += u;
26.205 - };
26.206 -
26.207 - ///Increments a bounding box with an other bounding box
26.208 - BoundingBox& operator +=(const BoundingBox &u){
26.209 - if ( !u.empty() ){
26.210 - *this += u.bottomLeft();
26.211 - *this += u.topRight();
26.212 - }
26.213 - return *this;
26.214 - };
26.215 -
26.216 - ///Sums two bounding boxes
26.217 - BoundingBox operator +(const BoundingBox& u){
26.218 - BoundingBox b = *this;
26.219 - return b += u;
26.220 - };
26.221 -
26.222 - };//class Boundingbox
26.223 -
26.224 -
26.225 - /// @}
26.226 -
26.227 -
26.228 -} //namespace hugo
26.229 -
26.230 -#endif //HUGO_XY_H