treewidth-smaniu/Graph.h at master · Telijas/treewidth-smaniu · 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
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
123
124
125
126
127
#ifndef Graph_h
#define Graph_h
#include <stdlib.h>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

//Class for the graph
class Graph{
private:
  std::unordered_map<unsigned long, std::unordered_set<unsigned long>> adj_list;
  std::unordered_set<unsigned long> node_set;
  unsigned long num_edges = 0;


public:

  void add_edge(unsigned long src, unsigned long tgt, bool undirected=true){
    if(!has_edge(src, tgt)){
      node_set.insert(src);
      node_set.insert(tgt);
      adj_list[src].insert(tgt);
      if(undirected) adj_list[tgt].insert(src);
      num_edges++;
    }
  };

  void add_node(unsigned long node){
    node_set.insert(node);
  }

  // Returns adjacency list
  std::unordered_set<unsigned long> remove_node(unsigned long node){
    node_set.erase(node);
    for(auto neighbour:adj_list[node]){
      adj_list[neighbour].erase(node);
      num_edges--;
    }
    auto it = adj_list.find(node);
    auto adjacency_list = std::move(it->second);
    adj_list.erase(it);
    return adjacency_list;
  }

  bool neighbour_improved(unsigned k,unsigned long n1, unsigned long n2){
		bool retval = false;
		auto &neigh1 = get_neighbours(n1);
		auto &neigh2 = get_neighbours(n2);

		unsigned long count = 0;
		if 	(neigh1.size()>k-1 && neigh2.size()>k-1){
			for (auto nn1:neigh1){
				for (auto nn2:neigh2){
					if (nn1==nn2){
						count = count+1;
						break;
					}

				}
			}
		}
		if (count > k-1){
			retval = true;
		}

		return retval;
}

  void fill(const std::unordered_set<unsigned long>& nodes,\
            bool undirected=true){
    for(auto src: nodes)
      for(auto tgt: nodes)
        if(undirected){
          if(src<tgt)
            add_edge(src, tgt, undirected);
        }
        else{
          if(src!=tgt)
            add_edge(src, tgt, undirected);
        }

  }

  void contract_edge(unsigned long src, unsigned long tgt){
    for(auto v:get_neighbours(tgt))
      if((v!=src)&&!has_edge(src,v)) add_edge(src,v);
    remove_node(tgt);
  }

  bool has_neighbours(unsigned long node) const{
    return adj_list.find(node)!=adj_list.end();
  }

  bool has_node(unsigned long node) const{
    return node_set.find(node)!=node_set.end();
  }

  bool has_edge(unsigned long src, unsigned long tgt) {
    bool retval = false;
    if(has_neighbours(src)){
      auto &neigh = get_neighbours(src);
      retval = neigh.find(tgt)!=neigh.end();
    }
    return retval;
  }

  const std::unordered_set<unsigned long> &get_neighbours(unsigned long node) const{
    assert(has_node(node));

    return (adj_list.find(node))->second;
  }

  const std::unordered_set<unsigned long> &get_nodes() const{
    return node_set;
  }

  unsigned long number_nodes() const{
    return node_set.size();
  }

  unsigned long number_edges() const{
    return num_edges;
  }
};


#endif /* Graph_h */