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