-
Notifications
You must be signed in to change notification settings - Fork 42
/
pmc_maxclique.h
122 lines (99 loc) · 3.46 KB
/
pmc_maxclique.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/**
============================================================================
Name : Parallel Maximum Clique (PMC) Library
Author : Ryan A. Rossi (rrossi@purdue.edu)
Description : A general high-performance parallel framework for computing
maximum cliques. The library is designed to be fast for large
sparse graphs.
Copyright (C) 2012-2013, Ryan A. Rossi, All rights reserved.
Please cite the following paper if used:
Ryan A. Rossi, David F. Gleich, Assefaw H. Gebremedhin, Md. Mostofa
Patwary, A Fast Parallel Maximum Clique Algorithm for Large Sparse Graphs
and Temporal Strong Components, arXiv preprint 1302.6256, 2013.
See http://ryanrossi.com/pmc for more information.
============================================================================
*/
#ifndef PMC_MAXCLIQUE_H_
#define PMC_MAXCLIQUE_H_
#include <cstddef>
#include <sys/time.h>
#include <unistd.h>
#include <iostream>
#include <algorithm>
#include "pmc_headers.h"
#include "pmc_utils.h"
#include "pmc_graph.h"
#include "pmc_input.h"
#include "pmc_vertex.h"
using namespace std;
namespace pmc {
class pmc_maxclique {
public:
vector<int>* edges;
vector<long long>* vertices;
vector<int>* bound;
vector<int>* order;
vector<int>* degree;
int param_ub;
int ub;
int lb;
double time_limit;
double sec;
double wait_time;
bool not_reached_ub;
bool time_expired_msg;
bool decr_order;
string vertex_ordering;
int edge_ordering;
int style_bounds;
int style_dynamic_bounds;
int num_threads;
void initialize() {
vertex_ordering = "kcore";
edge_ordering = 0;
style_bounds = 0;
style_dynamic_bounds = 0;
not_reached_ub = true;
time_expired_msg = true;
decr_order = false;
}
void setup_bounds(input& params) {
lb = params.lb;
ub = params.ub;
param_ub = params.param_ub;
if (param_ub == 0)
param_ub = ub;
time_limit = params.time_limit;
wait_time = params.remove_time;
sec = get_time();
num_threads = params.threads;
}
pmc_maxclique(pmc_graph& G, input& params) {
bound = G.get_kcores();
order = G.get_kcore_ordering();
setup_bounds(params);
initialize();
vertex_ordering = params.vertex_search_order;
decr_order = params.decreasing_order;
}
~pmc_maxclique() {};
int search(pmc_graph& G, vector<int>& sol);
void branch(
vector<Vertex> &P,
vector<short>& ind,
vector<int>& C,
vector<int>& C_max,
int* &pruned,
int& mc);
int search_dense(pmc_graph& G, vector<int>& sol);
void branch_dense(
vector<Vertex> &P,
vector<short>& ind,
vector<int>& C,
vector<int>& C_max,
int* &pruned,
int& mc,
bool** &adj);
};
};
#endif