Package org.apache.nemo.common.dag

Class DAG<V extends Vertex,​E extends Edge<V>>

  • Type Parameters:
    V - the vertex type
    E - the edge type
    All Implemented Interfaces:
    java.io.Serializable, DAGInterface<V,​E>
    public final class DAG<V extends Vertex,​E extends Edge<V>>
extends java.lang.Object
implements DAGInterface<V,​E>
    DAG implementation.
    See Also:
    Serialized Form

    • Field Summary

      Fields 
      Modifier and Type Field Description
      static java.lang.String EMPTY_DAG_DIRECTORY  

    • Constructor Summary

      Constructors 
      Constructor Description
      DAG​(java.util.Set<V> vertices, java.util.Map<V,​java.util.Set<E>> incomingEdges, java.util.Map<V,​java.util.Set<E>> outgoingEdges, java.util.Map<V,​LoopVertex> assignedLoopVertexMap, java.util.Map<V,​java.lang.Integer> loopStackDepthMap)
      Constructor of DAG, called by the DAGBuilder.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      com.fasterxml.jackson.databind.node.ObjectNode asJsonNode()  
      void dfsDo​(V vertex, java.util.function.Consumer<V> vertexConsumer, DAGInterface.TraversalOrder traversalOrder, java.util.Set<V> visited)
      A recursive helper function for DAGInterface.dfsTraverse(Consumer, TraversalOrder).
      void dfsTraverse​(java.util.function.Consumer<V> function, DAGInterface.TraversalOrder traversalOrder)
      Traverses the DAG by DFS, applying the given function.
      java.util.List<V> filterVertices​(java.util.function.Predicate<V> condition)
      Filters the vertices according to the given condition.
      java.util.List<V> getAncestors​(java.lang.String vertexId)
      Retrieves the ancestors of a vertex.
      LoopVertex getAssignedLoopVertexOf​(V v)
      Retrieves the wrapping LoopVertex of the vertex.
      java.util.List<V> getChildren​(java.lang.String vertexId)
      Retrieves the children vertices of the given vertex.
      java.util.List<V> getDescendants​(java.lang.String vertexId)
      Retrieves the descendants of a vertex.
      E getEdgeBetween​(java.lang.String srcVertexId, java.lang.String dstVertexId)
      Retrieves the edge between two vertices.
      E getEdgeById​(java.lang.String id)
      Retrieves the edge given its ID.
      java.util.List<E> getEdges()
      Retrieves the edges of this DAG.
      java.util.List<E> getIncomingEdgesOf​(java.lang.String vertexId)
      Retrieves the incoming edges of the given vertex.
      java.util.List<E> getIncomingEdgesOf​(V v)
      Retrieves the incoming edges of the given vertex.
      java.lang.Integer getLoopStackDepthOf​(V v)
      Retrieves the stack depth of the given vertex.
      java.util.List<E> getOutgoingEdgesOf​(java.lang.String vertexId)
      Retrieves the outgoing edges of the given vertex.
      java.util.List<E> getOutgoingEdgesOf​(V v)
      Retrieves the outgoing edges of the given vertex.
      java.util.List<V> getParents​(java.lang.String vertexId)
      Retrieves the parent vertices of the given vertex.
      java.util.List<V> getRootVertices()
      Retrieves the root vertices of this DAG.
      java.util.List<V> getTopologicalSort()
      Gets the DAG's vertices in topologically sorted order.
      V getVertexById​(java.lang.String id)
      Retrieves the vertex given its ID.
      java.util.List<V> getVertices()
      Retrieves the vertices of this DAG.
      java.lang.Boolean isCompositeVertex​(V v)
      Checks whether the given vertex is assigned with a wrapping LoopVertex.
      java.lang.Boolean pathExistsBetween​(V v1, V v2)
      Function checks whether there is a path between two vertices.
      void storeJSON​(java.lang.String directory, java.lang.String name, java.lang.String description)
      Stores JSON representation of this DAG into a file.
      void topologicalDo​(java.util.function.Consumer<V> function)
      Applies the function to each node in the DAG in a topological order.
      java.lang.String toString()  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

    • Field Detail

      • EMPTY_DAG_DIRECTORY

        public static final java.lang.String EMPTY_DAG_DIRECTORY
        See Also:
        Constant Field Values

    • Constructor Detail

      • DAG

        public DAG​(java.util.Set<V> vertices,
           java.util.Map<V,​java.util.Set<E>> incomingEdges,
           java.util.Map<V,​java.util.Set<E>> outgoingEdges,
           java.util.Map<V,​LoopVertex> assignedLoopVertexMap,
           java.util.Map<V,​java.lang.Integer> loopStackDepthMap)
        Constructor of DAG, called by the DAGBuilder.
        Parameters:
        vertices - set of vertices.
        incomingEdges - map of incoming edges for each vertex.
        outgoingEdges - map of outgoing edges for each vertex.
        assignedLoopVertexMap - map of assignedLoopVertex info.
        loopStackDepthMap - map of stack depth of LoopVertices.

    • Method Detail

      • getVertexById

        public V getVertexById​(java.lang.String id)
        Description copied from interface: DAGInterface
        Retrieves the vertex given its ID.
        Specified by:
        getVertexById in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        id - of the vertex to retrieve.
        Returns:
        the vertex.

      • getEdgeById

        public E getEdgeById​(java.lang.String id)
        Description copied from interface: DAGInterface
        Retrieves the edge given its ID.
        Specified by:
        getEdgeById in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        id - of the edge to retrieve.
        Returns:
        the edge.

      • getVertices

        public java.util.List<V> getVertices()
        Description copied from interface: DAGInterface
        Retrieves the vertices of this DAG.
        Specified by:
        getVertices in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Returns:
        the list of vertices. Note that the result is never null, ensured by DAGBuilder.

      • getEdges

        public java.util.List<E> getEdges()
        Description copied from interface: DAGInterface
        Retrieves the edges of this DAG.
        Specified by:
        getEdges in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Returns:
        the list of edges.

      • getRootVertices

        public java.util.List<V> getRootVertices()
        Description copied from interface: DAGInterface
        Retrieves the root vertices of this DAG.
        Specified by:
        getRootVertices in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Returns:
        the list of root vertices.

      • getIncomingEdgesOf

        public java.util.List<E> getIncomingEdgesOf​(V v)
        Description copied from interface: DAGInterface
        Retrieves the incoming edges of the given vertex.
        Specified by:
        getIncomingEdgesOf in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        v - the subject vertex.
        Returns:
        the list of incoming edges to the vertex. Note that the result is never null, ensured by DAGBuilder.

      • getIncomingEdgesOf

        public java.util.List<E> getIncomingEdgesOf​(java.lang.String vertexId)
        Description copied from interface: DAGInterface
        Retrieves the incoming edges of the given vertex.
        Specified by:
        getIncomingEdgesOf in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        vertexId - the ID of the subject vertex.
        Returns:
        the list of incoming edges to the vertex. Note that the result is never null, ensured by DAGBuilder.

      • getOutgoingEdgesOf

        public java.util.List<E> getOutgoingEdgesOf​(V v)
        Description copied from interface: DAGInterface
        Retrieves the outgoing edges of the given vertex.
        Specified by:
        getOutgoingEdgesOf in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        v - the subject vertex.
        Returns:
        the list of outgoing edges to the vertex. Note that the result is never null, ensured by DAGBuilder.

      • getOutgoingEdgesOf

        public java.util.List<E> getOutgoingEdgesOf​(java.lang.String vertexId)
        Description copied from interface: DAGInterface
        Retrieves the outgoing edges of the given vertex.
        Specified by:
        getOutgoingEdgesOf in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        vertexId - the ID of the subject vertex.
        Returns:
        the list of outgoing edges to the vertex. Note that the result is never null, ensured by DAGBuilder.

      • getParents

        public java.util.List<V> getParents​(java.lang.String vertexId)
        Description copied from interface: DAGInterface
        Retrieves the parent vertices of the given vertex.
        Specified by:
        getParents in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        vertexId - the ID of the subject vertex.
        Returns:
        the list of parent vertices.

      • getChildren

        public java.util.List<V> getChildren​(java.lang.String vertexId)
        Description copied from interface: DAGInterface
        Retrieves the children vertices of the given vertex.
        Specified by:
        getChildren in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        vertexId - the ID of the subject vertex.
        Returns:
        the list of children vertices.

      • getEdgeBetween

        public E getEdgeBetween​(java.lang.String srcVertexId,
                        java.lang.String dstVertexId)
        Description copied from interface: DAGInterface
        Retrieves the edge between two vertices.
        Specified by:
        getEdgeBetween in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        srcVertexId - the ID of the source vertex.
        dstVertexId - the ID of the destination vertex.
        Returns:
        the edge if exists.

      • getTopologicalSort

        public java.util.List<V> getTopologicalSort()
        Description copied from interface: DAGInterface
        Gets the DAG's vertices in topologically sorted order. This function brings consistent results.
        Specified by:
        getTopologicalSort in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Returns:
        the sorted list of vertices in topological order.

      • getAncestors

        public java.util.List<V> getAncestors​(java.lang.String vertexId)
        Description copied from interface: DAGInterface
        Retrieves the ancestors of a vertex.
        Specified by:
        getAncestors in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        vertexId - to find the ancestors for.
        Returns:
        the list of ancestors.

      • getDescendants

        public java.util.List<V> getDescendants​(java.lang.String vertexId)
        Description copied from interface: DAGInterface
        Retrieves the descendants of a vertex.
        Specified by:
        getDescendants in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        vertexId - to find the descendants for.
        Returns:
        the list of descendants.

      • filterVertices

        public java.util.List<V> filterVertices​(java.util.function.Predicate<V> condition)
        Description copied from interface: DAGInterface
        Filters the vertices according to the given condition.
        Specified by:
        filterVertices in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        condition - that must be satisfied to be included in the filtered list.
        Returns:
        the list of vertices that meet the condition.

      • topologicalDo

        public void topologicalDo​(java.util.function.Consumer<V> function)
        Description copied from interface: DAGInterface
        Applies the function to each node in the DAG in a topological order. This function brings consistent results.
        Specified by:
        topologicalDo in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        function - to apply.

      • dfsTraverse

        public void dfsTraverse​(java.util.function.Consumer<V> function,
                        DAGInterface.TraversalOrder traversalOrder)
        Description copied from interface: DAGInterface
        Traverses the DAG by DFS, applying the given function.
        Specified by:
        dfsTraverse in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        function - to apply.
        traversalOrder - which the DFS should be conducted.

      • pathExistsBetween

        public java.lang.Boolean pathExistsBetween​(V v1,
                                           V v2)
        Description copied from interface: DAGInterface
        Function checks whether there is a path between two vertices.
        Specified by:
        pathExistsBetween in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        v1 - First vertex to check.
        v2 - Second vertex to check.
        Returns:
        Whether or not there is a path between two vertices.

      • isCompositeVertex

        public java.lang.Boolean isCompositeVertex​(V v)
        Description copied from interface: DAGInterface
        Checks whether the given vertex is assigned with a wrapping LoopVertex.
        Specified by:
        isCompositeVertex in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        v - Vertex to check.
        Returns:
        whether or not it is wrapped by a LoopVertex

      • getLoopStackDepthOf

        public java.lang.Integer getLoopStackDepthOf​(V v)
        Description copied from interface: DAGInterface
        Retrieves the stack depth of the given vertex.
        Specified by:
        getLoopStackDepthOf in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        v - Vertex to check.
        Returns:
        The depth of the stack of LoopVertices for the vertex.

      • asJsonNode

        public com.fasterxml.jackson.databind.node.ObjectNode asJsonNode()
        Specified by:
        asJsonNode in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Returns:
        JsonNode for this DAG.

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object

      • storeJSON

        public void storeJSON​(java.lang.String directory,
                      java.lang.String name,
                      java.lang.String description)
        Description copied from interface: DAGInterface
        Stores JSON representation of this DAG into a file.
        Specified by:
        storeJSON in interface DAGInterface<V extends Vertex,​E extends Edge<V>>
        Parameters:
        directory - the directory which JSON representation is saved to
        name - name of this DAG
        description - description of this DAG