DancingLinks.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:12k
源码类别:

网格计算

开发平台:

Java

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