-
Notifications
You must be signed in to change notification settings - Fork 1
/
Graph.h
79 lines (71 loc) · 1.95 KB
/
Graph.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
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
// Copyright (c) 2013, Tim Kaler - MIT License
#include <cilk/cilk.h>
#include <cilk/reducer_list.h>
#include <cilk/reducer_min.h>
#include <cilk/reducer_max.h>
#include <cilk/holder.h>
#include <stdio.h>
#include <cstdlib>
#include <vector>
#include <list>
#include <map>
#include <string>
#include <set>
#include <cmath>
#include <algorithm>
#ifndef GRAPH_H_
#define GRAPH_H_
struct edge_info {
int edge_id;
int out_vertex;
int in_vertex;
int next;
} edge_info;
template<typename VertexType, typename EdgeType>
class Graph {
private:
int vertexCount;
int nextEdgeId;
std::vector<struct edge_info> temp_edges;
VertexType* vertexData;
EdgeType* edgeData;
int* outDegree;
int* inDegree;
// maps vertexId to start of out edges.
int* out_edge_index;
int* in_edge_index;
struct edge_info* out_edges;
struct edge_info* in_edges;
public:
Graph();
int* vertexColors;
void addEdge(int vid1, int vid2, EdgeType edgeInfo);
void addVertex(int vid, VertexType vdata);
void partition(int v, int* order, int* partitionIndexIn,
int* partitionIndexOut);
bool updateIndices(int r, int v, int* order,
int* partitionIndexIn, int* partitionIndexOut, int* currentIndexIn,
int* currentIndexOut, int* currentIndexInDynamic,
int* currentIndexOutDynamic);
void colorVertex(int v);
void asyncColor(int v, int* order, int* counters,
cilk::holder< std::set<int> >* neighbor_set_holder);
void finalize();
void resize(int size);
void prefetch_vertex(int vid);
int compute_coloring();
int compute_coloring_prefix();
int compute_coloring_rootset();
int compute_coloring_atomiccounter();
void validate_coloring();
int getVertexColor(int vid);
int getOutDegree(int vid);
int getInDegree(int vid);
int num_vertices();
int num_edges();
struct edge_info* getOutEdges(int vid);
struct edge_info* getInEdges(int vid);
VertexType* getVertexData(int vid);
EdgeType* getEdgeData(int eid);
};
#endif // GRAPH_H_