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
12namespace triton {
13namespace tools{
14
15template<class node_t>
16class graph {
17 typedef std::map<node_t, llvm::SetVector<node_t>> edges_t;
18
19public:
20 typedef std::map<size_t, std::vector<node_t>> cmap_t;
21 typedef std::map<node_t, size_t> nmap_t;
22
23private:
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
37public:
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
62private:
63 llvm::SetVector<node_t> nodes_;
64 edges_t edges_;
65};
66
67}
68}
69
70#endif
71