graph_def.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 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #define SCIP_Debug
36 
37 #ifndef GCG_GRAPH_DEF_H_
38 #define GCG_GRAPH_DEF_H_
39 
40 #include "scip/scip.h"
41 #include "graph.h"
42 
43 namespace gcg {
44 
45 template <class T>
47  SCIP* scip
48 ) : name("graph"),scip_(scip),graph(NULL),nconss(0),nvars(0),nnonzeroes(0),dummynodes(0)
49 {
50  graph = new T();
51 }
52 
53 template <class T>
55 {
56  if(graph != NULL)
57  delete graph;
58 
59 }
60 
61 template <class T>
62 SCIP_RETCODE Graph<T>::addNNodes(int _n_nodes)
63 {
64  return graph->addNNodes(_n_nodes);
65 }
66 
67 template <class T>
68 SCIP_RETCODE Graph<T>::addNNodes(int _n_nodes, std::vector<int> weights)
69 {
70  return graph->addNNodes(_n_nodes, weights);
71 }
72 
73 template <class T>
75  return graph->getNNodes();
76 }
77 
78 template <class T>
80  return graph->getNEdges();
81 }
82 
83 template <class T>
84 SCIP_RETCODE Graph<T>::getEdges(std::vector<void*>& edges)
85 {
86  return graph->getEdges(edges);
87 }
88 
89 template <class T>
90 SCIP_RETCODE Graph<T>::addNode(int i,int weight)
91 {
92  SCIP_CALL( graph->addNode(i, weight) );
93  return SCIP_OKAY;
94 }
95 
96 template <class T>
97 SCIP_RETCODE Graph<T>::addNode()
98 {
99  SCIP_CALL( graph->addNode() );
100  return SCIP_OKAY;
101 }
102 
104 template <class T>
105 SCIP_RETCODE Graph<T>::addEdge(int i, int j)
106 {
107  SCIP_CALL( graph->addEdge(i, j) );
108  return SCIP_OKAY;
109 }
110 
111 template <class T>
112 SCIP_RETCODE Graph<T>::flush()
113 {
114  SCIP_CALL( graph->flush() );
115  return SCIP_OKAY;
116 }
117 
118 template <class T>
119 SCIP_RETCODE Graph<T>::normalize()
120 {
121  SCIP_CALL( graph->normalize() );
122  return SCIP_OKAY;
123 }
124 
125 template <class T>
126 int Graph<T>::edge(int i, int j) {
127  assert( i>= 0);
128  assert(j >= 0);
129 
130  //int edge_ij=0;
131 
132  //return tcliqueIsEdge(tgraph,i,j);
133 
134  int edge_ij=0;
135  std::vector<int> Neighbors;
136 
137  Neighbors = getNeighbors(i);
138  for(int k=0; k<(int)Neighbors.size(); k++)
139  {
140  if(Neighbors[k] == j)
141  {
142  edge_ij = 1;
143  k = (int)Neighbors.size();
144  }
145  }
146  return edge_ij;
147 }
148 
149 template <class T>
151  assert( i >= 0);
152  return graph->getNNeighbors(i);
153 }
154 
155 template <class T>
156 std::vector<int> Graph<T>::getNeighbors(int i) {
157  assert(i >= 0);
158 
159  return graph->getNeighbors(i);
160 }
161 
162 template <class T>
163 void Graph<T>::setPartition(int i, int ID) {
164  partition.resize(getNNodes(), -1);
165  partition[i] = ID;
166 }
167 
169 template <class T>
171  int fd,
172  SCIP_Bool writeweights
173  )
174 {
175  int nnodes;
176  int nedges;
177  FILE* file;
178  file = fdopen(fd, "wx");
179  if( file == NULL )
180  return SCIP_FILECREATEERROR;
181 
182  nnodes = Graph<T>::getNNodes();
183  nedges = Graph<T>::getNEdges();
184 
185  SCIPinfoMessage(scip_, file, "%d %d\n", nnodes+dummynodes, nedges/2);
186 
187  for( int i = 0; i < nnodes; ++i )
188  {
189  int nneighbors = Graph<T>::getNNeighbors(i);
190  std::vector<int> neighbors = Graph<T>::getNeighbors(i);
191 
192  if( writeweights )
193  {
194  SCIPinfoMessage(scip_, file, "%d ", Graph<T>::getWeight(i));
195  }
196  for( int j = 0; j < nneighbors; ++j )
197  {
198  SCIPinfoMessage(scip_, file, "%d ", neighbors[j]+1);
199  }
200  SCIPinfoMessage(scip_, file, "\n");
201  }
202 
203  for( int i = 0; i < dummynodes; ++i )
204  {
205  SCIPinfoMessage(scip_, file, "\n");
206  }
207 
208  return SCIP_OKAY;
209 }
210 
212 /*template <class T>
213 SCIP_RETCODE Graph<T>::writeToFile(
214  int fd,
215  SCIP_Bool writeweights
216  )
217 {
218  int nnodes;
219  int nedges;
220  FILE* file;
221  file = fdopen(fd, "wx");
222  if( file == NULL )
223  return SCIP_FILECREATEERROR;
224 
225  nnodes = Graph<T>::getNNodes();
226  nedges = Graph<T>::getNEdges();
227 
228  SCIPinfoMessage(scip_, file, "%d %d\n", nnodes, nedges);
229 
230  for( int i = 0; i < nnodes; ++i )
231  {
232  SCIPinfoMessage(scip_, file, "node %d :\n ", i);
233  //int nneighbors = Graph<T>::getNNeighbors(i);
234  //int nneighbors = Graph<T>::getNNeighbors(i);
235  std::vector<int> neighbors = Graph<T>::getNeighbors(i);
236  //assert(nneighbors == (int)neighbors.size());
237 
238  for( int j : neighbors)
239  {
240  double w = Graph<T>::getEdgeWeight(i,j);
241  SCIPinfoMessage(scip_, file, "(%d, w= %.10f) ", j, w);
242  }
243  SCIPinfoMessage(scip_, file, "\n");
244  }
245 
246 
247  return SCIP_OKAY;
248 }*/
249 
251 template <class T>
253  const char* filename
254 )
255 {
256  ifstream input(filename);
257  if( !input.good() )
258  {
259  SCIPerrorMessage("Could not open file <%s> for reading\n", filename);
260  return SCIP_READERROR;
261  }
262  partition.resize(getNNodes(), -1);
263  for( int i = 0; i < getNNodes(); ++i )
264  {
265  int part = 0;
266  if( !(input >> part) )
267  {
268  SCIPerrorMessage("Could not read from file <%s>. It may be in the wrong format\n", filename);
269  return SCIP_READERROR;
270  }
271  partition[i] = part;
272  }
273 
274  input.close();
275  return SCIP_OKAY;
276 }
277 
279 template <class T>
281  int i
282  )
283 {
284  return graph->graphGetWeights(i);
285 }
286 
287 
289 template <class T>
290 SCIP_RETCODE Graph<T>::addEdge(int i, int j, double weight)
291 {
292  SCIP_CALL( graph->addEdge(i, j, weight) );
293  return SCIP_OKAY;
294 }
295 
297 template <class T>
298 SCIP_RETCODE Graph<T>::setEdge(int i, int j, double weight)
299 {
300  SCIP_CALL( graph->setEdge(i, j, weight) );
301  return SCIP_OKAY;
302 }
303 
305 template <class T>
306 double Graph<T>::getEdgeWeight(int i, int j)
307 {
308  return graph->getEdgeWeight(i, j);
309 }
310 
311 template <class T>
312 std::vector<std::pair<int, double> > Graph<T>::getNeighborWeights(int i)
313 {
314  return graph->getNeighborWeights(i);
315 }
316 
317 
318 template <class T>
320 {
321  return graph->getEdgeWeightPercentile(q);
322 }
323 
324 
325 
326 #ifdef WITH_GSL
327 
328 template <class T>
329 void Graph<T>::expand(int factor)
330 {
331  graph->expand(factor);
332 }
333 
334 template <class T>
335 void Graph<T>::inflate(double factor)
336 {
337  graph->inflate(factor);
338 }
339 
340 template <class T>
341 void Graph<T>::colL1Norm()
342 {
343  graph->colL1Norm();
344 }
345 
346 template <class T>
347 void Graph<T>::prune()
348 {
349  graph->prune();
350 }
351 
352 template <class T>
353 bool Graph<T>::stopMCL(int iter)
354 {
355  return graph->stopMCL(iter);
356 }
357 
358 template <class T>
359 std::vector<int> Graph<T>::getClustersMCL()
360 {
361  return graph->getClustersMCL();
362 }
363 
364 
365 template <class T>
366 void Graph<T>::initMCL()
367 {
368  graph->initMCL();
369 }
370 
371 template <class T>
372 void Graph<T>::clearMCL()
373 {
374  graph->clearMCL();
375 }
376 
377 
378 
379 #endif
380 
381 
382 } /* namespace gcg */
383 
384 #endif
virtual SCIP_RETCODE setEdge(int i, int j, double weight)=0
virtual SCIP_RETCODE addEdge(int i, int j, double weight)=0
virtual SCIP_RETCODE addNNodes(int _n_nodes)=0
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
virtual SCIP_RETCODE normalize()=0
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
virtual double getEdgeWeight(int i, int j)=0
SCIP_RETCODE addNode()
Definition: graph_def.h:97
virtual int getNNeighbors(int i)=0
virtual SCIP_RETCODE getEdges(std::vector< void * > &edges)=0
SCIP_RETCODE normalize()
Definition: graph_def.h:119
virtual std::vector< int > getNeighbors(int i)=0
virtual double getEdgeWeightPercentile(double q)=0
SCIP_RETCODE setEdge(int i, int j, double weight)
Definition: graph_def.h:298
virtual int getNNodes()=0
virtual ~Graph()
Definition: graph_def.h:54
virtual SCIP_RETCODE addNode(int i, int weight)=0
virtual SCIP_RETCODE flush()=0
virtual int getNEdges()=0
SCIP_RETCODE addEdge(int i, int j)
Definition: graph_def.h:105
std::vector< std::pair< int, double > > getNeighborWeights(int i)
Definition: graph_def.h:312
int getNEdges()
Definition: graph_def.h:79
miscellaneous graph methods for structure detection
Bridge * graph
Definition: graph.h:58
virtual std::vector< std::pair< int, double > > getNeighborWeights(int i)
Definition: bridge.h:89
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
int dummynodes
Definition: graph.h:62
int getNNodes()
Definition: graph_def.h:74
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
virtual int graphGetWeights(int i)=0
virtual int edge(int i, int j)
Definition: graph_def.h:126