COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/solver_bits.h @ 482:ed54c0d13df0

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

Thorough redesign of the LP/MIP interface (#44)

  • Redesigned class structure
  • Redesigned iterators
  • Some functions in the basic interface redesigned
  • More complete setting functions
  • Ray retrieving functions
  • Lot of improvements
  • Cplex common env
  • CLP macro definition to config.h.in
  • Update lp.h to also use soplex and clp
  • Remove default_solver_name
  • New solverName() function in solvers
  • Handle exceptions for MipCplex? test
  • Rename tolerance parameter to epsilon
  • Rename MapIt? to CoeffIt?
  • Lot of documentation improvements
  • Various bugfixes
File size: 4.5 KB
Line 
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_SOLVER_BITS_H
20#define LEMON_BITS_SOLVER_BITS_H
21
22namespace lemon {
23
24  namespace _solver_bits {
25
26    class VarIndex {
27    private:
28      struct ItemT {
29        int prev, next;
30        int index;
31      };
32      std::vector<ItemT> items;
33      int first_item, last_item, first_free_item;
34
35      std::vector<int> cross;
36
37    public:
38
39      VarIndex()
40        : first_item(-1), last_item(-1), first_free_item(-1) {
41      }
42
43      void clear() {
44        first_item = -1;
45        first_free_item = -1;
46        items.clear();
47        cross.clear();
48      }
49
50      int addIndex(int idx) {
51        int n;
52        if (first_free_item == -1) {
53          n = items.size();
54          items.push_back(ItemT());
55        } else {
56          n = first_free_item;
57          first_free_item = items[n].next;
58          if (first_free_item != -1) {
59            items[first_free_item].prev = -1;
60          }
61        }
62        items[n].index = idx;
63        if (static_cast<int>(cross.size()) <= idx) {
64          cross.resize(idx + 1, -1);
65        }
66        cross[idx] = n;
67
68        items[n].prev = last_item;
69        items[n].next = -1;
70        if (last_item != -1) {
71          items[last_item].next = n;
72        } else {
73          first_item = n;
74        }
75        last_item = n;
76
77        return n;
78      }
79
80      int addIndex(int idx, int n) {
81        while (n >= static_cast<int>(items.size())) {
82          items.push_back(ItemT());
83          items.back().prev = -1;
84          items.back().next = first_free_item;
85          if (first_free_item != -1) {
86            items[first_free_item].prev = items.size() - 1;
87          }
88          first_free_item = items.size() - 1;
89        }
90        if (items[n].next != -1) {
91          items[items[n].next].prev = items[n].prev;
92        }
93        if (items[n].prev != -1) {
94          items[items[n].prev].next = items[n].next;
95        } else {
96          first_free_item = items[n].next;
97        }
98
99        items[n].index = idx;
100        if (static_cast<int>(cross.size()) <= idx) {
101          cross.resize(idx + 1, -1);
102        }
103        cross[idx] = n;
104
105        items[n].prev = last_item;
106        items[n].next = -1;
107        if (last_item != -1) {
108          items[last_item].next = n;
109        } else {
110          first_item = n;
111        }
112        last_item = n;
113
114        return n;
115      }
116
117      void eraseIndex(int idx) {
118        int n = cross[idx];
119
120        if (items[n].prev != -1) {
121          items[items[n].prev].next = items[n].next;
122        } else {
123          first_item = items[n].next;
124        }
125        if (items[n].next != -1) {
126          items[items[n].next].prev = items[n].prev;
127        } else {
128          last_item = items[n].prev;
129        }
130
131        if (first_free_item != -1) {
132          items[first_free_item].prev = n;
133        }
134        items[n].next = first_free_item;
135        items[n].prev = -1;
136        first_free_item = n;
137
138        while (!cross.empty() && cross.back() == -1) {
139          cross.pop_back();
140        }
141      }
142
143      int maxIndex() const {
144        return cross.size() - 1;
145      }
146
147      void shiftIndices(int idx) {
148        for (int i = idx + 1; i < static_cast<int>(cross.size()); ++i) {
149          cross[i - 1] = cross[i];
150          if (cross[i] != -1) {
151            --items[cross[i]].index;
152          }
153        }
154        cross.back() = -1;
155        cross.pop_back();
156        while (!cross.empty() && cross.back() == -1) {
157          cross.pop_back();
158        }
159      }
160
161      void relocateIndex(int idx, int jdx) {
162        cross[idx] = cross[jdx];
163        items[cross[jdx]].index = idx;
164        cross[jdx] = -1;
165
166        while (!cross.empty() && cross.back() == -1) {
167          cross.pop_back();
168        }
169      }
170
171      int operator[](int idx) const {
172        return cross[idx];
173      }
174
175      int operator()(int fdx) const {
176        return items[fdx].index;
177      }
178
179      void firstItem(int& fdx) const {
180        fdx = first_item;
181      }
182
183      void nextItem(int& fdx) const {
184        fdx = items[fdx].next;
185      }
186
187    };
188  }
189}
190
191#endif
Note: See TracBrowser for help on using the repository browser.