Package edu.uci.ics.jung.graph

Class DelegateForest<V,​E>

  • Type Parameters:
    V - the vertex type
    E - the edge type
    All Implemented Interfaces:
    edu.uci.ics.jung.graph.DirectedGraph<V,​E>, edu.uci.ics.jung.graph.Forest<V,​E>, edu.uci.ics.jung.graph.Graph<V,​E>, edu.uci.ics.jung.graph.Hypergraph<V,​E>, java.io.Serializable
    public class DelegateForest<V,​E>
extends edu.uci.ics.jung.graph.GraphDecorator<V,​E>
implements edu.uci.ics.jung.graph.Forest<V,​E>
    An implementation of Forest that delegates to a specified DirectedGraph instance.
    See Also:
    Serialized Form

    • Field Summary

      • Fields inherited from class edu.uci.ics.jung.graph.GraphDecorator

        delegate

    • Constructor Summary

      Constructors 
      Constructor Description
      DelegateForest()
      Creates an instance backed by a new DirectedSparseGraph instance.
      DelegateForest​(edu.uci.ics.jung.graph.DirectedGraph<V,​E> delegate)
      Creates an instance backed by the input DirectedGraph i

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean addEdge​(E edge, java.util.Collection<? extends V> vertices)  
      boolean addEdge​(E e, V v1, V v2, edu.uci.ics.jung.graph.util.EdgeType edgeType)
      Add an edge to the tree, connecting v1, the parent and v2, the child.
      void addTree​(edu.uci.ics.jung.graph.Tree<V,​E> tree)
      Adds tree to this graph as an element of this forest.
      boolean addVertex​(V vertex)
      Add vertex as a root of the tree
      int getChildCount​(V vertex)  
      java.util.Collection<E> getChildEdges​(V vertex)  
      java.util.Collection<V> getChildren​(V v)
      Returns the children of v.
      int getDepth​(V v)
      computes and returns the depth of the tree from the root to the passed vertex
      int getHeight()
      computes and returns the height of the tree
      int getIncidentCount​(E edge)  
      V getParent​(V child)  
      E getParentEdge​(V vertex)  
      java.util.List<V> getPath​(V child)
      returns an ordered list of the nodes beginning at the root and ending at the passed child node, including all intermediate nodes.
      V getRoot()
      getter for the root of the tree returns null, as this tree has >1 roots
      java.util.Collection<V> getRoots()
      Returns the root of each tree of this forest as a Collection.
      java.util.Collection<edu.uci.ics.jung.graph.Tree<V,​E>> getTrees()  
      boolean isInternal​(V v)
      computes and returns whether the passed node is neither the root, nor a leaf node.
      boolean isLeaf​(V v)
      Returns true if v has no child nodes.
      boolean isRoot​(V v)
      Returns true if v has no parent node.
      boolean removeChild​(V orphan)
      removes a node from the tree, causing all descendants of the removed node also to be removed
      boolean removeEdge​(E edge)
      Removes edge from this tree, and the subtree rooted at the child vertex incident to edge.
      boolean removeEdge​(E edge, boolean remove_subtree)
      Removes edge from this tree.
      boolean removeVertex​(V vertex)
      Removes vertex from this tree, and the subtree rooted at vertex.
      boolean removeVertex​(V vertex, boolean remove_subtrees)
      Removes vertex from this tree.
      void setRoot​(V root)
      adds root as a root of the tree

      • Methods inherited from class edu.uci.ics.jung.graph.GraphDecorator

        addEdge, addEdge, containsEdge, containsVertex, degree, findEdge, findEdgeSet, getDefaultEdgeType, getDest, getEdgeCount, getEdgeCount, getEdges, getEdges, getEdgeType, getEndpoints, getIncidentEdges, getIncidentVertices, getInEdges, getNeighborCount, getNeighbors, getOpposite, getOutEdges, getPredecessorCount, getPredecessors, getSource, getSuccessorCount, getSuccessors, getVertexCount, getVertices, inDegree, isDest, isIncident, isNeighbor, isPredecessor, isSource, isSuccessor, outDegree

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

      • Methods inherited from interface edu.uci.ics.jung.graph.Graph

        addEdge, getDest, getEndpoints, getInEdges, getOpposite, getOutEdges, getPredecessorCount, getPredecessors, getSource, getSuccessorCount, getSuccessors, inDegree, isDest, isPredecessor, isSource, isSuccessor, outDegree

      • Methods inherited from interface edu.uci.ics.jung.graph.Hypergraph

        addEdge, containsEdge, containsVertex, degree, findEdge, findEdgeSet, getDefaultEdgeType, getEdgeCount, getEdgeCount, getEdges, getEdges, getEdgeType, getIncidentEdges, getIncidentVertices, getNeighborCount, getNeighbors, getVertexCount, getVertices, isIncident, isNeighbor

    • Constructor Detail

      • DelegateForest

        public DelegateForest()
        Creates an instance backed by a new DirectedSparseGraph instance.

      • DelegateForest

        public DelegateForest​(edu.uci.ics.jung.graph.DirectedGraph<V,​E> delegate)
        Creates an instance backed by the input DirectedGraph i

    • Method Detail

      • addEdge

        public boolean addEdge​(E e,
                       V v1,
                       V v2,
                       edu.uci.ics.jung.graph.util.EdgeType edgeType)
        Add an edge to the tree, connecting v1, the parent and v2, the child. v1 must already exist in the tree, and v2 must not already exist the passed edge must be unique in the tree. Passing an edgeType other than EdgeType.DIRECTED may cause an illegal argument exception in the delegate graph.
        Specified by:
        addEdge in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Overrides:
        addEdge in class edu.uci.ics.jung.graph.GraphDecorator<V,​E>
        Parameters:
        e - a unique edge to add
        v1 - the parent node
        v2 - the child node
        edgeType - should be EdgeType.DIRECTED
        Returns:
        true if this call mutates the underlying graph
        See Also:
        Graph.addEdge(java.lang.Object, java.lang.Object, java.lang.Object, edu.uci.ics.jung.graph.util.EdgeType)

      • addVertex

        public boolean addVertex​(V vertex)
        Add vertex as a root of the tree
        Specified by:
        addVertex in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        addVertex in class edu.uci.ics.jung.graph.GraphDecorator<V,​E>
        Parameters:
        vertex - the tree root to add
        Returns:
        true if this call mutates the underlying graph
        See Also:
        Hypergraph.addVertex(java.lang.Object)

      • removeEdge

        public boolean removeEdge​(E edge)
        Removes edge from this tree, and the subtree rooted at the child vertex incident to edge. (The subtree is removed to ensure that the tree in which the edge was found is still a tree rather than a forest. To change this behavior so that the
        Specified by:
        removeEdge in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        removeEdge in class edu.uci.ics.jung.graph.GraphDecorator<V,​E>
        Parameters:
        edge - the edge to remove
        Returns:
        true iff the tree was modified
        See Also:
        Hypergraph.removeEdge(java.lang.Object)

      • removeEdge

        public boolean removeEdge​(E edge,
                          boolean remove_subtree)
        Removes edge from this tree. If remove_subtree is true, removes the subtree rooted at the child vertex incident to edge. Otherwise, leaves the subtree intact as a new component tree of this forest.
        Parameters:
        edge - the edge to remove
        remove_subtree - if true, remove the subtree
        Returns:
        true iff the tree was modified

      • removeVertex

        public boolean removeVertex​(V vertex)
        Removes vertex from this tree, and the subtree rooted at vertex.
        Specified by:
        removeVertex in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        removeVertex in class edu.uci.ics.jung.graph.GraphDecorator<V,​E>
        Parameters:
        vertex - the vertex to remove
        Returns:
        true iff the tree was modified
        See Also:
        Hypergraph.removeVertex(java.lang.Object)

      • removeVertex

        public boolean removeVertex​(V vertex,
                            boolean remove_subtrees)
        Removes vertex from this tree. If remove_subtrees is true, removes the subtrees rooted at the children of vertex. Otherwise, leaves these subtrees intact as new component trees of this forest.
        Parameters:
        vertex - the vertex to remove
        remove_subtrees - if true, remove the subtrees rooted at vertex's children
        Returns:
        true iff the tree was modified

      • getPath

        public java.util.List<V> getPath​(V child)
        returns an ordered list of the nodes beginning at the root and ending at the passed child node, including all intermediate nodes.
        Parameters:
        child - the last node in the path from the root
        Returns:
        an ordered list of the nodes from root to child

      • getParent

        public V getParent​(V child)
        Specified by:
        getParent in interface edu.uci.ics.jung.graph.Forest<V,​E>

      • getRoot

        public V getRoot()
        getter for the root of the tree returns null, as this tree has >1 roots
        Returns:
        the root

      • setRoot

        public void setRoot​(V root)
        adds root as a root of the tree
        Parameters:
        root - the initial tree root

      • removeChild

        public boolean removeChild​(V orphan)
        removes a node from the tree, causing all descendants of the removed node also to be removed
        Parameters:
        orphan - the node to remove
        Returns:
        whether this call mutates the underlying graph

      • getDepth

        public int getDepth​(V v)
        computes and returns the depth of the tree from the root to the passed vertex
        Parameters:
        v - the node who's depth is computed
        Returns:
        the depth to the passed node.

      • getHeight

        public int getHeight()
        computes and returns the height of the tree
        Returns:
        the height

      • isInternal

        public boolean isInternal​(V v)
        computes and returns whether the passed node is neither the root, nor a leaf node.
        Returns:
        true if v is neither a leaf nor a root

      • isLeaf

        public boolean isLeaf​(V v)
        Returns true if v has no child nodes.

      • getChildren

        public java.util.Collection<V> getChildren​(V v)
        Returns the children of v.
        Specified by:
        getChildren in interface edu.uci.ics.jung.graph.Forest<V,​E>

      • isRoot

        public boolean isRoot​(V v)
        Returns true if v has no parent node.

      • getIncidentCount

        public int getIncidentCount​(E edge)
        Specified by:
        getIncidentCount in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        getIncidentCount in class edu.uci.ics.jung.graph.GraphDecorator<V,​E>

      • addEdge

        public boolean addEdge​(E edge,
                       java.util.Collection<? extends V> vertices)
        Specified by:
        addEdge in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        addEdge in class edu.uci.ics.jung.graph.GraphDecorator<V,​E>

      • getRoots

        public java.util.Collection<V> getRoots()
        Returns the root of each tree of this forest as a Collection.

      • getTrees

        public java.util.Collection<edu.uci.ics.jung.graph.Tree<V,​E>> getTrees()
        Specified by:
        getTrees in interface edu.uci.ics.jung.graph.Forest<V,​E>

      • addTree

        public void addTree​(edu.uci.ics.jung.graph.Tree<V,​E> tree)
        Adds tree to this graph as an element of this forest.
        Parameters:
        tree - the tree to add to this forest as a component

      • getChildCount

        public int getChildCount​(V vertex)
        Specified by:
        getChildCount in interface edu.uci.ics.jung.graph.Forest<V,​E>

      • getChildEdges

        public java.util.Collection<E> getChildEdges​(V vertex)
        Specified by:
        getChildEdges in interface edu.uci.ics.jung.graph.Forest<V,​E>

      • getParentEdge

        public E getParentEdge​(V vertex)
        Specified by:
        getParentEdge in interface edu.uci.ics.jung.graph.Forest<V,​E>