1 | #pragma once |
2 | |
3 | #ifndef _TRITON_TOOLS_THREAD_GRAPH_H_ |
4 | #define _TRITON_TOOLS_THREAD_GRAPH_H_ |
5 | |
6 | #include "llvm/ADT/SetVector.h" |
7 | |
8 | #include <map> |
9 | #include <vector> |
10 | #include <iostream> |
11 | |
12 | namespace triton { |
13 | namespace tools{ |
14 | |
15 | template<class node_t> |
16 | class graph { |
17 | typedef std::map<node_t, llvm::SetVector<node_t>> edges_t; |
18 | |
19 | public: |
20 | typedef std::map<size_t, std::vector<node_t>> cmap_t; |
21 | typedef std::map<node_t, size_t> nmap_t; |
22 | |
23 | private: |
24 | void connected_components_impl(node_t x, llvm::SetVector<node_t> &nodes, |
25 | nmap_t* nmap, cmap_t* cmap, int id) const { |
26 | if(nmap) |
27 | (*nmap)[x] = id; |
28 | if(cmap) |
29 | (*cmap)[id].push_back(x); |
30 | if (nodes.count(x)) { |
31 | nodes.remove(x); |
32 | for(const node_t &y: edges_.at(x)) |
33 | connected_components_impl(y, nodes, nmap, cmap, id); |
34 | } |
35 | } |
36 | |
37 | public: |
38 | void connected_components(cmap_t *cmap, nmap_t *nmap) const { |
39 | if(cmap) |
40 | cmap->clear(); |
41 | if(nmap) |
42 | nmap->clear(); |
43 | llvm::SetVector<node_t> nodes = nodes_; |
44 | unsigned id = 0; |
45 | while(!nodes.empty()){ |
46 | connected_components_impl(*nodes.begin(), nodes, nmap, cmap, id++); |
47 | } |
48 | } |
49 | |
50 | void add_edge(node_t x, node_t y) { |
51 | nodes_.insert(x); |
52 | nodes_.insert(y); |
53 | edges_[x].insert(y); |
54 | edges_[y].insert(x); |
55 | } |
56 | |
57 | void clear() { |
58 | nodes_.clear(); |
59 | edges_.clear(); |
60 | } |
61 | |
62 | private: |
63 | llvm::SetVector<node_t> nodes_; |
64 | edges_t edges_; |
65 | }; |
66 | |
67 | } |
68 | } |
69 | |
70 | #endif |
71 | |