Scippy

GCG

Branch-and-Price & Column Generation for Everyone

hyperrowgraph.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 hyperrowgraph.h
29  * @brief Column hypergraph
30  * @author Martin Bergner
31  * @author Annika Thome
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 
37 #ifndef GCG_HYPERROWGRAPH_H_
38 #define GCG_HYPERROWGRAPH_H_
39 
40 #include "matrixgraph.h"
41 #include "hypergraph.h"
42 #include "class_partialdecomp.h"
43 #include "class_detprobdata.h"
44 
45 namespace gcg
46 {
47 template <class T>
49 {
50 private:
51  Hypergraph<T> graph;
52 public:
54  SCIP* scip, /**< SCIP data structure */
55  Weights w /**< weights for the given graph */
56  );
57 
58  virtual ~HyperrowGraph();
59 
60  /** writes the graph to the given file.
61  * The format is graph dependent
62  */
63  SCIP_RETCODE writeToFile(
64  int fd, /**< filename where the graph should be written to */
65  SCIP_Bool edgeweights /**< whether to write edgeweights */
66  );
67 
68  /** return the number of nodes */
69  virtual int getNNodes();
70 
71  /** return the number of edges (or hyperedges) */
72  virtual int getNEdges();
73 
74  /** return node degree */
75  virtual int getNNeighbors(
76  int i
77  );
78 
79  virtual std::vector<int> getNeighbors(
80  int i
81  )
82  {
83  return this->graph.getNeighbors(i);
84  }
85 
86  virtual std::vector<int> getHyperedgeNodes(
87  int i
88  );
89 
90  /**
91  * reads the partition from the given file.
92  * The format is graph dependent. The default is a file with one line for each node a
93  */
94  virtual SCIP_RETCODE readPartition(
95  const char* filename /**< filename where the partition is stored */
96  )
97  {
98  SCIP_CALL( this->graph.readPartition(filename) );
99  return SCIP_OKAY;
100  }
101 
102  /** return a partition of the nodes */
103  virtual std::vector<int> getPartition()
104  {
105  return this->graph.getPartition();
106  }
107 
108  virtual SCIP_RETCODE createDecompFromPartition(
109  DEC_DECOMP** decomp /**< decomposition structure to generate */
110  );
111 
112  /** amplifies a partialdec by dint of a graph created with open constraints and open variables of the partialdec */
113  virtual SCIP_RETCODE createPartialdecFromPartition(
114  PARTIALDECOMP* oldpartialdec, /**< partialdec which should be amplifies */
115  PARTIALDECOMP** firstpartialdec, /**< pointer to buffer the new partialdec amplified by dint of the graph */
116  PARTIALDECOMP** secondpartialdec, /**< pinter to buffer the new partialdec whose border is amplified by dint of the graph */
117  DETPROBDATA* detprobdata /**< detection process information and data */
118  );
119 
120  /** creates a new partialdec by dint of a graph created with all constraints and variables */
121  virtual SCIP_RETCODE createPartialdecFromPartition(
122  PARTIALDECOMP** firstpartialdec, /**< pointer to buffer the new partialdec created by dint of the graph */
123  PARTIALDECOMP** secondpartialdec, /**< pointer to buffer the new partialdec whose border is amplified by dint of the graph */
124  DETPROBDATA* detprobdata /**< detection process information and data */
125  );
126 
127  virtual SCIP_RETCODE createFromMatrix(
128  SCIP_CONS** conss, /**< constraints for which graph should be created */
129  SCIP_VAR** vars, /**< variables for which graph should be created */
130  int nconss_, /**< number of constraints */
131  int nvars_ /**< number of variables */
132  );
133 
134  /** creates a graph with open constraints and open variables of the partialdec */
135  virtual SCIP_RETCODE createFromPartialMatrix(
136  DETPROBDATA* detprobdata, /**< detection process information and data */
137  PARTIALDECOMP* partialdec /**< partial decomposition to use for matrix */
138  );
139 
140 };
141 
142 } /* namespace gcg */
143 #endif /* GCG_HYPERROWGRAPH_H_ */
miscellaneous matrixgraph methods for structure detection
std::vector< int > getNeighbors(int i)
virtual SCIP_RETCODE createPartialdecFromPartition(PARTIALDECOMP *oldpartialdec, PARTIALDECOMP **firstpartialdec, PARTIALDECOMP **secondpartialdec, DETPROBDATA *detprobdata)
virtual int getNNeighbors(int i)
virtual int getNEdges()
HyperrowGraph(SCIP *scip, Weights w)
virtual int getNNodes()
SCIP_RETCODE writeToFile(int fd, SCIP_Bool edgeweights)
virtual SCIP_RETCODE createFromPartialMatrix(DETPROBDATA *detprobdata, PARTIALDECOMP *partialdec)
virtual std::vector< int > getPartition() const
SCIP_RETCODE readPartition(const char *filename)
miscellaneous hypergraph methods for structure detection
virtual SCIP_RETCODE readPartition(const char *filename)
Definition: hyperrowgraph.h:94
virtual SCIP_RETCODE createDecompFromPartition(DEC_DECOMP **decomp)
class to manage partial decompositions
virtual SCIP_RETCODE createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_)
virtual std::vector< int > getNeighbors(int i)
Definition: hyperrowgraph.h:79
class storing (potentially incomplete) decompositions
virtual std::vector< int > getHyperedgeNodes(int i)
virtual std::vector< int > getPartition()
class storing partialdecs and the problem matrix