COIN-OR::LEMON - Graph Library

Changeset 108:0351b00fd283 in lemon-0.x for src


Ignore:
Timestamp:
02/20/04 23:01:02 (16 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@143
Message:

Dynamic Maps added.

Location:
src/work/alpar
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/f_ed_ka.h

    r95 r108  
    1212//#include <bfs_iterator.hh>
    1313
    14 namespace marci {
     14namespace hugo {
    1515  template <typename Graph, typename FlowMap, typename CapacityMap>
    1616  typename FlowMap::ValueType maxFlow(Graph &G,
     
    115115  }
    116116 
    117 } // namespace marci
     117} // namespace hugo
    118118
    119119#endif //EDMONDS_KARP_HH
  • src/work/alpar/f_ed_ka_demo.cc

    r103 r108  
    99#include "../marci/time_measure.h"
    1010
    11 using namespace marci;
     11using namespace hugo;
    1212
    1313// Use a DIMACS max flow file as stdin.
     
    1515
    1616int main(int, char **) {
    17   //  typedef SmartGraph Graph;
    18   typedef ListGraph Graph;
     17  typedef SmartGraph Graph;
     18  //typedef ListGraph Graph;
    1919
    2020  typedef Graph::NodeIt NodeIt;
     
    2424  Graph G;
    2525  NodeIt s, t;
    26   Graph::EdgeMap<int> cap(G);
     26  Graph::DynEdgeMap<int> cap(G);
    2727  readDimacsMaxFlow(std::cin, G, s, t, cap);
    2828
    2929  std::cout << "edmonds karp demo..." << std::endl;
    30   Graph::EdgeMap<int> flow(G); //0 flow
     30  Graph::DynEdgeMap<int> flow(G); //0 flow
    3131 
    3232  int ret;
  • src/work/alpar/smart_graph.h

    r105 r108  
    2828    std::vector<EdgeT> edges;
    2929   
     30    template <typename Key> class DynMapBase
     31    {
     32    protected:
     33      SmartGraph* G;
     34    public:
     35      virtual void add(const Key k) = NULL;
     36      virtual void erase(const Key k) = NULL;
     37      DynMapBase(SmartGraph &_G) : G(&_G) {}
     38      virtual ~DynMapBase() {}
     39      friend class SmartGraph;
     40    };
    3041
    3142  public:
     43    template <typename T> class DynEdgeMap;
     44    template <typename T> class DynEdgeMap;
    3245
    3346    class NodeIt;
     47    class EdgeIt;
     48
     49  protected:
     50    std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
     51    std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
     52   
     53  public:
     54
    3455    class EachNodeIt;
    35     class EdgeIt;
    3656    class EachEdgeIt;
    3757    class OutEdgeIt;
     
    5575    SmartGraph() : nodes(), edges() { }
    5676   
    57     ~SmartGraph() {}
     77    ~SmartGraph()
     78    {
     79      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
     80          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
     81      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
     82          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
     83    }
    5884
    5985    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
    6086    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
    6187
     88    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
     89    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
     90
     91   
    6292    NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
    6393    NodeIt head(EdgeIt e) const { return edges[e.n].head; }
     
    115145      NodeIt n; n.n=nodes.size();
    116146      nodes.push_back(NodeT()); //FIXME: Hmmm...
     147
     148      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
     149          i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
     150
    117151      return n;
    118152    }
     153   
    119154    EdgeIt addEdge(NodeIt u, NodeIt v) {
    120155      EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
     
    123158      edges[e.n].next_in=nodes[v.n].first_in;
    124159      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
     160
     161      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
     162          i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);
     163
    125164      return e;
    126165    }
     
    131170      friend class SmartGraph;
    132171      template <typename T> friend class NodeMap;
     172      template <typename T> friend class DynNodeMap;
    133173     
    134174      friend class EdgeIt;
     
    157197      friend class SmartGraph;
    158198      template <typename T> friend class EdgeMap;
     199      template <typename T> friend class DynEdgeMap;
    159200     
    160201      friend class NodeIt;
     
    201242      typedef T ValueType;
    202243      typedef NodeIt KeyType;
    203       NodeMap(const SmartGraph& _G) : G(_G), container(G.nodeNum()) { }
     244      NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
    204245      NodeMap(const SmartGraph& _G, T a) :
    205         G(_G), container(G.nodeNum(), a) { }
     246        G(_G), container(G.maxNodeId(), a) { }
    206247      void set(NodeIt n, T a) { container[n.n]=a; }
    207248      T get(NodeIt n) const { return container[n.n]; }
    208249      T& operator[](NodeIt n) { return container[n.n]; }
    209250      const T& operator[](NodeIt n) const { return container[n.n]; }
    210       void update() { container.resize(G.nodeNum()); }
    211       void update(T a) { container.resize(G.nodeNum(), a); }
     251      void update() { container.resize(G.maxNodeId()); }
     252      void update(T a) { container.resize(G.maxNodeId(), a); }
    212253    };
    213254
     
    219260      typedef T ValueType;
    220261      typedef EdgeIt KeyType;
    221       EdgeMap(const SmartGraph& _G) : G(_G), container(G.edgeNum()) { }
     262      EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
    222263      EdgeMap(const SmartGraph& _G, T a) :
    223         G(_G), container(G.edgeNum(), a) { }
     264        G(_G), container(G.maxEdgeId(), a) { }
    224265      void set(EdgeIt e, T a) { container[e.n]=a; }
    225266      T get(EdgeIt e) const { return container[e.n]; }
    226267      T& operator[](EdgeIt e) { return container[e.n]; }
    227268      const T& operator[](EdgeIt e) const { return container[e.n]; }
    228       void update() { container.resize(G.edgeNum()); }
    229       void update(T a) { container.resize(G.edgeNum(), a); }
    230     };
    231 
    232 
    233 
    234 
     269      void update() { container.resize(G.maxEdgeId()); }
     270      void update(T a) { container.resize(G.maxEdgeId(), a); }
     271    };
     272
     273    template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
     274    {
     275      std::vector<T> container;
     276
     277    public:
     278      typedef T ValueType;
     279      typedef NodeIt KeyType;
     280
     281      DynNodeMap(SmartGraph &_G) :
     282        DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
     283      {
     284        //FIXME: What if there are empty Id's?
     285        G->dyn_node_maps.push_back(this);
     286      }
     287      ~DynNodeMap()
     288      {
     289        if(G) {
     290          std::vector<DynMapBase<NodeIt>* >::iterator i;
     291          for(i=G->dyn_node_maps.begin();
     292              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
     293          if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
     294        }
     295      }
     296
     297      void add(const NodeIt k)
     298      {
     299        if(k.n>=container.size()) container.resize(k.n+1);
     300      }
     301      void erase(const NodeIt k)
     302      {
     303        //FIXME: Please implement me.
     304      }
     305     
     306      void set(NodeIt n, T a) { container[n.n]=a; }
     307      T get(NodeIt n) const { return container[n.n]; }
     308      T& operator[](NodeIt n) { return container[n.n]; }
     309      const T& operator[](NodeIt n) const { return container[n.n]; }
     310
     311      void update() {}    //Useless for DynMaps
     312      void update(T a) {}  //Useless for DynMaps
     313    };
     314   
     315    template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
     316    {
     317      std::vector<T> container;
     318
     319    public:
     320      typedef T ValueType;
     321      typedef EdgeIt KeyType;
     322
     323      DynEdgeMap(SmartGraph &_G) :
     324        DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
     325      {
     326        //FIXME: What if there are empty Id's?
     327        //FIXME: Can I do that? :
     328        G->dyn_edge_maps.push_back(this);
     329      }
     330      ~DynEdgeMap()
     331      {
     332        if(G) {
     333          std::vector<DynMapBase<EdgeIt>* >::iterator i;
     334          for(i=G->dyn_edge_maps.begin();
     335              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
     336          if(*i==this) G->dyn_edge_maps.erase(i); //FIXME: Way too slow...
     337        }
     338      }
     339
     340      void add(const EdgeIt k)
     341      {
     342        if(k.n>=int(container.size())) container.resize(k.n+1);
     343      }
     344      void erase(const EdgeIt k)
     345      {
     346        //FIXME: Please implement me.
     347      }
     348     
     349      void set(EdgeIt n, T a) { container[n.n]=a; }
     350      T get(EdgeIt n) const { return container[n.n]; }
     351      T& operator[](EdgeIt n) { return container[n.n]; }
     352      const T& operator[](EdgeIt n) const { return container[n.n]; }
     353
     354      void update() {}    //Useless for DynMaps
     355      void update(T a) {}  //Useless for DynMaps
     356    };
     357       
    235358  };
    236359} //namespace hugo
Note: See TracChangeset for help on using the changeset viewer.