Class DelegateTree<V,E>

java.lang.Object
edu.uci.ics.jung.graph.GraphDecorator<V,E>
edu.uci.ics.jung.graph.DelegateTree<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>, Tree<V,E>, Serializable

public class DelegateTree<V,E> extends GraphDecorator<V,E> implements Tree<V,E>
An implementation of Tree that delegates to a specified instance of DirectedGraph.
See Also:
  • Field Details

    • root

      protected V root
    • vertex_depths

      protected Map<V,Integer> vertex_depths
  • Constructor Details

    • DelegateTree

      public DelegateTree()
      Creates an instance.
    • DelegateTree

      public DelegateTree(com.google.common.base.Supplier<DirectedGraph<V,E>> graphFactory)
      create an instance with passed values.
      Parameters:
      graphFactory - must create a DirectedGraph to use as a delegate
    • DelegateTree

      public DelegateTree(DirectedGraph<V,E> graph)
      Creates a new DelegateTree which delegates to graph. Assumes that graph is already a tree; if it's not, future behavior of this instance is undefined.
      Parameters:
      graph - the graph to which this instance will delegate operations.
  • Method Details

    • getFactory

      public static final <V, E> com.google.common.base.Supplier<Tree<V,E>> getFactory()
      Type Parameters:
      V - the vertex type for the graph Supplier
      E - the edge type for the graph Supplier
      Returns:
      a Supplier that creates an instance of this graph type.
    • addEdge

      public boolean addEdge(E e, V v1, V v2, 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 Graph<V,E>
      Overrides:
      addEdge in class 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:
    • addEdge

      public boolean addEdge(E e, V v1, V v2)
      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.
      Specified by:
      addEdge in interface Graph<V,E>
      Overrides:
      addEdge in class GraphDecorator<V,E>
      Parameters:
      e - a unique edge to add
      v1 - the parent node
      v2 - the child node
      Returns:
      true if this call mutates the underlying graph
      See Also:
    • addVertex

      public boolean addVertex(V vertex)
      Will set the root of the Tree, only if the Tree is empty and the root is currently unset.
      Specified by:
      addVertex in interface Hypergraph<V,E>
      Overrides:
      addVertex in class GraphDecorator<V,E>
      Parameters:
      vertex - the tree root to set
      Returns:
      true if this call mutates the underlying graph
      Throws:
      UnsupportedOperationException - if the root was previously set
      See Also:
    • removeVertex

      public boolean removeVertex(V vertex)
      remove the passed node, and all nodes that are descendants of the passed node.
      Specified by:
      removeVertex in interface Hypergraph<V,E>
      Overrides:
      removeVertex in class GraphDecorator<V,E>
      Parameters:
      vertex - the vertex to remove
      Returns:
      true iff the tree was modified
      See Also:
    • addChild

      public boolean addChild(E edge, V parent, V child, EdgeType edgeType)
      add the passed child node as a child of parent. parent must exist in the tree, and child must not already exist.
      Parameters:
      edge - the unique edge to connect the parent and child nodes
      parent - the existing parent to attach the child to
      child - the new child to add to the tree as a child of parent
      edgeType - must be EdgeType.DIRECTED or the underlying graph may throw an exception
      Returns:
      whether this call mutates the underlying graph
    • addChild

      public boolean addChild(E edge, V parent, V child)
      add the passed child node as a child of parent. parent must exist in the tree, and child must not already exist
      Parameters:
      edge - the unique edge to connect the parent and child nodes
      parent - the existing parent to attach the child to
      child - the new child to add to the tree as a child of parent
      Returns:
      whether this call mutates the underlying graph
    • getChildCount

      public int getChildCount(V parent)
      get the number of children of the passed parent node
      Specified by:
      getChildCount in interface Forest<V,E>
      Parameters:
      parent - the vertex whose child edges are to be returned
      Returns:
      the Collection of edges connecting vertex to its children in this tree
      See Also:
    • getChildren

      public Collection<V> getChildren(V parent)
      get the immediate children nodes of the passed parent
      Specified by:
      getChildren in interface Forest<V,E>
      Parameters:
      parent - the vertex whose children are to be returned
      Returns:
      the Collection of children of vertex in this tree
      See Also:
    • getParent

      public V getParent(V child)
      get the single parent node of the passed child
      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:
    • getPath

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

      public V getRoot()
      getter for the root of the tree
      Specified by:
      getRoot in interface Tree<V,E>
      Returns:
      the root
    • setRoot

      public void setRoot(V root)
      sets the root to the passed value, only if the root is previously unset
      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
      Specified by:
      getDepth in interface Tree<V,E>
      Parameters:
      v - the node who's depth is computed
      Returns:
      the depth to the passed node.
      See Also:
    • getHeight

      public int getHeight()
      Computes and returns the height of the tree.
      Specified by:
      getHeight in interface Tree<V,E>
      Returns:
      the height
      See Also:
    • isInternal

      public boolean isInternal(V v)
      Parameters:
      v - the vertex to test
      Returns:
      true if v is neither a leaf nor the root of this tree
    • isLeaf

      public boolean isLeaf(V v)
      Parameters:
      v - the vertex to test
      Returns:
      true if v has no children
    • isRoot

      public boolean isRoot(V v)
      Parameters:
      v - the vertex to test
      Returns:
      true if v has no parent
    • 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:
    • addEdge

      public boolean addEdge(E edge, 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:
    • toString

      public String toString()
      Overrides:
      toString in class Object
    • getTrees

      public 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
    • getChildEdges

      public 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:
    • 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: