graph.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 
37 
38 #ifndef GCG_GRAPH_H_
39 #define GCG_GRAPH_H_
40 #include "objscip/objscip.h"
41 #include "tclique/tclique.h"
42 #include "weights.h"
43 #include "pub_decomp.h"
44 #include "bridge.h"
45 #include "graph_interface.h"
46 #include <exception>
47 #include <vector>
48 #include <string>
49 
50 namespace gcg {
51 
52 template <class T>
53 class Graph : public GraphInterface {
54 public:
55  std::string name;
56 protected:
57  SCIP* scip_;
59  int nconss;
60  int nvars;
63 
64 public:
66  Graph(
67  SCIP* scip
68  );
69 
70  void swap(Graph & other) // the swap member function (should never fail!)
71  {
72  // swap all the members (and base subobject, if applicable) with other
73  std::swap(partition, other.partition);
74  std::swap(scip_ , other.scip_);
75  std::swap(graph , other.graph);
76  std::swap(nconss , other.nconss);
77  std::swap(nvars , other.nvars);
78  std::swap(nnonzeroes , other.nnonzeroes);
79  std::swap(dummynodes, other.dummynodes);
80  }
81 
82  Graph& operator=(Graph other) // note: argument passed by value!
83  {
84  // swap this with other
85  swap(other);
86 
87  return *this;
88  }
89 
91  virtual ~Graph();
92 
94  SCIP_RETCODE addNNodes(int _n_nodes);
95 
97  SCIP_RETCODE addNNodes(int _n_nodes, std::vector<int> weights);
98 
100  SCIP_RETCODE addNode(int i,int weight);
101 
103  SCIP_RETCODE addNode();
104 
106  SCIP_RETCODE addEdge(int i, int j);
107 
109  SCIP_RETCODE addEdge(int i, int j, double weight);
110 
112  SCIP_RETCODE setEdge(int i, int j, double weight);
113 
115  double getEdgeWeight(int i, int j);
116 
117  std::vector<std::pair<int, double> > getNeighborWeights(int i);
118 
120  int getNNodes();
121 
123  int getNEdges();
124 
126  SCIP_RETCODE getEdges(std::vector<void*>& edges);
127 
129  virtual int edge(int i, int j);
130 
132  virtual int getNNeighbors(
133  int i
134  );
135 
137  virtual std::vector<int> getNeighbors(
138  int i
139  );
140 
142  virtual void setPartition(int i, int ID);
143 
145  virtual SCIP_RETCODE createFromMatrix(
146  SCIP_CONS** conss,
147  SCIP_VAR** vars,
148  int nconss_,
149  int nvars_
150  ) { return SCIP_ERROR; }
151 
155  virtual SCIP_RETCODE writeToFile(
156  int fd,
157  SCIP_Bool writeweights
158  );
159 
160 
165  virtual SCIP_RETCODE readPartition(
166  const char* filename
167  );
168 
169  int getNNonzeroes() const
170  {
171  return nnonzeroes;
172  }
173 
175  virtual int getWeight(
176  int i
177  );
178 
180  void setDummynodes(int dummynodes_)
181  {
182  dummynodes = dummynodes_;
183  }
184 
185  int getDummynodes() const
186  {
187  return dummynodes;
188  }
189 
190  SCIP_RETCODE flush();
191 
192  SCIP_RETCODE normalize();
193 
194  virtual double getEdgeWeightPercentile(double q);
195 
196 #ifdef WITH_GSL
197 
198  virtual void expand(int factor);
199 
201  virtual void inflate(double factor);
202 
204  virtual void colL1Norm();
205 
207  virtual void prune();
208 
210  virtual bool stopMCL(int iter);
211 
213  virtual std::vector<int> getClustersMCL();
214 
216  virtual void initMCL();
217 
219  virtual void clearMCL();
220 #endif
221 
222 };
223 
224 }
225 
226 #endif
int getNNonzeroes() const
Definition: graph.h:169
virtual SCIP_RETCODE writeToFile(int fd, SCIP_Bool writeweights)
Definition: graph_def.h:170
SCIP_RETCODE addNNodes(int _n_nodes)
Definition: graph_def.h:62
int nnonzeroes
Definition: graph.h:61
Graph(SCIP *scip)
Definition: graph_def.h:46
virtual void setPartition(int i, int ID)
Definition: graph_def.h:163
virtual double getEdgeWeightPercentile(double q)
Definition: graph_def.h:319
SCIP_RETCODE flush()
Definition: graph_def.h:112
int nconss
Definition: graph.h:59
SCIP_RETCODE addNode()
Definition: graph_def.h:97
weight class for graphs
SCIP_RETCODE normalize()
Definition: graph_def.h:119
virtual SCIP_RETCODE createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_)
Definition: graph.h:145
void setDummynodes(int dummynodes_)
Definition: graph.h:180
SCIP_RETCODE setEdge(int i, int j, double weight)
Definition: graph_def.h:298
virtual ~Graph()
Definition: graph_def.h:54
void swap(Graph &other)
Definition: graph.h:70
SCIP_RETCODE addEdge(int i, int j)
Definition: graph_def.h:105
int getDummynodes() const
Definition: graph.h:185
std::vector< std::pair< int, double > > getNeighborWeights(int i)
Definition: graph_def.h:312
int getNEdges()
Definition: graph_def.h:79
Bridge * graph
Definition: graph.h:58
miscellaneous graph interface methods
Graph & operator=(Graph other)
Definition: graph.h:82
virtual SCIP_RETCODE readPartition(const char *filename)
Definition: graph_def.h:252
double getEdgeWeight(int i, int j)
Definition: graph_def.h:306
SCIP * scip_
Definition: graph.h:57
std::string name
Definition: graph.h:55
int dummynodes
Definition: graph.h:62
int getNNodes()
Definition: graph_def.h:74
int nvars
Definition: graph.h:60
SCIP_RETCODE getEdges(std::vector< void * > &edges)
Definition: graph_def.h:84
virtual int getNNeighbors(int i)
Definition: graph_def.h:150
virtual std::vector< int > getNeighbors(int i)
Definition: graph_def.h:156
virtual int getWeight(int i)
Definition: graph_def.h:280
std::vector< int > partition
bridge
public methods for working with decomposition structures
virtual int edge(int i, int j)
Definition: graph_def.h:126