1 import java.util.Random;
3 * This class implements nodes (both E- and H-nodes) of the EM graph. Sets
4 * up random neighbors and propagates field values among neighbors.
8 * The value of the node.
12 * The next node in the list.
16 * Array of nodes to which we send our value.
20 * Array of nodes from which we receive values.
24 * Coefficients on the fromNodes edges
28 * The number of fromNodes edges
32 * Used to create the fromEdges - keeps track of the number of edges that have
42 * Constructor for a node with given `degree'. The value of the
43 * node is initialized to a random value.
45 public Node(int degree, Random r)
47 value = r.nextDouble();
48 // create empty array for holding toNodes
49 toNodes = new Node[degree];
52 for (int i = 0; i<fromCount; i++) {
63 * Create the linked list of E or H nodes. We create a table which is used
64 * later to create links among the nodes.
65 * @param size the no. of nodes to create
66 * @param degree the out degree of each node
67 * @return a table containing all the nodes.
69 public Node[] fillTable(int size, int degree, Random r)
71 Node[] table = new Node[size];
73 Node prevNode = new Node(degree, r);
75 for (int i = 1; i < size; i++) {
76 Node curNode = new Node(degree, r);
78 prevNode.next = curNode;
85 * Create unique `degree' neighbors from the nodes given in nodeTable.
86 * We do this by selecting a random node from the give nodeTable to
87 * be neighbor. If this neighbor has been previously selected, then
88 * a different random neighbor is chosen.
89 * @param nodeTable the list of nodes to choose from.
91 public void makeUniqueNeighbors(Node[] nodeTable, Random rand)
93 for (int filled = 0; filled < toNodes.length; filled++) {
98 // generate a random number in the correct range
99 int index = rand.nextInt();
100 if (index < 0) index = -index;
101 index = index % nodeTable.length;
103 // find a node with the random index in the given table
104 otherNode = nodeTable[index];
106 for (k = 0; k < filled; k++) {
107 if (otherNode == toNodes[filled])
110 } while (k < filled);
112 // other node is definitely unique among "filled" toNodes
113 toNodes[filled] = otherNode;
115 // update fromCount for the other node
116 otherNode.fromCount++;
120 public void makeUniqueNeighborsThread(Node[] nodeTable, Random rand, int l, int u)
122 for (int filled = 0; filled < toNodes.length; filled++) {
127 // generate a random number in the correct range
128 int index = rand.nextInt();
129 if (index < 0) index = -index;
130 index = index % nodeTable.length;
132 // find a node with the random index in the given table
133 otherNode = nodeTable[index];
135 for (k = 0; k < filled; k++) {
136 if (otherNode == toNodes[filled])
139 } while (k < filled);
141 // other node is definitely unique among "filled" toNodes
142 toNodes[filled] = otherNode;
144 // update fromCount for the other node
145 otherNode.fromCount++;
151 * Allocate the right number of FromNodes for this node. This
152 * step can only happen once we know the right number of from nodes
153 * to allocate. Can be done after unique neighbors are created and known.
155 * It also initializes random coefficients on the edges.
157 public void makeFromNodes()
159 fromNodes = new Node[fromCount]; // nodes fill be filled in later
160 coeffs = new double[fromCount];
164 * Fill in the fromNode field in "other" nodes which are pointed to
167 public void updateFromNodes(Random rand)
169 for (int i = 0; i < toNodes.length; i++) {
170 Node otherNode = toNodes[i];
171 int count = otherNode.fromLength++;
172 otherNode.fromNodes[count] = this;
173 otherNode.coeffs[count] = rand.nextDouble();
178 * Get the new value of the current node based on its neighboring
179 * from_nodes and coefficients.
186 for (int i = 0; i < n.fromCount; i++) {
187 n.value -= n.coeffs[i] * n.fromNodes[i].value;
194 public void computeNewValue()
196 for (int i = 0; i < fromCount; i++) {
197 value -= coeffs[i] * fromNodes[i].value;
202 * Override the toString method to return the value of the node.
203 * @return the value of the node.
205 public String toString()
207 return "value " + value + ", from_count " + fromCount;