Class SparseTree<V>

    • Constructor Detail

      • SparseTree

        public SparseTree​(V root)
        Construct a tree with a root.
        Parameters:
        root - the tree root
    • Method Detail

      • root

        public V root()
        Description copied from interface: RootedTree
        Gets the root of this tree. The root is defined to be the vertex with respect to which vertex depth is measured.
        Specified by:
        root in interface RootedTree<V,​Arc<V>>
        Returns:
        the root of this tree
      • depth

        public int depth​(V v)
        Description copied from interface: RootedTree
        Gets the (unweighted) distance of a vertex from the root of the vertex.
        Specified by:
        depth in interface RootedTree<V,​Arc<V>>
        Parameters:
        v - the vertex whose depth is to be computed
        Returns:
        the length of the shortest unweighted path from its root to the vertex
      • height

        public int height()
        Description copied from interface: RootedTree
        Gets the maximum depth in this tree.
        Specified by:
        height in interface RootedTree<V,​Arc<V>>
        Returns:
        the maximum depth in this tree
      • vertices

        public Set<V> vertices()
        Description copied from interface: Graph
        Gets the set of all vertices in this graph.
        Specified by:
        vertices in interface Graph<V,​Arc<V>>
        Returns:
        all vertices in this graph
      • edges

        public Set<Arc<V>> edges()
        Description copied from interface: Graph
        Gets the set of all edges in this graph.
        Specified by:
        edges in interface Graph<V,​Arc<V>>
        Returns:
        all edges in this graph
      • edges

        public Set<Arc<V>> edges​(V v)
        Description copied from interface: Graph
        Gets the set of all edges associated with a vertex in this graph.
        Specified by:
        edges in interface Graph<V,​Arc<V>>
        Parameters:
        v - a vertex
        Returns:
        all edges associated with a vertex
      • addVertex

        public SparseTree<V> addVertex​(V v)
        Description copied from interface: Graph
        Adds a vertex to this graph. Does nothing if v is already in the graph.
        Specified by:
        addVertex in interface Graph<V,​Arc<V>>
        Parameters:
        v - the vertex to add
        Returns:
        this graph (for builder pattern)
      • addEdge

        public SparseTree<V> addEdge​(Arc<V> e)
        Add an edge to the tree, connecting v1, the parent and v2..., the children. v1 must already exist in the tree, and the children must not already exist.
        Specified by:
        addEdge in interface Graph<V,​Arc<V>>
        Parameters:
        e - an edge
        Returns:
        this graph (for builder pattern)
      • removeVertex

        public SparseTree<V> removeVertex​(V v)
        Description copied from interface: Graph
        Removes a vertex from this graph. Does nothing if v is not in the graph. The edges associated with this vertex are also removed.
        Specified by:
        removeVertex in interface Graph<V,​Arc<V>>
        Parameters:
        v - the vertex to be removed
        Returns:
        this graph (for builder pattern)
      • removeEdge

        public SparseTree<V> removeEdge​(Arc<V> e)
        Description copied from interface: Graph
        Removes an edge from this graph. Does nothing if e is not in the graph. The vertices associated with the edge is not removed.
        Specified by:
        removeEdge in interface Graph<V,​Arc<V>>
        Parameters:
        e - the edge to be removed
        Returns:
        this graph (for builder pattern)
      • parent

        public V parent​(V v)
        Description copied from interface: Tree
        Gets the unique parent of a vertex.
        Specified by:
        parent in interface Tree<V,​Arc<V>>
        Parameters:
        v - a vertex
        Returns:
        the parent of v
      • subTree

        public RootedTree<V,​Arc<V>> subTree​(V v)
        Description copied from interface: RootedTree
        Gets a sub-tree starting from a vertex.
        Specified by:
        subTree in interface RootedTree<V,​Arc<V>>
        Parameters:
        v - the root of the sub-tree
        Returns:
        the sub-tree
      • rotate

        public RootedTree<V,​Arc<V>> rotate​(V v)
        This method re-pivots the tree with a new root vertex.
        Parameters:
        v - the new root
        Returns:
        a re-pivoted tree
      • topologicalOrder

        public int topologicalOrder​(V v)
        Description copied from interface: DAGraph
        Get the topological order of a vertex.
        Specified by:
        topologicalOrder in interface DAGraph<V,​Arc<V>>
        Parameters:
        v - a vertex
        Returns:
        the topological order of a vertex
      • outgoingArcs

        public Set<Arc<V>> outgoingArcs​(V v)
        Description copied from interface: DiGraph
        Gets the set of all outgoing arcs associated with a vertex in this graph.
        Specified by:
        outgoingArcs in interface DiGraph<V,​Arc<V>>
        Parameters:
        v - a vertex
        Returns:
        all outgoing arcs associated with a vertex
      • incomingArcs

        public Set<Arc<V>> incomingArcs​(V v)
        Description copied from interface: DiGraph
        Gets the set of all incoming arcs associated with a vertex in this graph.
        Specified by:
        incomingArcs in interface DiGraph<V,​Arc<V>>
        Parameters:
        v - a vertex
        Returns:
        all incoming arcs associated with a vertex
      • parents

        public Set<V> parents​(V v)
        Description copied from interface: DiGraph
        Gets the set of all parents of this vertex.
        Specified by:
        parents in interface DiGraph<V,​Arc<V>>
        Parameters:
        v - a vertex
        Returns:
        the set of all parents
      • children

        public Set<V> children​(V v)
        Description copied from interface: DiGraph
        Gets the set of all children of this vertex.
        Specified by:
        children in interface DiGraph<V,​Arc<V>>
        Parameters:
        v - a vertex
        Returns:
        the set of all children