Scippy

GCG

Branch-and-Price & Column Generation for Everyone

hypergraph_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-2021 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 
28 /**@file hypergraph_def.h
29  * @brief miscellaneous hypergraph methods for structure detection
30  * @author Martin Bergner
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 
36 #ifndef GCG_HYPERGRAPH_DEF_H_
37 #define GCG_HYPERGRAPH_DEF_H_
38 
39 #include "scip/scip.h"
40 #include "hypergraph.h"
41 
42 namespace gcg {
43 
44 template <class T>
46  SCIP* scip /**< SCIP data structure */
47 ) : name("hypergraph"),scip_(scip),graph(NULL),lastnode(0),dummynodes(0)
48 {
49  SCIPdebugMessage("Creating graph\n");
50  graph = new Graph<T>(scip);
51 }
52 
53 template <class T>
55 {
56  if(graph != NULL)
57  delete graph;
58 
59 }
60 
61 template <class T>
63 {
64  int nodeid;
65  if( i < (int) nodes.size())
66  nodeid = nodes[i];
67  else
68  nodeid = lastnode;
69 
70  SCIPdebugMessage("Nodeid %d is %d\n", i, nodeid);
71  return nodeid;
72 }
73 
74 template <class T>
75 SCIP_RETCODE Hypergraph<T>::addNode(int i,int weight)
76 {
77  int nodeid = lastnode;
78  SCIPdebugMessage("Adding node %d (id=%d)\n", i, nodeid);
79  SCIP_CALL( graph->addNode(nodeid, weight) );
80  nodes.push_back(nodeid);
81  mapping.resize(nodeid+1);
82  mapping[nodeid] = i;
83  ++lastnode;
84  return SCIP_OKAY;
85 }
86 
87 /** adds the edge to the graph */
88 template <class T>
89 SCIP_RETCODE Hypergraph<T>::addHyperedge(std::vector<int> &edge, int weight)
90 {
91  int edgenodeid = lastnode;
92  ++lastnode;
93  SCIPdebugMessage("Adding hyperedge %lu (id=%d)\n", hedges.size(), edgenodeid);
94  SCIP_CALL( graph->addNode(edgenodeid, weight) );
95 
96  for( size_t i = 0; i < edge.size(); ++i )
97  {
98  SCIP_CALL( graph->addEdge(edgenodeid, computeNodeId(edge[i])) );
99  }
100  hedges.push_back(edgenodeid);
101  mapping.resize(edgenodeid+1);
102  mapping[edgenodeid] = hedges.size()-1;
103  return SCIP_OKAY;
104 }
105 
106 /** adds the edge to the graph */
107 template <class T>
108 SCIP_RETCODE Hypergraph<T>::addNodeToHyperedge(int node, int hedge)
109 {
110  int edgenodeid = hedges[hedge];
111  int nodeid = nodes[node];
112  SCIP_CALL( graph->addEdge(edgenodeid, nodeid) );
113 
114  return SCIP_OKAY;
115 }
116 
117 
118 template <class T>
120  return nodes.size();
121 }
122 
123 template <class T>
125  return hedges.size();
126 }
127 
128 template <class T>
130  assert( i >= 0);
131  return graph->getNNeighbors(i);
132 }
133 
134 template <class T>
135 std::vector<int> Hypergraph<T>::getNeighbors(int i) {
136  assert(i >= 0);
137  int nodeid = computeNodeId(i);
138  std::vector<int> edges = graph->getNeighbors(nodeid);
139 
140  std::set<int> neighbors;
141  for( size_t j = 0; j < edges.size(); ++j )
142  {
143  std::vector<int> tempneighbors = graph->getNeighbors(edges[j]);
144  neighbors.insert(tempneighbors.begin(), tempneighbors.end());
145  }
146  std::vector<int> r(neighbors.begin(), neighbors.end());
147  for( size_t j = 0; j < r.size(); ++j)
148  {
149  r[j] = mapping[r[j]];
150  }
151  std::vector<int>::iterator it = std::remove(r.begin(), r.end(), nodeid);
152 
153  return std::vector<int>(r.begin(), it);
154 }
155 
156 template <class T>
158  int i
159  )
160 {
161  std::vector<int> hnodes = graph->getNeighbors(hedges[i]);
162  for( size_t j = 0; j < hnodes.size(); ++j)
163  {
164  hnodes[j] = computeNodeId(hnodes[j]);
165  }
166  return hnodes;
167 }
168 
169 template <class T>
171  int i
172  )
173 {
174  return graph->getNNeighbors(hedges[i]);
175 }
176 
177 template <class T>
178 void Hypergraph<T>::setPartition(int i, int ID) {
179  partition.resize(getNNodes(), -1);
180  partition[i] = ID;
181 }
182 
183 /** write the hypergraph to a file */
184 template <class T>
186  int fd, /**< filename where the graph should be written to */
187  SCIP_Bool writeweights
188  )
189 {
190  FILE* file;
191  file = fdopen(fd, "w");
192  if( file == NULL )
193  return SCIP_FILECREATEERROR;
194 
195  SCIPinfoMessage(scip_, file, "%ld %ld\n", nodes.size()+dummynodes, hedges.size());
196 
197  for( size_t i = 0; i < hedges.size(); ++i )
198  {
199  int nneighbors = graph->getNNeighbors(hedges[i]);
200  std::vector<int> neighbors = graph->getNeighbors(hedges[i]);
201 
202  if( writeweights )
203  {
204  SCIPinfoMessage(scip_, file, "%d ", graph->getWeight(i));
205  }
206  for( int j = 0; j < nneighbors; ++j )
207  {
208  SCIPinfoMessage(scip_, file, "%d ", computeNodeId(neighbors[j])+1);
209  }
210  SCIPinfoMessage(scip_, file, "\n");
211  }
212 
213  return SCIP_OKAY;
214 }
215 
216 /** read in the partition from a file */
217 template <class T>
219  const char* filename
220 )
221 {
222  ifstream input(filename);
223  if( !input.good() )
224  {
225  SCIPerrorMessage("Could not open file <%s> for reading\n", filename);
226  return SCIP_READERROR;
227  }
228  partition.resize(getNNodes(), -1);
229  for( int i = 0; i < getNNodes(); ++i )
230  {
231  int part = 0;
232  if( !(input >> part) )
233  {
234  SCIPerrorMessage("Could not read from file <%s>. It may be in the wrong format\n", filename);
235  return SCIP_READERROR;
236  }
237  partition[i] = part;
238  }
239 
240  input.close();
241  return SCIP_OKAY;
242 }
243 
244 /** return the weight of given node */
245 template <class T>
247  int i /**< the given node */
248  )
249 {
250  return graph->getWeight(i);
251 }
252 
253 /** return the weight of given hyperedge */
254 template <class T>
256  int i /**< the given hyperedge */
257  )
258 {
259  int edgenodeid = hedges[i];
260 
261  return graph->getWeight(edgenodeid);
262 }
263 
264 template <class T>
265 SCIP_RETCODE Hypergraph<T>::flush()
266 {
267  SCIP_CALL( graph->flush() );
268  return SCIP_OKAY;
269 }
270 
271 } /* namespace gcg */
272 
273 #endif
int getHyperedgeWeight(int i)
std::vector< int > getNeighbors(int i)
SCIP_RETCODE addNodeToHyperedge(int node, int hedge)
void setPartition(int i, int ID)
static SCIP_RETCODE partition(SCIP *scip, SCIP_VAR **J, int *Jsize, SCIP_Longint *priority, SCIP_VAR **F, int Fsize, SCIP_VAR **origvar, SCIP_Real *median)
SCIP_RETCODE flush()
int getNHyperedgeNodes(int i)
Graph< T > * graph
Definition: hypergraph.h:59
int getNNeighbors(int i)
int getWeight(int i)
SCIP_RETCODE readPartition(const char *filename)
miscellaneous hypergraph methods for structure detection
std::vector< int > getHyperedgeNodes(int i)
SCIP_RETCODE addHyperedge(std::vector< int > &edge, int weight)
SCIP_RETCODE writeToFile(int fd, SCIP_Bool writeweights)
Hypergraph(SCIP *scip)
SCIP_RETCODE addNode(int i, int weight)