Scippy

GCG

Branch-and-Price & Column Generation for Everyone

priority_graph.h
Go to the documentation of this file.
1 #include <vector>
2 #include <queue>
3 #include <algorithm>
4 #include <iostream>
5 #include <set>
6 
7 using namespace std;
8 
9 struct Comparator{
10  bool operator() (const pair<int, set<int> >& lhs, const pair<int, set<int> >& rhs){
11  return lhs.second.size() > rhs.second.size()
12  || (lhs.second.size() == rhs.second.size() && lhs.first > rhs.first);
13  }
14 };
15 
16 class priority_graph : public priority_queue<pair<int, set<int> >, vector<pair<int, set<int> > >, Comparator >
17 {
18 private:
19  set<int> nodes; // for optimization reasons
20 public:
21  void addEdge(int node_i, int node_j){
22  bool found1 = false;
23  bool found2 = false;
24  for(auto it = this->c.begin(); it < this->c.end(); ++it)
25  {
26  if(it->first == node_i){
27  it->second.insert(node_j);
28  found1 = true;
29  }
30  if(it->first == node_j){
31  it->second.insert(node_i);
32  found2 = true;
33  }
34  if(found1 && found2) break;
35  }
36  make_heap(this->c.begin(), this->c.end(), this->comp);
37  }
38  set<int> getNeighbors(int node){
39  set<int> res;
40  for(auto it = this->c.begin(); it < this->c.end(); ++it){
41  if(it->first == node){
42  return it->second;
43  }
44  }
45  return res;
46  }
47  void addNode(int id){
48  auto res = nodes.insert(id);
49  if(res.second == true)
50  this->push(pair<int, set<int> >(id, set<int>()));
51  }
52  bool removeNode(int node, vector<int>& removed){
53  nodes.erase(node);
54  bool res;
55  auto it = this->c.begin();
56  for(; it < this->c.end(); ++it)
57  {
58  if(it->first == node){
59  break;
60  }
61  }
62  if (it != this->c.end()) {
63  this->c.erase(it);
64  make_heap(this->c.begin(), this->c.end(), this->comp);
65  removed.push_back(node);
66  res = true;
67  }
68  else{
69  cout << "failed to remove node " << node << endl;
70  return false;
71  }
72 
73  it = this->c.begin();
74  for(; it < this->c.end(); ++it)
75  {
76  it->second.erase(node);
77  }
78 
79  return res;
80  }
81  set<int> getNodes(){
82  return nodes;
83  }
84 };
void addNode(int id)
void addEdge(int node_i, int node_j)
bool removeNode(int node, vector< int > &removed)
set< int > getNodes()
set< int > getNeighbors(int node)