Package es.uam.eps.ir.relison.graph.tree.fast

Class FastTree<U>

java.lang.Object
es.uam.eps.ir.relison.graph.fast.AbstractFastGraph<U>
es.uam.eps.ir.relison.graph.tree.fast.FastTree<U>
Type Parameters:
U - Type of the nodes of the tree
All Implemented Interfaces:
DirectedGraph<U>, FastGraph<U>, Graph<U>, Tree<U>, ReducedIndex<U>, java.io.Serializable
Direct Known Subclasses:
FastUnweightedTree, FastWeightedTree
public abstract class FastTree<U>
extends AbstractFastGraph<U>
implements Tree<U>
Fast implementation of the tree.
See Also:
Serialized Form

  • Constructor Details

    • FastTree

      public FastTree​(DirectedEdges edges)
      Constructor.
      Parameters:
      edges - The edges of the tree.

  • Method Details

    • getRoot

      public U getRoot()
      Description copied from interface: Tree
      Obtains the root of the graph.
      Specified by:
      getRoot in interface Tree<U>
      Returns:
      the root of the graph.

    • getLeaves

      public java.util.stream.Stream<U> getLeaves()
      Description copied from interface: Tree
      Obtain the leaves of the tree.
      Specified by:
      getLeaves in interface Tree<U>
      Returns:
      a stream containing the leaves of the tree.

    • getLeaves

      public java.util.stream.Stream<U> getLeaves​(U u)
      Description copied from interface: Tree
      Obtains the leaves of a tree that come from a certain node
      Specified by:
      getLeaves in interface Tree<U>
      Parameters:
      u - the leaves of the tree.
      Returns:
      a stream containing the selected leaves of the tree.

    • getLevel

      public java.util.stream.Stream<U> getLevel​(int level)
      Description copied from interface: Tree
      Obtains all the nodes in a given level of the tree. Root equal to 0.
      Specified by:
      getLevel in interface Tree<U>
      Parameters:
      level - the level to retrieve.
      Returns:
      the nodes in the corresponding level.

    • getLevels

      public java.util.Map<java.lang.Integer,​java.util.Set<U>> getLevels()
      Description copied from interface: Tree
      Obtains all the nodes on each level.
      Specified by:
      getLevels in interface Tree<U>
      Returns:
      all the nodes on each level.

    • getChildren

      public java.util.stream.Stream<U> getChildren​(U u)
      Description copied from interface: Tree
      Obtains the direct children of a node.
      Specified by:
      getChildren in interface Tree<U>
      Parameters:
      u - the parent node
      Returns:
      A stream containing the children of a node. If it is a leaf, an empty stream is returned. If the node does not exist, null.

    • getChildrenCount

      public long getChildrenCount​(U u)
      Description copied from interface: Tree
      Gets the number of children of a node.
      Specified by:
      getChildrenCount in interface Tree<U>
      Parameters:
      u - the node.
      Returns:
      the number of children, -1 if the node does not exist.

    • getParent

      public U getParent​(U u)
      Description copied from interface: Tree
      Obtains the parent of a node.
      Specified by:
      getParent in interface Tree<U>
      Parameters:
      u - the child.
      Returns:
      the parent of the node, null if the node does not exist, or the node is the root.

    • isLeaf

      public boolean isLeaf​(U u)
      Description copied from interface: Tree
      Indicates if the node is a leaf or not.
      Specified by:
      isLeaf in interface Tree<U>
      Parameters:
      u - the user
      Returns:
      true if the node is a leaf, false if the node is not a leaf or it does not exist.

    • isRoot

      public boolean isRoot​(U u)
      Description copied from interface: Tree
      Indicates if the node is the root node or not.
      Specified by:
      isRoot in interface Tree<U>
      Parameters:
      u - the user.
      Returns:
      true if the node is the root, false if the node is not the root or it does not exist.

    • addRoot

      public boolean addRoot​(U root)
      Description copied from interface: Tree
      Adds a root to the tree.
      Specified by:
      addRoot in interface Tree<U>
      Parameters:
      root - the new root of the tree.
      Returns:
      true if the root is correctly added, false if there is already a root in the graph.

    • addChild

      public boolean addChild​(U parent, U child, double weight, int type)
      Description copied from interface: Tree
      Adds a child to a given node.
      Specified by:
      addChild in interface Tree<U>
      Parameters:
      parent - the parent node.
      child - the child node to add.
      weight - the weight of the edge.
      type - the type of the edge.
      Returns:
      true if the child is correcly added, false if not.

    • isParent

      public boolean isParent​(U parent, U child)
      Description copied from interface: Tree
      Checks if a node is the parent of another one.
      Specified by:
      isParent in interface Tree<U>
      Parameters:
      parent - the parent node.
      child - the node we want to check.
      Returns:
      true if the child

    • isAscendant

      public boolean isAscendant​(U parent, U child)
      Description copied from interface: Tree
      Checks if a node is ascendant of another one
      Specified by:
      isAscendant in interface Tree<U>
      Parameters:
      parent - the first node (the possible ascendant)
      child - the second node (the possible descendant)
      Returns:
      true if the second node descends from the first, false if not.

    • addNode

      public boolean addNode​(U node)
      Description copied from interface: Graph
      Adds a new node to the graph.
      Specified by:
      addNode in interface Graph<U>
      Specified by:
      addNode in interface Tree<U>
      Overrides:
      addNode in class AbstractFastGraph<U>
      Parameters:
      node - The new node to add.
      Returns:
      true if the node is correctly added, false if not.

    • addEdge

      public boolean addEdge​(U nodeA, U nodeB, double weight, int type, boolean insertNodes)
      Description copied from interface: Graph
      Adds a weighted edge to the graph.
      Specified by:
      addEdge in interface Graph<U>
      Specified by:
      addEdge in interface Tree<U>
      Overrides:
      addEdge in class AbstractFastGraph<U>
      Parameters:
      nodeA - The incident node.
      nodeB - The adjacent node.
      weight - The weight.
      type - The edge type.
      insertNodes - If true, nodes will be inserted if they do not exist. If false, the edge will only be added if both nodes are inserted.
      Returns:
      if the edge is correctly added, false if not.

    • getChildrenWeights

      public java.util.stream.Stream<Weight<U,​java.lang.Double>> getChildrenWeights​(U u)
      Description copied from interface: Tree
      Obtains the weights of the children of a node.
      Specified by:
      getChildrenWeights in interface Tree<U>
      Parameters:
      u - The parent node.
      Returns:
      A stream containing the children of the node if it exists, null if not.

    • getParentWeight

      public double getParentWeight​(U u)
      Description copied from interface: Tree
      Obtains the weight of the edge between a node and its parent
      Specified by:
      getParentWeight in interface Tree<U>
      Parameters:
      u - The child node
      Returns:
      The weight if the node exists and it is not the root, NaN otherwise.

    • getAdjacencyMatrixMap

      public Index<U> getAdjacencyMatrixMap()
      Description copied from interface: Graph
      For an adjacency matrix, obtains the mapping between indexes and nodes.
      Specified by:
      getAdjacencyMatrixMap in interface Graph<U>
      Overrides:
      getAdjacencyMatrixMap in class AbstractFastGraph<U>
      Returns:
      the mapping between indexes and nodes.