1 /*
2 * Created on Mar 3, 2007
3 *
4 * Copyright (c) 2007, the JUNG Project and the Regents of the University
5 * of California
6 * All rights reserved.
7 *
8 * This software is open-source under the BSD license; see either
9 * "license.txt" or
10 * http://jung.sourceforge.net/license.txt for a description.
11 */
12 package edu.uci.ics.jung.graph.util;
13
14 import edu.uci.ics.jung.graph.Forest;
15 import edu.uci.ics.jung.graph.Tree;
16
17 import java.util.ArrayList;
18 import java.util.Collection;
19 import java.util.List;
20
21 /**
22 * Contains static methods for operating on instances of <code>Tree</code>.
23 */
24 public class TreeUtils
25 {
26 /**
27 * Returns the roots of this forest.
28 * @param <V> the vertex type
29 * @param <E> the edge type
30 */
31 public static <V,E> List<V> getRoots(Forest<V,E> forest)
32 {
33 List<V> roots = new ArrayList<V>();
34 for(Tree<V,E> tree : forest.getTrees()) {
35 roots.add(tree.getRoot());
36 }
37 return roots;
38 }
39
40 /**
41 * Returns the subtree of <code>tree</code> which is rooted at <code>root</code> as a <code>Forest<V,E></code>.
42 * The tree returned is an independent entity, although it uses the same vertex and edge objects.
43 * @param <V> the vertex type
44 * @param <E> the edge type
45 * @param forest the tree whose subtree is to be extracted
46 * @param root the root of the subtree to be extracted
47 * @return the subtree of <code>tree</code> which is rooted at <code>root</code>
48 * @throws InstantiationException if a new tree of the same type cannot be created
49 * @throws IllegalAccessException
50 */
51 @SuppressWarnings("unchecked")
52 public static <V,E> Tree<V,E> getSubTree(Forest<V,E> forest, V root) throws InstantiationException, IllegalAccessException
53 {
54 if (!forest.containsVertex(root))
55 throw new IllegalArgumentException("Specified tree does not contain the specified root as a vertex");
56 Forest<V,E> subforest = forest.getClass().newInstance();
57 subforest.addVertex(root);
58 growSubTree(forest, subforest, root);
59
60 return subforest.getTrees().iterator().next();
61 }
62
63 /**
64 * Populates <code>subtree</code> with the subtree of <code>tree</code>
65 * which is rooted at <code>root</code>.
66 * @param <V> the vertex type
67 * @param <E> the edge type
68 * @param tree the tree whose subtree is to be extracted
69 * @param subTree the tree instance which is to be populated with the subtree of <code>tree</code>
70 * @param root the root of the subtree to be extracted
71 */
72 public static <V,E> void growSubTree(Forest<V,E> tree, Forest<V,E> subTree, V root) {
73 if(tree.getSuccessorCount(root) > 0) {
74 Collection<E> edges = tree.getOutEdges(root);
75 for(E e : edges) {
76 subTree.addEdge(e, tree.getEndpoints(e));
77 }
78 Collection<V> kids = tree.getSuccessors(root);
79 for(V kid : kids) {
80 growSubTree(tree, subTree, kid);
81 }
82 }
83 }
84
85 /**
86 * Connects <code>subTree</code> to <code>tree</code> by attaching it as a child
87 * of <code>node</code> with edge <code>connectingEdge</code>.
88 * @param <V> the vertex type
89 * @param <E> the edge type
90 * @param tree the tree to which <code>subTree</code> is to be added
91 * @param subTree the tree which is to be grafted on to <code>tree</code>
92 * @param node the parent of <code>subTree</code> in its new position in <code>tree</code>
93 * @param connectingEdge the edge used to connect <code>subtree</code>'s root as a child of <code>node</code>
94 */
95 public static <V,E> void addSubTree(Forest<V,E> tree, Forest<V,E> subTree,
96 V node, E connectingEdge) {
97 if (node != null && !tree.containsVertex(node))
98 throw new IllegalArgumentException("Specified tree does not contain the specified node as a vertex");
99 V root = subTree.getTrees().iterator().next().getRoot();
100 addFromSubTree(tree, subTree, connectingEdge, node, root);
101 }
102
103 /**
104 * Adds the trees in <code>source</code> to <code>destination</code>.
105 * <code>source</code> is left unchanged. The vertex and edge objects
106 * in <code>source</code> will also be used in <code>destination</code>,
107 * in the same (structural) roles.
108 * @param <V> the vertex type
109 * @param <E> the edge type
110 * @param destination the forest to which the trees in <code>source</code>
111 * will be added
112 * @param source the forest whose trees will be added to
113 * <code>destination</code>
114 * FIXME also note that this is redundant with DelegateForest.addTree()
115 *
116 */
117 // public static <V,E> void mergeForests(Forest<V,E> destination,
118 // Forest<V,E> source)
119 // {
120 // for (Tree<V,E> tree : source.getTrees())
121 // {
122 // V root = tree.getRoot();
123 // // FIXME this is not done: addChildrenToForest is not yet complete
124 // // also still need to integrate into MST2, etc. (see email thread)
125 //// addChildrenToForest(destination, tree, root);
126 // for (E e: tree.getOutEdges(root))
127 // {
128 // V child = tree.getOpposite(root, e);
129 // addFromSubTree(destination, source, e, root, child);
130 // }
131 // }
132 // }
133
134 public static <V,E> void addFromSubTree(Forest<V,E> tree, Forest<V,E> subTree,
135 E edge, V parent, V root) {
136
137 // add edge connecting parent and root to tree
138 if(edge != null && parent != null) {
139 tree.addEdge(edge, parent, root);
140 } else {
141 tree.addVertex(root);
142 }
143
144 Collection<E> outEdges = subTree.getOutEdges(root);
145 for(E e : outEdges) {
146 V opposite = subTree.getOpposite(root, e);
147 addFromSubTree(tree, subTree, e, root, opposite);
148 }
149 }
150
151 // FIXME: not done or integrated yet
152 // private static <V,E> void addChildrenToForest(Forest<V,E> forest, Tree<V,E> tree,
153 // V subtree_root)
154 // {
155 // V parent = tree.getPredecessors(subtree_root).iterator().next();
156 // for (E e : tree.getOutEdges(subtree_root))
157 // {
158 // V child = tree.getOpposite(subtree_root, e);
159 // addChildrenToForest(forest, tree, child);
160 // }
161 // }
162 }