Package edu.isi.pegasus.planner.refiner
Class ReduceEdges
- java.lang.Object
-
- edu.isi.pegasus.planner.refiner.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.
-
-
-
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
-
-