-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathGraphUtil.h
47 lines (39 loc) · 2.75 KB
/
GraphUtil.h
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
#ifndef _GRAPH_UTIL_H_
#define _GRAPH_UTIL_H_
#include "Graph.h"
#include <sys/time.h>
class GraphUtil {
public:
static void dfs(Graph& g, int vid, vector<int>& preorder, vector<int>& postorder, vector<bool>& visited);
static void topological_sort(Graph &g, vector<int>& ts);
static void topo_leveler(Graph& g);
static int topo_level(Graph& g, int vid);
static void transitive_closure(Graph g, Graph& tc);
static void tarjan(Graph& g, int vid, int& index, unordered_map< int, pair<int,int> >& order, vector<int>& sn,
multimap<int, int>& sccmap, int& scc);
static void mergeSCC(Graph& g, int* on, vector<int>& ts);
static void findTreeCover(Graph g, Graph& tree);
static void findTreeCover(Graph g, Graph& tree, vector<set<int> >& pred);
static void findTreeCover(Graph& g, Graph& tree, vector<set<int> >& pred, vector<int>& ts);
static void compute_pred(Graph g, vector<set<int> >& predMap);
static void findTreeCoverL(Graph g, Graph& tree);
static void traverse(Graph& tree, int vid, int& pre_post, vector<bool>& visited);
static void pre_post_labeling(Graph& tree);
static void pathDecomposition(Graph& g, vector<vector<int> >& pathMap);
static void pathDecomposition(Graph& g, vector<vector<int> >& pathMap, vector<int> ts);
static void treePathDecomposition(Graph tree, Graph& g, vector<vector<int> >& pathMap);
static void genRandomGraph(int n, double c, char* filename);
static bool DFSCheck(Graph& graph, int vid, bit_vector* visited, int trg);
static bool DFSReach(Graph& graph, int src, int trg);
static void buildGateGraphByNodeFast(Graph& g, bit_vector* isgates, int vid, int radius, map<int,int>& gateindex, Graph& gategraph, vector<int>& que, vector<int>& dist, int& ref);
static int buildGateGraphByNodeFastWrite(Graph& g, bit_vector* isgates, int vid, int radius, map<int,int>& gateindex, ostream& out, vector<int>& que, vector<int>& dist, int& ref);
static int buildGateGraphWrite(Graph& graph, bit_vector* isgate, int radius, ostream& out);
static bool DFSCheckCnt(Graph& graph, int vid, vector<int>& visited, int trg, int qcnt);
static bool DFSReachCnt(Graph& graph, int src, int trg, vector<int>& visited, int& qcnt);
static void collectInLocalGates(Graph& graph, const bit_vector* isgates, int vid, int radius, vector<int>& ingates);
static bool BFSOutLocalReach(Graph& graph, const bit_vector* isgates, int radius, int src, int trg, vector<int>& outgates);
static void collectOutLocalGates(Graph& graph, const bit_vector* isgates, int vid, int radius, vector<int>& outgates);
static int visit(Graph& tree, int vid, int& pre_post, vector<bool>& visited, vector<pair<int,int> >& dfslabels);
static void grail_labeling(Graph& tree, vector<pair<int,int> >& dfslabels);
};
#endif