/*
 * 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.