+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

master
12.4 KiB438 linesraw
1/**
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements.  See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership.  The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License.  You may obtain a copy of the License at
9 *
10 *     http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18package org.apache.hadoop.examples.dancing;
19
20import java.util.*;
21
22import org.apache.commons.logging.Log;
23import org.apache.commons.logging.LogFactory;
24
25/**
26 * A generic solver for tile laying problems using Knuth's dancing link
27 * algorithm. It provides a very fast backtracking data structure for problems
28 * that can expressed as a sparse boolean matrix where the goal is to select a
29 * subset of the rows such that each column has exactly 1 true in it.
30 * 
31 * The application gives each column a name and each row is named after the
32 * set of columns that it has as true. Solutions are passed back by giving the 
33 * selected rows' names.
34 * 
35 * The type parameter ColumnName is the class of application's column names.
36 */
37public class DancingLinks<ColumnName> {
38  private static final Log LOG = 
39    LogFactory.getLog(DancingLinks.class.getName());
40  
41  /**
42   * A cell in the table with up/down and left/right links that form doubly
43   * linked lists in both directions. It also includes a link to the column
44   * head.
45   */
46  private static class Node<ColumnName> {
47    Node<ColumnName> left;
48    Node<ColumnName> right;
49    Node<ColumnName> up;
50    Node<ColumnName> down;
51    ColumnHeader<ColumnName> head;
52    
53    Node(Node<ColumnName> l, Node<ColumnName> r, Node<ColumnName> u, 
54         Node<ColumnName> d, ColumnHeader<ColumnName> h) {
55      left = l;
56      right = r;
57      up = u;
58      down = d;
59      head = h;
60    }
61    
62    Node() {
63      this(null, null, null, null, null);
64    }
65  }
66  
67  /**
68   * Column headers record the name of the column and the number of rows that 
69   * satisfy this column. The names are provided by the application and can 
70   * be anything. The size is used for the heuristic for picking the next 
71   * column to explore.
72   */
73  private static class ColumnHeader<ColumnName> extends Node<ColumnName> {
74    ColumnName name;
75    int size;
76    
77    ColumnHeader(ColumnName n, int s) {
78      name = n;
79      size = s;
80      head = this;
81    }
82    
83    ColumnHeader() {
84      this(null, 0);
85    }
86  }
87  
88  /**
89   * The head of the table. Left/Right from the head are the unsatisfied 
90   * ColumnHeader objects.
91   */
92  private ColumnHeader<ColumnName> head;
93  
94  /**
95   * The complete list of columns.
96   */
97  private List<ColumnHeader<ColumnName>> columns;
98  
99  public DancingLinks() {
100    head = new ColumnHeader<ColumnName>(null, 0);
101    head.left = head;
102    head.right = head;
103    head.up = head;
104    head.down = head;
105    columns = new ArrayList<ColumnHeader<ColumnName>>(200);
106  }
107  
108  /**
109   * Add a column to the table
110   * @param name The name of the column, which will be returned as part of 
111   *             solutions
112   * @param primary Is the column required for a solution?
113   */
114  public void addColumn(ColumnName name, boolean primary) {
115    ColumnHeader<ColumnName> top = new ColumnHeader<ColumnName>(name, 0);
116    top.up = top;
117    top.down = top;
118    if (primary) {
119      Node<ColumnName> tail = head.left;
120      tail.right = top;
121      top.left = tail;
122      top.right = head;
123      head.left = top;
124    } else {
125      top.left = top;
126      top.right = top;
127    }
128    columns.add(top);
129  }
130  
131  /**
132   * Add a column to the table
133   * @param name The name of the column, which will be included in the solution
134   */
135  public void addColumn(ColumnName name) {
136    addColumn(name, true);
137  }
138  
139  /**
140   * Get the number of columns.
141   * @return the number of columns
142   */
143  public int getNumberColumns() {
144    return columns.size();
145  }
146  
147  /**
148   * Get the name of a given column as a string
149   * @param index the index of the column
150   * @return a string representation of the name
151   */
152  public String getColumnName(int index) {
153    return columns.get(index).name.toString();
154  }
155  
156  /**
157   * Add a row to the table. 
158   * @param values the columns that are satisfied by this row
159   */
160  public void addRow(boolean[] values) {
161    Node<ColumnName> prev = null;
162    for(int i=0; i < values.length; ++i) {
163      if (values[i]) {
164        ColumnHeader<ColumnName> top = columns.get(i);
165        top.size += 1;
166        Node<ColumnName> bottom = top.up;
167        Node<ColumnName> node = new Node<ColumnName>(null, null, bottom, 
168                                                     top, top);
169        bottom.down = node;
170        top.up = node;
171        if (prev != null) {
172          Node<ColumnName> front = prev.right;
173          node.left = prev;
174          node.right = front;
175          prev.right = node;
176          front.left = node;
177        } else {
178          node.left = node;
179          node.right = node;
180        }
181        prev = node;
182      }
183    }
184  }
185  
186  /**
187   * Applications should implement this to receive the solutions to their 
188   * problems.
189   */
190  public interface SolutionAcceptor<ColumnName> {
191    /**
192     * A callback to return a solution to the application.
193     * @param value a List of List of ColumnNames that were satisfied by each
194     *              selected row
195     */
196    void solution(List<List<ColumnName>> value);
197  }
198  
199  /**
200   * Find the column with the fewest choices.
201   * @return The column header
202   */
203  private ColumnHeader<ColumnName> findBestColumn() {
204    int lowSize = Integer.MAX_VALUE;
205    ColumnHeader<ColumnName> result = null;
206    ColumnHeader<ColumnName> current = (ColumnHeader<ColumnName>) head.right;
207    while (current != head) {
208      if (current.size < lowSize) {
209        lowSize = current.size;
210        result = current;
211      }
212      current = (ColumnHeader<ColumnName>) current.right;
213    }
214    return result;
215  }
216  
217  /**
218   * Hide a column in the table
219   * @param col the column to hide
220   */
221  private void coverColumn(ColumnHeader<ColumnName> col) {
222    LOG.debug("cover " + col.head.name);
223    // remove the column
224    col.right.left = col.left;
225    col.left.right = col.right;
226    Node<ColumnName> row = col.down;
227    while (row != col) {
228      Node<ColumnName> node = row.right;
229      while (node != row) {
230        node.down.up = node.up;
231        node.up.down = node.down;
232        node.head.size -= 1;
233        node = node.right;
234      }
235      row = row.down;
236    }
237  }
238  
239  /**
240   * Uncover a column that was hidden.
241   * @param col the column to unhide
242   */
243  private void uncoverColumn(ColumnHeader<ColumnName> col) {
244    LOG.debug("uncover " + col.head.name);
245    Node<ColumnName> row = col.up;
246    while (row != col) {
247      Node<ColumnName> node = row.left;
248      while (node != row) {
249        node.head.size += 1;
250        node.down.up = node;
251        node.up.down = node;
252        node = node.left;
253      }
254      row = row.up;
255    }
256    col.right.left = col;
257    col.left.right = col;
258  }
259  
260  /**
261   * Get the name of a row by getting the list of column names that it 
262   * satisfies.
263   * @param row the row to make a name for
264   * @return the list of column names
265   */
266  private List<ColumnName> getRowName(Node<ColumnName> row) {
267    List<ColumnName> result = new ArrayList<ColumnName>();
268    result.add(row.head.name);
269    Node<ColumnName> node = row.right;
270    while (node != row) {
271      result.add(node.head.name);
272      node = node.right;
273    }
274    return result;
275  }
276  
277  /**
278   * Find a solution to the problem.
279   * @param partial a temporary datastructure to keep the current partial 
280   *                answer in
281   * @param output the acceptor for the results that are found
282   * @return the number of solutions found
283   */
284  private int search(List<Node<ColumnName>> partial, SolutionAcceptor<ColumnName> output) {
285    int results = 0;
286    if (head.right == head) {
287      List<List<ColumnName>> result = new ArrayList<List<ColumnName>>(partial.size());
288      for(Node<ColumnName> row: partial) {
289        result.add(getRowName(row));
290      }
291      output.solution(result);
292      results += 1;
293    } else {
294      ColumnHeader<ColumnName> col = findBestColumn();
295      if (col.size > 0) {
296        coverColumn(col);
297        Node<ColumnName> row = col.down;
298        while (row != col) {
299          partial.add(row);
300          Node<ColumnName> node = row.right;
301          while (node != row) {
302            coverColumn(node.head);
303            node = node.right;
304          }
305          results += search(partial, output);
306          partial.remove(partial.size() - 1);
307          node = row.left;
308          while (node != row) {
309            uncoverColumn(node.head);
310            node = node.left;
311          }
312          row = row.down;
313        }
314        uncoverColumn(col);
315      }
316    }
317    return results;
318  }
319  
320  /**
321   * Generate a list of prefixes down to a given depth. Assumes that the 
322   * problem is always deeper than depth.
323   * @param depth the depth to explore down
324   * @param choices an array of length depth to describe a prefix
325   * @param prefixes a working datastructure
326   */
327  private void searchPrefixes(int depth, int[] choices, 
328                              List<int[]> prefixes) {
329    if (depth == 0) {
330      prefixes.add(choices.clone());
331    } else {
332      ColumnHeader<ColumnName> col = findBestColumn();
333      if (col.size > 0) {
334        coverColumn(col);
335        Node<ColumnName> row = col.down;
336        int rowId = 0;
337        while (row != col) {
338          Node<ColumnName> node = row.right;
339          while (node != row) {
340            coverColumn(node.head);
341            node = node.right;
342          }
343          choices[choices.length - depth] = rowId;
344          searchPrefixes(depth - 1, choices, prefixes);
345          node = row.left;
346          while (node != row) {
347            uncoverColumn(node.head);
348            node = node.left;
349          }
350          row = row.down;
351          rowId += 1;
352        }
353        uncoverColumn(col);
354      }
355    }
356  }
357  
358  /**
359   * Generate a list of row choices to cover the first moves.
360   * @param depth the length of the prefixes to generate
361   * @return a list of integer arrays that list the rows to pick in order
362   */
363  public List<int[]> split(int depth) {
364    int[] choices = new int[depth];
365    List<int[]> result = new ArrayList<int[]>(100000);
366    searchPrefixes(depth, choices, result);
367    return result;
368  }
369
370  /**
371   * Make one move from a prefix
372   * @param goalRow the row that should be choosen
373   * @return the row that was found
374   */
375  private Node<ColumnName> advance(int goalRow) {
376    ColumnHeader<ColumnName> col = findBestColumn();
377    if (col.size > 0) {
378      coverColumn(col);
379      Node<ColumnName> row = col.down;
380      int id = 0;
381      while (row != col) {
382        if (id == goalRow) {
383          Node<ColumnName> node = row.right;
384          while (node != row) {
385            coverColumn(node.head);
386            node = node.right;
387          }
388          return row;
389        }
390        id += 1;
391        row = row.down;
392      }
393    }
394    return null;
395  }
396  
397  /**
398   * Undo a prefix exploration
399   * @param row
400   */
401  private void rollback(Node<ColumnName> row) {
402    Node<ColumnName> node = row.left;
403    while (node != row) {
404      uncoverColumn(node.head);
405      node = node.left;
406    }
407    uncoverColumn(row.head);
408  }
409  
410  /**
411   * Given a prefix, find solutions under it.
412   * @param prefix a list of row choices that control which part of the search
413   *               tree to explore
414   * @param output the output for each solution
415   * @return the number of solutions
416   */
417  public int solve(int[] prefix, SolutionAcceptor<ColumnName> output) {
418    List<Node<ColumnName>> choices = new ArrayList<Node<ColumnName>>();
419    for(int i=0; i < prefix.length; ++i) {
420      choices.add(advance(prefix[i]));
421    }
422    int result = search(choices, output);
423    for(int i=prefix.length-1; i >=0; --i) {
424      rollback(choices.get(i));
425    }
426    return result;
427  }
428  
429  /**
430   * Solve a complete problem
431   * @param output the acceptor to receive answers
432   * @return the number of solutions
433   */
434  public int solve(SolutionAcceptor<ColumnName> output) {
435    return search(new ArrayList<Node<ColumnName>>(), output);
436  }
437  
438}