Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
70 lines (62 sloc) 2 KB
element Vertex end
element Edge end
const edges : edgeset{Edge}(Vertex,Vertex);
const vertices : vertexset{Vertex};
const cur_rank : vector{Vertex}(float);
const ngh_sum : vector{Vertex}(float);
const delta : vector{Vertex}(float);
const out_degree : vector {Vertex}(int);
const damp : float = 0.85;
const beta_score : float;
const epsilon2 : float = 0.1;
const epsilon : float = 0.0000001;
const init_delta: float;
func updateEdge(src : Vertex, dst : Vertex)
ngh_sum[dst] += delta[src]/out_degree[src];
end
func updateVertexFirstRound(v : Vertex) -> output : bool
delta[v] = damp*(ngh_sum[v]) + beta_score;
cur_rank[v] += delta[v];
delta[v] = delta[v]-1.0/edges.getVertices();
output = (fabs(delta[v]) > epsilon2*cur_rank[v]);
ngh_sum[v] = 0;
end
func updateVertex(v : Vertex) -> output : bool
delta[v] = ngh_sum[v]*damp;
cur_rank[v] += delta[v];
ngh_sum[v] = 0;
output = fabs(delta[v]) > epsilon2*cur_rank[v];
end
func initVectors(v : Vertex)
cur_rank[v] = 0.0;
ngh_sum[v] = 0.0;
delta[v] = init_delta;
end
export func set_graph(edges_args: edgeset{Edge}(Vertex, Vertex))
edges = edges_args;
vertices = edges.getVertices();
cur_rank = new vector{Vertex}(float)();
ngh_sum = new vector{Vertex}(float)();
delta = new vector{Vertex}(float)();
out_degree = edges.getOutDegrees();
beta_score = (1.0 - damp) / edges.getVertices();
init_delta = 1.0 / edges.getVertices();
vertices.apply(initVectors);
end
export func do_pagerank_delta() -> final_ranks: vector{Vertex} (float)
var n : int = edges.getVertices();
var frontier : vertexset{Vertex} = new vertexset{Vertex}(n);
for i in 1:10
#s1# edges.from(frontier).apply(updateEdge);
var output : vertexset{Vertex};
if i == 1
output = vertices.filter(updateVertexFirstRound);
else
output = vertices.filter(updateVertex);
end
delete frontier;
frontier = output;
end
delete frontier;
final_ranks = cur_rank;
end
You can’t perform that action at this time.