Graph-Centralities/GraphAlgorithm.java at master · franklinfollis/Graph-Centralities · GitHub

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
import java.util.*;

/**
 * Created by Francis on 2/06/2016.
 */
public class GraphAlgorithm {

    public static class MuteFloat {
        public float value = 0.f;

        public MuteFloat(Node ignored) { }
    }

    public class BrandesData {
        ArrayList<Node> pred = new ArrayList<>();
        int distance;

        float sigma;
        float dependency = 0;

        private BrandesData(int distance, float sigma) {
            this.distance = distance;
            this.sigma = sigma;
        }

        private BrandesData(Node ignored) {
            this(-1,0);
        }
    }

    public static float bfsSum(Node start) {
        Queue<Node> queue = new ArrayDeque<>();
        Map<Integer,Integer> distances = new HashMap<>();

        queue.add(start);
        distances.put(start.getID(), 0);

        float sum = 0;

        while (!queue.isEmpty()) {
            Node n = queue.remove();

            int dist = distances.get(n.getID());

            for (Node e : n.getEdges()) {
                if (!distances.containsKey(e.getID())) {
                    queue.add(e);
                    distances.put(e.getID(), dist+1);

                    sum += 1.f / (dist + 1);
                }
            }
        }

        return sum;
    }

    public void brandesAlg(Node start, Map<Node, MuteFloat> b){
        Queue<Node> queue = new ArrayDeque<>();
        Stack<Node> s = new Stack<>();
        Map<Node, BrandesData> nodeData = new IdentityHashMap<>();

        queue.add(start);

        nodeData.put(start, new BrandesData(0, 1));

        while (!queue.isEmpty()) {
            Node n = queue.remove();
            BrandesData nData = nodeData.computeIfAbsent(n, BrandesData::new);

            s.push(n);

            for (Node v : n.getEdges()) {
                BrandesData vData = nodeData.computeIfAbsent(v, BrandesData::new);

                if (vData.distance < 0) {
                    queue.add(v);
                    vData.distance = nData.distance + 1;
                }

                if (vData.distance == nData.distance + 1) {
                    vData.sigma += nData.sigma;
                    vData.pred.add(n);
                }
            }
        }

        while(!s.isEmpty()){
            Node w = s.pop();
            BrandesData wData = nodeData.get(w);

            for(Node v : wData.pred){
                BrandesData vData = nodeData.get(v);

                vData.dependency += (vData.sigma / wData.sigma) * (1 + wData.dependency);
            }

            if(w != start) b.computeIfAbsent(w, MuteFloat::new).value += wData.dependency;
        }
    }

    public float bfsKatz(Node start){
        float alpha = 0.5f;

        Queue<Node> queue = new ArrayDeque<>();
        Map<Integer,Integer> distances = new HashMap<>();

        queue.add(start);
        distances.put(start.getID(), 0);

        float sum = 0;

        while (!queue.isEmpty()) {
            Node n = queue.remove();

            int dist = distances.get(n.getID());

            for (Node e : n.getEdges()) {
                if (!distances.containsKey(e.getID())) {
                    queue.add(e);
                    distances.put(e.getID(), dist+1);

                    sum += Math.pow(alpha, (dist+1));
                }
            }
        }

        return sum;

    }
}