1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
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
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.utils.datastructures;
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;
23 * This class contains utilities for finding solutions for a tree of problems.
24 * (e.g. path finding, routing, etc)
26 * @author Toni Kalajainen
28 public class TreeProblem {
30 public interface ProblemNode {
32 * Get the cost to reach this node
33 * @return cost of reaching this node
38 * Is this problem node a solution
39 * @return true if this node is a solution
44 * Branch this problem into sub-problem
45 * @param list add sub-problems to the list
47 void branch(Collection<ProblemNode> list);
50 private final static Comparator<ProblemNode> COST_COMPARATOR =
51 new Comparator<ProblemNode>() {
53 public int compare(ProblemNode o1, ProblemNode o2) {
54 double c1 = o1.getCost();
55 double c2 = o2.getCost();
62 * Find any solution greedily (not optimal)
65 * @return a node that is complete, i.e. solves the specified problem or
66 * <code>null</code> if no solution was found
68 public static ProblemNode findSolution(ProblemNode root, int degree)
70 LinkedList<LinkedList<ProblemNode>> stack = new LinkedList<LinkedList<ProblemNode>>();
71 LinkedList<ProblemNode> lst = new LinkedList<ProblemNode>();
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>();
82 Collections.sort(lst, COST_COMPARATOR);
90 * Find optimal solution
93 * @return the optimal solution for the specified problem or
94 * <code>null</code> if no solution exists.
96 public static ProblemNode findOptimalSolution(ProblemNode root)
98 ArrayList<ProblemNode> lst = new ArrayList<ProblemNode>();
99 PriorityQueue<ProblemNode> pq = new PriorityQueue<ProblemNode>(16, COST_COMPARATOR);
101 while (!pq.isEmpty()) {
102 ProblemNode node = pq.poll();
103 if (node.isComplete()) return node;