Class ReduceEdges


  • public class ReduceEdges
    extends java.lang.Object
    An algorithm to reduce remove edges in the workflow, based on a DFS of a graph and doing least common ancestor tranversals to detect duplicate edges.
    Author:
    Rajiv Mayani, Karan Vahi
    • Constructor Summary

      Constructors 
      Constructor Description
      ReduceEdges()  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void assignLevels​(Graph workflow, GraphNode root)
      Prunes redundant edges from the workflow.
      private java.util.Collection<GraphNode> findLCA​(GraphNode from, GraphNode to)
      We find LCA of from and to.
      ADag reduce​(ADag dag)
      Prunes redundant edges from the workflow.
      Graph reduce​(Graph workflow)
      Prunes redundant edges from the workflow.
      private void reset​(Graph workflow)
      Resets internal depth and color counters associated with the nodes in the workflow, before doing any graph traversals.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • ReduceEdges

        public ReduceEdges()
    • Method Detail

      • reduce

        public ADag reduce​(ADag dag)
        Prunes redundant edges from the workflow. For example if A->B->C and A->D exists, we can delete edge A->D
        Parameters:
        dag - the workflow
        Returns:
      • reduce

        public Graph reduce​(Graph workflow)
        Prunes redundant edges from the workflow.
        Parameters:
        workflow -
        Returns:
        the workflow with non essential edges removed
      • findLCA

        private java.util.Collection<GraphNode> findLCA​(GraphNode from,
                                                        GraphNode to)
        We find LCA of from and to.
        Parameters:
        from -
        to -
        Returns:
        the ancestors for which the edge from ancestor to the "to" node that have to be deleted.
      • assignLevels

        public void assignLevels​(Graph workflow,
                                 GraphNode root)
        Prunes redundant edges from the workflow.
        Parameters:
        workflow -
        root - the root from which to start to assign the levels
      • reset

        private void reset​(Graph workflow)
        Resets internal depth and color counters associated with the nodes in the workflow, before doing any graph traversals.
        Parameters:
        workflow - the workflow