public static void main(String args[]) {
Importance s[] = new Importance[6]; for (int i=0;i<s.length;i++) s[i] = new Importance(i+1,0f,0f);
PriorityQueue<Integer> fetcher = new PriorityQueue<Integer>((a, b) -> s[a-1].total_score < s[b-1].total_score ? 1:-1);
s[0].total_score =100f; s[1].total_score = 100f;
fetcher.add(1); fetcher.add(2);
int edge [][] = {{2,5},{3,5},{4,5,6},{1,5},{1},{5}};
Set visited = new HashSet<Integer>(); int round = 0;
while(visited.size() <= 6) { System.out.println("\n**** Round "+round+" ****"); System.out.println("visited nodes" +visited.toString()); System.out.println("Priority Queue"); Iterator it = fetcher.iterator(); while(it.hasNext()) { int val = (int) it.next(); System.out.print(val + " " +s[val-1].total_score+" , "); } if (visited.size() == 6) break;
int temp = fetcher.poll();
float score_temp = s[temp-1].total_score; int name_temp = s[temp-1].name; float score_divide = score_temp/edge[name_temp-1].length; s[temp-1].last_score = s[temp-1].total_score; s[temp-1].total_score = 0;
for(int i =0 ; i < edge[name_temp-1].length; i++) { s[edge[name_temp-1][i]-1].total_score += score_divide; if (!fetcher.contains(edge[name_temp-1][i])) { fetcher.add(edge[name_temp-1][i]); }
} visited.add(temp); round++;
}
}
int name;float total_score; float last_score; Importance(int name, float total_score,
float last_score){
this.name = name; this.total_score = total_score; this.last_score = last_score;} }
Iteration: 0
------ priority queue: [(1, 1.0), (2, 1.0)] Iteration: 1
------ priority queue: [(2, 1.5), (5, 0.5)] Iteration: 2
------ priority queue: [(5, 1.25), (3, 0.75)] Iteration: 3
------ priority queue: [(1, 1.25), (3, 0.75)] Iteration: 4
------ priority queue: [(3, 0.75), (2, 0.625), (5, 0.625)] Iteration: 5
------ priority queue: [(5, 0.875), (2, 0.625), (4, 0.25), (6, 0.25)] Iteration: 6
------ priority queue: [(1, 0.875), (2, 0.625), (4, 0.25), (6, 0.25)] Iteration: 7
------ priority queue: [(2, 1.0625), (5, 0.4375), (4, 0.25), (6, 0.25)] Iteration: 8
------ priority queue: [(5, 0.96875), (3, 0.53125), (4, 0.25), (6, 0.25)] Iteration: 9
------ priority queue: [(1, 0.96875), (3, 0.53125), (4, 0.25), (6, 0.25)] Iteration: 10
------ priority queue: [(3, 0.53125), (2, 0.484375), (5, 0.484375), (4, 0.25), (6, 0.25)] Iteration: 11
------ priority queue: [(5, 0.6614583333333334), (2, 0.484375), (4, 0.42708333333333337), (6, 0.42708333333333337)] Iteration: 12
------ priority queue: [(1, 0.6614583333333334), (2, 0.484375), (4, 0.42708333333333337), (6, 0.42708333333333337)] Iteration: 13
------ priority queue: [(2, 0.8151041666666667), (4, 0.42708333333333337), (6, 0.42708333333333337), (5, 0.3307291666666667)] Iteration: 14
------ priority queue: [(5, 0.73828125), (4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337)] Iteration: 15
------ priority queue: [(1, 0.73828125), (4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337)]
Round0 PQ: [(1, 1.00), (2, 1.00)] visited nodes[] Round1 PQ: [(2, 1.50), (5, 0.50)] visited nodes[2] Round2 PQ: [(5, 1.25), (3, 0.75)] visited nodes[1, 2] Round3 PQ: [(1, 1.25), (3, 0.75)] visited nodes[1, 2] Round4 PQ: [(3, 0.75), (2, 0.625), (5, 0.625)] visited nodes[1, 2, 5] Round5 PQ: [(5, 0.875), (2, 0.625), (4, 0.25), (6, 0.25)] visited nodes[1, 2, 5] Round6 PQ: [(1, 0.875), (2, 0.625), (4, 0.25), (6, 0.25)] visited nodes[1, 2, 3, 5] Round7 PQ: [(2, 1.0625), (5, 0.4375), (4, 0.25), (6, 0.25)] visited nodes[1, 2, 3, 5] Round8 PQ: [(5, 0.96875), (3, 0.53125), (4, 0.25), (6, 0.25)] visited nodes[1, 2, 3, 5] Round9 PQ: [(1, 0.96875), (3, 0.53125), (4, 0.25), (6, 0.25)] visited nodes[1, 2, 3, 5] Round10 PQ: [(3, 0.53125), (2, 0.484375), (5, 0.484375), (4, 0.25), (6, 0.25)] visited nodes[1, 2, 3, 5] Round11 PQ: [(5, 0.6614583333333334), (2, 0.484375), (4, 0.42708333333333337), (6, 0.42708333333333337)] visited nodes[1, 2, 3, 5] Round12 PQ: [(1, 0.6614583333333334), (2, 0.484375), (4, 0.42708333333333337), (6, 0.42708333333333337)] visited nodes[1, 2, 3, 5] Round13 PQ: [(2, 0.8151041666666667), (4, 0.42708333333333337), (6, 0.42708333333333337), (5, 0.3307291666666667)] visited nodes[1, 2, 3, 5] Round14 PQ: [(5, 0.73828125), (4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337)] visited nodes[1, 2, 3, 5] Round15 PQ: [(1, 0.73828125), (4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337)] visited nodes[1, 2, 3, 5] Round16 PQ: [(4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337), (2, 0.369140625), (5, 0.369140625)] visited nodes[1, 2, 3, 5] Round17 PQ: [(5, 0.5826822916666667), (6, 0.42708333333333337), (3, 0.40755208333333337), (2, 0.369140625), (1, 0.21354166666666669)] visited nodes[1, 2, 3, 4, 5] Round18 PQ: [(1, 0.7962239583333335), (6, 0.42708333333333337), (3, 0.40755208333333337), (2, 0.369140625)] visited nodes[1, 2, 3, 4, 5] Round19 PQ: [(2, 0.7672526041666667), (6, 0.42708333333333337), (3, 0.40755208333333337), (5, 0.39811197916666674)]visited nodes[1, 2, 3, 4, 5] Round20 PQ: [(3, 0.7911783854166667), (5, 0.7817382812500001), (6, 0.42708333333333337)] visited nodes[1, 2, 3, 4, 5] Round21 PQ: [(5, 1.0454644097222223), (6, 0.6908094618055556), (4, 0.26372612847222227)] visited nodes[1, 2, 3, 4, 5] Round22 PQ: [(1, 1.0454644097222223), (6, 0.6908094618055556), (4, 0.26372612847222227)] visited nodes[1, 2, 3, 4, 5] Round23 PQ: [(6, 0.6908094618055556), (2, 0.5227322048611112), (5, 0.5227322048611112), (4, 0.26372612847222227)] visited nodes[1, 2, 3, 4, 5] Round24 PQ: [(5, 1.2135416666666667), (2, 0.5227322048611112), (4, 0.26372612847222227)] visited nodes[1, 2, 3, 4, 5, 6]
Iteration: 0
-- priority queue: [(1, 1.0), (2, 1.0)] Iteration: 1
-- priority queue: [(2, 1.5), (5, 0.5)] Iteration: 2
-- priority queue: [(5, 1.25), (3, 0.75)] Iteration: 3
-- priority queue: [(1, 1.25), (3, 0.75)] Iteration: 4
-- priority queue: [(3, 0.75), (2, 0.625), (5, 0.625)] Iteration: 5
-- priority queue: [(5, 0.875), (2, 0.625), (4, 0.25), (6, 0.25)] Iteration: 6
-- priority queue: [(1, 0.875), (2, 0.625), (4, 0.25), (6, 0.25)] Iteration: 7
-- priority queue: [(2, 1.0625), (5, 0.4375), (4, 0.25), (6, 0.25)] Iteration: 8
-- priority queue: [(5, 0.96875), (3, 0.53125), (4, 0.25), (6, 0.25)] Iteration: 9
-- priority queue: [(1, 0.96875), (3, 0.53125), (4, 0.25), (6, 0.25)] Iteration: 10
-- priority queue: [(3, 0.53125), (2, 0.484375), (5, 0.484375), (4, 0.25), (6, 0.25)] Iteration: 11
-- priority queue: [(5, 0.6614583333333334), (2, 0.484375), (4, 0.42708333333333337), (6, 0.42708333333333337)] Iteration: 12
-- priority queue: [(1, 0.6614583333333334), (2, 0.484375), (4, 0.42708333333333337), (6, 0.42708333333333337)] Iteration: 13
-- priority queue: [(2, 0.8151041666666667), (4, 0.42708333333333337), (6, 0.42708333333333337), (5, 0.3307291666666667)] Iteration: 14
-- priority queue: [(5, 0.73828125), (4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337)] Iteration: 15
-- priority queue: [(1, 0.73828125), (4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337)]
Iteration: 0 --- Priority queue: [(1, 1.0), (2, 1.0)] Visit list: set() Iteration: 1 --- Priority queue: [(2, 1.5), (5, 0.5)] Visit list: {1} Iteration: 2 --- Priority queue: [(5, 1.25), (3, 0.75)] Visit list: {1, 2} Iteration: 3 --- Priority queue: [(1, 1.25), (3, 0.75)] Visit list: {1, 2, 5} Iteration: 4 --- Priority queue: [(3, 0.75), (2, 0.625), (5, 0.625)] Visit list: {1, 2, 5} Iteration: 5 --- Priority queue: [(5, 0.875), (2, 0.625), (4, 0.25), (6, 0.25)] Visit list: {1, 2, 3, 5} Iteration: 6 --- Priority queue: [(1, 0.875), (2, 0.625), (4, 0.25), (6, 0.25)] Visit list: {1, 2, 3, 5} Iteration: 7 --- Priority queue: [(2, 1.0625), (5, 0.4375), (4, 0.25), (6, 0.25)] Visit list: {1, 2, 3, 5} Iteration: 8 --- Priority queue: [(5, 0.96875), (3, 0.53125), (4, 0.25), (6, 0.25)] Visit list: {1, 2, 3, 5} Iteration: 9 --- Priority queue: [(1, 0.96875), (3, 0.53125), (4, 0.25), (6, 0.25)] Visit list: {1, 2, 3, 5} Iteration: 10 --- Priority queue: [(3, 0.53125), (2, 0.484375), (5, 0.484375), (4, 0.25), (6, 0.25)] Visit list: {1, 2, 3, 5} Iteration: 11 --- Priority queue: [(5, 0.6614583333333334), (2, 0.484375), (4, 0.42708333333333337), (6, 0.42708333333333337)] Visit list: {1, 2, 3, 5} Iteration: 12 --- Priority queue: [(1, 0.6614583333333334), (2, 0.484375), (4, 0.42708333333333337), (6, 0.42708333333333337)] Visit list: {1, 2, 3, 5} Iteration: 13 --- Priority queue: [(2, 0.8151041666666667), (4, 0.42708333333333337), (6, 0.42708333333333337), (5, 0.3307291666666667)] Visit list: {1, 2, 3, 5} Iteration: 14 --- Priority queue: [(5, 0.73828125), (4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337)] Visit list: {1, 2, 3, 5} Iteration: 15 --- Priority queue: [(1, 0.73828125), (4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337)] Visit list: {1, 2, 3, 5} Iteration: 16 --- Priority queue: [(4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337), (2, 0.369140625), (5, 0.369140625)] Visit list: {1, 2, 3, 5} Iteration: 17 --- Priority queue: [(5, 0.5826822916666667), (6, 0.42708333333333337), (3, 0.40755208333333337), (2, 0.369140625), (1, 0.21354166666666669)] Visit list: {1, 2, 3, 4, 5} Iteration: 18 --- Priority queue: [(1, 0.7962239583333335), (6, 0.42708333333333337), (3, 0.40755208333333337), (2, 0.369140625)] Visit list: {1, 2, 3, 4, 5} Iteration: 19 --- Priority queue: [(2, 0.7672526041666667), (6, 0.42708333333333337), (3, 0.40755208333333337), (5, 0.39811197916666674)] Visit list: {1, 2, 3, 4, 5} Iteration: 20 --- Priority queue: [(3, 0.7911783854166667), (5, 0.7817382812500001), (6, 0.42708333333333337)] Visit list: {1, 2, 3, 4, 5} Iteration: 21 --- Priority queue: [(5, 1.0454644097222223), (6, 0.6908094618055556), (4, 0.26372612847222227)] Visit list: {1, 2, 3, 4, 5} Iteration: 22 --- Priority queue: [(1, 1.0454644097222223), (6, 0.6908094618055556), (4, 0.26372612847222227)] Visit list: {1, 2, 3, 4, 5} Iteration: 23 --- Priority queue: [(6, 0.6908094618055556), (2, 0.5227322048611112), (5, 0.5227322048611112), (4, 0.26372612847222227)] Visit list: {1, 2, 3, 4, 5} Iteration: 24 --- Priority queue: [(5, 1.2135416666666667), (2, 0.5227322048611112), (4, 0.26372612847222227)] Visit list: {1, 2, 3, 4, 5, 6}
Round 0 Priority queue: [(1, 1.0), (2, 1.0)] Visited: {} ---x-----x-----x------- Round 1 Priority queue: [(2, 1.5), (5, 0.5)] Visited: {1} ---x-----x-----x------- Round 2 Priority queue: [(5, 1.25), (3, 0.75)] Visited: {1, 2} ---x-----x-----x------- Round 3 Priority queue: [(1, 1.25), (3, 0.75)] Visited: {1, 2, 5} ---x-----x-----x------- Round 4 Priority queue: [(3, 0.75), (2, 0.625), (5, 0.625)] Visited: {1, 2, 5} ---x-----x-----x------- Round 5 Priority queue: [(5, 0.875), (2, 0.625), (4, 0.25), (6, 0.25)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 6 Priority queue: [(1, 0.875), (2, 0.625), (4, 0.25), (6, 0.25)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 7 Priority queue: [(2, 1.0625), (5, 0.4375), (4, 0.25), (6, 0.25)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 8 Priority queue: [(5, 0.96875), (3, 0.53125), (4, 0.25), (6, 0.25)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 9 Priority queue: [(1, 0.96875), (3, 0.53125), (4, 0.25), (6, 0.25)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 10 Priority queue: [(3, 0.53125), (2, 0.484375), (5, 0.484375), (4, 0.25), (6, 0.25)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 11 Priority queue: [(5, 0.6614583333333334), (2, 0.484375), (4, 0.42708333333333337), (6, 0.42708333333333337)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 12 Priority queue: [(1, 0.6614583333333334), (2, 0.484375), (4, 0.42708333333333337), (6, 0.42708333333333337)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 13 Priority queue: [(2, 0.8151041666666667), (4, 0.42708333333333337), (6, 0.42708333333333337), (5, 0.3307291666666667)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 14 Priority queue: [(5, 0.73828125), (4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 15 Priority queue: [(1, 0.73828125), (4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 16 Priority queue: [(4, 0.42708333333333337), (6, 0.42708333333333337), (3, 0.40755208333333337), (2, 0.369140625), (5, 0.369140625)] Visited: {1, 2, 3, 5} ---x-----x-----x------- Round 17 Priority queue: [(5, 0.5826822916666667), (6, 0.42708333333333337), (3, 0.40755208333333337), (2, 0.369140625), (1, 0.21354166666666669)] Visited: {1, 2, 3, 4, 5} ---x-----x-----x------- Round 18 Priority queue: [(1, 0.7962239583333335), (6, 0.42708333333333337), (3, 0.40755208333333337), (2, 0.369140625)] Visited: {1, 2, 3, 4, 5} ---x-----x-----x------- Round 19 Priority queue: [(2, 0.7672526041666667), (6, 0.42708333333333337), (3, 0.40755208333333337), (5, 0.39811197916666674)] Visited: {1, 2, 3, 4, 5} ---x-----x-----x------- Round 20 Priority queue: [(3, 0.7911783854166667), (5, 0.7817382812500001), (6, 0.42708333333333337)] Visited: {1, 2, 3, 4, 5} ---x-----x-----x------- Round 21 Priority queue: [(5, 1.0454644097222223), (6, 0.6908094618055556), (4, 0.26372612847222227)] Visited: {1, 2, 3, 4, 5} ---x-----x-----x------- Round 22 Priority queue: [(1, 1.0454644097222223), (6, 0.6908094618055556), (4, 0.26372612847222227)] Visited: {1, 2, 3, 4, 5} ---x-----x-----x------- Round 23 Priority queue: [(6, 0.6908094618055556), (2, 0.5227322048611112), (5, 0.5227322048611112), (4, 0.26372612847222227)] Visited: {1, 2, 3, 4, 5} ---x-----x-----x------- Round 24 Priority queue: [(5, 1.2135416666666667), (2, 0.5227322048611112), (4, 0.26372612847222227)] Visited: {1, 2, 3, 4, 5, 6}
Round: 1
Round: 2
Round: 3
Round: 4
Round: 5
Round: 6
Round: 7
Round: 8
Round: 9
Round: 10
Round: 11
Round: 12
Round: 13
Round: 14
Round: 15
Round: 16
Round: 17
Round: 18
Round: 19
Round: 20
Round: 21
Round: 22
Round: 23
Round: 24