bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/TreeProblem.java

   1 /*******************************************************************************\r
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
   3  * in Industry THTH ry.\r
   4  * All rights reserved. This program and the accompanying materials\r
   5  * are made available under the terms of the Eclipse Public License v1.0\r
   6  * which accompanies this distribution, and is available at\r
   7  * http://www.eclipse.org/legal/epl-v10.html\r
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.utils.datastructures;\r
  13 \r
  14 import java.util.ArrayList;\r
  15 import java.util.Collection;\r
  16 import java.util.Collections;\r
  17 import java.util.Comparator;\r
  18 import java.util.LinkedList;\r
  19 import java.util.PriorityQueue;\r
  20 \r
  21 \r
  22 /**\r
  23  * This class contains utilities for finding solutions for a tree of problems.\r
  24  * (e.g. path finding, routing, etc)\r
  25  * \r
  26  * @author Toni Kalajainen\r
  27  */\r
  28 public class TreeProblem {\r
  29 \r
  30         public interface ProblemNode {\r
  31                 /**\r
  32                  * Get the cost to reach this node\r
  33                  * @return cost of reaching this node\r
  34                  */\r
  35                 double getCost(); \r
  36                 \r
  37                 /** \r
  38                  * Is this problem node a solution\r
  39                  * @return true if this node is a solution\r
  40                  */\r
  41                 boolean isComplete();\r
  42                 \r
  43                 /**\r
  44                  * Branch this problem into sub-problem\r
  45                  * @param list add sub-problems to the list\r
  46                  */\r
  47                 void branch(Collection<ProblemNode> list);\r
  48         }\r
  49         \r
  50         private final static Comparator<ProblemNode> COST_COMPARATOR =\r
  51                 new Comparator<ProblemNode>() {\r
  52                         @Override\r
  53                         public int compare(ProblemNode o1, ProblemNode o2) {\r
  54                                 double c1 = o1.getCost();\r
  55                                 double c2 = o2.getCost();\r
  56                                 if (c1<c2) return -1;\r
  57                                 if (c1>c2) return 1;\r
  58                                 return 0;\r
  59                         }};\r
  60 \r
  61     /**\r
  62      * Find any solution greedily (not optimal)\r
  63      * \r
  64      * @param root\r
  65      * @return a node that is complete, i.e. solves the specified problem or\r
  66      *         <code>null</code> if no solution was found\r
  67      */\r
  68         public static ProblemNode findSolution(ProblemNode root, int degree)\r
  69         {\r
  70                 LinkedList<LinkedList<ProblemNode>> stack = new LinkedList<LinkedList<ProblemNode>>();          \r
  71                 LinkedList<ProblemNode> lst = new LinkedList<ProblemNode>();            \r
  72                 lst.add(root);\r
  73                 stack.add(lst);\r
  74                 while (!stack.isEmpty()) {\r
  75                         lst = stack.peekLast();\r
  76                         ProblemNode b = lst.removeFirst();\r
  77                         if (lst.isEmpty()) stack.removeLast();\r
  78                         if (b.isComplete()) return b;\r
  79                         lst = new LinkedList<ProblemNode>();\r
  80                         b.branch(lst);\r
  81                         if (!lst.isEmpty()) {\r
  82                                 Collections.sort(lst, COST_COMPARATOR);\r
  83                                 stack.addLast(lst);\r
  84                         }\r
  85                 }\r
  86                 return null;\r
  87         }\r
  88 \r
  89     /**\r
  90      * Find optimal solution\r
  91      * \r
  92      * @param root\r
  93      * @return the optimal solution for the specified problem or\r
  94      *         <code>null</code> if no solution exists.\r
  95      */\r
  96         public static ProblemNode findOptimalSolution(ProblemNode root)\r
  97         {\r
  98                 ArrayList<ProblemNode> lst = new ArrayList<ProblemNode>();\r
  99                 PriorityQueue<ProblemNode> pq = new PriorityQueue<ProblemNode>(16, COST_COMPARATOR);\r
 100                 pq.add(root);\r
 101                 while (!pq.isEmpty()) {\r
 102                         ProblemNode node = pq.poll();\r
 103                         if (node.isComplete()) return node;\r
 104                         //node.branch(pq);\r
 105                         lst.clear();\r
 106                         node.branch(lst);\r
 107                         pq.addAll(lst);\r
 108                 }\r
 109                 return null;\r
 110         }\r
 111         \r
 112 }\r