-
Notifications
You must be signed in to change notification settings - Fork 2
/
discount_degree.go
72 lines (62 loc) · 1.8 KB
/
discount_degree.go
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
package algorithm
import (
"github.com/jtejido/goim/util"
"github.com/jtejido/set"
)
type discountDegreeNode struct {
Node
deg float64
}
type DiscountDegree struct {
base
covQueue *util.PriorityQueue
graph *util.Graph
config *util.Config
}
func NewDiscountDegree(graph *util.Graph, config *util.Config, t int) *DiscountDegree {
dd := new(DiscountDegree)
dd.graph = graph
dd.config = config
dd.covQueue = util.NewPriorityQueue(func(n1, n2 interface{}) bool {
if n1.(*discountDegreeNode).deg != n2.(*discountDegreeNode).deg {
return n2.(*discountDegreeNode).deg < n1.(*discountDegreeNode).deg
}
return n1.(*discountDegreeNode).deg < n2.(*discountDegreeNode).deg
})
return dd
}
func (dd *DiscountDegree) Select(activated set.Set) set.Set {
s := set.NewSet()
queue_nodes := make(map[util.Node]*util.Item)
for node := range dd.graph.Nodes().Iter() {
nstruct := new(discountDegreeNode)
nstruct.id = node.(util.Node)
if !activated.Contains(nstruct.id) {
nstruct.deg = 1.
}
if dd.graph.Neighbors(node.(util.Node), false) != nil {
for _, edge := range dd.graph.Neighbors(node.(util.Node), false) {
if !activated.Contains(edge.Target) {
nstruct.deg += edge.Dist
}
}
}
queue_nodes[nstruct.id] = dd.covQueue.Push(nstruct)
}
for s.Len() < dd.config.Seeds {
nstruct := dd.covQueue.Peek().(*discountDegreeNode)
s.Add(nstruct.id)
if dd.graph.Neighbors(nstruct.id, false) != nil {
for _, edge := range dd.graph.Neighbors(nstruct.id, false) {
if !activated.Contains(edge.Target) && !s.Contains(edge.Target) {
newN := new(discountDegreeNode)
newN.id = edge.Target
newN.deg = queue_nodes[edge.Target].Value().(*discountDegreeNode).deg * (1.0 - edge.Dist)
dd.covQueue.Update(queue_nodes[edge.Target], newN)
}
}
}
dd.covQueue.Pop()
}
return s
}