Package edu.uci.ics.jung.graph

Class DelegateForest<V,​E>

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

    • Constructor Detail

      • DelegateForest

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

      • DelegateForest

        public DelegateForest​(DirectedGraph<V,​E> delegate)
        Creates an instance backed by the input DirectedGraph.
        Parameters:
        delegate - the graph to which operations will be delegated

    • Method Detail

      • 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 Hypergraph<V,​E>
        Overrides:
        removeEdge in class 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,
                            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)
        Description copied from interface: Forest
        Returns the parent of vertex in this tree. (If vertex is the root, returns null.) The parent of a vertex is defined as being its predecessor in the (unique) shortest path from the root to this vertex. This is a convenience method which is equivalent to Graph.getPredecessors(vertex).iterator().next().
        Specified by:
        getParent in interface Forest<V,​E>
        Parameters:
        child - the vertex whose parent is to be returned
        Returns:
        the parent of vertex in this tree
        See Also:
        Graph.getPredecessors(Object), Forest.getParentEdge(Object)

      • getRoot

        public V getRoot()
        Returns:
        the root of the tree, or null if the tree has > 1 roots

      • 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)
        Parameters:
        v - the vertex to test
        Returns:
        true if v is neither a leaf nor a root

      • isLeaf

        public boolean isLeaf​(V v)
        Parameters:
        v - the vertex to test
        Returns:
        true if v has no child nodes.

      • getChildren

        public java.util.Collection<V> getChildren​(V v)
        Description copied from interface: Forest
        Returns the children of vertex in this tree. The children of a vertex are defined as being the successors of that vertex on the respective (unique) shortest paths from the root to those vertices. This is syntactic (maple) sugar for getSuccessors(vertex).
        Specified by:
        getChildren in interface Forest<V,​E>
        Parameters:
        v - the vertex whose children are to be returned
        Returns:
        the children of v.
        See Also:
        Graph.getSuccessors(Object), Forest.getChildEdges(Object)

      • isRoot

        public boolean isRoot​(V v)
        Parameters:
        v - the vertex to test
        Returns:
        true if v has no parent node.

      • getIncidentCount

        public int getIncidentCount​(E edge)
        Description copied from interface: Hypergraph
        Returns the number of vertices that are incident to edge. For hyperedges, this can be any nonnegative integer; for edges this must be 2 (or 1 if self-loops are permitted).

        Equivalent to getIncidentVertices(edge).size().

        Specified by:
        getIncidentCount in interface Hypergraph<V,​E>
        Overrides:
        getIncidentCount in class GraphDecorator<V,​E>
        Parameters:
        edge - the edge whose incident vertex count is to be returned
        Returns:
        the number of vertices that are incident to edge.
        See Also:
        Hypergraph.getIncidentCount(java.lang.Object)

      • addEdge

        public boolean addEdge​(E edge,
                       java.util.Collection<? extends V> vertices)
        Description copied from interface: Hypergraph
        Adds edge to this graph. Fails under the following circumstances:
        • edge is already an element of the graph
        • either edge or vertices is null
        • vertices has the wrong number of vertices for the graph type
        • vertices are already connected by another edge in this graph, and this graph does not accept parallel edges
        Specified by:
        addEdge in interface Hypergraph<V,​E>
        Overrides:
        addEdge in class GraphDecorator<V,​E>
        Parameters:
        edge - the edge to add
        vertices - the vertices to which the edge will be connected
        Returns:
        true if the add is successful, and false otherwise
        See Also:
        Hypergraph.addEdge(java.lang.Object, java.util.Collection)

      • getRoots

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

      • getTrees

        public java.util.Collection<Tree<V,​E>> getTrees()
        Description copied from interface: Forest
        Returns a view of this graph as a collection of Tree instances.
        Specified by:
        getTrees in interface Forest<V,​E>
        Returns:
        a view of this graph as a collection of Trees

      • addTree

        public void addTree​(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)
        Description copied from interface: Forest
        Returns the number of children that vertex has in this tree. The children of a vertex are defined as being the successors of that vertex on the respective (unique) shortest paths from the root to those vertices. This is syntactic (maple) sugar for getSuccessorCount(vertex).
        Specified by:
        getChildCount in interface Forest<V,​E>
        Parameters:
        vertex - the vertex whose child edges are to be returned
        Returns:
        the Collection of edges connecting vertex to its children in this tree
        See Also:
        Forest.getChildEdges(Object), Forest.getChildren(Object), Graph.getSuccessorCount(Object)

      • getChildEdges

        public java.util.Collection<E> getChildEdges​(V vertex)
        Description copied from interface: Forest
        Returns the edges connecting vertex to its children in this tree. The children of a vertex are defined as being the successors of that vertex on the respective (unique) shortest paths from the root to those vertices. This is syntactic (maple) sugar for getOutEdges(vertex).
        Specified by:
        getChildEdges in interface Forest<V,​E>
        Parameters:
        vertex - the vertex whose child edges are to be returned
        Returns:
        the Collection of edges connecting vertex to its children in this tree
        See Also:
        Graph.getOutEdges(Object), Forest.getChildren(Object)

      • getParentEdge

        public E getParentEdge​(V vertex)
        Description copied from interface: Forest
        Returns the edge connecting vertex to its parent in this tree. (If vertex is the root, returns null.) The parent of a vertex is defined as being its predecessor in the (unique) shortest path from the root to this vertex. This is a convenience method which is equivalent to Graph.getInEdges(vertex).iterator().next(), and also to Graph.findEdge(vertex, getParent(vertex)).
        Specified by:
        getParentEdge in interface Forest<V,​E>
        Parameters:
        vertex - the vertex whose incoming edge is to be returned
        Returns:
        the edge connecting vertex to its parent, or null if vertex is the root
        See Also:
        Graph.getInEdges(Object), Forest.getParent(Object)