graph_gcg.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 #ifndef GCG_GRAPH_GCG_H_
36 #define GCG_GRAPH_GCG_H_
37 
38 #include <map>
39 #include "bridge.h"
40 
41 #ifdef WITH_GSL
42  #include <gsl/gsl_spmatrix.h>
43  #include <gsl/gsl_spblas.h>
44 #endif
45 
46 namespace gcg {
47 
48 class EdgeGCG
49 {
50 public:
51  int src, dest;
52  double weight;
53  EdgeGCG() {}
54  EdgeGCG(int s, int d, double w): src(s), dest(d), weight(w) {}
55 } ;
56 
57 class GraphGCG: public gcg::Bridge
58 {
59 private:
60  bool undirected;
61  bool locked; // true if we are not allowed to change the graph anymore
62  bool initialized; // true if at least 1 node
63  std::vector<int> nodes;
64 #ifdef WITH_GSL
65  gsl_spmatrix* adj_matrix_sparse;
66  gsl_spmatrix* working_adj_matrix; // this one is used ONLY during MCL algorithm!
67 #else
68  std::vector<std::vector<double>> adj_matrix;
69 #endif
70  std::vector<EdgeGCG*> edges;
71 
72 public:
73 
74  GraphGCG();
75  GraphGCG(int _n_nodes, bool _undirected);
76 
77  virtual ~GraphGCG();
78  virtual SCIP_RETCODE addNNodes(int _n_nodes);
79  virtual SCIP_RETCODE addNNodes(int _n_nodes, std::vector<int> weights);
80  virtual int getNNodes();
81  virtual int getNEdges();
82 
83 #ifdef WITH_GSL
84  virtual gsl_spmatrix* getAdjMatrix();
85  virtual void expand(int factor);
86  virtual void inflate(double factor);
87  virtual void colL1Norm();
88  virtual void prune();
89  virtual bool stopMCL(int iter);
90  virtual std::vector<int> getClustersMCL();
91  virtual void initMCL();
92  virtual void clearMCL();
93 #else
94  virtual std::vector<std::vector<double>> getAdjMatrix();
95 #endif
96  virtual SCIP_RETCODE getEdges(std::vector<void*>& edges);
97  virtual SCIP_Bool isEdge(int node_i, int node_j);
98  virtual int getNNeighbors(int node);
99  virtual std::vector<int> getNeighbors(int node);
100  virtual std::vector<std::pair<int, double> > getNeighborWeights(int node);
101  virtual SCIP_RETCODE addNode(int node, int weight);
102  virtual SCIP_RETCODE addNode();
103  virtual SCIP_RETCODE deleteNode(int node);
104  virtual SCIP_RETCODE addEdge(int i, int j);
105  virtual SCIP_RETCODE addEdge(int node_i, int node_j, double weight);
106  virtual SCIP_RETCODE setEdge(int node_i, int node_j, double weight);
107  virtual SCIP_RETCODE deleteEdge(int node_i, int node_j);
108  virtual int graphGetWeights(int node);
109  virtual double getEdgeWeight(int node_i, int node_j);
110 
111  virtual int edgeComp(const EdgeGCG* a, const EdgeGCG* b);
112 
113  virtual SCIP_RETCODE flush(); // lock the graph and compresses the adj matrix if we use GSL
114  virtual SCIP_RETCODE normalize();
115  virtual double getEdgeWeightPercentile(double q);
116 };
117 
118 } /* namespace gcg */
119 #endif /* GCG_GRAPH_GCG_H_ */
EdgeGCG(int s, int d, double w)
Definition: graph_gcg.h:54
double weight
Definition: graph_gcg.h:52
bridge