/*
* Created on Mar 3, 2007
*
* Copyright (c) 2007, The JUNG Authors
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.graph.util;
import edu.uci.ics.jung.graph.Forest;
import edu.uci.ics.jung.graph.Tree;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
/**
* Contains static methods for operating on instances of Tree.
*/
public class TreeUtils
{
/**
* @param the vertex type
* @param the edge type
* @param forest the forest whose roots are to be returned
* @return the roots of this forest.
*/
public static List getRoots(Forest forest)
{
List roots = new ArrayList();
for(Tree tree : forest.getTrees()) {
roots.add(tree.getRoot());
}
return roots;
}
/**
* Returns the subtree of tree which is rooted at root as a Forest.
* The tree returned is an independent entity, although it uses the same vertex and edge objects.
* @param the vertex type
* @param the edge type
* @param forest the tree whose subtree is to be extracted
* @param root the root of the subtree to be extracted
* @return the subtree of tree which is rooted at root
* @throws InstantiationException if a new tree of the same type cannot be created
* @throws IllegalAccessException if a new tree of the same type cannot be created
*/
@SuppressWarnings("unchecked")
public static Tree getSubTree(Forest forest, V root) throws InstantiationException, IllegalAccessException
{
if (!forest.containsVertex(root))
throw new IllegalArgumentException("Specified tree does not contain the specified root as a vertex");
Forest subforest = forest.getClass().newInstance();
subforest.addVertex(root);
growSubTree(forest, subforest, root);
return subforest.getTrees().iterator().next();
}
/**
* Populates subtree with the subtree of tree
* which is rooted at root.
* @param the vertex type
* @param the edge type
* @param tree the tree whose subtree is to be extracted
* @param subTree the tree instance which is to be populated with the subtree of tree
* @param root the root of the subtree to be extracted
*/
public static void growSubTree(Forest tree, Forest subTree, V root) {
if(tree.getSuccessorCount(root) > 0) {
Collection edges = tree.getOutEdges(root);
for(E e : edges) {
subTree.addEdge(e, tree.getEndpoints(e));
}
Collection kids = tree.getSuccessors(root);
for(V kid : kids) {
growSubTree(tree, subTree, kid);
}
}
}
/**
* Connects subTree to tree by attaching it as a child
* of node with edge connectingEdge.
* @param the vertex type
* @param the edge type
* @param tree the tree to which subTree is to be added
* @param subTree the tree which is to be grafted on to tree
* @param node the parent of subTree in its new position in tree
* @param connectingEdge the edge used to connect subtree's root as a child of node
*/
public static void addSubTree(Forest tree, Forest subTree,
V node, E connectingEdge) {
if (node != null && !tree.containsVertex(node))
throw new IllegalArgumentException("Specified tree does not contain the specified node as a vertex");
V root = subTree.getTrees().iterator().next().getRoot();
addFromSubTree(tree, subTree, connectingEdge, node, root);
}
public static void addFromSubTree(Forest tree, Forest subTree,
E edge, V parent, V root) {
// add edge connecting parent and root to tree
if(edge != null && parent != null) {
tree.addEdge(edge, parent, root);
} else {
tree.addVertex(root);
}
Collection outEdges = subTree.getOutEdges(root);
for(E e : outEdges) {
V opposite = subTree.getOpposite(root, e);
addFromSubTree(tree, subTree, e, root, opposite);
}
}
}
Ads help maintain this website.