Class OrderedKAryTree<V,​E>

  • 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>, edu.uci.ics.jung.graph.Tree<V,​E>, java.io.Serializable

    public class OrderedKAryTree<V,​E>
    extends AbstractTypedGraph<V,​E>
    implements edu.uci.ics.jung.graph.Tree<V,​E>
    An implementation of Tree in which each vertex has <= k children. The value of 'k' is specified by the constructor parameter. A specific child (edge) can be retrieved directly by specifying the index at which the child is located. By default, new (child) vertices are added at the lowest index available, if no index is specified.
    See Also:
    Serialized Form
    • Field Detail

      • edge_vpairs

        protected java.util.Map<E,​edu.uci.ics.jung.graph.util.Pair<V>> edge_vpairs
      • height

        protected int height
      • root

        protected V root
      • order

        protected int order
    • Constructor Detail

      • OrderedKAryTree

        public OrderedKAryTree​(int order)
        Creates a new instance with the specified order (maximum number of children).
    • Method Detail

      • getFactory

        public static <V,​E> org.apache.commons.collections4.Factory<edu.uci.ics.jung.graph.DirectedGraph<V,​E>> getFactory​(int order)
        Returns a Factory that creates an instance of this graph type.
        Type Parameters:
        V - the vertex type for the graph factory
        E - the edge type for the graph factory
      • getChildCount

        public int getChildCount​(V vertex)
        Returns the number of children that vertex has.
        Specified by:
        getChildCount in interface edu.uci.ics.jung.graph.Forest<V,​E>
        See Also:
        Forest.getChildCount(java.lang.Object)
      • getChildEdge

        public E getChildEdge​(V vertex,
                              int index)
        Returns the child edge of the vertex at index index.
        Parameters:
        vertex -
        index -
        Returns:
        the child edge of the vertex at index index
      • getChildEdges

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

        public java.util.Collection<V> getChildren​(V vertex)
        Returns an ordered list of vertex's child vertices. If there is no child in position i, then the list will contain null in position i. If vertex has no children then the empty set will be returned.
        Specified by:
        getChildren in interface edu.uci.ics.jung.graph.Forest<V,​E>
        See Also:
        Forest.getChildren(java.lang.Object)
      • getDepth

        public int getDepth​(V vertex)
        Specified by:
        getDepth in interface edu.uci.ics.jung.graph.Tree<V,​E>
        Returns:
        the depth of the vertex in this tree, or -1 if the vertex is not present in this tree
        See Also:
        Tree.getDepth(java.lang.Object)
      • getHeight

        public int getHeight()
        Returns the height of the tree, or -1 if the tree is empty.
        Specified by:
        getHeight in interface edu.uci.ics.jung.graph.Tree<V,​E>
        See Also:
        Tree.getHeight()
      • getParent

        public V getParent​(V vertex)
        Specified by:
        getParent in interface edu.uci.ics.jung.graph.Forest<V,​E>
        See Also:
        Forest.getParent(java.lang.Object)
      • getParentEdge

        public E getParentEdge​(V vertex)
        Specified by:
        getParentEdge in interface edu.uci.ics.jung.graph.Forest<V,​E>
        See Also:
        Forest.getParentEdge(java.lang.Object)
      • getRoot

        public V getRoot()
        Specified by:
        getRoot in interface edu.uci.ics.jung.graph.Tree<V,​E>
        See Also:
        Tree.getRoot()
      • 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>
        See Also:
        Forest.getTrees()
      • addEdge

        public boolean addEdge​(E e,
                               V parent,
                               V child,
                               int index)
        Adds the specified child vertex and edge e to the graph with the specified parent vertex parent. If index is greater than or equal to 0, then the child is placed at position index; if it is less than 0, the child is placed at the lowest available position; if it is greater than or equal to the order of this tree, an exception is thrown.
        See Also:
        Graph.addEdge(java.lang.Object, java.lang.Object, java.lang.Object)
      • addEdge

        public boolean addEdge​(E e,
                               V parent,
                               V child)
        Specified by:
        addEdge in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Overrides:
        addEdge in class AbstractGraph<V,​E>
        See Also:
        Graph.addEdge(java.lang.Object, java.lang.Object, java.lang.Object)
      • addEdge

        public boolean addEdge​(E e,
                               V v1,
                               V v2,
                               edu.uci.ics.jung.graph.util.EdgeType edge_type)
        Specified by:
        addEdge in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Overrides:
        addEdge in class AbstractGraph<V,​E>
        See Also:
        Graph.addEdge(java.lang.Object, java.lang.Object, java.lang.Object, edu.uci.ics.jung.graph.util.EdgeType)
      • getDest

        public V getDest​(E directed_edge)
        Specified by:
        getDest in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Specified by:
        getDest in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Graph.getDest(java.lang.Object)
      • getEndpoints

        public edu.uci.ics.jung.graph.util.Pair<V> getEndpoints​(E edge)
        Specified by:
        getEndpoints in interface edu.uci.ics.jung.graph.Graph<V,​E>
        See Also:
        Graph.getEndpoints(java.lang.Object)
      • getInEdges

        public java.util.Collection<E> getInEdges​(V vertex)
        Specified by:
        getInEdges in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Specified by:
        getInEdges in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Graph.getInEdges(java.lang.Object)
      • getOpposite

        public V getOpposite​(V vertex,
                             E edge)
        Specified by:
        getOpposite in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Overrides:
        getOpposite in class AbstractGraph<V,​E>
        See Also:
        Graph.getOpposite(java.lang.Object, java.lang.Object)
      • getOutEdges

        public java.util.Collection<E> getOutEdges​(V vertex)
        Specified by:
        getOutEdges in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Specified by:
        getOutEdges in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Graph.getOutEdges(java.lang.Object)
      • getPredecessorCount

        public int getPredecessorCount​(V vertex)
        Specified by:
        getPredecessorCount in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Overrides:
        getPredecessorCount in class AbstractGraph<V,​E>
        Returns:
        0 if vertex is the root, -1 if the vertex is not an element of this tree, and 1 otherwise
        See Also:
        Graph.getPredecessorCount(java.lang.Object)
      • getPredecessors

        public java.util.Collection<V> getPredecessors​(V vertex)
        Specified by:
        getPredecessors in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Specified by:
        getPredecessors in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Graph.getPredecessors(java.lang.Object)
      • getSource

        public V getSource​(E directed_edge)
        Specified by:
        getSource in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Specified by:
        getSource in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Graph.getSource(java.lang.Object)
      • getSuccessorCount

        public int getSuccessorCount​(V vertex)
        Specified by:
        getSuccessorCount in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Overrides:
        getSuccessorCount in class AbstractGraph<V,​E>
        See Also:
        Graph.getSuccessorCount(java.lang.Object)
      • getSuccessors

        public java.util.Collection<V> getSuccessors​(V vertex)
        Specified by:
        getSuccessors in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Specified by:
        getSuccessors in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Graph.getSuccessors(java.lang.Object)
      • inDegree

        public int inDegree​(V vertex)
        Specified by:
        inDegree in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Specified by:
        inDegree in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        inDegree in class AbstractGraph<V,​E>
        See Also:
        Graph.inDegree(java.lang.Object)
      • isDest

        public boolean isDest​(V vertex,
                              E edge)
        Specified by:
        isDest in interface edu.uci.ics.jung.graph.Graph<V,​E>
        See Also:
        Graph.isDest(java.lang.Object, java.lang.Object)
      • isLeaf

        public boolean isLeaf​(V vertex)
        Returns true if vertex is a leaf of this tree, i.e., if it has no children.
        Parameters:
        vertex - the vertex to be queried
        Returns:
        true if outDegree(vertex)==0
      • isPredecessor

        public boolean isPredecessor​(V v1,
                                     V v2)
        Returns true iff v1 is the parent of v2. Note that if v2 is the root and v1 is null, this method returns true.
        Specified by:
        isPredecessor in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Overrides:
        isPredecessor in class AbstractGraph<V,​E>
        See Also:
        Graph.isPredecessor(java.lang.Object, java.lang.Object)
      • isRoot

        public boolean isRoot​(V vertex)
        Returns true if vertex is a leaf of this tree, i.e., if it has no children.
        Parameters:
        vertex - the vertex to be queried
        Returns:
        true if outDegree(vertex)==0
      • isSource

        public boolean isSource​(V vertex,
                                E edge)
        Specified by:
        isSource in interface edu.uci.ics.jung.graph.Graph<V,​E>
        See Also:
        Graph.isSource(java.lang.Object, java.lang.Object)
      • isSuccessor

        public boolean isSuccessor​(V v1,
                                   V v2)
        Specified by:
        isSuccessor in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Overrides:
        isSuccessor in class AbstractGraph<V,​E>
        See Also:
        Graph.isSuccessor(java.lang.Object, java.lang.Object)
      • outDegree

        public int outDegree​(V vertex)
        Specified by:
        outDegree in interface edu.uci.ics.jung.graph.Graph<V,​E>
        Specified by:
        outDegree in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        outDegree in class AbstractGraph<V,​E>
        See Also:
        Graph.outDegree(java.lang.Object)
      • addEdge

        public boolean addEdge​(E edge,
                               java.util.Collection<? extends V> vertices,
                               edu.uci.ics.jung.graph.util.EdgeType edge_type)
        Specified by:
        addEdge in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        addEdge in class AbstractGraph<V,​E>
        See Also:
        Hypergraph.addEdge(java.lang.Object, java.util.Collection)
      • addVertex

        public boolean addVertex​(V vertex)
        Specified by:
        addVertex in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.addVertex(java.lang.Object)
      • isIncident

        public boolean isIncident​(V vertex,
                                  E edge)
        Specified by:
        isIncident in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        isIncident in class AbstractGraph<V,​E>
        See Also:
        Hypergraph.isIncident(java.lang.Object, java.lang.Object)
      • isNeighbor

        public boolean isNeighbor​(V v1,
                                  V v2)
        Specified by:
        isNeighbor in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        isNeighbor in class AbstractGraph<V,​E>
        See Also:
        Hypergraph.isNeighbor(java.lang.Object, java.lang.Object)
      • containsEdge

        public boolean containsEdge​(E edge)
        Specified by:
        containsEdge in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.containsEdge(java.lang.Object)
      • containsVertex

        public boolean containsVertex​(V vertex)
        Specified by:
        containsVertex in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.containsVertex(java.lang.Object)
      • findEdge

        public E findEdge​(V v1,
                          V v2)
        Specified by:
        findEdge in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        findEdge in class AbstractGraph<V,​E>
        See Also:
        Hypergraph.findEdge(java.lang.Object, java.lang.Object)
      • findEdgeSet

        public java.util.Collection<E> findEdgeSet​(V v1,
                                                   V v2)
        Specified by:
        findEdgeSet in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        findEdgeSet in class AbstractGraph<V,​E>
        See Also:
        Hypergraph.findEdgeSet(java.lang.Object, java.lang.Object)
      • getChild

        public V getChild​(V vertex,
                          int index)
        Returns the child of vertex at position index in this tree, or null if it has no child at that position.
        Parameters:
        vertex - the vertex to query
        Returns:
        the child of vertex at position index in this tree, or null if it has no child at that position
        Throws:
        java.lang.ArrayIndexOutOfBoundsException - if index is not in the range [0, order-1]
      • getEdgeCount

        public int getEdgeCount()
        Specified by:
        getEdgeCount in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.getEdgeCount()
      • getEdges

        public java.util.Collection<E> getEdges()
        Specified by:
        getEdges in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.getEdges()
      • getIncidentCount

        public int getIncidentCount​(E edge)
        Specified by:
        getIncidentCount in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        getIncidentCount in class AbstractGraph<V,​E>
        See Also:
        Hypergraph.getIncidentCount(java.lang.Object)
      • getIncidentEdges

        public java.util.Collection<E> getIncidentEdges​(V vertex)
        Specified by:
        getIncidentEdges in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.getIncidentEdges(java.lang.Object)
      • getIncidentVertices

        public java.util.Collection<V> getIncidentVertices​(E edge)
        Specified by:
        getIncidentVertices in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        getIncidentVertices in class AbstractGraph<V,​E>
        See Also:
        Hypergraph.getIncidentVertices(java.lang.Object)
      • getNeighborCount

        public int getNeighborCount​(V vertex)
        Specified by:
        getNeighborCount in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        Overrides:
        getNeighborCount in class AbstractGraph<V,​E>
        See Also:
        Hypergraph.getNeighborCount(java.lang.Object)
      • getNeighbors

        public java.util.Collection<V> getNeighbors​(V vertex)
        Specified by:
        getNeighbors in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.getNeighbors(java.lang.Object)
      • getVertexCount

        public int getVertexCount()
        Specified by:
        getVertexCount in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.getVertexCount()
      • getVertices

        public java.util.Collection<V> getVertices()
        Specified by:
        getVertices in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.getVertices()
      • removeEdge

        public boolean removeEdge​(E edge)
        Specified by:
        removeEdge in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.removeEdge(java.lang.Object)
      • removeVertex

        public boolean removeVertex​(V vertex)
        Specified by:
        removeVertex in interface edu.uci.ics.jung.graph.Hypergraph<V,​E>
        See Also:
        Hypergraph.removeVertex(java.lang.Object)
      • addEdge

        public boolean addEdge​(E edge,
                               edu.uci.ics.jung.graph.util.Pair<? extends V> endpoints,
                               edu.uci.ics.jung.graph.util.EdgeType edgeType)
        Description copied from class: AbstractGraph
        Adds edge to this graph with the specified endpoints and EdgeType.
        Specified by:
        addEdge in class AbstractGraph<V,​E>
        Returns:
        true iff the graph was modified as a result of this call