COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/lp_id.h @ 481:7afc121e0689

Last change on this file since 481:7afc121e0689 was 481:7afc121e0689, checked in by Balazs Dezso <deba@…>, 11 years ago

Port LP and MIP solvers from SVN -r3509 (#44)

File size: 3.9 KB
RevLine 
[481]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BITS_LP_SOLVER_ID_H
20#define LEMON_BITS_LP_SOLVER_ID_H
21
22namespace lemon {
23
24  namespace _lp_bits {
25
26    struct LpIdImpl {
27      std::vector<int> index;
28      std::vector<int> cross;
29      int first_index;
30      int first_free;
31    };
32
33    class LpId {
34    public:
35
36      class IdHandler {
37      public:
38        virtual ~IdHandler() {}
39        virtual int addId(LpIdImpl&) = 0;
40        virtual void eraseId(LpIdImpl&, int xn) = 0;
41      };
42
43      LpId(int min_index = 0) {
44        id_handler = 0;
45        impl.first_free = -1;
46        impl.first_index = min_index;
47        impl.cross.resize(impl.first_index);
48      }
49
50      LpId(const LpId& li) {
51        id_handler = 0;
52        impl = li.impl;
53      }
54
55      LpId& operator=(const LpId& li) {
56        id_handler = 0;
57        impl = li.impl;
58        return *this;
59      }
60
61      void setIdHandler(IdHandler& ih) {
62        id_handler = &ih;
63      }
64
65      int fixId(int fn) const {return impl.cross[fn];}
66      int floatingId(int xn) const {return impl.index[xn];}
67
68      int addId() {
69        if (id_handler == 0) {
70          int xn, fn = impl.cross.size();
71          if (impl.first_free == -1) {
72            xn = impl.index.size();
73            impl.index.push_back(fn);
74          } else {
75            xn = impl.first_free;
76            impl.first_free = impl.index[impl.first_free];
77            impl.index[xn] = fn;
78          }
79          impl.cross.push_back(xn);
80          return xn;
81        } else {
82          return id_handler->addId(impl);
83        }
84      }
85
86      void eraseId(int xn) {
87        if (id_handler == 0) {
88          int fn = impl.index[xn];
89          impl.index[xn] = impl.first_free;
90          impl.first_free = xn;
91          for(int i = fn + 1; i < int(impl.cross.size()); ++i) {
92            impl.cross[i - 1] = impl.cross[i];
93            impl.index[impl.cross[i]]--;
94          }
95          impl.cross.pop_back();
96        } else {
97          id_handler->eraseId(impl, xn);
98        }
99      }
100
101      void firstFloating(int& fn) const {
102        fn = impl.first_index;
103        if (fn == int(impl.cross.size())) fn = -1;
104      }
105
106      void nextFloating(int& fn) const {
107        ++fn;
108        if (fn == int(impl.cross.size())) fn = -1;
109      }
110
111      void firstFix(int& xn) const {
112        int fn;
113        firstFloating(fn);
114        xn = fn != -1 ? fixId(fn) : -1;
115      }
116
117      void nextFix(int& xn) const {
118        int fn = floatingId(xn);
119        nextFloating(fn);
120        xn = fn != -1 ? fixId(fn) : -1;
121      }
122
123    protected:
124      LpIdImpl impl;
125      IdHandler *id_handler;
126    };
127
128    class RelocateIdHandler : public LpId::IdHandler {
129    public:
130
131      virtual int addId(LpIdImpl& impl) {
132        int xn, fn = impl.cross.size();
133        if (impl.first_free == -1) {
134          xn = impl.index.size();
135          impl.index.push_back(fn);
136        } else {
137          xn = impl.first_free;
138          impl.first_free = impl.index[impl.first_free];
139          impl.index[xn] = fn;
140        }
141        impl.cross.push_back(xn);
142        return xn;
143      }
144
145      virtual void eraseId(LpIdImpl& impl, int xn) {
146        int fn = impl.index[xn];
147        impl.index[xn] = impl.first_free;
148        impl.first_free = xn;
149        impl.cross[fn] = impl.cross.back();
150        impl.index[impl.cross.back()] = fn;
151        impl.cross.pop_back();
152      }
153    };
154  }
155}
156
157#endif
Note: See TracBrowser for help on using the repository browser.