treewidth/CE.h at master · smaniu/treewidth · GitHub

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
//
//  CE.h
//  treewidth
//
//  Created by Silviu Maniu on 23/02/16.
//  Copyright © 2016 Silviu Maniu. All rights reserved.
//

#ifndef CE_h
#define CE_h

#include <ostream>
#include <string>
#include <algorithm>

#include "PermutationStrategy.h"
#include "Graph.h"

//Class implementing the edge contraction
class CE{
private:
  Graph& graph;
  PermutationStrategy& strategy;
public:
  CE(Graph& gr, PermutationStrategy& str):\
  graph(gr), strategy(str) {}
  //Computes estimation

  void con_edge(){
    //building the first permutation
    strategy.init_permutation(graph);
    unsigned long node = strategy.get_next();
    std::unordered_set<unsigned long> neigh = graph.get_neighbours(node);
    //getting the neighbour with least overlap
    unsigned long min_v = 0;
    unsigned long min_ovl = neigh.size();
    for(auto v:neigh){
      unsigned long ovl = 0;
      for(auto nv:graph.get_neighbours(v))
        if(graph.has_edge(node,nv)) ovl++;
      if(min_ovl>=ovl){
        min_v = v;
        min_ovl = ovl;
      }
      //contracting the edge
      graph.contract_edge(min_v,node);
    }

}
};

#endif /* CE_h */