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

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