source: ip/src/main/java/geniusweb/ip/ipSolver/IntegerPartitionGraph.java@ 52

Last change on this file since 52 was 52, checked in by ruud, 14 months ago

Fixed small issues in domaineditor.
File size: 14.1 KB
Line 
1package geniusweb.ip.ipSolver;
2
3import geniusweb.ip.general.IntegerPartition;
4
5public class IntegerPartitionGraph {
6 public Node[][] nodes;
7 public int largestIntegerBeingSplitInThisGraph;
8
9 // *****************************************************************************************************
10
11 /**
12 * Constructor. Places the subspaces into an integer partition graph
13 */
14 public IntegerPartitionGraph(Subspace[][] subspaces, int numOfAgents,
15 int largestIntegerBeingSplitInThisGraph) {
16 this.largestIntegerBeingSplitInThisGraph = largestIntegerBeingSplitInThisGraph;
17
18 // create a node for each subspace
19 nodes = new Node[numOfAgents][];
20 for (int level = 0; level < numOfAgents; level++) { // For each level
21 nodes[level] = new Node[subspaces[level].length];
22 for (int i = 0; i < subspaces[level].length; i++) { // For each
23 // subspace in
24 // the current
25 // level
26 nodes[level][i] = new Node(subspaces[level][i]);
27 }
28 }
29 // Create the edges of the graph
30 for (int level = 0; level < numOfAgents - 1; level++) { // For each
31 // level
32 for (int i = 0; i < nodes[level].length; i++) // For each node in
33 // the current level
34 {
35 IntegerPartition[] listOfDirectlyConnectedIntegerPartitions = nodes[level][i].integerPartition
36 .getListOfDirectedlyConnectedIntegerPartitions(
37 largestIntegerBeingSplitInThisGraph, 0);
38 if (listOfDirectlyConnectedIntegerPartitions == null) {
39 nodes[level][i].edgesFromThisNode = null;
40 } else {
41 nodes[level][i].edgesFromThisNode = new Edge[listOfDirectlyConnectedIntegerPartitions.length];
42 int index = 0;
43 for (int j = 0; j < nodes[level + 1].length; j++) { // For
44 // each
45 // node
46 // in
47 // the
48 // NEXT
49 // level
50 int[] integersThatResultedFromTheSplit = getIntegersThatResultedFromTheSplit(
51 nodes[level][i],
52 listOfDirectlyConnectedIntegerPartitions,
53 nodes[level + 1][j],
54 largestIntegerBeingSplitInThisGraph);
55 if (integersThatResultedFromTheSplit != null) {
56 int[] sortedParts1 = nodes[level][i].integerPartition.partsSortedAscendingly;
57 int[] sortedParts2 = nodes[level
58 + 1][j].integerPartition.partsSortedAscendingly;
59 int partThatWasSplit = -1;
60 for (int k = sortedParts1.length - 1; k >= 0; k--) { // compare
61 // the
62 // two
63 // arrays,
64 // STARTING
65 // FROM
66 // THE
67 // END
68 if (sortedParts1[k] != sortedParts2[k + 1]) {
69 partThatWasSplit = sortedParts1[k];
70 break;
71 }
72 }
73 nodes[level][i].edgesFromThisNode[index] = new Edge(
74 nodes[level + 1][j], partThatWasSplit,
75 integersThatResultedFromTheSplit);
76 index++;
77 if (index == nodes[level][i].edgesFromThisNode.length)
78 break;
79 }
80 }
81 }
82 }
83 }
84 }
85
86 // *****************************************************************************************************
87
88 /**
89 * Updates the edges, based on the fact that the current
90 * "largestIntegerBeingSplitInThisGraph" is greater than the previous
91 * "largestIntegerBeingSplitInThisGraph".
92 */
93 public void updateEdges(int numOfAgents,
94 int largestIntegerBeingSplitInThisGraph) {
95 int prev_largestIntegerBeingSplitInThisGraph = this.largestIntegerBeingSplitInThisGraph;
96 if (prev_largestIntegerBeingSplitInThisGraph >= largestIntegerBeingSplitInThisGraph)
97 return;
98
99 // Update the edges of the graph
100 for (int level = 1; level < numOfAgents - 1; level++) { // For each
101 // level
102 // STARTINNG
103 // FROM THE
104 // SECOND ONE!!!
105 for (int i = 0; i < nodes[level].length; i++) // For each node in
106 // the current level
107 {
108 IntegerPartition[] listOfDirectlyConnectedIntegerPartitions = nodes[level][i].integerPartition
109 .getListOfDirectedlyConnectedIntegerPartitions(
110 largestIntegerBeingSplitInThisGraph,
111 prev_largestIntegerBeingSplitInThisGraph);
112 if (listOfDirectlyConnectedIntegerPartitions != null) {
113 // in this case, we need to ADD to the existing list of
114 // edges
115 int index;
116 if (nodes[level][i].edgesFromThisNode == null) { // create a
117 // list
118 // of
119 // edges
120 // from
121 // scratch
122 index = 0;
123 nodes[level][i].edgesFromThisNode = new Edge[listOfDirectlyConnectedIntegerPartitions.length];
124 } else { // add to the existing list of edges
125 index = nodes[level][i].edgesFromThisNode.length;
126 Edge[] tempListOfEdges = new Edge[nodes[level][i].edgesFromThisNode.length
127 + listOfDirectlyConnectedIntegerPartitions.length];
128 for (int j = 0; j < nodes[level][i].edgesFromThisNode.length; j++)
129 tempListOfEdges[j] = nodes[level][i].edgesFromThisNode[j];
130 nodes[level][i].edgesFromThisNode = tempListOfEdges;
131 }
132 for (int j = 0; j < nodes[level + 1].length; j++) { // For
133 // each
134 // node
135 // in
136 // the
137 // NEXT
138 // level
139 int[] integersThatResultedFromTheSplit = getIntegersThatResultedFromTheSplit(
140 nodes[level][i],
141 listOfDirectlyConnectedIntegerPartitions,
142 nodes[level + 1][j],
143 largestIntegerBeingSplitInThisGraph);
144 if (integersThatResultedFromTheSplit != null) {
145 int[] sortedParts1 = nodes[level][i].integerPartition.partsSortedAscendingly;
146 int[] sortedParts2 = nodes[level
147 + 1][j].integerPartition.partsSortedAscendingly;
148 int partThatWasSplit = -1;
149 for (int k = sortedParts1.length - 1; k >= 0; k--) { // compare
150 // the
151 // two
152 // arrays,
153 // STARTING
154 // FROM
155 // THE
156 // END
157 if (sortedParts1[k] != sortedParts2[k + 1]) {
158 partThatWasSplit = sortedParts1[k];
159 break;
160 }
161 }
162 nodes[level][i].edgesFromThisNode[index] = new Edge(
163 nodes[level + 1][j], partThatWasSplit,
164 integersThatResultedFromTheSplit);
165 index++;
166 if (index == nodes[level][i].edgesFromThisNode.length)
167 break;
168 }
169 }
170 }
171 }
172 }
173 this.largestIntegerBeingSplitInThisGraph = largestIntegerBeingSplitInThisGraph;
174 }
175
176 // *****************************************************************************************************
177
178 /**
179 * Given two nodes that are at two consecutive levels, the method returns
180 * true iff there is an edge between the two nodes
181 */
182 private int[] getIntegersThatResultedFromTheSplit(Node nodeOnLowLevel,
183 IntegerPartition[] listOfDirectlyConnectedIntegerPartitions,
184 Node nodeOnHighLevel, int largestIntegerBeingSplitInThisGraph) {
185 int[] multiplicity1 = nodeOnHighLevel.integerPartition.sortedMultiplicity;
186 int underlyingSet1 = nodeOnHighLevel.integerPartition.sortedUnderlyingSetInBitFormat;
187
188 for (int i = 0; i < listOfDirectlyConnectedIntegerPartitions.length; i++) {
189 int[] multiplicity2 = listOfDirectlyConnectedIntegerPartitions[i].sortedMultiplicity;
190 int underlyingSet2 = listOfDirectlyConnectedIntegerPartitions[i].sortedUnderlyingSetInBitFormat;
191
192 if (underlyingSet1 != underlyingSet2)
193 continue;
194
195 boolean notEqual = false;
196 for (int j = 0; j < multiplicity1.length; j++) {
197 if (multiplicity1[j] != multiplicity2[j]) {
198 notEqual = true;
199 break;
200 }
201 }
202 if (notEqual)
203 continue;
204
205 return (listOfDirectlyConnectedIntegerPartitions[i].tempIntegersThatResultedFromASplit);
206 }
207 return (null);
208 }
209
210 // *****************************************************************************************************
211
212 /**
213 * For every node in the graph, this methods determines whether it is
214 * reachable from the bottom node, and that is given the m parameter
215 */
216 public void setReachabilityOfSubspaces(int m, int numOfAgents) {
217 // For every node, initlialize its reachability from the bottom node
218 for (int level = 0; level < 2; level++)
219 for (int i = 0; i < nodes[level].length; i++)
220 nodes[level][i].subspace.isReachableFromBottomNode = true;
221 for (int level = 2; level < numOfAgents; level++)
222 for (int i = 0; i < nodes[level].length; i++)
223 nodes[level][i].subspace.isReachableFromBottomNode = false;
224
225 // Delete the edges that split an integer greater than, or equal to, m
226 for (int level = 1; level < numOfAgents - 1; level++) {
227 for (int i = 0; i < nodes[level].length; i++) {
228 Node curNode = nodes[level][i];
229 if (curNode.edgesFromThisNode != null)
230 for (int j = 0; j < curNode.edgesFromThisNode.length; j++) {
231 if ((curNode.edgesFromThisNode[j] != null)
232 && (curNode.edgesFromThisNode[j].partThatWasSplit >= m))
233 curNode.edgesFromThisNode[j] = null;
234 }
235 }
236 }
237 // For every node, compute its reachability from the bottom node
238 for (int level = 1; level < numOfAgents - 1; level++) {
239 for (int i = 0; i < nodes[level].length; i++) {
240 Node curNode = nodes[level][i];
241 if (curNode.subspace.isReachableFromBottomNode == false) {
242 continue;
243 }
244 if (curNode.edgesFromThisNode != null)
245 for (int j = 0; j < curNode.edgesFromThisNode.length; j++) {
246 if (curNode.edgesFromThisNode[j] != null)
247 curNode.edgesFromThisNode[j].node.subspace.isReachableFromBottomNode = true;
248 }
249 }
250 }
251 }
252
253 // *****************************************************************************************************
254
255 /**
256 * Returns a list of nodes that are reachable from the given node. This, of
257 * course, only considers the edges that are currently present in this
258 * integer partition graph.
259 */
260 public Node[] getReachableNodes(Node node) {
261 if (node.edgesFromThisNode == null)
262 return (null);
263
264 int numOfIntegersInNode = node.integerPartition.partsSortedAscendingly.length;
265
266 // mark all nodes above "node" as unreachable
267 node.tempIntegerRoots = null;
268 for (int level = numOfIntegersInNode; level < nodes.length; level++) {
269 for (int i = 0; i < nodes[level].length; i++) {
270 nodes[level][i].tempFlag = false;
271 nodes[level][i].tempIntegerRoots = null;
272 }
273 }
274 // mark all nodes that are "directly" connected to "node" as reachable
275 for (int i = 0; i < node.edgesFromThisNode.length; i++) {
276 node.edgesFromThisNode[i].node.tempFlag = true;
277 setIntegerRoots(node, node.edgesFromThisNode[i].node,
278 node.edgesFromThisNode[i].twoPartsThatResultedFromTheSplit,
279 node.edgesFromThisNode[i].partThatWasSplit);
280 }
281 // continue to mark nodes as reachable...
282 int numOfReachableNodes = 0;
283 for (int level = numOfIntegersInNode; level < nodes.length
284 - 1; level++) {
285 for (int i = 0; i < nodes[level].length; i++) {
286 if (nodes[level][i].tempFlag) {
287 numOfReachableNodes++;
288 if (nodes[level][i].edgesFromThisNode != null) {
289 for (int j = 0; j < nodes[level][i].edgesFromThisNode.length; j++) {
290 if (nodes[level][i].edgesFromThisNode[j].node.tempFlag == false) {
291 nodes[level][i].edgesFromThisNode[j].node.tempFlag = true;
292 setIntegerRoots(nodes[level][i],
293 nodes[level][i].edgesFromThisNode[j].node,
294 nodes[level][i].edgesFromThisNode[j].twoPartsThatResultedFromTheSplit,
295 nodes[level][i].edgesFromThisNode[j].partThatWasSplit);
296 }
297 }
298 }
299 }
300 }
301 }
302 // Put the nodes that have "flag = true" in the list of reachable nodes
303 int index = 0;
304 Node[] listOfReachableNodes = new Node[numOfReachableNodes];
305 for (int level = numOfIntegersInNode; level < nodes.length
306 - 1; level++) {
307 for (int i = 0; i < nodes[level].length; i++) {
308 if (nodes[level][i].tempFlag) {
309 listOfReachableNodes[index] = nodes[level][i];
310 index++;
311 }
312 }
313 }
314 return (listOfReachableNodes);
315 }
316
317 // *****************************************************************************************************
318
319 /**
320 * for every integer "i", we keep track of its root, i.e., the integer that
321 * I kept splitting until I got "i"
322 */
323 private void setIntegerRoots(Node lowerNode, Node upperNode,
324 int[] twoPartsThatResultedFromTheSplit, int partThatWasSplit) {
325 int[] upperIntegers = upperNode.integerPartition.partsSortedAscendingly;
326 int[] lowerIntegers = lowerNode.integerPartition.partsSortedAscendingly;
327
328 // initializate all roots to be equal to -1
329 upperNode.tempIntegerRoots = new int[upperIntegers.length];
330 for (int i = 0; i < upperNode.tempIntegerRoots.length; i++)
331 upperNode.tempIntegerRoots[i] = -1;
332
333 if (lowerNode.tempIntegerRoots == null) {
334 // set the root for every one of two parts that resulted from the
335 // split
336 for (int k = 0; k < twoPartsThatResultedFromTheSplit.length; k++)
337 for (int j = 0; j < upperIntegers.length; j++)
338 if ((twoPartsThatResultedFromTheSplit[k] == upperIntegers[j])
339 && (upperNode.tempIntegerRoots[j] == -1)) {
340 upperNode.tempIntegerRoots[j] = partThatWasSplit;
341 break;
342 }
343 // set the root for every other integer to be equal to the integer
344 // itself
345 for (int j = 0; j < upperIntegers.length; j++)
346 if (upperNode.tempIntegerRoots[j] == -1)
347 upperNode.tempIntegerRoots[j] = upperIntegers[j];
348 } else {
349 // Initialization
350 int newRoot = -10;
351 int indexOfNewRoot = -10;
352
353 // get the new integer root
354 for (int i = 0; i < lowerIntegers.length; i++)
355 if (lowerIntegers[i] == partThatWasSplit) {
356 indexOfNewRoot = i;
357 newRoot = lowerNode.tempIntegerRoots[i];
358 }
359
360 // set the root of every integer except the two that resulted from
361 // the split
362 for (int i = 0; i < lowerNode.tempIntegerRoots.length; i++) {
363 if (i == indexOfNewRoot)
364 continue;
365
366 for (int j = 0; j < upperIntegers.length; j++)
367 if ((upperIntegers[j] == lowerIntegers[i])
368 && (upperNode.tempIntegerRoots[j] == -1)) {
369 upperNode.tempIntegerRoots[j] = lowerNode.tempIntegerRoots[i];
370 break;
371 }
372 }
373 // set the root for the two integers that resulted from the split
374 for (int j = 0; j < upperIntegers.length; j++)
375 if (upperNode.tempIntegerRoots[j] == -1)
376 upperNode.tempIntegerRoots[j] = newRoot;
377 }
378 }
379}
Note: See TracBrowser for help on using the repository browser.