1.1 --- a/src/work/alpar/f_ed_ka.h Fri Feb 20 21:59:34 2004 +0000
1.2 +++ b/src/work/alpar/f_ed_ka.h Fri Feb 20 22:01:02 2004 +0000
1.3 @@ -11,7 +11,7 @@
1.4
1.5 //#include <bfs_iterator.hh>
1.6
1.7 -namespace marci {
1.8 +namespace hugo {
1.9 template <typename Graph, typename FlowMap, typename CapacityMap>
1.10 typename FlowMap::ValueType maxFlow(Graph &G,
1.11 FlowMap &f,
1.12 @@ -114,6 +114,6 @@
1.13 goto augment; // Vivat goto forever!
1.14 }
1.15
1.16 -} // namespace marci
1.17 +} // namespace hugo
1.18
1.19 #endif //EDMONDS_KARP_HH
2.1 --- a/src/work/alpar/f_ed_ka_demo.cc Fri Feb 20 21:59:34 2004 +0000
2.2 +++ b/src/work/alpar/f_ed_ka_demo.cc Fri Feb 20 22:01:02 2004 +0000
2.3 @@ -8,14 +8,14 @@
2.4 #include "f_ed_ka.h"
2.5 #include "../marci/time_measure.h"
2.6
2.7 -using namespace marci;
2.8 +using namespace hugo;
2.9
2.10 // Use a DIMACS max flow file as stdin.
2.11 // read_dimacs_demo < dimacs_max_flow_file
2.12
2.13 int main(int, char **) {
2.14 - // typedef SmartGraph Graph;
2.15 - typedef ListGraph Graph;
2.16 + typedef SmartGraph Graph;
2.17 + //typedef ListGraph Graph;
2.18
2.19 typedef Graph::NodeIt NodeIt;
2.20 typedef Graph::EachNodeIt EachNodeIt;
2.21 @@ -23,11 +23,11 @@
2.22
2.23 Graph G;
2.24 NodeIt s, t;
2.25 - Graph::EdgeMap<int> cap(G);
2.26 + Graph::DynEdgeMap<int> cap(G);
2.27 readDimacsMaxFlow(std::cin, G, s, t, cap);
2.28
2.29 std::cout << "edmonds karp demo..." << std::endl;
2.30 - Graph::EdgeMap<int> flow(G); //0 flow
2.31 + Graph::DynEdgeMap<int> flow(G); //0 flow
2.32
2.33 int ret;
2.34 double pre_time=currTime();
3.1 --- a/src/work/alpar/smart_graph.h Fri Feb 20 21:59:34 2004 +0000
3.2 +++ b/src/work/alpar/smart_graph.h Fri Feb 20 22:01:02 2004 +0000
3.3 @@ -27,12 +27,32 @@
3.4 std::vector<NodeT> nodes;
3.5 std::vector<EdgeT> edges;
3.6
3.7 + template <typename Key> class DynMapBase
3.8 + {
3.9 + protected:
3.10 + SmartGraph* G;
3.11 + public:
3.12 + virtual void add(const Key k) = NULL;
3.13 + virtual void erase(const Key k) = NULL;
3.14 + DynMapBase(SmartGraph &_G) : G(&_G) {}
3.15 + virtual ~DynMapBase() {}
3.16 + friend class SmartGraph;
3.17 + };
3.18
3.19 public:
3.20 + template <typename T> class DynEdgeMap;
3.21 + template <typename T> class DynEdgeMap;
3.22
3.23 class NodeIt;
3.24 + class EdgeIt;
3.25 +
3.26 + protected:
3.27 + std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
3.28 + std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
3.29 +
3.30 + public:
3.31 +
3.32 class EachNodeIt;
3.33 - class EdgeIt;
3.34 class EachEdgeIt;
3.35 class OutEdgeIt;
3.36 class InEdgeIt;
3.37 @@ -54,11 +74,21 @@
3.38
3.39 SmartGraph() : nodes(), edges() { }
3.40
3.41 - ~SmartGraph() {}
3.42 + ~SmartGraph()
3.43 + {
3.44 + for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
3.45 + i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
3.46 + for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
3.47 + i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
3.48 + }
3.49
3.50 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
3.51 int edgeNum() const { return edges.size(); } //FIXME: What is this?
3.52
3.53 + int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
3.54 + int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
3.55 +
3.56 +
3.57 NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
3.58 NodeIt head(EdgeIt e) const { return edges[e.n].head; }
3.59
3.60 @@ -114,14 +144,23 @@
3.61 NodeIt addNode() {
3.62 NodeIt n; n.n=nodes.size();
3.63 nodes.push_back(NodeT()); //FIXME: Hmmm...
3.64 +
3.65 + for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
3.66 + i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
3.67 +
3.68 return n;
3.69 }
3.70 +
3.71 EdgeIt addEdge(NodeIt u, NodeIt v) {
3.72 EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
3.73 edges[e.n].tail=u.n; edges[e.n].head=v.n;
3.74 edges[e.n].next_out=nodes[u.n].first_out;
3.75 edges[e.n].next_in=nodes[v.n].first_in;
3.76 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
3.77 +
3.78 + for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
3.79 + i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);
3.80 +
3.81 return e;
3.82 }
3.83
3.84 @@ -130,6 +169,7 @@
3.85 class NodeIt {
3.86 friend class SmartGraph;
3.87 template <typename T> friend class NodeMap;
3.88 + template <typename T> friend class DynNodeMap;
3.89
3.90 friend class EdgeIt;
3.91 friend class OutEdgeIt;
3.92 @@ -156,6 +196,7 @@
3.93 class EdgeIt {
3.94 friend class SmartGraph;
3.95 template <typename T> friend class EdgeMap;
3.96 + template <typename T> friend class DynEdgeMap;
3.97
3.98 friend class NodeIt;
3.99 friend class EachNodeIt;
3.100 @@ -200,15 +241,15 @@
3.101 public:
3.102 typedef T ValueType;
3.103 typedef NodeIt KeyType;
3.104 - NodeMap(const SmartGraph& _G) : G(_G), container(G.nodeNum()) { }
3.105 + NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
3.106 NodeMap(const SmartGraph& _G, T a) :
3.107 - G(_G), container(G.nodeNum(), a) { }
3.108 + G(_G), container(G.maxNodeId(), a) { }
3.109 void set(NodeIt n, T a) { container[n.n]=a; }
3.110 T get(NodeIt n) const { return container[n.n]; }
3.111 T& operator[](NodeIt n) { return container[n.n]; }
3.112 const T& operator[](NodeIt n) const { return container[n.n]; }
3.113 - void update() { container.resize(G.nodeNum()); }
3.114 - void update(T a) { container.resize(G.nodeNum(), a); }
3.115 + void update() { container.resize(G.maxNodeId()); }
3.116 + void update(T a) { container.resize(G.maxNodeId(), a); }
3.117 };
3.118
3.119 template <typename T>
3.120 @@ -218,20 +259,102 @@
3.121 public:
3.122 typedef T ValueType;
3.123 typedef EdgeIt KeyType;
3.124 - EdgeMap(const SmartGraph& _G) : G(_G), container(G.edgeNum()) { }
3.125 + EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
3.126 EdgeMap(const SmartGraph& _G, T a) :
3.127 - G(_G), container(G.edgeNum(), a) { }
3.128 + G(_G), container(G.maxEdgeId(), a) { }
3.129 void set(EdgeIt e, T a) { container[e.n]=a; }
3.130 T get(EdgeIt e) const { return container[e.n]; }
3.131 T& operator[](EdgeIt e) { return container[e.n]; }
3.132 const T& operator[](EdgeIt e) const { return container[e.n]; }
3.133 - void update() { container.resize(G.edgeNum()); }
3.134 - void update(T a) { container.resize(G.edgeNum(), a); }
3.135 + void update() { container.resize(G.maxEdgeId()); }
3.136 + void update(T a) { container.resize(G.maxEdgeId(), a); }
3.137 };
3.138
3.139 + template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
3.140 + {
3.141 + std::vector<T> container;
3.142
3.143 + public:
3.144 + typedef T ValueType;
3.145 + typedef NodeIt KeyType;
3.146
3.147 + DynNodeMap(SmartGraph &_G) :
3.148 + DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
3.149 + {
3.150 + //FIXME: What if there are empty Id's?
3.151 + G->dyn_node_maps.push_back(this);
3.152 + }
3.153 + ~DynNodeMap()
3.154 + {
3.155 + if(G) {
3.156 + std::vector<DynMapBase<NodeIt>* >::iterator i;
3.157 + for(i=G->dyn_node_maps.begin();
3.158 + i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
3.159 + if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
3.160 + }
3.161 + }
3.162
3.163 + void add(const NodeIt k)
3.164 + {
3.165 + if(k.n>=container.size()) container.resize(k.n+1);
3.166 + }
3.167 + void erase(const NodeIt k)
3.168 + {
3.169 + //FIXME: Please implement me.
3.170 + }
3.171 +
3.172 + void set(NodeIt n, T a) { container[n.n]=a; }
3.173 + T get(NodeIt n) const { return container[n.n]; }
3.174 + T& operator[](NodeIt n) { return container[n.n]; }
3.175 + const T& operator[](NodeIt n) const { return container[n.n]; }
3.176 +
3.177 + void update() {} //Useless for DynMaps
3.178 + void update(T a) {} //Useless for DynMaps
3.179 + };
3.180 +
3.181 + template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
3.182 + {
3.183 + std::vector<T> container;
3.184 +
3.185 + public:
3.186 + typedef T ValueType;
3.187 + typedef EdgeIt KeyType;
3.188 +
3.189 + DynEdgeMap(SmartGraph &_G) :
3.190 + DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
3.191 + {
3.192 + //FIXME: What if there are empty Id's?
3.193 + //FIXME: Can I do that? :
3.194 + G->dyn_edge_maps.push_back(this);
3.195 + }
3.196 + ~DynEdgeMap()
3.197 + {
3.198 + if(G) {
3.199 + std::vector<DynMapBase<EdgeIt>* >::iterator i;
3.200 + for(i=G->dyn_edge_maps.begin();
3.201 + i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
3.202 + if(*i==this) G->dyn_edge_maps.erase(i); //FIXME: Way too slow...
3.203 + }
3.204 + }
3.205 +
3.206 + void add(const EdgeIt k)
3.207 + {
3.208 + if(k.n>=int(container.size())) container.resize(k.n+1);
3.209 + }
3.210 + void erase(const EdgeIt k)
3.211 + {
3.212 + //FIXME: Please implement me.
3.213 + }
3.214 +
3.215 + void set(EdgeIt n, T a) { container[n.n]=a; }
3.216 + T get(EdgeIt n) const { return container[n.n]; }
3.217 + T& operator[](EdgeIt n) { return container[n.n]; }
3.218 + const T& operator[](EdgeIt n) const { return container[n.n]; }
3.219 +
3.220 + void update() {} //Useless for DynMaps
3.221 + void update(T a) {} //Useless for DynMaps
3.222 + };
3.223 +
3.224 };
3.225 } //namespace hugo
3.226