2 files changed, 127 insertions, 1 deletions

diff --git a/core/src/Model/Workflow/Workflow.cpp b/core/src/Model/Workflow/Workflow.cpp
index a32149e..7afcf0b 100644
--- a/core/src/Model/Workflow/Workflow.cpp
+++ b/core/src/Model/Workflow/Workflow.cpp
@@ -1,5 +1,6 @@
 #include "Workflow.hpp"
 
+#include <tsl/robin_set.h>
 #include <algorithm>
 #include <cassert>
 #include <queue>
@@ -73,7 +74,8 @@ WorkflowConnection::Direction WorkflowNode::OutputPin::GetSupportedDirection() c
 
 WorkflowNode::WorkflowNode(Type type, Kind kind)
 	: mType{ type }
-	, mKind{ kind } {
+	, mKind{ kind }
+	, mDepth{ -1 } {
 }
 
 size_t WorkflowNode::GetId() const {
@@ -297,6 +299,8 @@ bool Workflow::Connect(WorkflowNode& sourceNode, int sourcePin, WorkflowNode& de
 
 	src.Connection = connId;
 	dst.Connection = connId;
+
+	mDepthsDirty = true;
 	return true;
 }
 
@@ -330,6 +334,7 @@ bool Workflow::DisconnectBySource(WorkflowNode& sourceNode, int sourcePin) {
 		} break;
 	}
 
+	mDepthsDirty = true;
 	return true;
 }
 
@@ -368,9 +373,118 @@ bool Workflow::DisconnectByDestination(WorkflowNode& destinationNode, int destin
 		} break;
 	}
 
+	mDepthsDirty = true;
 	return true;
 }
 
+void Workflow::RemoveConnection(size_t id) {
+	auto& conn = mConnections[id];
+	if (!conn.IsValid()) return;
+
+	switch (conn.ConnectionDirection) {
+		case WorkflowConnection::ManyToOne: {
+
+		} break;
+		case WorkflowConnection::OneToMany: {
+
+		} break;
+	}
+
+	// TODO
+
+	mDepthsDirty = true;
+}
+
+bool Workflow::DoesDepthNeedsUpdate() const {
+	return mDepthsDirty;
+}
+
+Workflow::GraphUpdateResult Workflow::UpdateGraph() {
+	// Terminology:
+	// - Input pin <=> dependency nodes
+
+	struct WorkingNode {
+		// The max depth out of all dependency nodes, maintained during the traversal and committed as the actual depth
+		// when all dependencies of this node has been resolved
+		int MaximumDepth = 0;
+		int FulfilledInputCount = 0;
+	};
+	std::vector<WorkingNode> workingNodes;
+	tsl::robin_set<size_t> workingSet; // The set of valid (known to has depth) nodes, used for iterating
+	tsl::robin_set<size_t> backWorkingSet; // The set of valid nodes built while iterating `workingSet`, and will be moved into it after done iterating
+
+	workingNodes.reserve(mNodes.size());
+	for (size_t i = 0; i < mNodes.size(); ++i) {
+		auto& node = mNodes[i];
+		workingNodes.push_back(WorkingNode{});
+
+		if (!node) continue;
+		node->mDepth = -1;
+
+		// Start traversing with the input nodes
+		if (node->GetType() == WorkflowNode::InputType) {
+			workingSet.insert(i);
+		}
+	}
+
+	auto HasCyclicReference = [&](WorkflowNode* node) -> bool {
+		// TODO
+		return false;
+	};
+
+	auto AddOutputsToWorkingSet = [&](WorkflowNode* node) -> void {
+		for (auto& pin : node->mOutputs) {
+			if (!pin.IsConnected()) continue;
+			auto& conn = mConnections[pin.Connection];
+
+			for (auto& point : conn.GetDestinationPoints()) {
+				auto& wn = workingNodes[point.Node];
+				auto& n = *mNodes[point.Node].get();
+
+				wn.FulfilledInputCount++;
+
+				if (HasCyclicReference(n)) {
+					// TODO
+					break;
+				}
+
+				// Fulfilled node
+				// We use >= here because for a many-to-one pin, the dependency is an "or" relation ship, i.e. any of the nodes firing before this will fulfill the requirement
+				// TODO calc depth based on previous dependencies
+				if (n.mInputs.size() >= wn.FulfilledInputCount) {
+					backWorkingSet.insert(point.Node);
+				}
+			}
+		}
+	};
+
+	int processedNodes = 0;
+	int currentDepth = 0;
+	while (true) {
+		for (size_t idx : workingSet) {
+			auto& wn = workingNodes[idx];
+			auto& n = *mNodes[idx];
+			if (n.mInputs.size() == wn.FulfilledInputCount) {
+				n.mDepth = currentDepth;
+
+				AddOutputsToWorkingSet(n);
+				processedNodes++;
+			}
+		}
+
+		workingSet = std::move(backWorkingSet);
+		backWorkingSet.clear();
+
+		currentDepth++;
+
+		if (processedNodes == mNodes.size()) {
+			break;
+		}
+	}
+
+	return GraphUpdateResult::Success;
+}
+
 std::pair<WorkflowConnection&, size_t> Workflow::AllocWorkflowConnection() {
 	for (size_t idx = 0; idx < mConnections.size(); ++idx) {
 		auto& elm = mConnections[idx];
diff --git a/core/src/Model/Workflow/Workflow.hpp b/core/src/Model/Workflow/Workflow.hpp
index a7b2c31..bfed722 100644
--- a/core/src/Model/Workflow/Workflow.hpp
+++ b/core/src/Model/Workflow/Workflow.hpp
@@ -99,6 +99,7 @@ protected:
 	std::vector<OutputPin> mOutputs;
 	Type mType;
 	Kind mKind;
+	int mDepth;
 
 public:
 	WorkflowNode(Type type, Kind kind);
@@ -144,6 +145,7 @@ private:
 	std::vector<WorkflowConnection> mConnections;
 	std::vector<std::unique_ptr<WorkflowNode>> mNodes;
 	std::vector<std::unique_ptr<BaseValue>> mConstants;
+	bool mDepthsDirty = true;
 
 public:
 	WorkflowConnection* GetConnectionById(size_t id);
@@ -157,6 +159,16 @@ public:
 	bool DisconnectBySource(WorkflowNode& sourceNode, int sourcePin);
 	bool DisconnectByDestination(WorkflowNode& destinationNode, int destinationPin);
 
+	void RemoveConnection(size_t id);
+
+	bool DoesDepthNeedsUpdate() const;
+
+	enum GraphUpdateResult {
+		Success,
+		CyclicReference,
+	};
+	GraphUpdateResult UpdateGraph();
+
 private:
 	std::pair<WorkflowConnection&, size_t> AllocWorkflowConnection();
 	std::pair<std::unique_ptr<WorkflowNode>&, size_t> AllocWorkflowStep();