# HG changeset patch # User alpar # Date 1077314462 0 # Node ID 0351b00fd2830f7fc5a80f8a737d560c8c632b0a # Parent 8d62f0072ff0da48244fbe322c977d27ad6c58eb Dynamic Maps added. diff -r 8d62f0072ff0 -r 0351b00fd283 src/work/alpar/f_ed_ka.h --- a/src/work/alpar/f_ed_ka.h Fri Feb 20 21:59:34 2004 +0000 +++ b/src/work/alpar/f_ed_ka.h Fri Feb 20 22:01:02 2004 +0000 @@ -11,7 +11,7 @@ //#include -namespace marci { +namespace hugo { template typename FlowMap::ValueType maxFlow(Graph &G, FlowMap &f, @@ -114,6 +114,6 @@ goto augment; // Vivat goto forever! } -} // namespace marci +} // namespace hugo #endif //EDMONDS_KARP_HH diff -r 8d62f0072ff0 -r 0351b00fd283 src/work/alpar/f_ed_ka_demo.cc --- a/src/work/alpar/f_ed_ka_demo.cc Fri Feb 20 21:59:34 2004 +0000 +++ b/src/work/alpar/f_ed_ka_demo.cc Fri Feb 20 22:01:02 2004 +0000 @@ -8,14 +8,14 @@ #include "f_ed_ka.h" #include "../marci/time_measure.h" -using namespace marci; +using namespace hugo; // Use a DIMACS max flow file as stdin. // read_dimacs_demo < dimacs_max_flow_file int main(int, char **) { - // typedef SmartGraph Graph; - typedef ListGraph Graph; + typedef SmartGraph Graph; + //typedef ListGraph Graph; typedef Graph::NodeIt NodeIt; typedef Graph::EachNodeIt EachNodeIt; @@ -23,11 +23,11 @@ Graph G; NodeIt s, t; - Graph::EdgeMap cap(G); + Graph::DynEdgeMap cap(G); readDimacsMaxFlow(std::cin, G, s, t, cap); std::cout << "edmonds karp demo..." << std::endl; - Graph::EdgeMap flow(G); //0 flow + Graph::DynEdgeMap flow(G); //0 flow int ret; double pre_time=currTime(); diff -r 8d62f0072ff0 -r 0351b00fd283 src/work/alpar/smart_graph.h --- a/src/work/alpar/smart_graph.h Fri Feb 20 21:59:34 2004 +0000 +++ b/src/work/alpar/smart_graph.h Fri Feb 20 22:01:02 2004 +0000 @@ -27,12 +27,32 @@ std::vector nodes; std::vector edges; + template class DynMapBase + { + protected: + SmartGraph* G; + public: + virtual void add(const Key k) = NULL; + virtual void erase(const Key k) = NULL; + DynMapBase(SmartGraph &_G) : G(&_G) {} + virtual ~DynMapBase() {} + friend class SmartGraph; + }; public: + template class DynEdgeMap; + template class DynEdgeMap; class NodeIt; + class EdgeIt; + + protected: + std::vector * > dyn_node_maps; + std::vector * > dyn_edge_maps; + + public: + class EachNodeIt; - class EdgeIt; class EachEdgeIt; class OutEdgeIt; class InEdgeIt; @@ -54,11 +74,21 @@ SmartGraph() : nodes(), edges() { } - ~SmartGraph() {} + ~SmartGraph() + { + for(std::vector * >::iterator i=dyn_node_maps.begin(); + i!=dyn_node_maps.end(); ++i) (**i).G=NULL; + for(std::vector * >::iterator i=dyn_edge_maps.begin(); + i!=dyn_edge_maps.end(); ++i) (**i).G=NULL; + } int nodeNum() const { return nodes.size(); } //FIXME: What is this? int edgeNum() const { return edges.size(); } //FIXME: What is this? + int maxNodeId() const { return nodes.size(); } //FIXME: What is this? + int maxEdgeId() const { return edges.size(); } //FIXME: What is this? + + NodeIt tail(EdgeIt e) const { return edges[e.n].tail; } NodeIt head(EdgeIt e) const { return edges[e.n].head; } @@ -114,14 +144,23 @@ NodeIt addNode() { NodeIt n; n.n=nodes.size(); nodes.push_back(NodeT()); //FIXME: Hmmm... + + for(std::vector * >::iterator i=dyn_node_maps.begin(); + i!=dyn_node_maps.end(); ++i) (**i).add(n.n); + return n; } + EdgeIt addEdge(NodeIt u, NodeIt v) { EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... edges[e.n].tail=u.n; edges[e.n].head=v.n; edges[e.n].next_out=nodes[u.n].first_out; edges[e.n].next_in=nodes[v.n].first_in; nodes[u.n].first_out=nodes[v.n].first_in=e.n; + + for(std::vector * >::iterator i=dyn_edge_maps.begin(); + i!=dyn_edge_maps.end(); ++i) (**i).add(e.n); + return e; } @@ -130,6 +169,7 @@ class NodeIt { friend class SmartGraph; template friend class NodeMap; + template friend class DynNodeMap; friend class EdgeIt; friend class OutEdgeIt; @@ -156,6 +196,7 @@ class EdgeIt { friend class SmartGraph; template friend class EdgeMap; + template friend class DynEdgeMap; friend class NodeIt; friend class EachNodeIt; @@ -200,15 +241,15 @@ public: typedef T ValueType; typedef NodeIt KeyType; - NodeMap(const SmartGraph& _G) : G(_G), container(G.nodeNum()) { } + NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { } NodeMap(const SmartGraph& _G, T a) : - G(_G), container(G.nodeNum(), a) { } + G(_G), container(G.maxNodeId(), a) { } void set(NodeIt n, T a) { container[n.n]=a; } T get(NodeIt n) const { return container[n.n]; } T& operator[](NodeIt n) { return container[n.n]; } const T& operator[](NodeIt n) const { return container[n.n]; } - void update() { container.resize(G.nodeNum()); } - void update(T a) { container.resize(G.nodeNum(), a); } + void update() { container.resize(G.maxNodeId()); } + void update(T a) { container.resize(G.maxNodeId(), a); } }; template @@ -218,20 +259,102 @@ public: typedef T ValueType; typedef EdgeIt KeyType; - EdgeMap(const SmartGraph& _G) : G(_G), container(G.edgeNum()) { } + EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { } EdgeMap(const SmartGraph& _G, T a) : - G(_G), container(G.edgeNum(), a) { } + G(_G), container(G.maxEdgeId(), a) { } void set(EdgeIt e, T a) { container[e.n]=a; } T get(EdgeIt e) const { return container[e.n]; } T& operator[](EdgeIt e) { return container[e.n]; } const T& operator[](EdgeIt e) const { return container[e.n]; } - void update() { container.resize(G.edgeNum()); } - void update(T a) { container.resize(G.edgeNum(), a); } + void update() { container.resize(G.maxEdgeId()); } + void update(T a) { container.resize(G.maxEdgeId(), a); } }; + template class DynNodeMap : public DynMapBase + { + std::vector container; + public: + typedef T ValueType; + typedef NodeIt KeyType; + DynNodeMap(SmartGraph &_G) : + DynMapBase(_G), container(_G.maxNodeId()) + { + //FIXME: What if there are empty Id's? + G->dyn_node_maps.push_back(this); + } + ~DynNodeMap() + { + if(G) { + std::vector* >::iterator i; + for(i=G->dyn_node_maps.begin(); + i!=G->dyn_node_maps.end() && *i!=this; ++i) ; + if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow... + } + } + void add(const NodeIt k) + { + if(k.n>=container.size()) container.resize(k.n+1); + } + void erase(const NodeIt k) + { + //FIXME: Please implement me. + } + + void set(NodeIt n, T a) { container[n.n]=a; } + T get(NodeIt n) const { return container[n.n]; } + T& operator[](NodeIt n) { return container[n.n]; } + const T& operator[](NodeIt n) const { return container[n.n]; } + + void update() {} //Useless for DynMaps + void update(T a) {} //Useless for DynMaps + }; + + template class DynEdgeMap : public DynMapBase + { + std::vector container; + + public: + typedef T ValueType; + typedef EdgeIt KeyType; + + DynEdgeMap(SmartGraph &_G) : + DynMapBase(_G), container(_G.maxEdgeId()) + { + //FIXME: What if there are empty Id's? + //FIXME: Can I do that? : + G->dyn_edge_maps.push_back(this); + } + ~DynEdgeMap() + { + if(G) { + std::vector* >::iterator i; + for(i=G->dyn_edge_maps.begin(); + i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; + if(*i==this) G->dyn_edge_maps.erase(i); //FIXME: Way too slow... + } + } + + void add(const EdgeIt k) + { + if(k.n>=int(container.size())) container.resize(k.n+1); + } + void erase(const EdgeIt k) + { + //FIXME: Please implement me. + } + + void set(EdgeIt n, T a) { container[n.n]=a; } + T get(EdgeIt n) const { return container[n.n]; } + T& operator[](EdgeIt n) { return container[n.n]; } + const T& operator[](EdgeIt n) const { return container[n.n]; } + + void update() {} //Useless for DynMaps + void update(T a) {} //Useless for DynMaps + }; + }; } //namespace hugo