考虑以下树:
我想要做的是模拟树波算法,这样如果一个节点从除一个直接连接的邻居之外的所有节点接收到一个令牌,它就会向那个沉默的邻居发送一个令牌(对于叶节点总是如此)。如果一个节点从沉默的邻居那里收到一个令牌,就会做出决定。节点总是 7,树结构相同,所以我总是知道每个节点的邻居(直接连接的节点)。
树算法伪代码:
我有以下对象:
public final class Node implements Runnable {
private final int name;
// Indicating token receiving from neighbours
private Map<Node, Boolean> neigh = new
HashMap<Node, Boolean>();
public Node(int name) {
this.name = name;
}
public int getName() {
return name;
}
public void addNeigh(Node node) {
neigh.put(node, false);
}
private int flag() {
Collection<Boolean> c = neigh.values();
int count = 0;
for (Boolean bool : c) {
if (!bool) {
count++;
}
}
return count;
}
private Node getSilentNeigh() {
for (Entry<Node, Boolean> entry : neigh.entrySet()) {
if (false == entry.getValue()) {
return entry.getKey();
}
}
return null;
}
public void sendToken(Node from, String token) {
Node n;
if ((n = getSilentNeigh()) != null && flag() == 1) {
if (from.equals(n)) {
System.out.println(name + " decides!");
}
}
neigh.put(from, true);
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof Node)) {
return false;
}
final Node n = (Node) obj;
return name == n.name;
}
@Override
public int hashCode() {
int hc = 17;
return 37 * hc + name;
}
@Override
public void run() {
while(flag() > 1);
Node n = getSilentNeigh();
System.out.println(name + " sends token to " + n.getName());
n.sendToken(this, "token");
}
@Override
public String toString() {
return "Node " + name;
}
}
在 run() 方法内部有一个 while(condition) 实际上意味着.. 等待(从邻居接收令牌),当只有一个邻居节点没有收到令牌时,向他发送令牌。
这就是我创建节点以及相互关联的方式:
// Number of nodes
int numberOfNodes = 7;
// Array of nodes
Node[] nodes = new Node[numberOfNodes];
for (int i = 0; i < nodes.length; i++) {
// Creating node
nodes[i] = new Node(i);
}
nodes[0].addNeigh(nodes[1]);
nodes[0].addNeigh(nodes[2]);
nodes[1].addNeigh(nodes[0]);
nodes[1].addNeigh(nodes[3]);
nodes[1].addNeigh(nodes[4]);
nodes[2].addNeigh(nodes[0]);
nodes[2].addNeigh(nodes[5]);
nodes[2].addNeigh(nodes[6]);
nodes[3].addNeigh(nodes[1]);
nodes[4].addNeigh(nodes[1]);
nodes[5].addNeigh(nodes[2]);
nodes[6].addNeigh(nodes[2]);
我所做的是随机选择要执行的节点顺序:
// List holding random node numbers
List numbers = new ArrayList<Integer>();
int chosen = 0;
while (chosen < numberOfNodes) {
int processNum = randInt(0, (numberOfNodes - 1));
if (!numbers.contains(Integer.valueOf(processNum))) {
numbers.add(new Integer(processNum));
chosen++;
}
}
因此,例如节点可以按任何顺序排列:
0, 5, 3, 4, 6, 2, 1
5, 3, 0, 2, 1, 6, 4
3, 1, 0, 2, 4, 6, 5
然后我启动线程:
for (Integer number : numbers) {
Thread thread = new Thread(nodes[number]);
thread.start();
}
有时我会得到预期的结果(2 必须决定):
Nodes selected: 0, 4, 5, 2, 6, 3, 1
5 sends token to 2
4 sends token to 1
6 sends token to 2
3 sends token to 1
1 sends token to 0
0 sends token to 2
2 decides!
2 sends token to 0
0 decides!
但通常我得到一个错误,只有一个决定:
Nodes selected: 5, 3, 4, 6, 0, 2, 1
3 sends token to 1
5 sends token to 2
4 sends token to 1
6 sends token to 2
2 sends token to 0
0 sends token to 1
1 decides!
Exception in thread "Thread-6" java.lang.NullPointerException
at uk.ac.ncl.csc8103.wave.Node.run(Node.java:86)
at java.lang.Thread.run(Thread.java:745)
是的,这是一个作业,我真的很接近这些人..但我正面临这个问题。