Skip to content

Feat: Adding heuristics for faster DFD TFG finding and evaluation #198

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
Entenwilli merged 4 commits into from
Aug 19, 2024
Merged

Feat: Adding heuristics for faster DFD TFG finding and evaluation #198

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
f727817
Feat: Adding heuristics for faster DFD TFG finding and evaluation
01Parzival10 Aug 13, 2024
173d237
Fix: Case of previous vertices being overwritten for multiple flows i…
01Parzival10 Aug 16, 2024
548a090
Refactor: Remove debugging construct
01Parzival10 Aug 16, 2024
7cd0830
Refactor: Change for loop for better understandability
01Parzival10 Aug 18, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
6 changes: 3 additions & 3 deletions ...sis.dfd/src/org/dataflowanalysis/analysis/dfd/core/DFDCyclicTransposeFlowGraphFinder.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -113,7 +113,7 @@ private List<DFDVertex> determineSinks(DFDVertex sink, List<Pin> inputPins, List
List<DFDVertex> finalVertices = vertices;

vertices = incomingFlowsToPin.stream()
.flatMap(flow -> handleIncomingFlow(flow, inputPin, finalVertices, sourceNodes, previousNodesInTransposeFlow).stream())
.flatMap(flow -> handleIncomingFlowCyclic(flow, inputPin, finalVertices, sourceNodes, previousNodesInTransposeFlow).stream())
Comment thread
BenjaminArp marked this conversation as resolved.
.toList();
}
return vertices;
Expand Down Expand Up @@ -141,7 +141,7 @@ private List<DFDVertex> loopAwareDetermineSinks(DFDVertex sink, List<Pin> inputP
//Skipping flows that cause cycles
if(previousNodesInTransposeFlow.contains(flow.getSourceNode().getEntityName())) continue;

List<DFDVertex> result = handleIncomingFlow(flow, inputPin, finalVertices, sourceNodes, previousNodesInTransposeFlow);
List<DFDVertex> result = handleIncomingFlowCyclic(flow, inputPin, finalVertices, sourceNodes, previousNodesInTransposeFlow);

uniqueVertices.addAll(result);
}
Expand All @@ -160,7 +160,7 @@ private List<DFDVertex> loopAwareDetermineSinks(DFDVertex sink, List<Pin> inputP
* @param sourceNodes
* @param previousNodesInTransposeFlow List of all Nodes part of the current transpose Flow
*/
private List<DFDVertex> handleIncomingFlow(Flow incomingFlow, Pin inputPin, List<DFDVertex> finalVertices, List<Node> sourceNodes,
private List<DFDVertex> handleIncomingFlowCyclic(Flow incomingFlow, Pin inputPin, List<DFDVertex> finalVertices, List<Node> sourceNodes,
List<String> previousNodesInTransposeFlow) {

var copyPreviousNodesInTransposeFlow = new ArrayList<>(previousNodesInTransposeFlow);
Expand Down
91 changes: 84 additions & 7 deletions ....analysis.dfd/src/org/dataflowanalysis/analysis/dfd/core/DFDTransposeFlowGraphFinder.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -6,6 +6,7 @@
import org.dataflowanalysis.analysis.core.TransposeFlowGraphFinder;
import org.dataflowanalysis.analysis.dfd.resource.DFDResourceProvider;
import org.dataflowanalysis.dfd.datadictionary.AbstractAssignment;
import org.dataflowanalysis.dfd.datadictionary.Behaviour;
import org.dataflowanalysis.dfd.datadictionary.DataDictionary;
import org.dataflowanalysis.dfd.datadictionary.Pin;
import org.dataflowanalysis.dfd.dataflowdiagram.DataFlowDiagram;
Expand All @@ -18,6 +19,8 @@
public class DFDTransposeFlowGraphFinder implements TransposeFlowGraphFinder {
private final DataDictionary dataDictionary;
protected final DataFlowDiagram dataFlowDiagram;

private Map<Pin, DFDVertex> mapOutPinToExistingVertex = new HashMap<>();

public DFDTransposeFlowGraphFinder(DFDResourceProvider resourceProvider) {
this.dataDictionary = resourceProvider.getDataDictionary();
Expand Down Expand Up @@ -55,6 +58,7 @@ public List<? extends AbstractTransposeFlowGraph> findTransposeFlowGraphs(List<?
.toList();
List<DFDTransposeFlowGraph> transposeFlowGraphs = new ArrayList<>();


for (Node endNode : potentialSinks) {
List<DFDVertex> sinks = determineSinks(new DFDVertex(endNode, new HashMap<>(), new HashMap<>()), endNode.getBehaviour()
.getInPin(), sources);
Expand All @@ -67,7 +71,7 @@ public List<? extends AbstractTransposeFlowGraph> findTransposeFlowGraphs(List<?
.anyMatch(vertex -> sources.contains(vertex.getReferencedElement())))
.toList();
}
sinks.forEach(sink -> sink.unify(new HashSet<>()));
sinks.parallelStream().forEach(sink -> sink.unify(new HashSet<>()));
sinks.forEach(sink -> transposeFlowGraphs.add(new DFDTransposeFlowGraph(sink)));
}
return transposeFlowGraphs;
Expand All @@ -81,13 +85,47 @@ public List<? extends AbstractTransposeFlowGraph> findTransposeFlowGraphs(List<?
* @param inputPins Relevant input pins on the given vertex
* @return List of sinks created from the initial sink with previous vertices calculated
*/
private List<DFDVertex> determineSinks(DFDVertex sink, List<Pin> inputPins, List<Node> sourceNodes) {
private List<DFDVertex> determineSinks(DFDVertex sink, List<Pin> pins, List<Node> sourceNodes) {
List<DFDVertex> vertices = new ArrayList<>();
vertices.add(sink);

if (sourceNodes.contains(sink.getReferencedElement())) {
return vertices;
}

var inputPins = new ArrayList<>(pins);

Map<Pin, List<Pin>> inToPreviousNodeInPinsMap = new HashMap<>();
for (var pin : inputPins) {
Set<Pin> outputPins = new HashSet<>();
inToPreviousNodeInPinsMap.put(pin, new ArrayList<>());
dataFlowDiagram.getFlows()
.stream()
.filter(flow -> flow.getDestinationPin().equals(pin))
.forEach(flow -> outputPins.add(flow.getSourcePin()));

outputPins.stream().forEach(outPin -> {
Behaviour behaviour = (Behaviour) outPin.eContainer();
behaviour.getAssignment().stream().filter(it -> it.getOutputPin().equals(outPin)).forEach(it -> inToPreviousNodeInPinsMap.get(pin).addAll(it.getInputPins()));
});
}

Map<Pin, List<Pin>> mapInPinToEqualInPin = new HashMap<>();
var keyList = inToPreviousNodeInPinsMap.keySet().stream().toList();
for (int i = 0; i < keyList.size(); i++) {
var key = keyList.get(i);
var inPins = inToPreviousNodeInPinsMap.get(key);
for (int j = i + 1; j < keyList.size(); j++) {
var key2 = keyList.get(j);
var inPin2 = inToPreviousNodeInPinsMap.get(key2);
if (inPins.containsAll(inPin2) && inPin2.containsAll(inPins)) {
if (mapInPinToEqualInPin.getOrDefault(key, null) == null) mapInPinToEqualInPin.put(key, new ArrayList<>());
mapInPinToEqualInPin.get(key).add(key2);
};
}
}
Comment thread
BenjaminArp marked this conversation as resolved.

mapInPinToEqualInPin.keySet().stream().map(mapInPinToEqualInPin::get).forEach(inputPins::removeAll);

for (Pin inputPin : inputPins) {
List<Flow> incomingFlowsToPin = dataFlowDiagram.getFlows()
Expand All @@ -98,28 +136,59 @@ private List<DFDVertex> determineSinks(DFDVertex sink, List<Pin> inputPins, List

List<DFDVertex> finalVertices = vertices;
vertices = incomingFlowsToPin.stream()
.flatMap(flow -> handleIncomingFlow(flow, inputPin, finalVertices, sourceNodes).stream())
.flatMap(flow -> handleIncomingFlow(flow, inputPin, finalVertices, sourceNodes, mapInPinToEqualInPin.getOrDefault(inputPin, new ArrayList<>())).stream())
.toList();
}

return vertices;
}

public List<DFDVertex> handleIncomingFlow(Flow incomingFlow, Pin inputPin, List<DFDVertex> vertices, List<Node> sourceNodes) {
public List<DFDVertex> handleIncomingFlow(Flow incomingFlow, Pin inputPin, List<DFDVertex> vertices, List<Node> sourceNodes, List<Pin> equalPins) {
List<DFDVertex> result = new ArrayList<>();

var outPin = incomingFlow.getSourcePin();
if (mapOutPinToExistingVertex.get(outPin) != null) {
for (DFDVertex vertex : vertices) {
List<DFDVertex> previousNodeVertices = new ArrayList<>();
var newVertex = mapOutPinToExistingVertex.get(outPin).copy(new IdentityHashMap<>());
previousNodeVertices.add(newVertex);
result.addAll(cloneVertexForMultipleFlowGraphs(vertex, inputPin, incomingFlow, previousNodeVertices, equalPins));
}
return result;
}

Node previousNode = incomingFlow.getSourceNode();
List<Pin> previousNodeInputPins = getAllPreviousNodeInputPins(previousNode, incomingFlow);
List<DFDVertex> previousNodeVertices = determineSinks(new DFDVertex(previousNode, new HashMap<>(), new HashMap<>()), previousNodeInputPins,
sourceNodes);
if (!previousNodeVertices.isEmpty()) {
mapOutPinToExistingVertex.put(outPin, previousNodeVertices.get(0));
}

if (vertices.size() == 1 && previousNodeVertices.size() == 1 && vertices.get(0).getPinDFDVertexMap().isEmpty()) {
var vertex = vertices.get(0);
vertex.getPinDFDVertexMap()
.put(inputPin, previousNodeVertices.get(0));
equalPins.forEach(it -> vertex.getPinDFDVertexMap().put(it, previousNodeVertices.get(0)));
vertex.getPinFlowMap()
.put(inputPin, incomingFlow);
equalPins.forEach(it -> {
var newFlow = dataFlowDiagram.getFlows().stream().filter(inFlow -> (inFlow.getDestinationPin().equals(it) && inFlow.getSourceNode().equals(incomingFlow.getSourceNode()))).findAny().orElseThrow();
vertex.getPinFlowMap().put(it, newFlow);
});
result.add(vertex);
return result;

}
for (DFDVertex vertex : vertices) {
result.addAll(cloneVertexForMultipleFlowGraphs(vertex, inputPin, incomingFlow, previousNodeVertices));
result.addAll(cloneVertexForMultipleFlowGraphs(vertex, inputPin, incomingFlow, previousNodeVertices, equalPins));
}


return result;
}

/**
* Calculate all input pins required on the previous node that will be needed to satisfy the assignments to reach the
* present node
* @param previousNode Previous node
* @param flow Flow from previous into present node
Expand All @@ -146,18 +215,26 @@ protected List<Pin> getAllPreviousNodeInputPins(Node previousNode, Flow flow) {
* @param previousNodeVertices List of previous vertices
* @return Returns a list of cloned vertices required for usage in multiple flow graphs
*/
protected List<DFDVertex> cloneVertexForMultipleFlowGraphs(DFDVertex vertex, Pin inputPin, Flow flow, List<DFDVertex> previousNodeVertices) {
protected List<DFDVertex> cloneVertexForMultipleFlowGraphs(DFDVertex vertex, Pin inputPin, Flow flow, List<DFDVertex> previousNodeVertices, List<Pin> equalPins) {
List<DFDVertex> newVertices = new ArrayList<>();
for (var previousVertex : previousNodeVertices) {
DFDVertex newVertex = vertex.copy(new IdentityHashMap<>());
newVertex.getPinDFDVertexMap()
.put(inputPin, previousVertex);
equalPins.forEach(it -> newVertex.getPinDFDVertexMap().put(it, previousVertex));
newVertex.getPinFlowMap()
.put(inputPin, flow);
equalPins.forEach(it -> {
var newFlow = dataFlowDiagram.getFlows().stream().filter(inFlow -> (inFlow.getDestinationPin().equals(it) && inFlow.getSourceNode().equals(flow.getSourceNode()))).findAny().orElseThrow();
newVertex.getPinFlowMap().put(it, newFlow);
});
newVertices.add(newVertex);
newVertex.unify(new HashSet<>());
}
return newVertices;
}



/**
* Gets a list of nodes that are sinks of the given list of nodes
Expand Down
20 changes: 13 additions & 7 deletions ...g.dataflowanalysis.analysis.dfd/src/org/dataflowanalysis/analysis/dfd/core/DFDVertex.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2,6 +2,7 @@

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
Expand Down Expand Up @@ -251,7 +252,7 @@ private static boolean evaluateTerm(Term term, List<Label> inputLabel) {
* Goes through the previous vertices and replaces equal vertices by the same vertex
* @param vertices Set of unique vertices that are used to replace equal vertices
*/
public void unify(Set<DFDVertex> vertices) {
public void unify(Set<DFDVertex> vertices) {
for (var key : this.getPinDFDVertexMap()
.keySet()) {
for (var vertex : vertices) {
Expand All @@ -264,9 +265,8 @@ public void unify(Set<DFDVertex> vertices) {
vertices.add(this.getPinDFDVertexMap()
.get(key));
}
this.getPinDFDVertexMap()
.values()
.forEach(vertex -> vertex.unify(vertices));
this.getPreviousElements()
.forEach(vertex -> ((DFDVertex)vertex).unify(vertices));
}

/**
Expand All @@ -275,7 +275,12 @@ public void unify(Set<DFDVertex> vertices) {
public DFDVertex copy(Map<DFDVertex, DFDVertex> mapping) {
Map<Pin, DFDVertex> copiedPinDFDVertexMap = new HashMap<>();
this.pinDFDVertexMap.keySet()
.forEach(key -> copiedPinDFDVertexMap.put(key, mapping.getOrDefault(this.pinDFDVertexMap.get(key), this.pinDFDVertexMap.get(key).copy(mapping))));
.forEach(key -> {
var oldVertex = this.pinDFDVertexMap.get(key);
var newVertice = mapping.getOrDefault(oldVertex, this.pinDFDVertexMap.get(key).copy(mapping));
copiedPinDFDVertexMap.put(key, newVertice);
mapping.putIfAbsent(oldVertex, newVertice);
});
return new DFDVertex(this.referencedElement, copiedPinDFDVertexMap, new HashMap<>(this.pinFlowMap));
}

Expand All @@ -286,6 +291,7 @@ public String toString() {

@Override
public boolean equals(Object other) {
if (super.equals(other)) return true;
if (!(other instanceof DFDVertex vertex))
return false;
if (!this.referencedElement.equals(vertex.getReferencedElement()))
Expand All @@ -302,8 +308,8 @@ public boolean equals(Object other) {
}

@Override
public List<AbstractVertex<?>> getPreviousElements() {
return new ArrayList<>(this.pinDFDVertexMap.values());
public List<AbstractVertex<?>> getPreviousElements() {
return (new HashSet<AbstractVertex<?>>(this.pinDFDVertexMap.values())).stream().toList();
}

/**
Expand Down