graphalgorithms.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 GRAPHALGORITHMS_H_
36 #define GRAPHALGORITHMS_H_
37 
38 #include "hypergraph.h"
39 #include "graph.h"
40 #include "graph_gcg.h"
41 
42 namespace gcg {
43 
44 // A structure to represent a subset for union-find
45 typedef struct subset
46 {
47  int parent;
48  int rank;
49 } subset;
50 
51 
52 template<class T>
54 
55 public:
57  static SCIP_Real computeSoed(
58  Hypergraph<T>& graph
59  );
60 
62  static SCIP_Real computeMincut(
63  Hypergraph<T>& graph
64  );
65 
67  static SCIP_Real computekMetric(
68  Hypergraph<T>& graph
69  );
70 
72  static std::vector<int> dbscan(
73  Graph<GraphGCG>& graph,
74  double eps,
75  int minPts = 4
76  );
77 
78 
80  static std::vector<int> mst(
81  Graph<GraphGCG>& graph,
82  double cutoff,
83  int minPts = 4
84  );
85 
86 
88  static std::vector<int> mcl(
89  Graph<GraphGCG>& graph,
90  int& stoppedAfter,
91  double inflatefac,
92  int maxiters = 25,
93  int expandfac = 2
94  );
95 
96 
97 
98 
99 //private:
100 
102  static void expandCluster(
103  Graph<T>& graph,
104  std::vector<bool>& visited,
105  std::vector<bool>& is_core,
106  std::vector<int>& labels,
107  int point,
108  std::vector<int>& NeighborPts,
109  int curr_cluster,
110  double eps,
111  int minPts
112  );
113 
114  static double cutoff;
115 
116  // Returns true if the weight of the edge is bigger than the this->cutoff
117  static bool cutoffif(
118  EdgeGCG &a
119  );
120 
121  // Compare two edges according to their weights.
122  // Used in sort() for sorting an array of edges
123  static int weightComp(
124  const void* a,
125  const void* b
126  );
127 
128  // A utility function to find set of an element i
129  // (uses path compression technique)
130  static int mstfind(
131  std::vector<subset>& subsets,
132  int i
133  );
134 
135  // A function that does union of two sets of x and y
136  // (uses union by rank)
137  static void mstunion(
138  std::vector<subset>& subsets,
139  int x,
140  int y
141  );
142 
143 };
144 
145 } /* namespace gcg */
146 
147 
148 
149 #endif /* GRAPHALGORITHMS_H_ */
miscellaneous hypergraph methods for structure detection
Implementation of the graph which supports both node and edge weights.
miscellaneous graph methods for structure detection
struct gcg::subset subset